# A New String Edit Distance and Applications
## 1 Introduction
### Background  
DNA-based human identification is an extremely powerful tool with many important applications such as identification of perpetrators of crimes, disaster victim identification, DNA typing of skeletal remains, and relationship testing [7; 8; 9]. The same methods are also applicable in food authenticity, poaching, and counter-bioterrorism [10]. DNA measurement technologies have made great strides recently, and now even minute quantities of DNA can be reliably measured [10].  
In forensic DNA testing, genetic material present at a crime scene is extracted and amplified through the polymerase chain reaction (PCR). In principle, this technology replicates specific regions of the human genome present in the sample by a repeated process of doubling. Errors may get introduced to the products during the PCR process, and these error sequences are called _artifacts_. Traditionally, analysis of the amplified DNA products is carried out via a length-based measurement using capillary electrophoresis (CE); however, with the introduction of sequencing to the workflow, the amplified products now enter the process of massively parallel sequencing (MPS) providing a sequencing-based measurement for an allele. After the sequencing is complete, the generated data can be used as an input for bioinformatics pipelines. The data analysis provides details about the measured quantity of the expected PCR product sequences (here referred to as _parent_ alleles) and numerous artifact sequences related to the range of genetic markers examined in these assays. In typing a standard single-source sample for a set of autosomal markers, the sequences observed should include one to two different parent alleles (depending on whether the sample was homozygous or heterozygous at the autosomal locus) and numerous artifact sequences that are present because of copying errors in the amplification and sequencing process. Each detected sequence is quantified by the number of sequences observed and is commonly referred to as the _depth of coverage_ (DoC). Along with the parent alleles there are artifacts that are also detected and are often present at a low DoC, and therefore easily distinguishable from the parent alleles. Each of the artifacts is an error sequence of a true parent, and one can generally infer which parent it came from, but occasionally the parent sequences are similar enough that it is difficult to tell which is the actual parent sequence. For single-contributor DNA samples, this is typically not an issue, but crime scene samples motivating this work are rarely from a single individual. Crime scene samples often consist of multiple individuals, contributing different amounts of genetic information. For example, in a complex mixture (e.g., three contributors at 70%-25%-5%) it can be challenging to determine the respective parent allele of each contributor and their corresponding artifact(s).  
In this light, quantifying what it means for nucleotide sequences to be similar becomes a crucial task, which has led to the notion of a generalized Levenshtein distance that allows gains and losses of multiple letters at once (here the change of multiple bases at once in the sequence string), and the development of an algorithm to calculate it. A major contribution of the proposed algorithm is in handling the exponential explosion of complexity when multiple-character edits and single-character edits interact, which requires careful techniques to resolve.