A run-length-compressed skiplist data structure for dynamic GBWTs supports time and space efficient pangenome operations over syncmers

Abstract

Skiplists (Pugh, 1990) 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 BWTs that supports O(logR) rank and access operations, and a dynamic version of this 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, singlethreaded in 52 minutes, on top of a 4GB 63bp syncmer set built in 37 minutes. Arbitrarily long maximal exact matches (MEMs) can then be found as seeds for sequence matches to the graph at a search rate of approximately 1Gbp per 10 seconds per thread.