We propose the use of local search to investigate protein residue networks ( PRN) . In a local search , clustering is inversely related to average path length. The opposite holds for a global search such as the commonly used breadth first strategy (BFS). The inverse relationship better fits the notion that amino acids get closer to each other as a protein becomes more compact. We use a greedy local search algorithm (EDS) that is Euclidean distance based and allows backtracking. While there are preferable differences between BFS and EDS paths in terms of variation in path length , search cost and link usage, there are also similarities in terms of centrality and hierarchy . EDS identifies a set of short-cut edges for each PRN . Short-cut edges are enriched with short-range links, and the short-cut network (SCN) they form spans most of a PRN's nodes, is adjacent to most of a PRN's edges and is strongly transitive. The short-cuts influence average EDS path length by reducing the difference in length or stretch between path-pairs. A consequence of this role is short-cut sets are more volatile, i.e. they undergo significantly more additions and deletions from step to step in a molecular dynamics (MD ) simulation than non-short-cut edge sets. Despite their volatility, about 79\% of SCN edge deletions have replacements (a deleted short-cut is replaced when an added short-cut is found in the edge cut-set of the deleted short-cut), and about 88\% of added short-cuts are replacement edges. This high edge replacement rate helps with the growth of the largest connected component of a SCN . More work is needed to understand the structure and formation of SCNs, in particular to identify the conditions under which short-cuts get deleted and how their replacements are selected .
We examined protein residue networks ( PRNs) from a local search perspective to understand why PRNs are highly clustered when having short paths is important for protein functionality. We found that by adopting a local search perspective, this conflict between form and function is resolved as increased clustering actually helps to reduce path length in PRNs. Further, the paths found via our EDS local search algorithm are more congruent with the characteristics of intra-protein communication . EDS identifies a subset of PRN edges called short-cuts that are distinct, have high usage, impacts EDS path length, diversity and stretch, and are dominated by short-range contacts. The short-cuts form a network (SCN) that increases in size and transitivity as a protein folds. The structure of a SCN supports its function and formation, and the function of a SCN influences its formation. Several significant differences in terms of SCN structure, function and formation is found between successful and unsuccessful MD trajectories. We hypothesize that strong SCN transitivity is a hallmark of well-formed SCNs, and suggest the possibility of using SCN transitivity as a folding coordinate for proteins whose native state is not known a priori. By connecting the static and the dynamic aspects of PRNs, the protein folding process becomes a problem of graph formation with the purpose of forming suitable pathways within proteins .
R
propose the use of local search to investigate
examined
R
PRN) . In
PRNs) from
R
, clustering is inversely related to average path length. The opposite holds for a global search such as the commonly used breadth first strategy (BFS). The inverse relationship better fits the notion that amino acids get closer to each other as a protein becomes more compact. We use a greedy local search algorithm (EDS) that is Euclidean distance based and allows backtracking. While there are preferable differences between BFS and EDS paths in terms of variation in path length ,
perspective to understand why PRNs are highly clustered when having short paths is important for protein functionality. We found that by adopting a local
R
cost and link usage, there are also similarities in terms of centrality and hierarchy
perspective, this conflict between form and function is resolved as increased clustering actually helps to reduce path length in PRNs. Further, the paths found via our EDS local search algorithm are more congruent with the characteristics of intra-protein communication
R
set of short-cut edges for each PRN . Short-cut edges are enriched with
subset of PRN edges called short-cuts that are distinct, have high usage, impacts EDS path length, diversity and stretch, and are dominated by
R
links, and the short-cut
contacts. The short-cuts form a
R
they form spans most of a PRN's nodes, is adjacent to most of a PRN's edges and is strongly transitive. The short-cuts influence average EDS path length by reducing the difference in length or stretch between path-pairs. A consequence of this role is short-cut sets are more volatile, i.e. they undergo significantly more additions and deletions from step to step in a molecular dynamics (MD ) simulation than non-short-cut edge sets. Despite their volatility, about 79\% of SCN edge deletions have replacements (a deleted short-cut is replaced when an added short-cut is found in the edge cut-set of the deleted short-cut), and about 88\% of added short-cuts are replacement edges. This high edge replacement rate helps with the growth of the largest connected component of a SCN . More work is needed to understand the structure and formation of SCNs, in particular to identify the conditions under which short-cuts get deleted and how their replacements are selected
that increases in size and transitivity as a protein folds. The structure of a SCN supports its function and formation, and the function of a SCN influences its formation. Several significant differences in terms of SCN structure, function and formation is found between successful and unsuccessful MD trajectories. We hypothesize that strong SCN transitivity is a hallmark of well-formed SCNs, and suggest the possibility of using SCN transitivity as a folding coordinate for proteins whose native state is not known a priori. By connecting the static and the dynamic aspects of PRNs, the protein folding process becomes a problem of graph formation with the purpose of forming suitable pathways within proteins