Protein design: a NP-hard problem in bioinformatics - DUMAS - Dépôt Universitaire de Mémoires Après Soutenance
Mémoires Année : 2014

Protein design: a NP-hard problem in bioinformatics

Résumé

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
Loading...

Dates et versions

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

Licence

Identifiants

  • HAL Id : dumas-01088787 , version 1

Citer

Hugo Bazille. Protein design: a NP-hard problem in bioinformatics. Computer Science [cs]. 2014. ⟨dumas-01088787⟩
723 Consultations
635 Téléchargements

Partager

More