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
Flagged first, then by citations
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
Minimap and miniasm: fast mapping and de novo assembly for noisy long sequences
Li, H. (2016) · Bioinformatics · doi:10.1093/bioinformatics/btw152 · Cited by 1,500
“Roberts et al. (2004) did not discuss the treatment of such equally good minimizers.”
BackgroundMethodNew strategies to improve minimap2 alignment accuracy
Li, H. (2021) · Bioinformatics · doi:10.1093/bioinformatics/btab705 · Cited by 1,275
“Minimap2 keeps all k -mer minimizers (Roberts et al., 2004) during indexing.”
BackgroundAssembling large genomes with single-molecule sequencing and locality-sensitive hashing
Berlin, K., Koren, S., Chin, C.-S., Drake, J. P., Landolin, J. M., & Phillippy, A. M. (2015) · Nature Biotechnology · doi:10.1038/nbt.3238 · Cited by 947
“The approach can also be viewed as a generalization of minimizers 27 .”
BackgroundBayesHammer: Bayesian clustering for error correction in single-cell sequencing
Nikolenko, S., Korobeynikov, A., & Alekseyev, M. A. (2013) · BMC Genomics · doi:10.1186/1471-2164-14-s1-s7 · Cited by 479
“[15].”
Telomere-to-telomere assembly of diploid chromosomes with Verkko
Rautiainen, M., Nurk, S., Walenz, B. P., Logsdon, G. A., Porubskỳ, D., Rhie, A., Eichler, E. E., Phillippy, A. M., & Koren, S. (2023) · Nature Biotechnology · doi:10.1038/s41587-023-01662-6 · Cited by 405
Exploiting sparseness in de novo genome assembly
Ye, C., Ma, Z. S., Cannon, C. H., Pop, M., & Yu, D. W. (2012) · BMC Bioinformatics · doi:10.1186/1471-2105-13-s6-s1 · Cited by 414
“We would like to note that our approach is similar in spirit to the minimizer idea introduced by Roberts et al. [20].”
BackgroundResultPangenomics enables genotyping of known structural variants in 5202 diverse genomes
Sirén, J., Monlong, J., Chang, X., Novak, A. M., Eizenga, J. M., Markello, C., Sibbesen, J. A., Hickey, G., Chang, P.-C., Carroll, A., et al. (2021) · Science · doi:10.1126/science.abg8871 · Cited by 400
“Haplotype minimizer seeding is shown in (C): Seeds are identified using an index of minimizers (subsets of sequences of specified length k ) ( 50 ) over the sequences of all the GBWT haplotypes.”
MethodMinimus: a fast, lightweight genome assembler
Sommer, D. D., Delcher, A. L., Salzberg, S. L., & Pop, M. (2007) · BMC Bioinformatics · doi:10.1186/1471-2105-8-64 · Cited by 386
“hash-overlap – a sequence overlapper that uses minimizers [27] to increase speed and decrease memory usage.”
BackgroundKMC 2: fast and resource-frugal k -mer counting
Deorowicz, S., Kokot, M., Grabowski, S., & Debudaj-Grabysz, A. (2015) · Bioinformatics · doi:10.1093/bioinformatics/btv022 · Cited by 287
“istics we need to find all c opies of each unique k-mer, which is not an easy task when the copies are stored in many places. A clever solution to these problems is based on the concept of minimizers (Roberts et al., 2004a,b). A minimizer of a k-mer is such of its m-mers (m < k) that no other lexicographically small…”
BackgroundLong-read mapping to repetitive reference sequences using Winnowmap2
Jain, C., Rhie, A., Hansen, N. F., Koren, S., & Phillippy, A. M. (2022) · Nature Methods · doi:10.1038/s41592-022-01457-8 · Cited by 276
“The seeding step reuses Winnowmap’s weighted mini-mizer sampling 11 , which yields an accuracy improvement over the standard minimizer technique 31 .”
GraphAligner: rapid and versatile sequence-to-graph alignment
Rautiainen, M., & Marschall, T. (2020) · Genome Biology · doi:10.1186/s13059-020-02157-2 · Cited by 242
Fast and robust metagenomic sequence comparison through sparse chaining with skani
Shaw, J., & Yu, Y. W. (2023) · Nature Methods · doi:10.1038/s41592-023-02018-3 · Cited by 248
Genome assembly in the telomere-to-telomere era
Li, H., & Durbin, R. M. (2024) · Nature Reviews Genetics · doi:10.1038/s41576-024-00718-w · Cited by 259
“Instead of storing every k -mer in reads, only a small subset of all k -mers — minimizers 103 or similar concepts 104,105 — are retained in memory.”
Bifrost: highly parallel construction and indexing of colored and compacted de Bruijn graphs
Holley, G., & Melsted, P. (2020) · Genome biology · doi:10.1186/s13059-020-02135-8 · Cited by 211
“The minimizer [60, 61] of an l -mer x is a g -mer y occurring in x such that g l and y is the lexicographically smallest of all the g -mers in x .”
BackgroundWeighted minimizer sampling improves long read mapping
Jain, C., Rhie, A., Zhang, H., Chu, C., Walenz, B. P., Koren, S., & Phillippy, A. M. (2020) · Bioinformatics · doi:10.1093/bioinformatics/btaa435 · Cited by 205
High-quality metagenome assembly from long accurate reads with metaMDBG
Benoit, G., Raguideau, S., James, R. S., Phillippy, A. M., Chikhi, R., & Quince, C. (2024) · Nature Biotechnology · doi:10.1038/s41587-023-01983-6 · Cited by 212
“Recall that in the original definition of minimizers 27 , a window is used to compute minimizers.”
Fast alignment and preprocessing of chromatin profiles with Chromap
Zhang, H., Song, L., Wang, X., Cheng, H., Wang, C., Meyer, C. A., Liu, T., Tang, M., Aluru, S., Yue, F., et al. (2021) · Nature Communications · doi:10.1038/s41467-021-26865-w · Cited by 191
Error correction enables use of Oxford Nanopore technology for reference-free transcriptome analysis
Sahlin, K., Sipos, B., James, P. L., & Medvedev, P. (2021) · Nature Communications · doi:10.1038/s41467-020-20340-8 · Cited by 174
“Technically, we use minimizers 27 as the anchors; intuitively, it means that the chosen anchors are not too many but they are also not too far apart, guaranteeing that reads that share homologous sequence will likely also share the anchors in it.”
Strain-level metagenomic assignment and compositional estimation for long reads with MetaMaps
Dilthey, A., Jain, C., Koren, S., & Phillippy, A. M. (2019) · Nature Communications · doi:10.1038/s41467-019-10934-2 · Cited by 170
A fast adaptive algorithm for computing whole-genome homology maps
Jain, C., Koren, S., Dilthey, A., Phillippy, A. M., & Aluru, S. (2018) · Bioinformatics · doi:10.1093/bioinformatics/bty597 · Cited by 169
Next-generation sequencing: big data meets high performance computing
Schmidt, B., & Hildebrandt, A. (2017) · Drug Discovery Today · doi:10.1016/j.drudis.2017.01.014 · Cited by 152
Technology dictates algorithms: recent developments in read alignment
Alser, M., Rotman, J., Deshpande, D., Taraszka, K., Shi, H., Baykal, P. I., Yang, H. T., Xue, V., Knyazev, S., Singer, B. D., et al. (2021) · Genome Biology · doi:10.1186/s13059-021-02443-7 · Cited by 144
A survey of k-mer methods and applications in bioinformatics
Moeckel, C., Mareboina, M., Konnaris, M. A., Chan, C. S. Y., Mouratidis, I., Montgomery, A., Chantzi, N., Pavlopoulos, G. A., & Georgakopoulos-Soares, I. (2024) · Computational and Structural Biotechnology Journal · doi:10.1016/j.csbj.2024.05.025 · Cited by 131
“2B) [68], k-mers can serve as effective minimizers to reduce memory and computational requirements for genomic data analysis (Table 1) [69].”
BackgroundSKA: Split Kmer Analysis Toolkit for Bacterial Genomic EpidemiologyPreprint
Harris, S. R. (2018) · bioRxiv (Cold Spring Harbor Laboratory) · doi:10.1101/453142 · Cited by 129
“To further increase analysis speed and reduce memory requirements, these methods use minimisers (6) and/or bloom filters (7).”
MethodHyPo: Super Fast & Accurate Polisher for Long Read Genome AssembliesPreprint
Kundu, R., Casey, J., & Sung, W.-K. K. (2019) · bioRxiv (Cold Spring Harbor Laboratory) · doi:10.1101/2019.12.19.882506 · Cited by 125
Syncmers are more sensitive than minimizers for selecting conserved k ‑mers in biological sequences
Edgar, R. C. (2021) · PeerJ · doi:10.7717/peerj.10805 · Cited by 117
“This was noted in (Roberts et al., 2004), where it was proposed that the problem can be addressed by introducing a special case at sequence terminals they called end-minimizers.”
BackgroundEkim, B., Berger, B., & Chikhi, R. (2021) · Cell Systems · doi:10.1016/j.cels.2021.08.009 · Cited by 116
Nossa, C. W., Havlak, P., Yue, J., Lv, J., Vincent, K. Y., Brockmann, H. J., & Putnam, N. H. (2014) · GigaScience · doi:10.1186/2047-217x-3-9 · Cited by 110
“Several mechanisms have been proposed for sampling k-mers in a representative way[49, 50].”
Turakhia, Y., Bejerano, G., & Dally, W. J. (2018) · International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS) · doi:10.1145/3173162.3173193 · Cited by 116
“Minimizers [66] help reduce the storage requirement of seeds.”
Backgroundlra: A long read aligner for sequences and contigs
Ren, J., & Chaisson, M. (2021) · PLoS Computational Biology · doi:10.1371/journal.pcbi.1009078 · Cited by 110
“An initial set of minimizers is determined in the standard approach, with minimizer k-mer parameter k and window w [22].”
Jayakumar, V., & Sakakibara, Y. (2017) · Briefings in Bioinformatics · doi:10.1093/bib/bbx147 · Cited by 107
Multiplex de Bruijn graphs enable genome assembly from long, high-fidelity reads
Bankevich, A., Bzikadze, A. V., Kolmogorov, M., Antipov, D., & Pevzner, P. A. (2022) · Nature Biotechnology · doi:10.1038/s41587-022-01220-6 · Cited by 103
“A minimizer-set of a string is defined as the set of all minimizers over all its substrings of length width 19 .”
BackgroundA Survey on Data Compression Methods for Biological Sequences
Hosseini, M., Pratas, D., & Pinho, A. J. (2016) · Information · doi:10.3390/info7040056 · Cited by 99
“Also, it uses “minimizers” [121] to pass similar (overlapping) DNA reads into the same bin [94,122–125].”
MethodA Fast Approximate Algorithm for Mapping Long Reads to Large Reference Databases
Jain, C., Dilthey, A., Koren, S., Aluru, S., & Phillippy, A. M. (2018) · Journal of Computational Biology · doi:10.1089/cmb.2018.0036 · Cited by 98
“Schleimer et al. (2003) proposed the winnowing algorithm, which picks a minimum hashed item (also known as a minimizer; Roberts et al., 2004) from each consecutive window of text as a means to more quickly estimate local similarity between web documents.”
De Novo Clustering of Long-Read Transcriptome Data Using a Greedy, Quality Value-Based Algorithm
Sahlin, K., & Medvedev, P. (2020) · Journal of Computational Biology · doi:10.1089/cmb.2019.0299 · Cited by 94
“Given two integers w and k such that 1 £ k £ w £ j r j , the minimizer at position i is the lexicographically smallest substring of r of length k that starts at a position in the interval of [ i , i + w ) (Roberts et al., 2004).”
Squeakr: an exact and approximate k -mer counting system
Pandey, P., Bender, M. A., Johnson, R., & Patro, R. (2017) · Bioinformatics · doi:10.1093/bioinformatics/btx636 · Cited by 93
On the Representation of de Bruijn Graphs
Chikhi, R., Limasset, A., Jackman, S. D., Simpson, J. T., & Medvedev, P. (2014) · Lecture notes in computer science · doi:10.1007/978-3-319-05269-4_4 · Cited by 92
MBG: Minimizer-based sparse de Bruijn Graph construction
Rautiainen, M., & Marschall, T. (2021) · Bioinformatics · doi:10.1093/bioinformatics/btab004 · Cited by 87
Strobealign: flexible seed size enables ultra-fast and accurate read alignment
Sahlin, K. (2022) · Genome biology · doi:10.1186/s13059-022-02831-7 · Cited by 99
Guo, L., Lau, J., Ruan, Z., et al. (2019) · IEEE International Symposium on Field-Programmable Custom Computing Machines (FCCM) · doi:10.1109/fccm.2019.00027 · Cited by 89
Liu, S., Rodriguez, J. S., Munteanu, V., Ronkowski, C., Sharma, N. K., Alser, M., Andreace, F., Blekhman, R., Błaszczyk, D., Chikhi, R., et al. (2025) · Nature Reviews Methods Primers · doi:10.1038/s43586-024-00376-6 · Cited by 99
“Minimizers 112 are a strategy for summarizing genomic data in a small memory footprint, thus offering speed and memory advantages over de Bruijn graph approaches.”
Efficient hybrid de novo assembly of human genomes with WENGAN
Genova, A. D., Buena‐Atienza, E., Ossowski, S., & Sagot, M. (2020) · Nature Biotechnology · doi:10.1038/s41587-020-00747-w · Cited by 86
Gerbil: a fast and memory-efficient k-mer counter with GPU-support
Erbert, M., Rechner, S., & Müller‐Hannemann, M. (2017) · Algorithms for Molecular Biology · doi:10.1186/s13015-017-0097-9 · Cited by 84
“• Roberts et al. [16]: they propose the lexico-graphic ordering of minimizers with respect to C < A < T < G .”
BackgroundEffective sequence similarity detection with strobemersPreprint
Sahlin, K. (2021) · Genome Research · doi:10.1101/gr.275648.121 · Cited by 86
“For third-generation sequencing data, MinHash (Broder 1997) and minimizers (Schleimer et al. 2003; Roberts et al. 2004) proved to be useful k - mer subsampling methods for such sequence comparison as min-imizers can be preserved in a window affected by an indel.”
MethodInfluentialREINDEER: efficient indexing of k -mer presence and abundance in sequencing datasets
Marchet, C., Iqbal, Z., Gautheret, D., Salson, M., & Chikhi, R. (2020) · Bioinformatics · doi:10.1093/bioinformatics/btaa487 · Cited by 78
LongStitch: high-quality genome assembly correction and scaffolding using long reads
Coombe, L., Li, J. X., Lo, T., Wong, J., Nikolić, V., Warren, R. L., & Birol, İ. (2021) · BMC Bioinformatics · doi:10.1186/s12859-021-04451-7 · Cited by 74
Sparse and skew hashing of K-mers
Pibiri, G. E. (2022) · bioRxiv · doi:10.1093/bioinformatics/btac245 · Cited by 92
“Minimizers are very popular in sequence analysis, such as for seed-and-extend algorithms, because of the following empirical property: consecutive k -mers tend to have the same minimizer (Roberts et al. , 2004; Schleimer et al., 2003).”
BackgroundGenStore: a high-performance in-storage processing system for genome sequence analysis
Ghiasi, N. M., Park, J., Mustafa, H., Kim, J. S., Olgun, A., Gollwitzer, A., Cali, D. S., Fırtına, C., Mao, H., Alserr, N. A., et al. (2022) · International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS) · doi:10.1145/3503222.3507702 · Cited by 76
Dysgu: efficient structural variant calling using short or long reads
Cleal, K., & Baird, D. M. (2022) · Nucleic Acids Research · doi:10.1093/nar/gkac039 · Cited by 75
“As pairwise 469 sequence comparison between neighbouring alignments is computationally costly, 470 we devised a novel algorithm based on clustering of the minimizer sketch of soft471 clipped reads (30).”
MethodTurakhia, Y., Bejerano, G., & Dally, W. J. (2018) · ACM SIGPLAN Notices · doi:10.1145/3296957.3173193 · Cited by 72
Improving the performance of minimizers and winnowing schemes
Marçais, G., Pellow, D., Bork, D., Orenstein, Y., Ron Shamir, A., & Kingsford, C. (2017) · Bioinformatics · doi:10.1093/bioinformatics/btx235 · Cited by 70
“Many of the tools mentioned above do not use lexicographic ordering of the k -mers, as originally proposed in Roberts et al. (2004b).”
MethodInfluentialPandora: nucleotide-resolution bacterial pan-genomics with reference graphs
Colquhoun, R., Hall, M. B., Lima, L., Roberts, L. W., Malone, K. M., Hunt, M., Letcher, B., Hawkey, J., George, S. A., Pankhurst, L. J., et al. (2021) · Genome biology · doi:10.1186/s13059-021-02473-1 · Cited by 69
“Second, we introduce a graph representation of genetic variation based on (w,k)-minimizers [25].”
MethodOn the Representation of De Bruijn Graphs
Chikhi, R., Limasset, A., Jackman, S. D., Simpson, J. T., & Medvedev, P. (2015) · Journal of Computational Biology · doi:10.1089/cmb.2014.0160 · Cited by 68
“Our algorithm is based on the idea of minimizers, first introduced by [30,31] and later used by [25].”
MethodAccelerating minimap2 for long-read sequencing applications on modern CPUs
Kalikar, S., Jain, C., Md, V., & Misra, S. (2022) · Nature Computational Science · doi:10.1038/s43588-022-00201-8 · Cited by 69
deSALT: fast and accurate long transcriptomic read alignment with de Bruijn graph-based index
Liu, B., Liu, Y., Li, J., Guo, H., Zang, T., & Wang, Y. (2019) · Genome biology · doi:10.1186/s13059-019-1895-9 · Cited by 64
Disk-based compression of data from genome sequencing
Grabowski, S., Deorowicz, S., & Roguski, Ł. (2014) · Bioinformatics · doi:10.1093/bioinformatics/btu844 · Cited by 63
Improved design and analysis of practical minimizers
Zheng, H., Kingsford, C., & Marçais, G. (2020) · Bioinformatics · doi:10.1093/bioinformatics/btaa472 · Cited by 61
“This result may be surprising as in practice the lexicographic minimizers have high density (Marc¸ais et al. , 2017; Roberts et al. , 2004a; and see Section 4).”
A survey of mapping algorithms in the long-reads era
Sahlin, K., Baudeau, T., Cazaux, B., & Marchet, C. (2023) · Genome biology · doi:10.1186/s13059-023-02972-3 · Cited by 66
Asymptotically optimal minimizers schemes
Marçais, G., DeBlasio, D., & Kingsford, C. (2018) · Bioinformatics · doi:10.1093/bioinformatics/bty258 · Cited by 56
Chin, C.-S., Behera, S., Khalak, A., Sedlazeck, F. J., Sudmant, P. H., Wagner, J., & Zook, J. M. (2023) · Nature Methods · doi:10.1038/s41592-023-01914-y · Cited by 61
“b (w, k, r, min_span) = (48, 56, 4, 12) 550,000 bps”
Alanko, J., Vuohtoniemi, J., Mäklin, T., & Puglisi, S. J. (2023) · Bioinformatics · doi:10.1093/bioinformatics/btad233 · Cited by 54
“The k -mer index of Bifrost is essentially a minimizer index (Roberts et al. 2004) of the set of unitig strings of the de Bruijn graph, whereas the k -mer index of Metagraph uses the BWT-based BOSS data structure (Bowe et al. 2012).”
MethodExtremely fast construction and querying of compacted and colored de Bruijn graphs with GGCATPreprint
Cracco, A., & Tomescu, A. I. (2023) · Genome Research · doi:10.1101/gr.277615.122 · Cited by 54
Scalable, ultra-fast, and low-memory construction of compacted de Bruijn graphs with Cuttlefish 2
Khan, J., Kokot, M., Deorowicz, S., & Patro, R. (2022) · Genome biology · doi:10.1186/s13059-022-02743-6 · Cited by 54
Sequencing Technologies and Analyses: Where Have We Been and Where Are We Going?
Bansal, V., & Boucher, C. A. (2019) · iScience · doi:10.1016/j.isci.2019.06.035 · Cited by 50
Comparative analysis of metagenomic classifiers for long-read sequencing datasets
Marić, J., Križanović, K., Riondet, S., Nagarajan, N., & Šikić, M. (2024) · BMC Bioinformatics · doi:10.1186/s12859-024-05634-8 · Cited by 63
“Therefore, modern tools usually use just a few discriminative kmers per genome or choose a lexico-graphically smallest kmer in a window of w consecutive kmers, i.e. minimiser [45].”
MethodAccelerating Minimap2 for Accurate Long Read Alignment on GPUs
Sadasivan, H., Maric, M., Dawson, E. T., Iyer, V., Israeli, J., & Narayanasamy, S. (2023) · Journal of Biotechnology and Biomedicine · doi:10.26502/jbb.2642-91280067 · Cited by 46
“In the offline pre-processing step, the reference genome is indexed to a multimap using a hash table with the popular time and space-saving k-mer samples called minimizers [18] as the key and minimizer locations on the reference as the values.”
MethodRawHash: enabling fast and accurate real-time analysis of raw nanopore signals for large genomes
Fırtına, C., Ghiasi, N. M., Lindegger, J., Singh, G., Cavlak, M. B., Mao, H., & Mutlu, O. (2023) · Bioinformatics · doi:10.1093/bioinformatics/btad272 · Cited by 48
Designing small universal k-mer hitting sets for improved analysis of high-throughput sequencing
Orenstein, Y., Pellow, D., Marçais, G., Ron Shamir, A., & Kingsford, C. (2017) · PLoS Computational Biology · doi:10.1371/journal.pcbi.1005777 · Cited by 48
Multiple genome alignment in the telomere-to-telomere assembly era
Kille, B., Balaji, A., Sedlazeck, F. J., Nute, M., & Treangen, T. J. (2022) · Genome Biology · doi:10.1186/s13059-022-02735-6 · Cited by 47
“Both MashMap [136, 137] and MiniMap [138, 139] use minimizers [140] in order to select seeds for pairwise genome alignment, but both algorithms are tailored towards mapping long reads to references, as opposed to finding small alignments across divergent genomes which are suitable for anchors.”
MethodRowe, W. P. M. (2019) · Genome biology · doi:10.1186/s13059-019-1809-x · Cited by 47
ntLink: A Toolkit for De Novo Genome Assembly Scaffolding and Mapping Using Long Reads
Coombe, L., Warren, R. L., Wong, J., Nikolić, V., & Birol, İ. (2023) · Current Protocols · doi:10.1002/cpz1.733 · Cited by 47
“As described in Roberts et al. (2004) and implemented in btllib (Nikolić et al., 2022), ntLink generates ordered minimizer sketches by first breaking the input sequences into their constituent k-mers (substrings of length k), and computing a hash value for each k-mer using ntHash2 (Kazemi et al.,…”
MethodMemory efficient minimum substring partitioning
Li, Y., Kamousi, P., Han, F., Yang, S., Yan, X., & Suri, S. (2013) · Proceedings of the VLDB Endowment · doi:10.14778/2535569.2448951 · Cited by 45
“The concept of minimum substring was introduced in [20] for memory-efficient sequence comparison.”
BackgroundOverlap graphs and de Bruijn graphs: data structures for de novogenome assembly in the big data era
Rizzi, R., Beretta, S., Patterson, M., et al. (2019) · Quantitative Biology · doi:10.1007/s40484-019-0181-x · Cited by 46
“Moreover, it uses minimizers [24] to further reduce the memory needed without an excessive impact on the quality of the overlap detection.”
MethodInternal Pattern Matching Queries in a Text and Applications
Kociumaka, T., Radoszewski, J., Rytter, W., & Waleń, T. (2014) · ACM-SIAM Symposium on Discrete Algorithms (SODA) · doi:10.1137/1.9781611973730.36 · Cited by 43
A Fast Approximate Algorithm for Mapping Long Reads to Large Reference Databases
Jain, C., Dilthey, A., Koren, S., Aluru, S., & Phillippy, A. M. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-56970-3_5 · Cited by 45
Sketching and Sublinear Data Structures in Genomics
Marçais, G., Solomon, B., Patro, R., & Kingsford, C. (2019) · Annual Review of Biomedical Data Science · doi:10.1146/annurev-biodatasci-072018-021156 · Cited by 45
“Pairwise string overlaps is the original genomics application for which minimizers were invented (108, 110): Given a set of sequencing reads, the first step of the overlap–layout–consensus method for genome assembly (114) is to find all the read pairs where the suffix of one read aligns with the prefix of the other.”
BackgroundMethodMinmers are a generalization of minimizers that enable unbiased local Jaccard estimation
Kille, B. L., Garrison, E. P., Treangen, T. J., & Phillippy, A. M. (2023) · Bioinformatics · doi:10.1093/bioinformatics/btad512 · Cited by 41
“In short, given some total ordering on the k -mers, a window of length w is slid over the sequence and the element with the lowest rank in each window (the “minimizer”) is selected, using the left-most position to break ties (Roberts et al. 2004).”
BackgroundMethodAccurate spliced alignment of long RNA sequencing reads
Sahlin, K., & Mäkinen, V. (2021) · Bioinformatics · doi:10.1093/bioinformatics/btab540 · Cited by 42
Theory of local k-mer selection with applications to long-read alignment
Shaw, J., & Yu, Y. W. (2021) · Bioinformatics · doi:10.1093/bioinformatics/btab790 · Cited by 43
Indexing and searching petabase-scale nucleotide resources
Shiryev, S. A., & Agarwala, R. (2024) · Nature Methods · doi:10.1038/s41592-024-02280-z · Cited by 43
“33,34 but they used the notation of ( w , k ) differently from the one used in ref.”
Fulgor: a fast and compact k-mer index for large-scale matching and color queries
Fan, J., Singh, N., Khan, J., Pibiri, G. E., & Patro, R. (2024) · Algorithms for Molecular Biology · doi:10.1186/s13015-024-00251-9 · Cited by 52
“This is achieved by storing the unitigs explicitly (i.e., as contiguous, 2-bit encoded strings) in some prescribed order so that a k -mer x occurring in some unitig u i can be quickly located using a minimal perfect hash function [28] built for the set of the minimizers [29] of the k -mers.”
MethodFQSqueezer: k-mer-based compression of sequencing data
Deorowicz, S. (2020) · Scientific Reports · doi:10.1038/s41598-020-57452-6 · Cited by 41
Data-dependent bucketing improves reference-free compression of sequencing reads
Patro, R., & Kingsford, C. (2015) · Bioinformatics · doi:10.1093/bioinformatics/btv248 · Cited by 40
“They assume that the sender and receiver have a copy of the reference (which, itself, would have to be transferred) and that the set of reads can be mapped with relatively high quality to this reference (such methods may perform poorly if there are many unmapped reads).”
Compression of genomic sequencing reads via hash-based reordering: algorithm and analysis
Chandak, S., Tatwawadi, K., & Weissman, T. (2017) · Bioinformatics · doi:10.1093/bioinformatics/btx639 · Cited by 39
Data Structures to Represent a Set of k -long DNA Sequences
Chikhi, R., Holub, J., & Medvedev, P. (2021) · ACM Computing Surveys · doi:10.1145/3445967 · Cited by 41
“For a given (cid:2) < k , an (cid:2) - minimizer of a k -mer x is the smallest (according to some given permutation function) (cid:2) -mer substring of x [Roberts et al. 2004; Schleimer et al. 2003].”
BackgroundBLight: efficient exact associative structure for k-mers
Marchet, C., Kerbiriou, M., & Limasset, A. (2021) · Bioinformatics · doi:10.1093/bioinformatics/btab217 · Cited by 39
Song, L., & Langmead, B. (2024) · Genome biology · doi:10.1186/s13059-024-03244-4 · Cited by 42
“No.”
ntJoin: Fast and lightweight assembly-guided scaffolding using minimizer graphs
Coombe, L., Nikolić, V., Chu, J., Birol, İ., & Warren, R. L. (2020) · Bioinformatics · doi:10.1093/bioinformatics/btaa253 · Cited by 41
Cali, D. S., Kanellopoulos, K., Lindegger, J., Bingöl, Z., Kalsi, G. S., Zuo, Z., Fırtına, C., Cavlak, M. B., Kim, J. S., Ghiasi, N. M., et al. (2022) · Proceedings - International Symposium on Computer Architecture/Proceedings · doi:10.1145/3470496.3527436 · Cited by 56
“As we explain in Section 6, since SeGraM performs minimizer-based seeding, we use minimizers [91, 126, 184] as the”
MethodBLEND: a fast, memory-efficient and accurate mechanism to find fuzzy seed matches in genome analysis
Fırtına, C., Park, J., Alser, M., Kim, J. S., Cali, D. S., Shahroodi, T., Ghiasi, N. M., Singh, G., Kanellopoulos, K., Alkan, C., et al. (2023) · NAR Genomics and Bioinformatics · doi:10.1093/nargab/lqad004 · Cited by 41
“For example, minimap2 uses only the k-mers with the minimum hash value in a window of w consecutive k-mers, known as the minimizerk-mers (56) (1 in Figure 2).”
MethodSPUMONI 2: improved classification using a pangenome index of minimizer digests
Ahmed, O., Rossi, M., Gagie, T., Boucher, C. A., & Langmead, B. (2023) · Genome biology · doi:10.1186/s13059-023-02958-1 · Cited by 38
Accelerating Long Read Alignment on Three Processors
Feng, Z., Qiu, S., Wang, L., & Luo, Q. (2019) · Proceedings of the International Conference on Parallel Processing · doi:10.1145/3337821.3337918 · Cited by 37
“Mini-map2 uses minimizers [20] as seeds to suit the new error profile of third-generation sequences.”
PanGraph: scalable bacterial pan-genome graph construction
Noll, N., Molari, M., Shaw, L. P., & Neher, R. A. (2023) · Microbial Genomics · doi:10.1099/mgen.0.001034 · Cited by 40
De novo diploid genome assembly using long noisy reads
Nie, F., Ni, P., Huang, N., Zhang, J., Wang, Z., Xiao, C., Luo, F., & Wang, J. (2024) · Nature Communications · doi:10.1038/s41467-024-47349-7 · Cited by 37
“The overlap-graph-based assemblers usually use seed (i.e., k-mers, minimizers 31 ) based methods to fi nd candidate overlaps, then perform local alignment to fi nd the true overlaps.”
Compact Universal k-mer Hitting Sets
Orenstein, Y., Pellow, D., Marçais, G., et al. (2016) · Lecture notes in computer science · doi:10.1007/978-3-319-43681-4_21 · Cited by 35
“Such a set has a number of applications in speeding up genomic analyses since it can often be used in places where minimizers have been used in the past [2].”
Background
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
