Transcript Exact Point Matching in R2

Alignment of Flexible
Molecular Structures
Motivation
Proteins are flexible. One would like to
align proteins modulo the flexibility.
Hinge and shear protein domain motions
(Gerstein, Lesk , Chotia).
Conformational flexibility in drugs.
Problem definition
Flexible Geometric Hashing
Exploit the fact that neighboring parts share
the joint - accumulate mutual information at
the joint.
Achieve complexity of the same order of
magnitude as in rigid alignment.
Flexible protein alignment
without prior hinge knowledge
FlexProt - algorithm

detects automatically flexibility regions,

exploits amino acid sequence order.
Motivation
Geometric Representation
3-D Curve
{vi}, i=1…n
Experimental Results
Experimental Results
FlexProt Algorithm
Input: two protein molecules A and B, each
being represented by the sequence of the
3-D coordinates of its Ca atoms.
Task: largest flexible alignment by
decomposing the two molecules into a
minimal number of rigid fragment pairs
having similar 3-D structure.
FlexProt Main Steps
Detection of Congruent
Rigid Fragment Pairs
Joining Rigid
Fragment Pairs
Clustering
(removing ins/dels)
Rigid
Structural Comparison
Structural Similarity Matrix
Congruent Rigid
Fragment Pair
Detection of Congruent Rigid Fragment
Pairs
k+l-1
k
i-1
t
i+1
i
j-1
j
t+l-1
j+1
vi-1 vi vi+1
wj-1 wj wj+1
Fragkt(l) =
vk
wt
…
…
vi ... vk+l-1
wj … wt+l-1
RMSD (Fragkt(l) ) < e
RMSD Computation
Vi …... Vi+l
P=
Wj ...… Wj+l
Vk …... Vk+m
Q=
Wt ...… Wt+m
P UQ
RMSD( P )
RMSD( P U Q ) in O(1) time
RMSD( Q )
NOT O( |P|+|Q| )
FlexProt Main Steps
Detection of Congruent
Rigid Fragment Pairs
Joining Rigid
Fragment Pairs
Clustering
(removing ins/dels)
Rigid
Structural Comparison
How to Join Rigid
Fragment Pairs ?
Graph Representation
Graph Node
Graph Edge
Graph Representation
•The fragments are in ascending order.
•The gaps (ins/dels) are limited.
•Allow some overlapping.
a
b
+ Size of the rigid fragment pair (node b)
- Gaps (ins/dels)
Penalties
- Overlapping
Graph Representation
W_t
• DAG (directed acyclic graph)
Optimal Solution ?
W_t
•“All Shortest Paths”
O(|E|*|V|+|V|2) (for DAG)
•“Single-source shortest paths”
O(|E|+|V|)
FlexProt Main Steps
Detection of Congruent
Rigid Fragment Pairs
Joining Rigid
Fragment Pairs
Clustering
(removing ins/dels)
Rigid
Structural Comparison
Clustering (removing ins/dels)
T1
T2
If joining two fragment pairs gives small RMSD (T1 ~ T2)
then put them into one cluster.
FlexProt Main Steps
Detection of Congruent
Rigid Fragment Pairs
Joining Rigid
Fragment Pairs
Clustering
(removing ins/dels)
Rigid
Structural Comparison
Correspondence Problem
Molecular Surface
Representation
Applications to docking
Motivation
Prediction of biomolecular recognition.
Detection of drug binding ‘cavities’.
Molecular Graphics.
1. Solvent Accessible Surface – SAS
2. Connolly Surface
Connolly’s MS algorithm
A ‘water’ probe ball (1.4-1.8 A
diameter) is rolled over the van der
Waals surface.
Smoothes the surface and bridges
narrow ‘inaccessible’ crevices.
Connolly’s MS algorithm - cont.
Convex, concave and saddle patches
according to the no. of contact points
between the surface atoms and the
probe ball.
Outputs points+normals according to the
required sampling density (e.g. 10 pts/A2).
Example - the surface of crambin
Critical points based on Connolly
rep. (Lin, Wolfson, Nussinov)
Define a single point+normal for
each patch.
Convex-caps, concave-pits, saddle belt.
Critical point definition
Connolly => Shou Lin
Solid Angle local extrema
hole
knob
Chymotrypsin surface colored by solid
angle (yellow-convex, blue-concave)