On the number of vertices of each rank in phylogenetic trees and their generalizations

Preprint English OPEN
Bóna, Miklós;
(2015)
  • Subject: Mathematics - Combinatorics | 05A15, 05A16
    arxiv: Quantitative Biology::Genomics | Quantitative Biology::Quantitative Methods | Quantitative Biology::Populations and Evolution
    acm: ComputingMethodologies_PATTERNRECOGNITION | MathematicsofComputing_DISCRETEMATHEMATICS | TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY

We find surprisingly simple formulas for the limiting probability that the rank of a randomly selected vertex in a randomly selected phylogenetic tree or generalized phylogenetic tree is a given integer.
  • References (20)
    20 references, page 1 of 2

    [1] D. Aldous. Asymptotic fringe distributions for general families of random trees. Ann. Appl. Probab., 1(2):228-266, 1991.

    [2] M. Bo´ na. k-protected vertices in binary search trees. Adv. Appl. Math., 53:1-11, 2014.

    [3] M. Bo´ na and P. Flajolet. Isomorphism and symmetries in random phylogenetic trees. J. Appl. Probab., 46(4).

    [4] M. Bo´ na and B. Pittel. On a random search tree: asymptotic enumeration of vertices by distance from leaves, 2014.

    [5] G.-S. Cheon and L. W. Shapiro. Protected points in ordered trees. Appl. Math. Lett., 21:516-520, 2008.

    [6] L. Devroye. A note on the height of binary search trees. .Assoc. Comput. Mach., pages 489-498, 1986.

    [7] L. Devroye and S. Janson. Protected nodes and fringe subtrees in some random trees. Electron. Commun. Probab, 19(6):10 pages, 2014.

    [8] R. R. Du and H. Prodinger. Notes on protected nodes in digital search trees. Appl. Math. Lett., 25:1025-1028, 2012.

    [9] P. Flajolet and R. Sedgewick. Analytic Combinatorics. CUP, 2009.

    [10] S. Janson and C. Holmgren. Asymptotic distribution of two-protected nodes in ternary search trees. Electron. J. Probab, 20(9):20 pages, 2015.

  • Related Organizations (2)
  • Metrics
Share - Bookmark