Page d'accueil > Catalogue > Informatique - Informatique appliquée

Algoritmos genéticos aplicados a búsqueda de motifs en secuencias de ADN

Name: Algoritmos genéticos aplicados a búsqueda de motifs en secuencias de ADN
Price: 27.95 EUR
Availability: InStock
Author: Miguel Angel Castañeda Reyes
ISBN: 978-3-668-43952-8

Thèse de Master, 2016

58 Pages

Miguel Angel Castañeda Reyes (Auteur)

Extrait

Índice General

Agradecimientos

Índice de Figuras

Resumen

Abstract

Capítulo 1 Introducción
1.1 Antecedentes
1.2 Planteamiento del problema
1.3 Justificación
1.4 Hipótesis
1.5 Objetivo general
1.6 Objetivos específicos
1.7 Contribuciones esperadas

Capítulo 2 Marco teórico
2.1 Motifs de ADN
2.2 Métodos exhaustivos de búsqueda
2.3 El problema de la búsqueda de motifs
2.4 Complejidad y análisis del problema de búsqueda de motifs
2.5 Algoritmos genéticos
2.5.1 Representación de un cromosoma
2.5.2 Algoritmo genético simple
2.5.3 Selección
2.5.4 Selección por ruleta
2.5.5 Selección por torneo
2.5.6 Cruzamiento
2.5.7 Mutación
2.5.8 Evaluación
2.6 Importancia de la optimización
2.7 Trabajos previos realizados para la búsqueda de motifs
2.8 Método de muestreo de Gibbs

Capítulo 3 Modelo propuesto
3.1 Búsqueda de motifs por posición usando AGs
3.2 Búsqueda de motifs por patrones usando AGs

Capítulo 4 Experimentos y resultados
4.1 Pruebas con datos del ADN del homosapiens
4.2 Prueba Shapiro-Wilks, T de Student y Wilcoxon

Capítulo 5 Conclusiones y trabajo futuro

Referencias

Agradecimientos

En primer lugar, quiero agradecer a Dios por permitirme vivir día con día

A mis padres por darme la vida y darme las herramientas necesarias para ser una persona de bien

A mis hermanos por todo el apoyo y cariño que me han brindado desde mi nacimiento. A mi esposa por ser una leal compañera y alentarme siempre en seguir adelante

A mi hijo por darme la dicha de ser padre y por fortalecer mi responsabilidad de ser mejor persona cada día

A mis amigos por convivir conmigo, alentarme y hacerme ver mis errores

A mis compañeros de la maestría por sus enseñanzas y trabajo en conjunto durante las horas de clase

A mi asesor de tesis por guiarme para alcanzar este grado

A mis compañeros de trabajo y a todos aquellos que conviven conmigo diariamente, porque aprendo algo nuevo cada día gracias a ellos

A mis sinodales por tomarse el tiempo de revisar mi trabajo y ser el jurado en mi defensa de tesis

Índice de Figuras

Fig. 1 Traducción de genes a proteínas

Fig. 2 Sitios de Unión de Factores de Transcripción (TFBS)

Fig. 3 Representación gráfica de un motif basado en frecuencias

Fig. 4 Superposición de secuencias

Fig. 5 Parámetros

Fig. 6 Sumatoria para obtener la puntuación

Fig. 7 Pasos para obtener la puntuación

Fig. 8 Representación binaria de un cromosoma

Fig. 9 Algoritmo genético simple

Fig. 10 Selección por ruleta

Fig. 11 Selección por torneo

Fig. 12 ADN a evaluar

Fig. 13 Gráfica de aptitud por posición

Fig. 14 Gráfica de aptitud por patrón

Fig. 15 Gráfica de porcentaje de precisión

Fig. 16 Gráfica de efectividad

Fig. 17 Gráfica de número de operaciones realizadas

Fig. 18 Gráfica de aptitud por posición con datos del homosapiens

Fig. 19 Gráfica de aptitud por patrón con datos del homosapiens

Fig. 20 Gráfica de porcentaje de precisión con datos del homosapiens

Fig. 21 Gráfica de efectividad con datos del homosapiens

Fig. 22 Gráfica comparativa de tiempo

RESUMEN

En esta tesis presento la comparación de dos enfoques para resolver el problema de la búsqueda de motifs en secuencias de ADN mediante el uso de algoritmos genéticos, el primer enfoque hace una búsqueda por posición, que es evaluar los patrones obtenidos de posiciones iníciales y determinar si es el motif a encontrar en las secuencias, el segundo enfoque es la búsqueda por patrón, que es evaluar todas las posibles cadenas que se pueden formar con una longitud fija de nucleótidos e ir comparando de principio a fin dentro de las secuencias de ADN para encontrar el motif.

Los motifs son una clase de patrones en el contexto del análisis de secuencias biológicas y son de mucha importancia porque se sabe que ciertas proteínas especiales llamadas TF (Transcription Factors) o Factores de Transcripción, se unen con algunas subcadenas en el ADN formando los motifs o TFBS(Transcription Factors Binding Sites) en español Sitios de Unión de Factores de Transcripción y con estas uniones se activa o desactiva el proceso de expresión genética, mediante el cual los genes son transcritos en forma de ARN mensajero(mARN) llamado ribosoma, el ribosoma toma una secuencia de nucleótidos y los traduce en una cadena de aminoácidos en el orden establecido por el mARN, formando cadenas poliméricas lineales de una proteína.

Los algoritmos genéticos son modelos computacionales que simulan los procesos biológicos de la reproducción de las especies y nos ayudan a resolver problemas de optimización y búsqueda. En este comparativo entre la búsqueda de motifs por patrones y la búsqueda de motifs por posiciones se pretende determinar qué método es más eficiente para encontrar los patrones con mayor exactitud, ¿cuál es su complejidad computacional? y cómo se comporta generación tras generación en el algoritmo genético.

ABSTRACT

In this thesis, I present the comparison of two approaches to solve the problem of finding motifs in DNA sequences using genetic algorithms, the first approach does a position search, which is to evaluate the patterns obtained from initial positions and determine if is the motif to find in the sequences, the second approach is a search by pattern, which is to evaluate all possible strings that can be formed with a fixed length of nucleotides and go comparing from beginning to end within the DNA sequences to find the motif.

Motifs are a class of patterns in the context of biological sequence analysis and are of great importance because it is known that certain special proteins called TF (Transcription Factors) that are joined with some substrings in the DNA forming the motifs or TFBS (Transcription Factors Binding Sites) and with these unions are activated or deactivated the gene expression process whereby genes are transcribed in a form of mRNA called ribosome, the ribosome takes a nucleotide sequence and translates it into a chain of amino acids in the established order by the mRNA forming linear polymer chains of a protein.

Genetic algorithms are computational models that simulate the biological processes of species reproduction and help us solve problems of optimization and search. In this comparison between the search for motifs by patterns and the search for motifs by positions is intended to determine which method is more efficient to find the patterns with greater accuracy, what is its computational complexity? and how it behaves generation after generation in the genetic algorithm.

Capítulo 1 Introducción.

1.1 Antecedentes.

La biología moderna tiene una gran cantidad de dudas fascinantes y nunca antes se había estado tan cerca de responder, por ejemplo, ¿Cómo se adaptan las especies a su ambiente?, ¿Qué parte de nuestro genoma está evolucionando más rápido?, ¿Somos descendientes de los neandertales?, etc. Muchas preguntas hechas en la biología moderna solo pueden responderse con el análisis computacional de grandes cantidades de datos genómicos.[1]Este análisis de datos mediante herramientas y técnicas computacionales es lo que se conoce como bioinformática. Dentro de la bioinformática se utilizan técnicas computacionales, matemáticas y estadísticas para el análisis, interpretación y generación de datos biológicos.[2]

Las primeras secuencias del genoma humano[23]fueron obtenidas en el 2001, estas secuencias genómicas se representan en grandes volúmenes de datos digitales por lo que para su análisis fue necesario encontrar nuevas técnicas que ayudaran a entender como estaba formado el ADN y su funcionamiento, para ayudar a la biología a entender cómo están formados los organismos, se puede decir que la bioinformática es de mucha importancia porque nos permite determinar qué información es biológicamente relevante a nivel molecular.[3]

Para estudiar estos datos se han utilizado métodos exhaustivos para recorrer las secuencias de ADN. Los métodos exhaustivos o también conocidos como de fuerza bruta son una herramienta utilizada cuando no se tiene un método eficiente para llegar a la solución, ya que examinan cada una de las posibles alternativas para encontrar dicha solución[14], concretamente para este trabajo la solución es encontrar patrones dentro del ADN.

Existe una clase de patrones dentro de las secuencias de ADN que se les conoce como motifs de ADN o Sitios de Unión de Factores de Transcripción o Transcription Factor Binding Sites (TFBS por sus siglas en inglés), que son patrones en secuencias biológicas que pueden indicar ciertas características biológicas, estos patrones son de longitudes pequeñas de entre 6 y 12 caracteres. La pregunta es ¿porqué son importantes estos motifs ? son importantes porque nos pueden ayudar a entender cómo se traduce la información genética para dar origen a los seres vivos.[8]Los motifs en español se les conoce como “motivos”, pero dentro de este trabajo se utilizará el término motifs para estar más apegado a la literatura existente.

Se sabe que ciertas proteínas especiales llamadas TF (Transcription Factors) o Factores de Transcripción, se unen con algunas subcadenas en el ADN formando los TFBS y con estas uniones se activa o desactiva el proceso de expresión genética, mediante el cual los genes son transcritos en forma de ARN mensajero (ácido Ribonucleico).[8]

Para la biología es muy importante la identificación de los TFBS’s y de elementos que controlan la expresión genética y las interacciones entre los Factores de Transcripción (FT) para explicar el origen de los seres vivos.[8]

En la actualidad se tienen grandes cantidades de datos biológicos en las secuencias de ADN de los organismos, es importante buscar técnicas que nos ayuden a encontrar patrones dentro de todos estos datos.[17]

La búsqueda de motifs no es algo fácil, es complicado encontrar patrones en tan grandes cantidades de datos, a esto se le conoce como el problema de la búsqueda de motifs y puede ser parafraseado de la siguiente manera: Dentro de un conjunto de secuencias aleatorias de ADN, un motif padre de longitud “l” se encuentra en cada secuencia en lugares aleatorios. En ocasiones el motif muta en “d” lugares, el problema es recuperar las posiciones de estos motifs, conociendo solo los parámetros “l” y “d” y que cada secuencia contenga una instancia del motif.[24]

El problema de la búsqueda de motifs por su complejidad pertenece a la clase de problemas NP-Completos, ya que no es posible encontrar una solución en tiempo polinomial, además que los motifs son señales muy pequeñas y en poca cantidad en comparación de la secuencia de ADN donde se buscan.[18]

Para evitar evaluar todas las posibles soluciones que nos dan los métodos exhaustivos se pueden acotar las posibilidades solo evaluando algunas soluciones que nos pudieran ayudar en nuestro caso a encontrar el motif, estas posibles soluciones pueden ser evaluadas con algoritmos genéticos (AG), que son una técnica de optimización y búsqueda basada en los principios de la genética y la selección natural.

Un AG permite a una población compuesta de muchos individuos a evolucionar bajo las reglas de la selección a un estado que maximiza la aptitud.[7]Cada uno de estos individuos representan una solución y bajo los principios genéticos de cruzamiento y mutación se puede encontrar una solución que represente el motif a buscar. En otras palabras un AG crea poblaciones y cada individuo es evaluado y es una solución potencial, los nuevos individuos de las nuevas generaciones van cambiando y aproximándose más a la solución ya que también son evaluados y se puede determinar que tan aptos son, es decir, que los que tengan una aptitud mayor pasarán su información a las nuevas generaciones y además serán cruzados con otros individuos para mejorar su aptitud, así como también pueden mutar para tener cambios que permitan explorar más posibles soluciones.

Los AG generan aproximaciones a la solución, pero no se puede garantizar encontrar siempre la mejor solución, pero por lo general son buenos para encontrar una que satisfaga lo que se está buscando u optimizando.

Los algoritmos genéticos fueron creados por John Holland en los años 60, y desarrollados por él mismo junto a sus estudiantes y sus colegas de la Universidad de Michigan, esta técnica imitaba en su funcionamiento a la selección natural y hasta la actualidad siguen siendo utilizados ampliamente en la bioinformática.[28]

En este trabajo se plantea utilizar un par de enfoques utilizados por los métodos exhaustivos para la búsqueda de motifs, el primero hace una búsqueda por posición, es decir, que analiza ciertas posiciones iníciales, estas posiciones son aleatorias e indican el inicio de cada patrón en cada una de las secuencias de ADN donde se van a buscar los motifs, las secuencias de ADN provienen de un extenso volumen de datos genéticos. Las posiciones iníciales leen las secuencias de datos y regresan cadenas cortas de tamaño fijo, estas cadenas de caracteres se alinean y se contabiliza la frecuencia de los nucleótidos del ADN(A, C, G, T) por cada columna para obtener el consenso y una puntuación, el consenso con la mayor puntuación representa una aproximación a la solución.

El segundo enfoque es la búsqueda por patrón, que es evaluar todas la posibles cadenas que se pueden formar con una longitud fija de nucleótidos e ir comparando de principio a fin dentro de las secuencias de ADN para encontrar el motif buscado, para ambos enfoques sería muy costoso en tiempo tratar de encontrar la solución con todas las posibles combinaciones tanto de posiciones iníciales para el primer enfoque como todas las posibles cadenas en el segundo enfoque es decir ir de AAAAA hasta TTTTTT siendo el motif a buscar solo de 6 dígitos, por esta razón los algoritmos genéticos mediante poblaciones aleatorias, las cuales representan posibles soluciones, se evalúan se cruzan y se mutan como lo haría la genética para dar origen a nuevos individuos que representen una buena solución.

En la literatura existen varios trabajos realizados para tratar de resolver el problema de la búsqueda de motifs, algunos usan algoritmos genéticos, el método de muestreo de Gibbs y algoritmos exhaustivos en general, muchos de los cuales sirvieron como referencia para realizar este trabajo.

La importancia de este trabajo es analizar cuál de los dos enfoques de búsqueda empleados se adapta mejor con los algoritmos genéticos, ya que solo a nivel exhaustivo el enfoque por posiciones tiene mayor complejidad algorítmica que el enfoque por patrones.

Los dos enfoques de búsqueda ya han sido explorados ampliamente pero aún no han sido comparados entre si con algoritmos genéticos. El comparativo incluye cual es más preciso y eficiente para encontrar los motifs, en cuanto a tiempo lo encuentra pero lo más importante es cuantas operaciones debe realizar para encontrarlo en cada ejecución.

1.2 Planteamiento del problema

En este trabajo se pretende adaptar los dos enfoques de búsqueda por posición y búsqueda por patrón a los algoritmos genéticos para saber cuál tiene mayor precisión y eficiencia para encontrar los motifs. También se pretende saber si mejora su complejidad computacional de los dos enfoques exhaustivos ya adaptados a los algoritmos genéticos.

1.3 Justificación

Es importante saber que la búsqueda de motifs en una cantidad grande de información no puede realizarse mediante fuerza bruta por ser un problema NP-Completo, esto nos podría llevar muchos días incluso años en encontrar estos patrones, por eso es el interés de poder encontrar más técnicas que nos permitan encontrar rasgos significativos en el ADN.

Los dos enfoques de búsqueda nos permiten revisar los datos de las secuencias de ADN evaluando todas las posibilidades de búsqueda, sin embargo se debe diseñar un buen método como herramienta para encontrar estos patrones, particularmente en este trabajo se debe diseñar un algoritmo genético y analizar con cual de los dos enfoques se adecua más para encontrar los motifs.

Existen trabajos previos realizados con técnicas computacionales aunque la precisión es aceptable aún no es del todo satisfactoria y la búsqueda de motifs sigue siendo un problema difícil.[17]Por lo cual se pretende analizar el comportamiento de los dos enfoques con algoritmos genéticos.

1.4 Hipótesis

Al comparar el funcionamiento de los algoritmos genéticos basados en el enfoque de búsqueda por patrones y el enfoque de búsqueda por posición, el algoritmo más rápido y más exacto para encontrar motifs es el de búsqueda por posiciones ya que a pesar de tener una mayor complejidad algorítmica en su enfoque exhaustivo, al adecuarse mejor con los algoritmos genéticos permite hacer mejores y más eficientes búsquedas y reducir su complejidad computacional al hacer menos operaciones que la búsqueda por patrones.

1.5 Objetivo general

El objetivo general de este trabajo es hacer un comparativo de los enfoques de búsqueda por posición y búsqueda por patrón mediante los algoritmos genéticos (AG) para no tener que explorar todas las secuencias exhaustivamente, los AG acotan todas las posibilidades y utilizan las más significativas para encontrar la solución. Los resultados dan a conocer que método es más eficiente para encontrar los motifs, es decir cuál encuentra mejor estos patrones con datos simulados, estos datos son secuencias creadas aleatoriamente, pero se insertan motifs en posiciones aleatorias de forma manual en cada secuencia, y datos del Homosapiens, también se obtiene el resultado de cual es más rápido tomando en cuenta la complejidad de cada uno de los métodos propuestos.

1.6 Objetivos específicos

Los objetivos específicos de este trabajo son:

- Diseñar un algoritmo genético que se adecúe a los enfoques de búsqueda por patrón y por posición.
- Generar un análisis de resultados de las pruebas realizadas para medir cual de los enfoques es más rápido y más preciso para encontrar los motifs.
- Evaluar cual es la complejidad computacional de ambos enfoques con algoritmos genéticos.

1.7 Contribuciones esperadas

La principal contribución esperada es hacer un análisis comparativo entre la búsqueda por posición y búsqueda por patrón, ambos enfoques con algoritmos genéticos, esperando que sea un trabajo útil para biólogos o bioinformáticos que quieran entender el uso de dichos enfoques y contribuyan para crear más herramientas para la búsqueda de motifs.

Capítulo 2 Marco Teórico.

2.1 Motifs de ADN.

Los motifs son una clase de patrones en el contexto del análisis de secuencias biológicas. En general los motifs podrían representar patrones en cualquier tipo de secuencias biológicas tales como secuencias de ADN, secuencias de ARN, secuencias de proteínas, etc.[26]Pero para este trabajo en particular solo se abarcan los de las secuencias de ADN.

Los motifs son conocidos también como TFBS (Transcription Factor Binding Sites) o Sitios de Unión de Factores de Transcripción, se sabe que proteínas especiales o Factores de Transcripción (TF) unidas con subcadenas en el ADN forman estos TFBS, y estas uniones pueden activar o desactivar procesos, los cuales transcriben genes en forma de ARN mensajero (ácido Ribonucleico), estas interacciones dan origen a los organismos vivos por eso los motifs o TFBS’s son tan importantes en la biología.[8]

Las principales características de los motifs es que son de tamaño constante, su tamaño es pequeño (6 a 10 bases) y se presentan en las secuencias de ADN, las cuales están hechas de un alfabeto de 4 caracteres, A, C, G, T. Adenina, Citosina, Guanina y Tiamina respectivamente, que son las bases en las secuencias de ADN[18]

Sin embargo, los principales retos que se presentan en la búsqueda de motifs es que los motifs son señales muy pequeñas y en poca cantidad en comparación al tamaño de la secuencia de ADN donde se buscan. Así como también el problema de la búsqueda de motifs es del tipo NP-Completo por lo que no hay una solución en tiempo polinomial. [18]

En la siguiente imagen se muestra como primeramente el ADN es transcrito a una secuencia de mARN, posteriormente el ARN hace una traducción para convertirlo a una proteína. En otras palabras el ADN hace al ARN y el ARN hace las proteínas. El ribosoma toma una secuencia de nucleótidos y los traduce en una cadena de aminoácidos en el orden establecido por el mARN, formando cadenas poliméricas lineales de una proteína.[27]Las secuencia de mARN es una fiel copia de la secuencia de ADN, pero este caso el ARN utiliza el nucleótido uracil (U) en lugar de la tiamina(T).[14]

Abbildung in dieser Leseprobe nicht enthalten

Fig. 1 Traducción de genes a proteínas.[14]

En la siguiente imagen se ve un modelo genérico de cómo trabaja un motif o un sitio de unión de factores de transcripción (TFBS por sus siglas en inglés).

Un factor de transcripción se une con un sitio de unión del ADN y de este modo regula la producción de una proteína desde un gen.[22]

Abbildung in dieser Leseprobe nicht enthalten

Fig. 2 Sitios de unión de factores de transcripción (TFBS).[22]

A continuación, muestro las frecuencias de los nucleótidos en cada posición y posteriormente la representación gráfica de los motifs basado en estas frecuencias:

Abbildung in dieser Leseprobe nicht enthalten

Fig. 3 Representación Gráfica de un Motif basado en frecuencias.[9]

2.2 Métodos exhaustivos de búsqueda.

Los métodos exhaustivos son conocidos también como de fuerza bruta ya que examinan cada una de las posibles alternativas para encontrar una solución.[14]Estos métodos son muy útiles sobre todo cuando no se conoce un método eficiente de solución, además que no son difíciles de diseñar y programar, son buenos para resolver algunos problemas en la biología, pero cabe señalar que pueden tardar mucho tiempo en encontrar una solución cuando crece el tamaño de variables a evaluar.

Existen muchos métodos que a su vez utilizan métodos exhaustivos para solucionar problemas, pero reducen su complejidad al ir descartando posibilidades que se sabe que no están dentro del rango de soluciones, como lo hacen los algoritmos de Branch-and- Bound o en español son conocidos como ramificación y acotamiento y los algoritmos genéticos en los cuales se hace enfoque en este trabajo.

2.3 El problema de la búsqueda de motifs.

Para encontrar una serie de motifs o patrones dentro de secuencias de ADN es necesario utilizar un método que nos permita revisar las secuencias y determinar si existe un patrón o motif en común.[13]

Para ejemplificar esto se crean secuencias aleatoriamente:

GACTTATGCAAGCTAGATTTAAATTAGACC

GATTGAGGCCTCAGCATGCATGCAACGTAC

AACGTAACCGTGGCATTGCAGCGTACGTTT

TTAGGGCATCAACGTTCAACGTTTAACTGG

TAGCACTGGTACGTACTGAATTTCAAAGGA

AGCTTGAGCATTAACGCACACTGGTTTGCA

TACGATCATGAGCATATCATGATGCATGGG

CATTTTACTTGACACGTAACATCCTGATTT

A continuación, solo con fines de ejemplificar y sea más simple de entender, sabiendo que los motifs ocurren naturalmente, se implanta el motif ACGTACGT en cada secuencia para tener lo siguiente.

GACTTATGACGTACGTATTTAAATTAGACC

GATTGAGGCCTCAGCATGCACGTACGTTAC

AAACGTACGTTGGCATTGCAGCGTACGTTT

TTAGGGCATCAAACGTACGTGTTTAACTGG

TAGACGTACGTCGTACTGAATTTCAAAGGA

AGCTTGAGCATTAACGCACAACGTACGTCA

TACGATCATACGTACGTCATGATGCATGGG

CATTTTACTTGACACGTAACATACGTACGT

Ya se tiene un motif en cada renglón pero a simple vista no se puede descubrir pero existe en cada secuencia.

GACTTATGACGTACGTATTTAAATTAGACC

GATTGAGGCCTCAGCATGCACGTACGTTAC

AAACGTACGTTGGCATTGCAGCGTACGTTT

TTAGGGCATCAAACGTACGTGTTTAACTGG

TAGACGTACGTCGTACTGAATTTCAAAGGA

AGCTTGAGCATTAACGCACAACGTACGTCA

TACGATCATACGTACGTCATGATGCATGGG

CATTTTACTTGACACGTAACATACGTACGT

Debido a que los motifs ocurren naturalmente no siempre se tendrá el patrón exacto en todas las secuencias porque en muchos casos puede haber mutaciones, por lo que se cambiará en 2 posiciones al azar cada motif para que el ejemplo sea más apegado a la realidad.

GACTTATGACGTtCcTATTTAAATTAGACC

GATTGAGGCCTCAGCATGCgCGTcCGTTAC

AAACaTACcTTGGCATTGCAGCGTACGTTT

TTAGGGCATCAAAgGTACGgGTTTAACTGG

TAGACGTtCGgCGTACTGAATTTCAAAGGA

AGCTTGAGCATTAACGCACAACGcgCGTCA

TACGATCATAaGTACtTCATGATGCATGGG

CATTTTACTTGACACGTAACATACGTAgGa

Como información adicional se debe conocer la longitud de cada motif en este caso es 8. La pregunta es ¿se puede encontrar el motif si se tiene una mutación en dos letras?

Esto es posible realizando una superposición, una alineación y un conteo de ocurrencias, este último se le conoce como perfil y por último el consenso. La superposición de los motifs es decir un paso previo a la alineación de los motifs.

GACTTATGACGTtCcTATTTAAATTAGACC

GATTGAGGCCTCAGCATGCgCGTcCGTTAC

AAACaTACcTTGGCATTGCAGCGTACGTTT

TTAGGGCATCAAAgGTACGgGTTTAACTGG

TAGACGTtCGgCGTACTGAATTTCAAAGGA

AGCTTGAGCATTAACGCACAACGcgCGTCA

TACGATCATAaGTACtTCATGATGCATGGG

CATTTTACTTGACACGTAACATACGTAgGa

Fig. 4 Superposición de secuencias[14]

A continuación se hace la alineación de motifs, se contabiliza la frecuencia de cada letra para obtener el perfil y por último obtener el consenso, eligiendo el caracter con valor máximo.

Abbildung in dieser Leseprobe nicht enthalten

Para llegar al consenso previamente se deben conocer las posiciones iniciales Si de cada motif.

Abbildung in dieser Leseprobe nicht enthalten

Encontrar el motif es relativamente fácil, cuando se conocen las posiciones iníciales, pero normalmente en la realidad no se conocen estas posiciones, ¿cómo se puede encontrar entonces el perfil o el consenso? La respuesta es encontrar una función que evalúe cierto número posiciones y regrese un resultado, el mejor resultado será el que ayude a encontrar el motif a esto le llamamos Puntuación.

Definición de parámetros.

t - Número de secuencias de ADN.

n - Longitud de cada secuencia de ADN.

ADN - Muestra de secuencias de ADN (arreglo de t x n).

l - Longitud del motif o patrón.

Si - Posición inicial de un elemento en la secuencia i. s = (S1, S2, S3, , St) - Arreglo de posiciones iniciales de cada motif.

s{S1=9 S2=20 S3=3 S4=13 S5=4 S6=21 S7=10 S8=23}

Abbildung in dieser Leseprobe nicht enthalten

Fig. 5 Parámetros. [14]

En esta figura se observan los parámetros que se utilizan para hacer la búsqueda de motifs, el número de renglones es t, l es la longitud conocida del motif, n es la longitud de cada renglón, ADN es el texto completo donde se van a buscar los motifs y finalmente s que es el arreglo que guarda las posiciones iníciales.

Evaluación de motifs.

Para la evaluación de motifs se tiene una función que obtiene la puntuación de las posiciones iníciales de los motifs, para esto necesitamos realizar la alineación, obtener el perfil y realizar el consenso.

La puntuación se obtiene de la siguiente manera:

Dado s = (S1, . . . , St) y ADN:

Puntuación(s, ADN) =

Abbildung in dieser Leseprobe nicht enthalten

Fig. 6 Sumatoria para obtener la puntuación [14]

Como se puede ver en la figura se contabiliza el número máximo que se repite cada letra por columna, lo cual nos dará un número que se sumará por columna para dar como resultado la puntuación.

En otros términos.

Abbildung in dieser Leseprobe nicht enthalten

Fig. 7 Pasos para obtener la puntuación [14]

Como se observa en la figura después de alinear las secuencias se debe contabilizar el número de frecuencias máximo por columna para obtener el consenso y la puntuación.

Pseudocódigo para obtener la Puntuación.

ObtenerPuntuacion(s)

BEGIN

FOR Columna Inicial TO Columna Final

Contabilizar Frecuencias por Columnas

ValMaxPorColumna = Obtener Valor Máximo por Columna

Puntuación = Puntuación + ValMaxPorColumna

END FOR

RETURN Puntuación

END

Como se puede ver en este pseudocódigo para obtener la puntuación, se recibe como parámetro el arreglo de las posiciones iniciales de cada motif, se recorre columna por columna contabilizando las frecuencias de A, C, G, T, después se obtiene el valor máximo por columna y se va guardando en una variable para sumarse cada una y finalmente regresar el valor de esa variable.

Puntuación Máxima Ideal.

La puntuación máxima que se puede obtener es cuando el arreglo de posiciones iniciales devuelve la mayor puntuación posible, es decir, cada posición inicial trae consigo los patrones que cuando se alinean y se contabilizan sus frecuencias por columna nos da como resultado el valor máximo a obtener, por ejemplo:

GACTTATGCAAGCTAGACGTACGTTAGACCGGAGTCAGCTGCATGAAGACTGCATGGTAG

GATTGAGGCCTCAGCATGCATGCAACGTACGTACTAGCAACGTTGCAGTACGTGACTGAC

TAACGTACGTTGGCATTGCAGCGTACGTTTGCATGCACGGCTAATGCAAGGCTACGGTTC

TTAGGGCATCAACGTTCAACGTTTAACTGGTGGTGCACCACTGCACGTACGTGCCGAGGA

TAGCACTGGTACGTACTGAACGTACGTTGACGTTTAAAGCAGCCCGTCAGTCCTACGTGC

AGCTTGAGCATTAACGCACACTGGTTTGCAACGTACGTCACTGACTGACTTCAGTCGTTA

TACGATCATGAGCATATCATGATGCATGGGAAGCATTTACTACGTACGTACGTCCGTACA

ACATTTTACTTGACACGTAACATCCTGATTTACGTACGTACACGTACTACGAACTGACAG

GCAGCTACAACTCGGGACATGCTTGCATCTACGGGTGCACTGCACCATGCACGTACGTCA

CACATGCATGCACCACGTACGTAACGTTGGTACAATGGGACTACGATCGGCTACACGTGC

TACGACTGACTCATCAACGTAACTACGAAACAACGTACGTATGCTATGCAATGCATGCTA

ACATCTGGGTAACGTACGTTATATCATACATTTAGGAGGATGCCTTTGCACTAAGCATCT

En este ejemplo el arreglo de posiciones es s= (17,25,3,45,20,31,42,32,51,14,33,12).

Al obtener el patrón que se obtiene de cada posición inicial tenemos:

Abbildung in dieser Leseprobe nicht enthalten

Posteriormente se alinea, se saca el perfil, se obtiene el consenso y la puntuación:

Abbildung in dieser Leseprobe nicht enthalten

La puntuación máxima que se puede obtener en el mejor de los casos es 96.

2.4 Complejidad y Análisis del problema de búsqueda de motifs.

Un algoritmo es una serie de instrucciones que se deben realizar con el fin de resolver un problema. Al solucionar algún problema mediante un algoritmo se puede hacer de diferentes formas, teniendo así diferentes soluciones algorítmicas llegando al mismo resultado. [11] Cuando atacamos un problema muy grande es necesario comparar una solución algorítmica con otra u otras para saber cuántos recursos de memoria o tiempo empleamos para resolver el problema.

No hay una fórmula mágica para analizar la eficiencia de los algoritmos. En su mayor parte es una cuestión de juicio, intuición y experiencia. Sin embargo, existen algunas técnicas básicas que suelen resultar útiles, tales como saber la forma de enfrentarse a estructuras de control y a ecuaciones de recurrencia. [11]

La eficiencia de los algoritmos se mide en función de dos parámetros, el espacio, que es la memoria que utiliza para resolver un problema y el tiempo, que es el tiempo que tarda en ejecutarse. [12]

Existen dos tipos de medición, la medida teórica consiste en obtener una función que acote el tiempo de ejecución de un algoritmo y otra medida real que consiste en medir el tiempo de ejecución de un algoritmo. [12] En otras palabras la medida teórica es el número de instrucciones por una computadora para llegar a la solución.

Para definir qué es lo que nos interesa medir ya sea espacio o tiempo se debe tener en cuenta con que tipo de computadora se ejecuta el algoritmo, es decir, si se utiliza un procesador de última generación comparado con uno de hace 20 años, se encontrará la solución más rápido en el de última generación, sin meterse en detalles de cuántos núcleos tiene para realizar operaciones simultáneas, etc. Por esta razón es difícil medir la complejidad algorítmica como unidad de tiempo, pero si se puede hacer contabilizando el número de instrucciones que realiza un algoritmo, suponiendo que el tiempo de cada instrucción es constante.

Por ejemplo si se tiene la función:

function int sumaBucle(int a, int n)

{

int suma = 0;

for( int i = 0; i < n; i++)

{

suma = suma + a;

suma = suma + 1;

} return suma;

}

Suponiendo que se le pasan los valores 5 y 10 a la variable “a” y “n” respectivamente, se tiene que la línea dentro del ciclo for se ejecuta n veces, en este caso 10 veces, pero como son dos instrucciones dentro del for entonces se ejecuta 2n veces, más la instrucción de retorno en la penúltima línea se tiene entonces que la complejidad de esta función es de 2n + 1. Al final la función devolverá un valor, pero no es relevante para medir la complejidad en este caso particular. Es importante saber que tanto incrementa el tiempo de ejecución cuando se aumenta el valor de n, como se puede ver la función 2n + 1 es lineal y el valor que se pasa a “n” se multiplica por 2, no es lo mismo si “n” vale 10 se ejecutará 20 veces a si vale 1000 se ejecuta 2000 veces, al final se le suma el + 1 y quedaría de 21 instrucciones y 2001 instrucciones respectivamente.

Algunos de los órdenes más importantes se enumeran de la siguiente manera:[15]

Abbildung in dieser Leseprobe nicht enthalten

Los problemas P o polinomiales son complejos pero con la ayuda de computadoras pueden resolverse rápido, no todos los problemas pueden ser resueltos en tiempo polinomial, existen otro tipo de problemas como los NP-Completos, NP viene de No Polinomial por sus siglas en inglés, un ejemplo es el clásico problema del vendedor viajero, donde es posible encontrar la solución pero hasta la fecha no se conoce un algoritmo rápido para solucionar este tipo de problemas, se puede decir que los problemas NP-Completos son teóricamente intratables y no pueden resolverse en tiempo polinomial, es decir, tardaríamos miles de años en encontrar una solución óptima, pero puede realizarse una aproximación permitiendo acercarse a la solución en un tiempo polinomial.[16]

En base al libro de Pevzner[14], el algoritmo de fuerza bruta en pseudocódigo para encontrar las posiciones iníciales dentro de las secuencias de ADN es:

BRUTEFORCEMOTIFSEARCH(DNA, t, n, l)

Abbildung in dieser Leseprobe nicht enthalten

Donde el DNA es el conjunto de datos del ADN a analizar, t es el número de secuencias, n es la longitud de las secuencias y l es la longitud del motif.

El número de posiciones se evalúa:

Abbildung in dieser Leseprobe nicht enthalten

La complejidad algorítmica en el peor de los casos de la búsqueda por posiciones es:

Abbildung in dieser Leseprobe nicht enthalten

El pseudocódigo para hacer la búsqueda por patrón es:

BRUTEFORCEMEDLANSEARCH(DNA, t, n, l)

Abbildung in dieser Leseprobe nicht enthalten

De igual manera que en el pseudocódigo anterior, DNA es el conjunto de datos del ADN a analizar, t es el número de secuencias, n es la longitud de las secuencias y l es la longitud del motif.

Su complejidad algorítmica en el peor de los casos:

Abbildung in dieser Leseprobe nicht enthalten

Donde el número 4 representa a los 4 nucleótidos del ADN(A, C, G, T).

Al realizar una serie de ejercicios se puede observar que la complejidad de la búsqueda por posición es menor a la búsqueda por patrón.

Tomando en cuenta que n es la longitud de las secuencias, l es el tamaño del motif y t es el número de secuencias a buscar.

Abbildung in dieser Leseprobe nicht enthalten

Búsqueda por posición:

Abbildung in dieser Leseprobe nicht enthalten

Búsqueda por patrón:

Abbildung in dieser Leseprobe nicht enthalten

Búsqueda por posición:

Abbildung in dieser Leseprobe nicht enthalten

Búsqueda por patrón:

Abbildung in dieser Leseprobe nicht enthalten

Búsqueda por posición:

Abbildung in dieser Leseprobe nicht enthalten

Búsqueda por patrón:

Abbildung in dieser Leseprobe nicht enthalten

2.5 Algoritmos genéticos.

Los algoritmos genéticos son un modelo computacional, utilizados en problemas de búsqueda y optimización inspirados en la evolución humana, la reproducción sexual y en el principio de supervivencia del más apto.

Una definición más formal dada por Goldberg es que "los algoritmos genéticos son algoritmos de búsqueda basados en la mecánica de selección natural y de la genética natural. Combinan la supervivencia del más apto entre estructuras de secuencias con un intercambio de información estructurado, aunque aleatorizado para construir así un algoritmo de búsqueda que tenga algo de las genialidades de las búsquedas humanas"(Goldberg, 1989) [13]

El primer paso en el algoritmo genético es generar una población de manera aleatoria, esto creará individuos que representan posibles soluciones y codificadas de una forma similar a un cromosoma que irán evolucionando conforme avancen las generaciones mediante la selección natural, el cruce y la mutación. A su vez estos cromosomas tendrán asociada una aptitud o fitness que nos permitirá cuantificar si es un buen individuo que represente una posible solución.

En base a esta aptitud se le pueden dar más o menos oportunidades de reproducirse pudiendo ser de una manera elitista, aunque cabe señalar que la mezcla con individuos menos calificados puede dar una mezcla que al final haga que los descendientes tengan una buena evaluación ya que dan más posibilidades de explorar otras soluciones sin caer en un solo sector en donde los individuos mejor calificados no lleguen a explorar del todo otras posibles soluciones.

2.5.1 Representación de un cromosoma.

La figura 8 muestra un cromosoma que por lo regular se representa de forma binaria, pero también puede representarse con números enteros, flotantes, reales, etc. Sin embargo se sustentará más adelante la razón del porqué se pueden realizar mejor las operaciones de un algoritmo genético de forma binaria.

Abbildung in dieser Leseprobe nicht enthalten

Fig. 8 Representación binaria de un Cromosoma [13]

2.5.2 Algoritmo genético simple.

BEGIN

Generar población Inicial

Evaluar cada individuo

WHILE NOT Terminado DO

FOR 1 TO Tamaño de la población / 2

Seleccionar un par individuos

Cruzar individuos seleccionados

Mutar descendientes

Evaluar descendientes Insertar descendientes en nueva generación

END FOR

IF Programa converge ó número de generaciones = N THEN Terminado = True

END IF

END WHILE END

Fig. 9 Algoritmo Genético Simple [20]

Cuando se dice que el programa converge es cuando ya no se tienen cambios en la solución en cada generación. Es decir, la solución ya no va a cambiar porque ya no se puede mover más y es posible que ya encontró la solución o porque se fue a un mínimo local y no puede explorar más posibles soluciones.

2.5.3 Selección.

Consiste en escoger a los mejores individuos dentro de una población dependiendo que tan aptos son, es decir, después de ser evaluados se seleccionan los que más sirven para llegar a una posible solución, la selección se puede hacer de varias formas, pero las más comunes son por torneo, por ruleta, por ranking. [19] 2.5.4 Selección por ruleta.

2.5.4 Selección por ruleta.

Consiste en que cada cromosoma se le asigna un porcentaje en base a su aptitud. La ruleta se gira tantas veces como número de cromosomas para ir determinando que individuos se irán seleccionando, de esta forma, los que tengan mayor aptitud tendrán la posibilidad de ser seleccionados con mayor frecuencia. [19]

Abbildung in dieser Leseprobe nicht enthalten

Fig. 10 Selección por ruleta. [19]

En este ejemplo en particular se debe girar 6 veces la ruleta, una por cada cromosoma, y se determina qué individuos se seleccionarán para posteriormente hacer el cruzamiento.

2.5.5 Selección por torneo.

Se refiere a poner a competir aleatoriamente a los individuos de la población en parejas, el mejor evaluado o más apto pasará a la siguiente generación, esto permite seleccionar a los mejores individuos pero también les da oportunidades de reproducirse a los menos aptos cuando compiten con los menos calificados, esto generará mayor diversidad de soluciones y de esta manera pueden ser parte de una solución óptima.

Al ser un torneo en parejas prevalecerá la mitad de esa generación, por lo que se deben realizar dos competencias, los más aptos serán seleccionados dos veces y tendrán más posibilidades de pasar a las siguientes generaciones. [19]

Abbildung in dieser Leseprobe nicht enthalten

Fig. 11 Selección por torneo [19]

En este ejemplo se puede observar que la selección por torneo al ser una competencia en parejas se benefician los individuos que tengan mejor aptitud, sin embargo, los que tienen menor aptitud tienen oportunidades al enfrentarse con alguno con aptitud baja.

2.5.6 Cruzamiento.

Es la simulación de la combinación biológica entre dos individuos que dará origen a nuevos descendientes. Mediante la combinación en un punto al azar de cruce, los cromosomas intercambian información que permitirá tener nuevos rasgos de los descendientes, buscando mejorar en cada generación la aptitud de los individuos para tener paulatinamente un acercamiento a la mejor solución. [19]

Para ejemplificar el cruzamiento de una posición se tienen dos cadenas.

Abbildung in dieser Leseprobe nicht enthalten

Si por ejemplo se escoge al azar el cruce en la posición 6, los descendientes quedan de la siguiente manera.

Abbildung in dieser Leseprobe nicht enthalten

Como se puede ver, ahora los dos descendientes tienen características de ambos cromosomas padres.

2.5.7 Mutación.

Permite modificar de forma aleatoria algún alelo de los cromosomas o individuos en un porcentaje bajo, lo que permite generar cambios significativos e ir mejorando características de dichos cromosomas, lo cual significa llegar a una mejor solución. [19]

Por ejemplo se tiene el cromosoma:

Abbildung in dieser Leseprobe nicht enthalten

Si se muta la posición 8, el cromosoma quedaría:

Abbildung in dieser Leseprobe nicht enthalten

Al mutar cualquier alelo al azar el individuo cambia y puede decirse que ya no es el mismo, ya que sufrió un cambio que puede ser significativo, sin embargo, la mutación se hace en un porcentaje muy bajo de individuos.

2.5.8 Evaluación.

Es necesario evaluar o calificar a cada individuo mediante una función de evaluación que nos indique si el individuo o cromosoma evaluado representa una buena solución. La función de evaluación regresa un valor numérico que se conoce también como aptitud o fitness, los individuos con mayor aptitud representan las mejores soluciones y tendrán mayores oportunidades de pasar su información a las siguientes generaciones. [19]

2.6 Importancia de la Optimización.

La optimización es el proceso de hacer mejor algo. Un ingeniero o científico crea una idea nueva, la optimización la mejora. La optimización consiste en tratar las variaciones de un concepto inicial y el uso de la información obtenida para mejorar la idea. [7]

Una computadora es una excelente herramienta para la optimización, pero se debe alimentar con datos suficientes y significativos para llegar a una solución. Optimización no significa encontrar la mejor solución en todos los casos, sino llegar a encontrar un resultado que satisfaga lo que se busca.

El término encontrar la mejor solución implica que podría haber varias soluciones y estas pueden ser unas mejores que otras. El término puede ser relativo y depende en sí del problema que se quiere resolver, en algunos casos será para buscar, maximizar o minimizar un resultado.

En este trabajo se incluye el término de optimización porque finalmente esta tesis incluye optimización de dos enfoques de búsqueda de motifs, al mejorar o al complementar estos métodos con algoritmos genéticos se está creando un par de enfoques optimizados.

2.7 Trabajos previos realizados para la búsqueda de Motifs

En la literatura se pueden encontrar muchos trabajos para resolver el problema de la búsqueda de motifs, como el realizado por Eric C. Rouchka y Bill Thompson basado en el método de muestreo de Gibbs el cual permite encontrar motifs en secuencias de ADN.

El método de muestreo de Gibbs consiste básicamente en contabilizar el número de ocurrencias y mediante métodos probabilísticos se obtiene la secuencia con mayor ocurrencia y esta determina el motif a buscar. [4] Desde un punto de vista personal es un buen método de búsqueda, pero tiende a quedarse en mínimos locales porque las soluciones se mueven muy poco, no es como los algoritmos genéticos que con el cruzamiento y la mutación puede tener más amplitud para encontrar la solución.

En el trabajo realizado por Liu Falcon y Tsai Jeffrey llamado FMGA: Finding Motifs by Genetic Algorithm, se utiliza una función total de aptitud para determinar el mejor individuo y obtener el motif, además se usa un método de penalizaciones para obtener las puntuaciones del consenso, con esto los motifs se pueden predecir de una manera más eficiente. Como se sabe, el consenso es la secuencia que refleja la base más frecuente en un conjunto de datos de ADN alineados. [5] Por la complejidad algorítmica es más tardado encontrar un motif con algoritmos genéticos que el muestreo de Gibbs, sin embargo, los autores confían más en la efectividad para la búsqueda de motifs usando algoritmos genéticos porque se obtienen mejores resultados de búsqueda.

En otro trabajo donde se utilizan Algoritmos Genéticos es el realizado por Dongsheng Che, Yinglei Song y Khaled Rasheed llamado MDGA: Motif Discovery Using a Genetic Algorithm, en el que también se habla de la importancia de otros algoritmos como métodos y técnicas experimentales como el “DNase foot-printing” y “gelshift assay” para la búsqueda de motifs. [6] La parte más interesante de este trabajo es el manejo de posiciones iníciales como el presentado en esta tesis y cuando encuentran alguna solución en un máximo o mínimo local hacen cambio de posiciones iníciales, permitiéndoles explorar otras soluciones y obtener buenos resultados, el manejo de posiciones como ya se ha visto anteriormente, es cuando se tiene un arreglo de posiciones s(pos1, pos2, pos3, pos4, pos n) donde al cambiar el orden de las posiciones en la función de aptitud arroja una nueva puntuación.

Por último, quiero mencionar el trabajo realizado por Fatemeh Zare-Mirakabad llamado Genetic Algorithm for dyad pattern finding in DNA sequences. [10] En donde hablan de un tipo de motifs pares separados por espacios, es decir, que estas secuencias pueden estar separadas pero representan patrones. Mencionan además que las aproximaciones que se utilizan para encontrar motifs no son del todo útiles para encontrar este tipo de patrones como el enfoque de búsqueda de motifs por posiciones. En este trabajo utilizan una función multiobjetivo basada en la suma de pares, el número de coincidencias y el contenido de información, los individuos de la población son optimizados por el método de muestreo de Gibbs. El algoritmo se implementa y prueba con diferentes conjuntos de datos reales.

Afortunadamente dentro de la bioinformàtica se han hecho grandes esfuerzos para encontrar métodos y técnicas para la búsqueda de motifs, se pueden nombrar y analizar muchos trabajos dentro de la literatura, lo cual aporta muchas ideas para diseñar un buen algoritmo de búsqueda de motifs, pero el objetivo general de este trabajo es hacer un análisis comparativo de los enfoques de búsqueda por posición y búsqueda por patrón mediante algoritmos genéticos y poder verificar cuàl devuelve mejores resultados.

2.8 Método de muestreo de Gibbs.

El método de muestreo de Gibbs, es un algoritmo de inferencia probabilística generalizado, utilizado para generar una secuencia de muestras a partir de una distribución de probabilidad conjunta de dos o más variables aleatorias. Su función consiste básicamente en contabilizar el número de ocurrencias y mediante métodos probabilísticos obtienen la secuencia con mayor ocurrencia, requiere un vector de parámetros de interés que son inicialmente desconocidos. El objetivo principal es encontrar estimaciones de los parámetros de interés para determinar que tan bien se ajustan los datos al modelo de interés y si coinciden con el modelo descrito por los datos observados. [4]

A continuación se muestra cómo encontrar un motif con el método de muestreo de Gibbs, se tiene que seguir el siguiente método.

Se tienen n secuencias y se pretende encontrar el motif.

1. CGTACTTCGT
2. GTACTACGTA
3. ACTAGGCATC
4. AGATCGACTT

Se debe escoger alguna secuencia, cualquiera que sea, para empezar el muestreo, en este ejercicio se selecciona la primera secuencia.

Posteriormente en las secuencias que no se seleccionaron se debe escoger una posición aleatoria de inicio en cada una, es decir en la secuencia dos, tres y cuatro.

GTACTACGTA

ACTAGGCATC

AGATCGACTT

Posteriormente se genera la tabla de frecuencias de las secuencias no seleccionadas.

Abbildung in dieser Leseprobe nicht enthalten

Nótese que en la columna 0 se ponen las frecuencias de los nucleótidos que están fuera de la posición inicial aleatoria.

La fórmula para obtener las probabilidades es la siguiente: [4]

Abbildung in dieser Leseprobe nicht enthalten

Para obtener la probabilidad de la columna 1 de A se sustituyen los valores.

Abbildung in dieser Leseprobe nicht enthalten

Donde bj es un número probabilístico asignado como constante y B es la suma de los 4 numero probabilísticos con valor 0.5 entonces B = 2 y N es el número total de frecuencias a contabilizar por columna.

También debe calcularse para la columna 0. En este caso se calcula la probabilidad de C en la columna 0. Nótese que en la probabilidad de los restantes es la siguiente fórmula:

Abbildung in dieser Leseprobe nicht enthalten

Si se calculan todas las probabilidades queda.

Abbildung in dieser Leseprobe nicht enthalten

El siguiente paso es calcular los pesos de cada posible posición de los motifs en la secuencia seleccionada previamente, se seleccionó la secuencia 1. CGTACTTCGT, después se debe seleccionar una posición inicial aleatoria.

CGTACTTCGT

Abbildung in dieser Leseprobe nicht enthalten

La probabilidad de que se empiece en la posición 1 es 1.21

Después se debe empezar en la segunda posición y así sucesivamente hasta la posición cuatro.

Abbildung in dieser Leseprobe nicht enthalten

Después deben normalizarse los resultados, es decir, que el valor de la columna 1 debe dividirse entre la suma de las cuatro columnas (1.21+0.026+0.0089+6.055=7.299), quedaría algo así:

Abbildung in dieser Leseprobe nicht enthalten

Esto quiere decir que debe empezarse en la posición 4 por tener la mayor probabilidad. Probabilísticamente el motif debe ser ACTTCGT para la secuencia 1.

El mismo procedimiento debe hacerse para las siguientes secuencias que deben alinearse para obtener el consenso y ese será el motif encontrado.

Capítulo 3 Modelo propuesto.

Existen diversos problemas bioinformáticos que se pueden resolver con algoritmos genéticos como la búsqueda de patrones. En este trabajo se hace una comparación entre dos enfoques para la búsqueda de motifs, el primero hace una búsqueda por posiciones, es decir, el cromosoma que se crea genera posiciones iniciales que serán evaluadas para encontrar el patrón a buscar, el segundo método hace búsquedas por patrones, en donde los cromosomas creados podrían ser en si el motif a buscar, estos patrones serán evaluados para encontrar el motif buscado.

3.1 Búsqueda de motifs por posición usando AGs.

Con este algoritmo genético se pretende generar poblaciones con posiciones aleatorias, estos individuos se evalúan y se determina cuál es el mejor en cada generación, también se pretende encontrar el consenso que indicará cuál es el motif encontrado.

Cada individuo de la población generada se representa como un cromosoma que contiene las posiciones iníciales que se van a evaluar y determinar que individuos representan una posible solución.

P1 = {34, 45, 23, 35, 2, 43, 29, 3, 32, 11, 32, 28}

P2 = {4, 24, 19, 43, 23, 5, 45, 11, 23, 10, 34, 33}

El archivo de datos tiene 60 caracteres de ancho, si el motif mide 8 dígitos la última posición donde se puede encontrar un motif es en la 52. Para esto se requieren 6 bits, se puede representar desde la posición 0 a la 63. Es decir, el 0 es representado como 000000 y el 63 como 111111. Entonces el cromosoma para 12 posiciones iníciales quedará 6 x 12 = 72 bits.

De esta manera, siguiendo el ejemplo anterior el primer individuo queda:

P1 = {34, 45, 23, 35, 2, 43, 29, 3, 32, 11, 32, 28}, la representación del cromosoma queda:

P1 = 100010 101101 010111 100011 000010 101011 011101 000011 100000 001011 100000 011100

Evaluación.

Una vez que se tienen las 12 posiciones iniciales se evalúan las secuencias que vamos a analizar.

En la forma en que se va a evaluar se requieren las posiciones iníciales.

Si se tiene el siguiente cromosoma:

100010 101101 010111 100011 000010 101011 011101 000011 100000 001011 100000 011100

Las posiciones en forma decimal son:

Abbildung in dieser Leseprobe nicht enthalten

También se tiene el siguiente fragmento de texto donde se devuelve un patrón en la posición que indica cada valor por renglón. Por ejemplo Pos1 = 34, si se verifica el primer renglón y tomando en cuenta que el motif tiene longitud de ocho caracteres, se obtiene la cadena GTCAGCTG, para seguir con el ejemplo se tiene que la Pos2 = 45, verificando el segundo renglón se obtiene GCAGTACG.

Continuado con la obtención de valores se tiene.