Protein residue networks from a local search perspective

Khor, Susan (2014) Protein residue networks from a local search perspective. Technical Report. Memorial University of Newfoundland, St. John's, Newfoundland. (Submitted)

[English] PDF - Submitted Version Available under License Creative Commons Attribution Non-commercial Share Alike. Download (1MB)

Abstract

Proteins have been abstracted as a network of interacting amino acids and much attention has been paid to the small-world property of such networks, which we call protein residue networks (PRNs). Hitherto, a global search strategy such as Breath-First Search (BFS) is commonly used to measure the average path length of PRNs. We propose that a local search strategy is more appropriate because the inverse relationship between clustering and average path length in a local search better fits the notion that amino acids get closer to each other as a protein becomes more compact. This inverse relationship is also observed in data from a molecular dynamics (MD) simulation of a protein unfolding. To study local search on PRNs, we devised a greedy local search algorithm called EDS and compared the characteristics of BFS paths with EDS paths. While they are different in terms of variation in path length, search cost and link usage, they exhibit similarities in terms of hierarchy and centrality. We argue that the differences are preferable as they make EDS paths a better model of intra-protein communication. The similarities are also preferable as they imply the transferability of existing methods based on BFS centrality. Clustering coupled with strong transitivity helps to keep EDS paths short on PRNs by creating a store of potential short-cut edges. The ready availability of PRN edges that can act as short-cuts helps EDS avoid backtracking. The number of short-cuts scales linearly with protein size. Short-cut edges are enriched with short-range contacts, see higher usage (are more central), have stronger local clustering but weaker local community structure, and effect larger EDS path dilation. Throughout the paper, network statistics for PRNs from a MD simulation are reported to support our findings, and to observe how the network statistics change as a protein folds.

Actions (login required)

View Item