The design and construction of reference pangenome graphs with minigraph

Abstract

The recent advances in sequencing technologies enable the assembly of individual genomes to the quality of the reference genome. How to integrate multiple genomes from the same species and make the integrated representation accessible to biologists remains an open challenge. Here, we propose a graph-based data model and associated formats to represent multiple genomes while preserving the coordinate of the linear reference genome. We implement our ideas in the minigraph toolkit and demonstrate that we can efficiently construct a pangenome graph and compactly encode tens of thousands of structural variants missing from the current reference genome.

Keywords: Bioinformatics; Genomics; Pangenome.

Fig. 1

Example rGFA and GAF formats. a Example rGFA format. rGFA-specific tags include SN, name of the stable sequence from which the vertex is derived; SO, offset on the stable sequence; SR, rank: 0 if the vertex or edge is on the linear reference; >0 for non-reference. b Corresponding sequence graph. Each thick arrow represents an oriented DNA sequence. c Example GAF format, using the segment coordinate, for reads “ GTGGCT” and “ CGTTTCC” mapped to the graph. d Equivalent GAF format using the stable coordinate

Fig. 2

Minigraph algorithms. a Diagram of the minigraph mapping algorithm. Minigraph seeds alignments with minimizers, finds good enough linear chains, connects them in the graph and seeks the most weighted path as a graph chain. b Diagram of incremental graph construction. A graph is iteratively constructed by mapping each assembly to an existing graph and augmenting the graph with long poorly mapped sequences in the assembly

Fig. 3

Characteristics of the human and the great ape graphs. a Human variations stratified by repeat class and by the number of alleles of each variation. The repeat annotation was obtained from the longest allele of each variation. VNTR: variable-number tandem repeat, a tandem repeat with the unit motif length ≥7bp. STR: short random repeat, a tandem repeat with the unit motif length ≤6bp. LCR: low-complexity regions. Mixed-inter.: a variation involving ≥2 types of interspersed repeats. b Great ape variations stratified by repeat class and by the number of alleles. c Human biallelic variations stratified by repeat class and by insertion to/deletion from GRCh38. Both alleles are required to be covered in all assemblies. d Human-specific biallelic variations stratified by repeat class and by insertion to/deletion from GRCh38. Red bars correspond to insertions to the human lineage. e Distribution of different types of human variations along chromosomes. f Boxplot of the longest allele length in each repeat class. Outliers are omitted for the clarity of the figure

Fig. 4

IGV screenshot of a region enriched with long insertions. Numbers on wide purple bars indicate insertion lengths. CLR: PacBio noisy continuous long reads. HiFi: PacBio high-fidelity reads

Fig. 5

Implementing 1-dimension Range-Min-Query (RMQ). Given a set of 2-tuples, a binary search tree is built for the first values in the tuples. Each node p in the tree is associated with a pointer. The pointer points to the node that is in the subtree descended from p and has the minimal second value. In this example, RMQ(20,50)=14