Abstract

The perfect phylogeny problem and various generalizations of it have been extensively studied in computational biology. We consider the following variant of the problem: Given a binary matrix M, the Minimum Conflict-Free Row Split problem asks to compute a smallest possible binary matrix M’ which corresponds to a perfect phylogeny and such that each row of M can be obtained as the bitwise OR of rows in M’. We give a new, more transparent formulation of this NP-hard problem in terms of an optimization problem on the set of branchings in a derived directed acyclic graph. Building on this formulation, we obtained several new results. Our work relates to chain partitions in partially ordered sets and (classical and weighted) colorings of graphs.

Originally, the problem was proposed for finding the different subtypes of a tumor using DNA sequencing. The equivalent branching formulation of the problem leads to an ILP formulation, which we implemented for the purpose of the application. Using simulated data, we showed that it is more accurate than existing methods in reconstructing the original phylogeny.

Bio

Edin is a third year mathematics PhD student at London School of Economics, under the mentorship of László Végh. He interests broadly in combinatorial optimization and theoretical computer science. More info at: https://zhero9.github.io/.