Comparing protein structures based on their contact maps is an important problem in structural proteomics. Building a system for reconstructing protein tertiary structures from their contact maps is one of the motivations for devising novel contact map comparison algorithms. Several methods that address the contact map comparison problem have been designed which are briefly discussed in this thesis. However, they suggest scoring schemes that do not satisfy the two characteristics of “metricity” and “universality”. In this research we investigate the applicability of the Universal Similarity Metric (USM) to the contact map comparison problem. The USM is an information theoretical measure which is based on the concept of Kolmogorov complexity. The ultimate goal of this research is to use the USM in case-based reasoning system to predict protein structures from their predicted contact maps. The fact that the contact maps that will be used in such a system are the ones which are predicted from the protein sequences and are not noise-free, implies that we should investigate the noise-sensitivity of the USM. This is the first attempt to study the noise-tolerance of the USM. In this research, as the first implementation of the USM we converted the two-dimensional data structures (contact maps) to one-dimensional data structures (strings). The results of this implementation motivated us to circumvent the dimension reduction in our second attempt to implement the USM. Our suggested method in this thesis has the advantage of obtaining a measure which is noise tolerant. We assess the effectiveness of this noise tolerance by testing different USM implementation schemes against noise-contaminated versions of distinguished data-sets. / Thesis (Master, Computing) -- Queen's University, 2008-09-27 05:53:31.988

Recently, many methods have been proposed for the classification and prediction problems in bioinformatics. One of these problems is the protein structure prediction. Machine learning approaches and new algorithms have been proposed to solve this problem. Among the machine learning approaches, Support Vector Machines (SVM) have attracted a lot of attention due to their high prediction accuracy. Since protein data consists of sequence and structural information, another most widely used approach for modeling this structured data is to use graphs. In computer science, graph theory has been widely studied; however it has only been recently applied to bioinformatics. In this work, we introduced new algorithms based on statistical methods, graph theory concepts and machine learning for the protein structure prediction problem. A new statistical method based on z-scores has been introduced for seed selection in proteins. A new method based on finding common cliques in protein data for feature selection is also introduced, which reduces noise in the data. We also introduced new binary classifiers for the prediction of structural transitions in proteins. These new binary classifiers achieve much higher accuracy results than the current traditional binary classifiers.

The recent determination of several crystal structures of voltage-gated ion channels has catalyzed computational efforts of studying these remarkable molecular machines that are able to conduct ions across biological membranes at extremely high rates without compromising the ion selectivity. Starting from the open crystal structures, we have studied the gating mechanism of these channels by molecular modeling techniques. Firstly, by applying a membrane potential, initial stages of the closing of the channel were captured, manifested in a secondary-structure change in the voltage-sensor. In a follow-up study, we found that the energetic cost of translocating this 310-helix conformation was significantly lower than in the original conformation. Thirdly, collaborators of ours identified new molecular constraints for different states along the gating pathway. We used those to build new protein models that were evaluated by simulations. All these results point to a gating mechanism where the S4 helix undergoes a secondary structure transformation during gating. These simulations also provide information about how the protein interacts with the surrounding membrane. In particular, we found that lipid molecules close to the protein diffuse together with it, forming a large dynamic lipid-protein cluster. This has important consequences for the understanding of protein-membrane interactions and for the theories of lateral diffusion of membrane proteins. Further, simulations of the simple ion channel antiamoebin were performed where different molecular models of the channel were evaluated by calculating ion conduction rates, which were compared to experimentally measured values. One of the models had a conductance consistent with the experimental data and was proposed to represent the biological active state of the channel. Finally, the underlying methods for simulating molecular systems were probed by implementing the CHARMM force field into the GROMACS simulation package. The implementation was verified and specific GROMACS-features were combined with CHARMM and evaluated on long timescales. The CHARMM interaction potential was found to sample relevant protein conformations indifferently of the model of solvent used. / At the time of the doctoral defense, the following paper was unpublished and had a status as follows: Paper 3: Manuscript.

<p>Proteins are among the most complex entities known to science. Composed of just 20 fundamental building blocks arranged in simple linear strings, they nonetheless fold into a dizzying array of architectures that carry out the machinations of life at the molecular level.</p><p>Despite this central role in biology, we cannot reliably predict the structure of a protein from its sequence, and therefore rely on time-consuming and expensive experimental techniques to determine their structures. Although these methods can reveal equilibrium structures with great accuracy, they unfortunately mask much of the inherent molecular flexibility that enables proteins to dynamically perform biochemical tasks. As a result, much of the field of structural biology is mired in a static perspective; indeed, most attempts to naively model increased structural flexibility still end in failure.</p><p>This document details my work to validate alternative protein conformations beyond the primary or equilibrium conformation. The underlying hypothesis is that more realistic modeling of flexibility will enhance our understanding of how natural proteins function, and thereby improve our ability to design new proteins that perform desired novel functions.</p><p>During the course of my work, I used structure validation techniques to validate conformational alternatives in a variety of settings. First, I extended previous work introducing the backrub, a local, sidechain-coupled backbone motion, by demonstrating that backrubs also accompany sequence changes and therefore are useful for modeling conformational changes associated with mutations in protein design. Second, I extensively studied a new local backbone motion, helix shear, by documenting its occurrence in both crystal and NMR structures and showing its suitability for expanding conformational search space in protein design. Third, I integrated many types of local alternate conformations in an ultra-high-resolution crystal structure and discovered the combinatorial complexity that arises when adjacent flexible segments combine into networks. Fourth, I used structural bioinformatics techniques to construct smoothed, multi-dimensional torsional distributions that can be used to validate trial conformations or to propose new ones. Fifth, I participated in judging a structure prediction competition by using validation of geometrical and all-atom contact criteria to help define correctness across thousands of submitted conformations. Sixth, using similar tools plus collation of multiple comparable structures from the public database, I determined that low-energy states identified by the popular structure modeling suite Rosetta sometimes are valid conformations likely to be populated in the cell, but more often are invalid conformations attributable to artifacts in the physical/statistical hybrid energy function.</p><p>Unified by the theme of validating conformational alternatives by reference to high-quality experimental structures, my cumulative work advances our fundamental understanding of protein structural variability, and will benefit future endeavors to design useful proteins for biomedicine or industrial chemistry.</p> / Dissertation

Evolutionary algorithms (EAs) have been shown to be competent at solving complex, multimodal optimisation problems in applications where the search space is large and badly understood. EAs are therefore among the most promising classes of algorithms for solving the Protein Structure Prediction Problem (PSPP). The PSPP is how to derive the 3D-structure of a protein given only its sequence of amino acids. This dissertation defines, evaluates and shows limitations of simplified models for solving the PSPP. These simplified models are off-lattice extensions to the lattice HP model which has been proposed and is claimed to possess some of the properties of real protein folding such as the formation of a hydrophobic core. Lattice models usually model a protein at the amino acid level of detail, use simple energy calculations and are used mainly for search algorithm development. Off-lattice models usually model the protein at the atomic level of detail, use more complex energy calculations and may be used for comparison with real proteins. The idea is to combine the fast energy calculations of lattice models with the increased spatial possibilities of an off-lattice environment allowing for comparison with real protein structures. A hypothesis is presented which claims that a simplified off-lattice model which considers other amino acid properties apart from hydrophobicity will yield simulated structures with lower Root Mean Square Deviation (RMSD) to the native fold than a model only considering hydrophobicity. The hypothesis holds for four of five tested short proteins with a maximum of 46 residues. Best average RMSD for any model tested is above 6Å, i.e. too high for useful structure prediction and excludes significant resemblance between native and simulated structure. Hence, the tested models do not contain the necessary biological information to capture the complex interactions of real protein folding. It is also shown that the EA itself is competent and can produce near-native structures if given a suitable evaluation function. Hence, EAs are useful for eventually solving the PSPP.

A novel approach is proposed for modeling of structurally variable regions in proteins. In this approach, a prerequisite sequence-structure alignment is examined for regions where the target sequence is not covered by the structural template. These regions, extended with a number of residues from adjacent stem regions, are submitted to fold recognition. The alignments produced by fold recognition are integrated into the initial alignment to create a multiple alignment where gaps in the main structural template are covered by local structural templates. This multiple alignment is used to create a protein model by existing protein modeling techniques. Several alternative parameters are evaluated using a set of ten proteins. One set of parameters is selected and evaluated using another set of 31 proteins. The most promising result is for loop regions not located at the C- or N-terminal of a protein, where the method produces an average RMSD 12% lower than the loop modeling provided with the program MODELLER. This improvement is shown to be statistically significant.

<div> <div> <div> <p>Proteins are drivers of almost all biological processes in the cell. The functions of a protein are dependent on their three-dimensional structure and elucidating the structure and function of proteins is key to understanding how a biological system operates. In this research, we developed computational methods using machine learning techniques to predicts the structure and function of proteins. Protein 3D structure prediction has advanced significantly in recent years, largely due to deep learning approaches that predict inter-residue contacts and, more recently, distances using multiple sequence alignments (MSAs). The performance of these models depends on the number of similar protein sequences to the query protein, wherein some cases similar sequences are few but dissimilar sequences with local similarities are more and can be helpful. We have developed a novel deep learning-based approach AttentiveDist which further improves over the previous state of art. We added an attention mechanism where dis-similar sequences are also used (increasing number of sequences) and the model itself determines which information from such sequences it should attend to. We showed that the improvement of distance predictions was successfully transferred to achieve better protein tertiary structure modeling. We also show that structure prediction from a predicted distance map can be further enhanced by using predicted inter-residue sidechain center distances and main-chain hydrogen-bonds. Protein function prediction is another avenue we explored where we want to predict the function that a protein will perform. The crux of the approach is to predict the function of protein based on the function of similar sequences. Here, we developed a method where we use dissimilar sequences to extract additional information and improve performance over the previous approaches. We used phylogenetic analysis to determine if a dissimilar sequence can be close to the query sequence and thus can provide functional information. Our method was ranked highly in worldwide protein function prediction competition CAFA3 (2016-2019). Further, we expanded the method with a neural network to predict protein toxicity that can be used as a safety check for human-designed protein sequences.</p></div></div></div>

No description available.

No description available.

A demanda criada pelos estudos biológicos resultou para predição da estrutura terciária de proteínas ser uma alternativa, uma vez que menos de 1% das sequências conhecidas possuem sua estrutura terciária determinada experimentalmente. As predições Ab initio foca nas funções baseadas da física, a qual se trata apenas das informações providas pela sequência primária. Por consequência, um espaço de busca com muitos mínimos locais ótimos deve ser pesquisado. Este cenário complexo evidencia uma carência de algoritmos eficientes para este espaço, tornando-se assim o principal obstáculo para este tipo de predição. A optimização Multi-Objetiva, principalmente os Algoritmos Evolutivos, vem sendo aplicados na predição da estrutura terciária já que na mesma se envolve um compromisso entre os objetivos. Este trabalho apresenta o framework ProtPred-PEO-GROMACS, ou simplesmente 3PG, que não somente faz predições com a mesma acurácia encontrada na literatura, mas também, permite investigar a predição por meio da manipulação de combinações de objetivos, tanto no aspecto energético quanto no estrutural. Além disso, o 3PG facilita a implementação de novas opções, métodos de análises e também novos algoritmos evolutivos. A fim de salientar a capacidade do 3PG, foi então discorrida uma comparação entre os algoritmos NSGA-II e SPEA2 aplicados na predição Ab initio da estrutura terciária de proteínas em seis combinações de objetivos. Ademais, o uso da técnica de refinamento por Dinâmica Molecular é avaliado. Os resultados foram adequados quando comparado com outras técnicas de predições: Algoritmos Evolutivo Multi-Objetivo, Replica Exchange Molecular Dynamics, PEP-FOLD e Folding@Home. / The demand created by biological studies resulted the structure prediction as an alternative, since less than 1% of the known protein primary sequences have their 3D structure experimentally determined. Ab initio predictions focus on physics-based functions, which regard only information about the primary sequence. As a consequence, a search space with several local optima must be sampled, leading to insucient sampling of this space, which is the main hindrance towards better predictions. Multi-Objective Optimization approaches, particularly the Evolutionary Algorithms, have been applied in protein structure prediction as it involves a compromise among conicting objectives. In this paper we present the ProtPred-PEO-GROMACS framework, or 3PG, which can not only make protein structure predictions with the same accuracy standards as those found in the literature, but also allows the study of protein structures by handling several energetic and structural objective combinations. Moreover, the 3PG framework facilitates the fast implementation of new objective options, method analysis and even new evolutionary algorithms. In this study, we perform a comparison between the NSGA-II and SPEA2 algorithms applied on six dierent combinations of objectives to the protein structure. Besides, the use of Molecular Dynamics simulations as a renement technique is assessed. The results were suitable when comparated with other prediction methodologies, such as: Multi-Objective Evolutionary Algorithms, Replica Exchange Molecular Dynamics, PEP-FOLD and Folding@Home.