Indexing Strategies for Rapid Searches of Short Words in Genome Sequences

Overview

Journal PLoS One

Specialties General Medicine
Science

Date 2007 Jun 28

PMID 17593978

Citations 50

Authors

Christian Iseli

Giovanna Ambrosini

Philipp Bucher

C Victor Jongeneel

Affiliations

Soon will be listed here.

Abstract

Searching for matches between large collections of short (14-30 nucleotides) words and sequence databases comprising full genomes or transcriptomes is a common task in biological sequence analysis. We investigated the performance of simple indexing strategies for handling such tasks and developed two programs, fetchGWI and tagger, that index either the database or the query set. Either strategy outperforms megablast for searches with more than 10,000 probes. FetchGWI is shown to be a versatile tool for rapidly searching multiple genomes, whose performance is limited in most cases by the speed of access to the filesystem. We have made publicly available a Web interface for searching the human, mouse, and several other genomes and transcriptomes with oligonucleotide queries.

Citing Articles

Click editing enables programmable genome writing using DNA polymerases and HUH endonucleases.

Ferreira da Silva J, Tou C, King E, Eller M, Rufino-Ramos D, Ma L Nat Biotechnol. 2024; .

PMID: 39039307 PMC: 11751136. DOI: 10.1038/s41587-024-02324-x.

Effect of C-type lectin 16 on dengue virus infection in salivary glands.

Chang Y, Liu W, Fang P, Li J, Liu K, Huang J PNAS Nexus. 2024; 3(5):pgae188.

PMID: 38813522 PMC: 11134184. DOI: 10.1093/pnasnexus/pgae188.

Click editing enables programmable genome writing using DNA polymerases and HUH endonucleases.

Ferreira da Silva J, Tou C, King E, Eller M, Ma L, Rufino-Ramos D bioRxiv. 2023; .

PMID: 37745481 PMC: 10515857. DOI: 10.1101/2023.09.12.557440.

A cis-regulatory sequence of the selector gene vestigial drives the evolution of wing scaling in Drosophila species.

Farfan-Pira K, Martinez-Cuevas T, Evans T, Nahmad M J Exp Biol. 2023; 226(10).

PMID: 37078652 PMC: 10234621. DOI: 10.1242/jeb.244692.

CRISPR mediated transactivation in the human disease vector Aedes aegypti.

Bui M, Dalla Benetta E, Dong Y, Zhao Y, Yang T, Li M PLoS Pathog. 2023; 19(1):e1010842.

PMID: 36656895 PMC: 9888728. DOI: 10.1371/journal.ppat.1010842.

References

Ning Z, Cox A, Mullikin J . SSAHA: a fast search method for large DNA databases. Genome Res. 2001; 11(10):1725-9. PMC: 311141. DOI: 10.1101/gr.194201. View

Iseli C, Stevenson B, de Souza S, Samaia H, Camargo A, Buetow K . Long-range heterogeneity at the 3' ends of human mRNAs. Genome Res. 2002; 12(7):1068-74. PMC: 186619. DOI: 10.1101/gr.62002. View

Wheeler D, Barrett T, Benson D, Bryant S, Canese K, Chetvernin V . Database resources of the National Center for Biotechnology Information. Nucleic Acids Res. 2006; 35(Database issue):D5-12. PMC: 1781113. DOI: 10.1093/nar/gkl1031. View

Liu G, Loraine A, Shigeta R, Cline M, Cheng J, Valmeekam V . NetAffx: Affymetrix probesets and annotations. Nucleic Acids Res. 2003; 31(1):82-6. PMC: 165568. DOI: 10.1093/nar/gkg121. View

Lal A, Sui I, Riggins G . Serial analysis of gene expression: probing transcriptomes for molecular targets. Curr Opin Mol Ther. 2009; 1(6):720-6. View

Pruitt K, Tatusova T, Maglott D . NCBI Reference Sequence (RefSeq): a curated non-redundant sequence database of genomes, transcripts and proteins. Nucleic Acids Res. 2004; 33(Database issue):D501-4. PMC: 539979. DOI: 10.1093/nar/gki025. View

Brenner S, Williams S, Vermaas E, Storck T, Moon K, McCollum C . In vitro cloning of complex mixtures of DNA on microbeads: physical separation of differentially expressed cDNAs. Proc Natl Acad Sci U S A. 2000; 97(4):1665-70. PMC: 26493. DOI: 10.1073/pnas.97.4.1665. View

Schmid C, Perier R, Praz V, Bucher P . EPD in its twentieth year: towards complete promoter coverage of selected model organisms. Nucleic Acids Res. 2005; 34(Database issue):D82-5. PMC: 1347508. DOI: 10.1093/nar/gkj146. View

Kuhn R, Karolchik D, Zweig A, Trumbower H, Thomas D, Thakkapallayil A . The UCSC genome browser database: update 2007. Nucleic Acids Res. 2006; 35(Database issue):D668-73. PMC: 1669757. DOI: 10.1093/nar/gkl928. View

10.

Stalker J, Gibbins B, Meidl P, Smith J, Spooner W, Hotz H . The Ensembl Web site: mechanics of a genome browser. Genome Res. 2004; 14(5):951-5. PMC: 479125. DOI: 10.1101/gr.1863004. View

11.

Zhang Z, Schwartz S, Wagner L, Miller W . A greedy algorithm for aligning DNA sequences. J Comput Biol. 2000; 7(1-2):203-14. DOI: 10.1089/10665270050081478. View

12.

Wei C, Ng P, Chiu K, Wong C, Ang C, Lipovich L . 5' Long serial analysis of gene expression (LongSAGE) and 3' LongSAGE for transcriptome characterization and genome annotation. Proc Natl Acad Sci U S A. 2004; 101(32):11701-6. PMC: 511040. DOI: 10.1073/pnas.0403514101. View

13.

Praz V, Jagannathan V, Bucher P . CleanEx: a database of heterogeneous gene expression data based on a consistent gene nomenclature. Nucleic Acids Res. 2003; 32(Database issue):D542-7. PMC: 308841. DOI: 10.1093/nar/gkh107. View

14.

Benson D, Karsch-Mizrachi I, Lipman D, Ostell J, Wheeler D . GenBank. Nucleic Acids Res. 2005; 34(Database issue):D16-20. PMC: 1347519. DOI: 10.1093/nar/gkj157. View

15.

Jongeneel C, Delorenzi M, Iseli C, Zhou D, Haudenschild C, Khrebtukova I . An atlas of human gene expression from massively parallel signature sequencing (MPSS). Genome Res. 2005; 15(7):1007-14. PMC: 1172045. DOI: 10.1101/gr.4041005. View