Finding common RNA pseudoknot structures in polynomial time. (English) Zbl 1228.92024
Summary: This paper presents the first polynomial time algorithm for finding common RNA substructures that include pseudoknots and similar structures. While a more general problem is known to be NP-hard, this algorithm exploits special features of RNA structures to match RNA bonds correctly in polynomial time. Although the theoretical upper bound on the algorithm’s time and space usage is high, the data-driven nature of its computation enables it to avoid computing unnecessary cases, dramatically reducing the actual running time. The algorithm works well in practice, and has been tested on sample RNA structures that include pseudoknots and pseudoknot-like tertiary structures.
MSC:
| 92C40 | Biochemistry, molecular biology |
| 92-08 | Computational methods for problems pertaining to biology |
| 68Q25 | Analysis of algorithms and problem complexity |
| 68W32 | Algorithms on strings |
| 90C39 | Dynamic programming |
References:
| [1] | Allali, J.; Sagot, M.-F., A new distance for high level RNA secondary structure comparison, IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2, 1, 3-14 (2005) |
| [2] | V. Bafna, S. Muthukrishnan, R. Ravi, Computing similarity between RNA strings, DIMACS Technical Report 96-30, 1996.; V. Bafna, S. Muthukrishnan, R. Ravi, Computing similarity between RNA strings, DIMACS Technical Report 96-30, 1996. |
| [3] | Brown, J., The ribonuclease P database, Nucleic Acids Research, 27, 314 (1999) |
| [4] | Burkard, M.; Turner, D.; Tinoco, I., Schematic diagrams of secondary and tertiary structure elements, (Gesteland, R.; Cech, T.; Atkins, J., The RNA World (1999), Cold Spring Harbor Laboratory Press: Cold Spring Harbor Laboratory Press Cold Spring Harbor, New York), 681-685 |
| [5] | Cannone, J., The comparative RNA web (CRW) site: an online database of comparative sequence and structure information for ribosomal, intron, and other RNAs, BMC Bioinformatics, 3, 15 (2002) |
| [6] | Demaine, E.; Mozes, S.; Rossman, B.; Weimann, O., An optimal decomposition algorithm for tree edit distance, (Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP 2007). Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP 2007), LNCS, vol. 4596 (2007), Springer-Verlag), 146-157 · Zbl 1171.68843 |
| [7] | Evans, P., Finding common subsequences with arcs and pseudoknots, (Proceedings of Combinatorial Pattern Matching ʼ99. Proceedings of Combinatorial Pattern Matching ʼ99, LNCS, vol. 1645 (1999), Springer-Verlag), 270-280 · Zbl 1063.68616 |
| [8] | Felden, B.; Florentz, C.; Giegé, R.; Westhof, E., A central pseudoknotted three-way junction imposes tRNA-like mimicry and the orientation of three 5′ upstream pseudoknots in the 3′ terminus of tobacco mosaic virus RNA, RNA, 2, 201-212 (1996) |
| [9] | D. Goldman, S. Istrail, C. Papadimitriou, Algorithmic aspects of protein similarity, in: Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS 99), 1999, pp. 512-521.; D. Goldman, S. Istrail, C. Papadimitriou, Algorithmic aspects of protein similarity, in: Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS 99), 1999, pp. 512-521. |
| [10] | Gramm, J., A polynomial-time algorithm for the matching of crossing contact map patterns, IEEE/ACM Transactions on Computational Biology and Bioinformatics, 1, 4, 171-180 (2004) |
| [11] | Skuzeski, J.; Bozarth, C.; Dreher, T., The turnip yellow mosaic virus tRNA-like structure cannot be replaced by generic tRNA-like elements or by heterologuous 3′ untranslated regions known to enhance mRNA expression and stability, Journal of Virology, 70, 2107-2115 (1996) |
| [12] | Vialette, S., On the computational complexity of 2-interval pattern matching problems, Theoretical Computer Science, 312, 2-3, 223-249 (2004) · Zbl 1070.68052 |
| [13] | K. Zhang, Computing similarity between RNA secondary structures, in: Proceedings of IEEE International Joint Symposia on Intelligence and Systems, 1998, pp. 126-132.; K. Zhang, Computing similarity between RNA secondary structures, in: Proceedings of IEEE International Joint Symposia on Intelligence and Systems, 1998, pp. 126-132. |
| [14] | Zhang, K.; Wang, L.; Ma, B., Computing similarity between RNA structures, (Proceedings of Combinatorial Pattern Matching ʼ99. Proceedings of Combinatorial Pattern Matching ʼ99, LNCS, vol. 1645 (1999), Springer-Verlag), 281-293 · Zbl 1063.68625 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
