A predição de estruturas de proteínas (Protein Structure Prediction PSP) é um problema computacionalmente complexo. Para tratar esse problema, modelos simplificados de proteínas, como o Modelo HP, têm sido empregados para representar as conformações e Algoritmos Evolutivos (AEs) são utilizados na busca por soluções adequadas para PSP. Entretanto, abordagens utilizando AEs muitas vezes não tratam adequadamente as soluções geradas, prejudicando o desempenho da busca. Neste trabalho, é apresentada uma formulação multiobjetivo para PSP em Modelo HP, de modo a avaliar de forma mais robusta as conformações produzidas combinando uma avaliação baseada no número de contatos hidrofóbicos com a distância entre os monômeros. Foi adotado o Algoritmo Evolutivo Multiobjetivo em Tabelas (AEMT) a fim de otimizar essas métricas. O algoritmo pode adequadamente explorar o espaço de busca com pequeno número de indivíduos. Como consequência, o total de avaliações da função objetivo é significativamente reduzido, gerando um método para PSP utilizando Modelo HP mais rápido e robusto / Protein Structure Prediction (PSP) is a computationally complex problem. To overcome this drawback, simplified models of protein structures, such as the HP Model, together with Evolutionary Algorithms (EAs) have been investigated in order to find appropriate solutions for PSP. EAs with the HP Model have shown interesting results, however, they do not adequately evaluate potential solutions by using only the usual metric of hydrophobic contacts, hamming the performance of the algorithm. In this work, we present a multi-objective approach for PSP using HP Model that performs a better evaluation of the solutions by combining the evaluation based on the number of hydrophobic contacts with the distance among the hydrophobic amino acids. We employ a Multi-objective Evolutionary Algorithm based on Sub-population Tables (MEAT) to deal with these two metrics. MEAT can adequately explore the search space with relatively low number of individuals. As a consequence, the total assessments of the objective function is significantly reduced generating a method for PSP using HP Model that is faster and more robust

This dissertation concerns the study and prediction of loops in protein structures. Proteins perform crucial functions in living organisms. Despite their importance, we are currently unable to predict their three dimensional structure accurately. Loops are segments that connect regular secondary structures of proteins. They tend to be located on the surface of proteins and often interact with other biological agents. As loops are generally subject to more frequent mutations than the rest of the protein, their sequences and structural conformations can vary significantly even within the same protein family. Although homology modelling is the most accurate computational method for protein structure prediction, difficulties still arise in predicting protein loops. Protein loop structure prediction is therefore a bottleneck in solving the protein structure prediction problem. Reflecting on the success of homology modelling, I implement an improved version of a database search method, FREAD. I show how sequence similarity as quantified by environment specific substitution scores can be used to significantly improve loop prediction. FREAD performs appreciably better for an identifiable subset of loops (two thirds of shorter loops and half of the longer loops tested) than ab initio methods; FREAD's predictive ability is length independent. In general, it produces results within 2Å root mean square deviation (RMSD) from the native conformations, compared to an average of over 10Å for loop length 20 for any of the other tested ab initio methods. I then examine FREAD’s predictive ability on a specific type of loops called complementarity determining regions (CDRs) in antibodies. CDRs consist of six hypervariable loops and form the majority of the antigen binding site. I examine CDR loop structure prediction as a general case of loop structure prediction problem. FREAD achieves accuracy similar to specific CDR predictors. However, it fails to accurately predict CDR-H3, which is known to be the most challenging CDR. Various FREAD versions including FREAD with contact information (ConFREAD) are examined. The FREAD variants improve predictions for CDR-H3 on homology models and docked structures. Lastly, I focus on the local properties of protein loops and demonstrate that the protein loop structure prediction problem is a local protein folding problem. The end-to-end distance of loops (loop span) follows a distinctive frequency distribution, regardless of secondary structure elements connected or the number of residues in the loop. I show that the loop span distribution follows a Maxwell-Boltzmann distribution. Based on my research, I propose future directions in protein loop structure prediction including estimating experimentally undetermined local structures using FREAD, multiple loop structure prediction using contact information and a novel ab initio method which makes use of loop stretch.

A predição de estruturas de proteínas é um campo de pesquisa que busca simular o enovelamento de cadeias de aminoácidos de forma a descobrir as funções das proteínas na natureza, um processo altamente dispendioso por meio de métodos in vivo. Inserida no contexto da Bioinformática, é uma das tarefas mais computacionalmente custosas e desafiadoras da atualidade. Devido à complexidade, muitas pesquisas se utilizam de gateways científicos para disponibilização de ferramentas de execução e análise desses experimentos, aliado ao uso de workflows científicos para organização de tarefas e disponibilização de informações. No entanto, esses gateways podem enfrentar gargalos de desempenho e falhas estruturais, produzindo resultados de baixa qualidade. Para atuar nesse contexto multifacetado e oferecer alternativas para algumas das limitações, esta tese propõe uma arquitetura modular baseada nos conceitos de Service Oriented Architecture (SOA) para oferta de recursos computacionais em gateways científicos, com foco nos experimentos de Protein Structure Prediction (PSP). A Arquitetura Modular Distribuída para auxílio à Predição de Estruturas de Proteínas (MDAPSP) é descrita conceitualmente e validada em um modelo de simulação computacional, no qual se pode identificar suas capacidades, detalhar o funcionamento de seus módulos e destacar seu potencial. A avaliação experimental demonstra a qualidade dos algoritmos propostos, ampliando a capacidade de atendimento de um gateway científico, reduzindo o tempo necessário para experimentos de predição e lançando as bases para o protótipo de uma arquitetura funcional. Os módulos desenvolvidos alcançam boa capacidade de otimização de experimentos de PSP em ambientes distribuídos e constituem uma novidade no modelo de provisionamento de recursos para gateways científicos. / PSP is a scientific process that simulates the folding of amino acid chains to discover the function of a protein in live organisms, considering that its an expensive process to be done by in vivo methods. PSP is a computationally demanding and challenging effort in the Bioinformatics stateof- the-art. Many works use scientific gateways to provide tools for execution and analysis of such experiments, along with scientific workflows to organize tasks and to share information. However, these gateways can suffer performance bottlenecks and structural failures, producing low quality results. With the goal of offering alternatives to some of the limitations and considering the complexity of the topics involved, this thesis proposes a modular architecture based on SOA concepts to provide computing resources to scientific gateways, with focus on PSP experiments. The Modular Distributed Architecture to support Protein Structure Prediction (MDAPSP) is described conceptually and validated in a computer simulation model that explain its capabilities, detail the modules operation and highlight its potential. The performance evaluation presents the quality of the proposed algorithms, a reduction of response time in PSP experiments and prove the benefits of the novel algorithms, establishing the basis for a prototype. The new modules can optmize the PSP experiments in distributed environments and are a innovation in the resource provisioning model for scientific gateways.

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 / 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

Este trabalho foca o desenvolvimento de algoritmos de otimização para o problema de PSP puramente ab initio. Algoritmos que melhor exploram o espaço de potencial de soluções podem, em geral, encontrar melhores soluções. Esses algoritmos podem beneficiar ambas abordagens de PSP, tanto o modelo ab initio quanto os baseados em conhecimento a priori. Pesquisadores tem mostrado que Algoritmos Evolutivos Multiobjetivo podem contribuir significativamente no contexto do problema de PSP puramente ab initio. Neste contexto, esta pesquisa investiga o Algoritmo Evolutivo Multiobjetivo baseado em Tabelas aplicado ao PSP puramente ab initio, que apresenta interessantes resultados para proteínas relativamente simples. Por exemplo, um desafio para o PSP puramente ab initio é a predição de estruturas com folhas-. Para trabalhar com tais proteínas, foi desenvolvido procedimentos computacionalmente eficientes para estimar energias de ligação de hidrogênio e solvatação. Em geral, estas não são consideradas no PSP por abordagens que combinam métodos de otimização e conhecimento a priori. Considerando somente van der Waals e eletrostática, as duas energias de interação que mais contribuem para a definição da estrutura de uma proteína, com as energias de ligação de hidrogênio e solvatação, o problema de PSP tem quatro objetivos. Problemas combinatórios (tais como o PSP), com mais de três objetivos, geralmente requerem métodos específicos capazes de lidar com muitos critérios. Para resolver essa limitação, este trabalho propõe um novo método para a otimização dos muitos objetivos, chamado Algoritmo Evolutivo Multiobjetivo com Muitas Tabelas (AEMMT). Esse método executa uma amostragem mais adequada do espaço de funções objetivo e, portanto, pode mapear melhor as regiões promissoras deste espaço. A capacidade de lidar com muitos objetivos capacita o AEMMT a utilizar melhor a informação oriunda das energias de solvatação e de ligação de hidrogênio, e então predizer estruturas com folhas- e algumas proteínas relativamente mais complexas. Do ponto de vista computacional, o AEMMT é um novo método que lida com muitos objetivos (mais de dez) encontrando soluções relevantes / This work focuses on the development of optimization algorithms for the purely ab initio Protein Structure Prediction (PSP) problem. Algorithms that better explore the space of potential solutions can in general find better solutions. Such algorithms can benefit both ab initio and template-based PSP, that uses priori knowledge. Researches have shown that Multiobjective evolutionary algorithms can contribute significantly in the context of purely ab initio PSP. In this context, this research investigates the Multiobjective Evolutionary Algorithm based on Tables applied to purely ab initio PSP, which has shown interesting results for relatively simple proteins. For example, one challenge for purely ab initio PSP is the prediction of structures with -sheets. To work with such proteins, this research has developed computationally efficient procedures to estimate hydrogen bond and solvation energies. In general, they are not considered by PSP approaches combining optimization methods with priori knowledge. Only by considering van der Waals and electrostatic, the two interaction energies that mostly contribute to defining a protein structure, and the hydrogen bond and solvation energies, the PSP problem has four objectives. Combinatorial problems (such as the PSP) with more than three objective usually require specific methods capable of dealing with many goals. To address this limitation, we propose a new method for many objective optimization, called Multiobjective Evolutionary Algorithm with Many Tables (MEAMT). This method performs a more adequate sampling of the space of objective functions and, therefore, can better map the promising regions of this space. The ability of dealing with many objectives enables the MEANT to better use information generated by solvation and hydrogen bond energies, and then predict structures with -sheets and some relatively complex proteins. From the computational point of view, the MEAMT is a new method for dealing with many objectives (more than ten) finding relevant solutions

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 / 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

As proteínas são moléculas que desempenham funções essenciais para a vida. Para entender a função de uma proteína é preciso conhecer sua estrutura tridimensional. No entanto, encontrar a estrutura da proteína pode ser um processo caro e demorado, exigindo profissionais altamente qualificados. Neste sentido, métodos computacionais têm sido investigados buscando predizer a estrutura de uma proteína a partir de uma sequência de aminoácidos. Em geral, tais métodos computacionais utilizam conhecimentos de estruturas de proteínas já determinadas por métodos experimentais, para tentar predizer proteínas com estrutura desconhecida. Embora métodos computacionais como, por exemplo, o Rosetta, I-Tasser e Quark tenham apresentado sucesso em suas predições, são apenas capazes de produzir estruturas significativamente semelhantes às já determinadas experimentalmente. Com isso, por utilizarem conhecimento a priori de outras estruturas pode haver certa tendência em suas predições. Buscando elaborar um algoritmo eficiente para Predição de Estruturas de Proteínas livre de tendência foi desenvolvido um Algoritmo de Estimação de Distribuição (EDA) específico para esse problema, com modelagens full-atom e algoritmos ab initio. O fato do algoritmo proposto ser ab initio é mais interessante para aplicação envolvendo proteínas com baixa similaridade, com relação às estruturas já conhecidas. Três tipos de modelos probabilísticos foram desenvolvidos: univariado, bivariado e hierárquico. O univariado trata o aspecto de multi-modalidade de uma variável, o bivariado trata os ângulos diedrais (Φ Ψ) de um mesmo aminoácido como variáveis correlacionadas. O hierárquico divide o problema em subproblemas e tenta tratá-los separadamente. Os resultados desta pesquisa mostraram que é possível obter melhores resultados quando considerado a relação bivariada (Φ Ψ). O hierárquico também mostrou melhorias nos resultados obtidos, principalmente para proteínas com mais de 50 resíduos. Além disso, foi realiza uma comparação com algumas heurísticas da literatura, como: Busca Aleatória, Monte Carlo, Algoritmo Genético e Evolução Diferencial. Os resultados mostraram que mesmo uma metaheurística pouco eficiente, como a Busca Aleatória, pode encontrar a solução correta, porém utilizando muito conhecimento a priori (predição que pode ser tendenciosa). Por outro lado, o algoritmo proposto neste trabalho foi capaz de obter a estrutura da proteína esperada sem utilizar conhecimento a priori, caracterizando uma predição puramente ab initio (livre de tendência). / Proteins are molecules that perform critical roles in the living organism and they are essential for their lifes. To understand the function of a protein, its 3D structure should be known. However, to find the protein structure is an expensive and a time-consuming task, requiring highly skilled professionals. Aiming to overcome such a limitation, computational methods for Protein Structure Prediction (PSP) have been investigated, in order to predict the protein structure from its amino acid sequence. Most of computational methods require knowledge from already determined structures from experimental methods in order to predict an unknown protein. Although computational methods such as Rosetta, I-Tasser and Quark have showed success in their predictions, they are only capable to predict quite similar structures to already known proteins obtained experimentally. The use of such a prior knowledge in the predictions of Rosetta, I-Tasser and Quark may lead to biased predictions. In order to develop a computational algorithm for PSP free of bias, we developed an Estimation of Distribution Algorithm applied to PSP with full-atom and ab initio model. A computational algorithm with ab initio model is mainly interesting when dealing with proteins with low similarity with the known proteins. In this work, we developed an Estimation of Distribution Algorithm with three probabilistic models: univariate, bivariate and hierarchical. The univariate deals with multi-modality of the distribution of the data of a single variable. The bivariate treats the dihedral angles (Proteins are molecules that perform critical roles in the living organism and they are essential for their lifes. To understand the function of a protein, its 3D structure should be known. However, to find the protein structure is an expensive and a time-consuming task, requiring highly skilled professionals. Aiming to overcome such a limitation, computational methods for Protein Structure Prediction (PSP) have been investigated, in order to predict the protein structure from its amino acid sequence. Most of computational methods require knowledge from already determined structures from experimental methods in order to predict an unknown protein. Although computational methods such as Rosetta, I-Tasser and Quark have showed success in their predictions, they are only capable to predict quite similar structures to already known proteins obtained experimentally. The use of such a prior knowledge in the predictions of Rosetta, I-Tasser and Quark may lead to biased predictions. In order to develop a computational algorithm for PSP free of bias, we developed an Estimation of Distribution Algorithm applied to PSP with full-atom and ab initio model. A computational algorithm with ab initio model is mainly interesting when dealing with proteins with low similarity with the known proteins. In this work, we developed an Estimation of Distribution Algorithm with three probabilistic models: univariate, bivariate and hierarchical. The univariate deals with multi-modality of the distribution of the data of a single variable. The bivariate treats the dihedral angles (Φ Ψ) within an amino acid as correlated variables. The hierarchical approach splits the original problem into subproblems and attempts to treat these problems in a separated manner. The experiments show that, indeed, it is possible to achieve better results when modeling the correlation (Φ Ψ). The hierarchical model also showed that is possible to improve the quality of results, mainly for proteins above 50 residues. Besides, we compared our proposed techniques among other metaheuristics from literatures such as: Random Walk, Monte Carlo, Genetic Algorithm and Differential Evolution. The results show that even a less efficient metaheuristic such as Random Walk managed to find the correct structure, however using many prior knowledge (prediction that may be biased). On the other hand, our proposed EDA for PSP was able to find the correct structure with no prior knowledge at all, so we can call this prediction as pure ab initio (biased-free).

Currently, one of the main research problems in Structural Bioinformatics is associated to the study and prediction of the 3-D structure of proteins. The 1990’s GENOME projects resulted in a large increase in the number of protein sequences. However, the number of identified 3-D protein structures have not followed the same growth trend. The number of protein sequences is much higher than the number of known 3-D structures. Many computational methodologies, systems and algorithms have been proposed to address the protein structure prediction problem. However, the problem still remains challenging because of the complexity and high dimensionality of a protein conformational search space. This work presents a new computational strategy for the 3-D protein structure prediction problem. A first principle strategy which uses database information for the prediction of the 3-D structure of polypeptides was developed. The proposed technique manipulates structural information from the PDB in order to generate torsion angles intervals. Torsion angles intervals are used as input to a genetic algorithm with a local-search operator in order to search the protein conformational space and predict its 3-D structure. Results show that the 3-D structures obtained by the proposed method were topologically comparable to their correspondent experimental structure.

Este trabalho foca o desenvolvimento de algoritmos de otimização para o problema de PSP puramente ab initio. Algoritmos que melhor exploram o espaço de potencial de soluções podem, em geral, encontrar melhores soluções. Esses algoritmos podem beneficiar ambas abordagens de PSP, tanto o modelo ab initio quanto os baseados em conhecimento a priori. Pesquisadores tem mostrado que Algoritmos Evolutivos Multiobjetivo podem contribuir significativamente no contexto do problema de PSP puramente ab initio. Neste contexto, esta pesquisa investiga o Algoritmo Evolutivo Multiobjetivo baseado em Tabelas aplicado ao PSP puramente ab initio, que apresenta interessantes resultados para proteínas relativamente simples. Por exemplo, um desafio para o PSP puramente ab initio é a predição de estruturas com folhas-. Para trabalhar com tais proteínas, foi desenvolvido procedimentos computacionalmente eficientes para estimar energias de ligação de hidrogênio e solvatação. Em geral, estas não são consideradas no PSP por abordagens que combinam métodos de otimização e conhecimento a priori. Considerando somente van der Waals e eletrostática, as duas energias de interação que mais contribuem para a definição da estrutura de uma proteína, com as energias de ligação de hidrogênio e solvatação, o problema de PSP tem quatro objetivos. Problemas combinatórios (tais como o PSP), com mais de três objetivos, geralmente requerem métodos específicos capazes de lidar com muitos critérios. Para resolver essa limitação, este trabalho propõe um novo método para a otimização dos muitos objetivos, chamado Algoritmo Evolutivo Multiobjetivo com Muitas Tabelas (AEMMT). Esse método executa uma amostragem mais adequada do espaço de funções objetivo e, portanto, pode mapear melhor as regiões promissoras deste espaço. A capacidade de lidar com muitos objetivos capacita o AEMMT a utilizar melhor a informação oriunda das energias de solvatação e de ligação de hidrogênio, e então predizer estruturas com folhas- e algumas proteínas relativamente mais complexas. Do ponto de vista computacional, o AEMMT é um novo método que lida com muitos objetivos (mais de dez) encontrando soluções relevantes / This work focuses on the development of optimization algorithms for the purely ab initio Protein Structure Prediction (PSP) problem. Algorithms that better explore the space of potential solutions can in general find better solutions. Such algorithms can benefit both ab initio and template-based PSP, that uses priori knowledge. Researches have shown that Multiobjective evolutionary algorithms can contribute significantly in the context of purely ab initio PSP. In this context, this research investigates the Multiobjective Evolutionary Algorithm based on Tables applied to purely ab initio PSP, which has shown interesting results for relatively simple proteins. For example, one challenge for purely ab initio PSP is the prediction of structures with -sheets. To work with such proteins, this research has developed computationally efficient procedures to estimate hydrogen bond and solvation energies. In general, they are not considered by PSP approaches combining optimization methods with priori knowledge. Only by considering van der Waals and electrostatic, the two interaction energies that mostly contribute to defining a protein structure, and the hydrogen bond and solvation energies, the PSP problem has four objectives. Combinatorial problems (such as the PSP) with more than three objective usually require specific methods capable of dealing with many goals. To address this limitation, we propose a new method for many objective optimization, called Multiobjective Evolutionary Algorithm with Many Tables (MEAMT). This method performs a more adequate sampling of the space of objective functions and, therefore, can better map the promising regions of this space. The ability of dealing with many objectives enables the MEANT to better use information generated by solvation and hydrogen bond energies, and then predict structures with -sheets and some relatively complex proteins. From the computational point of view, the MEAMT is a new method for dealing with many objectives (more than ten) finding relevant solutions

Submitted by PPG Ci?ncia da Computa??o (ppgcc@pucrs.br) on 2018-09-03T14:00:58Z No. of bitstreams: 1 RAFAEL CAUDURO OLIVEIRA MACEDO_DIS.pdf: 6178948 bytes, checksum: 6ed3599e31f122e78b11b322a8c0ac06 (MD5) / Approved for entry into archive by Sheila Dias (sheila.dias@pucrs.br) on 2018-09-04T12:17:04Z (GMT) No. of bitstreams: 1 RAFAEL CAUDURO OLIVEIRA MACEDO_DIS.pdf: 6178948 bytes, checksum: 6ed3599e31f122e78b11b322a8c0ac06 (MD5) / Made available in DSpace on 2018-09-04T12:47:15Z (GMT). No. of bitstreams: 1 RAFAEL CAUDURO OLIVEIRA MACEDO_DIS.pdf: 6178948 bytes, checksum: 6ed3599e31f122e78b11b322a8c0ac06 (MD5) Previous issue date: 2017-08-30 / Prote?nas executam um papel vital em todos os seres vivos, mediando uma s?rie de processos necess?rios para a vida. Apesar de existirem maneiras de determinar a composi??o dessas mol?culas, ainda falta-nos conhecimentos suficiente para determinar de uma maneira r?pida e barata a sua estrutura 3D, que desempenha um papel importante na suas fun??es. Um dos principais m?todos computacionais aplicados ao estudo das prote?nas e o seu processo de enovelamento, o qual determina a sua estrutura, ? Din?mica Molecular. Um aprimoramento deste m?todo, conhecido como Replica Exchange Molecular Dynamics (ou REMD), ? capaz de produzir resultados muito melhores, com o rev?s de significativamente aumentar o seu custo computacional e gerar um volume muito maior de dados. Esta disserta??o apresenta um novo m?todo de otimiza??o deste m?todo, intitulado Filtragem de Dados Anal?ticos, que tem como objetivo otimizar a an?lise p?s-simula??o filtrando as estruturas preditas insatisfat?rias atrav?s do uso de m?tricas de qualidade absolutas. A metodologia proposta tem o potencial de operar em conjunto com outras abordagens de otimiza??o e tamb?m cobrir uma ?rea ainda n?o abordada por elas. Adiante, a ferramenta SnapFi ? apresentada, a qual foi designada especialmente para o prop?sito de filtrar estruturas preditas insatisfat?rias e ainda operar em conjunto com as diferentes abordagens de otimiza??o do m?todo REMD. Um estudo foi ent?o conduzido sobre um conjunto teste de simula??es REMD de predi??o de estruturas de prote?nas afim de elucidar uma s?ries de hip?teses formuladas sobre o impacto das diferentes temperaturas na qualidade final do conjunto de estruturas preditas do processo REMD, a efici?ncia das diferentes m?tricas de qualidade absolutas e uma poss?vel configura??o de filtragem que utiliza essas m?tricas. Foi observado que as temperaturas mais altas do m?todo REMD para predi??o de estruturas de prote?nas podem ser descartadas de forma segura da an?lise posterior ao seu t?rmino e tamb?m que as m?tricas de qualidade absolutas possuem uma alta vari?ncia (em termos de qualidade) entre diferentes simula??es de predi??es de estruturas de prote?nas. Al?m disso, foi observado que diferentes configura??es de filtragem que utilize tais m?tricas carrega consigo esta vari?ncia. / Proteins perform a vital role in all living beings, mediating a series of processes necessary to life. Although we have ways to determine the composition of such molecules, we lack sufficient knowledge regarding the determination of their 3D structure in a cheap and fast manner, which plays an important role in their functions. One of the main computational methods applied to the study of proteins and their folding process, which determine its structure, is Molecular Dynamics. An enhancement of this method, known as Replica-Exchange Molecular Dynamics (or REMD) is capable of producing much better results, at the expense of a significant increase in computational costs and volume of raw data generated. This dissertation presents a novel optimization for this method, titled Analytical Data Filtering, which aims to optimize post-simulation analysis by filtering unsatisfactory predicted structures via the use of different absolute quality metrics. The proposed methodology has the potential of working together with other optimization approaches as well as covering an area still untouched at large by them to the best of the author knowledge. Further on, the SnapFi tool is presented, a tool designed specially for the purpose of filtering unsatisfactory structure predictions and also being able to work with the different optimization approaches of the Replica-Exchange Molecular Dynamics method. A study was then conducted on a test dataset of REMD protein structure prediction simulations aiming to elucidate a series of formulated hypothesis regarding the impact of the different temperatures of the REMD process in the final quality of the predicted structures, the efficiency of the different absolute quality metrics and a possible filtering configuration that take advantage of such metrics. It was observed that high temperatures may be safely discarded from post-simulation analysis of REMD protein structure prediction simulations, that absolute quality metrics posses a high variance of efficiency (regarding quality terms) between different protein structure prediction simulations and that different filtering configurations composed of such quality metrics carry on this inconvenient variance.