# A New String Edit Distance and Applications
## 2 Restricted Forensic Levenshtein Distance
### Details of the RFL Algorithm
#### 2.3.3 Restricted Forensic Levenshtein Distance
However, since RFL includes classical Levenshtein operations and takes the lowest-cost path, inserting the string 'A' will be considered both as a cost 1 edit (from the classical Levenshtein solution) and a cost 4 edit (from the dictionary), with the lower cost option being taken._  
In Example 1, a sequence was shown to demonstrate that an unbounded search space would not be desirable even if it was possible. Example 3 explains how the restriction affects the answer on that use case. **Example 3**. : _In Example 1, it was illustrated that the string_  
\[d= \{\text{insert cost:}\]3  
_would cost 21 to insert from a blank string if no motifs were considered, but it would cost 17 if the cost dictionary for the motif AAAGA contained strings of arbitrary length. The length of the motif AAAGA leads to a bound of \(2\times 5-1=9\) on the dictionary substrings. The RFL algorithm with this bound in place will see parts of the parent string and insert them from the dictionary when it is cheaper to do so. For example, the edit path from a blank string to the motif AAAGA costs 1 via forward stutter and the edit distance from AAAGA to the first six characters of the string, ATTTTA, costs 4 (three substitutions and one insertion), so to insert the first six characters of the string totals 5, whereas inserting each letter individually costs 6. As the RFL algorithm moves along the string, the next place it becomes cheaper to use the dictionary is when inserting ATTTTGI, which would cost 7 with single-character edits, but instead costs 6 via the dictionary (since AAAGA \(\rightarrow\) ATTTTGI requires three substitutions and an insertion). There are no other places where the RFL algorithm finds a more optimal route. Although an unbounded search space would give a cost of 17 and a classical Levenshtein would give a cost of 21, the RFL algorithm with the \(2k-1\) bound gives a cost of 19._  
It must be noted that the sequence in Example 3 was given as an extreme example. Motifs stutter in the data both forward or backward with notable frequency, with vastly fewer single-character edits. It would be vanishingly rare to see as many insertions as this extreme example demonstrates. Although it is a single straightforward step to change the dictionary to include more substrings, doing so will not reflect the true relative frequency of stutter versus single-character insertions and deletions. Each dictionary key accounts for exactly one stutter, whether forward or in reverse. Once substrings of length \(2k\) or more are being considered, it is much more likely that two stutters are at play instead of one, and the case of two stutters is already well-accounted for in the RFL implementation as it stands, since each motif will get treated separately. Rare, more complex theoretical exceptions are described in Appendix A.1. In the RFL algorithm, all edits are fully customizable. Every edit from one nucleotide to another can be set with a unique cost, and every relevant motif can stutter forward and backward with unique costs. The classical Levenshtein distance separately considers the cost of an insertion, deletion, or substitution, and takes the minimum of the three at each step to expand the matrix via dynamic programming. To account for all the substrings accessible via stutter, the RFL algorithm considers the same possibilities as classical Levenshtein, and additionally considers at each step the options of inserting or deleting any \(l\)-character portion, where \(l\) ranges from \(1\) to \(2k-1\), and where the respective cost is defined by the pre-built dictionary.