# Algorithms for Comparing Pedigree Graphs

### Bonnie Kirkpatrick

###
EECS Department

University of California, Berkeley

Technical Report No. UCB/EECS-2010-89

May 31, 2010

### http://www.eecs.berkeley.edu/Pubs/TechRpts/2010/EECS-2010-89.pdf

Family relationships in the form of pedigree graphs are currently collected from genealogical records in an expensive process of determining which pairs of people are parent and child. With the end goal of reconstructing pedigrees, this paper considers how to compare two pedigree graphs for accuracy.

This paper reminds the reader of an alternative formulation of pedigree relationships, published earlier, that describes a pedigree as a list of descendant individuals, rather than parent-child relationships. This formulation is useful for comparing two similar pedigree graphs via a randomized algorithm that estimates the minimum number of edge changes that are necessary to change one pedigree into the other. This randomized algorithm runs in polynomial time.

BibTeX citation:

@techreport{Kirkpatrick:EECS-2010-89, Author = {Kirkpatrick, Bonnie}, Title = {Algorithms for Comparing Pedigree Graphs}, Institution = {EECS Department, University of California, Berkeley}, Year = {2010}, Month = {May}, URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2010/EECS-2010-89.html}, Number = {UCB/EECS-2010-89}, Abstract = {Family relationships in the form of pedigree graphs are currently collected from genealogical records in an expensive process of determining which pairs of people are parent and child. With the end goal of reconstructing pedigrees, this paper considers how to compare two pedigree graphs for accuracy. This paper reminds the reader of an alternative formulation of pedigree relationships, published earlier, that describes a pedigree as a list of descendant individuals, rather than parent-child relationships. This formulation is useful for comparing two similar pedigree graphs via a randomized algorithm that estimates the minimum number of edge changes that are necessary to change one pedigree into the other. This randomized algorithm runs in polynomial time.} }

EndNote citation:

%0 Report %A Kirkpatrick, Bonnie %T Algorithms for Comparing Pedigree Graphs %I EECS Department, University of California, Berkeley %D 2010 %8 May 31 %@ UCB/EECS-2010-89 %U http://www.eecs.berkeley.edu/Pubs/TechRpts/2010/EECS-2010-89.html %F Kirkpatrick:EECS-2010-89