# A New String Edit Distance and Applications
## 2 Restricted Forensic Levenshtein Distance
### Details of the RFL Algorithm
#### 2.3.3 Restricted Forensic Levenshtein Distance  
Here the full steps of the RFL algorithm are presented. To compute the distance between strings \(a\) and \(b\), if \(a\) is the empty string, simply insert each character of \(b\), and the number of those insertions is the cost. If \(b\) is the empty string, delete each character of \(a\), and the number of those deletions is the cost. If the first characters of \(a\) and \(b\) are the same, then delete \(a[0]\) and \(b[0]\) for no cost and the overall distance will be the same as the Levenshtein distance between the remainder of the strings \(a[1:]\) and \(b[1:]\) (denoted as tail(\(a\)) and tail(\(b\)), respectively). In case the first characters of \(a\) and \(b\) do not match, line the two strings on top of each other with \(a[0]\) aligned to \(b[0]\), with all edits being made to the parent string \(a\) (this becomes important later, when the distance becomes asymmetric). The goal of the RFL algorithm is to make the leading characters of the strings match, in which case the matching leading characters can be deleted _for free_. For instance, the distance from CAT to CGT is the same as from AT to GT, since the leading C does not require editing. Returning to the aligned strings \(a\) and \(b\), there are three options. The first is that the leading character of \(a\) can be changed into the leading character of \(b\), which corresponds to substitution errors in PCR. A new leading character of \(a\) can be inserted to match the leading character of \(b\), which corresponds to insertion. Lastly, the leading character of \(a\) can be deleted so that the new leading character of \(a\) matches the leading character of \(b\), which corresponds to deletion. The goal is to be able to include the deletion or insertion of multiple consecutive letters as a separate edit type at a reduced cost. The classical Levenshtein solution is capable of gaining or losing multiple letters, but the cost will always be the sum total of the costs of the necessary single-character interim operations. The classical Levenshtein algorithm looks at a character and determines what operation at that position gives the lowest cost to change a single letter at that spot when changing one string into another. It does this iteratively, breaking the original problem into sub-problems by addressing a single letter at a time. The RFL modification further looks at multiple characters at once. This will correspond to looking back several positions within the dynamic programming matrix. Only particular substrings will be allowed as their own edit types, as opposed to any general substring. The RFL solution is to create a dictionary of multi-character substrings and their associated insertion and deletion costs. When a substring--for example CTG--needs to be inserted or deleted, the relevant cost associated with that substring in the dictionary is retrieved, and that option is included for the algorithm to consider when taking a minimum cost step at that index. This substring CTG corresponds to looking back three steps in the dynamic program. For the sake of illustration, assume unit costs for all edits, and consider AAAGA, the motif at the Penta D locus. If AAAGA is permitted to be added or deleted all at once, then inserting AAAA will be cheaper if AAAGA is first built and then the G deleted. Inserting AAA would cost the same either way: inserting 3 As, or inserting AAAGA (+1) and then deleting an A (+1) and deleting a G (+1). Inserting AAAGTA would cost 2 (+1 to stutter and +1 to insert), as opposed to costing 6 by inserting one at a time. The RFL algorithm needs to account for this, or else it would give the string AAAGTA a cost of 6 because the motif AAAGA is \"broken\" by the T.  
The question naturally arises: if costs are being precomputed for different substrings, which substrings should be included? Suppose that for a specific motif (e.g., AAAGA), all possible substrings and their associated costs were included.