Karpov Nikolai, Malikic Salem, Rahman Md Khaledur, Sahinalp S Cenk
1Department of Computer Science, Indiana University, Bloomington, IN USA.
2School of Computing Science, Simon Fraser University, Burnaby, BC Canada.
Algorithms Mol Biol. 2019 Jul 27;14:17. doi: 10.1186/s13015-019-0152-9. eCollection 2019.
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.
我们引入了一种新的成对“克隆树”之间的差异度量方法，每棵克隆树都代表一个肿瘤样本的进展和突变异质性，通过使用单细胞或批量高通量测序数据构建而成。在一棵克隆树中，每个顶点代表一个特定的肿瘤克隆，并以这样的方式标记一个或多个突变：每个突变都被分配到包含它的最古老的克隆上。给定两棵克隆树，我们的多标签树差异（MLTD）度量被定义为以任意顺序应用的突变/标签删除、（空）叶删除和顶点（克隆）扩展的最小数量，以便将两棵树中的每一棵都转换为最大公共树。我们表明，MLTD度量可以在多项式时间内有效地计算出来，并且它能很好地捕捉不同克隆粒度的树之间的相似性。
