A new method that simultaneously aligns and reconstructs ancestral sequences for any number of homologous sequences, when the phylogeny is given

Among the fundamental problems in molecular evolution and in the analysisof homologous sequences are alignment, phylogeny reconstruction, and thereconstruction of ancestral sequences. This paper presents a fast, combinedsolution to these problems. The new algorithm gives an approximation to theminimal history in terms of a distance function on sequences. The distancefunction on sequences is a minimal weighted path length constructed fromsubstitutions and insertions-deletions of segments of any length.Substitutions are weighted with an arbitrary metric on the set ofnucleotides or amino acids, and indels are weighted with a gap penaltyfunction of the form gk = a + (bxk), where k is the length of the indel anda and b are two positive numbers. A novel feature is the introduction ofthe concept of sequence graphs and a generalization of the traditionaldynamic sequence comparison algorithm to the comparison of sequence graphs.Sequence graphs ease several computational problems. They are used torepresent large sets of sequences that can then be compared simultaneously.Furthermore, they allow the handling of multiple, equally good, alignments,where previous methods were forced to make arbitrary choices. A programwritten in C implemented this method; it was tested first on 22 5S RNAsequences.