A Multi-Labeled Tree Dissimilarity Measure for Comparing “Clonal Trees” of Tumor Progression

Peer reviewed: 
Yes, item is peer reviewed.
Scholarly level: 
Graduate student (Masters)
Final version published as: 

Karpov N, Malikic S, Rahman MK, Sahinalp SC. A multi-labeled tree dissimilarity measure for comparing "clonal trees" of tumor progression. Algorithms Mol Biol. 2019;14:17. Published 2019 Jul 27. doi:10.1186/s13015-019-0152-9. DOI: 10.1186/s13015-019-0152-9.

Date created: 
Intra-tumor heterogeneity
Tumor evolution
Multi-labeled tree
Tree edit distance
Dynamic programming

We introduce a new dissimilarity measure between a pair of “clonal trees”, each representing the progression and mutational heterogeneity of a tumor sample, constructed by the use of single cell or bulk high throughput sequencing data. In a clonal tree, each vertex represents a specific tumor clone, and is labeled with one or more mutations in a way that each mutation is assigned to the oldest clone that harbors it. Given two clonal trees, our multi-labeled tree dissimilarity (MLTD) measure is defined as the minimum number of mutation/label deletions, (empty) leaf deletions, and vertex (clonal) expansions, applied in any order, to convert each of the two trees to the maximum common tree. We show that the MLTD measure can be computed efficiently in polynomial time and it captures the similarity between trees of different clonal granularity well.

Document type: