# A New String Edit Distance and Applications
## Appendix A
### An Algorithmic Limitation  
It is possible to weight the costs unequally enough that interferes with the output of the original Levenshtein. If the insert cost of C is 5, but every other edit cost is 1, then the actual cost of inserting a C is 2, since one could insert any other letter (+1) and then substitute in a C (+1). However, the Levenshtein function in the Weighted Levenshtein package available in Python does not reflect this. It will return _lev_(\", C) = 5, not 2.  
Forcing all insert costs to be the same in a given example actually avoids this issue altogether--for example, the stringdist package in R does not allow for individual insertions to have different costs from one another [34; 35]. All deletions must cost the same, as well, as do substitutions.  
If the insert cost of C is 1.5, for example, and every other edit cost is 1, then the cost of inserting a C is legitimately 1.5, since any other possible path returns at least 2. In order to have truly minimal-cost answers, then, it is necessary to enter in the individual edit costs in the standard Levenshtein function as minimal (e.g., insertion cost of any letter needs to be less than the sum of any other possible edit sequence to insert that letter indirectly).  
Insertion is not the only place where this is a problem. If the cost of A \(\rightarrow\) T was 5, but all other costs were 1, then A \(\rightarrow\) C \(\rightarrow\) T would cost 2, so A \(\rightarrow\) T should cost 2. A similar example could be constructed for deletion.  
The same does not hold true for stutter, however. If the forward stutter cost was raised to 15 and the backward stutter cost raised to 10 in the RFL algorithm, the matrix for the RFL distance (which is equal to the standard Levenshtein matrix) is shown in Table 12.  
There are no costs of 10 or higher, since it is never cheaper to stutter than to address each nucleotide separately. Thus, the addition of motifs to the Weighted Levenshtein package does not suffer from the same weaknesses. Because it uses the package as a base, though, it still has the same problems as the original Levenshtein distance with the other edit operations.  
The solution to this issue is a pre-processing step to ensure that the individual edit costs are already optimal prior to the application of the Levenshtein distance. It is more complicated than, e.g., ensuring that a two-step insert-substitute path is not cheaper than direct insertion. Pathological counterexamples exist that require more than two steps--a demonstration is shown in Example 13.  
\begin{table}
**A** & 1 & 0 & 1 & 2 & 3 & 4 & 5 \\ \hline
**C** & 1 & 1 & 0 & 1 & 2 & 3 & 4 \\ \hline
**G** & 3 & 2 & 1 & 0 & 1 & 2 & 3 \\ \hline \hline \end{tabular}
\end{table}
Table 11: RFL with high stutter penalties.  
**Example A2**.: _In a case where the following costs are set:_  
* _Cost to insert a C, T, or G: 10_
* _Cost to insert an A: 1_
* _Cost of T_ \(\to\) _C, A_ \(\to\) _C, or A_ \(\to\) _G: 10_
* _Cost of G_ \(\to\) _C, A_ \(\to\) _T, or T_ \(\to\) _G: 1_  
_Then in order to insert a C, it is cheaper to edit \"\(\to A\to T\to G\to\) C for a total cost of 4 than it is to insert a C directly (10), but one cannot go \"\(\to A\to\) C (cost of 11) or \"\(\to A\to T\to\) C (cost of 12)._  
In the application the RFL was designed for, however, all deletions cost the same, all insertions cost the same, and all substitutions cost the same, so this issue is avoided.  
The RFL algorithm is based on the idea that the sequences undergoing the edits in PCR should take the cheapest, most frequent path. Here distance is defined to be the lowest possible cost of any edit path between the strings (regardless of whether the minimal path is itself unique), with no penalty on the number of steps. The implementation of edit count penalization to the algorithm is an area of interest for future work.