Master's Dissertation
DOI
https://doi.org/10.11606/D.55.2010.tde-20052010-110415
Document
Author
Full name
Daniel Rodrigo Ferraz Bonetti
E-mail
Institute/School/College
Knowledge Area
Date of Defense
Published
São Carlos, 2010
Supervisor
Committee
Delbem, Alexandre Cláudio Botazzo (President)
Souza, Paulo Sergio Lopes de
Travieso, Gonzalo
Title in Portuguese
Aumento da eficiência do cálculo da energia de van der Waals em algoritmos genéticos para predição de estruturas de proteínas
Keywords in Portuguese
ab initio
Algoritmos genéticos
Predição de estruturas de proteínas
Programação paralela
Van de Waals
Abstract in Portuguese
As proteínas são moléculas presentes nos seres vivos e essenciais para a vida deles. Para entender a função de uma proteína, devese conhecer sua estrutura tridimensional (o posicionamento correto de todos os seus átomos no espaço). A partir da estrutura de uma proteína vital de um organismo causador de uma doença é possível desenvolver fármacos para o tratamento da doença. Para encontrar a estrutura de uma proteína, métodos biofísicos, como Cristalografia de Raio-X e Ressonância Nuclear Magnética têm sido empregados. No entanto, o uso desses métodos tem restrições práticas que impedem a determinação de várias estruturas de proteínas. Para contornar essas limitações, métodos computacionais para o problema de predição da estrutura da proteína (PSP, Protein Structure Prediction) têm sido investigados. Várias classes de métodos computacionais têm sido desenvolvidas para o problema de PSP. Entre elas, as abordagens ab initio são muito importantes, pois não utilizam nenhuma informação prévia de outras estruturas de proteínas para fazer o PSP, apenas a sequência de aminoácidos da proteína e o gráfico de Ramachandran são empregados. O PSP ab initio é um problema combinatorial que envolve relativamente grandes instâncias na prática, por exemplo, as proteínas em geral têm centenas ou milhares de variáveis para determinar. Para vencer esse entrave, metaheurísticas como os Algoritmos Genéticos (AGs) têm sido investigados. As soluções geradas por um AG são avaliadas pelo cálculo da energia potencial da proteína. Entre elas, o cálculo da interação da energia de van der Waals é custoso computacionalmente tornando o processo evolutivo do AG muito lento mesmo para proteínas pequenas. Este trabalho investiga técnicas para reduzir significativamente o tempo de execução desse cálculo. Basicamente, foram propostas modificações de técnicas de paralelização utilizando MPI e OpenMP para os algoritmos resultantes. Os resultados mostram que o cálculo pode ser 1.500 vezes mais rápido para proteínas gigantes quando aplicadas as técnicas investigadas neste trabalho
Title in English
Enhance the Van der Waals energy efficiency calculi in genetic algorithms for protein structure prediction
Keywords in English
ab initio
Genetic algorithms
Parallel programming
Protein structure prediction
Van de Waals
Abstract in English
Proteins are molecules present in the living organism and essential for their life. To understand the function of a protein, its threedimensional structure (the correct positions of all its atoms in the space) should be known. From the structure of a vital protein of an organism that causes a human disease, it is possible to develop medicines for treatment of the disease. To find a protein structure, biophysical methods, as Crystallography of X-Ray and Magnetic Nuclear Resonance, have been employed. However, the use of those methods have practical restrictions that impede the determination of several protein structures. Aiming to overcome such limitation, computational methods for the problem of protein structure prediction (PSP) has been investigated. Several classes of computational methods have been developed for PSP. Among them, ab initio approaches are very important since they use no previous information from other protein structure, only the sequence of amino acids of the protein and the Ramachandran graph are employed. The ab initio PSP is a combinatorial problem that involves relatively large instances in practice, i. e. proteins in general have hundreds or thousands of variables to be determined. To deal with such problem, metaheuristics as Genetic Algorithms (GAs) have been investigated. The solutions generated by a GA are evaluated by the calculus of the potencial energies of the protein. Among them, the calculation of the interaction of van der Waals energy is computationally intense making the evolutionary process of a GA very slow even for non-large proteins. This work investigated techniques to significantly reduce the running time for that calculus. Basically, we proposed modifications parallelization of the resultant algorithm using MPI and OpenMP techniques. The results show that such calculus can be 1.500 times faster when applying the techniques investigated in this work for large proteins
WARNING - Viewing this document is conditioned on your acceptance of the following terms of use:
This document is only for private use for research and teaching activities. Reproduction for commercial use is forbidden. This rights cover the whole data about this document as well as its contents. Any uses or copies of this document in whole or in part must include the author's name.
Publishing Date
2010-05-20