<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 10 Issue 1" %>
Accumulation Phylogenies
Mihaela Baroni and Mike Steel
Biomathematics Research Centre, University of Canterbury, Private Bag 4800, Christchurch, New Zealand
mihaela.baroni@ugal.ro, m.steel@math.canterbury.ac.nz
Annals of Combinatorics 10 (1) p.19-30 March, 2006
AMS Subject Classification: 05C05, 05C20, 92D15
Directed acyclic graphs provide a convenient representation of reticulate evolution in systematic biology. In this paper we formalize and analyse a simple model in which evolved characteristics are passed on to all descendant species. We show that the resulting observed sets of characteristics for the species at the leaves uniquely determine the digraph that described the evolution of the species, under certain restrictions. We also provide a characterisation for when this digraph is actually a tree.
Keywords: digraph, tree, reticulate evolution


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

2. M. Baroni, C. Semple, and M. Steel, A framework for representing reticulate evolution, Ann. Comb. 8 (2004) (4) 391-408.

3. S. Böcker and A.W.M. Dress, Recovering symbolically dated, rooted trees from symbolic ultrametrics, Adv. Math. 138 (1998) 105-125.

4. D. Bryant and V. Moulton, NeighborNet: an agglomerative algorithm for the construction of phylogenetic networks, Mol. Biol. Evol. 21 (2) (2004) 255-265.

5. P. Buneman, The recovery of trees from measures of dissimilarity, In: Mathematics in the Archaeological and Historical Sciences, F.R. Hodson, D.G. Kendall, and P. Tautu, Eds., Edinburgh University Press, (1971) pp. 387-395.

6. 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.

7. J. Felsenstein, Inferring Phylogenies, Sinauer Press, 2004.

8. D. Gusfield, S. Eddhu, and C. Langley, The Fine Structure of Galls in Phylogenetic Networks, INFORMS J. Comput. 16 (2004) 459-469.

9. J. Jansson and W.-K. Sung, Inferring a level-1 phylogenetic network from a dense set of rooted triplets, In: Proceedings of the Tenth International Computing and Combinatorics Conference, Springer-Verlag, 2004.

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, Systematic Biol. 51 (2) (2002) 199-216.

12. B.M.E. Moret, L. Nakhleh, T. Warnow, C.R. Linder, A. Tholse, A. Padolina, J. Sun, and R.E. Timme, Phylogenetic networks: modeling, reconstructibility, and accuracy, IEEE/ACM Trans. Comput. Biology Bioinform. 1 (1) (2004) 13-23.

13. L. Nakhleh, J. Sun, T. Warnow, C.R. Linder, B.M.E. Moret, and A. Tholse, Towards the development of computational tools for evaluating phylogenetic network reconstruction methods, In: Proceedings of the Eighth Pacific Symposium on Biocomputing, (2003) pp. 315-326.

14. L. Nakhleh, T. Warnow, and C.R. Linder, Reconstructing reticulate evolution in species—theory and practice, In: Proceedings of the Eighth Annual International Conference on Research in Computational Molecular Biology, (2004) pp. 337-346.

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

16. B. Snel, P. Bork, and M.A. Huynen, Genome phylogeny based on gene content, Nat. Genet. 21 (1999) 108-110.