Comparing Pedigree Graphs
Title | Comparing Pedigree Graphs |
Publication Type | Journal Article |
Year of Publication | 2012 |
Authors | Kirkpatrick, B., Reshef Y., Finucane H., Jiang H., Zhu B., & Karp R. M. |
Published in | Journal of Computational Biology |
Volume | 19 |
Issue | 9 |
Page(s) | 998-1014 |
Other Numbers | 3334 |
Abstract | 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 rst 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 rst 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. |
URL | http://www.icsi.berkeley.edu/pubs/algorithms/ICSI_comparingpedigree12.pdf |
Bibliographic Notes | Journal of Computational Biology, Vol. 19, No. 9, pp. 998-1014 |
Abbreviated Authors | B. Kirkpatrick, Y. Reshef, H. Finucane, H. Jiang, B. Zhu, and R. M. Karp |
ICSI Research Group | Algorithms |
ICSI Publication Type | Article in journal or magazine |