<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume8 Issue4" %>
A Framework for Representing Reticulate Evolution
Mihaela Baroni1, Charles Semple2, and Mike Steel3
Biomathematics Research Centre, Department of Mathematics and Statistics, University of Canterbury, Christchurch, New Zealand
mbaroni@ugal.ro, {c.semple, m.steel}@math.canterbury.ac.nz
Annals of Combinatorics 8 (4) p.391-408 December, 2004
AMS Subject Classification: 05C05, 92D15
Acyclic directed graphs (ADGs) are increasingly being viewed as more appropriate for representing certain evolutionary relationships, particularly in biology, than rooted trees. In this paper, we develop a framework for the analysis of these graphs which we call hybrid phylogenies. We are particularly interested in the problem whereby one is given a set of phylogenetic trees and wishes to determine a hybrid phylogeny that `embeds' each of these trees and which requires the smallest number of hybridisation events. We show that this quantity can be greatly reduced if additional species are involved, and investigate other combinatorial aspects of this and related questions.
Keywords: directed acyclic graph, reticulate evolution, hybrid species, subtree prune and regraft


1. B.L. Allen and M. Steel, Subtree transfer operations and their induced metrics on evolutionary trees, Ann. Comb. 5 (2001) 1--13.

2. H.-J. Bandelt and A.W.M. Dress, Weak hierarchies associated with similarity measures - an additive clustering technique, Bull. Math. Biol. 51 (1989) 133--166.

3. J.B. -Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications, Springer-Verlag, London, 2001.

4. K. Bremer and H.-E.Wanntorp, Hierarchy and reticulation in systematics, Syst. Zool. 28 (4) (1979) 624--627.

5. E. Diday and P. Bertrand, An extension of hierarchical clustering: the pyramidal presentation,In: Pattern Recognition in Practice II, E.S. Gelsema and L.N. Kanal, Eds., North- Holland, Amsterdam, 1986, pp. 411--423.

6. W.F. Doolittle, Phylogenetic classification and the universal tree, Science 284 (1999) 2124--2128.

7. A.W.M. Dress, D. Huson, and V. Moulton, Analysing and visualizing sequence and distance data using SPLITSTREE, Discrete Appl. Math. 71 (1996) 95--109.

8. V.A. Funk, Phylogenetic patterns and hybridization, Ann. Missouri Bot. Gand. 72 (1985) 681--715.

9. F.-J. Lapointe, How to account for reticulation events in phylogenetic analysis: a comparison of distance-based methods, J. Classification 17 (2000) 175--184.

10. P. Legendre, Biological applications of reticulate analysis, J. Classification 17 (2000) 191--195.

11. P. Legendre and V. Makarenkov, Reconstruction of biogeographic and evolutionary networks using reticulograms, Syst. Biol. 51 (2) (2002), 199--216.

12. M. Li, J. Tromp, and L. Zhang, On the nearest neighbour interchange distance between evolutionary trees, Journal of Theoretical Biology 182 (1996) 463--467.

13. G. Nelson, Reticulation in cladograms, In: Advances in Cladistics, vol. 2, N.I. Platnick and V.A. Funk, Eds., Columbia University Press, 1983, pp. 105--111.

14. D.F. Robinson and L.R. Foulds, Comparison of phylogenetic trees, Math. Biosci. 53 (1981) 131--147.

15. F.J. Rohlf, Phylogenetic models and reticulations, J. Classification 17 (2000) 185--189.

16. C. Semple and M. Steel, Phylogenetics, Oxford University Press, 2003.

17. P.E. Smouse, Reticulation inside the species boundary, J. Classification 17 (2000) 165--173.

18. P.H.A. Sneath, Reticulate evolution in bacteria and other organisms: how can we study it?, J. Classification 17 (2000) 159--163.

19. H.-E.Wanntorp, Reticulated cladograms and the identification of hybrid taxa, In: Advances in Cladistics, vol. 2, N.I. Platnick and V.A. Funk, Eds., Columbia University Press, 1983, pp. 81--88.