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

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.

Automated summary

The pan-genome defines the space for genomic analyses, with graphs being the most natural representation. The Computational Pan-Genomics Consortium identified desirable properties for graphical frameworks, such as spatiality, monotonicity, and readability, and introduced a coordinate system for DAGs based on the level function and minimum path cover.