# A New String Edit Distance and Applications
## 2 Restricted Forensic Levenshtein Distance
### Forensic Distance Overview  
The STR regions of DNA that are currently used for forensic identification were historically selected based on the polymorphic length variations of these markers observed in the population. Most of these are tetranucleotide repeats, but di-, tri-, penta- or hexanucleotide repeats also exist in the tandem oriented arrays. At sequence level a trinucleotide marker can be described as a string such as ACTACTACTACT, or abbreviated, as in [ACT]4. Backward stutter refers to losing a motif, or [ACT]3 in this example. Less-common forward stutter refers to gaining a motif, or [ACT]5 here. There are other possibilities, such as substitution, e.g., [ACT]4 to changing into an [ACT]2 AGT [ACT]1 via a C \(\rightarrow\) G substitution, but the individual single-character edits are significantly rarer than motif stutter, and are already taken into account under the classical Levenshtein distance. Stutter is more common than insertion or deletion, so it is modeled as a separate edit type. This enables the cost of stutter in the edit distance to be lowered to reflect its higher probability, instead of modeling it as the sum of individual nucleotide changes. In order to accomplish this, the RFL algorithm includes a step of looking at a set of substrings of various lengths with their associated costs from a precomputed dictionary. Whereas the standard dynamic programming solution looks back a single letter, the proposed approach looks back several letters. The particular dictionary of substrings is what gives the RFL algorithm the title \"restricted\", since the size of the dictionary limits how far back the algorithm looks. A naive approach would be to count the difference in the number of motifs and use the classical Levenshtein distance of the flanking regions, but this method misses vast numbers of edit interactions, and further misinterprets single-character edits in the STR region as stutter, e.g., [ACT]4 editing to [ACT]3 AGT would be qualified under a naive approach as back stutter, since there is one fewer ACT motif, but inspection clearly reveals a C\(\rightarrow\) G substitution. The complexity of the solution developed in this paper comes from the correct distinction of single-character edits and stutter, and the interaction of multi- and single-character edits. For example, the sequence [ACT]4 could change to [ACT]5 via forward stutter, then a C could be deleted, for a final result of [ACT]4 AT. This final string could have been attained by inserting the letters A and T from the original [ACT]4, but another option was the forward stutter and single nucleotide deletion. Different edits contribute different (customizable) costs, so one route may be more optimal than the other depending on the parameters. Extending these interactions across multiple edits becomes exponentially complex, as motifs can stutter forward and then characters can insert into the middle of that motif, for example, or a SNP could occur which turns a substring into a motif that can then stutter back, and neither of these would be detected by a naive approach. For example, if ACT were the motif, detecting the string GACGT as a three-edit insertion (one forward stutter, two single-character insertions) instead of five, or detecting TCT as a two-edit deletion instead of three, is a powerful capability, especially when considering that each edit can have vastly different costs. The RFL algorithm handles insertions, deletions, and substitutions, the addition and deletion of prespecified character motifs, and the overlapped interactions of the multi- and single-character edit types. A comparison between classical Levenshtein, the naive approach, and the RFL algorithm is shown in Table 1.  
Theoretical complexities arise when considering these edit interactions, as addressed in Example 1, Section 2.3.3, and Appendix A.1. These complexities are unbounded, so it is necessary to restrict the search space. However, the flexible parameter restrictions are required to accurately model the underlying sequence behavior.