CoChat
Sign Up
Cited by 95

The DOI matches its Crossref record; 3 of the 3 references it cites were found in a registry or an index.

Unbiased pangenome graphs

Garrison, Erik, Guarracino, Andrea·2023·Bioinformatics
DOI 10.1093/bioinformatics/btac743PMC PMC9805579

Published version of a preprint

Open this paper in CoChat — free account

Abstract

Motivation: Pangenome variation graphs model the mutual alignment of collections of DNA sequences. A set of pairwise alignments implies a variation graph, but there are no scalable methods to generate such a graph from these alignments. Existing related approaches depend on a single reference, a specific ordering of genomes or a de Bruijn model based on a fixed k-mer length. A scalable, self-contained method to build pangenome graphs without such limitations would be a key step in pangenome construction and manipulation pipelines. Results: We design the seqwish algorithm, which builds a variation graph from a set of sequences and alignments between them. We first transform the alignment set into an implicit interval tree. To build up the variation graph, we query this tree-based representation of the alignments to reduce transitive matches into single DNA segments in a sequence graph. By recording the mapping from input sequence to output graph, we can trace the original paths through this graph, yielding a pangenome variation graph. We present an implementation that operates in external memory, using disk-backed data structures and lock-free parallel methods to drive the core graph induction step. We demonstrate that our method scales to very large graph induction problems by applying it to build pangenome graphs for several species. Availability and implementation: seqwish is published as free software under the MIT open source license. Source code and documentation are available at https://github.com/ekg/seqwish. seqwish can be installed via Bioconda https://bioconda.github.io/recipes/seqwish/README.html or GNU Guix https://github.com/ekg/guix-genomics/blob/master/seqwish.scm.

Overview

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1093/bioinformatics/btac743

Cites

3 of 3 references verified0 citation errors · 0 not checkable

Statistics

Figures

Fig. 1. A visual description of variation graph induction. (Top) An alignment graph model for three sequences and their alignments. Nodes are single characters (DNA base pairs, of which the forward strand is shown) in individual sequences. Solid edges link successive characters in each sequence, and are colored (red, green and blue) to identify each. Dashed edges indicate aligned pairs of characters. (Bottom) A variation graph model induced from the alignment graph. Each transitive match closure (gray shaded edges, of increasing darkness) in the alignment graph results in a single node in the output graph, which is labeled by the rank of the transitive closure operation that produced it. By recording the full set of match closures, we can project the sequences in the input through to paths in the variation graph (colored edges). The unique set of node pairings in the paths provide the edges of the output graph. Closures 1 and 6 imply pairwise relationships between sequences seq1 and seq3, and seq1 and seq2, respectively, that are both absent in the input alignments
Fig. 1. A visual description of variation graph induction. (Top) An alignment graph model for three sequences and their alignments. Nodes are single characters (DNA base pairs, of which the forward strand is shown) in individual sequences. Solid edges link successive characters in each sequence, and are colored (red, green and blue) to identify each. Dashed edges indicate aligned pairs of characters. (Bottom) A variation graph model induced from the alignment graph. Each transitive match closure (gray shaded edges, of increasing darkness) in the alignment graph results in a single node in the output graph, which is labeled by the rank of the transitive closure operation that produced it. By recording the full set of match closures, we can project the sequences in the input through to paths in the variation graph (colored edges). The unique set of node pairings in the paths provide the edges of the output graph. Closures 1 and 6 imply pairwise relationships between sequences seq1 and seq3, and seq1 and seq2, respectively, that are both absent in the input alignmentsCC BY · PubMed Central
Fig. 2. Experimental results from the application of seqwish to four different pangenomes. Each plot shows the runtime (in hours) versus the average input genome length calculated as the total length of all sequences in the pangenome divided by the number of included haplotypes. Multiple minimum identity settings for the mapping (wfmash -p) and different minimum match length filter settings (seqwish -k) result in a collection of graph builds per pangenome input. We compare the runtime in hours with the size of the resulting graphs relative to the average size of an input genome in the particular set. Lower limits on pairwise identity result in more compact graphs. Similarly, filtering short matches increases graph size relative to not (seqwish -k = 0, red). The other way around, increasing the seqwish -k parameter tends to increase the size of the graph
Fig. 2. Experimental results from the application of seqwish to four different pangenomes. Each plot shows the runtime (in hours) versus the average input genome length calculated as the total length of all sequences in the pangenome divided by the number of included haplotypes. Multiple minimum identity settings for the mapping (wfmash -p) and different minimum match length filter settings (seqwish -k) result in a collection of graph builds per pangenome input. We compare the runtime in hours with the size of the resulting graphs relative to the average size of an input genome in the particular set. Lower limits on pairwise identity result in more compact graphs. Similarly, filtering short matches increases graph size relative to not (seqwish -k = 0, red). The other way around, increasing the seqwish -k parameter tends to increase the size of the graphCC BY · PubMed Central
Fig. 3. Base-pair lengths of graphs built from 100 permutations of yeast chrV. Each point corresponds to the length of a graph built from a specific permutation and the given method. We color each point by the first genome in the order (the ‘reference’ in minigraph). A boxplot per first genome group provides the mean and the first and third quartile intervals for each reference grouping
Fig. 3. Base-pair lengths of graphs built from 100 permutations of yeast chrV. Each point corresponds to the length of a graph built from a specific permutation and the given method. We color each point by the first genome in the order (the ‘reference’ in minigraph). A boxplot per first genome group provides the mean and the first and third quartile intervals for each reference groupingCC BY · PubMed Central

Verification

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Citations

Cites

Research works printed but not linked: 23

  1. Axtmann, 2017, 9:1
  2. Eizenga, 2021, Connecting with Computability, 169, 10.1007/978-3-030-80049-9_15 · DOI
  3. Garrison, 2018, Variation graph toolkit improves read mapping by representing genetic variation in the reference, Nat. Biotechnol, 36, 875, 10.1038/nbt.4227 · DOI · Paper page
  4. Gog, 2014, From theory to practice: plug and play with succinct data structures, Experimental Algorithms, 326, 10.1007/978-3-319-07959-2_28 · DOI
  5. Guarracino, 2022, ODGI: understanding pangenome graphs, Bioinformatics, 38, 3319, 10.1093/bioinformatics/btac308 · DOI
  6. Hein, 1989, A new method that simultaneously aligns and reconstructs ancestral sequences for any number of homologous sequences, when the phylogeny is given, Mol. Biol. Evol, 6, 649
  7. Hickey, 2020, Genotyping structural variants in pangenome graphs using the vg toolkit, Genome Biol, 21, 35, 10.1186/s13059-020-1941-7 · DOI · Paper page
  8. Jain, 2018, A fast adaptive algorithm for computing whole-genome homology maps, Bioinformatics, 34, i748, 10.1093/bioinformatics/bty597 · DOI
  9. Janson, 1993, The birth of the giant component, Random Struct. Algor, 4, 233, 10.1002/rsa.3240040303 · DOI
  10. Lee, 2002, Multiple sequence alignment using partial order graphs, Bioinformatics, 18, 452, 10.1093/bioinformatics/18.3.452 · DOI
  11. Li, 2018, Minimap2: pairwise alignment for nucleotide sequences, Bioinformatics, 34, 3094, 10.1093/bioinformatics/bty191 · DOI · Paper page
  12. Li, 2021, Bedtk: finding interval overlap with implicit interval tree, Bioinformatics, 37, 1315, 10.1093/bioinformatics/btaa827 · DOI
  13. Marco-Sola, 2021, Fast gap-affine pairwise alignment using the wavefront algorithm, Bioinformatics, 37, 456, 10.1093/bioinformatics/btaa777 · DOI
  14. Medini, 2005, The microbial pan-genome, Curr. Opin. Genet. Dev, 15, 589, 10.1016/j.gde.2005.09.006 · DOI
  15. Minkin, 2016, Twopaco: an efficient algorithm to build the compacted de Bruijn graph from many complete genomes, Bioinformatics, btw609, 10.1093/bioinformatics/btw609 · DOI
  16. Mose, 2019, Improved indel detection in DNA and RNA via realignment with abra2, Bioinformatics, 35, 2966, 10.1093/bioinformatics/btz033 · DOI
  17. Rhie, 2021, Towards complete and error-free genome assemblies of all vertebrate species, Nature, 592, 737, 10.1038/s41586-021-03451-0 · DOI · Paper page
  18. Sheikhizadeh, 2016, PanTools: representation, storage and exploration of pan-genomic data, Bioinformatics, 32, i487, 10.1093/bioinformatics/btw455 · DOI
  19. Sherman, 2020, Pan-genomics in the human genome era, Nat. Rev. Genet, 21, 243, 10.1038/s41576-020-0210-7 · DOI
  20. The Computational Pan-Genomics Consortium, 2018, Computational pan-genomics: status, promises and challenges, Brief Bioinformatics, 19, 118
  21. Yokoyama, 2019, MoMI-G: modular multi-scale integrated genome graph browser, BMC Bioinformatics, 20, 548, 10.1186/s12859-019-3145-2 · DOI
  22. Yu, 2021, Stliter: a novel algorithm to iteratively build the compacted de Bruijn graph from many complete genomes, IEEE/ACM Trans. Comput. Biol. Bioinform, 19, 2471, 10.1109/TCBB.2021.3062068 · DOI
  23. Yue, 2017, Contrasting evolutionary genome dynamics between domesticated and wild yeasts, Nat. Genet, 49, 913, 10.1038/ng.3847 · DOI

Cited by

Sorted by citations

See all 95

Metadata

Authors
Garrison, E., & Guarracino, A.
Affiliations
  • Department of Genetics, Genomics and Informatics, University of Tennessee Health Science Center , Memphis, TN 38163, USA
  • Genomics Research Centre, Human Technopole , Viale Rita Levi-Montalcini 1 , Milan 20157, Italy
ORCID
Venue
Bioinformatics
Publisher
Oxford University Press (OUP)
Published
2022-11-30
Volume
39
Issue
1
ISSN
1367-4811
DOI
10.1093/bioinformatics/btac743
PMC
PMC9805579
Cited by
95
References
3
Language
en
Licence
creativecommons.org/licenses/by/4.0/ (vor)
Funders
  • NIH
  • NIDA (U01DA047638)
  • NSF PPoSS (#2118709)
  • Human Technopole in Milan

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review