Linear-Time Reconstruction of Zero-Recombinant Mendelian Inheritance on Pedigrees without Mating Loops
Linear-Time Reconstruction of Zero-Recombinant Mendelian Inheritance on Pedigrees without Mating Loops
复制标题
无交配循环谱系的零重组孟德尔遗传的线性时间重建
DOI：
10.1142/9781860949852_0009
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
Tao Jiang
中科院分区：
文献类型：
--
作者：
Lan Liu;Tao Jiang
随着国际HapMap计划的启动，单体型推断问题近年来引起了计算生物学界的极大关注。在本文中，我们研究的问题，如何有效地推断单倍型的基因型相关的一个家系没有交配环的个人，假设遗传过程是免费的突变（即孟德尔遗传定律）和重组。我们将单倍型推断问题建模为线性方程组[10]，并提出了一个（最佳）线性时间（即O（mn）时间）算法来生成单倍型推断问题的特定解决方案 *，其中in是基因型中的基因座（或标记）数量，n是谱系中的个体数量。此外，该算法还在O（mn 2）时间内提供了一个通解t，这是最优的，因为通解的大小可以与e（mn 2）一样大。我们构造的关键成分是（i）基于对方程之间关系的仔细研究，对[10]中引入的线性方程组进行快速一致性检查;（ii）一种新的线性时间方法，用于求解线性方程组，而无需调用高斯消元法。虽然这样一个快速的方法求解方程是不知道一般的线性方程组系统，我们利用底层的无环谱系图和一些特殊性质的线性方程组。
With the launch of the international HapMap project, the haplotype inference problem has attracted a great deal of attention in the computational biology community recently. In this paper, we study the question of how to efficiently infer haplotypes from genotypes of individuals related by a pedigree without mating loops, assuming that the hereditary process was free of mutations (ie the Mendelian law of inheritance) and recombinants. We model the haplotype inference problem as a system of linear equations as in [10] and present an (optimal) linear-time (ie O (mn) time) algorithm to generate a particular solution* to the haplotype inference problem, where in is the number of loci (or markers) in a genotype and n is the number of individuals in the pedigree. Moreover, the algorithm also provides a general solution t in O (mn2) time, which is optimal because the size of a general solution could be as large as e (mn2). The key ingredients of our construction are (i) a fast consistency checking procedure for the system of linear equations introduced in [10] based on a careful investigation of the relationship between the equations (ii) a novel linear-time method for solving linear equations without invoking the Gaussian elimination method. Although such a fast method for solving equations is not known for general systems of linear equations, we take advantage of the underlying loop-free pedigree graph and some special properties of the linear equations.