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

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