Computational Drug Discovery and Design

CCðÞ¼v

XN

i¼ 1

diðÞ;v=ðÞN 1

! 1

ð 3 Þ

whered(i,v) is the minimal number of edges that bridge the

nodesiandv. For a given network topology,d(i,j) can be

calculated by using Dijkstra’s algorithm [34].

3. The betweenness centrality, CB(v), measures the extent to
   which a node has control over transmission of information
   between the nodes in the network [35].

CBðÞ¼v

2

ðÞN 1 ðÞN 2

NX 1

s¼ 1

XN

t¼sþ 1

σstðÞv

σst

ð 4 Þ

wheres 6 ¼t 6 ¼v. In the above definition,σstis the number of

shortest paths linking the nodessandt, andσst(v) is the number of

shortest paths linking the nodessandtvia the nodev. The factor

(N1)(N2)/2 is the normalization constant. To reduce the

computational cost of Eq.4, we used Brandes algorithm [36],

which exploits the sparse nature of typical real-world graphs, and

computes the betweenness centrality score for all vertices in the

graph in a very short time.

By surmising that allosteric hotspots are the mediators of infor-

mation flow in a network topology of a given protein structure, we

adopted betweenness centrality concept in identifying hotspot resi-

dues which can modulate the signal transduction in GPCRs (see

Note 4). Since the betweenness centrality calculates the extent to

which a particular node lies between other nodes in the network

[31, 36, 37], a member with high betweenness may act as a gate-

keeper or broker in the network for either smooth communication

or flow of information [37]. Using the minimum energy structures

generated by the MD simulation, the residue interaction network

was constructed with a cutoff distance of 7 A ̊. Subsequently, the

betweenness centrality was calculated to measure each residue’s

importance for the flux of information in the residue interaction

network (seeNote 5).

2.2.4 Network
Vulnerability Analysis
(Glycine Scanning)

When a network is attacked by a certain perturbation, it may or may

not collapse depending on the importance of the attacked site

[38]. The rate at which the network is affected by perturbation

could be regarded as a network’s tolerance to an error or vulnera-

bility to an attack, and a member with high vulnerability can be

considered to have a crucial role in the stable formation or integrity

of the network [39]. In the theory of complex network, this

vulnerability is evaluated using a relative change in the average

network centrality when a nodexis removed, which can be written

as follows [39]:

Molecular Dynamics Approach for Investigation of GPCR Allostery 463