Abstract
In the recent past, RNA structure comparison has appeared as an important field of bioinformatics. In this paper, we introduce a new and general intermediate model for comparing RNA structures: the Maximum Arc-Preserving Common Subsequence problem (or Mapcs). This new model lies between two well-known problems – namely the Longest Arc-Preserving Common Subsequence (Lapcs) and the Edit distance. After showing the relationship between Mapcs, Lapcs, Edit, and also the Maximum Linear Graph problem, we will investigate the computational complexity landscape of Mapcs, depending on the RNA structure complexity.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alber, J., Gramm, J., Guo, J., Niedermeier, R.: Computing the similarity of two sequences with nested arc annotations. Th. Comp. Science 312(2), 337–358 (2004)
Bafna, V., Muthukrishnan, S., Ravi, R.: Computing similarity between RNA strings. In: Galil, Z., Ukkonen, E. (eds.) Combinatorial Pattern Matching. LNCS, vol. 937, pp. 1–16. Springer, Heidelberg (1995)
Bernhart, F., Kainen, P.C.: The book thickness of a graph. Journal of Combinatorial Theory, Series B 27(3), 320–331 (1979)
Biedl, T., Kant, G., Kaufmann, M.: On triangulating planar graphs under the four-connectivity constraint. Algorithmica 19, 427–446 (1997)
Blin, G., Fertin, G., Rizzi, R., Vialette, S.: What makes the arc-preserving subsequence problem hard ? Trans. on Comp. Systems Biology 2, 1–36 (2005)
Blin, G., Fertin, G., Rusu, I., Sinoquet, C.: Extending the hardness of RNA secondary structure comparison. In: (ESCAPE). intErnational Symposium on Combinatorics, Algorithms, Probabilistic and Experimental methodologies. Springer, Heidelberg (to appear 2007)
Blin, G., Touzet, H.: How to compare arc-annotated sequences: The alignment hierarchy. In: Crestani, F., Ferragina, P., Sanderson, M. (eds.) SPIRE 2006. LNCS, vol. 4209, pp. 291–303. Springer, Heidelberg (2006)
Bose, P., Buss, J.F., Lubiw, A.: Pattern matching for permutations. Information Processing Letters 65(5), 277–283 (1998)
Davydov, E., Batzoglou, S.: A computational model for RNA multiple structural alignment. Theoretical Computer Science 368(3), 205–216 (2006)
Evans, P.: Algorithms and Complexity for Annotated Sequences Analysis. PhD thesis, University of Victoria (1999)
Evans, P.A.: Finding common RNA pseudoknot structures in polynomial time. In: Lewenstein, M., Valiente, G. (eds.) CPM 2006. LNCS, vol. 4009, pp. 223–232. Springer, Heidelberg (2006)
Goldman, D., Istrail, S., Papadimitriou, C.H.: Algorithmic aspects of protein structure similarity. In: Found. of Comp. Science (FOCS), pp. 512–522 (1999)
Gramm, J., Guo, J., Niedermeier, R.: Pattern matching for arc-annotated sequences. In: Agrawal, M., Seth, A.K. (eds.) FST TCS 2002. LNCS, vol. 2556, pp. 182–193. Springer, Heidelberg (2002)
Hirschberg, D.S.: The longest common subsequence problem. PhD thesis, Princeton University (1975)
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)
Kubica, M., Rizzi, R., Vialette, S., Walen, T.: Approximation of RNA multiple structural alignment. In: Lewenstein, M., Valiente, G. (eds.) CPM 2006. LNCS, vol. 4009, pp. 211–222. Springer, Heidelberg (2006)
Lin, G.H., Ma, B., Zhang, K.: Edit distance between two RNA structures. In (RECOMB). Int. Conf. on Computational Biology, pp. 211–220. ACM Press, New York (2001)
Lozano, A., Valiente, G.: String Algorithmics. In: On the maximum common embedded subtree problem for ordered trees, ch. 7, pp. 155–169. King’s College London Publications (2004)
Vialette, S.: On the computational complexity of 2-interval pattern matching problems. Theoretical Computer Science 312(2-3), 223–249 (2004)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Blin, G., Fertin, G., Herry, G., Vialette, S. (2007). Comparing RNA Structures: Towards an Intermediate Model Between the Edit and the Lapcs Problems. In: Sagot, MF., Walter, M.E.M.T. (eds) Advances in Bioinformatics and Computational Biology. BSB 2007. Lecture Notes in Computer Science(), vol 4643. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-73731-5_10
Download citation
DOI: https://doi.org/10.1007/978-3-540-73731-5_10
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-73730-8
Online ISBN: 978-3-540-73731-5
eBook Packages: Computer ScienceComputer Science (R0)