• Daniel Díaz Molina B22245
• Luis Fernando Mora B24449
• Emanuel Fernandez Villalobos B52714

El presente proyecto tiene el objetivo de crear un segundo acercamiento a la programación en Python, orientado a resolver un problema científico en el campo de la bioinformática, específicamente en el alineamiento de secuencias de ADN. Se implementará un programa que compare dos secuencias de ADN, las alinee de forma global según el algoritmo Needleman-Wunsch, y presente como resultado el alineamiento óptimo entre las dos secuencias. Como base teórica para el desarrollo de este programa se hará una investigación bibliográfica sobre la estructura del ADN, los elementos que lo conforman y el proceso de secuenciación que se lleva a cabo para determinar el orden de los nucleótidos en una secuencia específica. Se investigará sobre el algoritmo de alineamiento de secuencias desarrollado por los científicos Saul Needleman y Christian Wunsch en la década de los 70.

El estudio moderno de la genética se centra en la síntesis del proteínas, el estudio de secuencias de ADN y ARN. La proteínas son grandes macromoléculas que cumplen cualquier cantidad de funciones, se podría decir que enteder las proteinas es enteder el funcionamiento microscópico de la vida. Las proteinas son sintetizadas a partir del ADN y ARN. Los genes son en realidad cadenas de bases de ADN, que sintetizan una o más proteínas espećificas. El ADN está formado por una combinación de 4 bases nitrogenadas: Adenina, Guanina, Citosina y Tiamina. A un grupo de 3 estas bases se le llama codón, y cada uno se traduce directamente en un aminoácido, que son los bloques unitarios que componen las proteínas (Orengo, Jones, y Thornton, 2003). Así, se puede entender que el ADN es una receta o macro de las estructuras más complejas de la vida, verdaderamente un código genético con (casi) toda la información de un organismo. Es por esta razón que los científicos han dedicado un gran esfuerzo al estudio de secuencias genéticas, se ha invertido mucho dinero en financiar la bio-informática y a la búsqueda de patrones y diferencias de estas secuencias entre diferentes organismos. Sobre este marco de estudio genético surge la necesidad de encontrar patrones en grandes cantidades de datos genéticos. El estudio de la genética se combina con la computación y la informática, y surgen varios algoritmos para ordenar y alinear secuencias de ADN, ARN y proteínas. El descubrimiento de patrones comunes sugiere ancestros comunes entre especies, y las diferencias sugieren las mutaciones que han surgido con la evolución. La escala del problema es sumamente grande, y sin algoritmos secuenciadores que sean ejecutables por implementados por computadoras no sería posible terminar la tarea de comparar las enormes filas de caracteres

El ADN (ácido desoxirribonucléico) es una molécula formada por ácido fosfórico, desoxirribosa y bases nitrógenadas. La misma porta toda la información necesaria para el desarrollo y correcto funcionamiento del ser vivo al que pertenece, y a su vez es muy compleja. Por otro lado, las cuatro bases nitrógenadas que ya se mencionaron se encargan de dar estructura y de unir la doble hélice que conforma la molécula entera. Una imagen de una molécula de ADN se aprecia a continuación.

Estas cuatro bases son de principal interés para la ciencia de la bio-informática, la cual analiza y compara las similitudes entre diferentes cadenas de ADN entre especies, con el objetivo de encontrar similitudes funcionales o evolutivas. Para lograrlo, utilizan como materia prima la información que proporciona la secuenciación de ADN, la cual utiliza un conjunto de técnicas bioquímicas para determinar el orden de las bases nitrogenadas en una porción grande de ADN. La secuenciación de ADN tiene sus orígenes en los 1930's, y ha avanzado hasta novedosas técnicas automatizadas (Ansorge, W.J, 2009), las cuales permiten generar archivos de texto con las bases nitrogenadas en el orden en que fueron encontradas. Dichos archivos generalmente son guardados con extensión “.fasta” (que dicha extensión tiene su origen en los primeros paquetes de software capaces de analizar secuencias de ADN, pero luego que quedó por moda) y contienen grandes hileras de caracteres que pueden ser leídas con cierto formato. Un ejemplo se muestra a continuación.

Para analizar similitudes entre diferentes secuencias, se han desarrollado diferentes algoritmos de alineamiento a lo largo de los últimos dos siglos. Uno de ellos es el algoritmo Needleman-Wunsch, el cual fue desarrollado en 1970 por Saul B. Needleman y Christian D. Wunsch (Needleman,S. B. & Wunsch, C.D., 1970). El mismo es un ejemplo de programación dinámica, una rama de la programación que toma un problema muy complejo y lo subdivide en problemas manejables, que se solucionan y dicha solución se almacena para luego ser buscada si se requiriera. En este caso, lo que se almacena es un “camaster/mino de mejor puntaje”. Para generar las comparaciones, se genera una matriz con ambas secuencias como se muestra en la siguiente figura:

Dicha matriz se comienza a recorrer desde una fila y columna, asignando un puntaje de “+1” cuando las secuencias coinciden, y “-1” si no coinciden o si debe abrir un espacio-llamado “gap”- para que las próximas secuencias coincidan. El camino de mejor puntaje se almacena y se actualiza hasta que todas las combinaciones de fila-columna han sido exploradas y se determina que el alineamiento óptimo es aquel con mayor puntaje.

Para el presente proyecto, se implementó una librería disponible en Github, para Python, que implementa el algoritmo needleman-wunsch. El mismo recibe dos secuencias de bases nitrogenadas y las alinea según el mejor puntaje que se obtenga. Para visualizar el proceso de alineamiento, se desarrolló una interfaz gráfica por medio de PyGTK, que es un toolkit para crear interfaces gráficas tanto en plataformas GNU-Linux como Windows. Dicha interfaz gráfica se muestra a continuación:

Permite seleccionar las secuencias de ADN a analizar de archivos de texto, escoger el algoritmo de alineamiento de una lista de algoritmos disponibles y además tiene espacios para visualizar las secuencias.

A continuación se muestran los resultados de las velocidades tardadas por el algoritmo implementado en Python, dicho programa lo que hace es leer las cadenas de un archivo fuente, iniciar el conteo del tiempo antes de llamar a la funciona que las alinea, y cuenta el tiempo nuevamente después de que el algoritmo da el resultado, se saca la diferencia de ambos tiempos y con eso se obtiene el tiempo tardado por el algoritmo al comparar las dos secuencias leídas, el programa reúne los datos en una matriz, donde muestra la longitud de la primera cadena, la longitud de la segunda cadena, y el tiempo tardado en alinearlas. El programa continuara ejecutandose hasta que ya no hayan mas secuencias en el archivo fuente. Para el ejemplo mostrado se usaron dos archivos fuentes distintos con cadenas aleatorias.

gui.tar.gz

pairwise-alignment-in-python-dnksks.tar.gz

* Orengo, C., Jones, D. T., y Thornton, J. M. (2003). Bioinformatics: genes, proteins and computers. Garland Science.

* Ansorge, W.J. (2009). «Next-generation DNA sequencing techniques.». New Biotechnology 25

* Needleman, Saul B. & Wunsch, Christian D. (1970). “A general method applicable to the search for similarities in the amino acid sequence of two proteins”. Journal of Molecular Biology 48 (3): 443–53