Quadratic binary programming models in computational biology

In this paper we formulate four problems in computational molecular biology as 0–1 quadratic programs. These problems are all NP–hard and the current solution methods used in practice consist of heuristics or approximation algorithms tailored to each problem. Using test problems from scientific databases, we address the question, ‘Can a general–purpose solver obtain good answers in reasonable time?’ In addition, we use the latest heuristics as incumbent solutions to address the question, ‘Can a general–purpose solver confirm optimality or find an improved solution in reasonable time?’ Our computational experiments compare four different reformulation methods: three forms of linearization and one form of quadratic convexification.