Effective alignment of RNA pseudoknot structures using partition function posterior log-odds scores. Issue 1 (December 2015)

• Record Type: Journal Article
• Authors: Song, Yang; Hua, Lei; Shapiro, Bruce; Wang, Jason
• Is Part Of: BMC bioinformatics. Volume 16:Issue 1(2015)
• Page Start: 1
• Page End: 15
• Publication Date: 2015-12
• Subjects: RNA secondary structure including pseudoknots -- Structural alignment -- Dynamic programming algorithm; Bioinformatics -- Periodicals; Computational biology -- Periodicals; 570.285
• DOI: 10.1186/s12859-015-0464-9
• Languages: English
• ISSNs: 1471-2105

Abstract

Abstract Background RNA pseudoknots play important roles in many biological processes. Previous methods for comparative pseudoknot analysis mainly focus on simultaneous folding and alignment of RNA sequences. Little work has been done to align two known RNA secondary structures with pseudoknots taking into account both sequence and structure information of the two RNAs. Results In this article we present a novel method for aligning two known RNA secondary structures with pseudoknots. We adopt the partition function methodology to calculate the posterior log-odds scores of the alignments between bases or base pairs of the two RNAs with a dynamic programming algorithm. The posterior log-odds scores are then used to calculate the expected accuracy of an alignment between the RNAs. The goal is to find an optimal alignment with the maximum expected accuracy. We present a heuristic to achieve this goal. The performance of our method is investigated and compared with existing tools for RNA structure alignment. An extension of the method to multiple alignment of pseudoknot structures is also discussed. Conclusions The method described here has been implemented in a tool named RKalign, which is freely accessible on the Internet. As more and more pseudoknots are revealed, collected and stored in public databases, we anticipate a tool like RKalign will play a significant role in data comparison, annotation, analysis, and retrieval in these databases.