Subsecuencia común más larga

Problema algorítmico sobre pares de secuencias

Comparación de dos revisiones de un archivo de ejemplo, en función de su subsecuencia común más larga (negro)

Una subsecuencia común más larga ( LCS ) es la subsecuencia común más larga a todas las secuencias en un conjunto de secuencias (a menudo solo dos secuencias). Se diferencia de la subcadena común más larga : a diferencia de las subcadenas, no se requiere que las subsecuencias ocupen posiciones consecutivas dentro de las secuencias originales. El problema de calcular las subsecuencias comunes más largas es un problema clásico de la informática , la base de los programas de comparación de datos como la diffutilidad , y tiene aplicaciones en lingüística computacional y bioinformática . También es ampliamente utilizado por sistemas de control de revisión como Git para conciliar múltiples cambios realizados en una colección de archivos controlada por revisión.

Por ejemplo, considere las secuencias (ABCD) y (ACBAD). Tienen cinco subsecuencias comunes de longitud 2: (AB), (AC), (AD), (BD) y (CD); dos subsecuencias comunes de longitud 3: (ABD) y (ACD); y ya no tienen subsecuencias comunes. Por lo tanto, (ABD) y (ACD) son sus subsecuencias comunes más largas.

Complejidad

Para el caso general de un número arbitrario de secuencias de entrada, el problema es NP-duro . ^[1] Cuando el número de secuencias es constante, el problema se puede resolver en tiempo polinomial mediante programación dinámica .

Dadas secuencias de longitudes , una búsqueda ingenua probaría cada una de las subsecuencias de la primera secuencia para determinar si también son subsecuencias de las secuencias restantes; cada subsecuencia puede probarse en un tiempo lineal en las longitudes de las secuencias restantes, por lo que el tiempo para este algoritmo sería ${\displaystyle N}$ ${\displaystyle n_{1},...,n_{N}}$ ${\displaystyle 2^{n_{1}}}$

${\displaystyle O\left(2^{n_{1}}\sum _{i>1}n_{i}\right).}$

Para el caso de dos secuencias de n y m elementos, el tiempo de ejecución del enfoque de programación dinámica es O ( n × m ). ^[2] Para un número arbitrario de secuencias de entrada, el enfoque de programación dinámica proporciona una solución en

${\displaystyle O\left(N\prod _{i=1}^{N}n_{i}\right).}$

Existen métodos con menor complejidad, ^[3] que a menudo dependen de la longitud del LCS, del tamaño del alfabeto o de ambos.

La LCS no es necesariamente única; en el peor de los casos, el número de subsecuencias comunes es exponencial en las longitudes de las entradas, por lo que la complejidad algorítmica debe ser al menos exponencial. ^[4]

Solución para dos secuencias

El problema LCS tiene una subestructura óptima : el problema se puede dividir en subproblemas más pequeños y simples, que a su vez se pueden dividir en subproblemas más simples, y así sucesivamente, hasta que, finalmente, la solución se vuelve trivial. LCS en particular tiene subproblemas superpuestos : las soluciones a subproblemas de alto nivel a menudo reutilizan soluciones a subproblemas de nivel inferior. Los problemas con estas dos propiedades son susceptibles de enfoques de programación dinámica , en los que las soluciones de los subproblemas se memorizan , es decir, las soluciones de los subproblemas se guardan para su reutilización.

Prefijos

El prefijo S _n de S se define como los primeros n caracteres de S . ^[5] Por ejemplo, los prefijos de S = (AGCA) son

S0 ₌ ()

S1 = ₍ A)

S2 = ₍ AG)

S3 = ₍ CGA)

S4 = ₍ AGCA).

Sea LCS ( X , Y ) una función que calcula una subsecuencia más larga común a X e Y . Esta función tiene dos propiedades interesantes.

Primera propiedad

LCS ( X ^ A , Y ^ A ) = LCS ( X , Y )^ A , para todas las cadenas X , Y y todos los símbolos A , donde ^ denota concatenación de cadenas. Esto permite simplificar el cálculo de LCS para dos secuencias que terminan en el mismo símbolo. Por ejemplo, LCS ("BANANA", "ATANA") = LCS ("BANAN", "ATAN")^"A", y para los demás símbolos comunes, LCS ("BANANA", "ATANA") = LCS ("BAN", "AT")^"ANA".

Segunda propiedad

Si A y B son símbolos distintos ( A ≠ B ), entonces LCS (X^A,Y^B) es una de las cadenas de longitud máxima en el conjunto { LCS ( X ^ A , Y ), LCS ( X , Y ^ B ) }, para todas las cadenas X , Y .

Por ejemplo, LCS ("ABCDEFG", "BCDGK") es la cadena más larga entre LCS ("ABCDEFG", "BCDG") y LCS ("ABCDEF", "BCDGK"); si ambas tuvieran la misma longitud, se podría elegir una de ellas arbitrariamente.

Para realizar la propiedad se distinguen dos casos:

• Si LCS ("ABCDEFG", "BCDGK") termina con una "G", entonces la "K" final no puede estar en el LCS, por lo tanto, LCS ("ABCDEFG", "BCDGK") = LCS ("ABCDEFG", "BCDG").
• Si LCS ("ABCDEFG", "BCDGK") no termina con una "G", entonces la "G" final no puede estar en el LCS, por lo tanto, LCS ("ABCDEFG", "BCDGK") = LCS ("ABCDEF", "BCDGK").

LCSfunción definida

Sean dos sucesiones definidas de la siguiente manera: y . Los prefijos de son ; los prefijos de son . Sea el conjunto de la subsecuencia común más larga de los prefijos y . Este conjunto de sucesiones está dado por lo siguiente. ${\displaystyle X=(x_{1}x_{2}\cdots x_{m})}$ ${\displaystyle Y=(y_{1}y_{2}\cdots y_{n})}$ ${\displaystyle X}$ ${\displaystyle X_{0},X_{1},X_{2},\dots ,X_{m}}$ ${\displaystyle Y}$ ${\displaystyle Y_{0},Y_{1},Y_{2},\dots ,Y_{n}}$ ${\displaystyle {\mathit {LCS}}(X_{i},Y_{j})}$ ${\displaystyle X_{i}}$ ${\displaystyle Y_{j}}$

${\displaystyle {\mathit {LCS}}(X_{i},Y_{j})={\begin{cases}\epsilon &{\mbox{if }}i=0{\mbox{ or }}j=0\\{\mathit {LCS}}(X_{i-1},Y_{j-1}){\hat {}}x_{i}&{\mbox{if }}i,j>0{\mbox{ and }}x_{i}=y_{j}\\\operatorname {\max } \{{\mathit {LCS}}(X_{i},Y_{j-1}),{\mathit {LCS}}(X_{i-1},Y_{j})\}&{\mbox{if }}i,j>0{\mbox{ and }}x_{i}\neq y_{j}.\end{cases}}}$

Para hallar el MCS de y , compare y . Si son iguales, entonces la secuencia se extiende con ese elemento, . Si no son iguales, entonces se conserva la más larga de las dos secuencias, , y . (Si tienen la misma longitud, pero no son idénticas, entonces se conservan ambas). El caso base, cuando o está vacío, es la cadena vacía , . ${\displaystyle X_{i}}$ ${\displaystyle Y_{j}}$ ${\displaystyle x_{i}}$ ${\displaystyle y_{j}}$ ${\displaystyle {\mathit {LCS}}(X_{i-1},Y_{j-1})}$ ${\displaystyle x_{i}}$ ${\displaystyle {\mathit {LCS}}(X_{i},Y_{j-1})}$ ${\displaystyle {\mathit {LCS}}(X_{i-1},Y_{j})}$ ${\displaystyle X_{i}}$ ${\displaystyle Y_{i}}$ ${\displaystyle \epsilon }$

Ejemplo resuelto

Se encontrará la subsecuencia más larga común a R = (GAC) y C = (AGCAT). Debido a que la función LCS utiliza un elemento "cero", es conveniente definir prefijos cero que estén vacíos para estas secuencias: R ₀ = ε; y C ₀ = ε. Todos los prefijos se colocan en una tabla con C en la primera fila (lo que la convierte en un encabezado de columna ) y R en la primera columna (lo que la convierte en un encabezado de fila ).

Esta tabla se utiliza para almacenar la secuencia LCS para cada paso del cálculo. La segunda columna y la segunda fila se han rellenado con ε, porque cuando se compara una secuencia vacía con una secuencia no vacía, la subsecuencia común más larga siempre es una secuencia vacía.

LCS ( R ₁ , C ₁ ) se determina comparando los primeros elementos de cada secuencia. G y A no son iguales, por lo que esta LCS obtiene (usando la "segunda propiedad") la más larga de las dos secuencias, LCS ( R ₁ , C ₀ ) y LCS ( R ₀ , C ₁ ). Según la tabla, ambas están vacías, por lo que LCS ( R ₁ , C ₁ ) también está vacía, como se muestra en la tabla siguiente. Las flechas indican que la secuencia proviene tanto de la celda de arriba, LCS ( R ₀ , C ₁ ) como de la celda de la izquierda, LCS ( R ₁ , C ₀ ).

LCS ( R ₁ , C ₂ ) se determina comparando G y G. Coinciden, por lo que G se añade a la secuencia superior izquierda, LCS ( R ₀ , C ₁ ), que es (ε), dando (εG), que es (G).

Para LCS ( R ₁ , C ₃ ), G y C no coinciden. La secuencia anterior está vacía; la de la izquierda contiene un elemento, G. Si seleccionamos la más larga de ellas, LCS ( R ₁ , C ₃ ) es (G). La flecha apunta hacia la izquierda, ya que es la más larga de las dos secuencias.

LCS ( R ₁ , C ₄ ), asimismo, es (G).

LCS ( R ₁ , C ₅ ), asimismo, es (G).

Para LCS ( R ₂ , C ₁ ), A se compara con A. Los dos elementos coinciden, por lo que A se agrega a ε, dando (A).

Para LCS ( R ₂ , C ₂ ), A y G no coinciden, por lo que se utiliza la más larga de LCS ( R ₁ , C ₂ ), que es (G), y LCS ( R ₂ , C ₁ ), que es (A). En este caso, cada una contiene un elemento, por lo que a esta LCS se le asignan dos subsecuencias: (A) y (G).

Para LCS ( R ₂ , C ₃ ), A no coincide con C. LCS ( R ₂ , C ₂ ) contiene las secuencias (A) y (G); LCS( R ₁ , C ₃ ) es (G), que ya está contenida en LCS ( R ₂ , C ₂ ). El resultado es que LCS ( R ₂ , C ₃ ) también contiene las dos subsecuencias, (A) y (G).

Para LCS ( R ₂ , C ₄ ), A coincide con A, que se agrega a la celda superior izquierda, dando (GA).

Para LCS ( R ₂ , C ₅ ), A no coincide con T. Comparando las dos secuencias, (GA) y (G), la más larga es (GA), por lo que LCS ( R ₂ , C ₅ ) es (GA).

Para LCS ( R ₃ , C ₁ ), C y A no coinciden, por lo que LCS ( R ₃ , C ₁ ) obtiene la más larga de las dos secuencias, (A).

En el caso de LCS ( R ₃ , C ₂ ), C y G no coinciden. Tanto LCS ( R ₃ , C ₁ ) como LCS ( R ₂ , C ₂ ) tienen un elemento. El resultado es que LCS ( R ₃ , C ₂ ) contiene las dos subsecuencias (A) y (G).

Para LCS ( R ₃ , C ₃ ), C y C coinciden, por lo que C se agrega a LCS ( R ₂ , C ₂ ), que contiene las dos subsecuencias, (A) y (G), dando (AC) y (GC).

Para LCS ( R ₃ , C ₄ ), C y A no coinciden. Al combinar LCS ( R ₃ , C ₃ ), que contiene (AC) y (GC), y LCS ( R ₂ , C ₄ ), que contiene (GA), se obtienen un total de tres secuencias: (AC), (GC) y (GA).

Finalmente, para LCS ( R ₃ , C ₅ ), C y T no coinciden. El resultado es que LCS ( R ₃ , C ₅ ) también contiene las tres secuencias, (AC), (GC) y (GA).

El resultado final es que la última celda contiene todas las subsecuencias comunes más largas de (AGCAT) y (GAC); estas son (AC), (GC) y (GA). La tabla también muestra las subsecuencias comunes más largas para cada par posible de prefijos. Por ejemplo, para (AGC) y (GA), las subsecuencias comunes más largas son (A) y (G).

Enfoque de rastreo

Para calcular el LCS de una fila de la tabla LCS solo se necesitan las soluciones de la fila actual y de la fila anterior. Sin embargo, en el caso de secuencias largas, estas pueden ser numerosas y extensas, lo que requiere mucho espacio de almacenamiento. Se puede ahorrar espacio de almacenamiento guardando no las subsecuencias reales, sino la longitud de la subsecuencia y la dirección de las flechas, como se muestra en la tabla siguiente.

Las subsecuencias reales se deducen en un procedimiento de "rastreo" que sigue las flechas hacia atrás, comenzando desde la última celda de la tabla. Cuando la longitud disminuye, las secuencias deben haber tenido un elemento común. Son posibles varios caminos cuando se muestran dos flechas en una celda. A continuación se muestra la tabla para dicho análisis, con números coloreados en las celdas donde la longitud está a punto de disminuir. Los números en negrita trazan la secuencia, (GA). ^[6]

Relación con otros problemas

Para dos cadenas y , la longitud de la supersecuencia común más corta está relacionada con la longitud del LCS por ^[3] ${\displaystyle X_{1\dots m}}$ ${\displaystyle Y_{1\dots n}}$

${\displaystyle \left|SCS(X,Y)\right|=n+m-\left|LCS(X,Y)\right|.}$

La distancia de edición cuando solo se permite la inserción y eliminación (sin sustitución), o cuando el costo de la sustitución es el doble del costo de una inserción o eliminación, es:

${\displaystyle d'(X,Y)=n+m-2\cdot \left|LCS(X,Y)\right|.}$

Código para la solución de programación dinámica

Calcular la longitud del LCS

La función siguiente toma como entrada las secuencias X[1..m]y Y[1..n], calcula el LCS entre X[1..i]y Y[1..j]para todos 1 ≤ i ≤ my 1 ≤ j ≤ n, y lo almacena en C[i,j]. C[m,n]contendrá la longitud del LCS de Xy Y. ^[7]

función LCSLength(X[1..m], Y[1..n]) C = matriz(0..m, 0..n) para i := 0..m C[i,0] = 0 para j := 0..n C[0,j] = 0 para i := 1..m para j := 1..n si X[i] = Y[j] C[i,j] := C[i-1,j-1] + 1 demás C[i,j] := máx(C[i,j-1], C[i-1,j]) devuelve C[m,n]

Alternativamente, se podría utilizar la memorización .

Lectura de un LCS

La siguiente función retrocede en el tiempo a las opciones elegidas al calcular la Ctabla. Si los últimos caracteres de los prefijos son iguales, deben estar en un LCS. Si no es así, verifique cuál dio el LCS más grande de mantener y y haga la misma elección. Simplemente elija uno si tuvieran la misma longitud. Llame a la función con y . ${\displaystyle x_{i}}$ ${\displaystyle y_{j}}$i=mj=n

función backtrack(C[0..m,0..n], X[1..m], Y[1..n], i, j) si i = 0 o j = 0 devuelve "" si X[i] = Y[j] devuelve backtrack(C, X, Y, i-1, j-1) + X[i] si C[i,j-1] > C[i-1,j] devuelve backtrack(C, X, Y, i, j-1) devuelve backtrack(C, X, Y, i-1, j)

Lectura de todos los LCS

Si al elegir y se obtiene un resultado igualmente largo, se leen ambas subsecuencias resultantes. Esta función devuelve esto como un conjunto. Tenga en cuenta que esta función no es polinómica, ya que podría ramificarse en casi todos los pasos si las cadenas son similares. ${\displaystyle x_{i}}$ ${\displaystyle y_{j}}$

función backtrackAll(C[0..m,0..n], X[1..m], Y[1..n], i, j) si i = 0 o j = 0 devuelve {""} si X[i] = Y[j] devuelve {Z + X[i] para todos los Z en backtrackAll(C, X, Y, i-1, j-1)} R := {} si C[i,j-1] ≥ C[i-1,j] R := retrocederTodo(C, X, Y, i, j-1) si C[i-1,j] ≥ C[i,j-1] R := R ∪ retrocederTodo(C, X, Y, i-1, j) volver R

Imprime la diferencia

Esta función retrocederá a través de la matriz C e imprimirá la diferencia entre las dos secuencias. Tenga en cuenta que obtendrá una respuesta diferente si intercambia ≥y <con >y ≤a continuación.

función printDiff(C[0..m,0..n], X[1..m], Y[1..n], i, j) si i >= 0 y j >= 0 y X[i] = Y[j] imprimirDiff(C, X, Y, i-1, j-1) imprimir " " + X[i] de lo contrario si j > 0 y (i = 0 o C[i,j-1] ≥ C[i-1,j]) imprimirDiff(C, X, Y, i, j-1) imprimir "+ " + Y[j] de lo contrario si i > 0 y (j = 0 o C[i,j-1] < C[i-1,j]) imprimirDiff(C, X, Y, i-1, j) imprimir "- " + X[i] demás imprimir ""

Ejemplo

Sea “ ” y sea “ ”. La subsecuencia común más larga entre y es “ ”. La tabla que se muestra a continuación, que se genera mediante la función , muestra las longitudes de las subsecuencias comunes más largas entre los prefijos de y . La fila y la columna n.° muestran la longitud de la subsecuencia común más larga entre y . ${\displaystyle X}$XMJYAUZ ${\displaystyle Y}$MZJAWXU ${\displaystyle X}$ ${\displaystyle Y}$MJAUCLCSLength ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle X_{1..i}}$ ${\displaystyle Y_{1..j}}$

Los números resaltados muestran la ruta backtrackque seguiría la función desde la esquina inferior derecha hasta la esquina superior izquierda, al leer un LCS. Si los símbolos actuales en y son iguales, son parte del LCS, y vamos hacia arriba y hacia la izquierda (mostrados en negrita ). Si no, vamos hacia arriba o hacia la izquierda, dependiendo de qué celda tenga un número más alto. Esto corresponde a tomar el LCS entre y , o y . ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle X_{1..i-1}}$ ${\displaystyle Y_{1..j}}$ ${\displaystyle X_{1..i}}$ ${\displaystyle Y_{1..j-1}}$

Optimización de código

Se pueden realizar varias optimizaciones al algoritmo anterior para acelerarlo en casos del mundo real.

Reducir el conjunto de problemas

La matriz C en el algoritmo ingenuo crece cuadráticamente con las longitudes de las secuencias. Para dos secuencias de 100 elementos, se necesitaría una matriz de 10 000 elementos y se tendrían que realizar 10 000 comparaciones. En la mayoría de los casos del mundo real, especialmente en las diferencias y parches de código fuente, los comienzos y finales de los archivos rara vez cambian, y casi con certeza no ambos al mismo tiempo. Si solo han cambiado unos pocos elementos en el medio de la secuencia, se pueden eliminar el comienzo y el final. Esto reduce no solo los requisitos de memoria para la matriz, sino también la cantidad de comparaciones que se deben realizar.

función MCS(X[1..m], Y[1..n]) inicio := 1 m_fin := m n_fin := n Recortar los elementos coincidentes al principio  mientras start ≤ m_end y start ≤ n_end y X[start] = Y[start] inicio := inicio + 1 Recortar los elementos coincidentes al final  mientras start ≤ m_end y start ≤ n_end y X[m_end] = Y[n_end] m_fin := m_fin - 1 n_fin := n_fin - 1 C = matriz(inicio-1..m_fin, inicio-1..n_fin) solo recorre los elementos que han cambiado  para i := start..m_end para j := start..n_end el algoritmo continúa como antes...

En el mejor de los casos, una secuencia sin cambios, esta optimización eliminaría la necesidad de la matriz C. En el peor de los casos, un cambio en el primer y último elemento de la secuencia, solo se realizan dos comparaciones adicionales.

Reducir el tiempo de comparación

La mayor parte del tiempo que emplea el algoritmo ingenuo se dedica a realizar comparaciones entre elementos de las secuencias. En el caso de secuencias de texto, como el código fuente, conviene ver las líneas como elementos de la secuencia en lugar de caracteres individuales. Esto puede implicar comparaciones de cadenas relativamente largas para cada paso del algoritmo. Se pueden realizar dos optimizaciones que pueden ayudar a reducir el tiempo que consumen estas comparaciones.

Reducir cadenas a hashes

Se puede utilizar una función hash o suma de comprobación para reducir el tamaño de las cadenas en las secuencias. Es decir, para el código fuente donde la línea promedio tiene 60 o más caracteres de longitud, el hash o la suma de comprobación para esa línea podría tener solo entre 8 y 40 caracteres de longitud. Además, la naturaleza aleatoria de los hashes y las sumas de comprobación garantizaría que las comparaciones se acortaran más rápido, ya que las líneas de código fuente rara vez se modificarán al principio.

Esta optimización tiene tres inconvenientes principales. En primer lugar, es necesario dedicar una cierta cantidad de tiempo de antemano para calcular previamente los hashes de las dos secuencias. En segundo lugar, es necesario asignar memoria adicional para las nuevas secuencias con hashes. Sin embargo, en comparación con el algoritmo ingenuo utilizado aquí, ambos inconvenientes son relativamente mínimos.

El tercer inconveniente es el de las colisiones . Dado que no se garantiza que la suma de comprobación o el hash sean únicos, existe una pequeña posibilidad de que dos elementos diferentes se reduzcan al mismo hash. Esto es poco probable en el código fuente, pero es posible. Por lo tanto, un hash criptográfico sería mucho más adecuado para esta optimización, ya que su entropía será significativamente mayor que la de una suma de comprobación simple. Sin embargo, los beneficios pueden no valer la pena los requisitos de configuración y cálculo de un hash criptográfico para longitudes de secuencia pequeñas.

Reducir el espacio requerido

Si sólo se requiere la longitud de la LCS, la matriz se puede reducir a una matriz, o a un vector, ya que el enfoque de programación dinámica requiere sólo las columnas actual y anterior de la matriz. El algoritmo de Hirschberg permite la construcción de la secuencia óptima en sí misma en los mismos límites de tiempo cuadrático y espacio lineal. ^[8] ${\displaystyle 2\times \min(n,m)}$ ${\displaystyle \min(m,n)+1}$

Reducir los errores de caché

Chowdhury y Ramachandran idearon un algoritmo de espacio lineal de tiempo cuadrático ^{[9] [10]} para encontrar la longitud de LCS junto con una secuencia óptima que se ejecuta más rápido que el algoritmo de Hirschberg en la práctica debido a su rendimiento de caché superior. ^[9] El algoritmo tiene una complejidad de caché asintóticamente óptima bajo el modelo de caché ideal . ^[11] Curiosamente, el algoritmo en sí mismo no tiene en cuenta la caché ^[11], lo que significa que no toma ninguna decisión basada en los parámetros de caché (por ejemplo, tamaño de caché y tamaño de línea de caché) de la máquina.

Algoritmos aún más optimizados

Existen varios algoritmos que se ejecutan más rápido que el enfoque de programación dinámica presentado. Uno de ellos es el algoritmo Hunt–Szymanski , que normalmente se ejecuta en tiempo (para ), donde es el número de coincidencias entre las dos secuencias. ^[12] Para problemas con un tamaño de alfabeto acotado, se puede utilizar el Método de los Cuatro Rusos para reducir el tiempo de ejecución del algoritmo de programación dinámica por un factor logarítmico. ^[13] ${\displaystyle O((n+r)\log(n))}$ ${\displaystyle n>m}$ ${\displaystyle r}$

Comportamiento en cadenas aleatorias

Comenzando con Chvátal & Sankoff (1975), ^[14] varios investigadores han investigado el comportamiento de la longitud de la subsecuencia común más larga cuando las dos cadenas dadas se extraen aleatoriamente del mismo alfabeto. Cuando el tamaño del alfabeto es constante, la longitud esperada de la LCS es proporcional a la longitud de las dos cadenas, y las constantes de proporcionalidad (dependiendo del tamaño del alfabeto) se conocen como las constantes de Chvátal-Sankoff . Sus valores exactos no se conocen, pero se han demostrado límites superiores e inferiores en sus valores, ^[15] y se sabe que crecen inversamente proporcionalmente a la raíz cuadrada del tamaño del alfabeto. ^[16] Se ha demostrado que los modelos matemáticos simplificados del problema de la subsecuencia común más larga están controlados por la distribución de Tracy-Widom . ^[17]

Véase también

• Subsecuencia creciente más larga
• Subsecuencia alterna más larga
• Distancia de Levenshtein

Referencias

1. David Maier (1978). "La complejidad de algunos problemas sobre subsecuencias y supersecuencias". J. ACM . 25 (2). ACM Press: 322–336. doi : 10.1145/322063.322075 . S2CID  16120634.
2. Wagner, Robert; Fischer, Michael (enero de 1974). "El problema de la corrección de cuerda a cuerda". Revista de la ACM . 21 (1): 168–173. CiteSeerX 10.1.1.367.5281 . doi :10.1145/321796.321811. S2CID  13381535. 
3. L. Bergroth y H. Hakonen y T. Raita (7–29 de septiembre de 2000). Un estudio de los algoritmos de subsecuencia común más larga . Actas del Séptimo Simposio Internacional sobre Procesamiento de Cadenas y Recuperación de Información. SPIRE 2000. A Curuna, España: IEEE Computer Society. págs. 39–48. doi :10.1109/SPIRE.2000.878178. ISBN 0-7695-0746-8.S2CID10375334  .​
4. Ronald I. Greenberg (6 de agosto de 2003). "Límites en el número de subsecuencias comunes más largas". arXiv : cs.DM/0301030 .
5. Xia, Xuhua (2007). Bioinformática y la célula: enfoques computacionales modernos en genómica, proteómica y transcriptómica . Nueva York: Springer. p. 24. ISBN 978-0-387-71336-6.
6. Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest y Clifford Stein (2001). "15.4". Introducción a los algoritmos (2.ª ed.). MIT Press y McGraw-Hill. págs. 350–355. ISBN 0-262-53196-8.{{cite book}}: CS1 maint: multiple names: authors list (link)
7. Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2009) [1990]. "Programación dinámica". Introducción a los algoritmos (3.ª ed.). MIT Press y McGraw-Hill. pág. 394. ISBN 0-262-03384-4.
8. Hirschberg, DS (1975). "Un algoritmo espacial lineal para calcular subsecuencias comunes máximas". Comunicaciones de la ACM . 18 (6): 341–343. doi : 10.1145/360825.360861 . S2CID  207694727.
9. Chowdhury, Rezaul; Ramachandran, Vijaya (enero de 2006). "Programación dinámica sin memoria caché". Actas del decimoséptimo simposio anual ACM-SIAM sobre algoritmos discretos - SODA '06 . págs. 591–600. doi :10.1145/1109557.1109622. ISBN 0898716055.S2CID 9650418  .
10. Chowdhury, Rezaul; Le, Hai-Son; Ramachandran, Vijaya (julio de 2010). "Programación dinámica sin caché para bioinformática". Transacciones IEEE/ACM sobre biología computacional y bioinformática . 7 (3): 495–510. doi :10.1109/TCBB.2008.94. PMID  20671320. S2CID  2532039.
11. Frigo, Matteo; Leiserson, Charles E.; Prokop, Harald; Ramachandran, Sridhar (enero de 2012). "Algoritmos ajenos al caché". Transacciones ACM sobre algoritmos . 8 (1): 1–22. doi :10.1145/2071379.2071383.
12. Apostolico, Alberto; Galil, Zvi (29 de mayo de 1997). Algoritmos de comparación de patrones. Oxford University Press. ISBN 9780195354348.
13. Masek, William J.; Paterson, Michael S. (1980), "Un algoritmo más rápido para calcular distancias de edición de cadenas", Journal of Computer and System Sciences , 20 (1): 18–31, doi : 10.1016/0022-0000(80)90002-1 , MR  0566639.
14. Chvátal, Václáv ; Sankoff, David (1975), "Subsecuencias comunes más largas de dos secuencias aleatorias", Journal of Applied Probability , 12 (2): 306–315, doi :10.2307/3212444, JSTOR  3212444, MR  0405531, S2CID  250345191.
15. Lueker, George S. (2009), "Límites mejorados en la longitud promedio de las subsecuencias comunes más largas", Journal of the ACM , 56 (3), A17, doi :10.1145/1516512.1516519, MR  2536132, S2CID  7232681.
16. Kiwi, Marcos; Loebl, Martin; Matoušek, Jiří (2005), "Longitud esperada de la subsecuencia común más larga para alfabetos grandes", Advances in Mathematics , 197 (2): 480–498, arXiv : math/0308234 , doi : 10.1016/j.aim.2004.10.012 , MR  2173842.
17. Majumdar, Satya N.; Nechaev, Sergei (2005), "Resultados asintóticos exactos para el modelo de emparejamiento de Bernoulli de alineamiento de secuencias", Physical Review E , 72 (2): 020901, 4, arXiv : q-bio/0410012 , Bibcode :2005PhRvE..72b0901M, doi :10.1103/PhysRevE.72.020901, MR  2177365, PMID  16196539, S2CID  11390762.

Enlaces externos

• Diccionario de algoritmos y estructuras de datos: subsecuencia común más larga
• Una colección de implementaciones de la subsecuencia común más larga en muchos lenguajes de programación.
• Encontrar la subsecuencia común más larga en Python