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 n3N and storage n2N. Incorporating a “cutting corners” constraint against biologically unlikely alignments reduces these requirements so that they are proportional to n³ and n², respectively, for fixed N.