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

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.