Extensiones y Algoritmos

Sobre el Longest Common Subsequence:

Extensiones y Algoritmos

Wilson Soto* Yoan Pinzón*

Resumen

Dadas dos palabras x e y sobre un alfabeto finito cualquiera, el problema de la Longest Common

Subsequence (LCS) — en castellano Subsecuencia Común Más Larga — consiste, como su

nombre sugiere, en encontrar cuál es el largo máximo que puede tener una palabra que sea

subsecuencia de x e y simultáneamente. El presente artículo muestra una revisión y análisis de las

diferentes extensiones y técnicas algorítmicas más conocidas hasta el momento y que dan

solución a este problema.

Palabras clave: Alineamiento, LCS, subsecuencia común más larga, similitud

Abstract

Given to strings x and y over a finite alphabet, the problem of the Longest Common Subsequence

(LCS) is to find the longest possible string that is a subsequence of both x and y simultaneously.

Here we present a survey and analysis of the different extensions and most common algorithmical

techniques known up to now that can solve this problem.

Keywords: Alignment, LCS, longest common subsequence, Similarity

1 Introducción

El Longest Common Subsequence (LCS) — en castellano Subsecuencia Común Más Larga — es

uno de los principales problemas en el campo de la stringology (algoritmos para manipulación de

cadenas de caracteres). El LCS es uno de los modelos computacionales más usados, pues sirve

como medida de similaridad entre un conjunto de secuencias por medio de su longitud, que se

muestra a través de los símbolos que contiene en común. Las aplicaciones que tiene el LCS son

entre otras la compresión de datos, reconocimiento sintáctico de patrones, procesamiento XML,

recuperación WEB, detección de intrusos y virus, comparación de archivos y bioinformática [36].

El presente artículo busca dar una clasificación de los algoritmos desarrollados para dar solución a

las extensiones del Longest Common Subsequence desde el punto de vista de las técnicas más

comúnmente usadas. Un mapa conceptual que puede resumir la idea básica de este artículo se ve

en la Fig. 1. Por ello, en la Sección 2 se presentan los conceptos básicos y la notación necesaria

para entender los problemas. La Sección 3 explica las técnicas usadas para dar solución a los

problemas, incluyendo los algoritmos y estudios que se han desarrollado para las diferentes

extensiones asociadas al problema del Longest Common Subsequence. La Sección 4 pretende dar

una visión práctica de dónde aparece el problema e intenta descubrir las posibles aplicaciones y

sobre todo un campo de investigación. La Sección 5 muestra las necesidades de investigación que

son actualmente requeridas y en las que se puede desarrollar un estudio más profundo.

* Departamento de Ingeniería de Sistemas e Industrial, Grupo ALGOS-UN, Universidad Nacional de

Colombia, Bogotá D.C., Colombia. Email: {wesotof,ypinzon}@unal.edu.co

2

Fig. 1. Mapa conceptual del problema del longest common subsequence

2 El problema del longest common subsequence

Las siguientes definiciones son necesarias para entender este artículo: La distancia entre dos

cadenas de caracteres (strings) x y y es el mínimo costo de operaciones para transformar x en y. El

costo de una secuencia de operaciones es la suma de los costos de las operaciones individuales.

Alineamiento significa insertar espacios tal que letras iguales se alineen, evitando que ocurra lo

mismo con los espacios, pero aceptándolos al comienzo o final del string (c.f. Fig. 2).

G C A T - A T T -

- C A T G - T T G

Fig. 2. Alineamiento

Dado un alineamiento se calcula una medida de similitud, esta medida tiene tres posibilidades: (i)

de letra-letra, (ii) error letra-letra y (iii) letra-espacio (o viceversa). Los tipos de alineamiento se

resumen en [16]. Algunos de los algoritmos de alineamiento más conocidos son: Needleman y

Wunsch (1970), SW (Smith & Waterman, 1981), FASTA (1988) y BLAST (1990) que son

relacionados en [9].

3

La similitud de secuencias tiene diversas aplicaciones, entre otras ensamblaje de fragmentos,

agrupamientos, minería de datos, comparación de genomas, análisis fitogenético, homologías1

funcionales y estructurales. Entre las medidas de similitud se encuentran la distancia de Hamming,

La distancia de Levenshtein, la distancia de Episodio y el Longest Common Subsequence. El LCS

permite únicamente inserciones y eliminaciones, todas de costo unitario. El nombre de esta

distancia refiere a que esta medida representa la longitud más larga de acoplamiento entre los

caracteres que pueden estar entre dos cadenas de caracteres, teniendo en cuenta el orden de las

letras, caracteres o símbolos.

La siguiente es la notación formal usada. Sea S el Conjunto de elementos llamados símbolos,

caracteres o letras. Por ejemplo S = {A, C, G, T}. Un string o palabra es una secuencia finita de

símbolos que pertenece a un alfabeto S. Sea la función s de {1,…,n} sobre S tal que s = a1a2 ... an

donde ai = s(i) Î S. e es un string sin ningún símbolo o carácter. Sn define el conjunto de strings o

palabras de longitud n. Por ejemplo S3 = {LAS, ESS, FGR, DED, …}. Similarmente, S* se define

como el conjunto de strings sobre S de cualquier longitud. Por ejemplo S* = {ACT, TAC, TAG,

ACGT, CT, AG, ACTG, GG, AA, e, ...}. |s| indica la longitud de un string s. Por ejemplo, para s =

AGCATT, |s| = 6 o si s = e, |s| = 0. Un prefijo de s se define como el string v tal que s = vt para

ciertos t Î S*. Así mismo, un sufijo de s se define como el string v tal que s = tv para ciertos t

Î S*. Definimos d: S* x S* ® R como un función de distancia. Igualmente definimos las

siguientes operaciones:

— Inserción: Insertar un carácter en un string. Por ejemplo la operación de inserción sobre el

string s = TCA adicionando la letra G, es s’ = TCGA.

— Eliminación: Eliminar un carácter de un string. Por ejemplo la operación de eliminación

sobre el string s = TCGA eliminando una letra, es s’ = TGA.

— Sustitución: Reemplazar una letra en un string. Por ejemplo la operación de sustitución

sobre el string s = AATC reemplazando una letra por otra, es s’ = ATTC.

Con lo anterior, la definición del problema del LCS consiste en: Dado S y las secuencias S1, S2 Î

S*, |S1| = n y |S2| = m (m £ n), LCS(S1, S2) es una secuencia W tal que:

1. i, 1 £ i £ |W|-1,
j, j’: 1£ j < j’ £ |S1|,
k, k’: 1 £ k £ k’ £ |S2|

tal que W[i] = S1[j] = S2[k], y W[i+1] = S1[j’] = S2[k’];

2. W’ Î S*: (1) y |W’| > |W|

El objetivo es en encontrar cuál es el largo máximo que puede tener un string que sea subsecuencia

de S1 y S2 simultáneamente. Dado S, un conjunto de secuencias, s es una secuencia común de S si

esta es una subsecuencia de cada secuencia en S. La Fig. 3 muestra un ejemplo de algunas de las

subsecuencias comunes para dos cadenas S1 y S2 con |LCS(S1, S2)| = 9.

Fig. 3. Ejemplos de subsecuencias comunes para S1 y S2.

sc3 y sc4 son LCS.

1 proteínas que tienen un origen evolutivo común

S1= 1 0 0 2 3 2 1 1 0 2 2 2 3 3 1 0 0 1

S2= 0 1 1 1 3 3 3 0 2 1 2 1 1 0 1 2 1

sc1= 1 3 2 1 2 1

sc2= 0 1 1 3 3 1

sc3= 0 1 1 0 2 2 1 0 1

sc4= 1 0 2 2 1 1 0 2 1

4

En cuanto a la complejidad, el LCS es un problema que puede ser resuelto en tiempo polinomial

con programación dinámica para dos strings, o para algún número fijo de strings, pero este se

convierte en un problema “NP-Hard” en general para un número arbitrario k de strings. En [24] se

dedica un capítulo completo a la complejidad del algoritmo y la relación con la teoría NP que se

resume al problema de maximización siguiente: “Dado un lenguaje finito no vacío X, encontrar

una subsecuencia común de X de longitud máxima”. Algunos trabajos ya han estudiado el tema

como [3] [10], que tratan el tema con soluciones heurísticas que dan solución a la subsecuencia

común más larga en tiempo polinomial.

2.1 Extensiones del LCS

2.1.1. All Longest Common Subsequence (ALCS)

El problema del all Longest Common Subsequence consiste en buscar todas las subsecuencias

comunes más largas entre X y Y. Los estudios completos sobre los límites en tiempo de ejecución

sobre todos los algoritmos que generan ALCS distintos y ALCS embebidos (posiciones en ambos

strings para los cuales los caracteres del LCS correspondan) se encuentran en [1]. Una de las

variaciones presentadas en este tipo de extensión es el all semi-local Longest Common

Subsequence [42], donde cada string es comparado contra todos los sufijos del otro string.

2.1.2 Length Longest Common Subsequence (LLCS)

La longitud de un Longest Common Subsequence de dos o más strings es una útil medida de su

similaridad. La longitud esperada de un LCS es proporcional a la longitud de las secuencias dadas

y dependiente del tamaño del alfabeto [20]. La estimación de esta longitud esperada promueve

algunos problemas de interés combinatorial.

En [32] algunos de los algoritmos desarrollados

...