Abstract：
Due to uncertainty in tumor phylogeny inference from sequencing data, many methods infer multiple, equally plausible phylogenies for the same cancer. To summarize the solution space T of tumor phylogenies, consensus tree methods seek a single best representative tree S under a specified pairwise tree distance function. One such distance function is the ancestor-descendant (AD) distance [Formula: see text] , which equals the size of the symmetric difference of the transitive closures of the edge sets [Formula: see text] and [Formula: see text] . Here, we show that finding a consensus tree S for tumor phylogenies T that minimizes the total AD distance [Formula: see text] is NP-hard.
摘要：
由于测序数据中肿瘤系统发育推断的不确定性，许多方法推断多个，同一种癌症的系统发育同样合理。总结肿瘤系统发育的解空间T，共识树方法在指定的成对树距离函数下寻求单个最佳代表树S。一个这样的距离函数是祖先-后代(AD)距离[公式：见文本]，等于边集的传递闭包的对称差的大小[公式：见文本]和[公式：见文本]。这里,我们表明，找到了肿瘤系统发育T的共识树S，该共识树S使总AD距离∑TεTd（S，T）是NP难的。
