Simultaneous Solution of the RNA Folding, Alignment and Protosequence Problems

Source abstract

The alignment of finite sequences, the inference of ribonucleic acid secondary structures (folding), and the reconstruction of ancestral sequences on a phylogenetic tree, are three problems which have dynamic programming solutions, which we formulate in a common mathematical framework. Combining the objective functions for alignment (parsimony, or minimal mutations) and folding (free energy), we present an algorithm which solves all three problems simultaneously for a set of N sequences of length n in time proportional to $n^{3N}$ and storage $n^{2N}$. Incorporating a “cutting corners” constraint against biologically unlikely alignments reduces these requirements so that they are proportional to $n^{3}$ and $n^{2}$, respectively, for fixed N.