The Bourque distances for mutation trees of cancers
Open Access
- 10 June 2021
- journal article
- research article
- Published by Springer Science and Business Media LLC in Algorithms for Molecular Biology
- Vol. 16 (1), 1-15
- https://doi.org/10.1186/s13015-021-00188-3
Abstract
Mutation trees are rooted trees in which nodes are of arbitrary degree and labeled with a mutation set. These trees, also referred to as clonal trees, are used in computational oncology to represent the mutational history of tumours. Classical tree metrics such as the popular Robinson–Foulds distance are of limited use for the comparison of mutation trees. One reason is that mutation trees inferred with different methods or for different patients often contain different sets of mutation labels. We generalize the Robinson–Foulds distance into a set of distance metrics called Bourque distances for comparing mutation trees. We show the basic version of the Bourque distance for mutation trees can be computed in linear time. We also make a connection between the Robinson–Foulds distance and the nearest neighbor interchange distance.Keywords
Funding Information
- Ministry of Education - Singapore
This publication has 39 references indexed in Scilit:
- Twist–Rotation Transformations of Binary Trees and Arithmetic ExpressionsJournal of Algorithms, 1999
- Gene Trees in Species TreesSystematic Biology, 1997
- On the Nearest Neighbour Interchange Distance Between Evolutionary TreesJournal of Theoretical Biology, 1996
- Comparing multiple RNA secondary structures using tree comparisonsBioinformatics, 1990
- Tree graphs of RNA secondary structures and their comparisonsComputers and Biomedical Research, 1989
- Optimal algorithms for comparing trees with labeled leavesJournal of Classification, 1985
- Accuracy of estimated phylogenetic trees from molecular dataJournal of Molecular Evolution, 1982
- The Clonal Evolution of Tumor Cell PopulationsScience, 1976
- An iterative approach from the standpoint of the additive hypothesis to the dendrogram problem posed by molecular data setsJournal of Theoretical Biology, 1973
- ON THE COMPARISON OF TWO CLASSIFICATIONS OF THE SAME SET OF ELEMENTSTaxon, 1971