<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 12 Issue 1" %>
Counting Ancestral Reconstructions in a Fixed Phylogeny
Tobias Thierer1, David Bryant2,3, and Mike Steel4
1Proteomics Algorithmen und Simulation, ZBIT, Sand 14, 72076 Tübingen, Germany
2Department of Mathematics, University of Auckland, Private Bag 92019, Auckland Mail Centre, Auckland 1142, New Zealand
3McGill Centre for Bioinformatics, 3775 University Street, Montreal, Quebec, H3A 2B4, Canada
4Biomathematics Research Centre, University of Canterbury, Private Bag 4800, Christchurch 8140, New Zealand
Annals of Combinatorics 12 (1) p.123-132 March, 2008
AMS Subject Classification:92B05, 92B15, 05C05, 11T06
We give formulas for calculating in polynomial time the number of ancestral reconstructions for a tree with binary leaf- and root labels for each number of 0→1 and 1→0 arcs. For trees of fixed degree, the corresponding numbers of 0 →0 and 1→1 arcs can be deduced. We calculate intervals for the relative cost of 0→1 and 1→0 transitions over which the same labelings remain the cheapest.
Keywords: generating function, phylogenetic tree, binary character, transition


1. V.S. Alagar and D.K. Probst, A fast, low-space algorithm for multiplying dense multivariate polynomials, ACM Trans. Math. Software 13 (1) (1987) 35-57.

2. T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein, Introduction to Algorithms, 2nd Ed., MIT Press, Cambridge, 2001.

3. M.E. Cosner, R.K. Jansen, B.M.E. Moret, L.A. Raubeson, L.S. Wang, T. Warnow, and S.K. Wyman, An empirical comparison of phylogenetic methods on chloroplast gene order data in Campanulaceae, In: Comparative Genomics: Empirical and Analytical Approaches to Gene Order Dynamics, Map Alignment, and the Evolution of Gene Families, D. Sankoff and J. Nadeau, Eds., Kluwer Academic Publishers, Dordrecht (2000) pp. 99-121.

4. J.S. Farris, Phylogenetic analysis under Dollo's law, Syst. Zool. 26 (1) (1977) 77-88.

5. J. Felsenstein, Inferring Phylogenies, Sinauer Associates Inc., Massachusetts, 2004.

6. D.S. Hochbaum and A. Pathria, Path costs in evolutionary tree reconstruction, J. Comput. Biol. 4 (2) (1997) 163-176.

7. W.J. Le Quesne, The uniquely evolved character concept and its cladistic application, Syst. Zool. 23 (1974) 513-517.

8. I. Rinsma, M. Hendy, and D. Penny, Minimally colored trees. Math. Biosci. 98 (1990) 201- 210.

9. A.M. Shedlock and N. Okada, SINE insertions: powerful tools for molecular systematics, Bioessays 22 (2000) 148-160.

10. T. Thierer, Generalised and directed characters in phylogenetics, Master's thesis, University of Canterbury, 2004, http://www.tobias-thierer.de/mscthesis/.