# A New String Edit Distance and Applications
## 1 Introduction
### Short Tandem Repeats  
The DNA identification community commonly uses short tandem repeats (STRs) as their genetic marker of choice [11; 12]. STR typing methods are accurate and sensitive [13]. The work in this paper is designed for the analysis of DNA samples in forensic applications,but the methods presented here can be applied in other areas that use STR analysis. An STR is a region of DNA that contains consecutively repeating motifs. To the left and right of this repeating region is a non-repeating section of DNA called a _flanking region_. For example:  
ACTCC ATG ATG ATG ATG GGTTCTGA  
Here the motif ATG is repeated four times, which is represented in a short format as [ATG]4. As sequencing technology has developed, individual nucleotides within STR regions in the human genome can be measured increasingly economically and accurately, whereas in the past people were limited to measuring the total length of the targeted sequence. The standard length-based CE methods do not allow for the detection of intra-motif variations. For a real-data example, consider a sample with a two-allele locus with repeat regions  
A: [TCTA]8 [TCTG]1 [TCTA]1  
and  
B: [TCTA]10. Note A and B are identical by length. When both alleles at a locus share the same length but differ by sequence, they are known as _isometric heterozygotes_, and CE methods cannot discriminate between them. CE types both of these alleles as 10, an allele with a length of ten repeats, and classifies this sample as homozygous at this locus. By recognizing variation at the sequence level, the power to discriminate between individuals increases [14]. If an artifact sequence C = [TCTA]7 [TCTG]1 [TCTA]1 was detected in the sequencing output, it would be reasonable to infer that there is a higher likelihood of it being an error derived from A rather than B, since fewer changes are required to edit A into C than B into C. Consequently, it would make sense to infer that the artifact is related to A. With CE, A and B are viewed as identical, and no such conclusions about the artifact can be made. As crime scene samples are most often mixtures, the additional resolution of the alleles and artifacts provided by the use of sequencing can be advantageous compared to solely length-based analysis. In STR regions, motifs often expand and contract as a unit. This phenomenon of slippage of the polymerase on the template is referred to as _stutter_. The artifacts of in vitro stutter products are consistently present in measurable quantity and therefore are accounted for in routine forensic DNA analysis [15]. Furthermore, stutter occurs in vivo in STR regions even at conservative estimates at least 3-4 orders of magnitude more often than other random point mutations [16]. To reflect this, a generalization of string edit distance was used to capture similarity between sequences in MPS output. The goal was to include the addition or deletion of a motif as an edit type with a cost that can vary independently from single-nucleotide edits, to reflect the fact that these motif losses and expansions (called _backward_ and _forward_ stutter, respectively) occur consistently across various in vitro applications [17]. The proposed algorithm is also applicable to in vivo methods such as rare disease diagnosis and cancer progression tracking that use STR markers including their stutter [16]. It is desirable to develop a distance that gives high-frequency artifacts a lower distance to the true alleles than low-frequency artifacts, so it is important to capture both reverse and forward stutter as low-cost events. Standard string edit distances such as the Levenshtein distance modify one character at a time, so the cost of dropping or adding a multi-character motif is necessarily equal to the sum of the costs of dropping or adding the individual characters. Furthermore, unique motifs can stutter within a single STR region, with each motif having a potentially unique cost.