info:eu-repo/semantics/masterThesis
Métodos basados en optimización por colonia de hormigas aplicados al modelo hidrofóbico-polar del plegamiento de proteínas
Autor
MARGARITA ROSETE MONTERO
Resumen
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.
Materias
Ítems relacionados
Mostrando ítems relacionados por Título, autor o materia.
-
Compendio de innovaciones socioambientales en la frontera sur de México
Adriana Quiroga -
Caminar el cafetal: perspectivas socioambientales del café y su gente
Eduardo Bello Baltazar; Lorena Soto_Pinto; Graciela Huerta_Palacios; Jaime Gomez -
Material de empaque para biofiltración con base en poliuretano modificado con almidón, metodos para la manufactura del mismo y sistema de biofiltración
OLGA BRIGIDA GUTIERREZ ACOSTA; VLADIMIR ALONSO ESCOBAR BARRIOS; SONIA LORENA ARRIAGA GARCIA