{"paper_id":"08ebf8c3-9434-445c-a823-9e99c6c85d71","body_text":"A run-length-compressed skiplist data structure\nfor dynamic GBWTs supports time and space\nefficient pangenome operations over syncmers\nRichard Durbin1,2\n1 Department of Genetics, University of Cambridge, Cambridge CB2 3EH, UK\n2 Wellcome Sanger Institute, Hinxton, Cambridge CB10 1SA, UK\nrd109@cam.ac.uk\nOrcidID 0000-0002-9130-1006\nAbstract.Skiplists (Pugh, 1990) are probabilistic data structures over\norderedlistssupporting O(log N )insertionandsearch,whichsharemany\nproperties with balanced binary trees. Previously we introduced the\ngraph Burrows-Wheeler transform (GBWT) to support efficient search\nover pangenome path sets, but current implementations are static and\ncumbersome to build and use. Here we introduce two doubly-linked\nskiplistvariantsoverrun-length-compressedBWTsthatsupport O(log N )\nrank, access and insert operations. We use these to store and search\nover paths through a syncmer graph built from Edgar’s closed syncmers,\nequivalent to a sparse de Bruijn graph. Code is available inrskip.[ch]\nwithinthe syngpackageat github.com/richarddurbin/syng.Thisbuilds\na5.8GBlosslessGBWTrepresentationof92fullhumangenomes(280Gbp\nincluding all centromeres and other repeats) single-threaded in 52 min-\nutes, on top of a 4GB 63bp syncmer set built in 37 minutes. Arbitrarily\nlong maximal exact matches (MEMs) can then be found as seeds for\nsequence matches to the graph at a search rate of approximately 1Gbp\nper 10 seconds per thread.\nKeywords: skip list · pangenome · GBWT · syncmer graph\n.CC-BY 4.0 International licenseavailable under a \n(which was not certified by peer review) is the author/funder, who has granted bioRxiv a license to display the preprint in perpetuity. It is made \nThe copyright holder for this preprintthis version posted March 29, 2026. ; https://doi.org/10.64898/2026.03.26.714584doi: bioRxiv preprint \n\nRskip data structures for pangenome GBWTs 1\n1 Introduction\nThe idea of pangenomes is that rather than use a fixed linear reference genome\nsequence we should represent the genetic variation known to be present in a\nspecies or population when analysing data from a new individual, or set of indi-\nviduals[23,2]. To do this we combine information from many independently as-\nsembled genomes, removing redundancy by collapsing together shared segments\nof sequence. A standard way to do this is in a graph, with shared sequence seg-\nments represented by vertices, which are connected by edges that indicate what\ncan follow what. Both the vertices and the edges are bi-directional, like highways\nor rail lines, which can be travelled in one direction or the other, with the se-\nquence for a vertex being reverse-complemented when traversed in the opposite\ndirection.\nMost pangenome graph applications allow all routes across vertices that fol-\nlow edges of the graph with equal likelihood, or perhaps weighted by the fre-\nquency of a vertex/edge in the set of reference genomes from which the graph was\nconstructed. However there is longer range information in the reference genomes,\nbased on shared haplotypes, that we want to use. In the railway analogy, the\ngraph is the network but to get from A to B you need to take a series of trains\nthat follow established paths through the network. This longer range information\nis what enables the powerful genotype imputation framework used for genetic\nassociation on millions of samples over the last fifteen years[10].\nRecent methods for genotype imputation[20] have exploited the positional\nBurrows-Wheeler transform (PBWT)[3], which provides efficient storage of and\nmatching to haplotype sequence panels. Our goal is to support a similarly ef-\nficient and powerful framework for pangenome graphs, where sequences do not\njust vary at colinearly aligned binary variants. As a step in this direction, I\nintroduce here a computational framework for efficient calculation over graph\nBurrows-Wheeler transforms (GBWTs), the corresponding data structure to the\nPBWT for pangenome graphs, and present a practical implementation.\nBelow I present first the use of graph Burrows-Wheeler transforms (GBWTs)\nto store and search paths through pangenome graphs, and then the use of a vari-\nant form of Pugh’s skip list[16], which I call Rskip, for efficient computation over\npangenome GBWTs. Then I describe key features of myrskip implementation\nand its use in thesyng package, which builds pangenome grpahs in which the\nvertices represent overlappingkmers selected using Edgar’s closed syncmer crite-\nrion[4].Thisisfollowedbytheresultsofapplying syngtotheHumanPangenome\nReference Consortium phase 1 release of 92 full human genomes[9].\n2 Theory\nHere we discuss using GBWTs to represent a set of paths on a pangenome graph\nand provide efficient search over these. We will use the term ‘vertex’ for the\nelemnents of the graph associated with sequences, in our case syncmers, and\n‘node’ for nodes in the internal Rskip data structure that we use to manage the\nrouting tables for the paths, which happens to also be a form of graph.\n.CC-BY 4.0 International licenseavailable under a \n(which was not certified by peer review) is the author/funder, who has granted bioRxiv a license to display the preprint in perpetuity. It is made \nThe copyright holder for this preprintthis version posted March 29, 2026. ; https://doi.org/10.64898/2026.03.26.714584doi: bioRxiv preprint \n\n2 Richard Durbin\n2.1 Path traversal and search in a sparse graph via local GBWTs\nFig. 1.LF mapping to follow a path entering as offset 1 in the path bundle from C and\nexiting as offset 2 in the path bundle to X. The local GBWTG provides the routing\ninformation, with the index inG being the sum of the incoming offset and the total\ncount of preceding symbols in the input directoryD. All offsets and indexes are 0-\nbased. Adapted from [21] with permission.\nGiven a graph vertex with a set of paths running through it, and an ordering\non each of the bundles of paths coming into the vertex from other vertices, it is\nnatural to also list the vertices from which the paths come, and hence derive a\nglobal ordering of incoming paths (left side of Figure 1). Then a simple routing\ntable of corresponding output nodes, as highlighted in purple in Figure 1), is\nall that is needed to specify the output vertex for each incoming path. Given\nthat the paths within each outgoing bundle are ordered colinearly with incoming\npaths, as for the X’s and Y’s in Figure 1, adjacent paths in a bundle will share\nrecent sequence, and by construction the routing table will correspond to the\nsubsection of the Burrows-Wheeler (BWT) transform over sequences of vertices\nwhere the last symbol corresponded to the current vertex. This graph vertex\nBWT is called the Graph Burrows-Wheeler transform[21,5].\nBecause sharing past sequence is predictive of sharing future sequence and\nspecifically the next symbol, BWTs in general and the GBWT in particular tend\nto contain runs of the same symbol. They are therefore efficiently compressed\nby run-length compression. The run-length compressed GBWT or rGBWT for\nFigure 1 would be((Y,1),(X,1),(Z,1),(X,2),(Y,2)).\nWhen following a path using a GBWT we need operationsocc(D, s) on the\ninput directory D to give the total count of input paths from symbols listed\nbefore s, access(G, i) to give the symbol at positioni in the GBWT G and\n.CC-BY 4.0 International licenseavailable under a \n(which was not certified by peer review) is the author/funder, who has granted bioRxiv a license to display the preprint in perpetuity. It is made \nThe copyright holder for this preprintthis version posted March 29, 2026. ; https://doi.org/10.64898/2026.03.26.714584doi: bioRxiv preprint \n\nRskip data structures for pangenome GBWTs 3\nrank(G, i, s) to give the number of timess appears before position i in G, as\nshown in Figure 1. The same operations support efficient matching. There are\nstandard algorithms linear in match length in terms ofocc() and rank() op-\nerations to find the number of paths matching a substring or to find maximal\nexact matches (MEMs) of a longer search string (this is a little imprecise for\nMEMs, but let’s ignore that here).\nNote that this construction shows that for the update operations we do not\nrequire counts for all vertex symbols, only the ones incident to the current vertex,\nnor a global ordering of the symbols, just a local ordering of those that are\nincident. This is good because there are many millions of vertices, and different\norderings may be preferable for different vertices.\nTypically BWTs are built statically by one process, and then an index struc-\nture is built over them by a different process to support the required operations.\nHere we introduce a novel data structure that naturally supports dynamic build-\ning of run-length compressed BWTs for efficient storage, traversal and search.\n2.2 Skip lists for dynamic run-length-compressed arrays\nIf we don’t want to move large memory blocks when we insert into a dynamic\narray the simplest structure would be a linked list, but this incurs linear time\ntraversal cost for allaccess() and rank(). There are many succinct data struc-\ntures that can reduce these toO(log R) (where R is the number of runs) or for\nsome operations even constant time[14], but typically these assume relatively\nsmall alphabets, whereas our alphabet size is potentially unbounded, reaching\nin practice at least tens of thousands due to the repetitive structure of the\ngenome (see results).\nHere we take advantage of the elegant skip list data structure introduced by\nPugh in 1990[16], which augments a linked list with additional layers generated\nby a random process in which each node has an upward parent with probability\np (Figure 2A). Skip lists provide a lightweight alternative to balanced trees, sup-\nporting access() in expected O(log R) time as in Figure 2B, and alsoO(log R)\ninsert() (and if wanted delete()) by keeping track of the last node visited\nat each level on a stack and updating their pointers and counts as necessary for\na new column. Storing run lengths is natural in a skip list because the nodes at\nupper levels already store counts. To supportrank() once we are located at a\nnode, we need to find the sum of counts of the same symbol in preceding nodes.\nWe could count forward along the list how many are in succeeding nodes, then\nsubtract from a total count that we maintain for each symbol, but this would\nbe a linear time operation. Instead I add a second set ofright pointers that\npoint to the next node at the same level with the same symbol, and counts for\nhow many of that symbol are present up to that node. Effectively this is em-\nbedding a skip list for each symbol within the same set of columns as in the\noriginal primary skip list. We also need to addup pointers in reverse to the\ndown pointers. See Figure 2C. Now we can find the number of copies of symbol\ns by moving up and right along theup and sRight pointers, going up whenever\npossible, and accumulating sCounts as we go. This is exactly reciprocal to the\n.CC-BY 4.0 International licenseavailable under a \n(which was not certified by peer review) is the author/funder, who has granted bioRxiv a license to display the preprint in perpetuity. It is made \nThe copyright holder for this preprintthis version posted March 29, 2026. ; https://doi.org/10.64898/2026.03.26.714584doi: bioRxiv preprint \n\n4 Richard Durbin\nFig. 2.Skip list and Rskip data structures. A: a standard skip list over a run-length\narray, with columns up to (in this case) two levels. B: the access() operation is\nperformed in expectedO(log R) time by starting at the top of the first column, moving\nright accumulating a partial sum, and dropping levels when the sum for the next\nright edge would exceed the target; only the partial sums coloured in red need to be\ncalculated. C: Rskip structure with additional pointers and counts between nodes for\nthe same symbol.\ninitial access() search, so has expected timeO(log Rs) where there areRs runs\nfor symbol s. Analogous to theinsert() operation for a standard skip list, it\nis possible to also insert new columns into the Rskip structure: once the rank is\nknown the relevant node is found again usingsAcccess() on the symbol’s own\nskip list, and the stack of nodes up to that point can have theirsRight pointers\nand sCount values updated.\nAlthough the previous paragraph satisfies the requirement ofrank() for LF\nmappingtotraverseapath,wherewestartfromanodewiththerequiredsymbol,\nfor general rank(s,i) for an arbitrary symbols we would need to find the next\nnode with that symbol, which will require a linear search on the bottom level.\nThe expected time for this isO(S) where S is the alphabet size, since if symbol\ns has frequencyfs then the expected time for this search is1/fs so the expected\ntime for a random symbol isP\ns fs1/fs = P\ns 1 = S. Although this does not\nhappen when traversing a path, it can happen when matching a new sequence,\nor inserting a new column. Fortunately this is worst case. First, entries with the\nsame symbol tend to be clustered - indeed this is what facilitates run-length\ncompression and indeed inserting into the structure by incrementing a run is\nby far the most common insertion, requiring no new nodes and just updating\ncounts not pointers. Second, symbols that occur in only one run (singletons) can\nbe special-cased and due to the skewed distribution of pangenome graph edges\nthese are frequent.\n.CC-BY 4.0 International licenseavailable under a \n(which was not certified by peer review) is the author/funder, who has granted bioRxiv a license to display the preprint in perpetuity. It is made \nThe copyright holder for this preprintthis version posted March 29, 2026. ; https://doi.org/10.64898/2026.03.26.714584doi: bioRxiv preprint \n\nRskip data structures for pangenome GBWTs 5\nIn practice, I use two variants of the canonical Rskip structure described\nabove. When building and requiring support forinsert() I add back pointers\nleft and sLeft to simplify the update code at the cost of some additional\nmemory. In particular, when doing this there is no need to maintain a special\nstart column for each symbol. For static use while searching, it is possible to\nreplace the count and sCount in the nodes in Figure 2C by partial sums up\nto that node, in a single linear sweep through the structure. Then therank()\noperation that followsaccess() during path following is a simple lookup, since\nthe partialsSum of the symbol of a node is stored within the node. Furthermore,\ngeneral rank() can be executed inO(log Rs + S) time by following thesRight\nand down pointers while looking at thesum entries then scanning left for a node\nwith the required symbol.\n3 Implementation\nThe Rskip data structure and algorithms were implemented in C filerskip.c\nwith public interface inrskip.h. These are available within the syng package\nat github.com/richarddurbin/syng, which implements pangenome construc-\ntion and, for now, basic search operations based on rskip and Edgar’s closed\nsyncmers[4].\n3.1 Rskip implementation\nTo avoid memory fragmentation and ensure cache locality the entire Rskip data\nstructure is held in a single contiguous memory block made of an array ofmax\nnodes. In static search mode I use five 32-bit integers per node of typeFixed\nto record right, sRight and down pointers as offsets into the array, andsum,\nsSum partial sums. On the bottom level we set a top bit of sSum as a flag\nand use the down slot to hold the symbol identifiersym. The first node of the\nblock is used as a header, recordingmax, the number of symbolsnSym and the\nstartingnode.Thisisfollowedby nSymnodesformingadirectoryforthesymbols,\nwhich hold external symbol information and the total count for the symbol in\nthe whole array. The nextnSym nodes following the directory are the tops of\nthe first columns for each symbol. Column height for new nodes is sampled\nfrom a geometric distribution with mean height 1.6 by iterative sampling from\na lightweight random number generator so long as the returned value is under\n3/8, which is close to the optimum1/e.\nThe dynamic Rskip variant uses eleven integers per node: six for bidirectional\npointers right, left, sRight, sLeft, down, up, four for counts before and\nafter before, count, sBefore, sCount andonefor sym.The before/sBefore\ncounts are redundant with[left].count/[sLeft].sCount but simplify code\nat the left boundary which would otherwise require additional storage. There is\nagain a header node and directory, in this case with the directory entries holding\na pointer to the top of the left-most highest column for the relevant symbol. To\n.CC-BY 4.0 International licenseavailable under a \n(which was not certified by peer review) is the author/funder, who has granted bioRxiv a license to display the preprint in perpetuity. It is made \nThe copyright holder for this preprintthis version posted March 29, 2026. ; https://doi.org/10.64898/2026.03.26.714584doi: bioRxiv preprint \n\n6 Richard Durbin\nmanage new node allocation, afreepointer is kept in the header, and array size\nis doubled when more space is required\nBecause the Rskip structures are relatively heavy, I use a much simplified\nLinearnode array for small run lists, in both static and dynamic modes. Specif-\nically these contain a maximum of 128 two-byte nodes, with nodes holding either\na one-byte symbol identifier and count, or if the count is 255 then the subsequent\nnodeholds atwo-bytecount. Theheaderis nowtwonodes,and thedirectory uses\nfour nodes per symbol. Again there is afree pointer in the header in dynamic\nmode.\nImplicit in the description above is that internal to the Rskip I use symbol\nvalues denoted sym from the range0..nSym-1. Calls to therskip package are\nmade with a general integer, or in the case ofsyng with a general (symbol,offset)\npair, and the correspondingsym is looked up/stored in the directory. Currently\nthis lookup is done with a linear search, which in principle makes the time\ncomplexity O(S) where S is the local alphabet sizenSym. It would be possible\nto use a hash table or equivalent to make this constant time, but in practice\nthe frequencies of symbols in pangenome graphs are very skewed (most genetic\nvariants are rare). As a consequence, since the directory is built progressively\nas paths are added, high frequency symbols are at or close to the start of the\ndirectory list, meaning that the expected time for linear searches is short. Actual\nexpected search times for a human pangenome are given in the results section.\n3.2 syng implementation\nSince the focus of this paper is on the Rskip data structure and algorithms, only\nbrief details of the syng implementation are given here.\nSyng pangenome graphs are bi-directional, with each vertex representing a\nsyncmer and its reverse complement. Syncmers are fixed lengthkmers with the\nproperty that one of their terminal smers has less than or equal hash value\ncomparedtoallinternal smers[4].Thisgivesthemaguaranteedwindowproperty,\nlike minimizers to which they are related[19], with consecutive syncmers in a\nsequence overlapping by at leasts bases, though unlike minimizers syncmers are\nnot context dependent: whether akmer is a syncmer is an intrinsic property of\nthe kmer sequence. Hence syncmers cover any sequence (except for its ends),\nand a list of syncmers together with offsets between them, plus terminal ends of\nlength <= k − s, are sufficient to reconstruct the sequence. For syng we require\nthat k is odd (defaultk = 63, s = 8) and use a positive syncmer index value to\nindicate traversal in the direction that lexicographically comes before its reverse\ncomplement, and minus that value for the reverse-complement direction. Syng\ninterconverts sequences and syncmer lists via a rapid scanning algorithm and a\nhash table.\nFor each vertex syng keeps a 16-byte data structure with two sides,in and\nout, together with an 8-bit set of flags. In many cases there is only one edge for\na side, termed asimple side; then the next syncmer index is stored directly in\nthe side object, together with the offset to it and the edge count. Otherwise, a\n.CC-BY 4.0 International licenseavailable under a \n(which was not certified by peer review) is the author/funder, who has granted bioRxiv a license to display the preprint in perpetuity. It is made \nThe copyright holder for this preprintthis version posted March 29, 2026. ; https://doi.org/10.64898/2026.03.26.714584doi: bioRxiv preprint \n\nRskip data structures for pangenome GBWTs 7\npointer to an Rskip is stored, which maintains the list of edges in its directory\ntogether with a BWT supporting path reconstruction.\nTo follow a path using LF-mapping with a BWT standardly requires a rank\noperation on the BWT and a sorted occurrence array. In our GBWT case only\na small subset of the large total alphabet is relevant to each step, corresponding\nto the incoming and outgoing edges for each vertex in what is overall a very\nsparse graph. The rank operation is provided byrsRank() on the Rskip BWT\nfor the out side, and we support the occurrence operation via our standard\nlinear search of the directory for the in side, as when converting converting\n(syncmer,offset) pairs to rawsyms. During building this means that we need\nseparate counts for incoming and outgoing edges for each side, but after inserting\npaths in both directions these become equal, and we only keep a single value in\nthe static representation.\n3.3 Storage in ONEcode files\nThe syng graph structure is stored in a .1gbwt ONEcode file. Drawing on\n30 years of bioinformatics experience, ONEcode provides a flexible, efficient\nframework for bioinformatics data storage, implemented with Gene Myers at\ngithub.com/thegenemyers/ONEcodeandusedforexamplebyPathPhynder[11]\nand FastGA[13]. It supports strongly-typed record-based binary files with built-\nin schemas, indices and data-specific compression (separate codec adaptively\ntrained per record type), and a simple dependency-free interface (single C source\nfile and header), thread support and standard text interconvertibility. Thegbwt\nONEcode schema support serialisation of the vertex, edge and path structure\nstored in syng vertex and Rskip structures, effectively equivalent to the infor-\nmation stored in a GFA file[1]. Although syng operates on syncmer graphs, a\n.1gbwt file can store an arbitrary bidirectional sequence graph with paths over it.\nIn parallel, syng uses a .1khash file type to store the syncmer sequences, enabling\nfast reconstruction of its syncmer data structures.\n4 Results\nI demonstrate the performance of the Rskip data structure using 92 human\ngenomes comprising the Human Pangenome Reference Consortium (HPRC) re-\nlease 1[9] minus the two HG002 genomes which will be used as test sequences for\nalignment. These contain 37,269 sequences totalling 277.4 Gbp, which generated\n234 billion instances of 193 million syncmers, with average coverage 120.8, in\n37 minutes starting from FASTA sequences. The syncmer hash table and index\ntake 10.4GB in memory, but can be stored in 4.0GB on disk as a .1khash file.\nIt took syng 52 minutes on a Linux server, single-threaded, to build a full\nbi-directional GBWT from the syncmer lists, using 15.7GB max memory. Time\nto add genomes increased from ∼22 seconds per genome to ∼40 seconds per\ngenome (Figure 3). The resulting graph contained 339.8 million simple vertex\nsides connected to only one edge, and 46.2 million with multiple edges that\n.CC-BY 4.0 International licenseavailable under a \n(which was not certified by peer review) is the author/funder, who has granted bioRxiv a license to display the preprint in perpetuity. It is made \nThe copyright holder for this preprintthis version posted March 29, 2026. ; https://doi.org/10.64898/2026.03.26.714584doi: bioRxiv preprint \n\n8 Richard Durbin\nrequired Rskip objects. Of these 46 million were stored asLinear arrays with\non average 2.4 symbols and 5.4 runs taking 2.0 GB memory, and 175 thousand\nas Dynamic arrays with on average 53.5 symbols and 410 runs taking 7.8 GB\n(9.8GB total). The total BWT length (sum of runs) was 4.2 billion forLinear\nnodesand1.1billionfor Dynamicnodes,withanaveragerunlengthof16.4across\nboth types. In total there were 229 million edges, but the incidence distribution\nhas a very long tail due to complex vertices from repetitive regions such as\ncentromeres: the vertex side with the most edges had 13,506 and the maximum\nnumber of runs for one edge was 191,212 with maximum total count 1,274,525.\nThere were 151,991 sides with more than 20 edges. The expected directory list\nsearch length was 6.3. On disk, the resulting .1gbwt file used 5.8GB.\nFig. 3.Construction time pergenome and cumulative memory used when building a\nsyng pangenome from 92 HPRCv1 genome sequences\nFor initial mapping experiments I used the Pacific Biosciences HiFi readset\nfrom individual HG002 available froms3-us-west-2.amazonaws.com/human-\npangenomics/T2T/HG002/assemblies/polishing/HG002/v1.1/mapping/\nhifi_revio_pbmay24/hg002v1.1_hifi_revio_pbmay24.bam,comprising12.8\nmillionreadstotalling205Gbp(averagelength16.0kb).Instaticmodeforsearch-\ning, the Rskip data structures takes less memory, 1.4GB forLinear and 2.6GB\nfor Fixed (4.0GB total), both because there is no free space for expansion and\nbecause Fixed Rskip nodes are smaller thanDynamic nodes. With eight threads\nit takes 14.0 seconds to load the syncmer table and 36.0 seconds to load the ver-\ntices, edges and GBWT data using 8 threads. A single forward pass search of the\n205Gbp took 468 seconds or 2.3 seconds per Gbp, coming to 8.6 minutes total\n.CC-BY 4.0 International licenseavailable under a \n(which was not certified by peer review) is the author/funder, who has granted bioRxiv a license to display the preprint in perpetuity. It is made \nThe copyright holder for this preprintthis version posted March 29, 2026. ; https://doi.org/10.64898/2026.03.26.714584doi: bioRxiv preprint \n\nRskip data structures for pangenome GBWTs 9\nfor the search including loading tables. Parallelisation performance did not scale\nwith thread number, presumably because of cache contention accessing both the\nsyncmer and GBWT tables: single-threaded times were 125.6 seconds to load\nthe graph (3.5x) and 1890 seconds to search (9.2 seconds per Gb, 4x).\nThis scan found 204 million maximal exact matches (MEMs) of average\nlength 1304bp, with only 249 reads failing to find matches. MEMs are termi-\nnated either by a syncmer not found in the pangenome reference, which may be\ncaused either by a sequencing error or a true genetic variant, or by ancestral re-\ncombination generating a new haplotype not present in any reference sequence.\nIn this case we believe the primary reason is sequencing error. We know that\nthe PacBio HiFi sequencing error rate is around 0.1%, and that most errors are\nin homopolymer run lengths. If we homopolymer compress both the references\nand the reads, resulting in a 30% length reduction, then average match length\nincreases to 4421bp compressed, equivalent to approximately 6300bp in original\nbases.\n5 Discussion\nI have presented a GBWT computational model and implementation built on\nO(logR)core operations, which operates efficiently at the scale of a hundred\nhuman genomes. Empirical time complexity growth as seen in Figure 3 depends\non many factors beyond run lengths, but is increasing relatively slowly and\napparently sublinearly, so it is reasonable to expect this implementation to scale\nto the thousand haplotype level envisioned in current pangenome projects.\nNotably,syngconstruction is much faster than the time taken by Minigraph-\nCactus[7] or PGGB[6] to construct the HPRCv1vg graphs[9]. That said, the\nsyng graphs are fundamentally different in that the Minigraph-Cactus and pggb\ngraphs are based on multiple sequence alignments that aim to identify large\nscalecolinearchromosomalhomologywithfewifanycycles,whereasthesyncmer\ngraph built bysyngcontains many cycles through repetitive sequences. Similarly\nthe GBWT described here is fundamentally different to the one implemented in\nthe vg package that supports search using giraffe[22]. The DNA sequences\nof the vertices invg graphs are not unique, and so thegiraffe GBWT must\nindex the {A,C,G,T} strings, rather than sequences of graph vertices, which\nin our case are syncmers each with their own distinct sequence so indexable\nby sequence. Our construction is much closer to a de Bruijn graph as used in\nsequence assemblers[15,8], but only using a covering set of sparsekmers as in\nMBG[17] and Verkko[18]. Indeed, the syncmer code insyng (though notrskip)\nhasalreadybeenusedinthe syncasmassemblerthatformspartoftheOraganelle\nAssembly TookKitoatk[24].\nThe MEM finding results presented above are only an initial step towards\nsequence searching. I note that the current code does not even report all MEMs,\nbut this can be fixed given that our BWT is bidirectional by iterative for-\nward/backward matching, and in any case enough matches were found to each\nread to act as seeds for more complete alignment that accepts sequencing er-\n.CC-BY 4.0 International licenseavailable under a \n(which was not certified by peer review) is the author/funder, who has granted bioRxiv a license to display the preprint in perpetuity. It is made \nThe copyright holder for this preprintthis version posted March 29, 2026. ; https://doi.org/10.64898/2026.03.26.714584doi: bioRxiv preprint \n\n10 Richard Durbin\nrors and mutations, perhaps using principles from Myers’ wave alignment algo-\nrithm[12].\nIn the long run, as indicated in the introduction, the goal is to support impu-\ntation of genome sequences from partial data such as low coverage or short read\ndata sets together with a pangenome reference panel. This will require pulling\nout the most likely pair of haplotype sequences through the graph, based on\ncoverage of read alignments together with the longer range haplotype structure\nrepresented by the paths stored in the GBWT.\nAcknowledgments.I thank Chenxi Zhou and Gene Myers for ideas and comments\nrelating to this work, and more generally many other colleagues over the years for stim-\nulating relevant discussions. This work was supported by Wellcome Discovery award\n317408/Z/24/Z and a grant on Quantum Pangenomics from Wellcome Leap’s Q4Bio\nprogram.\nDisclosure of Interests.R.D. is a scientific advisory board member of Dovetail Inc.\nwith a small financial interest in its holding company EdenRoc Inc.\nReferences\n1. Graphical fragment assembly (GFA) format specification,\nhttps://github.com/GFA-spec/GFA-spec\n2. Bao, Z., Weigel, D.: Complexity welcome: Pangenome graphs for comprehensive\npopulation genomics. Quant. Plant Biol.6(e43), e43 (27 Oct 2025)\n3. Durbin, R.: Efficient haplotype matching and storage using the positional burrows-\nwheeler transform (PBWT). Bioinformatics30(9), 1266–1272 (1 May 2014)\n4. Edgar, R.: Syncmers are more sensitive than minimizers for selecting conserved\nk-mers in biological sequences. PeerJ9, e10805 (5 Feb 2021)\n5. Gagie, T., Manzini, G., Sirén, J.: Wheeler graphs: A framework for BWT-based\ndata structures. Theor. Comput. Sci.698, 67–78 (25 Oct 2017)\n6. Garrison, E., Guarracino, A., Heumos, S., Villani, F., Bao, Z., Tattini, L., Hag-\nmann, J., Vorbrugg, S., Marco-Sola, S., Kubica, C., Ashbrook, D.G., Thorell, K.,\nRusholme-Pilcher, R.L., Liti, G., Rudbeck, E., Golicz, A.A., Nahnsen, S., Yang,\nZ., Mwaniki, M.N., Nobrega, F.L., Wu, Y., Chen, H., de Ligt, J., Sudmant, P.H.,\nHuang, S., Weigel, D., Soranzo, N., Colonna, V., Williams, R.W., Prins, P.: Build-\ning pangenome graphs. Nat. Methods pp. 1–5 (21 Oct 2024)\n7. Hickey, G., Monlong, J., Ebler, J., Novak, A.M., Eizenga, J.M., Gao, Y., Human\nPangenome Reference Consortium, Marschall, T., Li, H., Paten, B.: Pangenome\ngraph construction from genome alignments with minigraph-cactus. Nat. Biotech-\nnol. 42(4), 663–673 (Apr 2024)\n8. Li, H., Durbin, R.: Genome assembly in the telomere-to-telomere era. Nat. Rev.\nGenet. (22 Apr 2024)\n9. Liao, W.W., Asri, M., Ebler, J., others: A draft human pangenome reference. Na-\nture 617(7960), 312–324 (May 2023)\n10. Marchini, J., Howie, B.: Genotype imputation for genome-wide association studies.\nNat. Rev. Genet.11(7), 499–511 (2 Jul 2010)\n11. Martiniano, R., De Sanctis, B., Hallast, P., Durbin, R.: Placing ancient DNA se-\nquences into reference phylogenies. Mol. Biol. Evol.39(2) (3 Feb 2022)\n.CC-BY 4.0 International licenseavailable under a \n(which was not certified by peer review) is the author/funder, who has granted bioRxiv a license to display the preprint in perpetuity. It is made \nThe copyright holder for this preprintthis version posted March 29, 2026. ; https://doi.org/10.64898/2026.03.26.714584doi: bioRxiv preprint \n\nRskip data structures for pangenome GBWTs 11\n12. Myers, E.W.: AnO(ND) difference algorithm and its variations. Algorithmica1(1),\n251–266 (1 Nov 1986)\n13. Myers, G., Durbin, R., Zhou, C.: FastGA: fast genome alignment. Bioinform. Adv.\n5(1), vbaf238 (6 Oct 2025)\n14. Navarro, G.: Compact Data Structures: A Practical Approach. Cambridge Univer-\nsity Press, Cambridge, England (5 Sep 2016)\n15. Pevzner, P.A., Tang, H., Waterman, M.S.: An eulerian path approach to DNA\nfragment assembly. Proc. Natl. Acad. Sci. U. S. A.98(17), 9748–9753 (14 Aug\n2001)\n16. Pugh, W.: Skip lists: a probabilistic alternative to balanced trees. Commun. ACM\n33(6), 668–676 (1 Jun 1990)\n17. Rautiainen, M., Marschall, T.: MBG: Minimizer-based sparse de bruijn graph con-\nstruction. Bioinformatics37(16), 2476–2478 (15 Aug 2021)\n18. Rautiainen, M., Nurk, S., Walenz, B.P., Logsdon, G.A., Porubsky, D., Rhie, A.,\nEichler, E.E., Phillippy, A.M., Koren, S.: Telomere-to-telomere assembly of diploid\nchromosomes with verkko. Nat. Biotechnol. (16 Feb 2023)\n19. Roberts, M., Hayes, W., Hunt, B.R., Mount, S.M., Yorke, J.A.: Reducing storage\nrequirements for biological sequence comparison. Bioinformatics20(18), 3363–3369\n(12 Dec 2004)\n20. Rubinacci, S., Delaneau, O., Marchini, J.: Genotype imputation using the posi-\ntional burrows wheeler transform. PLoS Genet.16(11), e1009049 (16 Nov 2020)\n21. Sirén, J., Garrison, E., Novak, A.M., Paten, B., Durbin, R.: Haplotype-aware graph\nindexes. Bioinformatics36(2), 400–407 (15 Jan 2020)\n22. Sirén, J., Monlong, J., Chang, X., Novak, A.M., Eizenga, J.M., Markello, C., Sibbe-\nsen, J.A., Hickey, G., Chang, P.C., Carroll, A., Gupta, N., Gabriel, S., Blackwell,\nT.W., Ratan, A., Taylor, K.D., Rich, S.S., Rotter, J.I., Haussler, D., Garrison, E.,\nPaten, B.: Pangenomics enables genotyping of known structural variants in 5202\ndiverse genomes. Science374(6574), abg8871 (17 Dec 2021)\n23. Taylor, D.J., Eizenga, J.M., Li, Q., Das, A., Jenike, K.M., Kenny, E.E., Miga, K.H.,\nMonlong, J., McCoy, R.C., Paten, B., Schatz, M.C.: Beyond the human genome\nproject: The age of complete human genome sequences and pangenome references.\nAnnu. Rev. Genomics Hum. Genet.25(1), 77–104 (27 Aug 2024)\n24. Zhou, C., Brown, M., Blaxter, M., Darwin Tree of Life Project Consortium, Mc-\nCarthy, S.A., Durbin, R.: Oatk: a de novo assembly tool for complex plant organelle\ngenomes. Genome Biol.26(1), 235 (7 Aug 2025)\n.CC-BY 4.0 International licenseavailable under a \n(which was not certified by peer review) is the author/funder, who has granted bioRxiv a license to display the preprint in perpetuity. It is made \nThe copyright holder for this preprintthis version posted March 29, 2026. ; https://doi.org/10.64898/2026.03.26.714584doi: bioRxiv preprint","source_license":"CC-BY-4.0","license_restricted":false}