Cargando…

Interpreting Sequence-Levenshtein distance for determining error type and frequency between two embedded sequences of equal length

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 fram...

Descripción completa

Detalles Bibliográficos
Autores principales: Logan, Robert, Wehe, Amy Wangsness, Woods, Dori C, Tilly, Jon, Khrapko, Konstantin
Formato: Online Artículo Texto
Lenguaje:English
Publicado: Cornell University 2023
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC10614987/
https://www.ncbi.nlm.nih.gov/pubmed/37904736
_version_ 1785129131201003520
author Logan, Robert
Wehe, Amy Wangsness
Woods, Dori C
Tilly, Jon
Khrapko, Konstantin
author_facet Logan, Robert
Wehe, Amy Wangsness
Woods, Dori C
Tilly, Jon
Khrapko, Konstantin
author_sort Logan, Robert
collection PubMed
description 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.
format Online
Article
Text
id pubmed-10614987
institution National Center for Biotechnology Information
language English
publishDate 2023
publisher Cornell University
record_format MEDLINE/PubMed
spelling pubmed-106149872023-10-31 Interpreting Sequence-Levenshtein distance for determining error type and frequency between two embedded sequences of equal length Logan, Robert Wehe, Amy Wangsness Woods, Dori C Tilly, Jon Khrapko, Konstantin ArXiv Article 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. Cornell University 2023-10-19 /pmc/articles/PMC10614987/ /pubmed/37904736 Text en https://creativecommons.org/licenses/by-sa/4.0/This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License (https://creativecommons.org/licenses/by-sa/4.0/) , which allows reusers to distribute, remix, adapt, and build upon the material in any medium or format, so long as attribution is given to the creator. The license allows for commercial use. If you remix, adapt, or build upon the material, you must license the modified material under identical terms.
spellingShingle Article
Logan, Robert
Wehe, Amy Wangsness
Woods, Dori C
Tilly, Jon
Khrapko, Konstantin
Interpreting Sequence-Levenshtein distance for determining error type and frequency between two embedded sequences of equal length
title Interpreting Sequence-Levenshtein distance for determining error type and frequency between two embedded sequences of equal length
title_full Interpreting Sequence-Levenshtein distance for determining error type and frequency between two embedded sequences of equal length
title_fullStr Interpreting Sequence-Levenshtein distance for determining error type and frequency between two embedded sequences of equal length
title_full_unstemmed Interpreting Sequence-Levenshtein distance for determining error type and frequency between two embedded sequences of equal length
title_short Interpreting Sequence-Levenshtein distance for determining error type and frequency between two embedded sequences of equal length
title_sort interpreting sequence-levenshtein distance for determining error type and frequency between two embedded sequences of equal length
topic Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC10614987/
https://www.ncbi.nlm.nih.gov/pubmed/37904736
work_keys_str_mv AT loganrobert interpretingsequencelevenshteindistancefordeterminingerrortypeandfrequencybetweentwoembeddedsequencesofequallength
AT weheamywangsness interpretingsequencelevenshteindistancefordeterminingerrortypeandfrequencybetweentwoembeddedsequencesofequallength
AT woodsdoric interpretingsequencelevenshteindistancefordeterminingerrortypeandfrequencybetweentwoembeddedsequencesofequallength
AT tillyjon interpretingsequencelevenshteindistancefordeterminingerrortypeandfrequencybetweentwoembeddedsequencesofequallength
AT khrapkokonstantin interpretingsequencelevenshteindistancefordeterminingerrortypeandfrequencybetweentwoembeddedsequencesofequallength