Por favor, use este identificador para citar o enlazar este ítem:
http://cicese.repositorioinstitucional.mx/jspui/handle/1007/327| Heurísticas para el problema de búsqueda de motivos en secuencias de ADN Heuristics for the motif finding problem | |
| Giovanna Martínez Arellano | |
| Carlos Alberto Brizuela Rodríguez | |
| Acceso Abierto | |
| Atribución | |
| Bioinformática,Algoritmos genéticos | |
| En esta tesis se describe una propuesta de solución para el problema de la búsqueda de motivos en secuencias de ADN. Los motivos son pequeños fragmentos de ADN los cuales están ubicados en la región promotora del gen. Estos fragmentos son sitios de acoplamiento de proteínas llamadas factores de transcripción las cuales permiten que se comience o se inhiba la transcripción de un gen. Debido a la complejidad de este problema, se han propuesto diferentes modelos para poder abordarlo. Uno de los modelos más estudiados es el modelo FM (Fixed number of Mutations) propuesto por Pevzner y Sze (2000). Este modelo consiste en buscar un motivo de longitud l con exactamente d mutaciones el cual se encuentra implantado en T secuencias de ADN cada una con una longitud de N nucleótidos. Junto con este modelo se propone el modelo VM (Variable number of Mutations), en el cual, la única diferencia con respecto a FM es que las d bases son mutadas con cierta probabilidad, teniendo cada ocurrencia del motivo a lo más d mutaciones. En este trabajo se proponen varios algoritmos genéticos para atacar este problema. La motivación de utilizar algoritmos genéticos la da el éxito que tienen éstos en problemas de optimización combinatoria mono- y multi-objetivo. A pesar de que ya hay trabajo en esta área para el problema de búsqueda de motivos, hace falta aún una investigación más profunda en cuanto a la comparación de distintos esquemas de representación de la solución en distintos casos del problema, y en cuanto a cómo mejorarlos. Los algoritmos genéticos propuestos utilizan dos codi?caciones: una basada en las posiciones de inicio y otra basada en un motivo consenso. Con el objetivo de mejorar el desempeño de los algoritmos, se propone incorporar en ellos estrategias de búsqueda local. En los experimentos elaborados, se utilizaron casos arti?ciales del modelo VM (Pevzner y Sze, 2000) y un caso real del sitio de acoplamiento CRP (cyclic-AMP Receptor Protein)(Stormo y Hartzell III, 1989). Resultados experimentales muestran que el algoritmo genético que utiliza una codi?cación basada en motivo es mejor que el algoritmo basado en posiciones de inicio, además hay una mejora importante en cuanto a calidad de solución y tiempos de ejecución del algoritmo genético estándar utilizando las estrategias de búsqueda local. Por otro lado, los resultados también muestran que la combinación de estrategias de búsqueda local fuera del genético pueden encontrar la solución al problema en un menor tiempo, sin embargo, los promedios de calidad de la solución nos muestran que el algoritmo genético que implementa las dos búsquedas combinadas obtiene más soluciones cercanas al óptimo que la búsqueda local por sí sola. In this work we present several enhanced heuristics for the motif ?nding problem. Motifs are small fragments of DNA located in the gene promoter region. These fragments are binding sites for proteins known as transcription factors which are involved in the gene regulation process. Due to the complexity of this problem, many models have been proposed. Pevzner and Sze (2000) studied a precise combinatorial formulation of this problem, called the planted motif problem (FM Model), which is of particular interest because it is a challenging model for commonly used motif-?nding algorithms. The FM model (Fixed number of Mutations) consists on ?nding a motif of length l with exactly d mutations which is implanted in T DNA sequences, each of length N. In addition to this model, Pevzner and Sze proposed the VM model (Variable number of Mutations) where the occurrences of the motif are mutated with certain probability. In this work, several genetic algorithms are proposed to solve this problem. The motivation of using genetic algorithms is given by the success of this strategy with mono- and multi-objective combinatorial optimization problems. Although there are previous works done in this area, studies comparing common encoding schemes and how to improve them are scarce. The genetic algorithms proposed in this work use two encoding schemes: one based on the initial positions of the occurrences in the input sequences and the other based on a consensus motif. In order to improve the average score and computation time of these algorithms, speci?c local search strategies are proposed. For the experiments, arti?cial instances were used, based on the VM model (Pevzner y Sze, 2000), as well as a real instance, the CRP binding site (cyclic-AMP Receptor Protein) (Stormo y Hartzell III, 1989). Experimental results show that an encoding scheme based on a consensus motif is better than the one based on initial positions. Experimental results also show that the memetic algorithm (genetic algorithm with local search strategies) provides better results in terms of average score and computation time compared to the standard genetic algorithm. Combined local search strategies also gave good results comparing to the standard genetic algorithm, nevertheless, the average score shows that the memetic algorithm gives more solutions that are close to the optimal than those obtained from the combined local search strategies. | |
| CICESE | |
| 2007 | |
| Tesis de maestría | |
| Español | |
| Martínez Arellano,G.2007.Heurísticas para el problema de búsqueda de motivos en secuencias de ADN.Tesis de Maestría en Ciencias. Centro de Investigación Científica y de Educación Superior de Ensenada, Baja California.xiii, 89 pp. | |
| CIENCIA DE LOS ORDENADORES | |
| Aparece en las colecciones: | Tesis - Ciencias de la Computación |
Cargar archivos:
| Fichero | Descripción | Tamaño | Formato | |
|---|---|---|---|---|
| 177681.pdf | Versión completa de la tesis | 631.33 kB | Adobe PDF | Visualizar/Abrir |