2013/06/06 by Bahi, Jacques M., Wojciech Bienia, Bienia, Wojciech +5 · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · #Protein Structure and Dynamics #Machine Learning in Bioinformatics #Algorithms and Data Compression
paper · pdf · doi:10.48550/arxiv.1306.1372
To determine the 3D conformation of proteins is a necessity to understand\ntheir functions or interactions with other molecules. It is commonly admitted\nthat, when proteins fold from their primary linear structures to their final 3D\nconformations, they tend to choose the ones that minimize their free energy. To\nfind the 3D conformation of a protein knowing its amino acid sequence,\nbioinformaticians use various models of different resolutions and artificial\nintelligence tools, as the protein folding prediction problem is a NP complete\none. More precisely, to determine the backbone structure of the protein using\nthe low resolution models (2D HP square and 3D HP cubic), by finding the\nconformation that minimize free energy, is intractable exactly. Both the proof\nof NP-completeness and the 2D prediction consider that acceptable conformations\nhave to satisfy a self-avoiding walk (SAW) requirement, as two different amino\nacids cannot occupy a same position in the lattice. It is shown in this\ndocument that the SAW requirement considered when proving NP-completeness is\ndifferent from the SAW requirement used in various prediction programs, and\nthat they are different from the real biological requirement. Indeed, the proof\nof NP completeness and the predictions in silico consider conformations that\nare not possible in practice. Consequences of this fact are investigated in\nthis research work.\n