Effective optimization algorithms for fragment-assembly based protein structure prediction

Kevin W. Deronne, George Karypis

Research output: Contribution to journalArticlepeer-review

4 Scopus citations


Despite recent developments in protein structure prediction, an accurate new fold prediction algorithm remains elusive. One of the challenges facing current techniques is the size and complexity of the space containing possible structures for a query sequence. Traditionally, to explore this space fragment assembly approaches to new fold prediction have used stochastic optimization techniques. Here, we examine deterministic algorithms for optimizing scoring functions in protein structure prediction. Two previously unused techniques are applied to the problem, called the Greedy algorithm and the Hill-climbing (HC) algorithm. The main difference between the two is that the latter implements a technique to overcome local minima. Experiments on a diverse set of 276 proteins show that the HC algorithms consistently outperform existing approaches based on Simulated Annealing optimization (a traditional stochastic technique) in optimizing the root mean squared deviation between native and working structures.

Original languageEnglish (US)
Pages (from-to)335-352
Number of pages18
JournalJournal of Bioinformatics and Computational Biology
Issue number2 A
StatePublished - Apr 2007


  • Fragment assembly
  • Optimization
  • Protein structure prediction

Fingerprint Dive into the research topics of 'Effective optimization algorithms for fragment-assembly based protein structure prediction'. Together they form a unique fingerprint.

Cite this