| EPSRC Reference: |
EP/D062012/1 |
| Title: |
Stochastic Local Search Algorithms for Structural Proteomics |
| Principal Investigator: |
Steinhofel, Dr K |
| Other Investigators: |
|
| Researcher Co-Investigators: |
|
| Project Partners: |
|
| Department: |
Computer Science |
| Organisation: |
Kings College London |
| Scheme: |
First Grant Scheme |
| Starts: |
01 October 2006 |
Ends: |
30 September 2009 |
Value (£): |
219,751
|
| EPSRC Research Topic Classifications: |
| Artificial Intelligence |
Chemical Biology |
| Genomics |
Mathematical Aspects of OR |
|
| EPSRC Industrial Sector Classifications: |
| No relevance to Underpinning Sectors |
|
|
| Related Grants: |
|
| Panel History: |
|
|
Summary on Grant Application Form |
|
Proteins are key elements of virtually all cellular functions. They are complex biological macromolecules that are composed of a sequence of amino acids, which is encoded by a gene in a genome. Amino acids are joined end-to-end during protein synthesis by the formation of peptide bonds. The sequence of peptide bonds forms a main chain or backbone for the protein. The functional properties of proteins depend upon their three-dimensional structures. Knowing the structure of a protein provides a basis for identifying the protein's function, and protein structures are necessary for many computational drug docking techniques. Unlike the structure of other biological macromolecules (e.g., DNA), proteins have complex, irregular structures that are difficult to predict. To understand the entire folding pathway, i.e., the complete dynamics and chemical changes involved in going from an unfolded linear state into a compact folded state is one of the most challenging problems in current biochemistry.proposed project focuses on the design and analysis of brand new classes of stochastic local search-based algorithms for structural proteomics, i.e. for protein folding as well as for related problems like protein structure alignments and protein sequence design (inverse to folding). All these problems can be formulated as optimisation problems. For instance, one of the basic paradigms in structural proteomics is given by Anfinsen's thermodynamic hypothesis: Proteins fold to a minimum energy state, and the information determining the three-dimensional structure (tertiary structure) of a protein resides in the chemistry of its primary structure. Therefore, the investigation of stochastic local search algorithms (SLSA) is a natural choice to tackle these very complex (NP-hard) problems. SLSAs such as Simulated Annealing and Genetic Algorithms have been successfully applied to a wide variety of combinatorial optimisation problems. Since it is practically impossible for protein folding to evaluate every feasible conformation, local search algorithms try to find an efficient walk through an (energy) landscape that is induced by all possible solutions, where neighbouring solutions are evaluated with respect to the value of the objective function. In our approach we investigate the applicability of inhomogeneous Markov chains in order to control these walks through landscapes, where we focus on different models of protein folding together with a variety of potential objective functions. The choice of inhomogeneous Markov chains will enable us to mathematically prove properties such as convergence to optimum solutions and time estimates for the confidence to be in an optimum solution, e.g., after T(1\d) computation steps, the probability of having found an optimum solution is greater than (1-d). key aspect of our proposed research is a theoretical and experimental analysis of key structural parameters of the energy landscape that affect the convergence to optimum solutions. Based on knowledge about parameters such as distribution and depth of local minima, we can analyse and characterise the behaviour of other popular local search methods such as genetic algorithms, tabu search, and memetic algorithms. Moreover, there is a conjecture that local minima represent misfolded conformations , i.e., stable conformations that have a locally optimum energy state. These misfolds play an important role in the current discussion about causative factors in diseases. So, our results will give new insights into a more detailed complexity characterisation of folding problems and the performance of stochastic local search. Our approach will also contribute to the classification of misfolds in terms of their structural characterisation as local minima with respect to different energy functions, which will be in the long term crucial for personalised drug design and life science in general.
|
|
Key Findings |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
|
Potential use in non-academic contexts |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
|
Impacts |
|
| Description |
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk |
| Summary |
|
| Date Materialised |
|
|
|
|
Sectors submitted by the Researcher |
|
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
|
| Project URL: |
|
| Further Information: |
|
| Organisation Website: |
|