Paper Info
Title
Memory Efficient Algorithms for Structural Alignment of RNAs with Pseudoknots
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.
Year
DOI
Venue
2012
10.1109/TCBB.2011.66
IEEE/ACM Trans. Comput. Biology Bioinform.
Keywords
Field
DocType
noncoding rna,computational biology,genomics,computational complexity,heuristic algorithm,memory management,molecular biophysics,macromolecules,time complexity,pseudoknot,rna,space complexity,structure alignment,secondary structure,structural alignment,bioinformatics
Structural alignment,Pseudoknot,Computer science,Algorithm,Theoretical computer science,Memory management,Molecular biophysics,Bioinformatics,Time complexity,Protein secondary structure,Recursion,Computational complexity theory
Journal
Volume
Issue
ISSN
9
1
1545-5963
Citations 
PageRank 
References 
3
0.41
10
Authors
4
Name
Order
Citations
PageRank
Thomas K. F. Wong1899.80
Y. -S. Chiu261.13
Tak-Wah Lam31860164.96
Siu-ming Yiu4102692.90