Pangenome graph layout by Path-Guided Stochastic Gradient Descent
Open Access
- 1 July 2024
- journal article
- research article
- Published by Oxford University Press (OUP) in Bioinformatics
- Vol. 40 (7)
Abstract
The increasing availability of complete genomes demands for models to study genomic variability within entire populations. Pangenome graphs capture the full genomic similarity and diversity between multiple genomes. In order to understand them, we need to see them. For visualization, we need a human-readable graph layout: a graph embedding in low (e.g. two) dimensional depictions. Due to a pangenome graph’s potential excessive size, this is a significant challenge. In response, we introduce a novel graph layout algorithm: the Path-Guided Stochastic Gradient Descent (PG-SGD). PG-SGD uses the genomes, represented in the pangenome graph as paths, as an embedded positional system to sample genomic distances between pairs of nodes. This avoids the quadratic cost seen in previous versions of graph drawing by SGD. We show that our implementation efficiently computes the low-dimensional layouts of gigabase-scale pangenome graphs, unveiling their biological features. We integrated PG-SGD in ODGI which is released as free software under the MIT open source license. Source code is available at https://github.com/pangenome/odgi.Keywords
Funding Information
- German Network for Bioinformatics Infrastructure (031A533A, 031A533B, 031A534A, 031A535A, 031A537A, 031A537B, 031A537C, 031A537D)
- National Institutes of Health
This publication has 19 references indexed in Scilit:
- Pangenome GraphsAnnual Review of Genomics and Human Genetics, 2020
- Pan-genomics in the human genome eraNature Reviews Genetics, 2020
- Is it time to change the reference genome?Genome Biology, 2019
- Variation graph toolkit improves read mapping by representing genetic variation in the referenceNature Biotechnology, 2018
- Graph Drawing by Stochastic Gradient DescentIEEE Transactions on Visualization and Computer Graphics, 2018
- Evaluation of GRCh38 and de novo haploid genome assemblies demonstrates the enduring quality of the reference assemblyGenome Research, 2017
- Computational pan-genomics: status, promises and challengesBriefings in Bioinformatics, 2016
- Comparative genomics: the bacterial pan-genomeCurrent Opinion in Microbiology, 2008
- The sequence and analysis of duplication-rich human chromosome 16Nature, 2004
- A new method that simultaneously aligns and reconstructs ancestral sequences for any number of homologous sequences, when the phylogeny is given.Molecular Biology and Evolution, 1989