Hybridization in Nonbinary Trees

ABSTRACT

Reticulate evolution—the umbrella term for processes like hybridization, horizontal gene transfer, and recombination—plays an important role in the history of life of many species. Although the occurrence of such events is widely accepted, approaches to calculate the extent to which reticulation has influenced evolution are relatively rare. In this paper, we show that the NP-hard problem of calculating the minimum number of reticulation events for two (arbitrary) rooted phylogenetic trees parameterized by this minimum number is fixed-parameter tractable.

REFERENCES

• 1: M. Baroni, S. Grünewald, V. Moulton, and C. Semple, "Bounding the Number of Hybridisation Events for a Consistent Evolutionary History," J. Math. Biology, vol. 51, pp. 171-182, 2005.
• 2: M. Baroni, C. Semple, and M. Steel, "Hybrids in Real Time," Systematic Biology, vol. 55, pp. 46-56, 2006.
• 3: M. Bordewich and C. Semple, "On the Computational Complexity of the Rooted Subtree Prune and Regraft Distance," Annals of Combinatorics, vol. 8, pp. 409-423, 2004.
• 4: Magnus Bordewich , Charles Semple, Computing the minimum number of hybridization events for a consistent evolutionary history, Discrete Applied Mathematics, v.155 n.8, p.914-928, April, 2007 [doi>10.1016/j.dam.2006.08.008]
• 5: Magnus Bordewich , Charles Semple, Computing the Hybridization Number of Two Phylogenetic Trees Is Fixed-Parameter Tractable, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v.4 n.3, p.458-466, July 2007 [doi>10.1109/tcbb.2007.1019]
• 6: R. Downey and M. Fellows, Parameterized Complexity. Springer, 1998.
• 7: J. Fehrer, B. Gemeinholzer, J. Chrtek Jr., and S. Bräutigam, "Incongruent Plastid and Nuclear DNA Phylogenies Reveal Ancient Intergeneric Hybridization in Pilosella Hawkweeds (Hieracium, Cichorieae, Asteraceae)," Molecular Phylogenetics and Evolution, vol. 42, pp. 347-361, 2007.
• 8: R.G. Harrison, "Hybrids and Hybrid Zones: Historical Perspectives," Hybrid Zones and the Evolutionary Process. Oxford Univ. Press, 1993.
• 9: S. Linz, "Reticulation in Evolution," PhD thesis, Heinrich-Heine Univ., 2008.
• 10: W.P. Maddison, "Reconstructing Character Evolution on Polytomous Cladograms," Cladistics, vol. 5, pp. 365-377, 1989.
• 11: J. Mallet, "Hybridization as an Invasion of the Genome," Trends in Ecology and Evolution, vol. 20, pp. 229-237, 2005.
• 12: O. Paun, C. Lehnebach, J.T. Johansson, P. Lockhart, and E. Hörandl, "Phylogenetic Relationships and Biogeography of Ranunculus and Allied Genera (Ranunculaceae) in the Mediterranean Region and in the European Alpine System," Taxon, vol. 59, pp. 911-930, 2005.
• 13: C. Semple and M. Steel, Phylogenetics. Oxford Univ. Press, 2003.
• 14: Y. Song and J. Hein, "Parsimonious Reconstruction of Sequence Evolution and Haplotype Blocks: Finding the Minimum Number of Recombination Events," Proc. Third Int'l Workshop Algorithms in Bioinformatics (WABI '03), vol. 2812, pp. 287-302, 2003.
• 15: Y. Song and J. Hein, "Constructing Minimal Ancestral Recombination Graphs," J. Computational Biology, vol. 12, pp. 147-169, 2005.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

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

General Terms:
Design, Performance

Keywords:
Combinatorial algorithms, Network problems