Simultaneous Solution of the RNA Folding, Alignment and Protosequence Problems

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.