| Introducción | Objetivos | Metodología | Programas | Resultados | Conclusiones | Referencias | Autoras | Agradecimientos |
CONCLUSIONES
Los resultados del análisis exhaustivo que aquí se detalla se encuentran en el apartado de Resultados. |
||
Análisi de la complejidad algorítmica y del coste computacional del algoritmo simple de correspondencia exacta versus el algoritmo de Knuth-Morris-Pratt El algoritmo simple de correspondencia exacta presenta una complejidad algorítmica de orden cuadrático: O(nm). Es un tipo de algoritmo que no requiere un pre-procesamiento del patrón. Tal como hemos visto tanto en el apartado de Metodología com de Programas, la idea es simple: el patrón y la secuencia son comparadas nucleótido por nucleótido, y en el caso de una mismatch, el patrón se desplaza una posición a la derecha, y la comparación se repite, y así hasta que se encuentra una correspondencia exacta o la secuencia ha finalizado.
Así pues, el coste computacional en el peor de los casos es O(nm). Éste tendría lugar para una secuencia de n A's seguidas por una C buscando un patrón de m A's y una C (asumiendo que m < n):
|
||
|
En este caso, hasta m nucleótidos se tendrían que comparar para todos los n - m + 1 desplazamientos dados. Ésto resume la mencionada complejidad computacional de aproximadamente O(nm).
En nuestros resultados, por ejemplo para el mRNA del gen de la EPO, la longitud de la secuencia (m) es de 579 nucleótidos. Nuestro programa genera unos 566 patrones de este mRNA de una logitud de 14 nucléotidos n. Por tanto, el número de operaciones esperado en el peor de los casos es 579*14*566 = 4.587.996. Pero implementando nuestro programa, el número de operaciones que realiza es de 439.250. Esta diferencia es causada porque no nos encontramos en el peor de los casos. Si dividimos el número total de operaciones realizadas per el número total de patrones generados a partir del mRNA (439.250/566), obtenemos un total de 776 operaciones por cada patrón, aproximadamente. Si el mRNA de la EPO de ratón tiene 579 nucleótidos, ésto significa que para cada patrón compara 1,35 nucleótidos. Ésto es: no compara cada vez todos los nucleótidos del patrón, sino que se desplaza a otra comparación después de encontrar un mismatch, al cabo de 1 - 2 nucleótidos, como media, de haber iniciado el patrón.
Aunque este algorismo simple aún es utilizado en diversas aplicaciones como la investigación en biología, presenta claros inconvenientes: es más bien un método ineficiente para subsecuencias de alfabetos pequeños, ya que los desplazamientos que realiza son muy pequeños (casi inapreciables) y la variable de la posición ha de hacer marcha atrás cada vez que se da un mismatch, lo que se traduce en que la secuencia ha de ser memorizada.
En cambio, el algorismo de Knuth-Morris-Pratt presenta una complejidad algorítmica de orden lineal O(n+m). Cuando hemos analizado el algoritmo simple de correspondencia exacta, hemos mencionado que era ineficiente, ya que retrocede la posición de la secuencia cada vez que hay un mismatch, y algunos nucleótidos son comparados dos o más veces, aunque por la información del patrón que disponemos, sabemos que se podría haber saltado algunas posiciones. El algoritmo de Knuth-Morris-Pratt trabaja más eficientemente: los nucleótidos del patrón y de la secuencia son comparados de izquierda a derecha. Si se produce un mismatch, el algorismo busca el prefijo del patrón que determina el desplazamiento del patrón sin saltarse ninguna posible correspondencia. Tal y como hemos explicado en el apartado de Metodología, la información que necesitamos para encontrar el desplazamiento de la posición es almacenada en una tabla adicional, la next table, que es construida comparando el patrón con él mismo.
Acabamos de comentar en líneas anteriores que el algoritmo de Knuth-Morris-Pratt tiene una complejidad lineal en el peor de los casos. Si analizamos el algoritmo en el apartado de Programas, parece que se ejecutaría hasta n y m veces, con una complejidad de O(nm). Pero no es así. Si recordamos nuestro algoritmo, siempre que los nucleótidos del patrón y de la secuencia coinciden, la posición se incrementa. Cuando se produce un mismatch, la posición sólo retrocede sgegún la next table, tantas veces como se había incrementado anteriormente, con un límite de 2n veces. Ésto significa que tiene una complejidad de O(2n) en el peor de los casos, sin considerar la construcción de la nexta table, que también presenta una complejidad similar. Por tanto, tendríamos que tener una complejidad global de O(2n) + O(2m) equivalente a O(n+m).
Éste es una de las principales ventajas del algoritmo KMP; otra buena razón para utilizarlo es que no necesita memorizar la secuencia a comparar.
Como inconvenientes de este algoritmo, que necesita pre-procesar cada patrón, y ésta no es la solución más eficiente para alfabetos más bien largos. Pero para nuesto problema, con el alfabeto biológico L = {A,C, G, T}, es útil.
Continuando con el ejemplo anterior de nuestros resultados de la EPO, pero ahora para el algoritmo de Knuth-Morris-Pratt, se realizan aproximadamente unas 399.104 operaciones, en lugar de las 439.250. Así pues, podemos concluir que el algoritmo de Knuth-Morris-Pratt obtiene una ganancia computacional del 9,14%. Y lo mismo sucede con el resto de mRNAs comprobados, que se puede observar en el apartado de Resultados. La ganacia computacional mediante el algoritmo de Knuth-Morris-Pratt versus el algoritmo simple de correspondencia exacta es del 8,695%.
|
|
|
|
||
Reproducción de los resultados del mRNA de ratón a partir del algoritmo de Knuth-Morris-Pratt
Podemos concluir que efectivamente nuestro programa funciona correctamente y puede corroborar los resultados obtenidos por el Dr. Robert Castelo para el gen de la EPO de Mus musculus, tal y como se ha demostrado en el apartado de Resultados. También informa del desplazamiento de los patrones encontrados, un factor muy importante para aquellos patrones que localizados entre dos exones separados por algún intrón. Además, hemos podido comprobar que la estrategia automática de mover la longitud también funciona eficientemente, ya que al reproducir las tres subsecuencias obtenemos otras más cortas y únicas en el cromosoma 5. Si esta misma búsqueda se lleva a cabo en todo el genoma, estas subsecuencias más cortas no se hubieran encotrado como únicas.
|
||
|
|
||
Predicción de la estructura secundaria del mRNA de la EPO
Como se puede observar en las imágenes del apartado de Resultados, obtenidas por medio del mFOLD, las subsecuencias únicas encontradaas para el mRNA de la EPO están localizadas en regiones suficientemente expuestas en la predicción de la estructura secundaria de este gen.
|
||
|
|
