title: Fast and accurate database homology search using upper bounds of local alignment scores.
abstract: BACKGROUND
  It is widely recognized that homology search and ortholog clustering are very useful for analyzing biological sequences. However, recent growth of sequence database size makes homolog detection difficult, and rapid and accurate methods are required.
  
  
  RESULTS
  We present a novel method for fast and accurate homology detection, assuming that the Smith-Waterman (SW) scores between all similar sequence pairs in a target database are computed and stored. In this method, SW alignment is computed only if the upper bound, which is derived from our novel inequality, is higher than the given threshold. In contrast to other methods such as FASTA and BLAST, this method is guaranteed to find all sequences whose scores against the query are higher than the specified threshold. Results of computational experiments suggest that the method is dozens of times faster than SSEARCH if genome sequence data of closely related species are available.
authors.affiliation: Bioinformatics Center, Institute for Chemical Research, Kyoto University Gokasho, Uji, Kyoto 611-0011, Japan. itoh@kuicr.kyoto-u.ac.jp
authors.forename: Masumi
authors.initials: M
authors.lastname: Itoh
authors.forename: Susumu
authors.initials: S
authors.lastname: Goto
authors.forename: Tatsuya
authors.initials: T
authors.lastname: Akutsu
authors.forename: Minoru
authors.initials: M
authors.lastname: Kanehisa
mesh_terms: D000465:Algorithms; D000595:Amino Acid Sequence; D003628:Database Management Systems; D030562:Databases, Protein; D016247:Information Storage and Retrieval / Q000379:methods*; D008969:Molecular Sequence Data; D011506:Proteins / Q000032:analysis / Q000737:chemistry*; D016415:Sequence Alignment / Q000379:methods*; D020539:Sequence Analysis, Protein / Q000379:methods*; D017386:Sequence Homology, Amino Acid; D012984:Software
chemical_list: D011506:Proteins