En informática , la supersecuencia común más corta de dos secuencias X e Y es la secuencia más corta que tiene X e Y como subsecuencias . Este es un problema estrechamente relacionado con el problema de subsecuencia común más largo . Dadas dos secuencias X =
Una supersecuencia común más corta (SCS) es una supersecuencia común de longitud mínima. En el problema de supersecuencia común más corto, se dan dos secuencias X e Y , y la tarea es encontrar una supersecuencia común más corta posible de estas secuencias. En general, un SCS no es único.
Para dos secuencias de entrada, un SCS puede formarse fácilmente a partir de una subsecuencia común más larga (LCS). Por ejemplo, la subsecuencia común más larga de Xy Yes Z. Al insertar los símbolos que no son LCS en Z mientras se conserva su orden original, obtenemos una supersecuencia común más corta U. En particular, la ecuación se mantiene para dos secuencias de entrada cualesquiera.
No existe una relación similar entre las supersecuencias comunes más cortas y las subsecuencias comunes más largas de tres o más secuencias de entrada. (En particular, LCS y SCS no son problemas duales .) Sin embargo, ambos problemas pueden resolverse en tiempo usando programación dinámica, donde es el número de secuencias, y es su longitud máxima. Para el caso general de un número arbitrario de secuencias de entrada, el problema es NP-difícil . [1]
Supercuerda común más corta
El problema estrechamente relacionado de encontrar una cadena de longitud mínima que sea una supercuerda de un conjunto finito de cadenas S = { s 1 , s 2 , ..., s n } también es NP-difícil. [2] Además, se han encontrado buenas aproximaciones (factor constante) para el caso promedio, pero no para el peor de los casos. [3] [4] Sin embargo, se puede formular como una instancia de cobertura de conjunto ponderada de tal manera que el peso de la solución óptima para la instancia de cobertura de conjunto sea menos del doble de la longitud de la supercuerda S más corta . Luego, se puede usar la aproximación O (log ( n )) para la cobertura del conjunto ponderado para obtener una aproximación O (log ( n )) para la supercuerda más corta (tenga en cuenta que esta no es una aproximación de factor constante).
Para cualquier cadena x en este alfabeto, defina P ( x ) como el conjunto de todas las cadenas que son subcadenas de x . La instancia I de cobertura del conjunto se formula de la siguiente manera:
- Sea M vacío.
- Para cada par de cadenas s i y s j , si los últimos k símbolos de s i son los mismos que los primeros k símbolos de s j , entonces agregue una cadena a M que consista en la concatenación con superposición máxima de s i con s j .
- Definir el universo de la instancia de portada establecida como S
- Defina el conjunto de subconjuntos del universo como { P ( x ) | x ∈ S ∪ M }
- Defina el costo de cada subconjunto P (x) como | x |, la longitud de x .
Luego, la instancia I puede resolverse utilizando un algoritmo para la cobertura del conjunto ponderado, y el algoritmo puede generar una concatenación arbitraria de las cadenas x para las que el algoritmo de cobertura del conjunto ponderado genera P ( x ). [5]
Ejemplo
Considere el conjunto S = {abc, cde, fab}, que se convierte en el universo de la instancia de cobertura del conjunto ponderado. En este caso, M = {abcde, fabc}. Entonces el conjunto de subconjuntos del universo es
que tienen costos 3, 3, 3, 5 y 4, respectivamente.
Referencias
- ^ David Maier (1978). "La complejidad de algunos problemas sobre subsecuencias y supersecuencias". J. ACM . Prensa ACM. 25 (2): 322–336. doi : 10.1145 / 322063.322075 .
- ^ Kari-Jouko Räihä, Esko Ukkonen (1981). "El problema de supersecuencia común más corto sobre el alfabeto binario es NP-completo". Informática Teórica . 16 (2): 187-198. doi : 10.1016 / 0304-3975 (81) 90075-x .
- ^ Tao Jiang y Ming Li (1994). "Sobre la aproximación de las supersecuencias comunes más cortas y las subsecuencias comunes más largas". Revista SIAM de Computación . 24 (5): 1122-1139. doi : 10.1137 / s009753979223842x .
- ^ Marek Karpinski y Richard Schmied (2013). "Sobre la mejora de los resultados de inapropiabilidad para la supercuerda más corta y problemas relacionados" (PDF) . Actas del 19º CRPIT CATS . 141 : 27–36.
- ^ Vazirani , pág. 20.
- Garey, Michael R .; Johnson, David S. (1979). Computadoras e intratabilidad: una guía para la teoría de NP-Completeness . WH Freeman. pag. 228 A4.2: SR8 . ISBN 0-7167-1045-5. Zbl 0411.68039 .
- Szpankowski, Wojciech (2001). Análisis de caso medio de algoritmos sobre secuencias . Serie Wiley-Interscience en matemáticas discretas y optimización. Con prólogo de Philippe Flajolet. Chichester: Wiley. ISBN 0-471-24063-X. Zbl 0968.68205 .
- Vazirani, Vijay V. (2001), algoritmos de aproximación , Springer-Verlag, ISBN 3-540-65367-8