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.