A Multi-labeled Tree Edit Distance for Comparing "Clonal Trees" of Tumor Progression
A Multi-labeled Tree Edit Distance for Comparing "Clonal Trees" of Tumor Progression
复制标题
用于比较肿瘤进展的“克隆树”的多标记树编辑距离
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
S. C. Sahinalp
中科院分区：
文献类型：
--
作者：
Nikolai Karpov;S. Malikić;Md. Khaledur Rahman;S. C. Sahinalp
我们引入了一个新的编辑距离测量之间的一对“克隆树”，每个代表的进展和突变异质性的肿瘤样本，通过使用单细胞或批量高通量测序数据构建。在克隆树中，每个顶点代表一个特定的肿瘤克隆，并且以每个突变被分配给包含它的最老克隆的方式标记有一个或多个突变。给定两个克隆树，我们的多标记树编辑距离（MLTED）度量被定义为以任何顺序应用的突变/标签删除、（空）叶删除和顶点（克隆）扩展的最小数量，将两棵树中的每一棵树转换为最大公共树。我们表明，MLTED措施可以有效地计算在多项式时间，它捕捉不同克隆粒度的树之间的相似性。我们已经实现了我们的算法来计算MLTED准确，并成功地将其应用到各种数据集。我们的方法的源代码可以在https://github.com/khaled-rahman/leafDelTED中找到。
We introduce a new edit distance 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 edit distance (MLTED) 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 maximal common tree. We show that the MLTED measure can be computed efficiently in polynomial time and it captures the similarity between trees of different clonal granularity well. We have implemented our algorithm to compute MLTED exactly and applied it to a variety of data sets successfully. The source code of our method can be found in: https://github.com/khaled-rahman/leafDelTED.