A linear-time algorithm for the Perfect Phylogeny Haplotyping (PPH) problem
A linear-time algorithm for the Perfect Phylogeny Haplotyping (PPH) problem
复制标题
DOI：
10.1089/cmb.2006.13.522
复制
发表时间：
2006-03-01
影响因子：
1.7
通讯作者：
Gusfield, D
中科院分区：
文献类型：
--
作者：
Ding, ZH;Filkov, V;Gusfield, D
自从在RECOMB 2002 （Gusfield, 2002）中引入完美系统发育单倍型（PPH）问题以来，尽管人们对PPH问题有广泛的兴趣，并发表了一系列关于它的各个方面的论文，但为它找到线性时间（确定性的，最坏情况）解决方案的问题仍然是开放的。本文以简单的数据结构和简单的运算为基础，给出了一种实用的确定性线性时间算法。该方法编程简单，并已完全实现。仿真结果表明，该方法在实际应用中比以往的非线性方法要快得多。PPH问题的线性时间解的价值部分是概念性的，部分是用于更复杂问题的算法内循环，其中PPH问题必须反复求解。
Since the introduction of the Perfect Phylogeny Haplotyping ( PPH) Problem in RECOMB 2002 ( Gusfield, 2002), the problem of finding a linear-time ( deterministic, worst-case) solution for it has remained open, despite broad interest in the PPH problem and a series of papers on various aspects of it. In this paper, we solve the open problem, giving a practical, deterministic linear-time algorithm based on a simple data structure and simple operations on it. The method is straightforward to program and has been fully implemented. Simulations show that it is much faster in practice than prior nonlinear methods. The value of a linear-time solution to the PPH problem is partly conceptual and partly for use in the inner loop of algorithms for more complex problems, where the PPH problem must be solved repeatedly.