Back close

Optimal Perfect Phylogeny Using ILP and Continuous Approximations

Publication Type : Conference Paper

Publisher : Springer

Source : Communications in Computer and Information Science

Url :

Campus : Coimbatore

School : School of Artificial Intelligence - Coimbatore

Year : 2023

Abstract : 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.

Cite this Research Publication : Pranav Kumaar, B.E., Aadharsh Aadhithya, A., Sachin Kumar, S., Anandaram, H., Soman, K.P. (2023). Optimal Perfect Phylogeny Using ILP and Continuous Approximations. In: Singh, M., Tyagi, V., Gupta, P., Flusser, J., Ören, T. (eds) Advances in Computing and Data Sciences. ICACDS 2023. Communications in Computer and Information Science, vol 1848. Springer, Cham.

Admissions Apply Now