# A New String Edit Distance and Applications
## 2 Restricted Forensic Levenshtein Distance
### Details of the RFL Algorithm
#### 2.3.3 Restricted Forensic Levenshtein Distance
Note that _any_ string with the letters AAAGA (in that order) would be cheaper to insert by first stuttering forward and then adding letters in between, instead of adding them one by one. This is shown in Example 1 to motivate the need for restricting the search space. The resolution of this example after the restrictions are in place will be shown in Example 3. **Example 1**. : _To build the string_  
\[\text{A(TTTT)A(TTTT)A(TTTT)G(TTTT)A}\]  
_using edit operations starting with an empty string, 21 letters would need to be inserted, for a cost of 21. This would cost 4 less overall by inserting the motif AAAGA first via stutter (cost of 1) and then inserting all the remaining nucleotides in between (cost of 16), for a total cost of 17. This is true for an unboundedly long string, with any number of characters in between the motif characters as long as the letters AAAGA are present in that order._  
Even if a string had the letters A...A...A...G...A with 2000 nucleotides in between each letter, by including it in the dictionary, the algorithm would qualify it as a modified stutter motif. Thus, not only is an infinite (or virtually infinite) dictionary impossible, it is undesirable and potentially absurd. In addition, there is no evidence to suggest that PCR results in such drastic numbers of errors. The faithfulness of the polymerase used in PCRs for STR typing has improved enough that these only err sporadically, which is supported by the fact that only small deviations were observed in artifacts in this study. Such assignment of stutter cost over excessive length of the string is undesirable, therefore a limit to the extent of the modification was incorporated. The appendix contains more detailed discussion regarding the complex cases that arise when considering this additional edit type, but a few examples are included here. As mentioned previously, it is possible to have intra-motif substitutions and indels. The STR [ACT]4 could give rise to [ACT]2 AT [ACT]1. The difference in the number of ATG motifs here is \(4-3=1\), but there was no stutter--just deletion of the letter C. Including the interaction of stutter with other edit types quickly explodes complexity in the minimal cost computation. Thus, for every possible nucleotide sequence of length \(\leq 2k-1\), where \(k\) is the length of the motif, the classical, weighted Levenshtein distances of both inserting these strings from scratch or deleting them are computed, with the requirement that the edit path of that substring contains exactly one stutter. Specifically, the precomputed insertions contain short sequences of letters with an associated cost, assuming the edit path begins with a motif insertion. The precomputed deletions contain the same strings as the insertion list, but with the cost of deleting, assuming the edit path ends with a motif deletion. These data are stored in a pair of dictionaries. In the GitHub resource, this function is called lsdp, an acronym standing for Levenshtein Stutter Dictionary Pair. Specifics are illustrated in Example 2. **Example 2**. : _For the motif TCTA, the stutter dictionary \(d\) has two keys: 'insert cost' and 'delete cost'. Each of these keys gives a dictionary \(d[key]\) of substrings and their associated costs. A selection is given as follows, where all edit costs equal to one--note that the insert and delete dictionaries will always contain the same entries, but different entries are shown here to demonstrate different costs:_  
\[d= \{\text{insert cost:}\] \[\{\text{TCTA: 1,}\] \[\text{TCTAT: 2,}\] \[\text{A: 4,}\] \[\text{GGGGGG: 8,}\] \[\text{...}\},\] \[\text{delete cost:}\] \[\{\text{TCTATGG: 4,}\] \[\text{TCT: 2,}\] \[d= \{\text{insert cost:}\]0 \[d= \{\text{insert cost:}\]1 \[d= \{\text{insert cost:}\]2  
_Note that strings like 'GGGGGGGG' and 'A' cost more to insert in this dictionary than they do in classical Levenshtein, since the RFL algorithm first inserts a motif for a cost of 1 before modifying it into the desired string. A symmetric fact holds for deletion entries.