Search bioRxiv⌕ Search
Home/Archive/bioRxiv

bioRxiv · 10.64898/2026.11.10.765781

Fast Pangenome Matching Statistics in Compressed Space with Move Structures

Brown, N. K.·Sanaullah, A.·Shakya, P.·Zhang, S.·Langmead, B.
View original source ↗Export metadata ↓

Abstract

Matching statistics and supermaximal exact matches (SMEMs) are key inputs for sequence homology search and classification. Methods such as MONI, PHONI, and ropebwt3 compute these statistics using compressed pangenome indexes, but are substantially slower than methods that compute approximations of matching statistics, such as pseudo-matching lengths (PMLs). PMLs can be computed quickly in a single pass, but SMEM computation can require overlapping forward or backward passes over the query. We present ms2, a suite of algorithms that use "move structures" to compute matching statistics and SMEMs efficiently in compressed space. Our four algorithms compose move structures for the LF, {Psi}, {varphi}, and {varphi}-1 permutations with additional longest common prefix (LCP) array summaries and samples. The algorithms offer different tradeoffs among speed, index size, and support for reporting SMEM offsets. They inherit the move structure's fast, constant-time operations and achieve high throughput by leveraging the move structure's locality of reference. Thanks to recent advances, move structures can be constructed in optimal time and compressed space, including the LCP information needed for "match recovery" during SMEM computation. On 100 haplotypes of human chromosome 22, ms2's fastest algorithm computes matching statistics 35 to 48 times as fast as PHONI's online approach, while using an index of similar size. On the 472-haplotype HPRC2 pangenome and human reads, three ms2 modes achieve speedups of at least 22, 19, and 15 times over ropebwt3, whose index is about 15% the size of ms2's fastest mode. When additionally reporting SMEMs and their offsets, ms2 achieves speedups of 25 to 34 times over ropebwt3. Together, these advances enable online computation of matching statistics and SMEMs at a throughput that supports real-time processing of approximately 21 PromethION nanopore flow cells on a single thread. The ms2 software is open source and available at https://github.com/langmead-lab/ms2. It builds on the open-source TeraTools suite (https://github.com/ucfcbb/TeraTools) and Orbit library (https://github.com/drnatebrown/orbit). Experimental scripts and other details are described in: https://github.com/langmead-lab/ms2-experiments.

Explore related subjects

bioinformaticsPreprint

Keep this discovery

Explore connections, maps & timelines

BibTeXRIS

Brown, N. K., Sanaullah, A., Shakya, P., Zhang, S., Langmead, B.. 2026-11-11. Fast Pangenome Matching Statistics in Compressed Space with Move Structures. https://doi.org/10.64898/2026.11.10.765781

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

KEEP EXPLORING

Related preprints

bioRxiv2026

Comparative functional genomics reveals distributed SERPINE1 like characteristics among Drosophila serpins

Serpins (serine protease inhibitors) regulate proteolytic activity through a suicide-substrate inhibitory mechanism, whereby the serpin covalently traps and inactivates their target protease. Serpins are broadly conserved across eukaryotes, but the evolutionary and functional relationships between human SERPINE1, and Drosophila Serpins in incompletely defined. To identify candidate Drosophila functional analogs of SERPINE1/PAI-1, a multi-omics framework was applied to thoroughly compare the serpins across species. The multi-level analysis integrated orthology prediction, protein sequence and structural characterization, phylogenetic reconstruction, bulk tissue transcriptomics, single-cell transcriptomics, and aging-associated expression analysis. Candidate serpins (Spn42Da, Spn42Db, Spn42Dc, Spn42Dd, Spn28B, and Spn28F) were evaluated using DIOPT, AlphaFold/ChimeraX structural comparisons, reactive center loop analyses, phylogenetic distances, GTEx, Human Protein Atlas, FlyAtlas2, Fly Cell Atlas, and Aging Fly Cell Atlas datasets. Comparative analyses demonstrated full-length sequence and reactive center loop (RCL) divergence despite preservation of the canonical serpin fold. Tissue, cell-type, and age-associated expression analysis revealed distinct candidate-specific patterns. Spn42Dd comparisons uncovered similarities to human SERPINE1 in sequence/structural and broad expression but did not represent the strongest overall cross-species expression correlations. Spn42Da and Spn42Db received the highest cross species integrated support. Quality check of the ranking confirmed that Spn42Da and Spn42Db were stable top candidates across orthology, sequence alignment, and expression domains. The multi-domain analysis was unable to identify a single definitive Drosophila serpin as the closest counterpart to human SERPINE1, indicating that cross-species similarity is distributed across multiple candidate serpins. This study therefore provides a quantitative method for prioritizing potential evolutionary and functional analogs across highly divergent species.

bioinformatics↗
bioRxiv2026

CellChat Hotspot: A Targeted Approach to Cell Cell Communication Analysis With Spatial transcriptomics Validation.

Abstract. In recent years, single cell RNA sequencing (scRNA seq) has enabled the investigation of intercellular communication through Cell Cell Communication (CCC) tools such as CellChat. Despite their potential, these approaches remain challenging to interpret, particularly when global analyses generate complex interaction networks that may include biologically irrelevant signals. To address this limitation, we developed a framework termed CellChat Hotspot, designed to improve the biological interpretability of inferred communication networks. This approach integrates gene set enrichment analysis with a context driven filtering strategy, selecting both genes and cells based on their functional relevance prior to communication inference. Applied to stage II colon cancer data, CellChat Hotspot enabled the identification of condition-specific interaction patterns associated with recurrence. Non recurrent patients showed enrichment of immune related processes, whereas recurrent cases were characterized by pathways associated with invasion and metastasis. Notably, a loss of interaction in the HSPG pathway between CALB1+ and stromal cells was observed in recurrent patients, suggesting a potential disruption of cell matrix adhesion mechanisms. To verify the reliability of this finding, we applied the framework to spatial transcriptomics data, which confirmed the presence of the HSPG2 DAG1 interaction in non-recurrent tumors and its near absence in recurrent ones. Overall, this framework provides a biologically guided strategy for studying intercellular communication in complex systems such as the tumor microenvironment.

bioinformatics↗
bioRxiv2026

DiffTernary: a Diffusion Model for Molecular Glue Ternary Complex Docking

Molecular glues (MGs) modulate protein function by inducing or stabilizing protein interactions. However, accurately modeling MG ternary complexes remains challenging. Here, we present DiffTernary, a diffusion-based docking method for the joint prediction of relative protein arrangement and MG binding pose. We introduce Ternary-PDB, a dataset of 76,702 experimentally determined ternary complexes curated from the Protein Data Bank using structural filters and a release cutoff aligned with AlphaFold 3 (AF3). When trained on this dataset, DiffTernary achieved acceptable protein-protein interaction (PPI) predictions (DockQ > 0.23) for 50.0% of MGBench complexes with a single prediction, compared with 51.1% for AF3. In comparisons with AF3, OpenFold3, ESMFold2, Protenix-v1 and Protenix-v2, DiffTernary ranked second with a best-of-25 PPI prediction success rate of 78.4%, behind ESMFold2 (90.9%) and ahead of AF3 (72.7%). A separate DiffTernary model trained on TernaryDB achieved a mean DockQ of 0.306 on the 94 complexes in the TernaryDB MGD test set with a single prediction, compared with 0.228 for DeepTernary. Confidence-based selection among 40 samples yielded acceptable PPI predictions for 41.5% of complexes, compared with 30.9% for DeepTernary. An E2Former variant increased training and sampling throughput 6.90-fold and 4.37-fold, respectively, under the evaluated configurations. Together, DiffTernary and Ternary-PDB provide an efficient docking approach for MG complex prediction and a valuable structural resource for MG discovery and design.

bioinformatics↗