{
  "abstract": "Skiplists 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 Burrows-Wheeler transforms that supports O(logR) rank and access operations, as well as a dynamic version 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, 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.",
  "abstract_shown": true,
  "affiliations": [
    "Department of Genetics, University of Cambridge, Cambridge, United Kingdom.",
    "Wellcome Sanger Institute, Cambridge, United Kingdom."
  ],
  "article_type": "research article",
  "arxiv": null,
  "author_total": 1,
  "authors": [
    {
      "affs": [
        0,
        1
      ],
      "name": "Richard Durbin",
      "orcid": "0000-0002-9130-1006"
    }
  ],
  "bibtex": "https://research.draconitic.com/paper/75t4hjhpxd19s.bib",
  "cited_by": 0,
  "doi": "10.1177/15578666261495122",
  "fulltext_url": "https://europepmc.org/articles/PMC7619509",
  "id": "75t4hjhpxd19s",
  "issns": [
    "1066-5277",
    "1557-8666"
  ],
  "landing_url": "https://europepmc.org/article/MED/42878135",
  "language": "eng",
  "licence": "CC-BY",
  "licence_label": "CC BY",
  "licence_source": "article",
  "licence_url": "https://creativecommons.org/licenses/by/4.0/",
  "metadata_licence": null,
  "native_subjects": [
    [
      "openalex",
      "1702|Algorithms and Data Compression"
    ]
  ],
  "openalex": "W7221964331",
  "pdf_url": "https://europepmc.org/articles/PMC7619509?pdf=render",
  "pmcid": "PMC7619509",
  "pmid": "42878135",
  "published": "2026-10-15",
  "publisher": null,
  "ris": "https://research.draconitic.com/paper/75t4hjhpxd19s.ris",
  "sources": [
    {
      "first_seen": "2026-10-30T12:18:46Z",
      "native_id": "MED:42878135",
      "source": "europepmc",
      "url": "https://europepmc.org/article/MED/42878135"
    }
  ],
  "subjects": [
    {
      "field": "biochemistry",
      "origin": "journal-openalex:1312|Genomics and Phylogenetic Studies",
      "subfield": "molecular-biology"
    }
  ],
  "title": "A Run-Length-Compressed Skiplist Data Structure for Dynamic GBWTs Supports Time- and Space-Efficient Pangenome Operations over Syncmers.",
  "title_text": "A Run-Length-Compressed Skiplist Data Structure for Dynamic GBWTs Supports Time- and Space-Efficient Pangenome Operations over Syncmers.",
  "type": "peer-reviewed",
  "updated_at": "2026-10-30T12:18:46Z",
  "url": "https://research.draconitic.com/paper/75t4hjhpxd19s",
  "venue": "Journal of computational biology : a journal of computational molecular cell biology",
  "versions": []
}