Coordinate Systems for Pangenome Graphs based on the Level Function and Minimum Path Covers

Thomas Büchler; Caroline Räther; Pascal Weber; Enno Ohlebusch

doi:https://doi.org/10.5220/0010165400210029

Coordinate Systems for Pangenome Graphs based on the Level Function and Minimum Path Covers

Thomas Büchler, Caroline Räther, Pascal Weber, Enno Ohlebusch

Publications: Contribution to book › Contribution to proceedings › Peer Reviewed

Abstract

The Computational Pan-Genomics Consortium (Consortium, 2016) described the role of coordinate systems in genomics as follows: “A pan-genome defines the space in which (pan-)genomic analyses take place. It should provide a ‘coordinate system’ to unambiguously identify genetic loci and (potentially nested) genetic variants.” The most natural representations of pangenomes are graphs. The Computational Pan-Genomics Consortium identified desirable properties of the linear reference genome model that graphical frameworks should attempt to preserve: spatiality, monotonicity, and readability. In this paper, we introduce a coordinate system for DAGs that has these properties. It is based on the level function and a minimum path cover of the graph. Moreover, we describe a new method for finding a minimum path cover in a DAG, which works very well in practice.

Original language	English
Title of host publication	Proceedings of the 14th International Joint Conference on Biomedical Engineering Systems and Technologies - BIOINFORMATICS
Editors	R Lorenz, A Fred, H Gamboa
Pages	21-29
Number of pages	9
Volume	3
DOIs	https://doi.org/10.5220/0010165400210029
Publication status	Published - 11 Feb 2021
Externally published	Yes

Austrian Fields of Science 2012

102033 Data mining

Keywords

Pangenome
Coordinate System
Directed Acyclic Graph
Level Function
Minimum Path Cover

Access to Document

https://doi.org/10.5220/0010165400210029

Cite this

Büchler, T., Räther, C., Weber, P., & Ohlebusch, E. (2021). Coordinate Systems for Pangenome Graphs based on the Level Function and Minimum Path Covers. In R. Lorenz, A. Fred, & H. Gamboa (Eds.), Proceedings of the 14th International Joint Conference on Biomedical Engineering Systems and Technologies - BIOINFORMATICS (Vol. 3, pp. 21-29) https://doi.org/10.5220/0010165400210029

@inproceedings{ee7e2563f37b495e84c6e094a414ad67,

title = "Coordinate Systems for Pangenome Graphs based on the Level Function and Minimum Path Covers",

abstract = "The Computational Pan-Genomics Consortium (Consortium, 2016) described the role of coordinate systems in genomics as follows: “A pan-genome defines the space in which (pan-)genomic analyses take place. It should provide a {\textquoteleft}coordinate system{\textquoteright} to unambiguously identify genetic loci and (potentially nested) genetic variants.” The most natural representations of pangenomes are graphs. The Computational Pan-Genomics Consortium identified desirable properties of the linear reference genome model that graphical frameworks should attempt to preserve: spatiality, monotonicity, and readability. In this paper, we introduce a coordinate system for DAGs that has these properties. It is based on the level function and a minimum path cover of the graph. Moreover, we describe a new method for finding a minimum path cover in a DAG, which works very well in practice.",

keywords = "Pangenome, Coordinate System, Directed Acyclic Graph, Level Function, Minimum Path Cover",

author = "Thomas B{\"u}chler and Caroline R{\"a}ther and Pascal Weber and Enno Ohlebusch",

year = "2021",

month = feb,

day = "11",

doi = "https://doi.org/10.5220/0010165400210029",

language = "English",

isbn = "978-989-758-490-9",

volume = "3",

pages = "21--29",

editor = "R Lorenz and A Fred and H Gamboa",

booktitle = "Proceedings of the 14th International Joint Conference on Biomedical Engineering Systems and Technologies - BIOINFORMATICS",

}

Coordinate Systems for Pangenome Graphs based on the Level Function and Minimum Path Covers. / Büchler, Thomas; Räther, Caroline; Weber, Pascal et al.

Proceedings of the 14th International Joint Conference on Biomedical Engineering Systems and Technologies - BIOINFORMATICS. ed. / R Lorenz; A Fred; H Gamboa. Vol. 3 2021. p. 21-29.

Publications: Contribution to book › Contribution to proceedings › Peer Reviewed

TY - GEN

T1 - Coordinate Systems for Pangenome Graphs based on the Level Function and Minimum Path Covers

AU - Büchler, Thomas

AU - Räther, Caroline

AU - Weber, Pascal

AU - Ohlebusch, Enno

PY - 2021/2/11

Y1 - 2021/2/11

N2 - The Computational Pan-Genomics Consortium (Consortium, 2016) described the role of coordinate systems in genomics as follows: “A pan-genome defines the space in which (pan-)genomic analyses take place. It should provide a ‘coordinate system’ to unambiguously identify genetic loci and (potentially nested) genetic variants.” The most natural representations of pangenomes are graphs. The Computational Pan-Genomics Consortium identified desirable properties of the linear reference genome model that graphical frameworks should attempt to preserve: spatiality, monotonicity, and readability. In this paper, we introduce a coordinate system for DAGs that has these properties. It is based on the level function and a minimum path cover of the graph. Moreover, we describe a new method for finding a minimum path cover in a DAG, which works very well in practice.

AB - The Computational Pan-Genomics Consortium (Consortium, 2016) described the role of coordinate systems in genomics as follows: “A pan-genome defines the space in which (pan-)genomic analyses take place. It should provide a ‘coordinate system’ to unambiguously identify genetic loci and (potentially nested) genetic variants.” The most natural representations of pangenomes are graphs. The Computational Pan-Genomics Consortium identified desirable properties of the linear reference genome model that graphical frameworks should attempt to preserve: spatiality, monotonicity, and readability. In this paper, we introduce a coordinate system for DAGs that has these properties. It is based on the level function and a minimum path cover of the graph. Moreover, we describe a new method for finding a minimum path cover in a DAG, which works very well in practice.

KW - Pangenome

KW - Coordinate System

KW - Directed Acyclic Graph

KW - Level Function

KW - Minimum Path Cover

U2 - https://doi.org/10.5220/0010165400210029

DO - https://doi.org/10.5220/0010165400210029

M3 - Contribution to proceedings

SN - 978-989-758-490-9

VL - 3

SP - 21

EP - 29

BT - Proceedings of the 14th International Joint Conference on Biomedical Engineering Systems and Technologies - BIOINFORMATICS

A2 - Lorenz, R

A2 - Fred, A

A2 - Gamboa, H

ER -

Büchler T, Räther C, Weber P, Ohlebusch E. Coordinate Systems for Pangenome Graphs based on the Level Function and Minimum Path Covers. In Lorenz R, Fred A, Gamboa H, editors, Proceedings of the 14th International Joint Conference on Biomedical Engineering Systems and Technologies - BIOINFORMATICS. Vol. 3. 2021. p. 21-29 doi: https://doi.org/10.5220/0010165400210029