Accurate 3D protein structure prediction is one of the most challenging problems facing bioinformaticians today. This thesis develops and examines an evaluation module for ranking predicted super-secondary structures – specifically a-helix pairs – as part of a case-based reasoning system. The proposed module is part of the Triptych project, which aims at the accurate prediction of the three-dimensional structure of proteins from contact maps. Triptych is an advanced case-based reasoning system that utilizes a library of existing protein structures and motifs to help predict the structure of a known polypeptide chain of amino acids that represents a target a-helix pair. The proposed module evaluates possible solutions by integrating multiple strategies, learning methods and sources of knowledge in the form of expert advisors. It uses advisors which integrate knowledge from the fields of biology, biochemistry, classical physics, and statistical data analysis obtained from pre-determined structures. Lastly, the proposed evaluation module would allow for the integration of more sources of knowledge, in the form of expert advisors, as well as serve as a framework for evaluating other structural motifs in future. / Thesis (Master, Computing) -- Queen's University, 2007-09-09 19:42:59.094

Proteins adopt three-dimensional structures which serve as a starting point to understand protein function and their evolutionary ancestry. It is unclear how proteins fold in vivo and how this process can be recreated in silico in order to predict protein structure from sequence. Contact maps are a possibility to describe whether two residues are in spatial proximity and structures can be derived from this simplified representation. Coevolution or supervised machine learning techniques can compute contact maps from sequence: however, these approaches only predict sparse subsets of the actual contact map. It is shown that the composition of these subsets substantially influences the achievable reconstruction quality because most information in a contact map is redundant. No strategy was proposed which identifies unique contacts for which no redundant backup exists. The StructureDistiller algorithm quantifies the structural relevance of individual contacts and identifies crucial contacts in protein structures. It is demonstrated that using this information the reconstruction performance on a sparse subset of a contact map is increased by 0.4 A, which constitutes a substantial performance gain. The set of the most relevant contacts in a map is also more resilient to false positively predicted contacts: up to 6% of false positives are compensated before reconstruction quality matches a naive selection of contacts without any false positive contacts. This information is invaluable for the training to new structure prediction methods and provides insights into how robustness and information content of contact maps can be improved. In literature, the relevance of two types of residues for in vivo folding has been described. Early folding residues initiate the folding process, whereas highly stable residues prevent spontaneous unfolding events. The structural relevance score proposed by this thesis is employed to characterize both types of residues. Early folding residues form pivotal secondary structure elements, but their structural relevance is average. In contrast, highly stable residues exhibit significantly increased structural relevance. This implies that residues crucial for the folding process are not relevant for structural integrity and vice versa. The position of early folding residues is preserved over the course of evolution as demonstrated for two ancient regions shared by all aminoacyl-tRNA synthetases. One arrangement of folding initiation sites resembles an ancient and widely distributed structural packing motif and captures how reverberations of the earliest periods of life can still be observed in contemporary protein structures.

Pattern discovery in protein structures is a fundamental task in computational biology, with important applications in protein structure prediction, profiling and alignment. We propose a novel approach for pattern discovery in protein structures using Particle Swarm-based flying windows over potentially promising regions of the search space. Using a heuristic search, based on Particle Swarm Optimization (PSO) is, however, easily trapped in local optima due to the sparse nature of the problem search space. Thus, we introduce a novel fitness-based stagnation detection technique that effectively and efficiently restarts the search process to escape potential local optima. The proposed fitness-based method significantly outperforms the commonly-used distance-based method when tested on eight classical and advanced (shifted/rotated) benchmark functions, as well as on two other applications for proteomic pattern matching and discovery. The main idea is to make use of the already-calculated fitness values of swarm particles, instead of their pairwise distance values, to predict an imminent stagnation situation. That is, the proposed fitness-based method does not require any computational overhead of repeatedly calculating pairwise distances between all particles at each iteration. Moreover, the fitness-based method is less dependent on the problem search space, compared with the distance-based method. The proposed pattern discovery algorithms are first applied to protein contact maps, which are the 2D compact representation of protein structures. Then, they are extended to work on actual protein 3D structures and interaction networks, offering a novel and low-cost approach to protein structure classification and interaction prediction. Concerning protein structure classification, the proposed PSO-based approach correctly distinguishes between the positive and negative examples in two protein datasets over 50 trials. As for protein interaction prediction, the proposed approach works effectively on complex, mostly sparse protein interaction networks, and predicts high-confidence protein-protein interactions — validated by more than one computational and experimental source — through knowledge transfer between topologically-similar interaction patterns of close proximity. Such encouraging results demonstrate that pattern discovery in protein structures and interaction networks are promising new applications of the fast-growing and far-reaching PSO algorithms, which is the main argument of this thesis. / Thesis (Ph.D, Computing) -- Queen's University, 2014-04-21 12:54:03.37