A Heuristic Based Implementation for the Cograph Editing Problem

A cograph is a P4-free graph. The cograph editing problem is about converting an arbitrary graph into a cograph by applying edit operations, i.e. adding and removal of edges. This problem has been shown to be NP-complete and therefore the implementation of heuristics and/or approximation algorithms are necessary. In this work, we present an implementation based on heuristics for the cograph editing problem, a pipeline that includes a branching procedure to search the solution space in order to find a minimum set of edit operations to modify the input graph. In particular, a modular decomposition plays an important role to identify the prime modules of the input graph. We also performed a case study in gene evolution. Recently, it has been shown that graphs whose vertices represent genes and whose edges represent valid orthology relations between genes can be modeled by cographs. It is noteworthy that, due to divergence of genes during evolution, these orthology relations are not always predicted correctly. Therefore, a method to verify and correct those predictions is useful, which has been tackled by our implementation.

Hosted by Maribel Hernandez