Por favor, use este identificador para citar o enlazar este ítem:
http://inaoe.repositorioinstitucional.mx/jspui/handle/1009/446| Métodos basados en optimización por colonia de hormigas aplicados al modelo hidrofóbico-polar del plegamiento de proteínas | |
| MARGARITA ROSETE MONTERO | |
| JESUS ANTONIO GONZALEZ BERNAL EDUARDO FRANCISCO MORALES MANZANARES | |
| Acceso Abierto | |
| Atribución-NoComercial-SinDerivadas | |
| Optimization Artificial intelligence Biochemistry | |
| In many knowledge fields different complex combinatorial optimization problems
arise, whose solution by computational means results very attractive. One such
problem in biophysics and biochemistry is the protein folding problem (PFP). This
problem consists, in a general way, in predicting the tridimensional structure of a
protein from its lineal amino acids chain. Proteins play a predominant role in the
biological functions of living organisms, and because of functions of proteins are
determined precisely by their tridimensional structure, studying the PFP is of high
importance. Throughout the years, several algorithms have been proposed to solve
this problem. Among them are the Monte Carlo and simulated annealing methods,
evolutionary algorithms and, in recent years, ant colony optimization (ACO). ACO
has shown to be a powerful metaheuristic able to solve combinatorial optimization
problems. However, any of the algorithms presented in the literature has shown to be
completely superior to others. For that reason, the development of new proposals that
reduce the execution time and find optimal solutions is very important. In this thesis
several algorithms based in ACO and oriented to the study of PFP are proposed. The
first two algorithms differ between them in two principal components: the heuristic
function and the pheromone actualization scheme. From different strategies to
combine the information given by these two individual algorithms, three versions of
hybrid-ACO algorithms are presented. Two new techniques that improve the global
performance of the algorithms are also presented: a technique to avoid stagnation in
algorithms and a new method to solve overlapping problem. Every algorithm was
evaluated using standard instances of the HP square and triangular model, which are
simplifications of the original PFP. Compared with other algorithms in the literature,
in general, the algorithms presented in this thesis showed a good performance in
terms of the quality of solutions and the execution time. En diversos campos del conocimiento se presentan problemas combinatorios de optimización complejos cuya resolución por medios computacionales resulta muy atractiva. Un problema dentro de la biofísica y la bioquímica es el problema del plegamiento de proteínas (PFP, por sus siglas en inglés). Este problema consiste, de manera general, en predecir la estructura tridimensional de una proteína a partir de su cadena lineal de aminoácidos. Las proteínas desempeñan un papel fundamental en las funciones de los seres vivos, y debido a que la función de una proteína está determinada por su estructura tridimensional, el estudio del PFP es muy importante. A través de los años se han propuesto varios algoritmos para intentar resolver este problema. Entre ellos encontramos métodos de Monte Carlo y recocido simulado, algoritmos genéticos y, en años recientes, optimización por colonia de hormigas (ACO), la cual se ha mostrado como una metaheurística poderosa para resolver problemas combinatorios de optimización. Si embargo, ninguno de los algoritmos en la literatura se ha mostrado completamente superior a los otros, por lo que el desarrollo de nuevas propuestas que reduzcan el tiempo de ejecución y encuentren soluciones óptimas es de gran importancia. En esta tesis se proponen varios algoritmos basados en ACO enfocados al PFP. Los dos primeros varían en dos componentes: la función heurística y el esquema de actualización de feromona. A partir de estrategias diferentes para combinar la información proporcionada por estos dos algoritmos individuales se presentan tres versiones de algoritmos ACO híbridos. Se presentan también dos nuevas técnicas que mejoran el desempeño general de los algoritmos: una técnica para evitar el estancamiento en los algoritmos y otra técnica para resolver el problema de traslape en la construcción de soluciones. Todos los algoritmos fueron evaluados utilizando secuencias estándar del modelo HP cuadrado y triangular 2D, los cuales son una simplificación del PFP original. Comparados con otros algoritmos en la literatura, los algoritmos propuestos mostraron buenos resultados en cuanto a la calidad de las soluciones encontradas y a su tiempo de ejecución. | |
| Instituto Nacional de Astrofísica, Óptica y Electrónica | |
| 2009-02 | |
| Tesis de maestría | |
| Español | |
| Estudiantes Investigadores Público en general | |
| Rosete-Montero M. | |
| CIENCIA DE LOS ORDENADORES | |
| Versión aceptada | |
| acceptedVersion - Versión aceptada | |
| Aparece en las colecciones: | Maestría en Ciencias Computacionales |
Cargar archivos:
| Fichero | Tamaño | Formato | |
|---|---|---|---|
| RoseteMM.pdf | 1.7 MB | Adobe PDF | Visualizar/Abrir |