The distance between two sequences
In this tutorial, we will focus on exhaustive methods.
These methods are based on dynamic programming.
Let a and b the two sequences, of length m and n, we want to compare.
ai and bj denote the ith base of the sequence and the jth base of the sequence b, respectively.
Let us define d(ai,bj) as the distance between the two sub-sequences of length i+1 and j+1 beginning by a0 and b0, respectively.
In this simple case, the distance will correspond to the minimal amount of deletion, insertion, substitution of bases we need to apply to transform one sequence to the other.