supersecuencia común más corta

En informática , la supersecuencia común más corta de dos secuencias X e Y es la secuencia más corta que tiene a X e Y como subsecuencias . Este es un problema estrechamente relacionado con el problema de la subsecuencia común más larga . Dadas dos secuencias X = < x ₁ ,...,x _m > e Y = < y ₁ ,...,y _n >, una secuencia U = < u ₁ ,...,u _k > es una supersecuencia común de X e Y si se pueden eliminar elementos de U para producir X e Y.

Una supersecuencia común más corta (SCS, por sus siglas en inglés) es una supersecuencia común de longitud mínima. En el problema de la SCS, se dan dos secuencias X e Y , y la tarea consiste en encontrar la supersecuencia común más corta posible de estas secuencias. En general, una SCS no es única.

Para dos secuencias de entrada, se puede formar fácilmente una SCS a partir de una subsecuencia común más larga (LCS). Por ejemplo, la subsecuencia común más larga de X${\displaystyle [1..m]=abcbdab}$y Y${\displaystyle [1..n]=bdcaba}$es Z${\displaystyle [1..L]=bcba}$Al insertar los símbolos que no son LCS en Z , conservando su orden original, obtenemos una supersecuencia común más corta U.${\displaystyle [1..S]=abdcabdab}$. En particular, la ecuación${\displaystyle L+S=m+n}$Se cumple para cualquier par de secuencias de entrada.

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${\displaystyle O(n^{k})}$tiempo usando programación dinámica , donde${\displaystyle k}$es el número de secuencias, y${\displaystyle n}$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 ]}

El problema estrechamente relacionado de encontrar una cadena de longitud mínima que sea una supercadena de un conjunto finito de cadenas S = { s ₁ , s ₂ ,..., s _n } también es NP-difícil. ^{[ 2 ]} Además, es APX -completo. ^{[ 3 ]} Se han propuesto varias aproximaciones de factor constante a lo largo de los años, y el mejor algoritmo conocido actualmente tiene un factor de aproximación de 2,475. ^{[ 4 ]} Sin embargo, quizás la solución más simple sea reformular el problema como una instancia de cobertura de conjuntos ponderada de tal manera que el peso de la solución óptima para la instancia de cobertura de conjuntos sea menor que el doble de la longitud de la supercadena más corta S . Entonces se puede usar la aproximación O(log( n )) para la cobertura de conjuntos ponderada para obtener una aproximación O(log( n )) para la supercadena más corta (nótese que esta no es una aproximación de factor constante).

Para cualquier cadena x en este alfabeto, definimos P ( x ) como el conjunto de todas las cadenas que son subcadenas de x . La instancia I de cobertura de conjuntos 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 iguales a 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${\displaystyle {\mathcal {U}}}$de la instancia de cubierta del conjunto a ser S
• Definimos el conjunto de subconjuntos del universo como { P ( x ) | x ∈ S ∪ M }
• Definimos el costo de cada subconjunto P (x) como | x |, la longitud de x .

La instancia I se puede resolver utilizando un algoritmo de cobertura de conjuntos ponderados, y el algoritmo puede generar una concatenación arbitraria de las cadenas x para las cuales el algoritmo de cobertura de conjuntos ponderados genera P ( x ). ^{[ 5 ]}

• Subsecuencia común más larga
• Subcadena común más larga

• Garey, Michael R.; Johnson , David S. (1979). Computadoras e intratabilidad: una guía a la teoría de la NP-completitud . WH Freeman. pág. 228 A4.2: SR8 . ISBN 0-7167-1045-5. Zbl 0411.68039 . 
• Szpankowski, Wojciech (2001). Análisis del caso promedio de algoritmos en 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

• Diccionario de algoritmos y estructuras de datos: supersecuencia común más corta
• Supersecuencia común más corta
• 1092. Supersecuencia común más corta
• Supersecuencia común más corta
• supersecuencia común más corta
• Supersecuencia común más corta (SCS)