EPSRC logo

Details of Grant 

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: