3.4: Coincidencia exacta de cadenas en tiempo lineal

Si bien hemos analizado diversas formas de alineación y algoritmos utilizados para encontrar tales alineaciones, estos algoritmos no son lo suficientemente rápidos para algunos fines. Por ejemplo, podemos tener una secuencia de 100 nucleótidos que queremos buscar en todo el genoma, que puede tener más de mil millones de nucleótidos de largo. En este caso, queremos un algoritmo con un tiempo de ejecución que dependa de la longitud de la secuencia de consulta, posiblemente con algún preprocesamiento en la base de datos, ya que procesar todo el genoma para cada consulta sería extremadamente lento. Para tales problemas, entramos en el ámbito de los algoritmos aleatorios donde en lugar de preocuparnos por el peor desempeño, estamos más interesados en asegurarnos de que el algoritmo sea lineal en el caso esperado. Al buscar coincidencias exactas (consecutivas) de una secuencia, el algoritmo de Karp-Rabin interpreta dicha coincidencia numéricamente. Hay muchas otras soluciones a este problema y algunas de ellas que pueden asegurar que el problema sea lineal en el peor de los casos como: el algoritmo Z, el algoritmo Boyer-Moore y Knuth-Morris-Pratt, algoritmos basados en árboles de sufijos, matrices de sufijos, etc. (discutido en las diapositivas de “Adición de la conferencia 3”)

Algoritmo Karp-Rabin

Este algoritmo intenta hacer coincidir un patrón particular con una cadena, que es el principio básico de la búsqueda en la base de datos. El problema es el siguiente: en texto T de longitud n estamos buscando patrón P de longitud m. Las cadenas se mapean a números para permitir una comparación rápida. Una versión ingenua del algoritmo implica mapear las subcadenas P y m -length de T números sinto x e y, respectivamente, deslizando x a lo largo de T en cada desplazamiento hasta que haya una coincidencia de los números.

Figura 3.10: Algoritmo de Karp-Rabin ingenuo

Sin embargo, se puede ver que el algoritmo, como se ha dicho, es de hecho no lineal por dos razones:

1. Calcular cada yi toma más que un tiempo constante (de hecho es lineal si calculamos ingenuamente cada número desde cero para cada subsecuencia)
2. Comparar x e yi puede ser costoso si los números son muy grandes, lo que podría suceder si el patrón a emparejar es muy largo

Para que el algoritmo sea más rápido, primero modificamos el procedimiento para calcular yi en tiempo constante utilizando el número previamente calculado,\( y_i − 1 \). Podemos hacer esto usando algunas operaciones de bit: una resta para eliminar el bit de orden superior, una multiplicación para desplazar los caracteres a la izquierda, y una suma para agregar el dígito de orden bajo. Por ejemplo, en la Figura 10, podemos calcular\( y_2 \) desde\( y_1 \) por

• eliminando el bit de orden más alto: 23590 mod 10000 = 3590

• desplazamiento a la izquierda: 3590 ∗ 10 = 35900
• sumando el nuevo dígito de orden bajo: 35900 + 2 = 35902

Nuestro siguiente problema surge cuando tenemos secuencias muy largas para comparar. Esto hace que nuestros cálculos sean con números muy grandes, lo que ya no se convierte en tiempo lineal. Para mantener los números pequeños para asegurar una comparación eficiente, hacemos todos nuestros cálculos módulo p (una forma de hash), donde p refleja la longitud de palabra disponible para nosotros para almacenar números, pero es lo suficientemente pequeña como para que la comparación entre x y\( y_i \) sea realizable en tiempo constante.

: Usar una función para mapear valores de datos a un conjunto de datos de tamaño fijo.
Debido a que estamos usando hash, mapear al espacio de números módulo p puede resultar en golpes espurios debido a colisiones hash, y así modificamos el algoritmo para tratar tales golpes espurios verificando explícitamente los hits reportados de los valores hash. De ahí que la versión final del algoritmo Karp-Rabin sea:

Para calcular el tiempo de ejecución esperado de Karp-Rabin, debemos tener en cuenta el costo esperado de verificación. Si podemos mostrar que la probabilidad de golpes espurios es pequeña, el tiempo de ejecución esperado es lineal.

Preguntas:

P: ¿Y si hay más de 10 caracteres en el alfabeto?

R: En tal caso, podemos simplemente modificar el algoritmo anterior incluyendo más dígitos, es decir, trabajando en una base que no sea 10, por ejemplo, digamos base 256. Pero en general, cuando se usa hash, las cadenas se mapean en un espacio de números y de ahí las cadenas se interpretan numéricamente.

P: ¿Cómo aplicamos esto al texto?

Figura 3.11: Algoritmo final de Karp-Rabin

R: Se utiliza una función hash que cambia el texto en números que son más fáciles de comparar. Por ejemplo, si se usa todo el alfabeto, a las letras se les puede asignar un valor entre 0 y 25, y luego usarse de manera similar a una cadena de números.

P: ¿Por qué el uso del módulo disminuye el tiempo de cálculo?

R: El módulo se puede aplicar a cada parte individual en el cálculo conservando la respuesta. Por ejemplo: imagina que nuestro texto actual es” 314152” y la longitud de la palabra es 5. Después de hacer nuestro primer cálculo en” 31415”, movemos nuestro marco para hacer nuestro segundo cálculo, que es:
\[ 14152 = (31415 − 3 ∗ 10000) ∗ 10 + 2(mod13) \nonumber \]

\[ = (7−3∗3)∗10+2(mod13) \nonumber \]
\[ = 8(mod13) \nonumber \]
Este cálculo se puede hacer ahora en tiempo lineal.

P: ¿Hay disposiciones en el algoritmo para coincidencias inexactas?

R: El algoritmo anterior solo funciona cuando hay regiones de similitud exacta entre la secuencia de consulta y la base de datos. Sin embargo, el algoritmo BLAST, que veremos más adelante, extiende las ideas anteriores para incluir la noción de buscar en un vecindario biológicamente significativo de la secuencia de consultas para dar cuenta de algunas coincidencias inexactas. Esto se hace buscando en la base de datos no solo la secuencia de consultas, sino también algunas variantes de la secuencia hasta algún número fijo de cambios.

En general, para reducir el tiempo de operaciones sobre argumentos como números o cadenas que son realmente largos, es necesario reducir el rango de números a algo más manejable. El hash es una solución general a esto e implica mapear claves k de un gran universo\( U \) de cadenas o números en un hash de la clave\( h(k) \) que se encuentra en un rango menor, digamos\( [1...m] \). Hay muchas funciones hash que se pueden utilizar, todas con diferentes propiedades teóricas y prácticas. Las dos propiedades clave que necesitamos para el hash son:

1. Reproducibilidad si\( x = y \), entonces\( h(x) = h(y) \). Esto es esencial para que nuestro mapeo tenga sentido.

2. Distribución uniforme de salida Esto implica que independientemente de la distribución de entrada, la distribución de salida es uniforme. es decir\( x! = y \), si, entonces\( P(h(x) = h(y)) = 1/m \), independientemente de la distribución de entrada. Esta es una propiedad deseable para reducir la posibilidad de golpes espurios.

Una idea interesante que se planteó fue que podría ser útil tener funciones hash sensibles a la localidad desde el punto de vista de uso en búsquedas vecinales, de tal manera que los puntos en U que están cerca entre sí son mapeados a puntos cercanos por la función hash. La noción de proyecciones aleatorias, como extensión del algoritmo BLAST, se basa en esta idea. Además, hay que señalar que el módulo no satisface la propiedad 2 anterior porque es posible tener distribuciones de entrada (por ejemplo, todos los múltiplos del número vis—vis que se toma el módulo) que resultan en muchas colisiones. Sin embargo, elegir un número aleatorio como divisor del módulo puede evitar muchas colisiones.

Trabajar con hash aumenta la complejidad de analizar el algoritmo ya que ahora necesitamos calcular el tiempo de ejecución esperado al incluir el costo de verificación. Para demostrar que el tiempo de ejecución esperado es lineal, necesitamos demostrar que la probabilidad de golpes espurios es pequeña.