We used a divide-and-conquer algorithm to recursively solve the two-dimensional problem of protein folding of an HP sequence with the maximum number of H-H contacts. We derived both lower and upper bounds for the algorithmic complexity by using the newly introduced concept of multi-directional width-bounded geometric separator. We proved that for a grid graph G with n grid points P, there exists a balanced separator A subseteq P$ such that A has less than or equal to 1.02074 sqrt{n} points, and G-A has two disconnected subgraphs with less than or equal to {2over 3}n nodes on each subgraph. We also derive a 0.7555sqrt {n} lower bound for our balanced separator. Based on our multidirectional width-bounded geometric separator, we found that there is an O(n^{5.563sqrt{n}}) time algorithm for the 2D protein folding problem in the HP model. We also extended the upper bound results to rectangular and triangular lattices.

Orientador: Aguinaldo Robinson de Souza / Banca: Julio Ricardo Sambrano / Banca: Antonio Caliri / O Programa de Pós-Graduação em Ciência e Tecnologia de Materiais, PosMat, tem caráter institucional e integra as atividades de pesquisa em materiais de diversos campi da Unesp / Resumo: Compreender como a sequencia de aminoácidos de uma proteína determina a sua funcionalidade biológica é de grande importância conceitual e prática como, por exemplo, no projeto de novas drogas. As proteínas consistem em polipeptídios composta por 20 L- aminoácidos diferentes, (formados pelos átomos de hidrogênio, carbono, nitrogênio e oxigênio) ligados por ligações peptídicas. O que torna as proteínas diferentes não é o número de aminoácidos, mas a sequencia deles na cadeia polipeptídica. No presente trabalho, apresentamos uma simulação computacional, com modelo simples, para a enumeração exata de todas as conformações possíveis em uma rede de todas as conformações possíveis em uma rede quadrada para n = 1 a 17 monômeros. Resultados mostram que 2.155.667 conformações diferentes são possíveis. Neste trabalho, confirmamos estes resultados e atribuímos aos sítios da rede quadrada os monômetros no modelo que foram usados para computar o número de contatos entre os monômeros, distribuição da energia configuracional, distância em relação a frequencia relativa de todas as conformações, contato topológico de longo alcance, aplicamos e comparamos os resultados das simulações do modelo com sequencia de Epitopos. / Abstract: The understanding of how the amino acids sequence determine the protein biological funtionality is one of the most practical and conceptual challenge as, for example, in the development of new drugs. The protein molecule consist of a long chain of polupeptides composed of 20 different amino acids (essentially formed by carbon, oxygen, nitrogen, and hydrogen atoms) linked together by peptide chemical bonds. What makes proteins different is not the number of amino acids in the chain but the amino acid sequence along the chain. In the present a computer simulation of a simple protein model, using the techinique of exact enumeration over all the possible conformations in the square lallice to a sequence of n = 1 to 17 monomers. The results indicate that we can found 2.155.1667 different possible conformations. We present the results for the Cartesian coordinates of all the monomers along the chain and computed the monomer-monomer contacts, the configurational energy, the long-range topological contact and a possible application of the HP model for a variety of epitopes sequences. / Mestre

Made available in DSpace on 2014-06-11T19:30:19Z (GMT). No. of bitstreams: 0 Previous issue date: 2009-08-03Bitstream added on 2014-06-13T18:40:21Z : No. of bitstreams: 1 silva_pm_me_bauru.pdf: 730929 bytes, checksum: 5e701d75d10b9d8e43b1b946295d7e3f (MD5) / Compreender como a sequencia de aminoácidos de uma proteína determina a sua funcionalidade biológica é de grande importância conceitual e prática como, por exemplo, no projeto de novas drogas. As proteínas consistem em polipeptídios composta por 20 L- aminoácidos diferentes, (formados pelos átomos de hidrogênio, carbono, nitrogênio e oxigênio) ligados por ligações peptídicas. O que torna as proteínas diferentes não é o número de aminoácidos, mas a sequencia deles na cadeia polipeptídica. No presente trabalho, apresentamos uma simulação computacional, com modelo simples, para a enumeração exata de todas as conformações possíveis em uma rede de todas as conformações possíveis em uma rede quadrada para n = 1 a 17 monômeros. Resultados mostram que 2.155.667 conformações diferentes são possíveis. Neste trabalho, confirmamos estes resultados e atribuímos aos sítios da rede quadrada os monômetros no modelo que foram usados para computar o número de contatos entre os monômeros, distribuição da energia configuracional, distância em relação a frequencia relativa de todas as conformações, contato topológico de longo alcance, aplicamos e comparamos os resultados das simulações do modelo com sequencia de Epitopos. / The understanding of how the amino acids sequence determine the protein biological funtionality is one of the most practical and conceptual challenge as, for example, in the development of new drugs. The protein molecule consist of a long chain of polupeptides composed of 20 different amino acids (essentially formed by carbon, oxygen, nitrogen, and hydrogen atoms) linked together by peptide chemical bonds. What makes proteins different is not the number of amino acids in the chain but the amino acid sequence along the chain. In the present a computer simulation of a simple protein model, using the techinique of exact enumeration over all the possible conformations in the square lallice to a sequence of n = 1 to 17 monomers. The results indicate that we can found 2.155.1667 different possible conformations. We present the results for the Cartesian coordinates of all the monomers along the chain and computed the monomer-monomer contacts, the configurational energy, the long-range topological contact and a possible application of the HP model for a variety of epitopes sequences.

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

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