An Integer Linear Programming Formulation of the Cophylogeny Reconstruction Problem

The cophylogeny reconstruction problem is that of finding minimal cost ex-planations of differences between evolutionary histories of ecologically linked groups of biological organisms. A general form of this problem is known to be NP-complete [2] and the problem is conjectured to remain intractable under a variety of assumptions. Therefore, heuristics and optimized search algo-rithms are needed for this problem. This report shows how the problem can be formulated as an integer linear programming (ILP) problem. Using this formulation, ILP solvers may be used to solve the problem or, alternatively, relaxation methods may be used to find approximate solutions to the problem