Biology subjects

Alanko, J. N.

Publications and source records attributed to Alanko, J. N..

4 recordsLinked to original sources

bioRxiv2024

Finimizers: Variable-length bounded-frequency minimizers for k-mer sets

The minimizer of a k-mer is the smallest m-mer inside the k-mer according to some order relation < of the m-mers. Minimizers are often used as keys in hash tables in indexing tasks in metagenomics and pangenomics. The main weakness of minimizer-based indexing is the possibility of very frequently occurring minimzers, which can slow query times down significantly. Popular minimizer alignment tools employ various and often wild heuristics as workarounds, typically by ignoring frequent minimizers or blacklisting commonly occurring patterns, to the detriment of other metrics (e.g., alignment recall, space usage, or code complexity). In this paper, we introduce frequency-bounded minimizers, which we call finimizers, for indexing sets of k-mers. The idea is to use an order relation < for minimizer comparison that depends on the frequency of the minimizers within the indexed k-mers. With finimizers, the length m of the m-mers is not fixed, but is allowed to vary depending on the context, so that the length can increase to bring the frequency down below a user-specified threshold t. Setting a maximum frequency solves the issue of very frequent minimizers and gives us a worstcase guarantee for the query time. We show how to implement a particular finimizer scheme efficiently using the Spectral Burrows-Wheeler Transform (SBWT) (Alanko et al., Proc. SIAM ACDA, 2023) augmented with longest common suffix information. In experiments, we explore in detail the special case in which we set t = 1. This choice simplifies the index structure and makes the scheme completely parameter-free apart from the choice of k. A prototype implementation of this scheme exhibits k-mer localization times close to, and often faster than, stateof-the-art minimizer-based schemes. The code is available at https://github.com/ElenaBiagi/Finito.

bioinformatics↗

bioRxiv2023

Themisto: a scalable colored k-mer index for sensitive pseudoalignment against hundreds of thousands of bacterial genomes

MotivationHuge data sets containing whole-genome sequences of bacterial strains are now commonplace and represent a rich and important resource for modern genomic epidemiology and metagenomics. In order to efficiently make use of these data sets, efficient indexing data structures -- that are both scalable and provide rapid query throughput -- are paramount. ResultsHere, we present Themisto, a scalable colored k-mer index designed for large collections of microbial reference genomes, that works for both short and long read data. Themisto indexes 179 thousand Salmonella enterica genomes in 9 hours. The resulting index takes 142 gigabytes. In comparison, the best competing tools Metagraph and Bifrost were only able to index 11 thousand genomes in the same time. In pseudoalignment, these other tools were either an order of magnitude slower than Themisto, or used an order of magnitude more memory. Themisto also offers superior pseudoalignment quality, achieving a higher recall than previous methods on Nanopore read sets. Availability and implementationThemisto is available and documented as a C++ package at https://github.com/algbio/themisto available under the GPLv2 license. Contactjarno.alanko@helsinki.fi Supplementary informationSupplementary data are available at Bioinformatics online.

bioinformatics↗

bioRxiv2022

Succinct k-mer Set Representations Using Subset Rank Queries on the Spectral Burrows-Wheeler Transform (SBWT)

The k-spectrum of a string is the set of all distinct substrings of length k occurring in the string. This is a lossy but computationally convenient representation of the information in the string, with many applications in high-throughput bioinformatics. In this work, we define the notion of the Spectral Burrows-Wheeler Transform (SBWT), which is a sequence of subsets of the alphabet of the string encoding the k-spectrum of the string. The SBWT is a distillation of the ideas found in the BOSS and Wheeler graph data structures. We explore multiple different approaches to index the SBWT for membership queries on the underlying k-spectrum. We identify subset rank queries as the essential subproblem, and propose four succinct index structures to solve it. One of the approaches essentially leads to the known BOSS data structure, while the other three offer attractive time-space trade-offs and support simpler query algorithms that rely only on fast rank queries. The most general approach involves a novel data structure we call the subset wavelet tree, which we find to be of independent interest. All of the approaches are also amendable to entropy compression, which leads to good space bounds on the sizes of the data structures. Using entropy compression, we show that the SBWT can support membership queries on the k-spectrum of a single string in O(k) time and (n + k)(log{sigma} + 1/ ln 2) + o((n + k){sigma}) bits of space, where n is the number of distinct substrings of length k in the input and{sigma} is the size of the alphabet. This improves from the time O(k log{sigma} ) achieved by the BOSS data structure. We show, via experiments on a range of genomic data sets, that the simplicity of our new indexes translates into large performance gains in practice over prior art.

bioinformatics↗

bioRxiv2022

Eulertigs: minimum plain text representation of k-mer sets without repetitions in linear time

A fundamental operation in computational genomics is to reduce the input sequences to their constituent k-mers. For maximum performance of downstream applications it is important to store the k-mers in small space, while keeping the representation easy and efficient to use (i.e. without k-mer repetitions and in plain text). Recently, heuristics were presented to compute a near-minimum such representation. We present an algorithm to compute a minimum representation in optimal (linear) time and use it to evaluate the existing heuristics. For that, we present a formalisation of arc-centric bidirected de Bruijn graphs and carefully prove that it accurately models the k-mer spectrum of the input. Our algorithm first constructs the de Bruijn graph in linear time in the length of the input strings (for a fixed-size alphabet). Then it uses a Eulerian-cycle-based algorithm to compute the minimum representation, in time linear in the size of the output. 2012 ACM Subject ClassificationApplied computing [->] Computational biology; Theory of computation [->] Data compression; Theory of computation [->] Graph algorithms analysis; Theory of computation [->] Data structures design and analysis

bioinformatics↗