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 spaceof tumor phylogenies, consensus tree methods seek a single best representative treeSunder a specified pairwise tree distance function. One such distance function is the ancestor–descendant (AD) distance, which equals the size of the symmetric difference of the transitive closures of the edge sets and . Here, we show that finding a consensus treeSfor tumor phylogeniesthat minimizes the total AD distance is NP-hard.
Get full access to this article
View all access options for this article.
References
1.
AguseN, QiY, El-KebirM. Summarizing the solution space in tumor phylogeny inference by multiple consensus trees. Bioinformatics, 2019; 35(14):i408–i416.
2.
ChristensenS, KimJ, ChiaN, et al.Detecting evolutionary patterns of cancers using consensus trees. Bioinformatics, 2020; 36(Suppl. 2):i684–i691.
3.
CookSA. The complexity of theorem-proving procedures. In: Proceedings of the Third Annual ACM Symposium on Theory of Computing. 1971; pp. 151–158.
4.
DiNardoZ, TomlinsonK, RitzA, et al.Distance measures for tumor evolutionary trees. Bioinformatics, 2020; 36(7):2090–2097.
5.
El-KebirM, SatasG, OesperL, et al.Inferring the mutational history of a tumor using multi-state perfect phylogeny mixtures. Cell Systems, 2016; 3(1):43–53.
6.
FuX, SchwartzR. Contreedp: A consensus method of tumor trees based on maximum directed partition support problem. In: 2021 IEEE International Conference on Bioinformatics and Biomedicine (BIBM). IEEE; 2021; pp. 125–130.
7.
GovekK, SikesC, OesperL. A consensus approach to infer tumor evolutionary histories. BCB, 2018; 63–72.
8.
GovekK, SikesC, ZhouY, et al.Graphyc: Using consensus to infer tumor evolution. IEEE/ACM Trans Comp Biol Bioinform, 2020; 19(1):465–478.
9.
GuangZ, Smith-ErbM, OesperL. A weighted distance-based approach for deriving consensus tumor evolutionary trees. Bioinformatics, 2023; 39(Suppl. 1):i204–i212; doi: 10.1093/bioinformatics/btad230.
10.
KarpRM.Reducibility among combinatorial problems. In: Complexity of Computer Computations: Proceedings of a symposium on the Complexity of Computer Computations, held March 20–22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, and sponsored by the Office of Naval Research, Mathematics Program, IBM World Trade Corporation, and the IBM Research Mathematical Sciences Department. (MillerRE, ThatcherJW, BohlingerJD. eds.) Springer US: Boston, MA, USA; 1972; pp. 85–103.
11.
KarpovN, MalikicS, RahmanM, et al.A multi-labeled tree dissimilarity measure for comparing “clonal trees” of tumor progression. Algorithms Mol Biol, 2019; 14(1):1–18.
12.
KimuraM. The number of heterozygous nucleotide sites maintained in a finite population due to steady flux of mutations. Genetics, 1969; 61(4):893.
13.
NowellPC. The clonal evolution of tumor cell populations. Science, 1976; 194(4260):23–28.
14.
QiY, PradhanD, El-KebirM. Implications of non-uniqueness in phylogenetic deconvolution of bulk DNA samples of tumors. Algorithms Mol Biol, 2019; 14:1–14.
15.
SchwartzR, SchäfferAA. The evolution of tumour phylogenetics: Principles and practice. Nat Rev Genet, 2017; 18(4):213–229.
16.
ZuckermanD. Linear degree extractors and the inapproximability of max clique and chromatic number. In: Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing. 2006; pp. 681–690.
