Protein design: a NP-hard problem in bioinformatics - DUMAS - Dépôt Universitaire de Mémoires Après Soutenance Access content directly
Master Thesis Year : 2014

Protein design: a NP-hard problem in bioinformatics


Proteins are biological macromolecules made of a chain of simple molecules called amino-acids. The three-dimensional folding of a protein greatly determines its function. Due to the combinatorial nature of the space of possible protein spatial conformations, computer-aided protein study is a major research field in bioinformatics. The problem of computational protein design aims at finding the best protein conformation to perform a given task. In this internship, this problem is reduced to an optimization problem, looking for the minimization of an energy function depending on the amino-acid interactions in the protein. The goal of this internship is to develop a new solver for this problem based on Answer Set Programming. ASP is a paradigm of declarative programming based on non monotonic reasoning. The computational protein design problem may be easily modeled as an ASP program but a practical implementation able to work on real-sized instances has never been achieved. This report presents the state-of-the-art approaches in the domain (A*, ILP, weighted-CSP...) and proposes an in-depth study in ASP that shows opportunities and pitfalls of this approach. We ran a series of benchmarks highlighting the importance of finding a good upper bound estimation of the target minimum energy to reduce the amount of combinatorial search. Our solution outperforms a previous ASP implementation and has comparable performances with respect to SAT-based approaches.
Fichier principal
Vignette du fichier
mri20132014_submission_45.pdf (2.54 Mo) Télécharger le fichier

Dates and versions

dumas-01088787 , version 1 (04-01-2015)




  • HAL Id : dumas-01088787 , version 1


Hugo Bazille. Protein design: a NP-hard problem in bioinformatics. Computer Science [cs]. 2014. ⟨dumas-01088787⟩
674 View
563 Download


Gmail Facebook X LinkedIn More