# A New String Edit Distance and Applications
## 2 Restricted Forensic Levenshtein Distance
### Implementation of the RFL Distance
#### 2.4.1 Building the First Row  
The cost of editing an empty string into an empty string is 0, so \(d[0,0]\) is always 0. The element \(d[0,1]\) is the cost of editing an empty string into the first character of the child string \(b\). A list of cost options at this step will be made and then the minimal cost option taken. Obtaining the first character can either be done by inserting it directly or by stuttering forward a motif and then deleting characters back. For example, if the first character of the string \(b\) was G, and the motifs being considered were GGC and ATTC, then the following costs would be appended to the options list:  
* The insert cost of the character G
* The cost of stuttering forward GGC plus the cost of the weighted Levenshtein distance from GGC to G.
* The cost of stuttering forward ATTC plus the cost of the weighted Levenshtein distance from ATTC to G.  
Each motif can have a different stutter cost associated with it that can vary across loci, and in forensic applications forward stutter will be more expensive than backward since it is a rarer artifact. In this example, GGC might cost 3 to stutter forward and 1 to stutter backward, while ATTC might cost 2 to stutter forward and 0.5 to stutter backward.  
The quantity \(d[0,1]\) is the minimum of the computed options, and the algorithm moves forward to \(d[0,2]\). Now there are several possibilities:  
* \(d[0,1]\) + the cost of inserting the second character via pure insertion (i.e., the cost of inserting \(b[1]\), using 0-based indexing)
* \(d[0,1]\) + the cost of inserting the second character via the stutter dictionary (for each stutter dictionary)
* \(d[0,0]\) + the cost of inserting the first two characters via the stutter dictionary (for each stutter dictionary)  
Furthermore, in general, for each motif, if the motif lengths are \(k_{i}\), for every length \(j\) less than or equal to \(2k_{i}-1\), substrings of characters from \(j\) positions back to the current can be checked, and if less costly those characters can be inserted via the stutter dictionary. It is impossible to look back further than the beginning of the string, however.  
To construct the first row \(d[0,:]\), pseudocode outlined in Listing 1 is followed. Building the first column \(d[:,0]\) follows similarly.  
```
1 parent_length=lengthofparentchild
2 child_length=lengthofchild
3k=lengthoflongestmotifbengconsidered
4 lookback=2k-1
5d=matrixofzeroswithparent_length+1 rowsandchild_length+1 columns
6
7 forifrom1 tochild_length:
8
9 sfindd[0,i],thecostofmodifyingablanksstringintothefirsticharactersofthechildstring
10 sd[0,0]isalways0,thecostofeditinganemptystringintosanemptystring
11
12 options=[]
13
14 sd[0,i-1]isthecostofinsertingthefirsti-1 charactersofthechildstring
15 options.append(a[0,i-1]+costofinsertingcharacteri)
16
17#lookback1,2,...,and2k-1 charactersinthestring(orbacktothefirstcharacter,whichevercomesfirst)
18 forjfrom1 tomin(lookback,i):
19
20#findthecostofinsertingthelastjcharactersuptoandincludingcharacteri,assumingaforwardstutterhappenedfirst
21
22s=thejcharactersimmediatelyprecedingandincludingcharacterjofthechildstring
23
24 foreverymotifbengconsidered:
25
26#iftherearemotifbunequalsize,therewillbesubstringsintheditionaryofthelargermotifbthatareoutofreachofthesmallermotif,sincethedictionaryforamoffoflengthLonlyincludesstringsoflength2L-1
27
28 ifSisnottoolongfortheforward-stutterdictionaryforthismotif:
29
30 options.append(a[0,i-j]+costofinsertingSfromdictionary)
31
32#thecostatthislocationisthesmallestcostoutoftheoptionsconsidered
33#[0,i]=minimumofttheoptionslist
```  
Listing 1: Building the first row of the dynamic programming matrix in the RFL algorithm.