Title
IPED: inheritance path-based pedigree reconstruction algorithm using genotype data.
Abstract
The problem of inference of family trees, or pedigree reconstruction, for a group of individuals is a fundamental problem in genetics. Various methods have been proposed to automate the process of pedigree reconstruction given the genotypes or haplotypes of a set of individuals. Current methods, unfortunately, are very time-consuming and inaccurate for complicated pedigrees, such as pedigrees with inbreeding. In this work, we propose an efficient algorithm that is able to reconstruct large pedigrees with reasonable accuracy. Our algorithm reconstructs the pedigrees generation by generation, backward in time from the extant generation. We predict the relationships between individuals in the same generation using an inheritance path-based approach implemented with an efficient dynamic programming algorithm. Experiments show that our algorithm runs in linear time with respect to the number of reconstructed generations, and therefore, it can reconstruct pedigrees that have a large number of generations. Indeed it is the first practical method for reconstruction of large pedigrees from genotype data.
Year
DOI
Venue
2013
10.1089/cmb.2013.0080
Journal of Computational Biology
Keywords
DocType
Volume
large pedigree,pedigree reconstruction algorithm,pedigrees generation,pedigree reconstruction,linear time,inheritance path,large number,time consuming,efficient algorithm,efficient dynamic programming algorithm,reconstructed generation,extant generation,genotype data
Journal
20
Issue
ISSN
Citations 
10
1557-8666
5
PageRank 
References 
Authors
0.81
4
5
Name
Order
Citations
PageRank
Dan He113312.54
Zhanyong Wang2507.04
Buhm Han3508.89
Laxmi Parida477377.21
Eleazar Eskin51790170.53