Effective alignment of RNA pseudoknot structures
using partition function posterior log-odds scores

Yang Song, Lei Hua, Bruce A. Shapiro, Jason T.L. Wang*

*Corresponding author: wangj@njit.edu

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.

Download RKalign

  • Instructions
  • RKalign

    Datasets used and alignment results

  • Datasets
  • PDB/RNA STRAND
  • PseudoBase

    Reference

    Yang Song, Lei Hua, Bruce A. Shapiro and Jason T.L. Wang, Effective alignment of RNA pseudoknot structures using partition function posterior log-odds scores, BMC Bioinformatics 2015, 16:39