Pith. sign in

REVIEW 2 major objections 6 minor 52 references

LCPan: efficient variation graph construction using Locally Consistent Parsing

T0 review · 2 major / 6 minor · reviewed 2026-08-03 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Using a string-parsing scheme from 30 years ago, with a single deterministic coin-tossing round, the paper claims pangenome variation graphs can be built more than ten times faster and with over thirteen times less memory than current leadi

desk verdict Strong engineering results with a real speedup, but the unquantified single-round-DCT gaps leave graph completeness unverified; worth peer review with specific requests for quantification and a corrected accuracy claim. read the letter →

arxiv 2511.12205 v4 pith:VSEFM5W5 submitted 2025-11-15 q-bio.GN

Akmuhammet Ashyralyyev , Zülal Bingöl , Begüm Filiz Öz , Kaiyuan Zhu , Salem Malikic , Uzi Vishkin , S. Cenk Sahinalp , Can Alkan This is my paper · ORCID
classification q-bio.GN MSC 68W3292D20
keywords locallyconsistentparsingvariationgraphpangenomedeterministiccointossingstringpartitioninggenomerepresentationsketchingconstruction
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper's central claim is that Locally Consistent Parsing — a scheme that splits a genome into short, exactly reproducible substrings called cores — can be run iteratively on real DNA and that this makes variation graph construction much cheaper. The authors present the first iterative implementation, show that each LCP level shrinks the number of cores by a consistent factor of about 0.43 (so the i-th level has O(n/c^i) cores with c about 2.34), and use the cores as fixed-size nodes of a variation graph. On a complete human reference with a large variant set, their builder runs in about eight minutes and roughly 8.6 GB, while the standard tool needed about 83 minutes and 114 GB, with comparable read-alignment accuracy on long-read data. If these numbers hold, pangenome graph construction stops being a big-server-only job and becomes a workstation-scale operation.

What carries the argument

Deterministic Coin Tossing is the load-bearing device. DCT maps each core's bitstream to a code made of the binary representation of the first position (from the right) where the stream differs from its left neighbor plus the value of the differing bit. This keeps the symbol alphabet small so the original LCP rules (local minimum, local maximum, repetitive interior, stranded sequence) can be applied to the higher-level 'string of cores,' preserving the contiguity and adjacency lemmas that bound the number of cores and guarantee no gaps. A single DCT round is used as a deliberate tradeoff: extra rounds would force more overlap between cores and reduce sparsity, at a cost the authors judge unn

What would settle it

A concrete test: at LCP levels 4-7, count the fraction of reference bases not contained in any core on several diverse genomes (plant, fungal, bacterial, and a repeat-rich human chromosome), and intersect those uncovered bases with known variant coordinates; if the uncovered fraction is non-negligible or systematically overlaps variants, the empirical completeness claim is falsified.

Watch

Extended reading notes

Core claim

The discovery is that a classic symmetry-breaking trick, Deterministic Coin Tossing (DCT), lets LCP be reapplied level after level without losing the spacing guarantees that make it useful. Each level-i core's bitstream is replaced by a short code recording the first bit position (counted from the right) where it differs from its left neighbor, plus that differing bit; the resulting reduced alphabet is parsed again by the same four local rules (local minimum, local maximum, repetitive interior, stranded sequence). Empirically the reduction is stable on whole human chromosomes: the core count falls by a factor of about 0.43 per level, average core length and spacing grow by about 2.34 per lev

Load-bearing premise

One round of Deterministic Coin Tossing keeps LCP's no-gap guarantee in practice: the few short uncovered 'stranded regions' are assumed to be too rare and too variant-free to affect graph completeness or accuracy.

Editorial extensions

If this is right

  • A whole human genome can be represented at LCP level 8 by about 3.6 million cores, so the memory and storage cost of a pangenome representation shrinks geometrically with level.
  • Human variation graphs built with LCP cores came out 10 to 13 times faster and with 13 times less peak memory than the standard tool, with alignment accuracy (precision, recall, F1) on long reads statistically the same.
  • Raising the LCP level from 4 to 7 cuts the number of graph segments from about 408 million to 67 million and links from about 423 million to 82 million on the human variant set, letting users trade granularity for size.
  • LCP cores are fewer and more uniformly spaced than minimizers, syncmers, UHS, or MinHash at comparable scale; for example, level-2 cores are fewer than minimizers or syncmers with similar average lengths, and spacing has lower relative deviation.
  • The same core partition is computed in one pass for all levels, so a user can choose the level after the fact without rerunning the parsing.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Extension: if the 0.43 reduction factor is stable across species, core counts and memory needs can be predicted from input length alone, letting downstream tools size themselves before running.
  • Extension: because cores are longer and more evenly spaced than minimizers, they may serve as sequence-anchoring features for long-read chaining or overlap detection, which the paper does not test.
  • Extension: the single-round DCT choice is the fragile assumption; a natural stress test is to count uncovered bases at every level on several diverse genomes and intersect them with variant coordinates, since the paper only reports that uncovered 'stranded regions' are 'highly infrequent' on human data.
  • Extension: the same API can run on non-DNA alphabets, so the graph-construction scheme could be adapted to protein sequences or other strings, something the paper notes but does not pursue.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 6 minor

Summary. The paper introduces Lcptools, the first iterative implementation of Locally Consistent Parsing (LCP) with Deterministic Coin Tossing (DCT), and LCPan, a variation graph constructor that partitions a reference genome into LCP cores and inserts VCF variants into the resulting backbone graph. On CHM13v2.0 the authors report that the number of cores decreases by a factor of ~0.43 per LCP level and that average core length and inter-core distance increase by a factor converging to ~2.34. On the HPRC human pangenome data with GRCh38, LCPan is reported to construct variation graphs >10x faster and with >13x less peak memory than vg, while GraphAligner-based read mapping on the resulting graphs gives broadly similar precision/recall/F1 values. The paper also reports a smaller yeast pangenome comparison and a multi-thread scaling analysis.

Significance. If the completeness caveat is resolved, this is a useful contribution: it provides an open-source implementation of iterative LCP, demonstrates its scaling behavior on a whole human genome, and shows a substantial practical speed/memory improvement for VCF-based variation graph construction relative to vg. The code is publicly available under a permissive license, and the benchmarks on CHM13, HPRC, and yeast are concrete and reproducible in principle. The core-number reduction measurements are empirical rather than a proof of an O(n/c^i) bound, but the authors mostly frame them as experimental observations. The main unresolved issue is whether the graphs produced by LCPan are complete representations of the reference and variant set, given the admitted single-round-DCT coverage gaps.

major comments (2)
  1. [§4.1, Lemma 1, §4.4, Table 3] The paper's central speed/memory claim depends on LCPan constructing a variation graph that contains the full reference and all VCF variants. However, the contiguity lemma is proved only for the base LCP alphabet before DCT, and §4.1 explicitly states that a single round of DCT 'can create a short stranded region not covered by any core substring.' The text asserts these regions are rare and do not measurably affect the distribution, but no quantification is provided: there is no count of uncovered reference bases, no analysis of whether uncovered regions overlap VCF variant spans, and Table 3 reports no coverage or variant-insertion statistics. If an uncovered internal region contains a variant, that variant cannot be placed in the graph, making the benchmark non-comparable to vg. Please measure the fraction of reference bases covered by LCPan segments at each reported level, count vari
  2. [Supplementary Lemma 1 proof] The proof of the Contiguity Property is a case-based sketch rather than a rigorous coverage proof. For each typed core it lists possible successors, but it does not systematically exclude the possibility of a position that is not covered by any core, especially after the reduced-alphabet DCT transformation used for levels above 1. Since LCPan's backbone is built from level-4 to level-7 cores, the relevant guarantee is for the iterative levels, not just the base level. Please provide a proof or a precise statement of the coverage property that applies to the DCT-reduced construction, or state clearly that the guarantee is not proved for iterative levels.
minor comments (6)
  1. [§2.2, Table 3] The vg execution time of 4958 s is the sum of construction and merge times, but excludes the additional ~11 min and 91 GB needed to convert the vg output to GFA. LCPan's reported time appears to include GFA output generation. Please report both vg numbers (with and without GFA conversion) so the comparison is exactly apples-to-apples; the text should clarify how the >10x and >13x ratios are computed.
  2. [Abstract, §2.4, Table 5] The abstract claims 'slightly better alignment accuracy using GraphAligner on HiFi data,' but Table 5 shows F1 scores that are equal or slightly lower for LCPan, and recall is lower for LCPan in all HiFi comparisons (0.70 vs 0.72 on chr1/10/22 and 0.53 vs 0.72 on the full genome), with mixed precision. The §2.4 text correctly concludes that accuracy is 'consistent'; the abstract should be revised to 'comparable' rather than 'slightly better.'
  3. [Table 1] The row labeled 'Decrease in Core Count' shows 0.44 for level 2 and 0.43 for later levels, while the text says the reduction factor is consistently 0.43. Please reconcile. Also, 'Total Size (GB)' is never defined; please state whether it is the memory needed to store all core labels, bitstreams, or something else.
  4. [§4.1, Figure 3] The DCT code is described as the concatenation of the binary representation of the differing position t and the differing bit, giving length ⌈log k⌉+1. It is not specified how these variable-length binary codes are ordered when the LCP rules are applied to the reduced alphabet. Please define the total order on reduced symbols and explain how boundary effects affect the 'same block yields the same reduced representation' claim.
  5. [Figure 1] The multi-thread scaling figure uses two y-axes (RAM and execution time) with a shared x-axis labeled '1 2 4 8 16'. The legend labels 'VG- GNU R AM' and 'VG- GNU Time' are hard to parse and the axis units/colors should be clarified. The text should also state how many runs each point is based on and whether error bars are omitted.
  6. [§2.1, Table 2] Minor wording issues: 'with 58 million unique users' should be 'unique k-mers'; 'r/GF A' in Table 3 should be 'rGFA/GFA'; and the 'UHS' row reports 983.5M total k-mers in the genome, which is higher than the other methods—this is explained only in prose, not in the table, so a footnote would help.

Circularity Check

0 steps flagged · score 0.0 of 10

No material circularity: the LCP reduction factor is a measured constant, the LCP lemmas are proved in the supplement, and the vg comparison is an external benchmark.

full rationale

The derivation chain does not reduce to its inputs by construction. Section 2.1 reports the core-count reduction factor 0.43 (c≈2.34) as an experimentally measured property of CHM13v2.0, explicitly saying the observation "empirically supports the theoretical analysis that 2≤c≤3" from [22]; it is not a fitted parameter that is later renamed as a prediction. The equality between the decrease in core count and the increase in average length/distance follows arithmetically from the fact that cores tile the input, but the paper reports both as measurements and does not derive one from the other as a novel result. The LCP contiguity and adjacency properties, while credited to [21,22], are re-proved in the Supplementary Material (Lemmas 1 and 2), so the self-citation is not load-bearing in a way that forces the conclusions. The main performance claims are benchmarked against an external tool (vg) using HPRC and yeast data, and the timing/memory comparisons are independent of LCP theory. Section 4.1's admission that a single round of DCT can create rare stranded regions is a completeness limitation and an empirical risk, but it is an acknowledged assumption rather than a circular step: the paper does not define LCPan's correctness in terms of the claimed speedup. No prediction in the paper is equivalent to its own input by construction.

Assumptions & free parameters 2 free parameters · 3 assumptions · 0 invented entities

The central performance claims rest on the empirical behavior of iterative LCP; the theoretical guarantees are inherited from the original LCP papers and are assumed to persist under the single-round DCT approximation.

free parameters (2)
  • LCP reduction factor c = ≈2.34
    Observed ratio of core counts/average distances between successive LCP levels on CHM13 (Table 1); used in the O(n/c^i) complexity statement. It is an empirical constant, not a theoretical bound.
  • Number of DCT rounds = 1
    Chosen by hand as a pragmatic tradeoff (Section 4.1); additional rounds are said to increase overlap and reduce sparsity. This choice weakens the theoretical contiguity guarantee.
assumptions (3)
  • standard math LCP at the base level satisfies Contiguity and Adjacency properties (Lemmas 1-2)
    Inherited from Sahinalp & Vishkin (1994); proofs in the supplementary are sketches for a simplified rule set.
  • domain assumption Applying DCT to the core-bitstream sequence preserves enough local consistency for iterative LCP to behave like the base level
    Section 4.1 asserts the reduced alphabet 'continues to satisfy the contiguity/adjacency-style constraints needed for iterative LCP' without formal proof; empirical evidence is limited to one human genome.
  • domain assumption MurmurHash labels do not collide in a way that affects core identity
    Section 4.2 uses MurmurHash as ψ; no collision analysis is provided.

how reviews work

0 comments
Cite this review

Pith. "Pith review of LCPan: efficient variation graph construction using Locally Consistent Parsing." pith.science (2026). https://pith.science/paper/VSEFM5W5

@misc{pith2026251112205,
  author       = {Pith},
  title        = {Pith review of: LCPan: efficient variation graph construction using Locally Consistent Parsing},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VSEFM5W5}},
  note         = {Machine review of arXiv:2511.12205}
}
read the original abstract

Efficient and consistent string processing is critical in the exponentially growing genomic data era. Locally Consistent Parsing (LCP) addresses this need by partitioning an input genome string into short, exactly matching substrings (e.g., "cores"), ensuring consistency across partitions. Labeling the cores of an input string consistently not only provides a compact representation of the input but also enables the reapplication of LCP to refine the cores over multiple iterations, providing a progressively longer and more informative set of substrings for downstream analyses. We present the first iterative implementation of LCP with Lcptools and demonstrate its effectiveness in identifying cores with minimal collisions. Experimental results show that the number of cores at the i^th iteration is O(n/c^i) for c ~ 2.34, while the average length and the average distance between consecutive cores are O(c^i). Compared to the popular sketching techniques, LCP produces significantly fewer cores, enabling a more compact representation and faster analyses. To demonstrate the advantages of LCP in genomic string processing in terms of computation and memory efficiency, we also introduce LCPan, an efficient variation graph constructor. We show that LCPan generates variation graphs >10x faster than vg, while using >13x less memory.

Figures

Figures reproduced from arXiv: 2511.12205 by the authors.

Figure 1
Figure 1. Multi-thread scaling analysis of LCPan and vg using HPRC data on GRCh38. Memory and run time of graph construction using different numbers of threads. LCPan and vg were run using their native multithreading implementations. vg was additionally parallelized using GNU Parallel by distributing single-threaded processes on chunks across concurrent jobs (VG-GNU). provided by LCP enables LCPan to efficiently scale computa… view at source ↗
Figure 2
Figure 2. depicts an example of the cores identified in a short DNA sequence. As the cores are identified, the two-bit encoding of the underlying characters (i.e., A = 00, C = 01, G = 10, T = 11) is used to form the core’s bitstream. Note that we use the term core alphabet to refer to the bitstreams that form the cores, specifically the DNA encoding used in the first LCP iteration. T C C G A C G T A G T G C T 11 01 01 10 00 0… view at source ↗
Figure 3
Figure 3. DCT for reducing bitstreams to a new alphabet. [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: Overview of the LCP with DCT and Labeling Paradigm. [PITH_FULL_IMAGE:figures/full_fig_p012_4.png]
Figure 5
Figure 5. Figure 5: Overview of the LCPan Method. 4.3 String Processing with Lcptools We have developed Lcptools as a C-based application programming interface (API) that imple￾ments the LCP method, which iteratively processes input strings and generates cores at multiple 13 [PITH_FULL_I…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

52 extracted references · 2 linked inside Pith

  1. [1]

    M.et al.Building and improving reference genome assemblies.Proceedings of the IEEE105, 422–435 (2017)

    Steinberg, K. M.et al.Building and improving reference genome assemblies.Proceedings of the IEEE105, 422–435 (2017)

    2017

  2. [2]

    Computational pan-genomics: status, promises and challenges.Brief- ings in Bioinformatics19, 118–135 (2018)

    Computational Pan-Genomics Consortium. Computational pan-genomics: status, promises and challenges.Brief- ings in Bioinformatics19, 118–135 (2018)

    2018

  3. [3]

    & Telford, M

    Kapli, P., Yang, Z. & Telford, M. J. Phylogenetic tree building in the genomic age.Nature reviews. Genetics21, 428–444 (2020)

    2020

  4. [4]

    & Bhatt, A

    Pinto, Y. & Bhatt, A. S. Sequencing-based analysis of microbiomes.Nature reviews. Genetics(2024)

    2024

  5. [5]

    D.et al.Mash: fast genome and metagenome distance estimation using MinHash.Genome Biology 17, 132 (2016)

    Ondov, B. D.et al.Mash: fast genome and metagenome distance estimation using MinHash.Genome Biology 17, 132 (2016)

    2016

  6. [6]

    Aligning sequence reads, clone sequences and assembly contigs with BW A-MEM.arXiv preprint arXiv:1303.3997(2013)

    Li, H. Aligning sequence reads, clone sequences and assembly contigs with BW A-MEM.arXiv preprint arXiv:1303.3997(2013)

    arXiv 2013

  7. [7]

    & Kidd, J

    Shen, F. & Kidd, J. M. Rapid, paralog-sensitive CNV analysis of 2457 human genomes using QuicK-mer2.Genes 11(2020)

    2020

  8. [8]

    & Kingsford, C

    Solomon, B. & Kingsford, C. Fast search of thousands of short-read sequencing experiments.Nature biotechnology 34, 300–302 (2016)

    2016

Show all 52 references
  1. [9]

    & Wheeler, D

    Burrows, M. & Wheeler, D. J. A block sorting lossless data compression algorithm. Tech. Rep., Digital Equipment Corporation (1994)

    1994

  2. [10]

    & Manzini, G

    Ferragina, P. & Manzini, G. Opportunistic data structures with applications. InFoundations of Computer Science, 2000. Proceedings. 41st Annual Symposium on, 390–398 (2000). URLhttp://ieeexplore.ieee.org/ stamp/stamp.jsp?arnumber=892127

    2000

  3. [11]

    Bloom, B. H. Space/time trade-offs in hash coding with allowable errors.Communications of the ACM13, 422–426 (1970)

    1970

  4. [12]

    Marchet, C.et al.Data structures based on k-mers for querying large collections of sequencing data sets.Genome Research31, 1–12 (2021)

    2021

  5. [13]

    R., Mount, S

    Roberts, M., Hayes, W., Hunt, B. R., Mount, S. M. & Yorke, J. A. Reducing storage requirements for biological sequence comparison.Bioinformatics20, 3363–3369 (2004)

    2004

  6. [14]

    & Mar¸ cais, G

    DeBlasio, D., Gbosibo, F., Kingsford, C. & Mar¸ cais, G. Practical universal k-mer sets for minimizer schemes. InProceedings of the 10th ACM International Conference on Bioinformatics, Computational Biology and Health Informatics, BCB ’19, 167–176 (Association for Computing Ma...

    2019

  7. [15]

    & Chikhi, R

    Ekim, B., Berger, B. & Chikhi, R. Minimizer-space de Bruijn graphs: Whole-genome assembly of long reads in minutes on a personal computer.Cell systems12, 958–968.e6 (2021)

    2021

  8. [16]

    Minimap2: pairwise alignment for nucleotide sequences.Bioinformatics34, 3094–3100 (2018)

    Li, H. Minimap2: pairwise alignment for nucleotide sequences.Bioinformatics34, 3094–3100 (2018)

    2018

  9. [17]

    & Kingsford, C

    Orenstein, Y., Pellow, D., Mar¸ cais, G., Shamir, R. & Kingsford, C. Compact universal k-mer hitting sets. In Frith, M. C. & Pedersen, C. N. S. (eds.)Algorithms in Bioinformatics - 16th International Workshop, WABI 2016, Aarhus, Denmark, August 22-24, 2016. Proceedings, vol. 9...

    2016

  10. [18]

    & Orenstein, Y

    Ekim, B., Berger, B. & Orenstein, Y. A randomized parallel algorithm for efficiently finding near-optimal universal hitting sets. In Schwartz, R. (ed.)Proceedings of the 24th Annual International Conference on Research in Computational Molecular Biology (RECOMB) 2020, vol. 120...

    2020

  11. [19]

    Effective sequence similarity detection with strobemers.Genome research31, 2080–2094 (2021)

    Sahlin, K. Effective sequence similarity detection with strobemers.Genome research31, 2080–2094 (2021)

  12. [20]

    Syncmers are more sensitive than minimizers for selecting conserved k -mers in biological sequences

    Edgar, R. Syncmers are more sensitive than minimizers for selecting conserved k -mers in biological sequences. PeerJ9, e10805 (2021)

    2021

  13. [21]

    Sahinalp, S. C. & Vishkin, U. On a parallel-algorithms method for string matching problems. In Bonuccelli, M. A., Crescenzi, P. & Petreschi, R. (eds.)Algorithms and Complexity, Second Italian Conference, CIAC ’94, Rome, Italy, February 23-25, 1994, Proceedings, vol. 778 ofLect...

    1994

  14. [22]

    Sahinalp, S. C. & Vishkin, U. Symmetry breaking for suffix tree construction. In Leighton, F. T. & Goodrich, M. T. (eds.)Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 23-25 May 1994, Montr´ eal, Qu´ ebec, Canada, 300–309 (ACM, 1994)

    1994

  15. [23]

    & Vishkin, U

    Cole, R. & Vishkin, U. Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms. In Hartmanis, J. (ed.)Proceedings of the 18th Annual ACM Symposium on Theory of Computing, May 28-30, 1986, Berkeley, California, USA, 206...

    1986

  16. [24]

    Sahinalp, S. C. & Vishkin, U. Efficient approximate and dynamic matching of patterns using a labeling paradigm. In37th Annual Symposium on Foundations of Computer Science, FOCS ’96, Burlington, Vermont, USA, 14-16 October, 1996, 320–328 (IEEE Computer Society, 1996)

    1996

  17. [25]

    & Sahinalp, C

    Batu, T., Ergun, F. & Sahinalp, C. Oblivious string embeddings and edit distance approximations. InProceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm, SODA ’06, 792–801 (Philadelphia, PA, USA, 2006). URLhttp://dl.acm.org/citation.cfm?id=1109557.1109644

    2006

  18. [26]

    & Sahinalp, S

    Hach, F., Numanagic, I., Alkan, C. & Sahinalp, S. C. SCALCE: boosting sequence compression algorithms using locally consistent encoding.Bioinformatics28, 3051–3057 (2012)

    2012

  19. [27]

    Efficient terabyte-scale text compression via stable local consistency and parallel grammar processing.arXiv preprint arXiv:2411.12439(2024)

    Diaz-Dominguez, D. Efficient terabyte-scale text compression via stable local consistency and parallel grammar processing.arXiv preprint arXiv:2411.12439(2024)

    2024 arXiv

  20. [28]

    & Sahinalp, S

    Batu, T. & Sahinalp, S. C. Locally consistent parsing and applications to approximate string comparisons. In Proceedings of DLT 2005, 22–35 (Springer, Palermo, Italy, 2005)

    2005

  21. [29]

    & Porat, E

    Birenzwige, O., Golan, S. & Porat, E. Locally consistent parsing for text indexing in small space. InProceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’20, 607–626 (Society for Industrial and Applied Mathematics, USA, 2020). URLhttps://dl.a...

    2020

  22. [30]

    & Pacheco, A

    D ´ ıaz-Dom ´ ınguez, D., Navarro, G. & Pacheco, A. An lms-based grammar self-index with local consistency prop- erties. InInternational Symposium on String Processing and Information Retrieval, 100–113 (Springer, 2021)

    2021

  23. [31]

    & Marschall, T

    Rautiainen, M. & Marschall, T. GraphAligner: rapid and versatile sequence-to-graph alignment.Genome biology 21, 253 (2020)

    2020

  24. [32]

    Garrison, E.et al.Building pangenome graphs.Nature Methods21, 2008–2012 (2024)

    2008

  25. [33]

    Hickey, G.et al.Pangenome graph construction from genome alignments with Minigraph-Cactus.Nature biotech- nology(2023)

    2023

  26. [34]

    Nurk, S.et al.The complete sequence of a human genome.Science376, 44–53 (2022)

    2022

  27. [35]

    & Limasset, A

    Ingels, F., Robidou, L., Martayan, I., Marchet, C. & Limasset, A. Minimizer density revisited: Models and multiminimizers.bioRxiv(2025). URLhttps://www.biorxiv.org/content/early/2025/11/21/2025.11.21. 689688.https://www.biorxiv.org/content/early/2025/11/21/2025.11.21.689688.full.pdf

    2025

  28. [36]

    Liao, W.-W.et al.A draft human pangenome reference.Nature617, 312–324 (2023)

    2023

  29. [37]

    K.et al.The 100-genomes strains, anS

    Strope, P. K.et al.The 100-genomes strains, anS. cerevisiaeresource that illuminates its natural phenotypic and genotypic variation and emergence as an opportunistic pathogen.Genome research25, 762–774 (2015)

    2015

  30. [38]

    & Kingsford, C

    Pandey, P., Gao, Y. & Kingsford, C. VariantStore: an index for large-scale genomic variant search.Genome biology22, 231 (2021)

    2021

  31. [39]

    GNU Parallel - the command-line power tool.;login: The USENIX Magazine36, 42–47 (2011)

    Tange, O. GNU Parallel - the command-line power tool.;login: The USENIX Magazine36, 42–47 (2011). URL http://www.gnu.org/s/parallel

    2011

  32. [40]

    F.et al.A complete diploid human genome benchmark for personalized genomics.bioRxiv(2025)

    Hansen, N. F.et al.A complete diploid human genome benchmark for personalized genomics.bioRxiv(2025)

    2025

  33. [41]

    & Tomescu, A

    Ma, J., C´ aceres, M., Salmela, L., M¨ akinen, V. & Tomescu, A. I. Chaining for accurate alignment of erroneous long reads to acyclic variation graphs.Bioinformatics39(2023)

    2023

  34. [42]

    M.et al.A robust benchmark for detection of germline large deletions and insertions.Nature Biotech- nology38, 1347–1355 (2020)

    Zook, J. M.et al.A robust benchmark for detection of germline large deletions and insertions.Nature Biotech- nology38, 1347–1355 (2020)

    2020

  35. [43]

    pbsv: PacBio structural variant SV calling and analysis tools (2025)

    Pacific Biosciences. pbsv: PacBio structural variant SV calling and analysis tools (2025). URLhttps://github. com/PacificBiosciences/pbsv. Accessed 1 July 2025

    2025

  36. [44]

    Murmurhash (2008)

    Appleby, A. Murmurhash (2008). URLhttps://github.com/aappleby/smhasher. Ethics declarations Ethics approval and consent to participate Not applicable. Consent for publication Not applicable. Competing interests No competing interest is declared. 16 Author contributions stateme...

    2008

  37. [45]

    Ifxyzis an LMIN core, then the substringzlmorlmnmay satisfy the LMAX rule (y < z < l andl > m≥n; ory < z < l < mandm > n), assumingnis not the middle character of another LMIN core. On the other hand, if the lexicographic order of subsequent characters increases (i.e.,y < z < ...

  38. [46]

    Ifxyzis an LMAX core, then the substringzlmorlmnmay satisfy the LMIN rule (y > z > l andl < m; ory > z > l > mandm < n). Alternatively, if the lexicographic order of subsequent characters decreases (i.e.,y > z > l > m > n), the SSEQ rule will apply after LMAX until the downstr...

  39. [47]

    The RINT substringxyzcan also be followed by an LMAX core wherezlmorlmnmay satisfy the LMAX rule (y < z < l andl > m; ory < z < l < mandm > n)

    Ifx yzis a RINT core (i.e.,x yz=xy iz, i >1), then the substringzlmorlmnmay satisfy the LMIN rule (y > z > landl < m;y > z > l > mandm < n). The RINT substringxyzcan also be followed by an LMAX core wherezlmorlmnmay satisfy the LMAX rule (y < z < l andl > m; ory < z < l < mand...

  40. [48]

    ⊓ ⊔ We showed in Lemma 1 that a string can be fully represented without gaps using cores

    By definition, an SSEQ core shares characters with its neighbor, concluding the correctness of the Contiguity Property. ⊓ ⊔ We showed in Lemma 1 that a string can be fully represented without gaps using cores. Below, we show that there is an upper bound on the number of potent...

  41. [49]

    By definition, no local minimum can exist adjacent to an LMAX core

    Ifxyzis an LMIN core, thenzlmorlmnmay be an LMAX core (i.e.,z̸=landl̸=m). By definition, no local minimum can exist adjacent to an LMAX core. Hence, they do not overlap for more than one character (i.e., an LMAX core cannot start withy). On the other hand, the closest RINT cor...

  42. [50]

    The closest RINT core could start atyifz=l, but in that case, no other core may start atzfor the same reason outlined above

    Ifxyzis an LMAX core, the closest LMIN core may only start atz. The closest RINT core could start atyifz=l, but in that case, no other core may start atzfor the same reason outlined above. Again, the same reasoning applies to the next SSEQ core that follows an LMAX core

  43. [51]

    For example, ifw=xyyznm, thenxyyzis a RINT core, and the next LMIN, LMAX, or SSEQ core may start atyzn

    Ifxy izis a RINT core (i >1), the closest possible cores may start aftericharacters. For example, ifw=xyyznm, thenxyyzis a RINT core, and the next LMIN, LMAX, or SSEQ core may start atyzn

  44. [52]

    Ifxyzis an SSEQ core, the closest possible core may start after the third character (i.e., it may bezlm). I

Pith tools

Reviewed August 3, 2026 · model on record in the stance chip above.