Consensus Tree Under the Ancestor–Descendant Distance is NP-Hard

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 d(T‚ T⁰), which equals the size of the symmetric difference of the transitive closures of the edge sets E(T) and E(T⁰). Here, we show that finding a consensus tree S for tumor phylogenies T that minimizes the total AD distance +_T∈T d(S‚ T) is NP-hard.