Page History

...

To use the plugin open a nucleotide or protein sequence in the Sequence View and select the Analyze ‣ Find pattern [Smith-Waterman] item in the context menu. The Smith-Waterman Search dialog appears:

Image Modified

Algorithm

This search algorithm has a huge calculation time advantage over the usual Search in sequence algorithm for large sequences. It happens, because the "Search in sequence" algorithm represents a suffix algorithm - one sequence moves along the other and areas opposite each other are иуштп compared. Using this approach, the computation time increases in direct proportion to the length of the sequence. The Smith-Waterman algorithm represents absolutely another approach - searching using a certain kind of matrices.

...

1. 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

2. 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,
   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:

    

   
   

3. 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.

...

• If you want to save the results as annotations input the annotations saving parameters (Annotation name, Group name, Annotation type, Description and a file to save the annotation to). Also you can add qualifier with corresponding pattern subsequences to result annotations. Check the corresponding checkbox for it.
• If you want to save the results as multiple alignment select the following parameters:

Image Modified

Here you can select a file to save the alignment to (Alignment files directory path parameter).

...