{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,15]],"date-time":"2026-07-15T12:12:10Z","timestamp":1784117530147,"version":"3.55.0"},"reference-count":26,"publisher":"Oxford University Press (OUP)","issue":"8","license":[{"start":{"date-parts":[[2016,10,2]],"date-time":"2016-10-02T00:00:00Z","timestamp":1475366400000},"content-version":"vor","delay-in-days":656,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015,4,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: 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.<\/jats:p>\n               <jats:p>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 \u223c2-fold increase in speed without a large decrease in search sensitivity. When we measured with metagenomic data, GHOSTZ is \u223c2.2\u20132.8 times faster than RAPSearch and is \u223c185\u2013261 times faster than BLASTX.<\/jats:p>\n               <jats:p>Availability and implementation: The source code is freely available for download at http:\/\/www.bi.cs.titech.ac.jp\/ghostz\/<\/jats:p>\n               <jats:p>Contact: \u00a0akiyama@cs.titech.ac.jp<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btu780","type":"journal-article","created":{"date-parts":[[2014,11,29]],"date-time":"2014-11-29T02:15:47Z","timestamp":1417227347000},"page":"1183-1190","source":"Crossref","is-referenced-by-count":38,"title":["Faster sequence homology searches by clustering subsequences"],"prefix":"10.1093","volume":"31","author":[{"given":"Shuji","family":"Suzuki","sequence":"first","affiliation":[{"name":"1 Graduate School of Information Science and Engineering, Tokyo Institute of Technology and 2Education Academy of Computational Life Sciences (ACLS), Tokyo Institute of Technology, Tokyo 152-8550, Japan"},{"name":"1 Graduate School of Information Science and Engineering, Tokyo Institute of Technology and 2Education Academy of Computational Life Sciences (ACLS), Tokyo Institute of Technology, Tokyo 152-8550, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Masanori","family":"Kakuta","sequence":"additional","affiliation":[{"name":"1 Graduate School of Information Science and Engineering, Tokyo Institute of Technology and 2Education Academy of Computational Life Sciences (ACLS), Tokyo Institute of Technology, Tokyo 152-8550, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Takashi","family":"Ishida","sequence":"additional","affiliation":[{"name":"1 Graduate School of Information Science and Engineering, Tokyo Institute of Technology and 2Education Academy of Computational Life Sciences (ACLS), Tokyo Institute of Technology, Tokyo 152-8550, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yutaka","family":"Akiyama","sequence":"additional","affiliation":[{"name":"1 Graduate School of Information Science and Engineering, Tokyo Institute of Technology and 2Education Academy of Computational Life Sciences (ACLS), Tokyo Institute of Technology, Tokyo 152-8550, Japan"},{"name":"1 Graduate School of Information Science and Engineering, Tokyo Institute of Technology and 2Education Academy of Computational Life Sciences (ACLS), Tokyo Institute of Technology, Tokyo 152-8550, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2014,12,16]]},"reference":[{"key":"2023051309020907500_btu780-B1","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1016\/S0022-2836(05)80360-2","article-title":"Basic local alignment search tool","volume":"215","author":"Altschul","year":"1990","journal-title":"J. Mol. Biol."},{"key":"2023051309020907500_btu780-B2","doi-asserted-by":"crossref","first-page":"3389","DOI":"10.1093\/nar\/25.17.3389","article-title":"Gapped BLAST and PSI-BLAST: a new generation of protein database search programs","volume":"25","author":"Altschul","year":"1997","journal-title":"Nucleic Acids Res."},{"key":"2023051309020907500_btu780-B3","doi-asserted-by":"crossref","first-page":"5101","DOI":"10.1111\/j.1742-4658.2005.04945.x","article-title":"Protein database searches using compositionally adjusted substitution matrices","volume":"272","author":"Altschul","year":"2005","journal-title":"FEBS J."},{"key":"2023051309020907500_btu780-B4","doi-asserted-by":"crossref","first-page":"i283","DOI":"10.1093\/bioinformatics\/btt214","article-title":"Compressive genomics for protein databases","volume":"29","author":"Daniels","year":"2013","journal-title":"Bioinformatics"},{"key":"2023051309020907500_btu780-B5","doi-asserted-by":"crossref","first-page":"D211","DOI":"10.1093\/nar\/gkp985","article-title":"The pfam protein families database","volume":"38","author":"Finn","year":"2010","journal-title":"Nucleic Acids Res."},{"key":"2023051309020907500_btu780-B6","doi-asserted-by":"crossref","first-page":"3150","DOI":"10.1093\/bioinformatics\/bts565","article-title":"CD-HIT: accelerated for clustering the next-generation sequencing data","volume":"28","author":"Fu","year":"2012","journal-title":"Bioinformatics"},{"key":"2023051309020907500_btu780-B7","doi-asserted-by":"crossref","first-page":"243","DOI":"10.4056\/sigs.1433550","article-title":"Meeting report: the terabase metagenomics workshop and the vision of an Earth microbiome project","volume":"3","author":"Gilbert","year":"2010","journal-title":"Stand. Genomic Sci."},{"key":"2023051309020907500_btu780-B8","first-page":"656","article-title":"BLAT\u2013the BLAST-like alignment tool","volume":"12","author":"Kent","year":"2002","journal-title":"Genome Res."},{"key":"2023051309020907500_btu780-B9","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1093\/dnares\/dsm018","article-title":"Comparative metagenomics revealed commonly enriched gene sets in human gut microbiomes","volume":"14","author":"Kurokawa","year":"2007","journal-title":"DNA Res."},{"key":"2023051309020907500_btu780-B10","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1038\/nmeth.1923","article-title":"Fast gapped-read alignment with Bowtie 2","volume":"9","author":"Langmead","year":"2012","journal-title":"Nat. Methods"},{"key":"2023051309020907500_btu780-B11","doi-asserted-by":"crossref","first-page":"R25","DOI":"10.1186\/gb-2009-10-3-r25","article-title":"Ultrafast and memory-efficient alignment of short DNA sequences to the human genome","volume":"10","author":"Langmead","year":"2009","journal-title":"Genome Biol."},{"key":"2023051309020907500_btu780-B12","doi-asserted-by":"crossref","first-page":"1754","DOI":"10.1093\/bioinformatics\/btp324","article-title":"Fast and accurate short read alignment with Burrows-Wheeler transform","volume":"25","author":"Li","year":"2009","journal-title":"Bioinformatics"},{"key":"2023051309020907500_btu780-B13","doi-asserted-by":"crossref","first-page":"589","DOI":"10.1093\/bioinformatics\/btp698","article-title":"Fast and accurate long-read alignment with Burrows-Wheeler transform","volume":"26","author":"Li","year":"2010","journal-title":"Bioinformatics"},{"key":"2023051309020907500_btu780-B14","doi-asserted-by":"crossref","first-page":"1658","DOI":"10.1093\/bioinformatics\/btl158","article-title":"CD-HIT: a fast program for clustering and comparing large sets of protein or nucleotide sequences","volume":"22","author":"Li","year":"2006","journal-title":"Bioinformatics"},{"key":"2023051309020907500_btu780-B15","doi-asserted-by":"crossref","first-page":"935","DOI":"10.1137\/0222058","article-title":"Suffix arrays: a new method for on-line string searches","volume":"22","author":"Manber","year":"1993","journal-title":"SIAM J. Comput."},{"key":"2023051309020907500_btu780-B16","doi-asserted-by":"crossref","first-page":"986","DOI":"10.1002\/prot.20881","article-title":"Accuracy of sequence alignment and fold assessment using reduced amino acid alphabets","volume":"63","author":"Melo","year":"2006","journal-title":"Proteins"},{"key":"2023051309020907500_btu780-B17","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1093\/protein\/13.3.149","article-title":"Simplified amino acid alphabets for protein fold recognition and implications for folding","volume":"13","author":"Murphy","year":"2000","journal-title":"Protein Eng."},{"key":"2023051309020907500_btu780-B18","doi-asserted-by":"crossref","first-page":"635","DOI":"10.1016\/0888-7543(91)90071-L","article-title":"Searching protein sequence libraries: comparison of the sensitivity and selectivity of the Smith-Waterman and FASTA algorithms","volume":"11","author":"Pearson","year":"1991","journal-title":"Genomics"},{"key":"2023051309020907500_btu780-B19","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1038\/nature08821","article-title":"A human gut microbial gene catalogue established by metagenomic sequencing","volume":"464","author":"Qin","year":"2010","journal-title":"Nature"},{"key":"2023051309020907500_btu780-B20","doi-asserted-by":"crossref","first-page":"631","DOI":"10.1126\/science.278.5338.631","article-title":"A genomic perspective on protein families","volume":"278","author":"Tatusov","year":"1997","journal-title":"Science"},{"key":"2023051309020907500_btu780-B21","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1186\/1471-2105-4-41","article-title":"The COG database: an updated version includes eukaryotes","volume":"4","author":"Tatusov","year":"2003","journal-title":"BMC Bioinformatics"},{"key":"2023051309020907500_btu780-B22","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1038\/nature11234","article-title":"Structure, function and diversity of the healthy human microbiome","volume":"486","author":"The Human Microbiome Project Consortium","year":"2012","journal-title":"Nature"},{"key":"2023051309020907500_btu780-B23","doi-asserted-by":"crossref","first-page":"1027","DOI":"10.1038\/nature05414","article-title":"An obesity-associated gut microbiome with increased capacity for energy harvest","volume":"444","author":"Turnbaugh","year":"2006","journal-title":"Nature"},{"key":"2023051309020907500_btu780-B24","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1093\/bioinformatics\/btq644","article-title":"GPU-BLAST: using graphics processors to accelerate protein sequence alignment","volume":"27","author":"Vouzis","year":"2011","journal-title":"Bioinformatics"},{"key":"2023051309020907500_btu780-B25","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1186\/1471-2105-12-159","article-title":"RAPSearch: a fast protein similarity search tool for short reads","volume":"12","author":"Ye","year":"2011","journal-title":"BMC Bioinformatics"},{"key":"2023051309020907500_btu780-B26","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1093\/bioinformatics\/btr595","article-title":"RAPSearch2: a fast and memory-efficient protein similarity search tool for next-generation sequencing data","volume":"28","author":"Zhao","year":"2012","journal-title":"Bioinformatics"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/31\/8\/1183\/50306286\/bioinformatics_31_8_1183.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/31\/8\/1183\/50306286\/bioinformatics_31_8_1183.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,13]],"date-time":"2023-05-13T09:03:28Z","timestamp":1683968608000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/31\/8\/1183\/212151"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,12,16]]},"references-count":26,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2015,4,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btu780","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2015,4,15]]},"published":{"date-parts":[[2014,12,16]]}}}