Unifying evolutionary and thermodynamic information for RNA folding of multiple alignments

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

Highly conserved substructures are under strong evolutionary pressure, possibly caused by interactions with bound molecules or other functional constraints. As mentioned in the Introduction section, these substructures cannot be accounted for in thermodynamic folding algorithms. We refer to them as a reliably conserved substructure rel , which is defined as follows. A substructure is a structure that fixes only some of the positions in a sequence, hence being a partial structure. A partial structure p is a tuple ðB; SÞ consisting of a set of base pairs B and a set of single-stranded positions S such that no single-stranded position in S is part of a base pair in B. Then, a partial structure p is a substructure of a structure if B and S sgðÞ. The reliably conserved substructure rel is a substructure of that is determined by the evolutionarily highly reliable positions. They are selected by using thresholds on the reliability scores of single-stranded (p threshold ss ) and base-paired positions (p threshold bp ). We get rel by using a Nussinov-style approach with the additional condition that There are two possible approaches to determine these thresholds. First, they can be estimated through parameter tuning using a data set of known RNA families to predict RNA structures most similar to their structure annotations (see Result section). Second, a statistical approach can be applied by determining positions whose reliability is significantly better than the average (see Supplementary Material). Our observation was that in practice the first approach worked better than the second.