Article

Comparing RNA structures with biologically relevant operations cannot be done without strong combinatorial restrictions

Authors:

Guillaume Blin,

Sylvie Hamel,

Stéphane VialetteAuthors Info & Claims

WALCOM'10: Proceedings of the 4th international conference on Algorithms and Computation

Pages 149 - 160

https://doi.org/10.1007/978-3-642-11440-3_14

Published: 10 February 2010 Publication History

Abstract

Arc-annotated sequences are useful for representing structural information of RNAs and have been extensively used for comparing RNA structures in both terms of sequence and structural similarities. Among the many paradigms referring to arc-annotated sequences and RNA structures comparison (see [2] for more details), the most important one is the general edit distance. The problem of computing an edit distance between two non-crossing arc-annotated sequences was introduced in [5]. The introduced model uses edit operations that involve either single letters or pairs of letters (never considered separately) and is solvable in polynomial-time [12].

To account for other possible RNA structural evolutionary events, new edit operations, allowing to consider either silmutaneously or separately letters of a pair were introduced in [9]; unfortunately at the cost of computational tractability. It has been proved that comparing two RNA secondary structures using a full set of biologically relevant edit operations is NP-complete. Nevertheless, in [8], the authors have used a strong combinatorial restriction in order to compare two RNA stem-loops with a full set of biologically relevant edit operations; which have allowed them to design a polynomial-time and space algorithm for comparing general secondary RNA structures.

In this paper we will prove theoretically that comparing two RNA structures using a full set of biologically relevant edit operations cannot be done without strong combinatorial restrictions.

References

[1]

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)

Digital Library

Google Scholar

[2]

Blin, G., Denise, A., Dulucq, S., Herrbach, C., Touzet, H.: Alignment of RNA structures. IEEE/ACM Transactions on Computational Biology and Bioinformatics (2008) (to appear)

Digital Library

Google Scholar

[3]

Blin, G., Fertin, G., Herry, G., Vialette, S.: Comparing RNA structures: Towards an intermediate model between the edit and the lapcs problems. In: Sagot, M.- F., Walter, M.E.M.T. (eds.) BSB 2007. LNCS (LNBI), vol. 4643, pp. 101-112. Springer, Heidelberg (2007)

Digital Library

Google Scholar

[4]

Blin, G., Fertin, G., Rusu, I., Sinoquet, C.: Extending the hardness of RNA secondary structure comparison. In: Chen, B., Paterson, M., Zhang, G. (eds.) ESCAPE 2007. LNCS, vol. 4614, pp. 140-151. Springer, Heidelberg (2007)

Digital Library

Google Scholar

[5]

Evans, P.: Algorithms and Complexity for Annotated Sequences Analysis. PhD thesis, University of Victoria (1999)

Digital Library

Google Scholar

[6]

Garey, M.R., Johnson, D.S.: Computers and Intractability: a guide to the theory of NP-completeness. W.H. Freeman, New York (1979)

Digital Library

Google Scholar

[7]

Gramm, J., Guo, J., Niedermeier, R.: Pattern matching for arc-annotated sequences. ACM Transactions on Algorithms 2(1), 44-65 (2006) (to appear)

Digital Library

Google Scholar

[8]

Guignon, V., Chauve, C., Hamel, S.: An edit distance between RNA stem-loops. In: Consens, M.P., Navarro, G. (eds.) SPIRE 2005. LNCS, vol. 3772, pp. 335-347. Springer, Heidelberg (2005)

Digital Library

Google Scholar

[9]

Jiang, T., Lin, G., Ma, B., Zhang, K.: A general edit distance between RNA structures. Journal of Computational Biology 9(2), 371-388 (2002)

Crossref

Google Scholar

[10]

Jiang, T., Lin, G., Ma, B., Zhang, K.: The longest common subsequence problem for arc-annotated sequences. Journal of Dicrete Algorithms, 257-270 (2004)

Google Scholar

[11]

Lin, G., Chen, Z.-Z., jiang, T., Wen, J.: The longest common subsequence problem for sequences with nested arc annotations. Journal of Computer and System Sciences 65, 465-480 (2002)

Digital Library

Google Scholar

[12]

Zhang, K., Shasha, D.: Simple fast algorithms for the editing distance between trees and related problems. SIAM Journal of Computing 18(6), 1245-1262 (1989)

Digital Library

Google Scholar

Cited By

View all

Blin GJiang MVialette S(2012)The longest common subsequence problem with crossing-free arc-annotated sequencesProceedings of the 19th international conference on String Processing and Information Retrieval10.1007/978-3-642-34109-0_14(130-142)Online publication date: 21-Oct-2012
https://dl.acm.org/doi/10.1007/978-3-642-34109-0_14

Comparing RNA structures with biologically relevant operations cannot be done without strong combinatorial restrictions
1. Applied computing
  1. Life and medical sciences
2. Theory of computation

Recommendations

Comparing RNA structures: towards an intermediate model between the edit and the LAPCS problems
BSB'07: Proceedings of the 2nd Brazilian conference on Advances in bioinformatics and computational biology

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 ...
Predicting pseudoknotted structures across two RNA sequences

Motivation: Laboratory RNA structure determination is demanding and costly and thus, computational structure prediction is an important task. Single sequence methods for RNA secondary structure prediction are limited by the accuracy of the underlying ...
Combinatorial RNA Design: Designability and Structure-Approximating Algorithm in Watson---Crick and Nussinov---Jacobson Energy Models

We consider the Combinatorial RNA Design problem, a minimal instance of RNA design where one must produce an RNA sequence that adopts a given secondary structure as its minimal free-energy structure. We consider two free-energy models where the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

WALCOM'10: Proceedings of the 4th international conference on Algorithms and Computation

February 2010

304 pages

ISBN:3642114393

Editors:
Md. Saidur Rahman
Department of Computer Science and Engineering, Bangladesh University of Engineering and Technology (BUET), Dhaka, Bangladesh
,
Satoshi Fujita
Graduate School of Engineering, Department of Information Engineering, Hiroshima University, Kagamiyama 1-4-1, Higashi-Hiroshima, Japan

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 10 February 2010

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Blin GJiang MVialette S(2012)The longest common subsequence problem with crossing-free arc-annotated sequencesProceedings of the 19th international conference on String Processing and Information Retrieval10.1007/978-3-642-34109-0_14(130-142)Online publication date: 21-Oct-2012
https://dl.acm.org/doi/10.1007/978-3-642-34109-0_14

Abstract

References

Cited By

Recommendations

Comparing RNA structures: towards an intermediate model between the edit and the LAPCS problems

Predicting pseudoknotted structures across two RNA sequences

Combinatorial RNA Design: Designability and Structure-Approximating Algorithm in Watson---Crick and Nussinov---Jacobson Energy Models

Comments

Information

Published In

Sponsors

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations