RNA-RNA interaction prediction based on multiple sequence alignments.
BACKGROUND
Many computerized methods for RNA-RNA interaction structure prediction have been developed. Recently, O(N(6)) time and O(N(4)) space dynamic programming algorithms have become available that compute the partition function of RNA-RNA interaction complexes. However, few of these methods incorporate the knowledge concerning related sequences, thus relevant evolutionary information is often neglected from the structure determination. Therefore, it is of considerable practical interest to introduce a method taking into consideration both: thermodynamic stability as well as sequence/structure covariation.


RESULTS
We present the a priori folding algorithm ripalign, whose input consists of two (given) multiple sequence alignments (MSA). ripalign outputs (i) the partition function, (ii) base pairing probabilities, (iii) hybrid probabilities and (iv) a set of Boltzmann-sampled suboptimal structures consisting of canonical joint structures that are compatible to the alignments. Compared to the single sequence-pair folding algorithm rip, ripalign requires negligible additional memory resource but offers much better sensitivity and specificity, once alignments of suitable quality are given. ripalign additionally allows to incorporate structure constraints as input parameters.


BACKGROUND
The algorithm described here is implemented in C as part of the rip package.
Tianjin Key Laboratory of Combinatorics, Nankai University Tianjin 300071, People's Republic of China.
Andrew X
AX
Li
Manja
M
Marz
Jing
J
Qin
Christian M
CM
Reidys
D000465:Algorithms; D020029:Base Pairing; D001483:Base Sequence; D015233:Models, Statistical; D008969:Molecular Sequence Data; D012313:RNA / Q000737:chemistry* / Q000235:genetics; D016415:Sequence Alignment / Q000379:methods*; D017423:Sequence Analysis, RNA / Q000379:methods*
D012313:RNA