Dataset Information

Faster sequence homology searches by clustering subsequences.

ABSTRACT: 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. 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. AVAILABILITY AND IMPLEMENTATION: The source code is freely available for download at http://www.bi.cs.titech.ac.jp/ghostz/ CONTACT: akiyama@cs.titech.ac.jp SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

SUBMITTER: Suzuki S

PROVIDER: S-EPMC4393512 | biostudies-literature | 2015 Apr

REPOSITORIES: biostudies-literature

ACCESS DATA

Publications

Faster sequence homology searches by clustering subsequences.

Suzuki Shuji S Kakuta Masanori M Ishida Takashi T Akiyama Yutaka Y

Bioinformatics (Oxford, England) 20141127 8

<h4>Motivation</h4>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.<h4>Results</h4>We developed a fast homology search method based on database subsequence clustering, and implemented it as GHOSTZ. This method clusters similar subsequences from a databas ...[more]

PMID: 25432166

Similar Datasets

Project description:BackgroundIt has been shown in a variety of organisms, including mammals, that genes that appeared recently in evolution, for example orphan genes, evolve faster than older genes. Low functional constraints at the time of origin of novel genes may explain these results. However, this observation has been recently attributed to an artifact caused by the inability of Blast to detect the fastest genes in different eukaryotic genomes. Distinguishing between these two possible explanations would be of great importance for any studies dealing with the taxon distribution of proteins and the origin of novel genes.ResultsHere we used simulations of protein sequences to examine the capacity of Blast to detect proteins of diverse evolutionary rates in the different species of an eukaryotic phylogenetic tree that included metazoans, fungi and plants. We simulated the evolution of protein genes with the same evolutionary rates than those observed in functional mammalian genes and with among-site rate heterogeneity. Under these conditions, we found that only a very small percentage of simulated ancestral eukaryotic proteins was affected by the Blast artifact. We show that the good detectability of Blast is due to the heterogeneity of protein evolutionary rates at different sites, since only a small conserved motif in a sequence suffices to detect its homologues. Our results indicate that Blast, at least when applied within eukaryotes, only misses homologues of extremely fast-evolving sequences, which are rare in the mammalian genome, as well as sequences evolving homogeneously or pseudogenes.ConclusionAlthough great care should be exercised in the recognition of remote homologues, most functional mammalian genes can be detected in eukaryotic genomes by Blast. That is, the majority of functional mammalian genes are not as fast as for not being detected in other metazoans, fungi or plants, if they had been present in these organisms. Thus, the correlation previously found between age and rate seems not to be due to a pure Blast artifact, at least for mammals. This may have important implications to understand the mechanisms by which novel genes originate.

Dataset Information

Faster sequence homology searches by clustering subsequences.

Publications

Faster sequence homology searches by clustering subsequences.

Similar Datasets

OmicsDI is part of the ELIXIR infrastructure

Tweets