A Generalized Robinson-Foulds Distance for Clonal Trees, Mutation Trees, and Phylogenetic Trees and Networks
Authors:
Open Access
- 21 September 2020
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 1-10
Abstract
Cancer evolution is often modeled by clonal trees (whose nodes are labeled by multiple somatic mutations) or mutation trees (where nodes are labeled by single somatic mutations). Clonal trees are generated from sequence data with different computational methods that may produce different clone phylogenies, rendering their analysis and comparison necessary to infer mutation order and clone origin during tumor progression. In this paper, we present a distance metric for multi-labeled trees that generalizes the Robinson-Foulds distance for phylogenetic trees, allows for a similarity assessment at much higher resolution, and can be applied to trees and networks with different sets of node labels. The generalized Robinson-Foulds distance can be computed in time quadratic in the size of the input multisets of multisets of node labels, and is a metric for clonal trees, mutation trees, phylogenetic trees, and several classes of phylogenetic networks.Keywords
This publication has 40 references indexed in Scilit:
- Faster computation of the Robinson–Foulds distance between phylogenetic networksInformation Sciences, 2012
- The infinite sites model of genome evolutionProceedings of the National Academy of Sciences, 2008
- Many different tumor types have polyclonal tumor origin: Evidence and implicationsMutation Research - Reviews in Mutation Research, 2008
- A distance metric for a class of tree-sibling phylogenetic networksBioinformatics, 2008
- Tripartitions do not always discriminate phylogenetic networksMathematical Biosciences, 2008
- Efficiently Computing the Robinson-Foulds MetricJournal of Computational Biology, 2007
- Efficient algorithms for inferring evolutionary treesNetworks, 1991
- Optimal algorithms for comparing trees with labeled leavesJournal of Classification, 1985
- Comparison of phylogenetic treesMathematical Biosciences, 1981
- Distance between SetsNature, 1971