Longest Common Subsequence Distance

La distancia entre dos strings $x$ e $y$ es el costo minimal de operaciones para transformar una $x$ en $y.$ La Longest Common Subsequence Distance (distancia LCS) se define considerando como operaciones válidas las inserciones y eliminaciones (ambas con costo 1), a diferencia de la distancia de Levenshtein que además permite sustituciones. Es decir, sólo se permiten agregar o eliminar símbolos en $x$.

La distancia LCS es una métrica frecuentemente utilizada en informática y bioinformática para estudiar la disimilitud entre dos secuencias, como por ejemplo, secuencias de ADN.

Definición

Notemos que insertar símbolos a $x$ puede ser visto como eliminar símbolos de $y$, y viceversa. Es decir, la distancia LCS corresponde a transformar $x$ e $y$ en una misma string $z$ realizando sólo eliminaciones, además, buscamos el proceso que resulte en el menor número de eliminaciones, lo que se traduce en obtener el string $z$ más largo posible. Esto permite definir la distancia LCS como el largo de la subsecuencia común más larga (LCS). A continuación se presenta la definición formal.

Una subsecuencia de un string $x=x_1x_2...x_m\in \Sigma^*$ es un string $\sigma=\sigma_1\sigma_2...\sigma_s\in\Sigma^*$ que resulta de eliminar $m-s$ símbolos de $x$, con $s\leq m$, donde $\Sigma$ es el alfabeto. Es decir, corresponde a una secuencia de símbolos de $x$ que respetan su orden relativo, pero sin necesariamente ser adyacentes entre sí. La subsecuencia común más larga (LCS por sus siglas en inglés) entre dos strings $x,y\in\Sigma^*$ es la subsecuencia de mayor longitud que está presente tanto en $x$ como en $y$.

Sean $x_1,x_2\in\Sigma^*$ dos secuencias con longitudes $l_1$ y $l_2$, respectivamente, y sea $l(x_1,x_2)$ la longitud de la LCS entre $x_1$ y $x_2$. La distancia LCS entre $x_1$ y $x_2$, denotada por $D_{LCS}(x_1, x_2)$, se define como:

\[ D\_{LCS}(x_1, x_2) = l_1 + l_2 - 2 \cdot l(x_1, x_2). \]

Intuitivamente, esta fórmula captura el número mínimo de operaciones de inserción y eliminación necesarias para transformar la cadena $x_1$ en la cadena $x_2$, las cuales se pueden describir en los siguientes dos casos:

Los caracteres que no están en la LCS deben ser eliminados de $x_1$, lo que corresponde a $l_1 - l(x_1, x_2)$ eliminaciones.
Los caracteres de $x_2$ que no están en la LCS deben ser insertados en $x_1$, lo que corresponde a $l_2 - l(x_1, x_2)$ inserciones.

Sumando ambas cantidades se obtiene la fórmula.

Propiedades

Sean $x,y,z\in\Sigma^*$ strings. La distancia LCS cumple las siguientes propiedades:

(P1) No negatividad: $D_{LCS}(x, y) \geq 0$.
(P2) Axioma de coincidencia: $D_{LCS}(x,y)=0\Longleftrightarrow x = y$.
(P3) Simetría: $D_{LCS}(x,y) = D_{LCS}(y, x)$.
(P4) Desigualdad triangular: $D_{LCS}(x, z) \leq D_{LCS}(x, y) + D_{LCS}(y, z)$.

Es decir, la distancia LCS es una métrica formal (en el sentido matemático). (P1) nos dice que la distancia LCS nunca es negativa. (P2), que la distancia es cero sólo cuando los dos strings son idénticos. (P3), por otro lado, indica que la distancia LCS es conmutativa, es decir, el costo de transformar $x$ a $y$ es igual al costo de transformar $y$ en $x$. Finalmente, (P4) corresponde a la desigualdad triangular, que se interpreta como que transformar $x$ a $z$ directamente nunca es más costoso que transformar primero $x$ a $y$ y luego $y$ a $z$.

Ejemplo 1

Como primer ejemplo consideremos $x_1 = \text{AGUA''}$ y $x_2 = \text{GATO''}$. Primero debemos calcular las longitudes: $l_1 = l_2=4$. Luego, debemos identificar la LCS, que en este caso se identifica fácilmente por inspección, y corresponde a la subsecuencia $\text{``GA''}$, cuyo largo es $2$, es decir, $l(x_1,x_2)=2$. Finalmente, se tiene que:

\[ D\_{LCS}(x_1,x_2) = l_1+l_2-2l(x_1,x_2) = 4 + 4 - 4 = 4 \]

Y podemos comprobar que para transformar $x_1$ en $x_2$, con la menor cantidad de operaciones, primero se debe pasar de $\text{AGUA''}$ a $\text{GA''}$, que son 2 eliminaciones, y luego se debe pasar de $\text{GA''}$ a $\text{GATO''}$, lo cual corresponde a 2 inserciones, resultando en un total de 4 operaciones.

Ejemplo 2

Consideremos ahora los strings $x_1 = \text{KARMA''}$ y $x_2 = \text{KAMELE''}$. En este caso las longitudes son $l_1 = 5$ y $l_2 = 6$. Además, la LCS es la subsecuencia $\text{``KAM''}$, por lo que $l(x_1,x_2)=3$. Entonces la distancia LCS corresponde a

\[ D\_{LCS}(x_1,x_2) = l_1+l_2-2l(x_1,x_2) = 5 + 6 - 6 = 5 \]

Y podemos comprobar que para transformar $x_1$ en $x_2$, con la menor cantidad de operaciones, primero se debe pasar de $\text{KARMA''}$ a $\text{KAM''}$, que son 2 eliminaciones, y luego se debe pasar de $\text{KAM''}$ a $\text{KAMELE''}$, lo cual corresponde a 3 inserciones, resultando en un total de 5 operaciones.

Código

Según la fórmula que define a la distancia LCS, calcular $D_{LCS}(x,y)$ se reduce a encontrar la LCS entre $x$ e $y$, pues lo demás es calcular las longitudes de cada string. El enfoque tradicional para resolver el problema de encontrar la LCS entre dos strings $x,y$ es utilizar programación dinámica para encontrar la LCS de todas las posibles combinaciones de prefijos de $x$ e $y$.

Formalmente, sean $x=x_1x_2...x_m$ y $y=y_1y_2...y_n$ dos strings. Se define la matriz $R$ de $(m+1)\times (n+1)$ tal que $R[i,j]$ es el largo de la LCS entre $x[1 ...i]=x_1...x_i$ e $y[1 ...j]=y_1...y_j$. La matriz $R$ cumple con la siguiente recurrencia:

\[ R[i,j] = \begin{cases} 0, & \text{si $i=0$ ó $j=0$,} \\ R[i-1, j-1]+1, & \text{si $x_i=y_j$,} \\ \max \{R[i-1, j], R[i,j-1]\}, & \text{si $x_i\neq y_j$} \end{cases} \]

Si estudiamos $x[1 ...i]$ e $y[1 ...j]$, entonces la recursión anterior plantea tres casos. El primero, si alguno de los prefijos no tiene símbolos, entonces la LCS tiene largo cero. En el segundo, si el último símbolo de ambos prefijos es el mismo, entonces podemos quitar ese símbolo de ambos prefijos y consultar la solución para $x[1 ...i-1]$ e $y[1 ...j-1]$, para luego sumar 1 por el símbolo que se quitó. El tercer y último caso dice que si el último símbolo de ambos prefijos es distinto, entonces estos no aportan simultáneamente a la LCS, por lo que debemos ver las soluciones quitando el último símbolo de $x[1 ...i]$ ó $y[1 ...j]$ y quedarnos con la mayor (la más larga).

Así, utilizando esta recurrencia podemos obtener la matriz $R$, y el largo $l(x,y)$ buscado se encontrará en $R[m,n]$. El siguiente código presenta la función largoLCS que recibe dos strings y retorna el largo de la LCS entre ellas, es decir, el valor de $R[m,n]$ anteriormente mencionado. Esta función utiliza programación dinámica para resolver el problema. Por otro lado, la función distanciaLCS recibe dos strings y calcula la distancia $D_{LCS}$ entre esas según la fórmula que la define. Finalmente, en main se resuelven los dos ejemplos antes mencionados, obteniéndose la misma respuesta.

# include <iostream>
# include <string>
# include <vector>
# include <algorithm>

int largoLCS(std::string &x, std::string &y) {
  // Función que calcula la matriz R y retorna el largo de la LCS entre x e y.
  int m = x.length();
  int n = y.length();
  // Al llenar con ceros se abarca el caso base para i=0 ó j=0
  std::vector<std::vector<int>> R(m + 1, std::vector<int>(n + 1, 0));

  for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= n; j++) {
      // Revisamos si coincide el último símbolo del prefijo correspondiente (segundo caso)
      if (x[i] == y[j]) {
        R[i][j] = 1 + R[i - 1][j - 1];
      }
      // Si no coinciden, estamos en el último caso.
      else {
        R[i][j] = std::max(R[i - 1][j], R[i][j - 1]);
      }
    }
  }
  return R[m][n];
}

int distanciaLCS(std::string &x, std::string &y) {
  int l_1 = x.length();
  int l_2 = y.length();
  int l_xy = largoLCS(x, y);

  // Aplicamos la fórmula para la distancia LCS
  return l_1 + l_2 - 2 * l_xy;
}

int main() {
  // Ejemplo 1: x_1 = AGUA y x_2 = GATO
  std::cout << "Ejemplo 1:\n";
  std::string x_1 = "AGUA";
  std::string x_2 = "GATO";
  std::cout << "x_1: " << x_1 << ", x_2: " << x_2 << std::endl;
  std::cout << "Largo LCS: l(x_1,x_2) = " << largoLCS(x_1, x_2) << std::endl;
  std::cout << "Distancia LCS: D_LCS(x_1,x_2) = " << distanciaLCS(x_1, x_2) << std::endl;
  std::cout << std::endl;

  // Ejemplo 2: x_1 = KARMA y x_2 = KAMELE
  std::cout << "Ejemplo 2:\n";
  x_1 = "KARMA";
  x_2 = "KAMELE";
  std::cout << "x_1: " << x_1 << ", x_2: " << x_2 << std::endl;
  std::cout << "Largo LCS: l(x_1,x_2) = " << largoLCS(x_1, x_2) << std::endl;
  std::cout << "Distancia LCS: D_LCS(x_1,x_2) = " << distanciaLCS(x_1, x_2) << std::endl;

  return 0;
}

Referencias

Wagner, R. A., & Fischer, M. J. (1974). The string-to-string correction problem. Journal of the ACM (JACM), 21(1), 168-173.
Bergroth, L., Hakonen, H., & Raita, T. (2000, September). A survey of longest common subsequence algorithms. In Proceedings Seventh International Symposium on String Processing and Information Retrieval. SPIRE 2000 (pp. 39-48). IEEE.
Needleman, S. B., & Wunsch, C. D. A general method applicable to the search for similarities in the amino acid sequence. Journal of Molecular Biology, 48, 433-453.
Apostolico, A., & Guerra, C. (1987). The longest common subsequence problem revisited. Algorithmica, 2(1), 315-336.
Navarro, G. (2001). A guided tour to approximate string matching. ACM computing surveys (CSUR), 33(1), 31-88. $$