logo móvil
Contáctanos

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

Descargar PDF

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


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 .

Otros recursos que podrían interesarte

Temas Virtualpro