Comparing Trees with Pendant Vertices Labelled
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.
- Optimal algorithms for comparing trees with labeled leaves
- Enumerating phylogenetic trees with multiple labels
- An optimal algorithm to reconstruct trees from additive distance data
- Significance of the length of the shortest tree
- The expected value of the squared cophenetic metric under the Yule and the uniform models
- scientific article; zbMATH DE number 3859156 (Why is no real title available?)
- scientific article; zbMATH DE number 3891391 (Why is no real title available?)
- scientific article; zbMATH DE number 4065020 (Why is no real title available?)
- Counting Phylogenetic Networks with Few Reticulation Vertices: Exact Enumeration and Corrections
- Neighborhoods of phylogenetic trees: exact and asymptotic counts
- Reconstructing evolution of sequences subject to recombination using parsimony
- On the variational distance of two trees
- The mean value of the squared path-difference distance for rooted phylogenetic trees
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)