The algorithm

We can roughly divide the SSGS algorithm into two stages (1) creating a set of transformations of a candidate protein that match fully or partially a target protein and (2) using dynamic programming to rank that transformation set. We use the dynamic programming score of the superimposition iteratively to refine the superimposition until we reach convergence. As depicted in the figure below.

 

The dynamic programming

The alignment and its evaluation are performed by a dynamic programming recursion aimed at achieving an affine mismatch topology dependent alignment that favors a smaller number of long mismatched regions over many short mismatched regions and punishes more strongly mismatches in a-helix and in ß-sheet structures over assigned loops. In a affine mismatch alignment there is a preference for longer mismatch regions over shorter ones. A mismatch between two residues means that the two residues are not spatial neighbors.

• An affine mismatch alignment

  Prior to the dynamic programming recursion, we preprocess the proteins and translate the input into a spatial neighboring relations matrix (SNRM), R (MxN). The input is the Ca atomic coordinates of the model and target proteins, with lengths of M and N, respectively. We index the Ca atoms according to their location on the backbone, starting from the N terminal side, and set all the values in R to a mismatch. For every Ca(j) atom of the model, we compute its Euclidian distance to every Ca (i) atom of the target. If the distance is smaller than radius r and Maximal shift value, we set R(i,j) to a match between Ca(i) and Ca(j). The latter condition excludes matches between residues whose indices along the protein sequence are distant from each other. Accordingly, if Cai and Caj are spatially distant from each other, we set R(i,j) as a mismatch.

 

• After the creation of the SNRM, we have to determent the favorable path through the spatial matrix which will illustrate which residues to set as matches,mismathced or gaps. The path is determent by the movment type of each step along the path for example (the figure below) moving from the cell (2,2) to cell (3,3) illustrates a movment from a Match cell (i.e. the residue 2 in the target is a spatial neighboor of the residue 2 in the model) to a Mismatch cell (i.e. the residue 3 in the target is not a spatial neighboor of residue 3 in the model). Therefore there are 4 possible movments as depicited in the figure below.

This notion enables us to give every diagonal movment the proper weight and enforce an affine mismatch alignment i.e opening a mismatch will alwayes be more expensive (score wise) than continuing an already open mismatch. Therefore the choosing a movment along the SNRM depends on three factors: (1) The value of the previous cell. (2) Whether the cell is a match or a mismatch.(3) Whether the next cell is a match or a mismatch.

In an affine gap alignment algorithm at every stage we check whether opening a new gap will be cheaper then continuing and older one. Therefore, we also keep for every cell the value of the best route to it ending with a gap from both direction up and left.

In order to introduce into the affine mismatch algorithm also an affine gap nature we have to define between different gaps according to the cell the gap begins from. (remainder: a gap is to skip a residue or a few residues in the alignment, a mismatch is to define two residues a pair of mismatches residues that are spatialy a part). Therefore, in order to find the best movement at each step of the algorithm, we have to compare five values as depicted in the figure below: As can be seen th ered arrow number illustrates a movment from a mismatched cell with opening a gap and three gaps to another mismatched cell. computing such a momvent will take into account the value the path for reaching the red cell, opening a gap and taking three additional gaps and a payoff for continuing a mismatch region.