An Efficient Graph Algorithm for Diploid Local Ancestry Inference

Abstract

In this paper, we present diploid sequence graphs, graphs whose paths encode pairs of haplotypes. We describe an efficient algorithm for creating a diploid graph from a directed acyclic (haploid) sequence graph, such that the diploid graph represents all the possible pairings of haplotypes present in the sequence graph and their similarity relationships. Starting with the sequence graph, our method uses a graph decomposition approach based on an extension of the SPQR-tree to systematically identify structural patterns that reduce redundancy while preserving genetic variation. We develop a polynomial-time algorithm that parsimoniously enumerates all disjoint paths with shared endpoints in two-terminal directed acyclic graphs. In the future, we envisage that diploid graphs may enable more accurate modeling of recombination, phasing, and variation-aware alignment in diploid genomes.