title: Faster sequence homology searches by clustering subsequences.
abstract: BACKGROUND
  Sequence homology searches are used in various fields. New sequencing technologies produce huge amounts of sequence data, which continuously increase the size of sequence databases. As a result, homology searches require large amounts of computational time, especially for metagenomic analysis.
  
  
  RESULTS
  We developed a fast homology search method based on database subsequence clustering, and implemented it as GHOSTZ. This method clusters similar subsequences from a database to perform an efficient seed search and ungapped extension by reducing alignment candidates based on triangle inequality. The database subsequence clustering technique achieved an ∼2-fold increase in speed without a large decrease in search sensitivity. When we measured with metagenomic data, GHOSTZ is ∼2.2-2.8 times faster than RAPSearch and is ∼185-261 times faster than BLASTX.
  
  
  METHODS
  The source code is freely available for download at http://www.bi.cs.titech.ac.jp/ghostz/
  
  
  BACKGROUND
  akiyama@cs.titech.ac.jp
  
  
  BACKGROUND
  Supplementary data are available at Bioinformatics online.
authors.affiliation: Graduate School of Information Science and Engineering, Tokyo Institute of Technology and Education Academy of Computational Life Sciences (ACLS), Tokyo Institute of Technology, Tokyo 152-8550, Japan Graduate School of Information Science and Engineering, Tokyo Institute of Technology and Education Academy of Computational Life Sciences (ACLS), Tokyo Institute of Technology, Tokyo 152-8550, Japan.
authors.forename: Shuji
authors.initials: S
authors.lastname: Suzuki
authors.affiliation: Graduate School of Information Science and Engineering, Tokyo Institute of Technology and Education Academy of Computational Life Sciences (ACLS), Tokyo Institute of Technology, Tokyo 152-8550, Japan.
authors.forename: Masanori
authors.initials: M
authors.lastname: Kakuta
authors.affiliation: Graduate School of Information Science and Engineering, Tokyo Institute of Technology and Education Academy of Computational Life Sciences (ACLS), Tokyo Institute of Technology, Tokyo 152-8550, Japan.
authors.forename: Takashi
authors.initials: T
authors.lastname: Ishida
authors.affiliation: Graduate School of Information Science and Engineering, Tokyo Institute of Technology and Education Academy of Computational Life Sciences (ACLS), Tokyo Institute of Technology, Tokyo 152-8550, Japan Graduate School of Information Science and Engineering, Tokyo Institute of Technology and Education Academy of Computational Life Sciences (ACLS), Tokyo Institute of Technology, Tokyo 152-8550, Japan.
authors.forename: Yutaka
authors.initials: Y
authors.lastname: Akiyama
mesh_terms: D000465:Algorithms; D000595:Amino Acid Sequence; D000818:Animals; D016000:Cluster Analysis; D030541:Databases, Genetic; D006801:Humans; D056186:Metagenomics; D008889:Military Personnel; D008969:Molecular Sequence Data; D011381:Programming Languages; D017422:Sequence Analysis, DNA / Q000379:methods; D017385:Sequence Homology; D012984:Software; D012987:Soil / Q000737:chemistry
chemical_list: D012987:Soil