Currently, pedigrees are constructed by careful survey of the parent-offspring relationships between individuals in an extended family. The survey is usually conducted by interviewing potential subjects and by examining birth records. The manual labor involved in conducting these surveys is quite expensive and the resulting data can be incomplete or erroneous. In this paper, we present an alternative formulation of pedigree relationships that may be useful either for inferring pedigrees from micro-satellite data or for focusing a genealogical survey towards parts of the pedigree that are poorly resolved.

Much of the early work on pedigree reconstruction relied on a graphical model of inheritance in pedigrees, where the reconstruction algorithms choose pedigree graphs that maximized the likelihood of the observed data. That formulation of the pedigree reconstruction problem is a typical example of parametric structured machine learning where the graphical model of interest is the pedigree model. The work presented here is a departure from parametric methods and develops combinatorial methods for estimating pedigree structures.

(Manuscript revised Apr 20, 2010. Manuscript drafted on May 16, 2008 as part of a class project for CS294-26/STAT260: Computational and Mathematical Population Genetics with Prof. Yun Song.)




Download Full History