  Pedigree graphs, or family trees, are typically constructed by an expensive
process of examining genealogical records to determine which pairs of
individuals are parent and child. New methods to automate this process take as
input genetic data from a set of extant individuals and reconstruct ancestral
individuals. There is a great need to evaluate the quality of these methods by
comparing the estimated pedigree to the true pedigree.
  In this paper, we consider two main pedigree comparison problems. The first
is the pedigree isomorphism problem, for which we present a linear-time
algorithm for leaf-labeled pedigrees. The second is the pedigree edit distance
problem, for which we present 1) several algorithms that are fast and exact in
various special cases, and 2) a general, randomized heuristic algorithm.
  In the negative direction, we first prove that the pedigree isomorphism
problem is as hard as the general graph isomorphism problem, and that the
sub-pedigree isomorphism problem is NP-hard. We then show that the pedigree
edit distance problem is APX-hard in general and NP-hard on leaf-labeled
pedigrees.
  We use simulated pedigrees to compare our edit-distance algorithms to each
other as well as to a branch-and-bound algorithm that always finds an optimal
solution.
