The DOI matches its Crossref record; 12 of the 12 references it cites were found in a registry or an index.
Reducing storage requirements for biological sequence comparison
Open accessAbstract
MOTIVATION: Comparison of nucleic acid and protein sequences is a fundamental tool of modern bioinformatics. A dominant method of such string matching is the 'seed-and-extend' approach, in which occurrences of short subsequences called 'seeds' are used to search for potentially longer matches in a large database of sequences. Each such potential match is then checked to see if it extends beyond the seed. To be effective, the seed-and-extend approach needs to catalogue seeds from virtually every substring in the database of search strings. Projects such as mammalian genome assemblies and large-scale protein matching, however, have such large sequence databases that the resulting list of seeds cannot be stored in RAM on a single computer. This significantly slows the matching process. RESULTS: We present a simple and elegant method in which only a small fraction of seeds, called 'minimizers', needs to be stored. Using minimizers can speed up string-matching computations by a large factor while missing only a small fraction of the matches found using all seeds.
Overview
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
Verification
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?
The cited source says what the claim attributes to it.
In the citing paper
“is a tradeoff between sensitivity and specificity”
From <tt>SAFARI</tt> : pangenome alignment of ancient DNA using purine/pyrimidine encodings (2025) · cites this paper as [23]
The cited source says what the claim attributes to it.
In the citing paper
“The minimizer index data structure was first invented to reduce storage space for biological sequence data [23].”
From <tt>SAFARI</tt> : pangenome alignment of ancient DNA using purine/pyrimidine encodings (2025) · cites this paper as [23]
The cited source says what the claim attributes to it.
In the citing paper
“Since then, minimizers have proven invaluable as a means of providing promising seeds for potential extension during alignment.”
From <tt>SAFARI</tt> : pangenome alignment of ancient DNA using purine/pyrimidine encodings (2025) · cites this paper as [23]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
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
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
The sequence of the human genome
Venter, J. C., Adams, M. D., Myers, E. W., Li, P. W., Mural, R. J., Sutton, G. G., Smith, H. O., Yandell, M., Evans, C. A., Holt, R. A., et al. (2001) · Science · doi:10.1126/science.1058040 · Cited by 13,909
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
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
Rapid and sensitive protein similarity searches
Lipman, D. J., & Pearson, W. R. (1985) · Science · doi:10.1126/science.2983426 · Cited by 4,033
A Whole-Genome Assembly of Drosophila
Myers, E. W., Sutton, G. G., Delcher, A. L., Dew, I. M., Fasulo, D., Flanigan, M. J., Kravitz, S. A., Mobarry, C. M., Reinert, K., Remington, K., et al. (2000) · Science · doi:10.1126/science.287.5461.2196 · Cited by 1,533
SSAHA: A Fast Search Method for Large DNA Databases
Ning, Z., Cox, A. J., & Mullikin, J. C. (2001) · Genome Research · doi:10.1101/gr.194201 · Cited by 965
PatternHunter: faster and more sensitive homology search
Ma, B., Tromp, J., & Li, M. (2002) · Bioinformatics · doi:10.1093/bioinformatics/18.3.440 · Cited by 837
High-Throughput Gene Mapping in Caenorhabditis elegansPreprint
Swan, K. A., Curtis, D. E., McKusick, K. B., Voinov, A. V., Mapa, F., & Cancilla, M. R. (2002) · Genome Research · doi:10.1101/gr.208902 · Cited by 617
Cited by
Sorted by citations
Minimap2: Pairwise alignment for nucleotide sequences
Li, H. (2018) · Bioinformatics · doi:10.1093/bioinformatics/bty191 · Cited by 14,807
Improved metagenomic analysis with Kraken 2
Wood, D. E., Lu, J., & Langmead, B. (2019) · Genome biology · doi:10.1186/s13059-019-1891-0 · Cited by 7,173
“We also performed a third parameter sweep, focused on translated search (Kraken 2X), where we looked at values for l in the interval [11, 15], values for k in the interval [l, l+3], and values for s in the interval [0, 3].”
MethodKraken: ultrafast metagenomic sequence classification using exact alignments
Wood, D. E., & Salzberg, S. L. (2014) · Genome Biology · doi:10.1186/gb-2014-15-3-r46 · Cited by 4,521
“Because Kraken very frequently uses a k-mer as a database query immediately after querying an adjacent kmer, and because adjacent k-mers share a substantial amount of sequence, we utilize the minimizer concept [20] to group similar k-mers together.”
BackgroundMethodMash: fast genome and metagenome distance estimation using MinHash
Ondov, B. D., Treangen, T. J., Melsted, P., Mallonee, A. B., Bergman, N. H., Koren, S., & Phillippy, A. M. (2016) · Genome biology · doi:10.1186/s13059-016-0997-x · Cited by 3,373
“[41], which has been used in genome assembly [42], k-mer counting [43], and metagenomics [44].”
MethodVersatile genome assembly evaluation with QUAST-LG
Mikheenko, A., Prjibelski, A. D., Saveliev, V., Antipov, D., & Gurevich, A. A. (2018) · Bioinformatics · doi:10.1093/bioinformatics/bty266 · Cited by 1,537
Metadata
- Authors
- Roberts, M., Hayes, W., Hunt, B. R., Mount, S. M., & Yorke, J. A.
- Affiliations
- University of Maryland, College Park (US)
- Corresponding author
- Roberts, Michael
- Venue
- Bioinformatics
- Publisher
- Oxford University Press (OUP)
- Published
- 2004-07-15
- Volume
- 20
- Issue
- 18
- Pages
- 3363-3369
- ISSN
- 1367-4803 (ISSN-L)
- 1367-4811
- OpenAlex
- W2144560237
- Cited by
- 485
- References
- 12
- Citations by year
- 2026: 30 · 2025: 57 · 2024: 65 · 2023: 81 · 2022: 49 · 2021: 49 · 2020: 40 · 2019: 31 · 2018: 26 · 2017: 18 · 2016: 8 · 2015: 10 · 2014: 8 · 2013: 3 · 2012: 3
- FWCI
- 1.35
- Type
- journal article
- Language
- en
- Open access
- bronze
- doi.org
- Locations
- Bioinformatics (publishedVersion)
- PubMed (publishedVersion)
- Funders
- National Science Foundation (0312360, 0104087, 0114792)
- National Institutes of Health
- National Human Genome Research Institute (1R01HG0294501)
- Topics
- Physical Sciences › Mathematics › Theoretical Computer Science › 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
- minimizers, string matching, sequence comparison, storage reduction, nucleic acid sequences, protein sequences, sequence databases
- MeSH terms
- Algorithms, Numerical Analysis, Computer-Assisted, Information Storage and Retrieval, Sequence Alignment, Sequence Analysis, Databases, Genetic
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
