next up previous
Next: Introduction

Evaluation Measures of Multiple Sequence Alignments

Gaston H. Gonnet, *Chantal Korostensky and Steve Benner
Institute for Scientific Computing
ETH Zurich, 8092 Zuerich, Switzerland
phone: ++41 1 632 74 79
e-mail: {gonnet,korosten}


Multiple sequence alignments (MSAs) are frequently used in the study of families of protein sequences or DNA/RNA sequences. They are a fundamental tool for the understanding of structure, functionality and ultimately evolution of proteins. A new algorithm, the Circular Sum (CS) method, is presented for formally evaluating the quality of an MSA. It is based on the use of a solution to the Traveling Salesman Problem, which identifies a circular tour through an evolutionary tree connecting the sequences in a protein family. With this approach the calculation of an evolutionary tree and the errors that it would introduce can be avoided altogether. The algorithm gives an upper bound, the best score that can possibly be achieved by any MSA for a given set of protein sequences. Alternatively, if presented with a specific MSA, the algorithm provides a formal score for the MSA, which serves as an absolute measure of the quality of the MSA. The CS measure yields a direct connection between an MSA and the associated evolutionary tree, which allows us to use the measure to evaluate evolutionary trees and as a tool for evaluating different methods for producing MSAs. A brief example of the last application is provided. Because it weights all evolutionary events on a tree identically, but does not require the reconstruction of a tree, the CS algorithm has advantages over the frequently used sum-of-pairs measures for scoring MSAs, which weight some evolutionary events more strongly than others. Compared to other weighted sum-of-pairs measures it has the advantage that no evolutionary tree must be constructed, because we can find a circular tour without knowing the tree.
Keywords: multiple sequence alignment, phylogenetic tree, scoring function, TSP, evolution

next up previous
Next: Introduction
Chantal Korostensky