Unifying evolutionary and thermodynamic information for RNA folding of multiple alignments

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

PETfold takes O(L 2 ) space and OðL 3 Þ time when the number of sequences N is much smaller than the sequence length L. The most time-consuming parts of the algorithm are the calculation of evolutionarily reliabilities using Pfold (OðL 3 Þ þ OðL 2 Þ), the calculation of energy-based probabilities of N sequences using RNAfold (N Â OðL 3 Þ) and the Nussinov-style algorithm (OðL 3 Þ). In practice, the running time of PETfold is approximately twice that of Pfold and much longer than that of RNAalifold (see Table 1 for details). Major reasons for the longer runtimes are the implementation of PETfold in Perl and the external calls to Pfold and RNAfold.