Introducción

Esta aplicación presupone que el usuario ya dispone de unos ciertos conocimientos básicos sobre el ADN y su comportamiento, una vez cumplido este requisito podemos pasar a explicar en qué consiste esta aplicación.

El método de secuenciación por Shotgun es bastante conocido en la actualidad, el proceso en términos generales consiste en primero replicar la secuencia de ADN a secuenciar, fragmentar de forma aleatoria las secuencias replicadas (método Shotgun) y una vez hecho esto intentar recomponer la secuencia a partir de los fragmentos solapados. Esta última etapa es con mucho la más complicada de las tres, si bien los errores que se puedan producir en las otras dos etapas previas son una complicación añadida.

Bien, el problema que nos atañe es el siguiente: cuando queremos recomponer la secuencia original a partir de los fragmentos, debemos comparar cada par de segmentos para conocer la mejor superposición posible entre ambos, o si incluso no solapan en absoluto. Si has de comparar cada par de segmentos el número de comparaciones tiene una cota máxima de O(n^2) (donde n es el número de segmentos), esto ha de multiplicarse por el coste de cada comparación. El algoritmo que devuelve el solapamiento óptimo tiene un coste aproximado de O(m^2) (donde m es el número de bases del fragmento), así obtenemos que el coste sólo del proceso de comparación de segmentos tiene un coste de O(n^2) * O(m^2), si consideramos que el número de bases de los fragmentos es parecido al de segmentos obtendremos un coste aproximado de O(n^4), este coste no es aceptable computacionalmente si tratamos con n de magnitud superior al millar.

Como se ha visto el coste computacional de este proceso es inadmisible, por ello se intenta abordar el problema de otra manera: en vez de aplicar el algoritmo cuadrático a fuerza bruta, primero aplicamos un algoritmo de criba a cada par, así nos quedaremos sólo con los pares de bases candidatos, aquellos en los que sea posible encontrar una superposición; así el conjunto inicial de comparaciones se verá reducido en un orden de magnitud. El coste de este proceso será de O(n^2) * O(m) = O(n^3) (suponiendo m y n de magnitud similar), que es a diferencia del coste del algoritmo anterior, computable.

Este programa didáctico intentará explicar el funcionamiento del algoritmo de criba, dicho algoritmo se basa en la búsqueda de grupos de bases coincidentes, la longitud mínima de estos grupos viene indicada por el usuario. Así las entradas del algoritmo serán los dos segmentos de ADN y un parámetro numérico que indicará la sensibilidad del proceso.