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.
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?
The choice of k is a tradeoff between sensitivity and specificity, with larger k leading to greater specificity and lower sensitivity, and likewise for w.
“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 minimizer index data structure was first invented to reduce storage space for biological sequence data.
“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]
Minimizers provide promising seeds for potential extension during alignment.
“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.
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
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 · 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
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
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 · see citing works
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 · see citing works
PatternHunter: faster and more sensitive homology search
Ma, B., Tromp, J., & Li, M. (2002) · Bioinformatics · doi:10.1093/bioinformatics/18.3.440 · Cited by 819 · see citing works
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 618 · see citing works
The whole genome assembly of Drosophila
Myers, G. (2000) · Symposium on Discrete Algorithms · doi:10.5555/338219.338635 · Cited by 112 · see citing works
A Preprocessor for Shotgun Assembly of Large Genomes
Roberts, M., Hunt, B. R., Yorke, J. A., et al. (2004) · Journal of Computational Biology · doi:10.1089/cmb.2004.11.734 · Cited by 56 · see citing works
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 · see citing works
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 · see citing works
“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 · see citing works
“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
(2016) · Genome biology · doi:10.1186/s13059-016-0997-x · Cited by 3,373 · see citing works
“[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 · see citing works
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,460 · see citing works
“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,237 · see citing works
“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 928 · see citing works
“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 · see citing works
“[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 397 · see citing works
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 413 · see citing works
“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 · see citing works
“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 399 · see citing works
“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 282 · see citing works
“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 266 · see citing works
“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 · see citing works
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 243 · see citing works
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 251 · see citing works
“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 · see citing works
“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 · see citing works
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 199 · see citing works
“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 · see citing works
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 · see citing works
“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 · see citing works
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 166 · see citing works
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 147 · see citing works
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 · see citing works
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 · see citing works
“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 125 · see citing works
“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 · see citing works
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 · see citing works
“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 · see citing works
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 108 · see citing works
“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 107 · see citing works
“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 105 · see citing works
“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 105 · see citing works
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 · see citing works
“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 · see citing works
“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 · see citing works
“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 98 · see citing works
“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 96 · see citing works
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 · see citing works
MBG: Minimizer-based sparse de Bruijn Graph construction
Rautiainen, M., & Marschall, T. (2021) · Bioinformatics · doi:10.1093/bioinformatics/btab004 · Cited by 91 · see citing works
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 90 · see citing works
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 · see citing works
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 92 · see citing works
“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 · see citing works
Gerbil: a fast and memory-efficient k-mer counter with GPU-support
Erbert, M., Rechner, S., & Müller-Hannemann, M. (2016) · Algorithms for Molecular Biology · doi:10.1186/s13015-017-0097-9 · Cited by 72 · see citing works
“• 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 81 · see citing works
“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 77 · see citing works
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 · see citing works
Sparse and skew hashing of K-mers
Pibiri, G. E. (2022) · bioRxiv · doi:10.1093/bioinformatics/btac245 · Cited by 92 · see citing works
“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 73 · see citing works
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 72 · see citing works
“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 70 · see citing works
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 · see citing works
“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 · see citing works
“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 · see citing works
“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 · see citing works
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 · see citing works
Disk-based compression of data from genome sequencing
Grabowski, S., Deorowicz, S., & Roguski, Ł. (2014) · Bioinformatics · doi:10.1093/bioinformatics/btu844 · Cited by 63 · see citing works
Improved design and analysis of practical minimizers
Zheng, H., Kingsford, C., & Marçais, G. (2020) · Bioinformatics · doi:10.1093/bioinformatics/btaa472 · Cited by 61 · see citing works
“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 61 · see citing works
Asymptotically optimal minimizers schemes
Marçais, G., DeBlasio, D., & Kingsford, C. (2018) · Bioinformatics · doi:10.1093/bioinformatics/bty258 · Cited by 56 · see citing works
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 53 · see citing works
“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 · see citing works
“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 · see citing works
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 53 · see citing works
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 · see citing works
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 49 · see citing works
“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 · see citing works
“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 · see citing works
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 · see citing works
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 · see citing works
“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 · see citing works
ntLink: A Toolkit for De Novo Genome Assembly Scaffolding and Mapping Using Long Reads
Coombe, L., Warren, R. L., Wong, J., et al. (2023) · Current Protocols · doi:10.1002/cpz1.733 · Cited by 46 · see citing works
“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 · see citing works
“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 · see citing works
“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 · see citing works
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 · see citing works
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 43 · see citing works
“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 43 · see citing works
“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 · see citing works
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 · see citing works
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 · see citing works
“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 42 · see citing works
“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 · see citing works
Data-dependent bucketing improves reference-free compression of sequencing reads
Patro, R., & Kingsford, C. (2015) · Bioinformatics · doi:10.1093/bioinformatics/btv248 · Cited by 40 · see citing works
“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 · see citing works
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 · see citing works
“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 · see citing works
Song, L., & Langmead, B. (2024) · Genome biology · doi:10.1186/s13059-024-03244-4 · Cited by 38 · see citing works
“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 36 · see citing works
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 52 · see citing works
“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 38 · see citing works
“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 36 · see citing works
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 · see citing works
“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 36 · see citing works
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 · see citing works
“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 · see citing works
“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
- 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 › 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
- 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
