IJPAM: Volume 117, No. 1 (2017)

Title

NON-RECURSIVE ENUMERATION
OF HETEROCHRONOUS TREES

Authors

Paul F. Slade
Computational Biology and Bioinformatics Unit
Research School of Biology
R.N. Robertson Building - 46
Australian National University
ACT 0200, AUSTRALIA

Abstract

The enumeration formula of a non-contemporaneous genealogy with total sample size n=n1+n2 requires a nested sum-product. The set of ancestral patterns in the non-contemporaneous genealogy yields a multiplicity factor that translates from the set of ancestral patterns in the isochronous genealogy. A computation formula of the multiplicity factor proves to be non-recursive. Evaluation of small sample sizes demonstrates the emergent complexity. Extension to the enumeration formula in the heterochronous genealogy with m samples of total size n=n1+...+nm yields a non-recursive nested sum-product. These enumeration formulae measure sample spaces of Bayesian prior distributions of trees relevant to theoretical and computational phylogenetics.

History

Received: 2017-10-18
Revised: 2017-11-13
Published: December 12, 2017
Revisions: January 20, 2018: On author request. Download the original published file from here.

AMS Classification, Key Words

AMS Subject Classification: 05C05, 05C30, 68R10, 92D15
Key Words and Phrases: bifurcation, genealogy, nested sum-product, non-contemporaneous samples

Download Section

Download paper from here.
You will need Adobe Acrobat reader. For more information and free download of the reader, see the Adobe Acrobat website.

Bibliography

1
J. Wakeley, Coalescent Theory: an introduction, Roberts and Company Publishers, Greenwood Village, 2009.

2
J. Hein, M.H. Schierup and C. Wiuf, Gene Genealogies, Variation and Evolution: a primer in coalescent theory, Oxford University Press, Oxford, 2005.

3
S. Tavaré, Ancestral inference in population genetics, In: Ecole d'Eté de Probabilités de Saint Flour XXX1 - 2001 (Ed J. Picard), Lectures on Probability Theory and Statistics, 1837, Springer-Verlag, Berlin, 2004, 1-188.

4
A. Gavryushkina, T.A. Heath, D.T. Ksepka, T. Stadler, D. Welch and A.J. Drummond, Bayesian total-evidence dating reveals the recent crown radiation of penguins, Syst. Biol., 66 (1) (2017), 57-73, doi: https://doi.org/10.1093/sysbio/syw060.

5
K. Dialdestro, J.A. Sibbesen, L. Maretty, J. Raghwani, A. Gall, et al.,Coalescent inference using serially-sampled, high-throughput sequencing data from intra-host HIV infection, Genetics, 202 (2016), 1449-1472, doi: https://doi.org/10.1534/genetics.115.177931/-/DC1.

6
A.J. Drummond and T. Stadler, Bayesian phylogenetic estimation of fossil ages, Phil. Trans. R. Soc. B 371 (2016), 20150129, doi: https://doi.org/10.1098/rstb.2015.0129.

7
S. Duchêne, D. Duchêne, E.C. Holmes and S.Y.W. Ho, The performance of the date-randomization test in phylogenetic analyses of time-structured virus data, Mol. Biol. Evol., 32 (7) (2015), 1895-1906, doi: https://doi.org/10.1093/molbev/msv056.

8
J. Heled and A.J. Drummond, Calibrated birth-death phylogenetics time-tree priors for Bayesian inference, Syst. Biol., 64 (3) (2015), 369-383, doi: https://doi.org/10.1093/sysbio/syu089.

9
A. Gavryushkina, D. Welch, T. Stadler and A.J. Drummond, Bayesian inference of sampled ancestor trees for epidemiology and fossil calibration, PLoS Comput. Biol., 10 (12) (2014), e1003919, doi: https://doi.org/10.1371/journal.pcbi.1003919.

10
R.D. Wilkinson, M.E. Steiper, C. Soligo, R.D. Martin, Z. Yang and S. Tavaré, Dating primate divergences through an integrated analysis of palaeontological and molecular data, Syst. Biol., 60 (1) (2011), 16-31, doi: https://doi.org/10.1093/sysbio/syq054.

11
J. Wakeley, Coalescent theory has many new branches, Theor. Popul. Biol., 87 (2013), 1-4, doi: https://doi.org/10.1016/j.tpb.2013.06.001.

12
M. Steel, Phylogeny: discrete and random processes in evolution, CBMS-NSF Regional Conference Series in Applied Mathematics 89, SIAM, Philadelphia, 2016.

13
A. Lambert and T. Stadler, Birth-death models and coalescent point processes: the shape and probability of reconstructed phylogenies, Theor. Popul. Biol., 90 (2013), 113-128, doi: https://doi.org/10.1016/j.tpb.2013.10.002.

14
C.J. Burden and H. Simon, Genetic drift in populations governed by a Galton-Watson branching process, Theor. Popul. Biol., 109 (2016), 63-74, doi: https://doi.org/10.1016/j.tpb.2016.03.002.

15
A.G. Rodrigo and J. Felsenstein, Coalescent approaches to HIV-1 population genetics, In: The Evolution of HIV (Ed K.A. Crandall), Johns Hopkins University Press, Baltimore, 1999, 233-272.

16
A.J. Drummond, O.G. Pybus, A. Rambaut, R. Forsberg and A.G. Rodrigo, Measurably evolving populations, Trends Ecol. Evol., 18 (9) (2003), 481-488, doi: https://doi.org/10.1016/S0169-5347(03)00216-7.

17
A.J. Drummond, G.K. Nicholls, A.G. Rodrigo and W. Solomon, Genealogies from time-stamped sequence data, In: Tools for Constructing Chronologies Crossing Disciplinary Boundaries (Ed-s C.E. Buck and A. Millard), Lecture Notes in Statistics, Springer-Verlag, New York, 2004, 149-171.

18
A.G. Rodrigo, G. Ewing and A.J. Drummond, The evolutionary analysis of measurably evolving populations using serially sampled gene sequences, In: Reconstructing Evolution: new mathematical and computational advances (Ed-s O. Gascuel and M. Steel), Oxford University Press, Oxford, 2007, 30-61.

19
A. Gavryushkina, D. Welch and A. J. Drummond, Recursive algorithms for phylogenetic tree counting, Algorithms Mol. Biol., 8 (2013), 26-38, doi: https://doi.org/10.1186/1748-7188-8-26.

20
A.J. Drummond and T Stadler, Evolutionary trees, In: Bayesian Evolutionary Analysis with BEAST (A.J. Drummond and R.R. Bouckaert)     Cambridge University Press, Cambridge, 2015, 21-43.

21
A.J. Drummond, R. Bouckaert and W. Xie, Measurably evolving populations, Online documentation for BEAST version 2.2,2015. (http://beast2.org/tutorials/)

22
R. Bouckaert, J. Heled, D. Kühnert, T. Vaughan, C-H Wu, et al.,BEAST 2: a software platform for Bayesian evolutionary analysis, PLoS Comput. Biol., 10 (4) (2014), e1003537, doi: https://doi.org/10.1371/journal.pcbi.1003537.

23
A.J. Drummond, M.A. Suchard, D. Xie and A. Rambaut, Bayesian phylogenetics with BEAUti and the BEAST 1.7, Mol. Biol. Evol. 29 (8) (2012), 1969-1973, doi: https://doi.org/10.1093/molbev/mss075.

24
C.N.K. Anderson, U. Ramakrishnan, Y.L. Chan and E.A. Hadley, Serial SimCoal: a population genetics model for data from multiple populations and points in time, Bioinformatics, 21 (8) (2005), 1733-1734, doi: https://doi.org/10.1093/bioinformatics/bti154.

25
A. Gavryushkin and A.J. Drummond, The space of ultrametric phylogenetic trees, J. Theor. Biol., 403 (2016), 197-208, doi: https://doi.org/10.1016/j.jtbi.2016.05.001.

26
L. Cavalli-Sforza and A.W.F. Edwards, Phylogenetic analysis: models and estimation procedures, Evolution, 21 (3) (1967), 550-570, doi: https://doi.org/10.1111/j.1558-5646.1967.tb03411.x.

How to Cite?

DOI: 10.12732/ijpam.v117i1.17 How to cite this paper?

Source: International Journal of Pure and Applied Mathematics
ISSN printed version: 1311-8080
ISSN on-line version: 1314-3395
Year: 2017
Volume: 117
Issue: 1
Pages: 235 - 246


Google Scholar; DOI (International DOI Foundation); WorldCAT.

CC BY This work is licensed under the Creative Commons Attribution International License (CC BY).