Kept on Wikipedia:Minimizer
 | This article may be too technical for most readers to understand. Please help improve it to make it understandable to non-experts, without removing the technical details. (July 2021) (Learn how and when to remove this template message) |
In bioinformatics, given a fixed window length w, minimizer is the smallest k-mer in a pre-defined ordering (e.g. lexicographically or by hash value) of each k-mer in the window. For a sequence, minimizers from sliding windows yield a compact representation that can be used in a wide range of genome analyses such as mapping, assembly and read classification. A minimizer algorithm has three parameters: (O,w,k). O is the total order of the k-mers and determines how kmers are ordered. w is the window length and k is the kmers length. Thus, for every window, w-k+1 k-mers are ordered according to O and the smallest k-mer is selected. Sequences with length longer than w will yield an ordered minimizer set which includes contiguity information unlike unordered k-mer sets.
History
The concept of minimizers was first introduced by Roberts et al. in 2004 for biological sequence comparison to address the large storage space needed when using the seed-and-extend performing biological sequence comparison using the seed-and-extend approach, which requires extraction and storage of all k-mers in the sequences being compared. The use of minimizers could accomplish this using a few representative k-mers; thus, significantly reducing storage requirements. Minimizers were selected according to the lexicographical ordering of k-mers within each window and ties were broken by sampling all equally minimum k-mers.[1]
Coincidentally, a similar concept was proposed by Schleimer in 2003 named winnowing for document fingerprinting. The k-grams, which are analogous to k-mers, are hashed and the k-gram with the smallest hash value is selected as the minimizer. To break ties, Schleimer used an approach called robust winnowing where minimizers that have been encountered in previous windows are preferred.[2]
Minimizer schemes
A minimizer scheme refers to the method used for ordering and selecting k-mers. Density, which refers to the fraction of k-mers selected for a given sequence, is a metric that can be used to evaluate the performance of a scheme.[3] Various methods have been developed for selecting a set of k-mers with as low density as possible while ensuring that sequences with an exact match of at least w + k - 1 bases long have a common minimizer.
Lexicographical ordering
Lexicographical ordering refers to the selection of k-mers based on alphabetical order. For example, if considering all possible 4-mers, "AAAA" would be the smallest. Although this was the standard scheme, it's biased to sampling more minimizers over low-complexity regions.[3] When introducing minimizers, Roberts et al. acknowledged this problem and proposed ways to increase the chance of rare k-mers being minimizers by re-ordering based on nucleotide frequency.[1] For example, rather than following the lexicographical order of A, C, G, T, the nucleotides could be ordered C, A, T, G such that "CCCC" would be the smallest k-mer.
Pseudo-random ordering
Given the problems mentioned with homopolymer runs, a more common minimizer scheme is to improve pseudo-randomness prior to lexicographical ordering.[4] Often this involves representing the nucleotide sequences as base-4 digits followed by hashing or the use of XOR operations.
Weighted minimizers
Weighted minimizers addresses the issue of frequently occurring k-mers, such as those in repetitive genomic segments, by considering a weight for each k-mer. The advantage of this is that it allows biased selection of certain k-mers over others. Specifically, the higher the weight of a k-mer relative to others within the same window, the more likely it is to be sampled as a minimizer.[5]
There are several methods of assigning weights, for example:
- Winnowmap, a weight-minimizer sampling algorithm, assigns lower weights to low complexity k-mers[5]
- Canu, a long-read assembler, uses term frequency-inverse document frequency (tf-idf) weighting for sequence overlap detection[6]
The use of weights is a promising alternative to the popular approach of masking low-complexity regions, as done in tools such as Minimap2.[7] It has been shown that masking filters out these frequent minimizers; thus, minimizer matches between sequences sharing sufficiently long substrings are no longer guaranteed.[5]
Applications
Mapping
Mapping biological reads to references is a crucial step in most genome analysis studies. Algorithms such as Needleman–Wunsch and Smith–Waterman provide accurate mappings of reads; however, these techniques are sensitive to sequencing errors and can be inefficient when the mapped sequences are long. That's why for long-reads, minimizer adapted algorithms have been developed.
- Minimap2 stores minimizers positions in reference and uses them as seeds to map long-reads in a seed-and-extend approach.[7]
Assembly
Short-reads yield comparatively more accurate reads, however, due to the abundance of repetitive regions of the genome the length of short-reads may not be enough to resolve these repeats in a de novo assembly.[6] To overcome this problem, long-read methods can be utilized for de novo assembly.[6] In these approaches overlap graphs are generated based on minimizers or minimizer alike sampling of k-mers. Then overlap graphs are traversed to produce an assembly.
- Canu does not directly utilize minimizers but uses the same concept as the MinHash algorithm where k-mers with the minimum hash value are considered for sequence similarity.[6]
- Shasta overlaps reads based on randomly choosen kmers acting as markers.[8]
- MHAP is integrated upon the Celera Assembler and maps long-reads to the assemblies via minimizer concordance to provide long-range information. This approach is reported to increase the continuity of assemblies.[9]
Read binning
Read binning with minimizers is used for pre-processing or optimizing queries on k-mers.
- Kraken is a metagenomic classifier for reads that queries the read k-mers against a database where they are related with a taxonomic id. To optimize these queries k-mers are binned according to their minimizers.[10]
- MSPKmerCounter is a kmer counting tool. Considering the large genomes this task can be memory intensive, that's why MSPKmerCounter optimizes the process by binning k-mers according to their novel technique Minimum Substring Partitioning which is the almost same concept with minimizer.[11]
References
- ↑ 1.0 1.1 Roberts, Michael (2004). "Reducing storage requirements for biological sequence comparison". Bioinformatics. 20 (18): 3363–9. doi:10.1093/bioinformatics/bth408. PMID 15256412.
- ↑ Schleimer, Saul (9 June 2003). "Winnowing: local algorithms for document fingerprinting". SIGMOD '03: Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data. Sigmod '03: 76–85. doi:10.1145/872757.872770. ISBN 9781581136340. Unknown parameter
|s2cid=ignored (help) - ↑ 3.0 3.1 Marçais, Guillaume; Pellow, David; Bork, Daniel; Orenstein, Yaron; Shamir, Ron; Kingsford, Carl (15 July 2017). "Improving the performance of minimizers and winnowing schemes". Bioinformatics. 33 (14): i110–i117. doi:10.1093/bioinformatics/btx235. ISSN 1367-4803. PMC 5870760. PMID 28881970.
- ↑ Edgar, Robert (5 February 2021). "Syncmers are more sensitive than minimizers for selecting conserved k‑mers in biological sequences". PeerJ. 9: e10805. doi:10.7717/peerj.10805. ISSN 2167-8359. PMC 7869670 Check
|pmc=value (help). PMID 33604186 Check|pmid=value (help). - ↑ 5.0 5.1 5.2 Jain, Chirag; Rhie, Arang; Zhang, Haowen; Chu, Claudia; Walenz, Brian P.; Koren, Sergey; Phillippy, Adam M. (1 July 2020). "Weighted minimizer sampling improves long read mapping". Bioinformatics. 36 (Supplement_1): i111–i118. doi:10.1093/bioinformatics/btaa435. ISSN 1367-4803. PMC 7355284 Check
|pmc=value (help). PMID 32657365 Check|pmid=value (help). - ↑ 6.0 6.1 6.2 6.3 Koren, Sergey; Walenz, Brian P.; Berlin, Konstantin; Miller, Jason R.; Bergman, Nicholas H.; Phillippy, Adam M. (2017). "Canu: scalable and accurate long-read assembly via adaptive k-mer weighting and repeat separation". Genome Research. 27 (5): 722–736. doi:10.1101/gr.215087.116. ISSN 1088-9051. PMC 5411767. PMID 28298431.
- ↑ 7.0 7.1 Li, Heng (15 September 2018). "Minimap2: pairwise alignment for nucleotide sequences". Bioinformatics. 34 (18): 3094–3100. doi:10.1093/bioinformatics/bty191. ISSN 1367-4803. PMC 6137996. PMID 29750242.
- ↑ Shafin, K.; Pesout, T.; Lorig-Roach, R.; et al. (2020). "Nanopore sequencing and the Shasta toolkit enable efficient de novo assembly of eleven human genomes". Nat Biotechnol. 38 (9): 044–1053. doi:10.1038/s41587-020-0503-6. PMC 7483855 Check
|pmc=value (help). PMID 32686750 Check|pmid=value (help). - ↑ Berlin, Konstantin (2015). "Assembling large genomes with single-molecule sequencing and locality-sensitive hashing". Nature Biotechnology. 33 (6): 623–630. doi:10.1038/nbt.3238. PMID 26006009. Unknown parameter
|s2cid=ignored (help) - ↑ Wood, Derrick E.; Salzberg, Steven L. (3 March 2014). "Kraken: ultrafast metagenomic sequence classification using exact alignments". Genome Biology. 15 (3): R46. doi:10.1186/gb-2014-15-3-r46. ISSN 1474-760X. PMC 4053813. PMID 24580807.
- ↑ Li, Yang; XifengYan (2015). "MSPKmerCounter: A Fast and Memory Efficient Approach for K-mer Counting". arXiv:1505.06550 [q-bio.GN].
This article "Minimizer" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:Minimizer. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.
|
This page exists already on Wikipedia. |
