Vijayasatya Ravi, Mukherjee Amar
School of Computer Science, University of Central Florida, 32816-2362, USA.
Proc IEEE Comput Syst Bioinform Conf. 2005:103-10. doi: 10.1109/csb.2005.12.
The Perfect Phylogeny Haplotyping (PPH) problem is one of the many computational approaches to the Haplotype Inference (HI) problem. Though there are many O(nm(2)) solutions to the PPH problem, the complexity of the PPH problem itself has remained an open question. In this paper, We introduce the FlexTree data structure that represents all the solutions for a PPH instance. We also introduce row-ordering that arranges the genotypes in a more manageable fashion. The column ordering, the FlexTree data structure and the row ordering together make the O(nm) OPPH algorithm possible. We also present some results on simulated data which demonstrate that the OPPH algorithm performs quiet impressively when compared to the earlier O(nm(2)) algorithms.
完美系统发育单倍型分型（PPH）问题是单倍型推断（HI）问题的众多计算方法之一。尽管有许多针对PPH问题的O(nm(2))解决方案，但PPH问题本身的复杂度仍是一个悬而未决的问题。在本文中，我们引入了表示PPH实例所有解决方案的FlexTree数据结构。我们还引入了行排序，以更易于管理的方式排列基因型。列排序、FlexTree数据结构和行排序共同使得O(nm)的OPPH算法成为可能。我们还展示了一些模拟数据的结果，这些结果表明，与早期的O(nm(2))算法相比，OPPH算法的表现相当出色。
