Bonnie Kirkpatrick

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2010-89

May 31, 2010

http://www2.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},
    Year= {2010},
    Month= {May},
    Url= {http://www2.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://www2.eecs.berkeley.edu/Pubs/TechRpts/2010/EECS-2010-89.html
%F Kirkpatrick:EECS-2010-89