Complexity and Algorithms for Finding a Perfect Phylogeny from Mixed Tumor Samples.

Area of Science:

• Computational Biology
• Bioinformatics
• Cancer Genomics

Background:

• Deconvoluting mixed tumor samples is crucial for understanding tumor evolution and identifying cancer mutations.
• Previous models, like Hajirasouliha and Raphael's (WABI 2014), aimed to reconstruct perfect phylogenies from sequencing data.
• Key challenges include the computational complexity of matrix decomposition and phylogenetic inference.

Purpose of the Study:

• To re-evaluate and disprove existing claims regarding the computational complexity of the mixed perfect phylogeny problem.
• To provide a correct proof of the NP-hardness for this deconvolution task.
• To develop novel algorithms for efficient and optimal solutions to tumor sample analysis.

Main Methods:

• Disproving previously published NP-hardness proofs for the mixed perfect phylogeny problem.
• Developing a new, independent proof to establish the problem's NP-hardness.
• Proving NP-completeness for a related variant of the problem.
• Designing a heuristic algorithm utilizing co-comparability graph coloring.
• Implementing a polynomial-time algorithm for specific matrix instances.

Main Results:

• Several claims regarding the mixed perfect phylogeny problem, including its NP-hardness, were disproven.
• The study successfully established the problem as NP-hard through a novel proof.
• A variant of the problem was proven to be NP-complete.
• An efficient heuristic and a polynomial-time algorithm were developed and implemented.

Conclusions:

• The computational complexity landscape of deconvoluting mixed tumor samples has been clarified.
• New algorithmic approaches offer practical solutions for analyzing tumor evolution and cancer mutations from sequencing data.
• Open-source implementations are available for broader research application.