Minimum Edit Distance
The minimum edit distance between two strings Is the minimum number of editing operations. Insertion Operation Deletion Operation Substitution Operation Needed to transform one string into the other string. Two strings and their alignment: If each operation has cost of 1, Distance between these is 5 If substitutions cost 2 (Levenstein), Distance between them is 8 Alignment in Computational Biology Given a sequence of bases AGGCTATCACCTGACCTCCAGGCCGATGCCC TAGCTATCACGACCGCGGTCGATTTGCCCGAC An alignment: Given two sequences, align each letter to a letter or gap How to find the Minimum Edit Distance ? Searching for a path (sequence of edits) from the start string to the final string: ◦ Initial state: the word we’re transforming ◦ Operators: insert, delete, substitute ◦ Goal state: the word we’re trying to get to ◦ Path cost: what we want to minimize: the number of edits You can also see the video of solving minimum e...