A Run-Length-Compressed Skiplist Data Structure for Dynamic GBWTs Supports Time- and Space-Efficient Pangenome Operations over Syncmers.

Authors

Richard Durbin

Published in

Journal of computational biology : a journal of computational molecular cell biology. Pages 15578666261495122. Oct 15, 2026. Epub Oct 15, 2026.

Abstract

Skiplists are probabilistic data structures over ordered lists supporting $O\left(\text{log}N\right)$ 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\left(\text{log}R\right)$ rank and access operations, as well as a dynamic version that supports $O(\text{log}R+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.

PMID:
42878135
Bibliographic data and abstract were imported from PubMed on 16 Oct 2026.

Read full publication at:
Please sign in to see all details.

Stats

1-terrible, 9-excellent. How would you rate this publication? Sign in in to submit your rating.

Post a comment

You need to be signed in to post comments. You can sign in here.

Comments

There are no comments yet.