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

Additional Files

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

Vol. 3 No. 2 (2008)

Section

Articles

License

The copyright of the submitted article is hereby transferred to “Preeminent Academic Facets Inc. (the “publisher”) to the extent possible by the laws in the respective countries of the author(s). The author(s) retain all other rights including the following: 1. Any patents and trademark rights. 2. Right to post a pre-print version of the paper on the author’s personal website which is not used for commercial purposes. The author(s) warrant that the work is original, it has not been published elsewhere, it is not currently under consideration for publication in any form, and it does not infringe any copyright laws. The signing author or agent further warrants that all authors, if applicable, have been informed of the terms of this agreement and obtained the approval and authority to sign the agreement.