Pairwise RNA secondary structure alignment with conserved stem pattern.
BACKGROUND
The regulatory functions performed by non-coding RNAs are related to their 3D structures, which are, in turn, determined by their secondary structures. Pairwise secondary structure alignment gives insight into the functional similarity between a pair of RNA sequences. Numerous exact or heuristic approaches have been proposed for computational alignment. However, the alignment becomes intractable when arbitrary pseudoknots are allowed. Also, since non-coding RNAs are, in general, more conserved in structures than sequences, it is more effective to perform alignment based on the common structural motifs discovered.


RESULTS
We devised a method to approximate the true conserved stem pattern for a secondary structure pair, and constructed the alignment from it. Experimental results suggest that our method identified similar RNA secondary structures better than the existing tools, especially for large structures. It also successfully indicated the conservation of some pseudoknot features with biological significance. More importantly, even for large structures with arbitrary pseudoknots, the alignment can usually be obtained efficiently.


METHODS
Our algorithm has been implemented in a tool called PSMAlign. The source code of PSMAlign is freely available at http://homepage.cs.latrobe.edu.au/ypchen/psmalign/.
Department of Computer Science and Information Technology, La Trobe University, Melbourne, Victoria 3086, Australia.
Jimmy Ka Ho
JK
Chiu
Department of Computer Science and Information Technology, La Trobe University, Melbourne, Victoria 3086, Australia.
Yi-Ping Phoebe
YP
Chen
D000465:Algorithms; D009690:Nucleic Acid Conformation; D022661:RNA, Untranslated / Q000737:chemistry*; D016415:Sequence Alignment; D017423:Sequence Analysis, RNA / Q000379:methods; D012984:Software
D022661:RNA, Untranslated