Theory of local k-mer selection with applications to long-read alignment.

ABSTRACT:

Motivation

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.

Results

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 variet

SUBMITTER: Shaw J 

PROVIDER: S-EPMC9563685 | biostudies-literature | 2022 Oct

REPOSITORIES: biostudies-literature