Abstract: Since traditional multiple alignment formulations are NP-hard, heuristics are commonly employed to find acceptable alignments with no guaranteed performance bound. This causes a substantial difficulty in understanding what the resulting alignment means and in assessing the quality of these alignments. We propose an alternative formulation of multiple alignment based on the idea of finding a multiple alignment of k sequences which preserves k-1 pairwise alignments as specified by edges of a given tree. Although it is well known that such a preserving alignment always exists, it did not become a mainstream method for multiple alignment since it seems that a lot of information is lost from ignoring pairwise similarities outside the tree. In contrast, by using pairwise alignments that incorporate consistency information from other sequences, we show that it is possible to obtain very good accuracy with the preserving alignment formulation. We show that a reasonable objective function to use is to find the shortest preserving alignment, and, by a reduction to a graph-theoretic problem, that the problem of finding the shortest preserving multiple alignment can be solved in polynomial time.

Short Bio: Sing-Hoi Sze is an assistant professor of computer science and of biochemistry & biophysics at Texas A&M University. Before joining Texas A&M in fall 2002, he was a postdoctoral research associate at the University of California, San Diego. He received his Ph.D. in computer science from the University of Southern California in 2000. His research focuses on the application of computer science techniques, most notably
graph-theoretic techniques, to solve problems in biology.