SSAHA: A Fast Search Method for Large DNA Databases
Open accessAbstract
We describe an algorithm, SSAHA (S equence S earch and A lignment by H ashing A lgorithm), for performing fast searches on databases containing multiple gigabases of DNA. Sequences in the database are preprocessed by breaking them into consecutive k-tuples of k contiguous bases and then using a hash table to store the position of each occurrence of each k-tuple. Searching for a query sequence in the database is done by obtaining from the hash table the “hits” for each k-tuple in the query sequence and then performing a sort on the results. We discuss the effect of the tuple length k on the search speed, memory usage, and sensitivity of the algorithm and present the results of computational experiments which show that SSAHA can be three to four orders of magnitude faster than BLAST or FASTA, while requiring less memory than suffix tree methods. The SSAHA algorithm is used for high-throughput single nucleotide polymorphism (SNP) detection and very large scale sequence assembly. Also, it provides Web-based sequence search facilities for Ensembl projects.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
A total of approximately 1.2 million single nucleotide polymorphisms (SNPs) were identified within the 1.84-Gb sequenced female platypus genome using two independent analyses, SSAHA2 and PCAP output.
“We identified a total of , 1.2 million single nucleotide polymorphisms (SNPs) within the 1.84-Gb sequenced female platypus genomeusing two independent analyses, SSAHA2 (SSAHA: a fast search method for large DNA databases 72 ) and PCAP output 20 (Supplementary Notes 11).”
From Genome analysis of the platypus reveals unique signatures of evolution (2008) · cites this paper as [72]
The citation is attached to the method name SSAHA2, not to the platypus SNP count. The Abstract describes SSAHA and its use in SNP detection, but our copy does not identify or describe SSAHA2 specifically (searched: SSAHA2). (LLM, conf=0.84)
Experimental — accuracy not yet measured
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
Basic local alignment search tool
Altschul, S. F., Gish, W., Miller, W., Myers, E. W., & Lipman, D. J. (1990) · Journal of Molecular Biology · doi:10.1006/jmbi.1990.9999 · Cited by 98,669 · see citing works
Gapped BLAST and PSI-BLAST: a new generation of protein database search programs
Altschul, S. (1997) · Nucleic Acids Research · doi:10.1093/nar/25.17.3389 · Cited by 73,302 · see citing works
Initial sequencing and analysis of the human genome
International Human Genome Sequencing Consortium, Whitehead Institute for Biomedical Research, C. F. G. R., Lander, E. S., Linton, L. M., Birren, B., Nusbaum, C., Zody, M. C., Baldwin, J., Devon, K., Dewar, K., et al. (2001) · Nature · doi:10.1038/35057062 · Cited by 24,216 · see citing works
Self-citationThe Art of Computer Programming
Knuth, D. E. (1968) · Cited by 16,097 · see citing works
Needleman, S. B., & Wunsch, C. D. (1970) · Journal of Molecular Biology · doi:10.1016/0022-2836(70)90057-4 · Cited by 11,288 · see citing works
Improved tools for biological sequence comparison.
Pearson, W. R., & Lipman, D. J. (1988) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.85.8.2444 · Cited by 11,227 · see citing works
Identification of common molecular subsequences
Smith, T. F., & Waterman, M. S. (1981) · Journal of Molecular Biology · doi:10.1016/0022-2836(81)90087-5 · Cited by 9,962 · see citing works
Tandem repeats finder: a program to analyze DNA sequences
Benson, G. (1999) · Nucleic Acids Research · doi:10.1093/nar/27.2.573 · Cited by 9,374 · see citing works
A Greedy Algorithm for Aligning DNA Sequences
Zhang, Z., Schwartz, S., Wagner, L., & Miller, W. (2000) · Journal of Computational Biology · doi:10.1089/10665270050081478 · Cited by 5,459 · see citing works
Rapid and sensitive protein similarity searches
Lipman, D. J., & Pearson, W. R. (1985) · Science · doi:10.1126/science.2983426 · Cited by 4,033 · see citing works
Algorithms on strings, trees, and sequences computer science and computational biology
Gusfield, D. (1997) · Cited by 3,490 · see citing works
Algorithms on Strings, Trees and Sequences
Gusfield, D. (1997) · Cambridge University Press eBooks · doi:10.1017/cbo9780511574931 · Cited by 3,092 · see citing works
A map of human genome sequence variation containing 1.42 million single nucleotide polymorphisms
The International SNP Map Working Group, Laboratories:, C. S. H., Sachidanandam, R., Weissman, D., Schmidt, S. C., Kakol, J. M., Stein, L. D., National Center for Biotechnology Information:, Marth, G., Sherry, S., et al. (2001) · Nature · doi:10.1038/35057149 · Cited by 2,977 · see citing works
Self-citationKnuth, D. E. (1973) · Cumulative Index of Computer Aided Architectural Design · Cited by 1,532 · see citing works
The Art of Computer Programming, Vol. 3: Sorting and Searching
McClellan, M. T., Minker, J., & Knuth, D. E. (1974) · Mathematics of Computation · doi:10.2307/2005383 · Cited by 914 · see citing works
Delcher, A. L., Kasif, S., Fleischmann, R. D., Peterson, J., White, O., & Salzberg, S. L. (1999) · Nucleic Acids Research · doi:10.1093/nar/27.11.2369 · Cited by 893 · see citing works
An SNP map of the human genome generated by reduced representation shotgun sequencing
Altshuler, D., Pollara, V. J., Cowles, C. R., Etten, W. J. V., Baldwin, J., Linton, L., & Lander, E. S. (2000) · Nature · doi:10.1038/35035083 · Cited by 725 · see citing works
Introduction to Computational Biology: Maps, Sequences and Genomes.
Waterman, M. S. (1998) · Biometrics · doi:10.2307/2534039 · Cited by 465 · see citing works
Miller, C. J., Gurd, J. R., & Brass, A. (1999) · Bioinformatics · doi:10.1093/bioinformatics/15.2.111 · Cited by 33 · see citing works
Flagged first, then by citations
Cited by
Sorted by citations
Fast and accurate short read alignment with Burrows-Wheeler transform
Li, H., & Durbin, R. (2009) · Bioinformatics · doi:10.1093/bioinformatics/btp324 · Cited by 58,607 · see citing works
Fast and accurate long-read alignment with Burrows-Wheeler transform.
Li, H., & Durbin, R. (2010) · Bioinformatics · doi:10.1093/bioinformatics/btp698 · Cited by 12,063 · see citing works
“…BLAT (Kent, 2002) and PatternHunter (Ma et al ., 2002), greatly speeding up matching capillary sequencing technologies arrived that generated millions of short (<100bp) reads, a variety of new algorithms were developed which were 10–1000 times faster, including SOAP (Li,R. et al 2008), MAQ…”
Diet rapidly and reproducibly alters the human gut microbiome
David, L. A., Maurice, C. F., Carmody, R. N., Gootenberg, D. B., Button, J. E., Wolfe, B. E., Ling, A. V., Devlin, A. S., Varma, Y., Fischbach, M. A., et al. (2014) · Nature · doi:10.1038/nature12820 · Cited by 10,100 · see citing works
<tt>BLAT</tt> —The <tt>BLAST</tt> -Like Alignment Tool
Kent, W. J. (2002) · Genome Research · doi:10.1101/gr.229202 · Cited by 8,480 · see citing works
Initial sequencing and comparative analysis of the mouse genome
Mouse Genome Sequencing Consortium (2002) · Nature · doi:10.1038/nature01262 · Cited by 7,187 · see citing works
The International HapMap Project
†The International HapMap Consortium, Genotyping centres: Baylor College of Medicine and ParAllele BioScience, Gibbs, R. A., Belmont, J. W., Hardenbol, P., Willis, T. D., Yu, F., Chinese HapMap Consortium, Yang, H., Ch'ang, L.-Y., et al. (2003) · Nature · doi:10.1038/nature02168 · Cited by 6,057 · see citing works
Self-citationThe ENCODE Project Consortium (2007) · Nature · doi:10.1038/nature05874 · Cited by 5,223 · see citing works
A draft sequence of the Neandertal genome
Green, R. E., Krause, J., Briggs, A. W., Maricic, T., Stenzel, U., Kircher, M., Patterson, N., Li, H., Zhai, W., Fritz, M. H.-Y., et al. (2010) · Science · doi:10.1126/science.1188021 · Cited by 4,318 · see citing works
Self-citationGenome sequence, comparative analysis and haplotype structure of the domestic dog
members, B. S. P., Lindblad-Toh, K., Wade, C. M., Mikkelsen, T. S., Karlsson, E. K., Jaffe, D. B., Kamal, M., Clamp, M., Chang, J. L., Kulbokas, E. J., et al. (2005) · Nature · doi:10.1038/nature04338 · Cited by 2,568 · see citing works
An integrated catalog of reference genes in the human gut microbiome
MetaHIT Consortium, Li, J., Jia, H., Cai, X., Zhong, H., Feng, Q., Sunagawa, S., Arumugam, M., Kultima, J. R., Prifti, E., et al. (2014) · Nature Biotechnology · doi:10.1038/nbt.2942 · Cited by 2,164 · see citing works
Fast and SNP-tolerant detection of complex variants and splicing in short reads
Wu, T. D., & Nacu, S. (2010) · Bioinformatics · doi:10.1093/bioinformatics/btq057 · Cited by 1,894 · see citing works
The origin and evolution of mutations in acute myeloid leukemia
Welch, J. S., Ley, T. J., Link, D. C., Miller, C. A., Larson, D. E., Koboldt, D. C., Wartman, L. D., Lamprecht, T. L., Liu, F., Xia, J., et al. (2012) · Cell · doi:10.1016/j.cell.2012.06.023 · Cited by 1,575 · see citing works
Mapping and sequencing of structural variation from eight human genomes
Kidd, J. M., Cooper, G. M., Donahue, W. F., Hayden, H. S., Sampas, N., Graves, T., Hansen, N., Teague, B., Alkan, C., Antonacci, F., et al. (2008) · Nature · doi:10.1038/nature06862 · Cited by 1,119 · see citing works
Self-citationThe DNA sequence of the human X chromosome
Ross, M. T., Grafham, D. V., Coffey, A. J., Scherer, S., McLay, K., Muzny, D., Platzer, M., Howell, G. R., Burrows, C., Bird, C. P., et al. (2005) · Nature · doi:10.1038/nature03440 · Cited by 1,129 · see citing works
Self-citationSNP detection for massively parallel whole-genome resequencing
Li, R., Li, Y., Fang, X., Yang, H., Wang, J., Kristiansen, K., & Wang, J. (2009) · Genome Research · doi:10.1101/gr.088013.108 · Cited by 944 · see citing works
A survey of sequence alignment algorithms for next-generation sequencing
Li, H., & Homer, N. (2010) · Briefings in Bioinformatics · doi:10.1093/bib/bbq015 · Cited by 875 · see citing works
Xenobiotics shape the physiology and gene expression of the active human gut microbiome
Maurice, C. F., Haiser, H. J., & Turnbaugh, P. J. (2013) · Cell · doi:10.1016/j.cell.2012.10.052 · Cited by 811 · see citing works
The Molecular Diversity of Adaptive Convergence
Tenaillon, O., Rodríguez-Verdugo, A., Gaut, R. L., McDonald, P., Bennett, A. F., Long, A. D., & Gaut, B. S. (2012) · Science · doi:10.1126/science.1212986 · Cited by 815 · see citing works
Retrotransposons regulate host genes in mouse oocytes and preimplantation embryos
Peaston, A. E., Evsikov, A. V., Graber, J. H., de Vries, W. N., Holbrook, A. E., Solter, D., & Knowles, B. B. (2004) · Developmental Cell · doi:10.1016/j.devcel.2004.09.004 · Cited by 710 · see citing works
Genome analysis of the platypus reveals unique signatures of evolution
paper, A. L. O. A. A. T. A. A. A. T. E. O. T. (2008) · Nature · doi:10.1038/nature06936 · Cited by 719 · see citing works
Genome of the marsupial Monodelphis domestica reveals innovation in non-coding sequences
Broad Institute Genome Sequencing Platform, Mikkelsen, T. S., Broad Institute Whole Genome Assembly Team, Wakefield, M. J., Aken, B., Amemiya, C. T., Chang, J. L., Duke, S., Garber, M., Gentles, A. J., et al. (2007) · Nature · doi:10.1038/nature05805 · Cited by 711 · see citing works
Haiser, H. J., Gootenberg, D. B., Chatman, K., Sirasani, G., Balskus, E. P., & Turnbaugh, P. J. (2013) · Science · doi:10.1126/science.1235872 · Cited by 704 · see citing works
Talkowski, M. E., Rosenfeld, J. A., Blumenthal, I., Pillalamarri, V., Chiang, C., Heilbut, A., Ernst, C., Hanscom, C., Rossin, E., Lindgren, A. M., et al. (2012) · Cell · doi:10.1016/j.cell.2012.03.028 · Cited by 577 · see citing works
Reducing storage requirements for biological sequence comparison
Roberts, M., Hayes, W., Hunt, B. R., Mount, S. M., & Yorke, J. A. (2004) · Bioinformatics · doi:10.1093/bioinformatics/bth408 · Cited by 485 · see citing works
Franke, L., Bakel, H. V., Fokkens, L., de Jong, E. D., Egmont-Petersen, M., & Wijmenga, C. (2006) · The American Journal of Human Genetics · doi:10.1086/504300 · Cited by 476 · see citing works
Turnbaugh, P. J., Quince, C., Faith, J. J., McHardy, A. C., Yatsunenko, T., Niazi, F., Affourtit, J., Egholm, M., Henrissat, B., Knight, R., et al. (2010) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1002355107 · Cited by 478 · see citing works
Reich, D., Nalls, M. A., Kao, W. H. L., Akylbekova, E. L., Tandon, A., Patterson, N., Mullikin, J., Hsueh, W.-C., Cheng, C.-Y., Coresh, J., et al. (2009) · PLoS Genetics · doi:10.1371/journal.pgen.1000360 · Cited by 423 · see citing works
Self-citationSupply, P., Marceau, M., Mangenot, S., Roche, D., Rouanet, C., Khanna, V., Majlessi, L., Criscuolo, A., Tap, J., Pawlik, A., et al. (2013) · Nature Genetics · doi:10.1038/ng.2517 · Cited by 305 · see citing works
Keinan, A., Mullikin, J. C., Patterson, N., & Reich, D. (2007) · Nature Genetics · doi:10.1038/ng2116 · Cited by 272 · see citing works
Self-citationApplication of 'next-generation' sequencing technologies to microbial genetics
MacLean, D., Jones, J. D. G., & Studholme, D. J. (2009) · Nature Reviews Microbiology · doi:10.1038/nrmicro2088 · Cited by 293 · see citing works
Mutation Altering the miR-184 Seed Region Causes Familial Keratoconus with Cataract
Hughes, A. E., Bradley, D. T., Campbell, M., Lechner, J., Dash, D. P., Simpson, D. A., & Willoughby, C. E. (2011) · The American Journal of Human Genetics · doi:10.1016/j.ajhg.2011.09.014 · Cited by 276 · see citing works
Bikel, S., Valdez-Lara, A., Cornejo-Granados, F., Rico, K., Canizales-Quinteros, S., Soberón, X., Del Pozo-Yauner, L., & Ochoa-Leyva, A. (2015) · Computational and Structural Biotechnology Journal · doi:10.1016/j.csbj.2015.06.001 · Cited by 263 · see citing works
Comparing de novo assemblers for 454 transcriptome data
Kumar, S., & Blaxter, M. L. (2010) · BMC Genomics · doi:10.1186/1471-2164-11-571 · Cited by 255 · see citing works
Mullikin, J. C., & Ning, Z. (2003) · Genome Research · doi:10.1101/gr.731003 · Cited by 222 · see citing works
Self-citationA metagenomic analysis of pandemic influenza A (2009 H1N1) infection in patients from North America
Greninger, A. L., Chen, E. C., Sittler, T., Scheinerman, A., Roubinian, N., Yu, G., Kim, E., Pillai, D. R., Guyard, C., Mazzulli, T., et al. (2010) · PLoS ONE · doi:10.1371/journal.pone.0013381 · Cited by 193 · see citing works
Łabaj, P. P., Leparc, G. G., Linggi, B. E., Markillie, L. M., Wiley, H. S., & Kreil, D. P. (2011) · Bioinformatics · doi:10.1093/bioinformatics/btr247 · Cited by 141 · see citing works
de Groot, A., Roche, D., Fernandez, B., Ludanyi, M., Cruveiller, S., Pignol, D., Vallenet, D., Armengaud, J., & Blanchard, L. (2014) · Genome Biology and Evolution · doi:10.1093/gbe/evu069 · Cited by 72 · see citing works
Light whole genome sequence for SNP discovery across domestic cat breeds
Mullikin, J. C., Hansen, N. F., Shen, L., Ebling, H., Donahue, W. F., Tao, W., Saranga, D. J., Brand, A., Rubenfield, M. J., Young, A. C., et al. (2010) · BMC Genomics · doi:10.1186/1471-2164-11-406 · Cited by 56 · see citing works
Self-citationReciprocal regulation of microRNA and mRNA profiles in neuronal development and synapse formation
Manakov, S. A., Grant, S. G., & Enright, A. J. (2009) · BMC Genomics · doi:10.1186/1471-2164-10-419 · Cited by 34 · see citing works
Application of a superword array in genome assembly
Huang, X. (2006) · Nucleic Acids Research · doi:10.1093/nar/gkj419 · Cited by 30 · see citing works
- Authors
- Ning, Z., Cox, A. J., & Mullikin, J. C.
- Affiliations
- Wellcome Sanger Institute (GB)
- Venue
- Genome Research
- Publisher
- Cold Spring Harbor Laboratory
- Published
- 2001-10-01
- Volume
- 11
- Issue
- 10
- Pages
- 1725-1729
- ISSN
- 1088-9051 (ISSN-L)
- 1549-5469
- PMC
- PMC311141
- OpenAlex
- W2142619120
- Cited by
- 965
- References
- 19
- Citations by year
- 2026: 5 · 2025: 7 · 2024: 13 · 2023: 11 · 2022: 13 · 2021: 24 · 2020: 18 · 2019: 20 · 2018: 25 · 2017: 38 · 2016: 46 · 2015: 56 · 2014: 69 · 2013: 94 · 2012: 95
- Type
- posted content
- Language
- en
- Open access
- bronze
- doi.org
- Locations
- Genome Research (publishedVersion)
- PubMed Central (publishedVersion)
- PubMed (publishedVersion)
- Funders
- European Bioinformatics Institute
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Algorithms and Data Compression
- Life Sciences › Biochemistry, Genetics and Molecular Biology › Molecular Biology › Genomics and Phylogenetic Studies
- Life Sciences › Biochemistry, Genetics and Molecular Biology › Molecular Biology › Fractal and DNA sequence analysis
- Keywords
- sequence database searching, DNA databases, hash tables, sequence alignment, memory usage, search speed, BLAST comparison, suffix trees, single nucleotide polymorphism detection, next-generation sequencing, sequence assembly, Ensembl
- MeSH terms
- Algorithms, Base Composition, Base Sequence, Database Management Systems, DNA, Sensitivity and Specificity, Software, Databases, Factual, Sequence Alignment
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
