Comparing Trees with Pendant Vertices Labelled

From MaRDI portal





Phylogenetic trees are used to represent (hypothesised) ancestral relationships among taxa. Usually these trees are obtained by the analysis of protein sequence data, they may be binary or not. In this paper a difference measure for phylogenetic trees is investigated in order to compare two trees arising from conflicting evolutionary hypothesises. A phylogenetic tree T with labelled pendant vertices is a tree with endpoints (vertices of degree 1) labelled by 0,1,...,n. If T is directed by designating vertex 0 as the root of the tree, for each edge e the content c(e) is defined as the set of all labels of vertices beyond e; furthermore, the content c(T) of the tree T is \(c(T)=\{c(e)| e\in E\}\) where E is the edge set of T. Now the difference between two trees \(T_ 1\) and \(T_ 2\) with labelled pendant vertices \(\{\) 0,1,...,n\(\}\) is defined as \(d(T_ 1,T_ 2)=| c(T_ 1)\Delta c(T_ 2)|,\) i.e. the number of elements in the symmetric difference of their contents. With the use of certain generating polynomials for trees, probability distributions for tree differences are obtained. Explicit results are stated for arbitrary phylogenetic trees with up to 12 labels and binary trees with up to 16 labels. A connection with this problem and a combinatorial problem, Touchard's problem of single systems, is pointed out.











This page was built for publication: Comparing Trees with Pendant Vertices Labelled

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3221788)