Multiple sequence comparison and
n-dimensional image reconstruction
Martin Vingron1 and Pavel A. Pevzner2
| (1) |
Department of Mathematics, University of Southern California, 90089-1113 Los Angeles, CA |
| (2) |
Computer Science Department, The Pennsylvania State University 333 Whitmore Laboratory, 16802 University Park, PA |
Abstract
Calculation of dot-matrices is a widespread tool in pairwise sequence comparison. In recent studies the usefulness of dot-matrices for multiple sequence alignment has been proved. 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. From this perspective we introduce and develop the filtering method due to Vingron and Argos (J. Mol. Biol. (1991), 218, pp. 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(n
3·L3) time (L is the length of the longest sequence). This is equivalent to only one iteration of the original algorithm. We also discuss applications to DNA/protein sequence comparisons.
This research was supported by grants from the National Science Foundation (DMS 90-05833, DMS 90-05833) and the National Institute of Health (GM-36230). This paper was written when P.A.P. was at the Department of Mathematics, University of Southern California, Los Angeles.
References secured to subscribers.