title: GHOSTX: an improved sequence homology search algorithm using a query suffix array and a database suffix array.
abstract: DNA sequences are translated into protein coding sequences and then further assigned to protein families in metagenomic analyses, because of the need for sensitivity. However, huge amounts of sequence data create the problem that even general homology search analyses using BLASTX become difficult in terms of computational cost. We designed a new homology search algorithm that finds seed sequences based on the suffix arrays of a query and a database, and have implemented it as GHOSTX. GHOSTX achieved approximately 131-165 times acceleration over a BLASTX search at similar levels of sensitivity. GHOSTX is distributed under the BSD 2-clause license and is available for download at http://www.bi.cs.titech.ac.jp/ghostx/. Currently, sequencing technology continues to improve, and sequencers are increasingly producing larger and larger quantities of data. This explosion of sequence data makes computational analysis with contemporary tools more difficult. We offer this tool as a potential solution to this problem.
authors.affiliation: Graduate School of Information Science and Engineering, Tokyo Institute of Technology, Meguro-ku, Tokyo, Japan.
authors.forename: Shuji
authors.initials: S
authors.lastname: Suzuki
authors.affiliation: Graduate School of Information Science and Engineering, Tokyo Institute of Technology, Meguro-ku, Tokyo, Japan.
authors.forename: Masanori
authors.initials: M
authors.lastname: Kakuta
authors.affiliation: Graduate School of Information Science and Engineering, Tokyo Institute of Technology, Meguro-ku, Tokyo, Japan.
authors.forename: Takashi
authors.initials: T
authors.lastname: Ishida
authors.affiliation: Graduate School of Information Science and Engineering, Tokyo Institute of Technology, Meguro-ku, Tokyo, Japan.
authors.forename: Yutaka
authors.initials: Y
authors.lastname: Akiyama
mesh_terms: D000465:Algorithms; D030541:Databases, Genetic; D016415:Sequence Alignment / Q000379:methods*; D017385:Sequence Homology; D012984:Software
references.citation: FEBS J. 2005 Oct;272(20):5101-9
references.pmid: 16218944
references.citation: Nature. 2006 Dec 21;444(7122):1027-31
references.pmid: 17183312
references.citation: Genomics. 1991 Nov;11(3):635-50
references.pmid: 1774068
references.citation: DNA Res. 2007 Aug 31;14(4):169-81
references.pmid: 17916580
references.citation: Genome Res. 2002 Apr;12(4):656-64
references.pmid: 11932250
references.citation: Nucleic Acids Res. 1997 Sep 1;25(17):3389-402
references.pmid: 9254694
references.citation: Bioinformatics. 2012 Jan 1;28(1):125-6
references.pmid: 22039206
references.citation: J Mol Biol. 1990 Oct 5;215(3):403-10
references.pmid: 2231712
references.citation: Nature. 2012 Jun 13;486(7402):207-14
references.pmid: 22699609
references.citation: Bioinformatics. 2011 Jan 15;27(2):182-8
references.pmid: 21088027
references.citation: Proceedings (IEEE Int Conf Bioinformatics Biomed). 2009 Nov 1;2009(1-4):83-97
references.pmid: 21278916
references.citation: Nucleic Acids Res. 2012 Jan;40(Database issue):D109-14
references.pmid: 22080510
references.citation: Nucleic Acids Res. 2000 Jan 1;28(1):27-30
references.pmid: 10592173
references.citation: BMC Bioinformatics. 2011 May 15;12:159
references.pmid: 21575167