Memory Efficient Algorithms for Structural Alignment of RNAs with Pseudoknots
Pages 161 - 168
Abstract
In this paper, we consider the problem of structural alignment of a target RNA sequence of length n and a query RNA sequence of length m with known secondary structure that may contain simple pseudoknots or embedded simple pseudoknots. The best known algorithm for solving this problem runs in O(mn^3) time for simple pseudoknot or O(mn^4) time for embedded simple pseudoknot with space complexity of O(mn^3) for both structures, which require too much memory making it infeasible for comparing noncoding RNAs (ncRNAs) with length several hundreds or more. We propose memory efficient algorithms to solve the same problem. We reduce the space complexity to O(n^3) for simple pseudoknot and O(mn^2 + n^3) for embedded simple pseudoknot while maintaining the same time complexity. We also show how to modify our algorithm to handle a restricted class of recursive simple pseudoknot which is found abundant in real data with space complexity of O(mn^2 + n^3) and time complexity of O(mn^4). Experimental results show that our algorithms are feasible for comparing ncRNAs of length more than 500.
References
[1]
S. He, C. Liu, G. Skogerbo, H. Zhao, J. Wang, T. Liu, B. Bai, Y. Zhao, and R. Chen, "Noncode v2.0: Decoding the Non-Coding," Nucleic Acids Research, vol. 36(Database), pp. D170-D172, 2007.
[2]
S. Griffiths-Jones, A. Bateman, M. Marshall, A. Khanna, and S.R. Eddy, "Rfam: An RNA Family Database," Nucleic Acids Research, vol. 31, no. 1, pp. 439-441, 2003.
[3]
S.Y. Le, J.H. Chen, and J. Maizel, "Structure and Methods: Human Genome Initiative and DNA Recombination," Chapter Efficient Searches for Unusual Folding Regions in RNA Sequences, vol. 1, pp. 127-130, 1990.
[4]
E. Rivas and S. Eddy, "Secondary Structure Alone is Generally Not Statistically Significant for the Detection of Noncoding RNAs," Bioinformatics, vol. 16, no. 7, pp. 583-605, 2000.
[5]
R. Klein and S. Eddy, "Rsearch: Finding Homologs of Single Structured RNA Sequences," BMC Bioinformatics, vol. 4, article 44, 2003.
[6]
S. Zhang, B. Hass, E. Eskin, and V. Bafna, "Searching Genomes for Noncoding RNA Using FastR," IEEE/ACM Trans. Computational Biology and Bioinformatics, vol. 2, no. 4, pp. 366-379, Oct.-Dec. 2005.
[7]
E.P. Nawrocki and S.R. Eddy, "Query-Dependent Banding (QDB) for Faster RNA Similarity Searches," PLoS Computational Biology, vol. 3, p. 15, 2007.
[8]
J. Hen and C.W. Greider, "Functional Analysis of the Pseudoknot Structure in Human Telomerase RNA," Proc. Nat'l Academy of Sciences USA, vol. 102, no. 23, pp. 8080-8085, 2005.
[9]
E. Dam, K. Pleij, and D. Draper, "Structural and Functional Aspects of RNA Pseudoknots," Biochemistry, vol. 31, no. 47, pp. 11665-11676, 1992.
[10]
P.L. Adams, M.R. Stahley, A.B. Kosek, J. Wang, and S.A. Strobel, "Crystal Structure of a Self-Splicing Group I Intron with Both Exons," Nature, vol. 430, pp. 45-50, 2004.
[11]
H. Matsui, K. Sato, and Y. Sakakibara, "Pair Stochastic Tree Adjoining Grammars for Aligning and Predicting Pseudoknot RNA Structures," Bioinformatics, vol. 21, pp. 2611-2617, 2005.
[12]
B. Han, B. Dost, V. Bafna, and S. Zhang, "Structural Alignment of Pseudoknotted RNA," J. Computational Biology, vol. 15, no. 5, pp. 489-504, 2008.
[13]
S.R. Eddy, "A Memory-Efficient Dynamic Programming Algorithm for Optimal Alignment of a Sequence to an RNA Secondary Structure," BMC Bioinformatics, vol. 3, article 18, 2002.
[14]
Y. Song, C. Liu, X. Huang, R.L. Malmberg, Y. Xu, and L. Cai, "Efficient Parameterized Algorithms for Biopolymer Structure-Sequence Alignment," IEEE/ACM Trans. Computational Biology and Bioinformatics, vol. 3, no. 4, pp. 423-432, Oct.-Dec. 2006.
[15]
D.S. Hirschberg, "A Linear Space Algorithm for Computing Maximal Common Subsequences," Comm. ACM, vol. 18, no. 6, pp. 341-343, 1975.
- Memory Efficient Algorithms for Structural Alignment of RNAs with Pseudoknots
Recommendations
An Efficient Alignment Algorithm for Searching Simple Pseudoknots over Long Genomic Sequence
Structural alignment has been shown to be an effective computational method to identify structural noncoding RNA (ncRNA) candidates as ncRNAs are known to be conserved in secondary structures. However, the complexity of the structural alignment ...
A machine learning approach for accurate annotation of noncoding RNAs
Searching genomes to locate noncoding RNA genes with known secondary structure is an important problem in bioinformatics. In general, the secondary structure of a searched noncoding RNA is defined with a structure model constructed from the structural ...
Structural alignment of RNA with complex pseudoknot structure
WABI'09: Proceedings of the 9th international conference on Algorithms in bioinformaticsThe secondary structure of an ncRNA molecule is known to play an important role in its biological functions. Aligning a known ncRNA to a target candidate to determine the sequence and structural similarity helps in identifying de novo ncRNA molecules ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Publisher
IEEE Computer Society Press
Washington, DC, United States
Publication History
Published: 01 January 2012
Published in TCBB Volume 9, Issue 1
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 85Total Downloads
- Downloads (Last 12 months)2
- Downloads (Last 6 weeks)1
Reflects downloads up to 01 Jan 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in