  A protein contact map is a binary symmetric adjacency matrix capturing the
distance relationship between atoms of a protein. Each cell (i, j) of a protein
contact map states whether the atoms (nodes) i and j are within some Euclidean
distance from each other. We examined the radius one Moore neighborhood
surrounding each cell (i, j) where j > (i + 2) in complete protein contact maps
by mutating them one at a time. We found that the particular configuration of a
neighborhood is generally (97%) optimal in the sense that no other
configuration could maintain or improve upon existing local and global
efficiencies of the nodes residing in a neighborhood. Local efficiency of a
node is directly related to its clustering measure. Global efficiency of a node
is inversely related to its distance to other nodes in the network. This
feature of the Moore neighborhood in complete protein contact maps may explain
how protein residue networks are able to form long-range links to reduce
average path length while maintaining a high level of clustering throughout the
process of small-world formation, and could suggest new approaches to protein
contact map prediction. Effectively, the problem of protein contact map
prediction is transformed to one of maximizing the number of optimal
neighborhoods. By comparison, Moore neighborhoods in protein contact maps with
randomized long-range links are less optimal.
