What Makes the Arc-Preserving Subsequence Problem Hard?

  • Guillaume Blin
  • Guillaume Fertin
  • Romeo Rizzi
  • Stéphane Vialette
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3680)


In molecular biology, RNA structure comparison and motif search are of great interest for solving major problems such as phylogeny reconstruction, prediction of molecule folding and identification of common functions. RNA structures can be represented by arc-annotated sequences (primary sequence along with arc annotations), and this paper mainly focuses on the so-called arc-preserving subsequence (APS) problem where, given two arc-annotated sequences (S,P) and (T,Q), we are asking whether (T, Q) can be obtained from (S, P) by deleting some of its bases (together with their incident arcs, if any). In previous studies, this problem has been naturally divided into subproblems reflecting the intrinsic complexity of the arc structures. We show that APS(Crossing, Plain) is NP-complete, thereby answering an open problem posed in . Furthermore, to get more insight into where the actual border between the polynomial and the NP-complete cases lies, we refine the classical subproblems of the APS problem in much the same way as in  and prove that both APS \((\{\sqsubset, \between\}, \emptyset)\) and APS \((\{<, \between\}, \emptyset)\) are NP-complete. We end this paper by giving some new positive results, namely showing that APS \((\{\between\}, \emptyset)\) and APS( \((\{\between\}, \{\between\})\) are polynomial time.


RNA structures Arc-Preserving Subsequence problem Computational complexity 


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Alber, J., Gramm, J., Guo, J., Niedermeier, R.: Towards optimally solving the longest common subsequence problem for sequences with nested arc annotations in linear time. In: Apostolico, A., Takeda, M. (eds.) CPM 2002. LNCS, vol. 2373, pp. 99–114. Springer, Heidelberg (2002)CrossRefGoogle Scholar
  2. 2.
    Alber, J., Gramm, J., Guo, J., Niedermeier, R.: Computing the similarity of two sequences with nested arc annotations. Theoretical Computer Science 312(2-3), 337–358 (2004)zbMATHCrossRefMathSciNetGoogle Scholar
  3. 3.
    Billoud, B., Guerrucci, M.-A., Masselot, M., Deutsch, J.S.: Cirripede phylogeny using a novel approach: Molecular morphometrics. Molecular Biology and Evolution 19, 138–148 (2000)Google Scholar
  4. 4.
    Caetano-Anolls, G.: Tracing the evolution of RNA structure in ribosomes. Nucl. Acids. Res. 30, 2575–2587 (2002)CrossRefGoogle Scholar
  5. 5.
    Chaia, W., Stewart, V.: RNA Sequence Requirements for NasR-mediated, Nitrate-responsive Transcription Antitermination of the Klebsiella oxytoca M5al nasF Operon Leader. Journal of Molecular Biology 292, 203–216 (1999)CrossRefGoogle Scholar
  6. 6.
    Evans, P.: Algorithms and Complexity for Annotated Sequence Analysis. PhD thesis, U. Victoria (1999)Google Scholar
  7. 7.
    Evans, P.: Finding common subsequences with arcs and pseudoknots. In: Crochemore, M., Paterson, M. (eds.) CPM 1999. LNCS, vol. 1645, pp. 270–280. Springer, Heidelberg (1999)CrossRefGoogle Scholar
  8. 8.
    Farris, A.D., Koelsch, G., Pruijn, G.J., van Venrooij, W.J., Harley, J.B.: Conserved features of Y RNAs revealed by automated phylogenetic secondary structure analysis. Nucl. Acids. Res. 27, 1070–1078 (1999)CrossRefGoogle Scholar
  9. 9.
    Garey, M., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York (1979)Google Scholar
  10. 10.
    Goldman, D., Istrail, S., Papadimitriou, C.H.: Algorithmic aspects of protein structure similarity. In: Proc. of the 40th Symposium of Foundations of Computer Science (FOCS 1999), pp. 512–522 (1999)Google Scholar
  11. 11.
    Gramm, J., Guo, J., Niedermeier, R.: Pattern matching for arc-annotated sequences. In: Agrawal, M., Seth, A.K. (eds.) FSTTCS 2002. LNCS, vol. 2556, pp. 182–193. Springer, Heidelberg (2002)CrossRefGoogle Scholar
  12. 12.
    Guo, J.: Exact algorithms for the longest common subsequence problem for arc-annotated sequences. Master’s Thesis, Universitat Tubingen, Fed. Rep. of Germany (2002)Google Scholar
  13. 13.
    Hellendoorn, K., Michiels, P.J., Buitenhuis, R., Pleij, C.W.: Protonatable hairpins are conserved in the 5’-untranslated region of tymovirus RNAs. Nucl. Acids. Res. 24, 4910–4917 (1996)CrossRefGoogle Scholar
  14. 14.
    Hofacker, L., Fekete, M., Flamm, C., Huynen, M.A., Rauscher, S., Stolorz, P.E., Stadler, P.F.: Automatic detection of conserved RNA structure elements in complete RNA virus genomes. Nucl. Acids. Res. 26, 3825–3836 (1998)CrossRefGoogle Scholar
  15. 15.
    Jiang, T., Lin, G.-H., Ma, B., Zhang, K.: The longest common subsequence problem for arc-annotated sequences. In: Giancarlo, R., Sankoff, D. (eds.) CPM 2000. LNCS, vol. 1848, pp. 154–165. Springer, Heidelberg (2000)CrossRefGoogle Scholar
  16. 16.
    Juan, V., Crain, C., Wilson, S.: Evidence for evolutionarily conserved secondary structure in the H19 tumor suppressor RNA. Nucl. Acids. Res. 28, 1221–1227 (2000)CrossRefGoogle Scholar
  17. 17.
    Lancia, G., Carr, R., Walenz, B., Istrail, S.: 101 optimal PDB structure alignments: a branch-and-cut algorithm for the maximum contact map overlap problem. In: Proceedings of the 5th ACM International Conference on Computational Molecular Biology (RECOMB 2001), pp. 193–202 (2001)Google Scholar
  18. 18.
    Teunissen, S.W.M., Kruithof, M.J.M., Farris, A.D., Harley, J.B., van Venrooij, W.J., Pruijn, G.J.M.: Conserved features of Y RNAs: a comparison of experimentally derived secondary structures. Nucl. Acids. Res. 28, 610–619 (2000)CrossRefGoogle Scholar
  19. 19.
    Vialette, S.: Pattern matching over 2-intervals sets. In: Apostolico, A., Takeda, M. (eds.) CPM 2002. LNCS, vol. 2373, pp. 53–63. Springer, Heidelberg (2002)CrossRefGoogle Scholar
  20. 20.
    Vialette, S.: On the computational complexity of 2-interval pattern matching. Theoretical Computer Science 312(2-3), 223–249 (2004)zbMATHCrossRefMathSciNetGoogle Scholar
  21. 21.
    Wang, H.-Y., Lee, S.-C.: Secondary structure of mitochondrial 12S rRNA among fish and its phylogenetic applications. Molecular Biology and Evolution 19, 138–148 (2002)Google Scholar
  22. 22.
    Wuyts, J., De Rijk, P., Van de Peer, Y., Pison, G., Rousseeuw, P., De Wachter, R.: Comparative analysis of more than 3000 sequences reveals the existence of two pseudoknots in area V4 of eukaryotic small subunit ribosomal RNA. Nucl. Acids. Res. 28, 4698–4708 (2000)CrossRefGoogle Scholar
  23. 23.
    Zhang, K., Wang, L., Ma, B.: Computing the similarity between RNA structures. In: Crochemore, M., Paterson, M. (eds.) CPM 1999. LNCS, vol. 1645, pp. 281–293. Springer, Heidelberg (1999)CrossRefGoogle Scholar
  24. 24.
    Zuker, M.: RNA folding. Meth. Enzymology 180, 262–288 (1989)CrossRefGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2005

Authors and Affiliations

  • Guillaume Blin
    • 1
  • Guillaume Fertin
    • 1
  • Romeo Rizzi
    • 2
  • Stéphane Vialette
    • 3
  1. 1.LINA – FRE CNRS 2729 Université de NantesNantesFrance
  2. 2.Dipartimento di Informatica e TelecomunicazioniUniversit degli Studi di Trento Facolt di ScienzePovo – TrentoItaly
  3. 3.LRI – UMR CNRS 8623 Faculté des Sciences d’OrsayUniversité Paris-Sud, Bât 490OrsayFrance

Personalised recommendations