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),

...