The Undirected Incomplete Perfect Phylogeny Problem

ABSTRACT

The incomplete perfect phylogeny (IPP) problem and the incomplete perfect phylogeny haplotyping (IPPH) problem deal with constructing a phylogeny for a given set of haplotypes or genotypes with missing entries. The earlier approaches for both of these problems dealt with restricted versions of the problems, where the root is either available or can be trivially re-constructed from the data, or certain assumptions were made about the data. In this paper, we deal with the unrestricted versions of the problems, where the root of the phylogeny is neither available nor trivially recoverable from the data. Both IPP and IPPH problems have previously been proven to be NPcomplete. Here, we present efficient enumerative algorithms that can handle practical instances of the problem. Empirical analysis on simulated data shows that the algorithms perform very well both in terms of speed and in terms accuracy of the recovered data.

REFERENCES

• 1: Richa Agarwala , David Fernandez-Baca, A Polynomial-Time Algorithm for the Perfect Phylogeny Problem when the Number of Character States is Fixed, SIAM Journal on Computing, v.23 n.6, p.1216-1224, Dec. 1994 [doi>10.1137/S0097539793244587]
• 2: HapMapConsortium, "The International Hapmap Project," Nature , vol. 426, pp. 789-796, Dec. 2003.
• 3: A.G. Clark, "Inference of Haplotypes from PCR-Amplified Samples of Diploid Populations," Molecular Biology and Evolution, vol. 7, pp. 111-122, 1990.
• 4: Dan Gusfield, Haplotyping as perfect phylogeny: conceptual framework and efficient solutions, Proceedings of the sixth annual international conference on Computational biology, p.166-175, April 18-21, 2002, Washington, DC, USA [doi>10.1145/565196.565218]
• 5: Y. Liu and C.-Q. Zhang, "A Linear Solution for Haplotype Perfect Phylogeny Problem," Proc. Int'l Conf. Bioinformatics and Its Applications (ICBA), 2004.
• 6: Ravi VijayaSatya , Amar Mukherjee, An Efficient Algorithm for Perfect Phylogeny Haplotyping, Proceedings of the 2005 IEEE Computational Systems Bioinformatics Conference, p.103-110, August 08-11, 2005 [doi>10.1109/CSB.2005.12]
• 7: Z. Ding, V. Filkov, and D. Gusfield, "A Linear Time Algorithm for the Perfect Phylogeny Haplotyping (PPH) Problem," Proc. Ann. Int'l Conf. Research in Computational Molecular Biology (RECOMB '05), pp. 585-600, 2005.
• 8: Z. Ding, V. Filkov, and D. Gusfield, "A Linear Time Algorithm for the Perfect Phylogeny Haplotyping (PPH) Problem," J. Computational Biology, vol. 13, no. 2, pp. 522-553, 2006.
• 9: R. Vijaya Satya and A. Mukherjee, "An Optimal Algorithm for Perfect Phylogeny Haplotyping," J. Computational Biology, vol. 13, no. 4, pp. 897-928, 2006.
• 10: M. Steel, "The Complexity of Reconstructing Trees from Qualitative Characters and Subtrees," J. Classification, vol. 9, pp. 91-116, 1992.
• 11: Itsik Pe'er , Tal Pupko , Ron Shamir , Roded Sharan, Incomplete Directed Perfect Phylogeny, SIAM Journal on Computing, v.33 n.3, p.590-607, 2004 [doi>10.1137/S0097539702406510]
• 12: G. Kimmel and R. Shamir, "The Incomplete Perfect Phylogeny Problem," J. Bioinformatics and Computational Biology, vol. 3, no. 2, pp. 1-25, 2005.
• 13: Eran Halperin , Richard M. Karp, Perfect phylogeny and haplotype assignment, Proceedings of the eighth annual international conference on Resaerch in computational molecular biology, p.10-19, March 27-31, 2004, San Diego, California, USA [doi>10.1145/974614.974617]
• 14: R. Vijaya Satya and A. Mukherjee, The Undirected Incomplete Perfect Phylogeny Problem, Technical Report CS-TR-05-11, School of Computer Science, Univ. of Central Florida, Dec. 2005.
• 15: J. Gramm, T. Nierhoff, R. Sharan, and T. Tantau, "Haplotyping with Missing Data via Perfect Path Phylogenies," Proc. Second RECOMB Satellite Workshop Computational Methods for SNPs and Haplotypes, pp. 35-46, 2004.
• 16: V. Bafna, D. Gusfield, G. Lancia, and S. Yooseph, "Haplotyping as Perfect Phylogeny: A Direct Approach," J. Computational Biology, vol. 10, nos. 3-4, pp. 323-340, 2003.
• 17: R. Hudson, "Generating Samples under the Wright-Fisher Neutral Model of Genetic Variation," Bioinformatics, vol. 18, pp. 337-338, 2002.

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.3 LIFE AND MEDICAL SCIENCES
      Subjects: Biology and genetics

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.1 Models
  I.6 SIMULATION AND MODELING
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Theory

Keywords:
Phylogenetics, Perfect Phylogeny, Incomplete Perfect Phylogeny, Haplotype Inference