Résumés
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.
Keywords:
- integer programming,
- quadratic binary programming,
- computational biology,
- sequence alignment,
- protein folding,
- contact map overlap,
- rotamer assignment,
- protein similarity
Veuillez télécharger l’article en PDF pour le lire.
Télécharger