title: Historical pedigree reconstruction from extant populations using PArtitioning of RElatives (PREPARE).
abstract: Recent technological improvements in the field of genetic data extraction give rise to the possibility of reconstructing the historical pedigrees of entire populations from the genotypes of individuals living today. Current methods are still not practical for real data scenarios as they have limited accuracy and assume unrealistic assumptions of monogamy and synchronized generations. In order to address these issues, we develop a new method for pedigree reconstruction, [Formula: see text], which is based on formulations of the pedigree reconstruction problem as variants of graph coloring. The new formulation allows us to consider features that were overlooked by previous methods, resulting in a reconstruction of up to 5 generations back in time, with an order of magnitude improvement of false-negatives rates over the state of the art, while keeping a lower level of false positive rates. We demonstrate the accuracy of [Formula: see text] compared to previous approaches using simulation studies over a range of population sizes, including inbred and outbred populations, monogamous and polygamous mating patterns, as well as synchronous and asynchronous mating.
authors.affiliation: The Balvatnic School of Computer Science, Tel-Aviv University, Tel-Aviv, Israel.
authors.forename: Doron
authors.initials: D
authors.lastname: Shem-Tov
authors.affiliation: The Balvatnic School of Computer Science, Tel-Aviv University, Tel-Aviv, Israel; International Computer Science Institute, Berkeley, California, United States of America; Molecular Microbiology and Biotechnology Department, Tel-Aviv University, Tel-Aviv, Israel.
authors.forename: Eran
authors.initials: E
authors.lastname: Halperin
mesh_terms: D000465:Algorithms; D019295:Computational Biology; D003196:Computer Graphics; D003198:Computer Simulation; D005260:Female; D005828:Genetics, Population / Q000379:methods* / Q000706:statistics & numerical data; D005838:Genotype; D006801:Humans; D016013:Likelihood Functions; D008297:Male; D010375:Pedigree