IPED: Inheritance Path-based Pedigree Reconstruction Algorithm Using Genotype Data
IPED: Inheritance Path-based Pedigree Reconstruction Algorithm Using Genotype Data
复制标题
DOI：
10.1089/cmb.2013.0080
复制
发表时间：
2013-10-01
影响因子：
1.7
通讯作者：
Eskin, Eleazar
中科院分区：
文献类型：
--
作者：
He, Dan;Wang, Zhanyong;Eskin, Eleazar
对一群个体的家谱或系谱重建的推断问题是遗传学中的一个基本问题。已经提出了各种方法来自动化的过程中的系谱重建给定的基因型或单倍型的一组个人。目前的方法，不幸的是，是非常耗时和不准确的复杂谱系，如与近亲繁殖的谱系。在这项工作中，我们提出了一个有效的算法，能够重建大谱系合理的准确性。我们的算法重建的系谱一代一代，从现存的一代在时间上倒退。我们预测在同一世代的个人之间的关系，使用一个有效的动态规划算法实现的继承路径为基础的方法。实验表明，该算法的运行时间与重建的代数成线性关系，因此，它可以重建具有大量代数的谱系。事实上，这是第一个实用的方法重建大谱系基因型数据。
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.