Unifying evolutionary and thermodynamic information for RNA folding of multiple alignments

Seemann, Stefan E.; Gorodkin, Jan; Backofen, Rolf

Before we can extend the model, we have to more precisely define what it means that two sequences can adopt the same consensus structure under a given alignment matrix A ¼ ða u;l Þ, where u denotes the number of sequences and l the number of alignment columns. This is necessary because a consensus structure is defined as a set of paired alignment columns. Hence, let n be the number of sequences and let f u A ðiÞ ¼ l be the alignment column corresponding to position i in sequence s u . The mapping f u A can be extended to structures: f u A ðÞ ¼ fðf u A ðiÞ; f u A ðjÞÞ j ði; jÞ 2 g: In the previous section, we searched for a consensus structure that had the maximal expected overlap with other possible consensus structures defined by the probabilistic evolutionary model, thus minimizing the expected number of evolutionary prediction errors. Now, we also want to evaluate the expected overlap for each sequence s with its ensemble of structures as given by the energy model. This implies that for each sequence s, we consider the distribution of structures as introduced by McCaskill (28). For this purpose, let p s k;l ¼ P ðk;lÞ2 Pr½js be the base pair probabilities for a sequence s as calculated by, e.g. RNAfold Àp (1) and q s k ¼ 1 À P l6 ¼k p s k;l the probability for position k being single stranded in sequence s. The combined expected overlap now consists of two parts, generally weighted with 1 for the conservation part and for the thermodynamic overlap: