Cadena más cercana - Closest string

En informática teórica , la cadena más cercana es un problema computacional NP-hard , 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. Por lo general, este problema se estudia teniendo en cuenta la distancia de Hamming .

Definicion formal

Más formalmente, dada n longitud- m cadenas s 1 , s 2 , ..., s n , el problema de cadena más cercano busca una nueva longitud- m cadena s tal que d ( s , s i ) ≤ k para todo i , donde d denota la distancia de Hamming y donde k es lo más pequeño posible. Una versión de problema de decisión del problema de cuerdas más cercano, que es NP-completo , toma k como otra entrada y se pregunta si hay una cuerda dentro de la distancia de Hamming k de todas las cadenas de entrada.

El problema de cuerdas más cercano 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 cuerdas más cercano 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 dureza 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 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 conducir 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 más frecuencia con a , el carácter que aparece en segundo lugar con más frecuencia con b , y así sucesivamente. Dada una solución a 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 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

Espacio de búsqueda para el problema normalizado. La cadena central aaaa y aaab conduce a las distancias de Hamming 1, 2, 1 y 2, 1, 1, respectivamente.

Dada una instancia con tres cadenas de entrada uvwx , xuwv y xvwu . Esto podría escribirse como una matriz como esta:

tu v w X
X tu w v
X v w tu

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 con mayor frecuencia, 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 sustituye por una y u se sustituye por b , la obtención de la nueva segunda columna ( un , b , un ). Hacer lo mismo con todas las columnas da la instancia normalizada

B a a a
a B a B
a a a C

Reducción de datos obtenidos de la normalización

La normalización de la entrada reduce el tamaño del alfabeto como máximo al 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 y col. desarrolló un esquema de aproximación polinomial-temporal 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 yd es la distancia máxima deseada desde la cadena de solución a cualquier cadena de entrada.

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. Mientras que la cadena más cercana resulta ser manejable con parámetros fijos de varias formas, la subcadena más cercana es W [1] -hard con respecto a estos parámetros.

Referencias

  1. ↑ a b Lanctot, J. Kevin; Li, Ming; Ma, Bin; Wang, Shaojiu; Zhang, Louxin (2003), "Distinguiendo problemas de selección de cuerdas", Information and Computation , 185 (1): 41-55, doi : 10.1016 / S0890-5401 (03) 00057-9 , MR  1994748
  2. ^ Bin Ma; Xiaming Sun (2008). "Algoritmos más eficientes para los problemas más cercanos de cadenas y subcadenas" (PDF) . Investigación en Biología Molecular Computacional . 12th Ann. En t. Conf. de Investigación en Biología Molecular Computacional (RECOMB). LNCS . 4955 . Saltador. págs. 396–409. doi : 10.1007 / 978-3-540-78839-3_33 . ISBN 978-3-540-78838-6.
  3. ^ M. Li, B. Ma y L. Wang. (2002), "Sobre los problemas más cercanos de cadenas y subcadenas". (PDF) , Revista de la ACM , 49 (2): 157–171, arXiv : cs / 0002012 , doi : 10.1145 / 506147.506150Mantenimiento de CS1: utiliza el parámetro de autores ( enlace )
  4. ^ Jens Gramm, Rolf Niedermeier y 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-3Mantenimiento de CS1: utiliza el parámetro de autores ( enlace )