2026/03/29 by Richard Durbin · 1 voice
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #Binary number #Data structure #De Bruijn graph #De Bruijn sequence #Genome Rearrangement Algorithms #Genomics and Phylogenetic Studies #Graph #Lossless compression #Probabilistic logic #Representation (politics) #Set (abstract data type) #Set operations
paper · pdf · doi:10.64898/2026.03.26.714584
openalex publication_date 2026/03/29 · openalex created_date 2026/03/31 · openalex updated_date 2026/07/17
Abstract Skiplists (Pugh, 1990) are probabilistic data structures over ordered lists supporting 𝒪 (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 BWTs that supports 𝒪 (log N ) rank and access operations, and a dynamic version of this that supports 𝒪 (log N + S ) rank and insert operations, where 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 (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.