Introduction

Recently, Hajirasouliha and Raphael (WABI 2014) proposed a model for deconvoluting mixed tumor samples measured from a collection of high-throughput sequencing reads. This is related to understanding tumor evolution and critical cancer mutations. In short, their formulation asks to split each row of a binary matrix so that the resulting matrix corresponds to a perfect phylogeny and has the minimum number of rows among all matrices with this property. In this paper we disprove several claims about this problem, including an NP-hardness proof of it. However, we show that the problem is indeed NP-hard, by providing a different proof. We also prove NP-completeness of a variant of this problem proposed in the same paper. On the positive side, we propose an efficient (though not necessarily optimal) heuristic algorithm based on coloring co-comparability graphs, and a polynomial time algorithm for solving the problem optimally on matrix instances in which no column is contained in both columns of a pair of conflicting columns. Implementations of these algorithms are freely available at https://github.com/alexandrutomescu/MixedPerfectPhylogeny.

Publications

  1. Complexity and algorithms for finding a perfect phylogeny from mixed tumor samples.
    Cite this
    Hujdurovic A, Kacar U, Milanic M, Ries B, Tomescu AI, 2016-10-01 - IEEE/ACM transactions on computational biology and bioinformatics

Credits

  1. Ademir Hujdurovic
    Developer

  2. Ursa Kacar
    Developer

  3. Martin Milanic
    Developer

  4. Bernard Ries
    Developer

  5. Alexandru I Tomescu
    Investigator

Community Ratings

UsabilityEfficiencyReliabilityRated By
0 user
Sign in to rate
Summary
AccessionBT002916
Tool TypeApplication
Category
PlatformsLinux/Unix
TechnologiesC++
User InterfaceTerminal Command Line
Download Count0
Submitted ByAlexandru I Tomescu