  Although proteins have been recognized as small-world networks and their
small-world network properties of clustering and short paths have been
exploited computationally to produce biologically relevant information, they
have not been truly explored as such, i.e. as navigable small-world networks in
the original spirit of Milgram's work. This research seeks to fill this gap by
exploring local search on a network representation of proteins and to probe the
source of navigability in proteins. Previously, we confirmed that proteins are
navigable small-world networks and observed that local search paths exhibit
different characteristics from global search paths. In this paper, we
investigate the biological relevance of the differences in path characteristics
on a type III receptor tyrosine kinase (KIT). A chief difference that works in
favour of local search paths as intra-protein communication pathways is their
weaker proclivity, compared to global search paths, for traversing long-range
edges. Long-range edges tend to be less stable and their inclusion tends to
decrease the communication propensity of a path. The source of protein
navigability is traced to clustering provided by short-range edges. The
majority of a protein's short-range edges reside within structures deemed
important for long-range energy transport and modulation of allosteric
communication in proteins. Therefore, the disruption of intra-protein
communication as a result of the destruction of these structures via random
rewiring is expected. A local search perspective leads us to this expected
conclusion while a global search perspective does not. These findings initiate
the compilation of a list of path properties that are characteristic of
intra-protein pathways and could suggest fresh avenues for evolving and
regulating navigable (small-world) networks.
