Pattern Discovery in Protein Structures and Interaction Networks
Abstract
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.
URI for this record
http://hdl.handle.net/1974/12051Request an alternative format
If you require this document in an alternate, accessible format, please contact the Queen's Adaptive Technology CentreRelated items
Showing items related by title, author, creator and subject.
-
Protein:Protein interactions and in vivo phosphorylation status of bacterial-type phosphoenolpyruvate carboxylase in castor flower tissue
Hill, Allyson (2011-04-27)Phosphoenolpyruvate carboxylase (PEPC) is a tightly regulated, key metabolic enzyme that is central to carbon metabolism in plants. PEPC catalyzes the irreversible β-carboxylation of phosphoenolpyruvate (PEP) and HCO3- to ... -
Regulation of the Human Ether-a-go-go Related Gene Potassium Channel by Neural Precursor Cell Expressed Developmentally Down-regulated Protein 4-2 Interacting Proteins
Kang, Yudi (2015-08-19)Dysfunction of the human ether-a-go-go related gene (hERG)-encoded rapidly activating delayed rectifier K+ channel is a major cause of long QT syndrome (LQTS) due to its critical role in the repolarization of cardiac action ... -
Antifreeze Proteins: Activity Comparisons and De Novo Design of an Ice-Binding Protein
Yu, Sally Oi Wah (2010-02-01)Antifreeze proteins (AFPs) help cold-adapted organisms survive below 0 ◦C by binding to and inhibiting the growth of ice crystals. In this way, AFPs depress the freezing point of aqueous fluids below the melting point of ...