Generating functions for multi-labeled trees

Multi-labeled trees are a generalization of phylogenetic trees that are used, for example, in the study of gene versus species evolution and as the basis for phylogenetic network construction. Unlike phylogenetic trees, in a leaf-multi-labeled tree it is possible to label more than one leaf by the s...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2013-01, Vol.161 (1-2), p.107-117
Main Authors: Czabarka, É., Erdős, P.L., Johnson, V., Moulton, V.
Format: Article
Language:English
Subjects:
Counting
Evolution
Functions (mathematics)
Generating function
Genes
Labels
Mathematical analysis
MUL-tree
Multi-labeled tree
Otters
Phylogenetic tree
Trees
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Multi-labeled trees are a generalization of phylogenetic trees that are used, for example, in the study of gene versus species evolution and as the basis for phylogenetic network construction. Unlike phylogenetic trees, in a leaf-multi-labeled tree it is possible to label more than one leaf by the same element of the underlying label set. In this paper we derive formulae for generating functions of leaf-multi-labeled trees and use these to derive recursions for counting such trees. In particular, we prove results which generalize previous theorems by Harding on so-called tree-shapes, and by Otter on relating the number of rooted and unrooted phylogenetic trees.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2012.08.010