Parsimony Score of Phylogenetic Networks: Hardness Results and a Linear-Time Heuristic

ABSTRACT

Phylogenies—the evolutionary histories of groups of organisms—play a major role in representing the interrelationships among biological entities. Many methods for reconstructing and studying such phylogenies have been proposed, almost all of which assume that the underlying history of a given set of species can be represented by a binary tree. Although many biological processes can be effectively modeled and summarized in this fashion, others cannot: recombination, hybrid speciation, and horizontal gene transfer result in networks of relationships rather than trees of relationships. In previous works, we formulated a maximum parsimony (MP) criterion for reconstructing and evaluating phylogenetic networks, and demonstrated its quality on biological as well as synthetic data sets. In this paper, we provide further theoretical results as well as a very fast heuristic algorithm for the MP criterion of phylogenetic networks. In particular, we provide a novel combinatorial definition of phylogenetic networks in terms of “forbidden cycles,” and provide detailed hardness and hardness of approximation proofs for the "small” MP problem. We demonstrate the performance of our heuristic in terms of time and accuracy on both biological and synthetic data sets. Finally, we explain the difference between our model and a similar one formulated by Nguyen et al., and describe the implications of this difference on the hardness and approximation results.

REFERENCES

• 1: V. Bafna and V. Bansal, "Improved Recombination Lower Bounds for Haplotype Data," Proc. Int'l Conf. Computational Molecular Biology (RECOMB '05), pp. 569-584, 2005.
• 2: U. Bergthorsson, K.L. Adams, B. Thomason, and J.D. Palmer, "Widespread Horizontal Transfer of Mitochondrial Genes in Flowering Plants," Nature, vol. 424, pp. 197-201, 2003.
• 3: U. Bergthorsson, A. Richardson, G.J. Young, L. Goertzen, and J.D. Palmer, "Massive Horizontal Transfer of Mitochondrial Genes from Diverse Land Plant Donors to Basal Angiosperm Amborella," Proc. Nat'l Academy of Sciences USA, vol. 101, pp. 17747-17752, 2004.
• 4: J.R. Brown, "Ancient Horizontal Gene Transfer," Nature Rev. Genetics, vol. 4, pp. 121-132, 2003.
• 5: C.F. Delwiche and J.D. Palmer, "Rampant Horizontal Transfer and Duplication of Rubisco Genes in Eubacteria and Plastids," Molecular Biology and Evolution, vol. 13, no. 6, pp. 873-882, 1996.
• 6: W.F. Doolittle, Y. Boucher, C.L. Nesbo, C.J. Douady, J.O. Andersson, and A.J. Roger, "How Big is the Iceberg of Which Organellar Genes in Nuclear Genomes Are but the Tip?" Philosophical Trans. Royal Society B, vol. 358, pp. 39-57, 2003.
• 7: J.A. Eisen, "Assessing Evolutionary Relationships among Microbes from Whole-Genome Analysis," Current Opinion in Microbiology, vol. 3, pp. 475-480, 2000.
• 8: W. Fitch, "Toward Defining the Course of Evolution: Minimum Change for a Specified Tree Topology," Systematic Zoology, vol. 20, pp. 406-416, 1971.
• 9: M.R. Garey, R. Garey, and D.S. Johnson, Computer and Intractability . Bell Lab, 1979.
• 10: Pawel Górecki, Reconciliation problems for duplication, loss and horizontal gene transfer, Proceedings of the eighth annual international conference on Resaerch in computational molecular biology, p.316-325, March 27-31, 2004, San Diego, California, USA [doi>10.1145/974614.974656]
• 11: D. Gusfield and V. Bansal, "A Fundamental Decomposition Theory for Phylogenetic Networks and Incompatible Characters," Proc. Int'l Conf. Computational Molecular Biology (RECOMB '05), pp. 217-232, 2005.
• 12: Mike Hallett , Jens Lagergren , Ali Tofigh, Simultaneous identification of duplications and lateral transfers, Proceedings of the eighth annual international conference on Resaerch in computational molecular biology, p.347-356, March 27-31, 2004, San Diego, California, USA [doi>10.1145/974614.974660]
• 13: Johan Håstad, Some optimal inapproximability results, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.1-10, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258536]
• 14: Dorit S. Hochbaum, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 15: D.H. Huson, T. Klopper, P.J. Lockhart, and M. Steel, "Reconstruction of Reticulate Networks from Gene Trees," Proc. Int'l Conf. Computational Molecular Biology (RECOMB '05), pp. 233-249, 2005.
• 16: T.N.D. Huynh, J. Jansson, N.B. Nguyen, and W.K. Sung, "Constructing a Smallest Refining Galled Phylogenetic Network," Proc. Int'l Conf. Computational Molecular Biology (RECOMB '05), pp. 265-280.
• 17: R. Jain, M.C. Rivera, J.E. Moore, and J.A. Lake, "Horizontal Gene Transfer Accelerates Genome Innovation and Evolution," Molecular Biology and Evolution, vol. 20, no. 10, pp. 1598-1602, 2003.
• 18: Guohua Jin , Luay Nakhleh , Sagi Snir , Tamir Tuller, Efficient parsimony-based methods for phylogenetic network reconstruction, Bioinformatics, v.23 n.2, p.e123-e128, January 2007 [doi>10.1093/bioinformatics/btl313]
• 19: Guohua Jin , Luay Nakhleh , Sagi Snir , Tamir Tuller, Maximum likelihood of phylogenetic networks, Bioinformatics, v.22 n.21, p.2604-2611, October 2006 [doi>10.1093/bioinformatics/btl452]
• 20: G. Jin, L. Nakhleh, S. Snir, and T. Tuller, "Inferring Phylogenetic Networks by the Maximum Parsimony Criterion: A Case Study," Molecular Biology and Evolution, vol. 24, no. 1, pp. 324-337, 2007.
• 21: W.S. Judd and R.G. Olmstead, "A Survey of Tricolpate (Eudicot) Phylogenetic Relationships," Am. J. Botany, vol. 91, pp. 1627-1644, 2004.
• 22: C.G. Kurland, "Something for Everyone-Horizontal Gene Transfer in Evolution," Embo Reports, vol. 1, no. 2, pp. 92-95, 2000.
• 23: J.A. Lake, R. Jain, and M.C. Rivera, "Mix and Match in the Tree of Life," Science, vol. 283, pp. 2027-2028, 1999.
• 24: C.R. Linder, B.M.E. Moret, L. Nakhleh, and T. Warnow, "Network (Reticulate) Evolution: Biology, Models, and Algorithms," Proc. Pacific Symp. Biocomputing, tutorial, 2004.
• 25: C.R. Linder and L.H. Rieseberg, "Reconstructing Patterns of Reticulate Evolution in Plants," Am. J. Botany, vol. 91, pp. 1700- 1708, 2004.
• 26: V. Makarenkov, D. Kevorkov, and P. Legendre, "Phylogenetic Network Reconstruction Approaches," Applied Mycology and Biotechnology (Bioinformatics), vol. 6, 2006.
• 27: O. Matte-Tailliez, C. Brochier, P. Forterre, and H. Philippe, "Archaeal Phylogeny Based on Ribosomal Proteins," Molecular Biology and Evolution, vol. 19, no. 5, pp. 631-639, 2002.
• 28: F.A. Michelangeli, J.I. Davis, and D.Wm. Stevenson, "Phylogenetic Relationships among Poaceae and Related Families as Inferred from Morphology, Inversions in the Plastid Genome, and Sequence Data from Mitochondrial and Plastid Genomes," Am. J. Botany, vol. 90, pp. 93-106, 2003.
• 29: Bernard M. E. Moret , Luay Nakhleh , Tandy Warnow , C. Randal Linder , Anna Tholse , Anneke Padolina , Jerry Sun , Ruth Timme, Phylogenetic Networks: Modeling, Reconstructibility, and Accuracy, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v.1 n.1, p.13-23, January 2004 [doi>10.1109/TCBB.2004.10]
• 30: L. Nakhleh, A. Clement, T. Warnow, C.R. Linder, and B.M.E. Moret, "Quality Measures for Phylogenetic Networks," Technical Report TR-CS-2004-06, Univ. of New Mexico, 2004.
• 31: Luay Nakhleh , Guohua Jin , Fengmei Zhao , John Mellor-Crummey, Reconstructing Phylogenetic Networks Using Maximum Parsimony, Proceedings of the 2005 IEEE Computational Systems Bioinformatics Conference, p.93-102, August 08-11, 2005 [doi>10.1109/CSB.2005.47]
• 32: Luay Nakhleh , Tandy Warnow , C. Randal Linder, Reconstructing reticulate evolution in species: theory and practice, Proceedings of the eighth annual international conference on Resaerch in computational molecular biology, p.337-346, March 27-31, 2004, San Diego, California, USA [doi>10.1145/974614.974659]
• 33: C. Thach Nguyen , Nguyen Bao Nguyen , Wing-Kin Sung , Louxin Zhang, Reconstructing Recombination Network from Sequence Data: The Small Parsimony Problem, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v.4 n.3, p.394-402, July 2007 [doi>10.1109/tcbb.2007.1018]
• 34: C.H. Papadimitriou, Computational Complexity. Addison-Wesley Pub., 1993.
• 35: A. Rambaut and N.C. Grassly, "Seq-Gen: An Application for the Monte Carlo Simulation of DNA Sequence Evolution along Phylogenetic Trees," Computer Applications in Bioscience, vol. 13, 1997.
• 36: M. Sanderson, "r8s Software Package," http://loco.ucdavis.edu/ r8s/r8s.html, 2008.
• 37: D. Sankoff, "Minimal Mutation Trees of Sequences," SIAM J. Applied Math., vol. 28, pp. 35-42, 1975.
• 38: L. Wang, K. Zhang, and L. Zhang, "Perfect Phylogenetic Networks with Recombination," J. Computational Biology, vol. 8, no. 1, pp. 69-78, 2001.
• 39: D. Zwickl and D. Hillis, "Increased Taxon Sampling Greatly Reduces Phylogenetic Error," Systematic Biology, vol. 51, pp. 588- 598, 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
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Time series analysis

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
Maximum parsimony, phylogenetic networks, horizontal gene transfer, hardness and approximation.