Pedigree Reconstruction Using Identity by Descent

TitlePedigree Reconstruction Using Identity by Descent
Publication TypeJournal Article
Year of Publication2011
AuthorsKirkpatrick, B., Li S. Cheng, Karp R. M., & Halperin E.
Published inJournal of Computational Biology
Other Numbers3876

Can we find the family trees, or pedigrees, that relate the haplotypes of a group of individu-als? Collecting the genealogical information for how individuals are related is a very time-consuming andexpensive process. Methods for automating the construction of pedigrees could stream-line this process.While constructing single-generation families is relatively easy given whole genome data, reconstructingmulti-generational, possibly inbred, pedigrees is much more challenging.This paper addresses the important question of reconstructing monogamous, regular pedigrees, wherepedigrees are regular when individuals mate only with other individuals at the same generation. This pa-per introduces two multi-generational pedigree reconstruction methods: one for inbreeding relationshipsand one for outbreeding relationships. In contrast to previous methods that focused on the independentestimation of relationship distances between every pair of typed individuals, here we present methodsthat aim at the reconstruction of the entire pedigree. We show that both our methods out-performthe state-of-the-art and that the outbreeding method is capable of reconstructing pedigrees at least sixgenerations back in time with high accuracy.The two programs are available at


This work was partially supported by funding provided through a National Science Foundation Graduate Research Grant and through National Science Foundation grant CCF : 1052553 (“Systematic Construction of Heuristic Algorithms for Combinatiorial Optimization Problems in Biology"). Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors or originators and do not necessarily reflect the views of the National Science Foundation.

Bibliographic Notes

Journal of Computational Biology, Vol. 18, No. 11, pp. 1481-1493, November 2011.

Abbreviated Authors

B. Kirkpatrick, S. C. Li, R. M. Karp, and E. Halperin

ICSI Research Group


ICSI Publication Type

Article in journal or magazine