A Run-Length-Compressed Skiplist Data Structure for Dynamic GBWTs Supports Time- and Space-Efficient Pangenome Operations over Syncmers.
- 1Department of Genetics, University of Cambridge, Cambridge, United Kingdom.
- 2Wellcome Sanger Institute, Cambridge, United Kingdom.
Abstract
Skiplists are probabilistic data structures over ordered lists supporting O(logN) insertion and search, which share many properties with balanced binary trees. Previously, we introduced the graph Burrows-Wheeler transform (GBWT) to support efficient search over pangenome path sets, but current implementations are static and cumbersome to build and use. Here, we introduce a doubly linked skiplist variant over run-length-compressed Burrows-Wheeler transforms that supports O(logR) rank and access operations, as well as a dynamic version that supports O(logR+S) rank and insert operations, where R is the number of runs and S is the number of symbols in the alphabet. We use these to store and search over paths through a syncmer graph built from Edgar's closed syncmers, equivalent to a sparse de Bruijn graph. Code is available in rskip.[ch] within the syng package at github.com/richarddurbin/syng. This builds a 5.8 GB lossless GBWT representation of 92 full human genomes, single-threaded in 52 minutes, on top of a 4GB 63bp syncmer set built in 37 minutes. Arbitrarily long maximal exact matches can then be found as seeds for sequence matches to the graph at a search rate of ∼1Gbp per 10 seconds per thread.
Related
- From plant pangenome assemblies to operational graph references
- MineGraph facilitates plastid and mitochondrial graph pangenome analysis in plants
- The Emirati pangenome featuring a diploid chromosome-level reference
- DNA CODEC: compressed obfuscated DNA encoding in cells for secure in vivo data storage
- The Vizitig pangenome and pantranscriptome explorer
BibTeX
@article{durbin2026runlengthcompressed,
title = {{A Run-Length-Compressed Skiplist Data Structure for Dynamic GBWTs Supports Time- and Space-Efficient Pangenome Operations over Syncmers.}},
author = {Richard Durbin},
journal = {Journal of computational biology : a journal of computational molecular cell biology},
year = {2026},
month = oct,
doi = {10.1177/15578666261495122},
url = {https://europepmc.org/article/MED/42878135},
note = {CC BY},
}
RIS
TY - JOUR
TI - A Run-Length-Compressed Skiplist Data Structure for Dynamic GBWTs Supports Time- and Space-Efficient Pangenome Operations over Syncmers.
AU - Richard Durbin
PY - 2026
DA - 2026/10/15
JO - Journal of computational biology : a journal of computational molecular cell biology
DO - 10.1177/15578666261495122
UR - https://europepmc.org/article/MED/42878135
AB - Skiplists are probabilistic data structures over ordered lists supporting O(logN) insertion and search, which share many properties with balanced binary trees. Previously, we introduced the graph Burrows-Wheeler transform (GBWT) to support efficient search over pangenome path sets, but current implementations are static and cumbersome to build and use. Here, we introduce a doubly linked skiplist variant over run-length-compressed Burrows-Wheeler transforms that supports O(logR) rank and access operations, as well as a dynamic version that supports O(logR+S) rank and insert operations, where R is the number of runs and S is the number of symbols in the alphabet. We use these to store and search over paths through a syncmer graph built from Edgar's closed syncmers, equivalent to a sparse de Bruijn graph. Code is available in rskip.[ch] within the syng package at github.com/richarddurbin/syng. This builds a 5.8 GB lossless GBWT representation of 92 full human genomes, single-threaded in 52 minutes, on top of a 4GB 63bp syncmer set built in 37 minutes. Arbitrarily long maximal exact matches can then be found as seeds for sequence matches to the graph at a search rate of ∼1Gbp per 10 seconds per thread.
SN - 1066-5277
SN - 1557-8666
ER -