En 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 .
Más formalmente, dadas n cadenas s 1 , s 2 , ..., s n de longitud m , el problema de cadenas más cercano 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 de problema de decisión del problema de cadena más cercano, que es NP-completo , toma k como otra entrada y pregunta si hay una cadena dentro de la distancia de Hamming k de todas las cadenas de entrada. [1]
El problema de cuerdas más cercanas 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.
En bioinformática , el problema de cuerdas más cercano es una faceta intensamente estudiada del problema de encontrar señales en el ADN .
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 complejidad del problema. Por ejemplo, si algunas cadenas contienen el carácter a , pero ninguna contiene el carácter z , reemplazar todas las a s con 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.
Cuando todas las cadenas de entrada que comparten la misma longitud se escriben una encima de la 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 ) con otra columna ( x , x , y ) puede generar una cadena de solución diferente, pero no puede afectar la solubilidad, porque ambas columnas expresan la misma estructura, a saber. 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 más frecuencia por a , el carácter que aparece en segundo lugar con mayor frecuencia por 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 dureza del problema. Eso significa que si permutamos todas las cadenas de entrada de acuerdo con una cierta permutación π y obtenemos una cadena solución s para esa instancia modificada, entonces π −1 ( s ) será una solución para la instancia original.
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, se reemplaza v por a y u se reemplaza por b , obteniendo la nueva segunda columna ( a , b , a ). Hacer lo mismo con todas las columnas da la instancia normalizada.
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.
Li y col. desarrolló un esquema de aproximación de tiempo polinomial [3] que es prácticamente inutilizable debido a las grandes constantes ocultas.
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 de solución a cualquier cadena de entrada. [4]
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 ser manejable con parámetros fijos de varias maneras, la subcadena más cercana es W[1]-hard con respecto a estos parámetros.
