Aproximación de coincidencia de cadenas con translocaciones desequilibradas adyacentes no superpuestas
Autores: Cantone, Domenico; Faro, Simone; Pavone, Arianna
Idioma: Inglés
Editor: MDPI
Año: 2025
Acceso abierto
Artículo científico
2025
Aproximación de coincidencia de cadenas con translocaciones desequilibradas adyacentes no superpuestas
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
Investigar
Editar operaciones
Subcadenas adyacentes
Modificaciones a gran escala
Biología computacional
Programación dinámica
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 21
Citaciones: Sin citaciones
En este documento, investigamos cuándo las operaciones de edición permitidas son . Este tipo de operación de edición tiene lugar cuando dos subcadenas adyacentes del texto se intercambian, lo que resulta en una cadena modificada. Las dos subcadenas involucradas pueden tener longitudes diferentes. Estas modificaciones a gran escala de cadenas tienen diversas aplicaciones, especialmente en campos como la biología computacional y la genómica, donde las reorganizaciones estructurales juegan un papel clave. Sin embargo, a pesar de su papel central en muchos campos de procesamiento de texto, se ha prestado poca atención al problema de emparejar cadenas que permitan este tipo de operación de edición. En este documento, presentamos tres algoritmos para resolver el problema, todos ellos con una complejidad de peor caso y de espacio, donde y son la longitud del patrón y del texto, respectivamente. Específicamente, nuestro primer algoritmo se basa en el enfoque de programación dinámica. Nuestra segunda solución mejora la anterior al hacer uso del Grafo de Palabras Acíclico Dirigido del patrón. Finalmente, nuestro tercer algoritmo se basa en un procedimiento de alineación. También mostramos que bajo las suposiciones de equiprobabilidad e independencia de caracteres, nuestro segundo algoritmo tiene una complejidad temporal promedio para un alfabeto de tamaño .
Descripción
En este documento, investigamos cuándo las operaciones de edición permitidas son . Este tipo de operación de edición tiene lugar cuando dos subcadenas adyacentes del texto se intercambian, lo que resulta en una cadena modificada. Las dos subcadenas involucradas pueden tener longitudes diferentes. Estas modificaciones a gran escala de cadenas tienen diversas aplicaciones, especialmente en campos como la biología computacional y la genómica, donde las reorganizaciones estructurales juegan un papel clave. Sin embargo, a pesar de su papel central en muchos campos de procesamiento de texto, se ha prestado poca atención al problema de emparejar cadenas que permitan este tipo de operación de edición. En este documento, presentamos tres algoritmos para resolver el problema, todos ellos con una complejidad de peor caso y de espacio, donde y son la longitud del patrón y del texto, respectivamente. Específicamente, nuestro primer algoritmo se basa en el enfoque de programación dinámica. Nuestra segunda solución mejora la anterior al hacer uso del Grafo de Palabras Acíclico Dirigido del patrón. Finalmente, nuestro tercer algoritmo se basa en un procedimiento de alineación. También mostramos que bajo las suposiciones de equiprobabilidad e independencia de caracteres, nuestro segundo algoritmo tiene una complejidad temporal promedio para un alfabeto de tamaño .