MULTIPLE SEQUENCE COMPARISON AND CONSISTENCY ON MULTIPARTITE GRAPHS

Calculation of dot-matrices is a widespread tool in biological sequenc e comparison. As a visual aid they are used in pairwise sequence compa rison but so far have been of little help in the simultaneous comparis on of several sequences. Viewing dot-matrices as projections of unknow n n-dimensional points we consider the multiple alignment problem (for n sequences) as an n-dimensional image reconstruction problem with no ise. 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 reg arding the number of iterations their algorithm requires and demonstra te 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(n(3) . L(3)) time (L is the length of the longest sequen ce and n is the number of sequences). This is equivalent to only one i teration of the original algorithm. We further consider the relationsh ip between consistency and transitivity and introduce a hierarchy of n otions linking consistency and transitivity. Finally applications to b iological sequence comparison will be presented. (C) 1995 Academic Pre ss, Inc.