THE DEFERRED PATH HEURISTIC FOR THE GENERALIZED TREE ALIGNMENT PROBLEM

Many multiple alignment methods implicitly or explicitly try to minimi ze the amount of biological change implied by an alignment, At the lev el of sequences, biological change is measured along a phylogenetic tr ee, a structure frequently being predicted only after the multiple ali gnment instead of together with it, The Generalized Tree Alignment pro blem addresses both questions simultaneously. It can formally be viewe d as a Steiner tree problem in sequence space and our approach merges a path heuristic for the construction of a Steiner tree with a cluster ing method as usually applied only to distance data, This combination is achieved using sequence graphs, a data structure for efficient repr esentation of similar sequences. Although somewhat slower in practice than an earlier method by Hein (1989) the current approach achieves si gnificantly better results in terms of the underlying scoring function , Furthermore, a variant of the algorithm is introduced that maintains a guaranteed error bound of (2 - 2/n) for n sequences.