An efficient algorithm for haplotype inference on pedigrees with recombinations and mutations.
An efficient algorithm for haplotype inference on pedigrees with recombinations and mutations.
复制标题
一种对具有重组和突变的谱系进行单倍型推断的有效算法。
DOI：
10.1109/tcbb.2011.51
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Jiang,Tao
中科院分区：
文献类型：
--
作者：
Pirola,Yuri;Bonizzoni,Paola;Jiang,Tao
单倍型推断（HI）是一系列遗传学研究中至关重要的计算挑战。系谱允许从基因型比群体数据更准确地推断单倍型，因为孟德尔遗传限制了可能的解决方案的集合。在这项工作中，我们定义了一个关于谱系的新HI问题，称为最小变化单倍型配置（MCHC）问题，该问题允许两种类型的遗传变异事件：重组和突变。我们的新配方扩展了最小重组单倍型配置（MRHC）的问题，已在文献中提出，以克服经典的统计单倍型分析方法的局限性。我们的贡献是双重的。首先，我们证明了MCHC问题是APX困难的几个限制。其次，我们提出了一个高效和准确的启发式算法MCHC的基础上L-减少一个著名的编码问题。我们的启发式算法还可以用于解决原始的MRHC问题，并且可以利用有关输入基因型的额外知识。此外，L-约化首次证明了MCHC和MRHC在一般家系上是O（nm/log nm）-可近似的，其中n是家系大小，m是基因型长度。最后，我们提出了一个广泛的实验评估和比较，我们的启发式算法与其他几个国家的最先进的方法HI的谱系。
Haplotype Inference (HI) is a computational challenge of crucial importance in a range of genetic studies. Pedigrees allow to infer haplotypes from genotypes more accurately than population data, since Mendelian inheritance restricts the set of possible solutions. In this work, we define a new HI problem on pedigrees, called Minimum-Change Haplotype Configuration (MCHC) problem, that allows two types of genetic variation events: recombinations and mutations. Our new formulation extends the Minimum-Recombinant Haplotype Configuration (MRHC) problem, that has been proposed in the literature to overcome the limitations of classic statistical haplotyping methods. Our contribution is twofold. First, we prove that the MCHC problem is APX-hard under several restrictions. Second, we propose an efficient and accurate heuristic algorithm for MCHC based on an L-reduction to a well-known coding problem. Our heuristic can also be used to solve the original MRHC problem and can take advantage of additional knowledge about the input genotypes. Moreover, the L-reduction proves for the first time that MCHC and MRHC are O(nm/log nm)-approximable on general pedigrees, where n is the pedigree size and m is the genotype length. Finally, we present an extensive experimental evaluation and comparison of our heuristic algorithm with several other state-of-the-art methods for HI on pedigrees.