Protein design: a NP-hard problem in bioinformatics

Hugo Bazille 1, 2
2 Dyliss - Dynamics, Logics and Inference for biological Systems and Sequences
Inria Rennes – Bretagne Atlantique , IRISA-D7 - GESTION DES DONNÉES ET DE LA CONNAISSANCE
Abstract : 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.
Document type :
Master Thesis
Complete list of metadatas

Cited literature [40 references]  Display  Hide  Download

https://dumas.ccsd.cnrs.fr/dumas-01088787
Contributor : Co-Responsables Du Mri V. Gouranton Et S. Blazy <>
Submitted on : Sunday, January 4, 2015 - 12:55:58 PM
Last modification on : Thursday, November 15, 2018 - 11:57:52 AM
Long-term archiving on: Thursday, September 10, 2015 - 11:16:06 PM

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

  • HAL Id : dumas-01088787, version 1

Citation

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

Share

Metrics

Record views

820

Files downloads

644