Jahn Katharina, Beerenwinkel Niko, Zhang Louxin
Department of Biosystems Science and Engineering, ETH Zurich, Basel, Switzerland.
SIB Swiss Institute of Bioinformatics, Basel, Switzerland.
Algorithms Mol Biol. 2021 Jun 10;16(1):9. doi: 10.1186/s13015-021-00188-3.
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.
突变树是有根树，其中节点具有任意度数，并标记有一个突变集。这些树，也称为克隆树，在计算肿瘤学中用于表示肿瘤的突变历史。诸如流行的罗宾逊 - 福尔兹距离等经典树度量在比较突变树时用途有限。一个原因是，用不同方法推断或针对不同患者的突变树通常包含不同的突变标签集。
我们将罗宾逊 - 福尔兹距离推广为一组称为布尔克距离的距离度量，用于比较突变树。我们表明，突变树的布尔克距离基本版本可以在线性时间内计算。我们还建立了罗宾逊 - 福尔兹距离与最近邻交换距离之间的联系。
