Quadratic Binary Programming Models in Computational Biology

Authors

  • Richard John Forrester Dickinson College
  • Harvey J Greenberg University of Colorado at Denver

Keywords:

integer programming, quadratic binary programming, computational biology, sequence alignment, protein folding, contact map overlap, rotamer assignment, protein similarity

Abstract

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.

Downloads

Published

2008-07-21

How to Cite

Forrester, R. J., & Greenberg, H. J. (2008). Quadratic Binary Programming Models in Computational Biology. Algorithmic Operations Research, 3(2). Retrieved from https://journals.lib.unb.ca/index.php/AOR/article/view/5930

Issue

Section

Articles