Optimal Perfect Phylogeny Using ILP and Continuous Approximations

The concept of perfect phylogeny is observed to be non-universal, however, in some studies, it is shown that it provides great insights from a biological standpoint. Most natural phylogenies are imperfect but this is debated by the presence of noise in data acting as a disguise, the solution to uncover the underlying perfect phylogeny in the simplest approach is known as Minimum Character Removal (MCR) problem. Another variant of the solution achieved by a change in perspective and computational methodology is known as Maximal Character Compatibility (MCC) problem. Both MCR and MCC problems are solved optimally with reasonable efficiency by using Integer Linear Programming (ILP) technique. A central part of MCC solution involves solving the Max-clique problem of the generated representation allowing numerous clique-solving algorithms to generate various solutions. The comparison between the solution’s optimality and the run-time of these methods substantiates the goal of the different algorithms being applied. The above methods are formulated and implemented using modern programming languages like Python and Matlab. This exploration introduces the problem of perfect phylogeny, its ILP formulations, and its solution along with comparisons between different methods in consideration.