Búsqueda de la Combinación de Segmentos Binarios para la Reconstrucción de una Cadena Binaria Original

B´usqueda de la Combinaci´on de Segmentos Binarios para la Reconstrucci´on de una Cadena Binaria Original Sebasti´an Alexis Moraga Garrido Junio de 2014 Resumen Propuesta de un algoritmo para la b´ usqueda de la combinaci´ on de segmentos binarios que reconstruyen a una cadena binaria original. La propuesta es comparada con un algoritmo de fuerza bruta bajo el criterio de crecimiento asint´ otico temporal. Los resultados de tal comparaci´ on muestran que la propuesta resulta superior al algoritmo de fuerza bruta.

1. 1.1.

Introducci´ on Motivaci´ on de la propuesta

Seg´ un Salomon en [11, p. 21], la disminuci´on de la redundancia en la representaci´on de datos es la base para la compresi´ on de los datos. Una manera de medir la redundancia en la representaci´on de datos, es a trav´es de la medici´ on de la entrop´ıa actual y total sobre ellos. Por lo que la compresi´on de datos est´a directamente relacionada con la disminuci´ on de su entrop´ıa, de manera que al recodificar los datos se elimina la redundancia en su representaci´ on. Para lograr esto, se debe implementar un m´etodo de recodificaci´on tal que se logre una cercan´ıa al m´ınimo de la redundancia. Seg´ un Salomon en [10, p. 47], la entrop´ıa de los datos est´a representada por H(X) =

X

p(x) lg(

x∈X

1 ) p(x)

(1)

donde X es una variable aleatoria de un conjunto discreto de s´ımbolos x ∈ X, con probabilidad p(x) = P (X = x). Y la redundancia, seg´ un Salomon en [10, p. 47], es la diferencia entre la entrop´ıa total y la actual, expresada a trav´es de ! ! X X X 1 1 1 p(x) lg( ) = lg(kXk) − p(x) lg( ) (2) R(X) = P lg( ) − P p(x) p(x) x∈X

x∈X

x∈X

donde P es una probabilidad igual para cada x ∈ X. Lo que se busca en compresi´ on de datos es que R(X) sea cercano o igual a 0. Un algoritmo que disminuye la redundancia en datos es el propuesto por Huffman en [5] llamado algoritmo de Huffman, que es un tipo de algoritmo de compresi´on de datos de representaci´on m´ınima. El algoritmo de Hufmman permite construir una representaci´on con redundancia cercana a la m´ınima para recodificar los datos. Sin embargo, los algoritmos de compresi´on de datos de representaci´on m´ınima s´olo son posibles de aplicar una sola vez sobre el c´ odigo a recodificar. Al aplicar tales m´etodos m´as de una vez, no se consigue una

1

nueva disminuci´ on de la redundancia. Esto es debido a que durante la primera aplicaci´on se consigui´ o una recodificaci´ on de los datos con la menor redundancia posible. Una manera de aplicar nuevamente un conjunto de algoritmos de compresi´on de representaci´on m´ınima es a trav´es de la inducci´ on de entrop´ıa sobre los datos. Por lo tanto, se requiere de un m´etodo que induzca entrop´ıa sobre los datos. Un m´etodo para inducir entrop´ıa sobre los datos es el descrito a trav´es de una funci´on que ser´a representada como S B = χκB (S A ) B

(3)

A

que devolver´ a S , donde S ser´ a una cadena de s´ımbolos utilizando s´ımbolos pertenecientes al conjunto A; B ser´ a un conjunto de s´ımbolos que permitir´a encontrar un conjunto de cadenas de s´ımbolos que configuren a S A , que ser´ a llamada familia de cadenas SB ımbolos original A, tal que A , no importando el conjunto de s´ B ∀Sk ∈ SA , Sk = S A ; y S B ser´ a una cadena en SB escogida a trav´ e s de alg´ u n criterio κ predefinido, tal que A κ podr´ıa ser definido como una funci´ on heur´ıstica. Sin embargo, este m´etodo para inducci´on de entrop´ıa no podr´ a ser aplicado infinitas veces sobre S A , sino que podr´a ser aplicado mientras la secuencia de s´ımbolos B S pueda ser recodificada nuevamente en forma m´ınima, provocando una disminuci´on en el tama˜ no de cada s´ımbolo en B. A continuaci´ on, se describe un m´etodo de compresi´on utilizando la funci´on χκB (S A ) y el algoritmo de B Huffman: Sea Sf los datos resultantes una vez alcanzado un punto en el que no es posible seguir la disminuci´ on A de la entrop´ıa sobre S . 1. Aplicar el algoritmo de Huffman sobre S A , obteniendo S H . 2. Si H(S H ) < H(S A ), entonces continuar en el paso 2a. Sino, SfB ← S H y finalizar. a) Aplicar S B ← χκB (S H ); B 6= H. Luego, S A ← S B . b) Volver al paso 1. Este trabajo presenta las bases para la implementaci´on de la funci´on χκB (S A ). Espec´ıficamente, se dar´ aa B se obtendr´ a n a . Las cadenas S ∈ S conocer un m´etodo para la b´ usqueda del conjunto B y la familia SB k A A partir de combinaciones de algunos s´ımbolos en B, tal que cada cadena Sk tenga una alineaci´on global con un un S ∈ SB toda la cadena S A , sin excepciones. Finalmente, la funci´on χκB (S A ) escoger´a alg´ A utilizando alg´ B criterio κ predefinido, tal que S ← S.

1.2.

Trabajos relacionados

Los trabajos publicados que m´ as cercanos est´an al presente son los relacionados con algoritmos de alineaci´ on de cadenas: El algoritmo propuesto en este trabajo busca cadenas Sh formadas a partir de combinaciones de s´ımbolos de un conjunto B que se alineen con una cadena S A , mientras que los trabajos ya hechos corresponden a algoritmos que alinean un conjunto de cadenas preexistentes. Los m´etodos de alineaci´ on propuestos en los trabajos publicados pueden ser de alineaci´on de pares o de alineaci´ on m´ ultiple. Los de alineaci´ on de pares pueden ser clasificados en los siguientes tres grupos: M´etodos dot-matrix, m´etodos de programaci´ on din´ amica y m´etodos de palabras. Los de alineaci´on m´ ultiple pueden ser clasificados en los siguientes cinco grupos: m´etodos de programaci´on din´amica, m´etodos progresivos, m´etodos ´ iterativos, an´ alisis de perfil, y m´etodos basados en modelos formales. Estos u ´ltimos pueden ser basados en modelos ocultos de Markov, transformada Burrows-Wheeler, algoritmos gen´eticos, refundido simulado, entre otras t´ecnicas formales. Algunos de los m´etodos de alineaci´ on m´ ultiple son el m´etodo de Wilbur-Lipman descrito en [15], Clustal propuesto por Higgins y Sharp en [4], Clustal V descrito por Higgins et Al. en [3], Clustal W propuesto

2

por Thompson et Al. en [14], Clustal X propuesto por Thompson et Al. en [13], T-Coffee propuesto por Notredame et Al. en [9], MAFFT propuesto por Katoh et Al. en [6], MUSCLE propuesto por Edgar en [1]. Tales m´etodos, si bien permiten alinear cadenas, utilizan m´etodos algor´ıtmicos distintos al propuesto en el presente trabajo. M´etodos como el de Wilbur-Lipman descrito en [15] utilizan heur´ısticas para optimizar el tiempo de ejecuci´ on de la alineaci´ on de dos cadenas. En contraste, el criterio κ en la funci´on χκB (S A ) de la expresi´ on (3), donde κ puede ser implementado a trav´es de una heur´ıstica, es utilizado en la selecci´ on de A alg´ un Sh ∈ SB y no en la alineaci´ o n de cada S con S . h A El trabajo publicado que va en una l´ınea similar al presente es el algoritmo de programaci´on din´ amica conocido como algoritmo Needleman-Wunsch de alineaci´on global, dado a conocer por Needleman y Wunsch en [8]. Este algoritmo permite alinear dos cadenas S1 y S2 buscando hacerlas coincidir desde los primeros s´ımbolos hasta los u ´ltimos. Otro trabajo similar al de Needleman y Wunsch, es el algoritmo de programaci´ on din´ amica conocido como algoritmo Smith-Waterman de alineaci´on local propuesto por Smith y Waterman en [12] y mejorado por Gotoh en [2]. El algoritmo Smith-Waterman permite alinear dos cadenas S1 y S2 localmente buscando regiones de similitud de S2 en S1 .

1.3.

Definici´ on de conceptos

Sea B = {0, 1} el conjunto de los valores binario. Sea S = B? una cadena binaria, tal que S = b1 b2 b3 . . . bn , donde bk es un bit en B. Sea B = {s1 , s2 , s3 , . . . , sm } un conjunto de segmentos de cadenas binarias que ser´ an llamadas s´ımbolos, donde sk es un segmento de S tal que sk ⊂ S; sk = bp bq ..., ksk k ≥ 2 Sea S B una cadena compuesta por s´ımbolos sk ∈ B, tal que (1,a) (a+1,b) b+1,c s2 s3

S B = s1

. . . s(y+1,z) n

(4)

(i,j)

donde z = kS B k y sk es un s´ımbolo en B que abarca desde un bit bi hasta uno bj . Sea S A una cadena compuesta por s´ımbolos s0k ∈ A, tal que 0(1,a) 0(a+1,b) 0(b+1,c) s2 s3

S A = s1

. . . s0(y+1,z) n

(5)

0(i,j)

donde z = kS A k y sk es un s´ımbolo en A que abarca desde un bit bi hasta uno bj . Sea SB una familia de cadenas S, tal que cada cadena S sea una combinaci´on de s´ımbolos s ∈ B alineados A globalmente con S A . A las cadenas S ∈ SB an dependencias, porque la combinaci´on secuencial A se les llamar´ de s´ımbolos sk ∈ B que conforma a S depende de S A al estar ambas cadenas S y S A alineadas. Y a la familia de cadenas SB a familia de dependencias. A se le llamar´ A Formalmente, una dependencia cualquiera Sh ∈ SB A es una cadena alineada con S , tal que si Sh = (1,a) (a+1,b) b+1,c (y+1,z) s3 . . . sn , entonces s1 s2 (1,b)

s1

∈ Sh = head(S A ), s(y+1,z) ∈ Sh = tail(S A ) n

(6)

Un s´ımbolo sa se dir´ a s´ımbolo b´ asico cuando no est´e definido por ning´ un otro s´ımbolo sb , tal que (@sb )sb ⊂ sa ; sb , sa ∈ B

(7)

Y un s´ımbolo sa se dir´ a s´ımbolo compuesto cuando sea posible definirlo a trav´es de un conjunto B 0 , tal que B 0 ⊂ B, (∀s ∈ B 0 )s ⊆ sa ; sa ∈ B (8) Entonces, los s´ımbolos sk de una cadena binaria S ser´an patrones autorrepetitivos b´asicos o compuestos en S. 3

1.4.

Propuesta

Lo que se propone en este trabajo es un algoritmo que, dada una cadena S A , determine una familia de dependencias SB ımbolos sk ∈ B, donde cada dependencia Sh ∈ SB A de cadenas Sh compuestas por s´ A se alinee globalmente con la cadena S A . Para conocer el conjunto B, se buscar´ an s´ımbolos sk en la cadena S A . Para esto, se propone un algoritmo para la b´ usqueda de los s´ımbolos sk ∈ S A en la secci´on 2.1. Una vez conocidos los s´ımbolos sk ∈ B, se procede a analizar cu´ ales son sus posibles combinaciones, conformando las dependencias Sh ∈ SB A , tales que configuren nuevamente a S A . Una forma de encontrar la familia de dependencias SB es de la optimizaci´on de la expresi´on (9), A es a trav´ intentando que siempre fB (S A ) = kS A k.  0 ; kS A k = 0  A ∞ ; @s ∈ B, s = head(S A ) ∨ kS A k < 0 (9) fB (S ) =  A fB (head(S ) − s) + ksk, s ∈ B ; ∃s ∈ B, s = head(S A ) ∧ kS A k > 0 Una manera de implementar algor´ıtmicamente la expresi´on (9) es a trav´es del algoritmo 1 de fuerza bruta, que explora todas las combinaciones de s´ımbolos en B para conformar dependencias Sh ∈ SB A , sin descartar ninguna combinaci´ on. Algoritmo 1 Algoritmo de fuerza bruta para encontrar la familia de dependencias SB A , derivado de la expresi´ on (9). Entrada: Cadena binaria S A ; conjunto de s´ımbolos B; y, variable S para construir una dependencia. Salida: Familia de dependencias SB A con las dependencias S encontradas. 1: SB A ←∅ 2: function dependencias(S A ,B,S) 3: si kS A k = 0 entonces 4: SB A ←S 5: devolver 6: si no 7: para todo s ∈ B hacer 8: si kS A k ≥ ksk y S A comienza con s entonces 9: x ← removeFromHead(S A ,s) 10: dependencias(x,B,S ∪ s) 11: fin si 12: fin para 13: fin si 14: fin function n

La b´ usqueda de soluciones a trav´es de la expresi´on (9) resulta en una complejidad temporal O(n c ); c ≈ √ 6 n, n = kS A k respecto al n´ umero de comparaciones. Una propuesta de una soluci´on de menor tiempo se da a conocer en este trabajo, eliminando aquellos caminos sin soluci´on (ver ´ıtem 3 en la secci´on 2). M´ as adelante (en la secci´ on 2), se da a conocer los pasos del algoritmo propuesto para obtener el conjunto D de las dependencias de una cadena S. Luego (en la secci´on 3), se presentan las conclusiones respecto a la comparaci´ on del algoritmo propuesto y el de fuerza bruta derivado de la expresi´on (9).

2.

Propuesta del algoritmo de b´ usqueda de dependencias El algoritmo que se propone para la obtenci´on de dependencias consta de los siguientes cinco pasos: 4

1. Buscar s´ımbolos sk b´ asicos y compuestos repetidos en la cadena principal S A para conformar el conjunto B (ver secci´ on 2.1). 2. Obtener conjunto de alineaciones locales por cada s´ımbolos sk ∈ B sobre la cadena principal S A (ver secci´ on 2.2). 3. Limpiar conjunto de alineaciones de cada s´ımbolos sk ∈ B sobre la cadena S A obtenido en el paso 2 (ver secci´ on 2.3). 4. Obtener dependencias Sh a partir del resultado del paso 3, las cuales conformar´an la familia de dependencias SB on 2.4). A (ver secci´ Estos pasos se ver´ an a trav´es de un ejemplo. Para esto, sea S A = 0110000111010. En las siguientes secciones (desde la secci´ on 2.1 hasta la 2.4) se muestran los pasos anteriores, respectivamente.

2.1.

Buscar s´ımbolos repetidos en la cadena principal – paso 1

La obtenci´ on de s´ımbolos repetidos se realiza de la siguiente manera: 1. Recorrer la cadena S A secuencialmente obteniendo un conjunto de s´ımbolos b´asicos sk (definidos a trav´es de la expresi´ on (7)) de la siguiente forma B = {si ; si = bi bi+1 ⊂ S A , i = 1 . . . (kS A k − 1)}

(10)

Aplicando este subpaso se obtienen los resultados mostrados en la tabla 1, con lo que B queda de la siguiente forma B1 = {01, 11, 10, 00, 00, 00, 01, 11, 11, 10, 01, 10} (11) 2. Disponer la cadena S A en una matriz tanto en fila como en columna, de la cual s´olo se utilizar´ a su tri´ angulo inferior, como se muestra en la tabla 2. 3. Por cada fila, buscar las coincidencias del valor representado por la fila con el valor representado por la columna. Si existe coincidencia, marcar la coincidencia con un 1. El resultado de aplicar este subpaso sobre S A se muestra en la tabla 3, y corresponde a los s´ımbolos s1 = 000, s2 = 11, s3 = 00, s4 = 10, s5 = 01, s6 = 011, s7 = 110, s8 = 01, s9 = 10

(12)

4. Para obtener los patrones a partir de la matriz que se muestra en la tabla 3, se deben considerar el grupo de celdas dispuestas en diagonal descendente, los cuales corresponder´an a los s´ımbolos compuestos sk , tal que ||sk || > 2. Una representaci´ on gr´afica de estos s´ımbolos se muestra en la tabla 4. Considerando los s´ımbolos de la expresi´ on (12), el resultado obtenido de este subpaso es B2 = {000, 011, 110}

(13)

El conjunto B resultante corresponder´ a a la uni´on del resultado de las expresiones (11) y (13), tal que B= B=

B1 ∪ B2 {01, 11, 10, 00, 00, 00, 01, 11, 11, 10, 01, 10} ∪ {000, 011, 110}

(14)

Luego, el conjunto B resulta en B = {00, 000, 01, 10, 11, 011, 110}

5

(15)

0 0

1 1 1

1

0

1 1

0

0 0

0

0 0

0

0 0

1

0 0

1

1 1

1

1 1

0

1 1

0 0

1

0

1 1

0

Tabla 1: Obtenci´ on de s´ımbolos b´asicos sk = bk bk+1 ⊂ S A para el conjunto B.

b1 b2 b3 .. .

b1 -

b2 -

b3 -

... -

bn -

-

-

bn

Tabla 2: Formato de matriz para la obtenci´on de s´ımbolos compuestos repetidos en S A , tal que bk ∈ S A .

0 1 1 0 0 0 0 1 1 1 0 1 0

0 -

1 1

1 -

1 1 1

1 1 1

1

1

1 1 1 1

1 1

0 1 1 1

0 1 1

0 1

0 -

1

1

1

1

1

1

1

1

1 1 1

1 1

1 -

1

1

1

0 1

1 -

0 -

Tabla 3: Matriz para la obtenci´on de s´ımbolos compuestos de S A .

6

El tiempo de ejecuci´ on de los subpasos anteriormente descritos, es aproximadamente T (n) = n + n2 , tal A que n = kS k. El tiempo para la obtenci´ on del conjunto B de la expresi´on (15) a partir del de la expresi´on (14) es aproximadamente T (m) = m + m lg(m), tal que m = kBk, y kBk = 21 n2 − 52 n + 3; n = kS A k. Luego, T (n) = ( 21 n2 − 52 n + 3) + ( 12 n2 − 52 n + 3) lg( 12 n2 − 52 n + 3). Por lo tanto, el tiempo de ejecuci´ on del paso actual es T (n) = 32 n2 − 23 n + 3 + ( 12 n2 − 52 n + 3) lg( 12 n2 − 5 2 2 n + 3); O(n) = n

2.2.

Alinear localmente conjunto de s´ımbolos con la cadena principal – Paso 2

Se buscar´ a alineaciones locales por cada sk ∈ B sobre la cadena S A utilizando el algoritmo KMP propuesto por Knuth, Morris y Pratt en [7]. Para esto, el algoritmo KMP devolver´a un arreglo que se llamar´ a C y corresponder´ a a un arreglo de ´ındices en S A donde inicie una alineaci´on local de la cadena sk ∈ B con S A . El conjunto de todas las alineaciones locales ser´a llamado L. Cada alineaci´on local de sk se representar´a como (i,j) sk , donde tal alineaci´ on comienza en el s´ımbolo bi de ´ındice i en S A y termina en el s´ımbolo bj con ´ındice (i,j) A j en S , tal que sk ∈ B y sk ∈ L. La forma de buscar alineaciones locales de cada sk ∈ B sobre S A se describe a trav´es del algoritmo 2. La aplicaci´ on del algoritmo 2 sobre la cadena S A se muestra gr´aficamente en la tabla 5, donde cada coincidencia suma una unidad a la celda que la representa. La tabla 6 muestra gr´ aficamente en detalle las alineaciones locales del s´ımbolos s2 = 000 ∈ B sobre la cadena S A a partir del resultado mostrado en la tabla 5. En la tabla 7 se interpretan gr´ aficamente la totalidad de los resultados de la tabla 5, correspondiente al conjunto L. 0 1 1 0 0 0

0 -

1 -

1 -

0 -

0 -

0 -

0 -

1 -

1 -

1 -

0 -

1 -

0 -

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

0 1 1 1 0 1 0

Tabla 4: Representaci´ on gr´ afica de s´ımbolos compuestos mostrados como l´ıneas diagonales descendentes de SA . 7

Algoritmo 2 Algoritmo de b´ usqueda de coincidencias. A Entrada: Cadena binaria S ; conjunto de s´ımbolos B. Salida: ... 1: SB A ←∅ 2: function buscarCoincidencias(S A ,B) 3: para todo s ∈ B hacer 4: C ←KMP(S A ,s) 5: para todo i ← 0 . . . kCk hacer 6: L ← s(Ci ,Ci +ksk−1) 7: fin para 8: fin para 9: fin function

´ Indices → B \S A 00 000 01 10 11 011 110

1 0

2 1

1

1

1

1 1 1

3 1

4 0 1 1

1 1 1 1

1

5 0 2 2

6 0 2 2

7 0 1 1 1

1

8 1

9 1

10 1

1 1 1

1

2 1 1

1 1 1

11 0

12 1

13 0

1 1

1 1

1

1

Tabla 5: Matriz de alineaci´on local de s´ımbolos sk ∈ B a lo largo de S A .

´ Indices → B \S A 000

1 0

2 1

3 1

4 0 1

5 0 1

6 0 1

7 0

1

1

8 1

9 1

10 1

11 0

12 1

13 0

(4,6)

000

s2 1

(5,7) s2

Tabla 6: Alineaciones locales del s´ımbolo s2 ∈ B sobre la cadena S A . En este ejemplo se muestran las (4,6) (5,7) alineaciones locales s2 y s2 , ambas en L.

8

´ Indices → B \S A

1 0

2 1

3 1

00

4 0

5 0

6 0

7 0

1

2

2

1

8 1

9 1

10 1

11 0

12 1

1

1

13 0

1 1 (4,5) s1 1 1 (5,6) s1 1 1 (6,7) s1 000

1 1

01

1

1

2

2

1

1 1 (4,6) s2 1 1 1 (5,7) s2 1

1

1 1 (1,2) s3 1 1 (7,8) s3 1 1 (11,12) s3 10

1

1

1

1

1

1

1 1 (3,4) s4 1 1 (10,11) s4 1 1 (12,13) s4 11

1

1

1

2

1

1 1 (2,3) s5 1 1 (8,9) s5 1 1 (9,10) s5 011

1

1

1

1

1

1

1

1

1

(1,3)

s6

1 110

1

1

1

1

1

1

1 1 (7,9) s6 1

1

1

(2,4)

s7

1

1 1 (9,11) s7

Tabla 7: Matriz interpretada de alineaciones locales de s´ımbolos sk ∈ B a lo largo de S A , correspondiente al conjunto L. 9

De esta forma, de acuerdo al detalle mostrado en la tabla 7, el conjunto L estar´a compuesto de los siguientes elementos: ( ) (4,5) (5,6) (6,7) (4,6) (5,7) (1,2) (7,8) (11,12) (3,4) s1 ; s1 ; s1 ; s2 ; s2 ; s3 ; s3 ; s3 ; s4 ; L= (16) (10,11) (12,13) (2,3) (8,9) (9,10) (1,3) (7,9) (2,4) (9,11) s4 ; s4 ; s5 ; s5 ; s5 ; s6 ; s6 ; s7 ; s7 Suponiendo que el s´ımbolo sa ∈ B m´ as largo es ksa k = (n −
1), el tiempo de ejecuci´on de los pasos 17 2 anteriormente descritos, es aproximadamente T (n) = 12 n2 − 25 n + 3 (n + n − 1) = n3 − 11 2 n + 2 n − 3; n = A 3 kS k, O(n) = n .

2.3.

Limpiar alineaciones de s´ımbolos – Paso 3

Sobre los resultados del conjunto L de la expresi´on (16) se obtendr´a L0 ⊂ L, que contendr´a alineaciones que cumplan con caracter´ısticas descritas en el siguiente procedimiento:

(a,b) sk

(i,j)

1. Limpiar alineaciones de s´ımbolos del conjunto L, recorriendo los s´ımbolos sk desde i = 1 en adelante. Para esto, eliminar aquellas alineaciones de s´ımbolos tal que no coincidan con el inicio de S A y no tengan antecesor. Esta condici´ on se muestra formalmente a trav´es de la siguiente expresi´on: (b,c)

sk

(a,b−1)

, a > 1 ∧ sl

∈ /L

(17) (i,j)

2. Limpiar alineaciones de s´ımbolos del conjunto L, recorriendo los s´ımbolos sk desde j = kS A k hacia atr´ as. Para esto, eliminar aquellas alineaciones de s´ımbolos que no coincidan con el final de S A y que no tengan sucesor. Esta condici´ on se muestra formalmente a trav´es de la siguiente expresi´on: (a,b)

sk

(b+1,c)

, b < kS A k ∧ sl

∈ /L

(18)

Al aplicar los pasos 1 y 2 sobre el conjunto L, se obtienen los siguientes resultados: Del paso 1, se consigue lo siguiente: (2,3)

es eliminada, porque no comienza al inicio de S A y no tiene un antecesores

(2,4)

es eliminada, porque no comienza al inicio de S A y no tiene un antecesores

• La alineaci´ on s5 (a,1) sk .

• La alineaci´ on s7 (a,1) sk .

Del paso 2, se consigue lo siguiente: (11,12)

• La alineaci´ on s3 (13,b) sk .

es eliminada, porque no coincide con el final de S A y no tiene un sucesores

(11,12)

(9,10)

• A s3 le anteceden s5 (11,12) de s3 . (9,10)

• A s5

(7,8)

le antecede s3

, el que tambi´en es eliminado, debido a que no tiene sucesor distinto (9,11)

, el que no es eliminado, debido a que le sucede s7

.

Luego, el resultado se muestra en la tabla 8. De esta forma, de acuerdo a la tabla 8, el conjunto L0 estar´a compuesto de los siguientes elementos: ( ) (4,5) (5,6) (6,7) (4,6) (5,7) (1,2) (7,8) s1 ; s1 ; s1 ; s2 ; s2 ; s3 ; s3 ; 0 L = (19) (3,4) (10,11) (12,13) (8,9) (1,3) (7,9) (9,11) s4 ; s4 ; s4 ; s5 ; s6 ; s6 ; s7 10

´ Indices → A B \S 00

1 0

2 1

3 1

000

01

1 1 1 1 (1,2) s3

4 5 6 7 0 0 0 0 1 2 2 1 1 1 (4,5) s1 1 1 (5,6) s1 1 1 (6,7) s1 1 2 2 1 1 1 1 (4,6) s2 1 1 1 (5,7) s2 1

8 1

9 1

10 1

11 0

12 1

13 0

1

1

1

1

1

1 1 (7,8) s3 10

1 1 1 1 (3,4) s4

1 1 (10,11) s4 1 1 (12,13) s4 11

011

1 1

1 1

1 1

1

1 1 1 1 (8,9) s5 1 1

(1,3)

s6

1 110

1 1 (7,9) s6 1 1

1 1

1 1

(9,11)

s7

(a,b)

Tabla 8: Matriz limpia e interpretada con las alineaciones de s´ımbolos sk

11

∈ L sobre S A .

Suponiendo que 31 de los elementos de B coinciden con el principio de S A y otro 13 coinciden con el final de S A , el de ejecuci´ on de los pasos anteriormente descritos, es aproximadamente T (n) =
tiempo 2 1 2 5 1 2 5 n − n + 3 = n − n + 2; n = kS A k, O(n) = n2 . 3 2 2 3 3

2.4.

Obtener Dependencias – Paso 4

De los resultados del conjunto L0 de la expresi´on (19), se obtiene la siguiente familia de dependencias SB A:   (1,2) (3,4) (5,6) (7,8) (9,11) (12,13)   S = {s ; s ; s ; s ; s ; s }, 1   3 4 1 3 7 4     (1,2) (3,4) (5,6) (7,9) (10,11) (12,13)     S = {s ; s ; s ; s ; s ; s }, 2   3 4 1 6 4 4     (1,2) (3,4) (5,7) (8,9) (10,11) (12,13) S = {s ; s ; s ; s ; s ; s }, 3 A 3 4 2 5 4 4 SB = (20) (4,5) (6,7) (8,9) (10,11) (12,13)  S4 = {s(1,3)  ; s1 ; s1 ; s5 ; s4 ; s4 },   6     (1,3) (4,6) (7,8) (9,11) (12,13)     S5 = {s6 ; s2 ; s3 ; s7 ; s4 },       (1,3) (4,6) (7,9) (10,11) (12,13) S6 = {s6 ; s2 ; s6 ; s4 ; s4 } Se han conseguido seis dependencias, SB A = {S1 , S2 , S3 , S4 , S5 , S6 }, donde cada una de ellas constituyen las cadenas que se alinean con S A compuestas por s´ımbolos sk ∈ B. Suponiendo que los s´ımbolos sk de B tienen un tama˜ no m´ınimo, i.e. 2, y que se distribuyen equiA tativamente a lo largo de S , el tiempo de ejecuci´ o n de este u ´ltimo paso es aproximadamente T (n) = s n n 5n n2
n )−( )+3 ( ( ) 2 2 n2 = n + n6 − 5 2 ; n = kS A k, O(n) = n 2 .

3.

Conclusiones

El algoritmo propuesto en la secci´ on 2, describe una soluci´on para encontrar el conjunto de dependencias SB . Este algoritmo, a diferencia del de fuerza bruta de la expresi´on (9), permite reducir los caminos de A b´ usqueda de dependencias; la soluci´ on del algoritmo 1 de fuerza bruta inicia una exploraci´on independiente por cada s´ımbolo sk del conjunto B, no descartando ninguno. Por el contrario, el algoritmo propuesto descarta parte de las combinaciones de s´ımbolos que no aseguran reconstruir a S A , reduciendo el n´ umero de exploraciones. Esto u ´ltimo se propicia debido al paso 3 del algoritmo propuesto, donde se descartan los s´ımbolos que no contribuyen a combinaciones que reconstruyan a S A . Lo anterior, se evidencia al contrastar la complejidad temporal de ambos algoritmos: Por una parte, el algoritmo propuesto, y de acuerdo a las complejidades temporales de cada uno de sus pasos, tiene una cota n superior aproximada de O(n 2 + n3 ) ; por on 1.3 √ otra parte, el algoritmo 1 de fuerza bruta descrito en la secci´ n posee una cota superior de O(n c ); c ≈ 6 n. En ambos casos, n = kS A k. Comparando ambas as´ıntotas en la figura 1 el algoritmos propuesto (A) resulta tener un crecimiento asint´otico m´as lento que el otro de fuerza bruta (B).

12

Figura 1: Comparaci´ on de las as´ıntotas de complejidad temporal de los algoritmos propuesto (A) y de fuerza bruta (B).

Referencias [1] Robert C Edgar. Muscle: multiple sequence alignment with high accuracy and high throughput. Nucleic acids research, 32(5):1792–1797, 2004. [2] Osamu Gotoh. An improved algorithm for matching biological sequences. Journal of molecular biology, 162(3):705–708, 1982. [3] Desmond G Higgins, Alan J Bleasby, and Rainer Fuchs. Clustal v: improved software for multiple sequence alignment. Computer applications in the biosciences: CABIOS, 8(2):189–191, 1992. [4] Desmond G Higgins and Paul M Sharp. Clustal: a package for performing multiple sequence alignment on a microcomputer. Gene, 73(1):237–244, 1988. [5] David A Huffman et al. A method for the construction of minimum redundancy codes. proc. IRE, 40(9):1098–1101, 1952. [6] Kazutaka Katoh, Kazuharu Misawa, Kei-ichi Kuma, and Takashi Miyata. Mafft: a novel method for rapid multiple sequence alignment based on fast fourier transform. Nucleic acids research, 30(14):3059–3066, 2002. 13

[7] Donald E Knuth, James H Morris, Jr, and Vaughan R Pratt. Fast pattern matching in strings. SIAM journal on computing, 6(2):323–350, 1977. [8] Saul B Needleman and Christian D Wunsch. A general method applicable to the search for similarities in the amino acid sequence of two proteins. Journal of molecular biology, 48(3):443–453, 1970. [9] C´edric Notredame, Desmond G Higgins, and Jaap Heringa. T-coffee: A novel method for fast and accurate multiple sequence alignment. Journal of molecular biology, 302(1):205–217, 2000. [10] David Salomon. Data compression: the complete reference. Springer, 2004. [11] David Salomon. A Concise Introduction to Data Compression. Undergraduate Topics in Computer Science. Springer, London, 2008. [12] T.F. Smith and M.S. Waterman. Identification of common molecular subsequences. Journal of Molecular Biology, 147(1):195 – 197, 1981. [13] Julie D Thompson, Toby J Gibson, Fr´ed´eric Plewniak, Fran¸cois Jeanmougin, and Desmond G Higgins. The clustal x windows interface: flexible strategies for multiple sequence alignment aided by quality analysis tools. Nucleic acids research, 25(24):4876–4882, 1997. [14] Julie D Thompson, Desmond G Higgins, and Toby J Gibson. Clustal w: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice. Nucleic acids research, 22(22):4673–4680, 1994. [15] W John Wilbur and David J Lipman. The context dependent comparison of biological sequences. SIAM Journal on Applied Mathematics, 44(3):557–567, 1984.

14