Sherlock Holmes y el misterio del origen de replicación
Buscando códigos secretos en el ADN:
el algoritmo de Knuth-Morris-Pratt
El descifrado de códigos secretos ha sido un tema recurrente en la literatura. Un ejemplo clásico es el enigma que aparece en El escarabajo de oro, de Edgar Allan Poe, aunque mi preferido es el de la novela Los bailarines de Arthur Conan-Doyle. En este relato, Sherlock Holmes se enfrenta al misterio de unos mensajes secretos enviados por un criminal a una mujer casada que conoce el código para descifrarlos. El marido de ésta contrata a Holmes para conocer su contenido ya que sospecha que puedan resultar amenazadores. A continuación se muestra los mensajes del criminal y una respuesta de la esposa. Puedes observar que el cifrado se ha realizado con siluetas que representan movimientos humanos (de ahí el nombre del relato).
Descifrar este mensaje no resulta demasiado complejo. Un opción es comprobar qué caracteres son los más usados y compararlos con las letras más habituales del idioma inglés (esta es la estrategia utilizada por Holmes). También se pueden buscar grupos de caracteres y tratar de relacionarlos con palabras muy usadas. Por ejemplo, en el figura anterior se han resaltado dos grupos de cinco caracteres repetidos.
Esta búsqueda de grupos de caracteres sirve para algo más que descifrar mensajes secretos del enemigo. Tiene una aplicación importante en ciencia, por ejemplo para la búsqueda del origen de replicación en bacterias. A continuación voy a describir este problema, para después preguntarme cómo lo hubiera resuelto el doctor Watson o la mente más preclara de Sherlock Holmes.
Origen de replicación en bacterias
Muchas bacterias suelen contar con un solo cromosoma circular e inician su duplicado previo a la división celular en un único punto denominado origen de replicación o oriC. Conocer este punto de inicio de duplicación del genoma es importante en ingeniería genética, donde algunos cromosomas bacterianos se utilizan como vectores en los que se añaden genes de interés para que se fabrique una proteína concreta en el interior de la célula huésped. Si en el proceso de inserción del nuevo gen se destruyera o dividiera la zona del origen de replicación, este vector perdería la capacidad de duplicarse en la célula huésped.
Existen varios indicios que permiten localizar in silico (sin experimentos de laboratorio, utilizando métodos computacionales) oriC en bacterias. Uno de ellos es la diferente proporción de aminoácidos guanina y citosina antes y después de oriC (debido a que la enzima ADN-polimerasa solamente copia el cromosoma en una de las dos direcciones posibles). Otro sería la presencia en las cercanías de oriC del gen DnaA, que codifica una proteína importante para el inicio de la replicación. Pero lo que realmente caracteriza el origen de replicación es la presencia de fragmentos de 9 nucleótidos que se repiten con mucha frecuencia en esta zona, denominados secuencias DnaA (DnaA boxes). Por ejemplo, en la bacteria Escherichia coli esta secuencia es TTATCACACA. En otras bacterias las secuencias DnaA pueden ser ligeramente distintas a esta (en las clamidias es TTTTCCACA) o con más diferencias (en las Bradyrhizobiaceae es TGTTTCACG).
Para encontrar oriC en el genoma de una bacteria bastaría entonces con localizar una zona en la que alguna de estas secuencias se encontrara con una mayor frecuencia. Sí, sí, muy fácil, pero ¿cómo lo hacemos de forma rápida y eficiente si un genoma bacteriano tiene varios millones de nucleótidos?
Algoritmo de fuerza bruta
Para entender cómo buscar un patrón en un texto vamos a simplificar el problema. Supongamos que tenemos que buscar el patrón TATACGTAT en el texto TATATACATATACGTATCG. Ambas secuencias se muestran a continuación, y cada una de las secuencias se acompaña por un contador que indica la posición en la secuencia, i para el patrón y k para el texto (sí, los informáticos empezamos a contar desde cero, somos así de raros).
¿Cómo harías esta búsqueda? No me vale la respuesta de “así a ojo, mirando a ver”. Piensa que acabaremos buscando en cadenas de millones de caracteres, por lo que es mejor idear un sistema que evite equivocaciones y nos permita después implementarlo en un programa. Supongo que una cosa que se nos ocurriría a todos (también al Dr. Watson) sería la siguiente: empezamos alineando verticalmente las posiciones iniciales del patrón y el texto, y recorremos simultáneamente cada par de caracteres en vertical mientras que no encontremos dos diferentes. Es más fácil de dibujar que de explicar:
En el ejemplo hay una discrepancia en la posición 4, así que muevo el patrón una posición a la derecha y repito el proceso.
En este caso la primera posición ya es distinta, así que vuelvo a desplazar el patrón de nuevo.
Esta vez ha estado más cerca, las cinco primeras posiciones eran correctas. Este procedimiento seguiría hasta encontrar el patrón en el texto (como se muestra en la siguiente figura), en cuyo caso me anotaría la posición del texto en la que lo he encontrado (8).
Bueno, como estrategia no parece nada mal. Pero piensa una cosa: en el caso de genomas bacterianos estamos hablando de comprobar varios millones de posiciones. Y si te fijas bien, verás que estamos desaprovechando información. Si miras de nuevo la figura en la que se busca el patrón en la posición 2 del texto (dos figuras atrás) verás que recorremos éste hasta la posición 7, en la que paramos porque encontramos una discrepancia. Ahora desplazamos el patrón y volvemos a mirar las posiciones de la 3 a la 7. ¿Hay alguna forma de no volver atrás y aprovechar que ya hemos visto esas posiciones? ¿Crees que a Holmes se le ocurriría una solución mejor que la de Watson?
Algoritmo de Knuth-Morris-Pratt
Supongamos que tenemos la tabla mágica que se muestra a continuación, también conocida como función de fallos. Dejaré para el final la explicación de cómo se construye esta tabla (por eso es, por ahora, mágica).
¿Qué significa el valor del desplazamiento que aparece en la tabla asociado a cada carácter del patrón? Para responder a esta pregunta voy a repetir el proceso de búsqueda del patrón anterior. Empecemos.
El principio es el mismo. Alineamos las posiciones iniciales de patrón y texto, comparamos los pares de letras hasta que llegamos a una discrepancia, en este caso en la posición 4 del patrón, el carácter C. Pero ahora vamos a hacer algo distinto. En la función de fallos a la letra C de la posición 4 le corresponde el número 2, así que vamos a continuar comparando el texto desde la posición 4 con la posición 2 del patrón.
Fíjate en el trabajo que nos hemos ahorrado:
- No hemos retrocedido en la posición del texto. Encontramos una discrepancia en la posición 4 y seguimos en la misma posición.
- No hemos revisado si había una coincidencia alineando el patrón con la posición 1 del texto, aunque es obvio que no la hay.
- Estamos revisando la alineación del patrón con la posición 2 del texto, pero no hemos hecho las dos primeras comprobaciones.
Sigamos. La nueva discrepancia aparece en la posición 7 del texto (A) y la 5 del patrón (G). Por lo tanto alineamos la posición 7 del texto con el inicio del patrón (valor 0 en la posición 5 de la tabla). Si te fijas, verás que hemos desplazado el patrón en… ¡5 posiciones!
Ahora encontramos una discrepancia en la posición 0 del patrón, y en la tabla se nos indica que hay que alinear el texto en la posición 7 del texto con la posición -1 del patrón. Esto equivale simplemente a desplazar el patrón una posición a la izquierda. De esta forma ya encontramos el patrón en el texto.
En resumen, con esta estrategia conseguimos que la posición k del texto nunca retroceda, y se producen saltos en la comparación del patrón con el texto que disminuyen considerablemente el número de comparaciones.
Como puedes imaginar, este algoritmo no fue desarrollado por Sherlock Holmes. De hecho fue ideado unos 120 años después de su nacimiento por Donald Knuth y Vaughan Pratt y de modo independiente por James H. Morris, aunque lo publicaron conjuntamente en 1977.
Bien, pero ¿cómo se calcula la tabla?
Ahora es el momento de explicar cómo se construye la tabla mágica. La parte fácil es que en la posición 0 siempre hay un -1 y en la posición 1 hay siempre un 0.
La parte complicada es que, en el resto de posiciones, se indica la longitud del prefijo de mayor tamaño que coincide con el sufijo del mismo tamaño en la subcadena que llega hasta la posición anterior.
Vale, vale… vamos a contarlo con ejemplos. Empezaré por calcular el valor de la tabla en las posición 3. Esto significa que he de considerar la cadena que termina en 2, es decir, TAT. Hay una coincidencia de un carácter (T) en el principio de la cadena y el final, por lo que la tabla toma el valor 1 en la posición 3.
En la posición 4 de la tabla la secuencia a considerar es TATA, por lo que hay una secuencia de tamaño 2 que coincide al principio y al final.
Como último ejemplo, al calcular la posición 5 la cadena es TATAC, por lo que no hay ninguna coincidencia entre principio y final, y el valor en la tabla es 0. El resto de valores de la tabla pueden calcularse de manera similar.
Para terminar
El algoritmo de Knuth-Morris-Pratt no es ni el único ni el más eficiente para buscar patrones en un texto. Si te interesa aprender otras estrategias para el mismo fin, te aconsejo que estudies los algoritmos de Boyer-Moore y Rabin-Karp.
Cuando se estudia un nuevo genoma bacteriano se desconoce a priori la secuencia DnaA. En esos caso se suele buscar la secuencia de la Escherichia Coli, pero admitiendo la variación en alguno de los nueve caracteres. En ese caso los algoritmos mencionados no son válidos.
Por último, si quieres saber cómo se resuelve el enigma de Los bailarines te aconsejo que leas el relato original (que puedes descargar gratuitamente aquí) o el análisis del mismo que se hace aquí. Y si te gusta Sherlock Holmes no puedo dejar de aconsejar que vuelvas a leer la obra de Conan-Doyle, así como el reciente relato La aventura del abrigo amarillo de Daurmith.
Esta entrada participa en la Edición 5.7: Alan Turing del Carnaval de Matemáticas, cuyo anfitrión es el blog El zombi de Schrödinger.
Si te apetece escribir algún comentario, puedes hacerlo buscando los signos ‘+’ que se encuentran a la derecha de cada párrafo. Y si te ha gustado, puedes recomendar este artículo haciendo clic en el botón al final del texto.
