Rfold: an exact algorithm for computing local base pairing probabilities.
BACKGROUND
Base pairing probability matrices have been frequently used for the analyses of structural RNA sequences. Recently, there has been a growing need for computing these probabilities for long DNA sequences by constraining the maximal span of base pairs to a limited value. However, none of the existing programs can exactly compute the base pairing probabilities associated with the energy model of secondary structures under such a constraint.


RESULTS
We present an algorithm that exactly computes the base pairing probabilities associated with the energy model under the constraint on the maximal span W of base pairs. The complexity of our algorithm is given by O(NW2) in time and O(N+W2) in memory, where N is the sequence length. We show that our algorithm has a higher sensitivity to the true base pairs as compared to that of RNAplfold. We also present an algorithm that predicts a mutually consistent set of local secondary structures by maximizing the expected accuracy function. The comparison of the local secondary structure predictions with those of RNALfold indicates that our algorithm is more accurate. Our algorithms are implemented in the software named 'Rfold.'


BACKGROUND
The C++ source code of the Rfold software and the test dataset used in this study are available at http://www.ncrna.org/software/Rfold/.
Kiryu
Hisanori
H
Computational Biology Research Center, National Institute of Advanced Industrial Science and Technology (AIST), 2-42 Aomi, Koto-ku, Tokyo, Japan. kiryu-h@aist.go.jp
Kin
Taishin
T
Asai
Kiyoshi
K
D000465:Algorithms; D020029:Base Pairing / Q000235:genetics*; D001483:Base Sequence; D003198:Computer Simulation; D008956:Models, Chemical; D008957:Models, Genetic; D015233:Models, Statistical; D008969:Molecular Sequence Data; D022661:RNA, Untranslated / Q000737:chemistry* / Q000235:genetics*; D017423:Sequence Analysis, RNA / Q000379:methods*; D012984:Software
D022661:RNA, Untranslated