...
A matrix is createad where the sequence in which the search is carried out is located vertically, and the searched sequence is located horizontally. Fill the adjacent row and column with 0. Example:
The sequence in which the search is carried out - ACGCGAT.
The searched sequence - CGCG.D(i,j)
C G C G 0 0 0 0 0 A 0 C 0 G 0 C 0 G 0 A 0 T 0 Start filling the matrix from the left top corner moving from left to right and from top to bottom using the following formula:
Where:
D(S1, S2) - current cell,
D(S1-1, S2) - the cell on the left,
D(S1, S2-1) - the cell above,
D(S1-1, S2-1) - the on the top and left,
gap - the Gap open penalty if we meet gap for the first time and the Gap extension penalty if we meet gap the second time or more.
score - the value from the Scoring matrix table.
The following example uses nucl Scoring matrix (+5 for match, -4 for mismatch) and -1 for Gap open and Gap extension penalties:
- Find the greater number and move to the top, left or top-left to the next greater number:
Matching green symbols indicate the desired sequence intersection.
...