3D Structural Alignment
and
Tunnel Computation
David Sehnal
Contents
• Two Worlds
– 3D Structural Alignment (on the small scale)
– Tunnel Computation
• The Worlds Collide?
2
3D Alignment
• Large scale (proteins)
– Global (classification,
evolutionary links)
– Local (compare smaller sub-
structures)
• Small scale
3
3D Alignment
• What we need?
– Know which atoms/amino acids/… belong
together
– Find a transformation that fits the corresponding
pairs
4
Rotation component
Translation component
Maximize thisStays the same
The Transformation Part
• Horn K.P.: Closed-form solution of absolute orientation using unit
quaternions, Journal of the Optical Society of America, 1986.
• Karney C.F.F.: Quaternions in molecular modeling. Journal of Molecular
Graphics and Modelling, 2007.
5
Pairing the Elements
• Large Scale
– Usually work on the secondary structure (amino
acids)
– Combinatorial extensions, subgraph isomorphism,
dynamic programming, …
• Small Scale
– Usually work on 3D structure
– Exhaustive search, pairing based on distance,
subgraph isomorphism, …
6
(My) Simple Algorithm
1. For each bijection f: Atoms(A) -> Atoms(B)
– Align sequences f(A) and B using the quaternion
method
2. Return the alignment that yields the lowest
RMSD
• Improvement for small protein substructures:
– Grouping of atoms
C
S
O
NCYS
7
Applications
Reverse Proteins
Classification
Lectines
66 structures
56 atom on each
Apoptosis
Analysis of the
model structure
8
(Sort of Mine) Better Approach
• Hoppe A., Frommel C.: NeedleHaystack: a program for the rapid recognition of
local structures in large sets of atomic coordinates, Journal of applied
crystallography, 2003.
• Find sets of 3 suitable pivots in each structure
• For each pair of pivot sets
– Align the structures using these pivots (quaternions)
1. Match atoms based on distance (with a threshold)
2. Align again (quaternions)
3. (Goto 1 until a stable configuration is reached)
– Score = f(A, B, RMSDM)
• Return the alignment with the best score
M is the set of matched atoms, N is the total number of
atoms, and RMSDM is the RMSD of matched atoms.
9
Example (FeN4S2)
10
Example (FeN4S2)
11
Example (FeN4S2)
12
Scoring
SiteBinder Needle-Haystack
# of matched atoms
RMSD
M is the set of matched atoms, N is the total number of atoms, and
RMSDM is the RMSD of matched atoms.
13
Different Pivot Criteria (Charges)
14
RM
2 says how well the matched charges correlate.
3D Alignment Summary
3D structural alignment using pivot elements and
improved scoring function to identify the correct
result.
15
Tunnels
• MOLE, Caver, Hollow,
MolAxis
• Static analysis vs.
dynamics
• Grid/Triangulation
Based
16
Protein (Delaunay) Triangulation
• Edelsbrunner H., Liang J.: Anatomy of protein pockets and cavities:
measurement of binding site geometry and implications for ligand design,
Protein Science, 1998.
17
Finding the Tunnels – The Idea
18
Tunnel Finding Algorithm
1. Triangulate the molecule (Voronoi diagram)
2. Specify starting point (from a database/user)
3. Do depth-first (A*) search
– Each time a boundary tetrahedron is visited,
report a tunnel
– Edge weight ~ amount off space around the edge
4. Post-process the tunnels (remove duplicate
tunnels, …)
19
(My) Modified Approach
1. Triangulate the molecule (Voronoi diagram)
2. Identify cavities (“empty space”)
– Remove tetrahedrons that are too big or too small
– Find connected components in the new graph
3. Identify start points within cavities
– Deep point(s) in each cavity
– Database/user
4. Identify end points within cavities
– Connected components of the “boundary”
5. For each pair of start and end points in the same cavity
use Dijkstra’s algorithm to find the tunnel
1. Edge weight ~ amount of space around the edge
6. Post-process the tunnels (remove duplicate tunnels, …)
20
The Cavities
21
Start and End Points
22
Depth Computation
23
The Tunnels
24
Tunnel Computation Summary
Triangulate the protein, split it into smaller
graphs and use Dijkstra’s algorithm to find
interesting paths (= tunnels) in them.
25
Aligning the Tunnels/Cavities
?
Reduced Cavity Graph 26
Summary
• 3D Alignment Algorithm
• Tunnel Finding Algorithm
27
Future Work
• Combine 3D structural alignment and tunnel
computation
• (Write PhD thesis about it)
28
Thank you for your attention.
29