Comparing and Aggregating Partially Resolved Trees
Authors:
- Mukul S. BansalMBMukul S. Bansal
- Jianrong DongJDJianrong Dong
- David Fernández-BacaDFDavid Fernández-Baca
Preprint
Abstract
We define, analyze, and give efficient algorithms for two kinds of distance measures for rooted and unrooted phylogenies. For rooted trees, our measures are based on the topologies the input trees induce on triplets; that is, on three-element subsets of the set of species. For unrooted trees, the measures are based on quartets (four-element subsets). Triplet and quartet-based distances provide a robust and fine-grained measure of the similarities between trees. The distinguishing feature of our distance measures relative to traditional quartet and triplet distances is their ability to deal cleanly with the presence of unresolved nodes, also called polytomies. For rooted trees, these are nodes with more than two children; for unrooted trees, they are nodes of degree greater than three. Our first class of measures are parametric distances, where there is a parameter that weighs the difference between an unresolved triplet/quartet topology and a resolved one. Our second class of measures are based on Hausdorff distance. Each tree is viewed as a set of all possible ways in which the tree could be refined to eliminate unresolved nodes. The distance between the original (unresolved) trees is then taken to be the Hausdorff distance between the associated sets of fully resolved trees, where the distance between trees in the sets is the triplet or quartet distance, as appropriate.Keywords
All Related Versions
This publication has 17 references indexed in Scilit:
- Using Max Cut to Enhance Rooted Trees ConsistencyIEEE/ACM Transactions on Computational Biology and Bioinformatics, 2006
- Discriminating Supported and Unsupported Relationships in Supertrees Using TripletsSystematic Biology, 2006
- A classification of consensus methods for phylogenetics2003
- Statistically based postprocessing of phylogenetic analysis by clusteringBioinformatics, 2002
- Subtree Transfer Operations and Their Induced Metrics on Evolutionary TreesAnnals of Combinatorics, 2001
- Distributions on bicoloured evolutionary treesBulletin of the Australian Mathematical Society, 1990
- Voting schemes for which it can be difficult to tell who won the electionSocial Choice and Welfare, 1989
- The median procedure for n-treesJournal of Classification, 1986
- N-trees as nestings: Complexity, similarity, and consensusJournal of Classification, 1986
- Obtaining common pruned treesJournal of Classification, 1985