# Presentation: 261428

## Homotopy Optimization Methods and Protein Structure PredictionDaniel M. Dunlavy Applied Mathematics and Scientific ComputationUniversity of Maryland, College Park

## Protein Structure Prediction

- Amino Acid Sequence

## Protein Structure Prediction

- Given:
- Protein model
- Properties of constituent particles
- Potential energy function (force field)
- Goal:
- Predict native (lowest energy) conformation
- Thermodynamic hypothesis [Anfinsen, 1973]
- Develop hybrid method, combining:
- Energy minimization [numerical optimization]
- Comparative modeling [bioinformatics]
- Use **template** (known structure) to predict **target** structure

## Backbone model
Single chain of particles with residue attributes
Particles model C atoms in proteins

Properties of particles
Hydrophobic, Hydrophilic, Neutral 
Diverse hydrophobic-hydrophobic interactions

- Backbone model
- Single chain of particles with residue attributes
- Particles model C atoms in proteins
- Properties of particles
- Hydrophobic, Hydrophilic, Neutral
- Diverse hydrophobic-hydrophobic interactions

**Protein Model: Particle Properties**

- [Veitshans, Klimov, and Thirumalai. *Protein Folding Kinetics*, 1996.]

## Potential Energy Function

## Potential Energy Function

## Goal
Minimize energy function of target protein:

Steps to solution
Energy of template protein:
Define a homotopy function:

Deforms template protein into target protein
Produce sequence of minimizers of               starting at            and ending at 

- Minimize energy function of target protein:
- Steps to solution
- Energy of template protein:
- Define a homotopy function:
- Deforms template protein into target protein
- Produce sequence of minimizers of               starting at            and ending at

**Homotopy Optimization ****Method (HOM)**

## Energy Landscape Deformation   Dihedral Terms

**Energy Landscape Deformation**** ****  ****Dihedral Terms**

## Illustration of HOM

## Homotopy Optimization using Perturbations & Ensembles (HOPE)

- Improvements over HOM
- Produces ensemble of sequences of local minimizers of              by perturbing intermediate results
- Increases likelihood of predicting global minimizer
- Algorithmic considerations
- Maximum ensemble size
- Determining ensemble members

## Illustration of HOPEMaximum ensemble size = 2

## Numerical Experiments

- 9 chains (22 particles) with known structure

**Loop Region**

**Hydrophobic****	****Hydrophilic****	****Neutral**

- ABCDE F GH I

|  | A | B | C | D | E | F | G | H | I |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| A | 100 |  |  |  |  |  |  |  |  |
| B | 77 | 100 |  |  |  |  |  |  |  |
| C | 86 | 91 | 100 |  |  |  |  |  |  |
| D | 91 | 86 | 77 | 100 |  |  |  |  |  |
| E | 73 | 82 | 73 | 82 | 100 |  |  |  |  |
| F | 68 | 68 | 59 | 77 | 86 | 100 |  |  |  |
| G | 68 | 68 | 59 | 77 | 86 | 100 | 100 |  |  |
| H | 68 | 68 | 59 | 77 | 86 | 100 | 100 | 100 |  |
| I | 73 | 59 | 64 | 68 | 77 | 73 | 73 | 73 | 100 |

**Sequence Homology (%)**

## Numerical Experiments

**Numerical Experiments**

## Numerical Experiments

- 62 template-target pairs
- 10 pairs had identical native structures
- Methods
- HOM vs. Newton’s method w/trust region (N-TR)
- HOPE vs. simulated annealing (SA)
- Different ensemble sizes (2,4,8,16)
- Averaged over 10 runs
- Perturbations where sequences differ
- Measuring success
- Structural overlap function:
- Percentage of interparticle distances off by more   than 20% of the average bond length (  )
- Root mean-squared deviation (RMSD)

- Ensemble SA
- Basin hopping
- T0 = 105
- Cycles = 10
- Berkeley schedule

## Structural Overlap Function

- Native

- Predicted

## RMSD

- Measures the distance between corresponding particles in the predicted and lowest energy conformations when they are optimally superimposed.

- where           is a rotation and translation of

## Results

## Results

- Success of HOPE and SA with ensembles of size 16 for each template-target pair. The size of each circle represents the percentage of successful predictions over the 10 runs.

- SA

- HOPE

## Conclusions

- Homotopy optimization methods
- More successful than standard minimizers
- HOPE
- For problems with                          readily available
- Solves protein structure prediction problem
- Outperforms ensemble-based simulated annealing
- Future work
- Protein Data Bank (templates), TINKER (energy)
- Convergence analysis for HOPE

## Acknowledgements

- Dianne O’Leary (UM)
- Advisor
- Dev Thirumalai (UM), Dmitri Klimov (GMU)
- Model, numerical experiments
- Ron Unger (Bar-Ilan)
- Problem formulation
- National Library of Medicine (NLM)
- Grant: F37-LM008162

## Thank You

**Daniel Dunlavy – HOPE**
- http://www.math.umd.edu/~ddunlavy
- ddunlavy@math.umd.edu

## HOPE Algorithm

## Homotopy Parameter Functions

**Homotopy Parameter Functions**

- Split low/high frequency dihedral terms
- Homotopy parameter functions for each term

## Different         for individual energy terms

**Homotopy Function for Proteins**

- Template

- Target