Multiple sequence comparison and consistency on multipartite graphs

Calculation of dot-matrices is a widespread tool in biological sequence comparison. As a visual aid they are used in pairwise sequence comparison but so far have been of little help in the simultaneous comparison of several sequences. Viewing dot-matrices as projections of unknown n-dimensional points we consider the multiple alignment problem (for n sequences) as an n-dimensional image reconstruction problem with noise. We model this situation using a multipartite graph and introduce a notion of "consistency" on such a graph. From this perspective we introduce and develop the filtering method due to Vingron and Argos (J. Mol. Biol. 218 (1991), 33-43). We discuss a conjecture of theirs regarding the number of iterations their algorithm requires and demonstrate that this number may be large. An improved version of the original algorithm is introduced that avoids costly dot-matrix multiplications and runs in O(n3 · L3) time (L is the length of the longest sequence and n is the number of sequences). This is equivalent to only one iteration of the original algorithm. We further consider the relationship between consistency and transitivity and introduce a hierarchy of notions linking consistency and transitivity. Finally applications to biological sequence comparison will be presented.