Computing the actual Local structural alignment

With all the relevant background at this stage we now describe our algorithm which finds highly similar sub-structures between two proteins $P_1$ and $P_2$ for details on how the atomic coordinates in $P_1$ and $P_2$ are described please refer to section3.1. And let ${L^1}_{pdb}$ and ${L^2}_{pdb}$ be the linear list of atoms as described in section3.1,the details of our algorithm can be summarized as follows.

1. Select a window of size $w$ , slide it across the list's ${L^1}_{pdb}$ and ${L^2}_{pdb}$ . Let ${S^1}_i$ be the atoms from ${L^1}_{pdb}$ at a position $i$ in list ${L^1}_{pdb}$ , similarly define ${S^2}_j$ for atoms within the window at position $j$ in ${L^2}_{pdb}$ .
2. For every such ${S^1}_i$ , ${S^2}_j$ $1\leq i,j \leq n$ , compute ${V^1}[i]$ , ${V^2}[j]$ , which are the same vectors in Algorithm1
3. Define a cost matrix $C_{i,j} = W_{i,j}$ , where $W_{i,j}$ is the weighted distance (defined in section3.4) between vectors ${V^1}[i]$ and ${V^2}[j]$ (defined in above step each of size $w$ ).
4. Use a variation of our dynamic programming(see Algorithm4 we will explain this in the next section)algorithm, the algorithm is similar to Longest Common Substring (Please note the difference between Substring and Subsequence both are different problems).

Now we give algorithms corresponding each of the steps described steps 1&2 are done by Algorithm3, steps 3&4 are performed by Algorithm4. Finally we put all these into a high-level Algorithm5 for better understanding. boxed

boxed

boxed

We have given the details of our Local Structural Alignment algorithm which starts with LocalStructAlign (Algorithm5) and produces a metric called the Z-Score we use this metric in finding the closest structurally similar proteins. In the next section we describe how we use the Z-Score computed by Algorithm5 in classification of the protein into classes and super families.We also describe on how we used Algorithm5 in finding structural motifs in section5.