{Reference Type}: Journal Article
{Title}: Consensus Tree Under the Ancestor-Descendant Distance is NP-Hard.
{Author}: Qi Y;El-Kebir M;
{Journal}: J Comput Biol
{Volume}: 31
{Issue}: 1
{Year}: 2024 01 28
{Factor}: 1.549
{DOI}: 10.1089/cmb.2023.0262
{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.