next up previous
Next: Structural Alignment algorithm based Up: Efficient algorithms for Local Previous: Introduction


Problem Definition of Local structural alignment

INPUT: Given two protein structures $ P_1=(a_{1,1},a_{1,2},a_{1,3}{\ldots})$ and $ P_2=(b_{1,1},b_{1,2},b_{1,3}\ldots)$ where $ a_{i,j}$ represents $ j^{th}$ atom of $ i^{th}$ residue $ P_1$ and $ b_{p,q}$ is $ q^{th}$ atom in $ p^{th}$ residue of $ P_2$ . The value in $ a_{i,j}$ and $ b_{p,q}$ corresponds to 3D-coordinate of that atom, $ a_{i,j}=(X_{j},Y_{j},Z_{j})$ and $ b_{p,q}=(X_{q},Y_{q},Z_{q})$ .
OUTPUT: Define correspondence between $ P_1$ and $ P_2$ as $ C_{1,2} = ((a_{p,q},b_{r,s}),(a_{m,n},b_{k,l}),{\ldots})$ , the Local structural alignment problem asks to find a correspondence ($ C_{1,2}$ ) between $ P_1$ ,$ P_2$ along with a rotational matrix $ R$ and translation matrix $ T$ such that when you apply $ R$ and $ T$ to one set of coordinates ( $ a_{p,q},a_{m,n},\ldots$ ) we would be able to produce the other set in the correspondence ( $ b_{r,s},b_{k,l},\ldots$ ), the optimization version asks for $ \vert C_{1,2}\vert$ to be maximal.



Vamsi Kundeti 2007-10-10