An Efficient Graph Algorithm for Diploid Local Ancestry Inference

Avatar
Poster
Voice is AI-generated
Connected to paperThis paper is a preprint and has not been certified by peer review

An Efficient Graph Algorithm for Diploid Local Ancestry Inference

Authors

Jafarzadeh, N.; Eizenga, J. M.; Paten, B.

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.

Follow Us on

0 comments

Add comment