Tracing the Right Path: Determination of Large Pedigree Segmentation and Relatedness

Abstract Large population databases frequently include complicated family structures that are amenable to modern biometric methods: allowing for intergenerational and extended pedigree analyses. To date, much of the latent potential of these resources remains untapped due to numerous complexities that arise in their analysis. Two difficult and critical problems are (1) finding independent extended families within larger population databases, and (2) determining coefficients of relatedness among all pairs of individuals within those extended families. If these problems were solved, researchers could more fully utilize data on extended families for biometric modeling. In this paper, we provide fast, computationally efficient algorithms for both of these problems and several more that are applicable to arbitrarily large and complex pedigrees. The algorithms rely solely on mother-child and father-child relationships that form the basis of many large population databases. These methods will be invaluable to any researcher trying to segment standard pedigree data files into independent extended family units, compute relatedness coefficients within extended families, and conduct intergenerational and other biometric modeling.