Threading is a protein structure prediction method that uses a library of template protein structures in the following steps: first the target sequence is matched to the template library and the best template structure is selected, secondly the predicted target structure of the target sequence is modeled by this selected template structure. The deceleration of new folds which are added to the protein data bank promises completion of the template structure library. This thesis uses a new set of template-specific weights to improve the energy function for sequence-to-structure alignment in the template selection step of the threading process. The weights are estimated using least squares methods with the quality of the modelling step in the threading process as the label. These new weights show an average 12.74% improvement in estimating the label. Further family analysis show a correlation between the performance of the new weights to the number of seeds in pFam.

Threading is a protein structure prediction method that uses a library of template protein structures in the following steps: first the target sequence is matched to the template library and the best template structure is selected, secondly the predicted target structure of the target sequence is modeled by this selected template structure. The deceleration of new folds which are added to the protein data bank promises completion of the template structure library. This thesis uses a new set of template-specific weights to improve the energy function for sequence-to-structure alignment in the template selection step of the threading process. The weights are estimated using least squares methods with the quality of the modelling step in the threading process as the label. These new weights show an average 12.74% improvement in estimating the label. Further family analysis show a correlation between the performance of the new weights to the number of seeds in pFam.

This thesis is an investigation of novel mono-ADP-ribosylating toxins. In the current data-rich era, making the leap from sequence data to knowledge is a task that requires an elegant bioinformatics toolset to pinpoint questions. A strategy to expand important protein-family knowledge is required, particularly in cases in which primary sequence identity is low but structural conservation is high. For example, the mono-ADP-ribosylating toxins fit these criteria and several approaches have been used to accelerate the discovery of new family members. A newly developed tactic for detecting remote members of this family -- in which fold recognition dominates -- reduces reliance on sequence similarity and advances us toward a true structure-based protein-family expansion methodology. Chelt, a cholera-like toxin from Vibrio cholerae, and Certhrax, an anthrax-like toxin from Bacillus cereus, are among six new bacterial protein toxins identified and characterized using in silico and cell-based techniques. Medically relevant toxins from Mycobacterium avium and Enterococcus faecalis were also uncovered. Agriculturally relevant toxins were found in Photorhabdus luminescens and Vibrio splendidus. Computer software was used to build models and analyze each new toxin to understand features including: structure, secretion, cell entry, activation, NAD+ substrate binding, intracellular target binding and the reaction mechanism. Yeast-based activity tests have since confirmed activity. Vibrio cholerae produces cholix – a potent protein toxin of particular interest that has diphthamide-specific ADP-ribosyltransferase activity against eukaryotic elongation factor 2. Here we present a 2.1Å apo X-ray structure as well as a 1.8Å X-ray structure of cholix in complex with its natural substrate, nicotinamide adenine dinucleotide (NAD+). Hallmark catalytic residues were substituted and analyzed both for NAD+ binding and ADP-ribosyltransferase activity using a fluorescence-based assay. These new toxins serve as a reference for ongoing inhibitor development for this important class of virulence factors. In addition to using toxins as targets for antivirulence compounds, they can be used to make vaccines and new cancer therapies. / Natural Sciences and Engineering Research Council (CGS-D), Canadian Institutes of Health Research, Cystic Fibrosis Canada, Human Frontier Science Program, Ontario government (OGSST), University of Guelph (Graduate Research Scholarship)

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.

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.

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 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).

Proteine spielen auf der zellulären Ebene eines Organismus eine fundamentale Rolle. Sie sind quasi die „Maschinen“ der Zelle. Ihre Bedeutung wird nicht zuletzt in ihrem Namen deutlich, welcher 1838 erstmals von J. Berzelius verwendet wurde und „das Erste“, „das Wichtigste“ bedeutet. Proteine sind aus Aminosäuren aufgebaute Moleküle. Unter physiologischen Bedingungen besitzen sie eine definierte dreidimensionale Gestalt, welche für ihre biologische Funktion bestimmend ist. Es wird heutzutage davon ausgegangen, dass diese dreidimensionale, stabile Struktur von Proteinen eindeutig durch die Abfolge der einzelnen Aminosäuren, der Sequenz, bestimmt ist. Diese Abfolge ist für jedes Protein in der Desoxyribonukleinsäure (DNS) gespeichert. Es ist allerdings eines der größten ungelösten Probleme der letzten Jahrzehnte, wie die Beziehung zwischen Sequenz und 3D-Struktur tatsächlich aussieht. Die Beantwortung dieser Fragestellung erfordert interdisziplinäre Ansätze aus Biologie, Informatik und Physik. In dieser Arbeit werden mit Hilfe von Methoden der theoretischen (Bio-) Physik einige der damit verbundenen Aspekte untersucht. Das Hauptaugenmerk liegt dabei auf Wechselwirkungen der einzelnen Aminosäuren eines Proteins untereinander, wofür in dieser Arbeit ein entsprechendes Energiemodell entwickelt wurde. Es werden Grundzustände sowie Energielandschaften untersucht und mit experimentellen Daten verglichen. Die Stärke der Wechselwirkung einzelner Aminosäuren erlaubt zusätzlich Aussagen über die Stabilität von Proteinen bezüglich mechanischer Kräfte. Die vorliegende Arbeit unterteilt sich wie folgt: Kapitel 2 dient der Einleitung und stellt Proteine und ihre Funktionen dar. Kapitel 3 stellt die Modellierung der Proteinstrukturen in zwei verschiedenen Modellen vor, welche in dieser Arbeit entwickelt wurden, um 3D-Strukturen von Proteinen zu beschreiben. Anschließend wird in Kapitel 4 ein Algorithmus zum Auffinden des exakten Energieminimums dargestellt. Kapitel 5 beschäftigt sich mit der Frage, wie eine geeignete diskrete Energiefunktion aus experimentellen Daten gewonnen werden kann. In Kapitel 6 werden erste Ergebnisse dieses Modells dargestellt. Der Frage, ob der experimentell bestimmte Zustand dem energetischen Grundzustand eines Proteins entspricht, wird in Kapitel 7 nachgegangen. Die beiden Kapitel 8 und 9 zeigen die Anwendung des Modells an zwei Proteinen, dem Tryptophan cage protein als dem kleinsten, stabilen Protein und Kinesin, einem Motorprotein, für welches 2007 aufschlussreiche Experimente zur mechanischen Stabilität durchgeführt wurden. Kapitel 10 bis 12 widmen sich Membranproteinen. Dabei beschäftigt sich Kapitel 10 mit der Vorhersage von stabilen Bereichen (sog. Entfaltungsbarrieren) unter externer Krafteinwirkung. Zu Beginn wird eine kurze Einleitung zu Membranproteinen gegeben. Im folgenden Kapitel 11 wird die Entfaltung mit Hilfe des Modells und Monte-Carlo-Techniken simuliert. Mit dem an Membranproteine angepassten Wechselwirkungsmodell ist es möglich, den Einfluss von Mutationen auch ohne explizite strukturelle Informationen vorherzusagen. Dieses Thema wird in Kapitel 12 diskutiert. Die Beziehung zwischen Primär- und Tertiärstruktur eines Proteins wird in Kapitel 13 behandelt. Es wird ein Ansatz skizziert, welcher in der Lage ist, Strukturbeziehungen zwischen Proteinen zu detektieren, die mit herkömmlichen Methoden der Bioinformatik nicht gefunden werden können. Die letzten beiden Kapitel schließlich geben eine Zusammenfassung bzw. einen Ausblick auf künftige Entwicklungen und Anwendungen des Modells.

<p>Proteins are significant components of living cells. They perform a diverse range of biological functions such as cell shape and metabolism. The functions of proteins are determined by their three-dimensional structures. Cryogenic-electron microscopy (cryo-EM) is a technology known for determining the structure of large macromolecular structures including protein complexes. When individual atomic protein structures are available, a critical task in structure modeling is fitting the individual structures into the cryo-EM density map.</p> <p>In my research, I report a new computational method, MarkovFit, which is a machine learning-based method that performs simultaneous rigid fitting of the atomic structures of individual proteins into cryo-EM maps of medium to low resolution to model the three-dimensional structure of protein complexes. MarkovFit uses Markov random field (MRF), which allows probabilistic evaluation of fitted models. MarkovFit starts by searching the conformational space using FFT for potential poses of protein structures, computes scores which quantify the goodness-of-fit between each individual protein and the cryo-EM map, and the interactions between the proteins. Afterwards, proteins and their interactions are represented using a MRF graph. MRF nodes use a belief propagation algorithm to exchange information, and the best conformations are then extracted and refined using two structural refinement methods. </p> <p>The performance of MarkovFit was tested on three datasets; a dataset of simulated cryo-EM maps at resolution 10 Å, a dataset of high-resolution experimentally-determined cryo-EM maps, and a dataset of experimentally-determined cryo-EM maps of medium to low resolution. In addition to that, the performance of MarkovFit was compared to two state-of-the-art methods on their datasets. Lastly, MarkovFit modeled the protein complexes from the individual protein atomic models generated by AlphaFold, an AI-based model developed by DeepMind for predicting the 3D structure of proteins from their amino acid sequences.</p>

No description available.