2023/10/19 by Robert Logan, Amy Wangsness Wehe, Logan, Robert +7
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #FOS: Biological sciences #Genomics and Phylogenetic Studies #Quantitative Methods (q-bio.QM) #RNA and protein synthesis mechanisms
paper · pdf · doi:10.48550/arxiv.2310.12833
openalex publication_date 2023/10/19 · openalex created_date 2023/10/21 · openalex updated_date 2026/07/28
Levenshtein distance is a commonly used edit distance metric, typically applied in language processing, and to a lesser extent, in molecular biology analysis. Biological nucleic acid sequences are often embedded in longer sequences and are subject to insertion and deletion errors that introduce frameshift during sequencing. These frameshift errors are due to string context and should not be counted as true biological errors. Sequence-Levenshtein distance is a modification to Levenshtein distance that is permissive of frameshift error without additional penalty. However, in a biological context Levenshtein distance needs to accommodate both frameshift and weighted errors, which Sequence-Levenshtein distance cannot do. Errors are weighted when they are associated with a numerical cost that corresponds to their frequency of appearance. Here, we describe a modification that allows the use of Levenshtein distance and Sequence-Levenshtein distance to appropriately accommodate penalty-free frameshift between embedded sequences and correctly weight specific error types.