bioRxiv Science⌕ Search
Home/Archive/bioRxiv

bioRxiv · 10.64898/2026.02.12.705572

Theseus: Fast and Optimal Affine-Gap Sequence-to-Graph Alignment

Jimenez-Blanco, A.·Lopez-Villellas, L.·Moure, J. C.·Moreto, M.·Marco-Sola, S.
View original source ↗Export metadata ↓

Abstract

MotivationSequence-to-graph alignment is a central problem in bioinformatics, with applications in multiple sequence alignment (MSA) and pangenome analysis, among others. However, current algorithms for optimal affine-gap alignment impose high memory and computational requirements, limiting their scalability to aligning long sequences to complex graphs. Practical solutions partially address this problem using heuristic strategies that ultimately trade off optimality for speed. ResultsThis work presents Theseus, a novel, fast, and optimal affine-gap sequence-to-graph alignment algorithm. Theseus leverages similarities between genomic sequences to accelerate the alignment computation and reduces the overall memory requirements without compromising optimality. To that end, Theseus exploits the diagonal transition property to process only a subset of the dynamic programming cells, combined with a sparse-data strategy that enables efficient sequence-to-graph alignment. Moreover, our algorithm supports optimal affine-gap alignment on arbitrary directed graphs, including those with cycles. We evaluate Theseus on two key problems: multiple sequence alignment (MSA) and pangenome read mapping. For MSA, we compare it against the state-of-the-art methods SPOA, abPOA, and POASTA. Theseus is 2.0x to 232.2x faster than the other two optimal aligners, SPOA and POASTA. Compared with abPOA, a heuristic aligner, Theseus is 3.3x faster on average, while ensuring optimality. For pangenome read mapping, we benchmark Theseus against the alignment stage of the popular mapping tool vg map, along with the alignment kernels of SPOA, abPOA, and POASTA. Theseus outperforms the other methods, showing a 1.9x to 16.9x speed improvement on short reads. AvailabilityTheseus code and documentation are publicly available at https://github.com/albertjimenezbl/theseus-lib. Contactalbert.jimenez.blanco@upc.es

Source connections

Explore related subjects

bioinformaticsPreprint

Keep this discovery

Explore connections, maps & timelines

BibTeXRIS

Jimenez-Blanco, A., Lopez-Villellas, L., Moure, J. C., Moreto, M., Marco-Sola, S.. 2026-02-14. Theseus: Fast and Optimal Affine-Gap Sequence-to-Graph Alignment. https://doi.org/10.64898/2026.02.12.705572

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

KEEP EXPLORING

Related preprints

bioRxiv2026

deepTools4: Faster, Scalable, and Modernized Genomic Data Analysis

The deepTools suite is widely used for quality control, summarization, and visualization of high-throughput sequencing data. However, as genomic datasets grow in scale and depth, existing tools often become computational bottlenecks. We present deepTools4, a modernized framework designed for high performance, scalability, and enhanced usability, while maintaining seamless integration with the Galaxy platform. Core functionality has been rewritten and thoroughly benchmarked, achieving substantial computational speed-ups. Visualization tools have been modernized to provide more intuitive, high-quality graphical outputs. In addition, our testing framework has been expanded to facilitate continuous development and ensure robustness. We demonstrate the utility of deepTools4 across diverse epigenomics and transcriptomics datasets, highlighting its ability to summarize genome-wide signals, apply a wide range of common normalization methods, and visualize enrichment patterns. The enhanced deepTools4 framework delivers a faster, more scalable solution for reproducible genome-wide analysis and interpretation across many sequencing modalities. Availability: https://github.com/deeptools/deepTools/

bioinformatics↗
bioRxiv2026

Reproducibility and cross-dataset concordance of drug-induced transcriptional responses

Drug-perturbation transcriptomic resources are expanding, but the reproducibility and cross-source consistency of the responses they measure remain critical to their use. We compared six resources using independent replicates, matched-drug analyses, and response decomposition. High agreement in treated expression did not translate into equally repeatable drug-induced changes. Cross-source response concordance was generally limited, including under matched cell and treatment conditions, although some comparisons retained drug-specific information. In Tahoe, a control-expression-only baseline left substantial drug-specific variation unresolved. Measured drug main effects - the average responses across cell lines - provided information for predicting cell-specific interactions, with this relationship retained in a cross-plate validation. Exploratory analyses of structure, target, and external-response representations identified modest signals in selected pipelines. Together, these analyses characterize the reliability and transferability of current perturbation resources and identify prediction of drug main effects as a key bottleneck in the framework examined, motivating shared reference measurements and better recovery of drug-specific responses.

bioinformatics↗
bioRxiv2026

Propensity-Adjusted AUC under Nuisance-Model Misspecification

Propensity adjustment compares medical-image detector scores within groups with similar measured properties, such as stain or focus. We examine its sensitivity to the nuisance model that forms those groups. Under Gaussian latent-index assumptions and exact linear-index strata, a closed-form correlation gives an exact boundary for adjusted AUC to fall below one half. Quadrature matches 36 simulation cells within 0.008. Inflation and attenuation relative to correct adjustment are empirical findings, not general ordering results. An overlap screen and a self-stratified control introduced for this study miss 140 of 141 simulated cells with absolute error above 0.05: checking the fitted propensity cannot certify completeness of the adjustment set. On real pathology corpora, logistic and boosted-tree models using the same 16 features disagree. Among splits where both pass both checks, mean adjusted-AUC gaps are 0.057 on acid-fast bacilli (AFB), 0.048 on Kaggle, and 0.049 on PCam, over three, five, and three splits respectively. These gaps measure model sensitivity; neither estimate is known to be correct. A controlled colour shift moves adjusted AUC relative to model-specific references in the predicted direction in 78 of 80 label-dependent cells. Broader balance and label-fit diagnostics favour trees without certifying their adjusted AUC. We recommend reporting sensitivity across nuisance models alongside these diagnostics. Reversal relative to known truth occurs in constructed stress tests; its frequency in practice remains unknown.

bioinformatics↗