Identification of relationships and pedigree simplification using graph theory

Reliable pedigree and genomic data are essential for single-step genomic best linear unbiased prediction. Discrepancies between pedigree and genomic relationships must be identified and resolved before analysis. While parent-progeny relationships are typically verified using genomic data, other relationships, such as those between progeny and grandparents or half-sibs, are often unchecked. The numerator relationship matrix and genomic relationship matrix further obscure the precise nature of individuals' relationships. For example, half-sibs and grandparent-progeny pairs appear identical in the numerator relationship matrix. This article identifies these relationships among individuals in the numerator relationship matrix that are inconsistent with the genomic relationship matrix, applying graph theory to identify the precise type of their relationships and simplify pedigrees to pinpoint and correct errors. The results demonstrate that graph theory algorithms can accurately identify pedigree relationship types and extract any individual's ancestors, descendants, or other relationships from the pedigree.