Complete publication list

Effective Optimization Algorithms for Fragment-assembly based Protein Structure Prediction

Kevin W. DeRonne and George Karypis
Computational Systems Bioinformatics Conference (CSB), 2006
Download Paper
Abstract
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 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 Hill-climbing algorithms consistently outperform existing approaches based on Simulated
Annealing optimization (a traditional stochastic technique) in optimizing the root mean
squared deviation (RMSD) between native and working structures.

Research topics: Bioinformatics