Por favor, use este identificador para citar o enlazar este ítem:
http://cicese.repositorioinstitucional.mx/jspui/handle/1007/2204| Un algoritmo evolutivo híbrido para el problema del plegamiento de proteínas bajo el modelo hidrofóbico polar en tres dimensiones A hybrid genetic algorithm for the protein folding problem under the 3D hydrophobic-polar model | |
| Jorge Enrique Luna Taylor | |
| Carlos Alberto Brizuela Rodríguez | |
| Acceso Abierto | |
| Atribución | |
| Bioinformática,Heurística,Proteínas,Algoritmos genéticos,Modelo Monte Carlo | |
| En esta tesis se describe el problema del plegamiento de proteínas el cual representa uno de los retos más importantes dentro de la biología molecular. Debido a que este problema es extremadamente difícil se han propuesto diferentes modelos simplificados para abordarlo. Uno de los modelos más estudiados es el modelo hidrofóbico-polar (HP). A pesar de las simplificaciones que propone el modelo HP, el problema pertenece a la clase NP-difícil, es decir, no se conoce algún método para resolverlo eficientemente. En este trabajo se propone un algoritmo heurístico basado en el método Constrained Hydrophobic Core Construction (CHCC) de Yue y Dill (1995), para tratar este problema. El CHCC es un método exacto que ha arrojado el óptimo para 13 casos tipo del problema con secuencias de hasta 88 residuos. Las fortalezas del CHCC se basan en el concepto de centros-H y en el manejo de restricciones del problema. La fase final del CHCC intenta acomodar los residuos de la secuencia dentro de los centros-H a través de una enumeración exhaustiva, lo cual observamos como una limitante del método para tratar con secuencias más largas. Nuestra propuesta es aprovechar las fortalezas del método CHCC y aplicar un algoritmo heurístico en lugar de la enumeración exhaustiva, para intentar acomodar los residuos de la secuencia dentro de los centros-H calculados. Esta heurística consiste en aplicar un algoritmo genético principal, compuesto a su vez por un algoritmo genético interno para el cálculo de la aptitud de los individuos, y por un algoritmo del tipo Monte Carlo para el manejo de las restricciones del problema. Después de los experimentos realizados se concluye que sí es posible aplicar un algoritmo heurístico para acomodar los residuos de la secuencia dentro de un centro-H óptimo conocido, encontrando con esto el plegado óptimo de la secuencia correspondiente. Finalmente, se comentan algunas ideas para mejorar el método propuesto, así como algunas propuestas de líneas de investigación a futuro. This thesis deal with the protein folding problem which is one of the most challenging problems in molecular biology. Due to the problem complexity, many approximate and simplified models have been proposed to deal with it. One of these models is the one known as hydrophobic-polar (HP) model. Despite the simplifications of this model the problem belongs to the NP-hard class of problems, i.e. problems for which we do not know efficient algorithms to solve any given instance efficiently. In this work a heuristic procedure based on Yuen and Dill’s Constrained Hydrophobic Core Construction (CHCC) method is proposed. The CHCC is an exact method which has generated the optimum for 13 well known instances of up to 88 residues. The positive aspects of this method is the concept of hydrophibic centers and the use of constraints to reduce the search space size. The final stage of this method, once an optimal center is given, tries to lay each H mononer inside the center trough exhaustive enumeration. This constitutes the main drawback of the method when dealing with long sequences. Our main idea is to use the positive aspects of the method and to replace the exhaustive procedure by a heuristics in order to try to lay the whole sequence inside the hydrophobic center. The heuristics is composed by a genetic algorithm, which contains another internal genetic algorithm to compute the fitness function. It also contains a Monte Carlo algorithm to handle some problem-specific constraints. Eperimental results allow us to conclude that it is possible to use the proposed heuristics to correctly lay the residues inside a known optimal hydrophobic center. Finally, some ideas to improve the proposed method as well as some lines for future research are described. | |
| CICESE | |
| 2006 | |
| Tesis de maestría | |
| Español | |
| Luna Taylor, J. E.2006.Un algoritmo evolutivo híbrido para el problema del plegamiento de proteínas bajo el modelo hidrofóbico polar en tres dimensiones.Tesis de Maestría en Ciencias. Centro de Investigación Científica y de Educación Superior de Ensenada, Baja California.xvii, 175 hojas | |
| TECNOLOGÍA DE LOS ORDENADORES | |
| Aparece en las colecciones: | Tesis - Ciencias de la Computación |
Cargar archivos:
| Fichero | Tamaño | Formato | |
|---|---|---|---|
| 173881.pdf | 36.01 MB | Adobe PDF | Visualizar/Abrir |