A Bayesian statistical algorithm for RNA secondary structure prediction

A Bayesian approach for predicting RNA secondary structure that addresses t he following three open issues is described: (1) the need for a representat ion of the full ensemble of probable structures; (2) the need to specify a fixed set of energy parameters; (3) the desire to make statistical inferenc es on all variables in the problem. It has recently been shown that Bayesia n inference can be employed to relax or eliminate the need to specify the p arameters of bioinformatics recursive algorithms and to give a statistical representation of the full ensemble of probable solutions with the incorpor ation of uncertainty in parameter values. In this paper, we make an initial exploration of these potential advantages of the Bayesian approach. We pre sent a Bayesian algorithm that is based on stacking energy rules but relaxe s the need to specify the parameters. The algorithm returns the exact poste rior distribution of the number of destabilizing loops, stacking energy mat rices, and secondary structures. The algorithm generates statistically repr esentative structures from the full ensemble of probable secondary structur es in exact proportion to the posterior probabilities. Once the forward rec ursions for the algorithm are completed, the backward recursive sampling ex ecutes in O(n) time, providing a very efficient approach for generating rep resentative structures. We demonstrate the utility of the Bayesian approach with several tRNA sequences. The potential of the approach for predicting RNA secondary structures and presenting alternative structures is illustrat ed with applications to the Escherichia coli tRNA(Ala) sequence and the Xen opus laevis oocyte 5S rRNA sequence. (C) 1999 Elsevier Science Ltd. All rig hts reserved.