It is very simple algorithm modifying SmithWatermanAlgorithm. It can be applied to searching repetitive [Motif] finding.

It is slightly different from SmithWatermanAlgorithm on the DynamicProgramming matrix, especially on the F(i,0).

• In normal SmithWatermanAlgorithm, there are two choices for F(i,0).

  • F(i,0) = max { 0, F(i-1,0) - d }

    • where d means gap penalty.

  But in the RepeatedMatchMethod, there are different two choices for F(i,0).

  • F(i,0) = max { F(i-1,0) , F(i-1,j) - T }

    • where T is threshold of RepeatedMatchMethod and j is the row number of the location which the highest score is recorded in the F(i-1, all numbers ).

  and another difference is the F(i,j)'s selection.

  • F(i,j) = max { F(i,0) , F(i-1,j-1)+s(xi+yi) , F(i-1,j)-d , F(i,j-1)-d }

    • compare this selection with the SmithWatermanAlgorithm's.

-- From the book named BiologicalSequenceAnalysis (written by RichardDurbin).