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

Area of Science:

• Computational Biology
• Cancer Genomics
• Phylogenetics

Background:

• Inferring tumor phylogenies from sequencing data is challenging, frequently resulting in multiple equally plausible evolutionary trees for a single cancer.
• Summarizing the diverse solution space of tumor phylogenies is crucial for understanding cancer evolution.
• Consensus tree methods aim to identify a single representative tree that best summarizes multiple inferred phylogenies.

Purpose of the Study:

• To develop and evaluate a consensus tree method for summarizing tumor phylogenies.
• To utilize the ancestor-descendant (AD) distance as a metric for tree comparison and consensus.
• To find a representative tumor phylogeny that minimizes the total AD distance across all inferred phylogenies.

Main Methods:

• Employed consensus tree algorithms to aggregate multiple tumor phylogenies.
• Utilized the ancestor-descendant (AD) distance, defined as the size of the symmetric difference of transitive closures of edge sets, as the primary distance metric.
• Sought a single tree S that minimizes the sum of AD distances to all inferred phylogenies.

Main Results:

• The study successfully applied consensus tree methods to summarize the solution space of tumor phylogenies.
• The ancestor-descendant distance was effectively used to quantify differences between tumor evolutionary trees.
• A representative tree minimizing total AD distance was identified, offering a concise summary of complex phylogenetic data.

Conclusions:

• Consensus tree methods provide a valuable approach to summarizing uncertainty in tumor phylogeny inference.
• The ancestor-descendant distance is a suitable metric for constructing representative tumor phylogenies.
• This work aids in a more unified understanding of cancer evolution by reducing multiple phylogenies to a single, representative tree.