Refining Phylogenetic Trees Given Additional Data: An Algorithm Based on Parsimony

ABSTRACT

Given a set X of taxa, a phylogenetic X-tree T that is only partially resolved, and a collection of characters on X, we consider the problem of finding a resolution (refinement) of T that minimizes the parsimony score of the given characters. Previous work has shown that this problem has a polynomial time solution provided certain strong constraints are imposed on the input. In this paper we provide a new algorithm for this problem, and show that it is fixed parameter tractable under more general conditions.

REFERENCES

• 1: Ernst Althaus , Rouven Naujoks, Computing steiner minimum trees in Hamming metric, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.172-181, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109578]
• 2: G. Blelloch, K. Dhamdhere, E. Halperin, R. Ravi, R. Schwartz, and S. Sridhar, "Fixed Parameter Tractability of Binary Near-Perfect Phylogenetic Tree Reconstruction," M. Bugliesi, B. Preneel, V. Sassone, I. Wegener, eds., Proc. 33rd Int'l Colloquium Automata, Languages and Programming (ICALP '06), Part I, pp. 667-678, 2006.
• 3: M. Bonet, M. Steel, T. Warnow, and S. Yooseph, "Better Methods for Solving Parsimony and Compatibility," J. Computational Biology, vol. 5, no. 3, pp. 391-408, 1998.
• 4: T. Bruen and D. Bryant, "A Subdivision Approach to Maximum Parsimony," Annals of Combinatorics, vol. 12, pp. 45-51, 2008.
• 5: W.H.E Day, "Computationally Difficult Parsimony Problems in Phylogenetics Systematics," J. Theoretical Biology, vol. 103, pp. 429-438, 1983.
• 6: J. Felsenstein, Inferring Phylogenies. Sinauer Assoc., Inc., 2004.
• 7: W. Fitch, "Toward Defining the Course of Evolution: Minimum Change for a Specified Tree Topology," Systematic Zoology, vol. 20, pp. 406-416, 1971.
• 8: L.R. Foulds and R.L. Graham, "The Steiner Problem in Phylogeny Is NP-Complete," Advances in Applied Math., vol. 3, pp. 43-49, 1982.
• 9: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 10: J.A. Hartigan, "Minimum Mutation Fits to a Given Tree," Biometrics, vol. 29, pp. 53-65, 1973.
• 11: D. Huson, M. Steel, and J. Whitfield, "Reducing Distortion in Phylogenetic Networks," Proc. Sixth Workshop Algorithms in Bioinformatics (WABI '06), pp. 150-161, 2006.
• 12: R. Niedermeier, Invitation to Fixed-Parameter Algorithms. Oxford Univ. Press, 2006.
• 13: O. Nomura, Z.H. Lin, Muladno, Y. Wada, and H. Yasue, "A SINE Species from Hippopotamus and Its Distribution among Animal Species," Mammalian Genome, vol. 9, no. 7, pp. 550-555, 1998.
• 14: A.M. Shedlock and N. Okada, "SINE Insertions: Powerful Tools for Molecular Systematics," Bioessays, vol. 22, pp. 148-160, 2000.
• 15: C. Semple and M. Steel, Phylogenetics. Oxford Univ. Press, 2003.
• 16: M. Steel and D. Penny, "Maximum Parsimony and the Phylogenetic Information in Multi-State Characters," Parsimony, Phylogeny and Genomics, V. Albert, ed., pp. 163-178, Oxford Univ. Press, 2005.

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees

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

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms

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

General Terms:
Algorithms, Design, Performance

Keywords:
Combinatorial algorithms, Life and Medical Sciences