title: Generating, Maintaining, and Exploiting Diversity in a Memetic Algorithm for Protein Structure Prediction.
abstract: Computational approaches to de novo protein tertiary structure prediction, including those based on the preeminent "fragment-assembly" technique, have failed to scale up fully to larger proteins (on the order of 100 residues and above). A number of limiting factors are thought to contribute to the scaling problem over and above the simple combinatorial explosion, but the key ones relate to the lack of exploration of properly diverse protein folds, and to an acute form of "deception" in the energy function, whereby low-energy conformations do not reliably equate with native structures. In this article, solutions to both of these problems are investigated through a multistage memetic algorithm incorporating the successful Rosetta method as a local search routine. We found that specialised genetic operators significantly add to structural diversity and that this translates well to reaching low energies. The use of a generalised stochastic ranking procedure for selection enables the memetic algorithm to handle and traverse deep energy wells that can be considered deceptive, which further adds to the ability of the algorithm to obtain a much-improved diversity of folds. The results should translate to a tangible improvement in the performance of protein structure prediction algorithms in blind experiments such as CASP, and potentially to a further step towards the more challenging problem of predicting the three-dimensional shape of large proteins.
authors.affiliation: Decision and Cognitive Sciences Research Centre, University of Manchester, Manchester, M15 6PB, UK mario.garza-fabre@manchester.ac.uk.
authors.forename: Mario
authors.initials: M
authors.lastname: Garza-Fabre
authors.affiliation: Faculty of Life Sciences, University of Manchester, Manchester, M13 9PT, UK shaun.kandathil@manchester.ac.uk.
authors.forename: Shaun M
authors.initials: SM
authors.lastname: Kandathil
authors.affiliation: Decision and Cognitive Sciences Research Centre, University of Manchester, Manchester, M15 6PB, UK julia.handl@manchester.ac.uk.
authors.forename: Julia
authors.initials: J
authors.lastname: Handl
authors.affiliation: School of Computer Science, University of Birmingham, Birmingham, B15 2TT, UK j.knowles.1@cs.bham.ac.uk.
authors.forename: Joshua
authors.initials: J
authors.lastname: Knowles
authors.affiliation: Faculty of Life Sciences, University of Manchester, Manchester, M13 9PT, UK simon.lovell@manchester.ac.uk.
authors.forename: Simon C
authors.initials: SC
authors.lastname: Lovell
mesh_terms: D000465:Algorithms; D019295:Computational Biology; D019143:Evolution, Molecular; D056004:Molecular Dynamics Simulation; D010446:Peptide Fragments / Q000737:chemistry / Q000235:genetics; D011487:Protein Conformation; D017433:Protein Structure, Secondary; D017434:Protein Structure, Tertiary; D011506:Proteins / Q000737:chemistry* / Q000235:genetics; D013269:Stochastic Processes
chemical_list: D010446:Peptide Fragments; D011506:Proteins
keywords: Fragment assembly; Memetic algorithms.; Protein structure prediction