Theory of local k-mer selection with applications to long-read alignment
Open Access
- 19 November 2021
- journal article
- research article
- Published by Oxford University Press (OUP) in Bioinformatics
- Vol. 38 (20) , 4659-4669
Abstract
Selecting a subset of k-mers in a string in a local manner is a common task in bioinformatics tools for speeding up computation. Arguably the most well-known and common method is the minimizer technique, which selects the ‘lowest-ordered’ k-mer in a sliding window. Recently, it has been shown that minimizers may be a sub-optimal method for selecting subsets of k-mers when mutations are present. There is, however, a lack of understanding behind the theory of why certain methods perform well. We first theoretically investigate the conservation metric for k-mer selection methods. We derive an exact expression for calculating the conservation of a k-mer selection method. This turns out to be tractable enough for us to prove closed-form expressions for a variety of methods, including (open and closed) syncmers, (a, b, n)-words, and an upper bound for minimizers. As a demonstration of our results, we modified the minimap2 read aligner to use a more conserved k-mer selection method and demonstrate that there is up to an 8.2% relative increase in number of mapped reads. However, we found that the k-mers selected by more conserved methods are also more repetitive, leading to a runtime increase during alignment. We give new insight into how one might use new k-mer selection methods as a reparameterization to optimize for speed and alignment quality. Simulations and supplementary methods are available at https://github.com/bluenote-1577/local-kmer-selection-results. os-minimap2 is a modified version of minimap2 and available at https://github.com/bluenote-1577/os-minimap2. Supplementary data are available at Bioinformatics online.Keywords
All Related Versions
Funding Information
- Natural Sciences and Engineering Research Council of Canada (NSERC
- NSERC (RGPIN-2022-03074)
This publication has 29 references indexed in Scilit:
- Fast genotyping of known SNPs through approximate k-mer matchingBioinformatics, 2016
- Computational biology in the 21st centuryCommunications of the ACM, 2016
- Mash: fast genome and metagenome distance estimation using MinHashGenome Biology, 2016
- Coming of age: ten years of next-generation sequencing technologiesNature Reviews Genetics, 2016
- Kraken: ultrafast metagenomic sequence classification using exact alignmentsGenome Biology, 2014
- Sequence assembly demystifiedNature Reviews Genetics, 2013
- PBSIM: PacBio reads simulator—toward accurate genome assemblyBioinformatics, 2012
- SCALCE: boosting sequence compression algorithms using locally consistent encodingBioinformatics, 2012
- Mapping single molecule sequencing reads using basic local alignment with successive refinement (BLASR): application and theoryBMC Bioinformatics, 2012
- Reducing storage requirements for biological sequence comparisonBioinformatics, 2004