A local alignment metric for accelerating biosequence database search.
We introduce a metric for local sequence alignments that has utility for accelerating optimal alignment searches without loss of sensitivity. The metric's triangle inequality property permits identification of redundant database entries guaranteed to have optimal alignments to the query sequence that fall below a specified score threshold, thereby permitting comparisons to these entries to be skipped. We prove the existence of the metric for a variety of scoring systems, including the most commonly used ones, and show that a triangle inequality can be established as well for nucleotide-to-protein sequence comparisons. We discuss a database clustering and search strategy that takes advantage of the triangle inequality. The strategy permits moderate but significant acceleration of searches against the widely used "nr" protein database. It also provides a theoretically based method for database clustering in general and provides a standard against which to compare heuristic clustering strategies.
Spiro
Peter A
PA
Incyte Genomics, Inc., 3160 Porter Drive, Palo Alto, CA 94304, USA. Peter.Spiro@alumni.brown.edu
Macura
Natasa
N
D000465:Algorithms; D000595:Amino Acid Sequence; D001483:Base Sequence; D019295:Computational Biology / Q000379:methods; D003628:Database Management Systems; D030541:Databases, Genetic; D030562:Databases, Protein; D016678:Genome; D008969:Molecular Sequence Data; D016415:Sequence Alignment; D017422:Sequence Analysis, DNA; D020539:Sequence Analysis, Protein; D017386:Sequence Homology, Amino Acid; D012689:Sequence Homology, Nucleic Acid; D012984:Software