bioRxiv Science⌕ Search
Home/Archive/bioRxiv

bioRxiv · 10.1101/2025.05.19.654936

Sequence alignment with k-bounded matching statistics

Mäklin, T.·Alanko, J. N.·Biagi, E.·Puglisi, S. J.
View original source ↗Export metadata ↓

Abstract

Finding high-quality local alignments between a query sequence and sequences contained in a large genomic database is a fundamental problem in computational genomics, at the core of thousands of biological analysis pipelines. Here, we describe a novel algorithm for approximate local alignment search based on the so-called k-bounded matching statistics of the query sequence with respect to an indexed database of sequences. We compute the k-bounded matching statistics, which capture the longest common suffix lengths of consecutive k-mer matches between query and target sequences, using the spectral Burrows-Wheeler transform, a data structure that enables computationally efficient queries. We show that our method is as fast and as accurate as state-of-the-art tools in several bacterial genomics tasks. Our method is available as a set of three kbo Rust packages that provide a command-line interface, a graphical user interface that runs in a browser without server-side processing, and a core library that can be accessed by other tools.

Explore related subjects

bioinformaticsPreprint

Keep this discovery

Explore connections, maps & timelines

BibTeXRIS

Mäklin, T., Alanko, J. N., Biagi, E., Puglisi, S. J.. 2025-05-24. Sequence alignment with k-bounded matching statistics. https://doi.org/10.1101/2025.05.19.654936

Cite the original work for its findings. Save a collection to share your selection of sources.

KEEP EXPLORING

Related preprints

bioRxiv2026

Uniformly processed transcriptome-wide alternative splicing profiles for pediatric cancer research

Alterations in regulatory processes like alternative splicing contribute to pediatric cancer development. Although splicing aberrations have been observed in pediatric leukemias, alternative splicing has yet to be studied in pediatric cancers at scale, due to a lack of uniformly processed, sample-level pediatric cancer splicing profiles with non-diseased tissue comparators. We address this need by quantifying splice event usage for a curated set of bulk RNA-seq datasets from the NCI's Therapeutically Applicable Research to Generate Effective Treatments (TARGET, n = 1152) and Genotype-Tissue Expression (GTEx, n = 1098) as a comparator. This Treehouse Splice Compendium is accompanied by a reproducible workflow that was used to generate the data in the compendium and reflects the largest known RNA-seq dataset processed by the splice quantification tool Shiba. The compendium is part of a suite of large, uniformly processed datasets aggregated by the UCSC Treehouse Childhood Cancer Initiative and Alex's Lemonade Stand Foundation's Childhood Cancer Data Lab, which include the Treehouse Expression Compendia, refine.bio, and the Single-cell Pediatric Cancer Atlas.

bioinformatics↗
bioRxiv2026

POAnoise: A Graph-based Denoising Pipeline for Amplicon Sequencing Data

High-throughput DNA metabarcoding enables large-scale biodiversity assessment by identifying taxa from environmental samples, but its accuracy critically depends on denoising methods that separate true biological variation from PCR and sequencing errors. A persistent challenge is robust reconstruction of sequence diversity across abundance distributions, where low-abundance variants are particularly difficult to recover. We introduce POAnoise, a graph-based denoising framework that uses Partial Order Alignment (POA) to model relationships among noisy sequencing reads. POAnoise incrementally constructs sequence graphs that represent substitutions and indels, and derives consensus sequences from graph-supported paths using a weighted consensus strategy. By combining graph-based alignment with abundance-aware clustering, the method provides a structured way to reconstruct sequence variants from noisy amplicon data across heterogeneous abundance regimes. We evaluated POAnoise on simulated ITS and 16S datasets and compared its performance with established denoising methods, DADA2 and UNOISE3, across multiple parameter settings. Across the benchmark datasets, POAnoise generally achieved higher F1-scores and exhibited more stable performance across parameter configurations. In abundance-aware analyses, POAnoise showed reconstruction ratios closer to unity and reduced abundance-dependent deviation compared with DADA2, while remaining broadly comparable to UNOISE3 across most abundance classes. Overall, these results indicate that POAnoise can provide a robust alternative for amplicon denoising.

bioinformatics↗
bioRxiv2026

Serum metabolomics reveals signatures associated with physical resilience trajectories from middle to older age

Lifecourse physical resilience is defined by the ability to maintain abilities across multiple domains of physical performance. While the importance of physical resilience in functional independence and mobility disability is clear, studies investigating metabolomic signatures of physical resilience are lacking. Here, we performed untargeted metabolomics on serum samples from a community-based cohort of 237 individuals followed over 28 years, and applied spectral data mining tools to map identified metabolites to health phenotypes from public repositories. We identified metabolites across multiple chemical classes, including acylcarnitines, glutamine conjugates, and phosphocholines, that were differentially associated with physical resilience status. Notably, medium-chain acylcarnitines negatively associated with physical resilience were more frequently observed in disease phenotypes than in healthy individuals. Kynurenine, a tryptophan metabolite linked to age-related functional decline, increased more steeply with age in individuals with low physical resilience. We also found that metabolites of the antihypertensive drug verapamil were associated with physical resilience in a metabolism-dependent manner, differing between oxidative and glucuronidated forms. Together, these metabolic signatures offer a resource for identifying biochemical pathways and biomarkers relevant to physical resilience for healthy aging.

bioinformatics↗