Hispanopedia WikiEn informática teórica , la cadena más cercana es un problema computacional NP-duro , [1] que intenta encontrar el centro geométrico de un conjunto de cadenas de entrada.
Para entender la palabra "centro", es necesario definir una distancia entre dos cuerdas. Generalmente, este problema se estudia teniendo en cuenta la distancia de Hamming .
Definición formal
Más formalmente, dadas n cadenas s 1 , s 2 , ..., s n de longitud m , el problema de la cadena más cercana busca una nueva cadena s de longitud m tal que d ( s , s i ) ≤ k para todo i , donde d es la distancia de Hamming , y donde k es lo más pequeño posible. [2] Una versión del problema de la cadena más cercana, que es NP-completo , toma en cambio k como otra entrada y cuestiona si hay una cadena dentro de la distancia de Hamming k de todas las cadenas de entrada. [1]
El problema de la cuerda más cercana puede verse como un caso especial del problema genérico de 1 centro en el que las distancias entre elementos se miden utilizando la distancia de Hamming.
Motivación
En bioinformática , el problema de la cadena más cercana es una faceta intensamente estudiada del problema de encontrar señales en el ADN .
Simplificaciones y reducciones de datos
Las instancias de la cadena más cercana pueden contener información que no es esencial para el problema. En cierto sentido, la entrada habitual de la cadena más cercana contiene información que no contribuye a la dificultad del problema. Por ejemplo, si algunas cadenas contienen el carácter a , pero ninguna contiene el carácter z , reemplazar todas las a s por z s produciría una instancia esencialmente equivalente, es decir: a partir de una solución de la instancia modificada, se puede restaurar la solución original, y viceversa.
Normalizando la entrada
Cuando todas las cadenas de entrada que comparten la misma longitud se escriben una encima de otra, forman una matriz. Ciertos tipos de filas tienen esencialmente las mismas implicaciones para la solución. Por ejemplo, reemplazar una columna con entradas ( a , a , b ) por otra columna ( x , x , y ) puede llevar a una cadena de solución diferente, pero no puede afectar la capacidad de solución, porque ambas columnas expresan la misma estructura, es decir, las dos primeras entradas son iguales, pero diferentes de la tercera.
Una instancia de entrada se puede normalizar reemplazando, en cada columna, el carácter que aparece con mayor frecuencia por a , el carácter que aparece en segundo lugar con b , y así sucesivamente. Dada una solución para la instancia normalizada, la instancia original se puede encontrar reasignando los caracteres de la solución a su versión original en cada columna.
El orden de las columnas no contribuye a la dificultad del problema. Esto significa que, si permutamos todas las cadenas de entrada según una determinada permutación π y obtenemos una cadena de solución s para esa instancia modificada, entonces π −1 ( s ) será una solución para la instancia original.
Ejemplo
Dada una instancia con tres cadenas de entrada uvwx , xuwv y xvwu , esto podría escribirse como una matriz como esta:
La primera columna tiene los valores ( u , x , x ). Como x es el carácter que aparece con más frecuencia, lo reemplazamos por a , y reemplazamos u , el segundo carácter más frecuente, por b , obteniendo la nueva primera columna ( b , a , a ). La segunda columna tiene los valores ( v , u , v ). En cuanto a la primera columna, v se reemplaza por a y u se reemplaza por b , obteniendo la nueva segunda columna ( a , b , a ). Al hacer lo mismo con todas las columnas, se obtiene la instancia normalizada
Reducción de datos obtenida a partir de la normalización
La normalización de la entrada reduce el tamaño del alfabeto a, como máximo, el número de cadenas de entrada. Esto puede resultar útil para algoritmos cuyos tiempos de ejecución dependen del tamaño del alfabeto.
Aproximabilidad
Li et al. desarrollaron un esquema de aproximación de tiempo polinomial [3] que es prácticamente inutilizable debido a las grandes constantes ocultas.
Tratabilidad de parámetros fijos
La cadena más cercana se puede resolver en , donde k es el número de cadenas de entrada, L es la longitud de todas las cadenas y d es la distancia máxima deseada desde la cadena solución a cualquier cadena de entrada. [4]
Relaciones con otros problemas
La cadena más cercana es un caso especial del problema más general de la subcadena más cercana, que es estrictamente más difícil. Si bien la cadena más cercana resulta manejable con parámetros fijos de varias maneras, la subcadena más cercana es W[1]-hard con respecto a estos parámetros.
Referencias
- ^ ab Lanctot, J. Kevin; Li, Ming; Ma, Bin; Wang, Shaojiu; Zhang, Louxin (2003), "Distinguir problemas de selección de cadenas", Información y computación , 185 (1): 41–55, doi :10.1016/S0890-5401(03)00057-9, MR 1994748
- ^ Bin Ma; Xiaming Sun (2008). "Algoritmos más eficientes para problemas de cadenas y subcadenas más cercanas" (PDF) . Investigación en biología molecular computacional . 12.ª conferencia anual internacional sobre investigación en biología molecular computacional (RECOMB). LNCS . Vol. 4955. Springer. págs. 396–409. doi :10.1007/978-3-540-78839-3_33. ISBN . 978-3-540-78838-6.
- ^ M. Li; B. Ma; L. Wang. (2002), "Sobre los problemas de subcadenas y cuerdas más cercanas". (PDF) , Journal of the ACM , 49 (2): 157–171, arXiv : cs/0002012 , doi :10.1145/506147.506150, S2CID 965332
- ^ Jens Gramm; Rolf Niedermeier ; Peter Rossmanith (2003), "Algoritmos de parámetros fijos para la cadena más cercana y problemas relacionados", Algorithmica , 37 : 25–42, CiteSeerX 10.1.1.61.736 , doi :10.1007/s00453-003-1028-3, S2CID 8206021
