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

Aguse N, Qi Y, El-Kebir M. Summarizing the solution space in tumor phylogeny inference by multiple consensus trees. Bioinformatics 2019;35(14):i408–i416.

Christensen S, Kim J, Chia N, et al. Detecting evolutionary patterns of cancers using consensus trees. Bioinformatics 2020;36(Suppl. 2):i684–i691.

Cook SA. The complexity of theorem-proving procedures. In: Proceedings of the Third Annual ACM Symposium on Theory of Computing. 1971; pp. 151–158.

DiNardo Z, Tomlinson K, Ritz A, et al. Distance measures for tumor evolutionary trees. Bioinformatics 2020;36(7):2090–2097.

El-Kebir M, Satas G, Oesper L, et al. Inferring the mutational history of a tumor using multi-state perfect phylogeny mixtures. Cell Systems 2016;3(1):43–53.

Fu X, Schwartz R. 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.

Govek K, Sikes C, Oesper L. A consensus approach to infer tumor evolutionary histories. BCB 2018;63–72.

Govek K, Sikes C, Zhou Y, et al. Graphyc: Using consensus to infer tumor evolution. IEEE/ACM Trans Comp Biol Bioinform 2020;19(1):465–478.

Guang Z, Smith-Erb M, Oesper L. A weighted distance-based approach for deriving consensus tumor evolutionary trees. Bioinformatics 2023;39(Suppl. 1):i204–i212;.

Karp RM. 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. (Miller RE, Thatcher JW, Bohlinger JD. eds.) Springer US: Boston, MA, USA; 1972; pp. 85–103.

Karpov N, Malikic S, Rahman M, et al. A multi-labeled tree dissimilarity measure for comparing “clonal trees” of tumor progression. Algorithms Mol Biol 2019;14(1):1–18.

Kimura M. The number of heterozygous nucleotide sites maintained in a finite population due to steady flux of mutations. Genetics 1969;61(4):893.

Nowell PC. The clonal evolution of tumor cell populations. Science 1976;194(4260):23–28.

Qi Y, Pradhan D, El-Kebir M. Implications of non-uniqueness in phylogenetic deconvolution of bulk DNA samples of tumors. Algorithms Mol Biol 2019;14:1–14.

Schwartz R, Schäffer AA. The evolution of tumour phylogenetics: Principles and practice. Nat Rev Genet 2017;18(4):213–229.

Zuckerman D. 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.