Thesis (Index)   <-  Sean Forman   <-  You Are Here

Torsion Angle Selection and Emergent Non-local Secondary Structure in Protein Structure Prediction

Sean Forman
Department of Math and Computer Science
Saint Joseph's University

Working with
Alberto Segre, University of Iowa
Yinyu Ye, University of Iowa
Kenneth Murphy, University of Iowa

What use is a genome?

• The genome is a set of A, G, T, and C patterns.

• Within the genome, genes are informational sequences of DNA bases.

• They are a list of amino acids that make up different proteins.

Why do we care about proteins?

• Nearly all bodily processes are regulated by proteins.

• Knowing a protein's structure (also called conformation or fold) can tell us what sort of drugs will interact with that protein.

• Finding the structure is harder than it might seem.

What determines a protein's structure?

• It is widely believed that the sequence of amino acids determines the 3-D structure of the protein, (Anfinsen 1973, [#!anfinsen73:-princ!#]).

• Sequence is relatively cheap to determine - Human Genome Project

• We want to use this sequence to find new proteins and their sequences, and then determine their 3-D structure.

• Expensive to determine - NMR, X-ray Crystallography

• Then we want to use the structure to determine how the protein works, and then we want to determine how the proteins interact.

What do proteins look like?

• A protein is an open chain of amino acids, like beads on a string.

• Amino acids are molecules of seven or more atoms. There are twenty different types of amino acids.

What is an amino acid's structure?

• Amino acids are made of carbon, hydrogen, nitrogen, oxygen and sulfur atoms.

• There are twenty different amino acids. Each amino acid has the same backbone and a unique sidechain.

• Amino acid backbones plug together to form a protein.

$$\begin{array}{c c} \multicolumn{1}{l}{\mbox{\bf Alanine - AL... ...udegraphics[height=2.5in]{GRAPHICS/TRP_tri.ps} \\ \end{array}$$

How can the shape of the amino acid change?

• The bond lengths and angles are essentially fixed.

• The main allowable movement is in the bond torsion angles $\{\phi, \psi, \omega\}$. The rotation along the bonds.

• Also, the $\omega$ angle occurs only as $180^\circ$ or $0^\circ$ since it is a partial double bond.

• Sidechains can rotate as well, but they are local changes.

• The primary variables in a protein's conformation are its torsion angles.

Energetics: How does the long chain become a globular molecule?

• Folding is caused by molecular attractions and repulsions (energetics) within the protein and with the surrounding water.

• $N$ and $O$ like to share hydrogens, but $C$ doesn't.

• Proteins fold in water, and water is polar (shares hydrogens). Proteins strive to expose $N$ and $O$ to outside or each other and keep $C$ on inside. These interactions are called hydrogen bonds.

• Because of this sharing behavior some amino acids are termed hydrophobic and some hydrophilic.

Effects of hydrogen bonding and secondary structure

• There are two common secondary structures that allow proteins to form many hydrogen bonds.

• $\alpha-Helices$ are helical formations.

• $\beta-Strands$ are long strands of amino acids that come together to form $\beta-Sheets$.

• There are other ways, but they occur less frequently.

• The amino acids in these structures correspond to repeating torsion angle values.

Figure: $\alpha$-helix hydrogen bonding pattern. These images are produced using Rasmol [#!program-rasmol!#].

Figure: Hydrogen bonding patterns for parallel and anti-parallel $\beta$-sheets.

$$\begin{array}{c c} \multicolumn{1}{l}{\mbox{\bf Anti-Paralle... ...egraphics[height=3.0in]{GRAPHICS/paraPattern.pstex} \end{array}$$

$$\begin{array}{c c} \multicolumn{1}{l}{\mbox{\bf Carbonic Anh... ...cludegraphics[height=3.0in]{GRAPHICS/fancypdb_2.ps} \end{array}$$

Problem Description

The protein folding problem is defined as the prediction of the protein's three-dimensional (tertiary) structure from its amino acid sequence.

MTYKLILNGKTLKGETTTEAVDAATAEK
VFKQYANDNGVDGEWTYDDATKTFTVTE

$$\begin{array}{c c c} \includegraphics[width=2.5in]{GRAPHICS/... ...includegraphics[width=2.5in]{GRAPHICS/1PGB.ps} \\ \end{array}$$

Current Techniques in Protein Folding

• Pattern Recognition
  • sequence homology - match target's amino acid sequence to sequences of known structure

  • fold recognition - match target's sequence to known structures and see how well they fit

• Molecular Modeling - ab initio techniques
  • Formulate an energy function to minimize

  • Search a space of potential conformations

  • Simplifying assumptions

  • Proven NP-complete [#!berger98:-protein-hp-np-compl!#].

HOPS-Hybrid Optimizer of Protein Structure

• First, we reduce the continuous range of torsion angles to a discrete set using clustering.

• Full protein representation

• We then search using the discrete set of torsion angles and a simplified energy function.

• Search done in parallel with a variety of techniques.

• In certain cases, we will consider a continuous relaxation of the discrete torsion angles.

Protein Representation

• The protein backbone is modeled as an open link chain, e.g. a robot arm, with a homogeneous coordinate system.

• Updating an amino acid's position takes a series of $4 \times 4$ matrix multiplications. Position is location and orientation.

• Backbone bond lengths and angles are fixed.

• Only torsion angles can change.

• Sidechain libraries are pre-defined.

Searching

• We begin with the very first amino acid, and choose from the $\phi$ and $\psi$ angles found in our discretization.

• From there, we continue adding amino acids to our protein.

• This can be viewed as a search tree.

• Certain angle combinations can lead to steric clashes which causes backtracking.

• Clashes stored in a failure cache accessed with a hash function.

@font

picture(6316,4765)(301,-3962) (281,-3415)(0,0)[lb]AAcid $L - 1$% (281,-3939)(0,0)[lb]AAcid $L$% (5026,-3736)(0,0)[lb]at each level% (5026,-3436)(0,0)[lb]$n_k$ angle choices% (1051,-286)(0,0)[lb]AAcid $2$% (1051, 89)(0,0)[lb]AAcid $1$% (2851,464)(0,0)[lb] $(\phi_1,\psi_1)$% (4876,464)(0,0)[lb] $(\phi_n,\psi_n)$%

Continuous Optimization

• The finite angle set is good at generating $\alpha-helices$, but poor at generating $\beta-sheets$ due to the finite number of turn angles available.

• To aid in the creation of $\beta-sheets$ we have added a continuous optimization technique to bring two or more $\beta-strands$ into alignment. This will be detailed later.

Contributions to Energy Function

• The energy function and its parameters are based on laboratory data.
  • Accessible Surface Area of $C$ atoms

  • ASA of $N$ and $O$ atoms

  • ASA of the sidechain (involves entropy)

  • number of hydrogen bonds between $O$ and $N$

  • Overestimate of the potential contributions of the protein's unfolded portion

• Since we overestimate the best solution along this path, entire branches can be pruned.

• A good early solution means more pruning.

A Parallel Programming Method: Nagging

• scalable (transfers well to a large number of machines)

• fault-tolerant (can survive a machine crashing)

• not a partitioning method (work isn't divided among machines)

• each machine is given the current state of the solution and is asked to search the space in an order different from the parent machine

• infrequent communication between processors keeps down overhead costs

• relies on a large variance in the solution time dependent on ordering

• Nagging has been implemented on 3SAT, TSP, First-Order Logic, Matching Problem, Game-Tree Search

Nagging and Protein Folding

• The nagger is given the angles and amino acids set by the parent in its search.

• It receives an energy value for the current best solution and the current angle set from the parent and then searches the remaining angles in a different manner from the parent.

• The nagger reports any solutions or lack thereof to the parent, who uses that information to improve its search.

Clustering

• HOPS depends on the selection of torsion angle choices for each type of amino acid to frame the search.

• $\omega$ is fixed. Patterns emerge in Ramachandran plots ( $\phi - \psi$ angle pairs).

• Patterns are a result of the amino acid shape and sidechains.

• Angle space is a torus.

• Should choose just enough angle pairs to represent the space.

$$\begin{array}{c c} \multicolumn{1}{l}{\mbox{\bf Glycine }} &... ...ght=2.8in, angle=-90]{GRAPHICS/TRP_graph.ps} \\ \end{array}$$

Algorithms

• Hierarchical - build clusters of increasing or decreasing size, MST.

• Optimization - build structures to minimize some objective, $k$-means.

• We use a Multiple Facilities Location technique, which is an operations research technique.

• Cluster points are facilities and the torsion angles are demand points.

• The Weber single facility location problem is defined as find $(X,Y)$ that minimizes, $C(X,Y)$, the total distance from the cluster points to the torsion angles.

  $$\operatorname*{min} C(X,Y) = \sum_{j = 1}^{n} \sqrt{(X - x_j)^2 - (Y - y_j)^2}$$ (1)

  
  

Weber's Solution

• For the single facility problem, we have an iterative solution [#!wesolowsky93:-weber!#].

• We choose an initial solution, and we then use the following iterations until we converge to a solution [#!bricker98:-facil-locat-probl-plane!#].

  $$X^{k+1} = \frac{ \displaystyle{\sum_{j=1}^{n} \frac{x_j}{d_j(X^k,Y^k) }}} { \displaystyle{\sum_{j=1}^{n} \frac{1}{d_j(X^k,Y^k) }}}$$ (2)

  
  

  $$Y^{k+1} = \frac{ \displaystyle{\sum_{j=1}^{n} \frac{y_j}{d_j(X^k,Y^k)} } }{ \displaystyle{\sum_{j=1}^{n} \frac{1}{d_j(X^k,Y^k)} } }$$ (3)

  
  

Multiple Cluster Points

$$\begin{array}{c c c} \includegraphics[width=2.0in]{GRAPHICS/... ...[width=2.0in]{GRAPHICS/cluster_final.xfig.eps} \\ \end{array}$$

Clustering, other issues

• How many is enough?

• We usually strive for 2-10.

• Incremental addition of points

Clustering Samples

$$\begin{array}{c c} \multicolumn{1}{l}{\mbox{\bf Threonine}} ... ...ght=3.5in, angle=-90]{GRAPHICS/ASN_graph_3.ps} \\ \end{array}$$

Tweaking

$$\begin{array}{l r} \includegraphics[width=2.5in]{GRAPHICS/st... ...egraphics[width=3.5in]{GRAPHICS/strandsAligned.eps} \end{array}$$

• HOPS creates many $\beta$-strands, but they rarely become $\beta$-sheets.

• In some cases, we need to continuously adjust the turn torsion angles so that two $\beta$-strands will align.

• In our protein representation, the global positions of the atoms are stored in $4 \times 4$ matrices (position matrices), as are the changes from one backbone atom to the next (transform matrices).

Global Position Matrix

$$\begin{multline} \mathnormal{P} \left(r_X, r_Y, r_Z, l_X, l_Y, l_Z \right) = ... ...cos r_X \cos r_Y & l_Z \\ 0 & 0 & 0 & 1 \\ \end{array}\right) \end{multline}$$

Backbone Transform Matrix

$$\mathnormal{T} \mathbf{ \left(\tau, \kappa, L \right) } = \left( ... ...\cos \kappa \sin \tau & \cos \tau & 0 0 & 0 & 0 & 1 \end{array} \right)$$ (4)

One atom to another

$$\mathnormal{P}_{i,\ensuremath{\mathbf{N}}} = \mathnormal{P}_{i - 1,\ensuremath{\mathbf{C'}}} \mathnormal{T}_{i - 1,\omega}$$ (5)

A string of atoms. To align two atoms, we adjust intermediate transform matrices.

$$\mathnormal{P}_{j,\ensuremath{\mathbf{C^\prime}}} \mathnormal{T}_... ..... \mathnormal{T}_{k-1,\psi} \mathnormal{T}_{k-1,\omega} = \mathnormal{P}_{k,N}$$ (6)

$$\mathnormal{T}_{j,\omega} \mathnormal{T}_{j+1,\phi} \mathnormal{T... ...^{-1} \mathnormal{P}_{k,\ensuremath{\mathbf{N}}} \doteqdot \mathnormal{G_\zeta}$$ (7)

Each transform matrix is a function of $${ \mathnormal{T}_{i,\theta} ( \tau_{i,\theta} + \Delta \tau_{i,\theta})}$$. We want to find $\{ \Delta \tau_{i,\theta} \}$ that cause an equality in Equation .

Problem Specification

$$\operatorname{minimize} \qquad \sum_{(i,\theta) = (j+1,\phi) }^{ (k-1,\omega)} \Vert \Delta \tau_{i,\theta} \Vert _2$$ (8)

$$\operatorname{subject to} \qquad \mathnormal{T}_{j,\omega} ( \tau_{j,\omega}) \prod_{(i,\th... ...eta} ( \tau_{i,\theta} + \Delta \tau_{i,\theta}) \doteqdot \mathnormal{G_\zeta}$$

or restated using vector notation as

$$\operatorname{minimize} \qquad \Vert \boldsymbol{\Delta \tau} \Vert _2$$ (9)

$$\operatorname{subject to} \qquad \mathbf{T} ( \boldsymbol{\tau + \Delta \tau}) \doteqdot \mathnormal{G_\zeta}$$ (10)

Solving the System of Equations

• To solve this problem, we replace the equality constraint with its First-Order Taylor Expansion.

  $$\mathbf{T} (\boldsymbol{\tau + \Delta \tau}) \thickapprox \mathbf... ...d\mathbf{T}(\boldsymbol{\tau_{}})}{d\boldsymbol{\tau}}}\boldsymbol{\Delta \tau}$$ (11)

  
  

• This creates a linear equality-constrained least-squares problem (in terms of $\boldsymbol{\Delta \tau}$ which approximates the original problem. We can then use Lagrangian multipliers to solve our system. We iteratively improve our constraint, $${ \boldsymbol{\tau_{i + 1}} = \boldsymbol{\tau_0 + \Delta \tau_{i + 1}}}$$

$$\mathbf{I}\boldsymbol{\Delta \tau}_{i + 1} \quad- \quad\ensuremath{\frac{d\mathbf{T}(\boldsymbol{\tau_{i}})}{d\boldsymbol{\tau}}}^\mathnormal{T} \boldsymbol{\lambda} \quad= \quad\mathbf{0}$$

$$\ensuremath{\frac{d\mathbf{T}(\boldsymbol{\tau_{i}})}{d\boldsymbol{\tau}}}\boldsymbol{\Delta \tau}_{i + 1} \quad- \quad\boldsymbol{0 \lambda} \quad= \quad\mathnormal{G_\zeta} - \mathbf{T} (\boldsymbol{\tau}_{i}) + ... ...hbf{T}(\boldsymbol{\tau_{i}})}{d\boldsymbol{\tau}}}\boldsymbol{\Delta \tau_{i}}$$

• Our matrices are generally small (10-50 variables). This can be easily and relatively quickly solved for $\boldsymbol{\Delta \tau}_{i + 1}$ using a QR factorization and Meschach [#!stewart94:-mesch!#].

Tweaking, other issues

• Hold previous secondary structure fixed

• Implemented in parallel

• Implemented with iterative deepening and optimism

$$\begin{array}{c c} \multicolumn{1}{l}{\mbox{\bf Tweaked \mbo... ...6}} & \multicolumn{1}{l}{\mbox{\bf Score: 75736}} \end{array}$$

$$\begin{array}{c c c} \includegraphics[width=2.5in]{GRAPHICS/... ...lumn{1}{c}{\mbox{\bf Prediction Score: 6941 }} \\ \end{array}$$

Future Work

• Caching of tweaks

• Tweaking and other structures - disulfides and motifs

• Incremental tweaking

• Enter CASP V

No References!

About this document ...

This document was generated using the LaTeX2HTML translator Version 99.2beta8 (1.46)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -split 8 -dir /home/sforman/thesis-html/defense defense

The translation was initiated by Sean Forman on 2001-11-21