# Pin-Align: A New Dynamic Programming  Approach to Align Protein-Protein Interaction Networks

Authors: Farid Amir-Ghiasvand; Abbas Nowzari-Dalini; Vida Momenzadeh
Journal: Computational and Mathematical Methods in Medicine
 (2014)

---

## Abstract

To date, few tools for aligning protein-protein interaction networks have been suggested. These tools typically find conserved interaction patterns using various local or global alignment algorithms. However, the improvement of the speed, scalability, simplification, and accuracy of network alignment tools is still the target of new researches. In this paper, we introducePin-Align, a new tool for local alignment of protein-protein interaction networks. Pin-Align accuracy is tested on protein interaction networks from IntAct, DIP, and the Stanford Network Database and the results are compared with other well-known algorithms. It is shown that Pin-Align has higher sensitivity and specificity in terms of KEGG Ortholog groups.


---

## Body

## 1. Introduction

In the last decade, high throughput techniques in experimental biology produced a large amount of biological data which usually can be modeled by large networks such as metabolic networks, gene regulatory networks, and protein-protein interaction (PPI) networks [1]. Analogous to biological sequence comparison [2–4], comparing large biological networks can improve our biological understanding of them. Comparison of PPI networks is a well-studied area due to the important roles of PPI networks. The main idea behind comparison of PPI networks is to find evolutionary conserved interaction modules which describes functional relevance. Exact comparison of large PPI networks is a NP-hard problem and there is no polynomial time algorithm for it. The NP-hardness of this problem is based on the fact that this problem can be reduced to the subgraph isomorphism problem. In this way, the exact comparison of PPI networks is computationally infeasible, and PPI networks comparison is often addressed by heuristic methods [5–7].Several algorithms have been proposed for biological network alignment. One of the first proposed network alignment algorithms isPath-Blast [8]. This algorithm finds high-score conserved pathways. After that, Sharan et al. designedNetwork-Blast [9] in order to identify conserved protein complexes in multiple species. Koyuturk et al. devised an evolution-based scoring scheme to detect conserved clusters, calledMaWISh (maximum weight induced subgraph) [10]. Flannick et al. proposedGraemlin as the first method to detect conserved subnetworks of arbitrary structures with progressive alignment method [11]. All these mentioned algorithms are called local alignment algorithms owing to the fact that they started to find subnetworks such as pathways and protein complexes and expanded their search results to obtain the feasible alignment. In local network alignment, each protein may be mapped to several proteins. On the other hand, global network alignment algorithm is defined to detect the best overall mapping across all parts of the input networks.IsoRank is the first global network alignment algorithm aiming to maximize the overall match between two networks [12]. Flannick et al. extendedGraemlin to global network alignment by using a training set of known network alignments to learn parameters for the scoring function. This novel algorithm is calledGraemlin 2.0 and is claimed to have linear time complexity with the number of PPIs [13]. The next version ofIsoRank,IsoRankN [14], usesNibble-Page-Rank algorithm [15] to align input networks locally and globally. Tian and Samatova introduced a connected-components based algorithm, calledHopeMap, for pairwise network alignment with the focus on fast identification of maximal conserved patterns [16]. After that,GRAAL [6] andH-GRAAL [1] are presented as the global network alignment algorithms based on seed-extend approaches and Hungarian algorithm, respectively. Both ofGRAAL andH-GRAAL algorithms are capable of aligning any kind of network owing to the fact that they are specifically designed based on network structure and do not use sequence similarity data. Observing that the size of true orthologs across species is small comparing to the total number of proteins in all species, Tian and Samatova presented a different approach based on a precompiled list of homologs identified by KO terms [17].In this paper,Pin-Align (protein interaction network alignment) algorithm is introduced as a novel local network alignment algorithm for aligning two protein-protein interaction networks. InPin-Align, Hub Clustering and hierarchical clustering algorithms are applied in the heuristic and dynamic programming phases in order to reduce time and space complexity of the problem. Two different types of scoring,Node-Scoring andStructural-Scoring, are used to find the best local alignments.Node-Scoring is simply based on BLAST bit score [18] andStructural-Scoring is based on the importance ofBridges (Bridges are considerable edges, which take part in most of the paths and consequently conserved paths in the networks) in biological networks.ThePin-Align algorithm is performed on the protein interaction networks ofEscherichia coli (E. coli), Salmonella typhimurium (S. typhimurium), Caulobacter crescentus (C. crescentus), human, mouse, yeast, and Drosophila melanogaste (fly) extracted from IntAct [19], DIP [20], and Stanford Network database (SNDB) [21]. The obtained results are compared with other well-known local alignment algorithms NetworkBLAST [9], MaWISh [10], Graemlin [11], and Graemlin 2.0 [13], in a way that Graemlin 2.0 compares its results, because it is the only method that compares results of all local alignment tools against KEGG Ortholog (KO) groups [22].


## 2. Materials and Methods

Protein-protein interaction (PPI) network is defined as the set of relationships among proteins. Here, a PPI network is modeled by an undirected and weighted graphG
=
(
V
,
E
), where nodes correspond to proteins and each weighted edge specifies the probability that two proteins interact. For two graphs G
1
=
(
V
1
,
E
1
) and G
2
=
(
V
2
,
E
2
) (such as two sample networks A and B in Figure 1), the goal of network alignment is to identify possible mappings which map vertices of G
1 into vertices of G
2.Two sample networksA and B.
(a)
(b)In addition, for each mapping, the corresponding set of conserved edges is also identified. Mappings may be partial; that is, they do not need to be defined for all the nodes of the graphs. Each mapping implies a common subgraph between the two graphs. When proteina
1 from graph G
1 is mapped to protein a
2 from graph G
2, then a
1 and a
2 refer to the same node in the common subgraph; the edges in the common subgraph correspond to the conserved edges [23].Pin-Align algorithm is a local network alignment algorithm, mainly designed based on the dynamic programming approach. To explainPin-Align in more detail, first a formal definition of local network alignment is presented. Given two graphs G
1
(
V
1
,
E
1
) and G
2
(
V
2
,
E
2
), local alignment L
A
G
1
,
G
2
(
S
g
1
,
S
g
2
,
M
) is a triplet where S
g
1 and S
g
2 are the subgraphs of G
1 and G
2, respectively, and M is defined as the mapping which aligns vertices of S
g
1 into vertices of S
g
2. Two sample local alignments of networks A and B of Figure 1 are shown in Figure 2(a).Figure 2
(a) Two local alignments of networksA and B of Figure 1. (b) Result of merging them.Following, the best local network alignment (BLA) is defined as a function to obtain the best local alignment for each subgraph ofG
1. The best local alignment of S
g
1 as a subgraph of G
1 with a subgraph of G
2 is shown by BL
A
G
1
,
G
2
(
S
g
1
), which represents a local alignment with the highest score among all possible alignments between S
g
1 and all possible subgraphs of G
2 that can be mapped to S
g
1.Now, a naive dynamic programming algorithm for network alignment is demonstrated in the next subsection, and laterPin-Align algorithm is presented.


### 2.1. Dynamic Programming Algorithm to Align PPI Networks

In alignment of two weighted graphsG
1 and G
2 through dynamic programming technique, we generate all LAs of size one (subgraphs with a single vertex) in the first step. For obtaining LAs of larger subgraphs of G
1, we merge all possible pairs of LA of smaller subgraphs. In other words, for each subgraph of G
1 such as S
g
1, there are several pairs of distinct subgraphs (subgraphs with no common vertices) such as (
T
1
,
T
2
) where S
g
1
=
T
1
∪
T
2. Figure 2 demonstrated the merge process of two sample local alignments of networks A and B of Figure 1. We produce all possible local alignments for S
g
1 such as L
A
G
1
,
G
2
(
S
g
1
,
S
g
2
,
M
) by merging every possible local alignments of T
1 such as L
A
G
1
,
G
2
(
T
1
,
T
1
′
,
M
′
) with every possible local alignment of T
2 such as L
A
G
1
,
G
2
(
T
2
,
T
2
′
,
M
′′
). This process is done iteratively, and finally all local alignments of G
1 including BL
A
G
1
,
G
2
(
G
1
) are obtained.Inspired by dynamic programming technique, we proposeSimple-Align algorithm in Algorithm 1. This algorithm can find all BLAs; however by considering time and memory complexity, this algorithm is not feasible. To overcome this, we use several heuristics to reduce memory and time complexity and propose a new local alignment algorithm,Pin-Align, in next section.Algorithm 1:
Simple-Align algorithm.
Input: Graph G
1(V
1, E
1), Graph G
2(V
2, E
2) such that |
V
1
|
=
n
Output: Local alignment
(1)   Define S as an array of sets with length n
(2)   S
[
1
] = Set of all local alignments of size one
(3)   for  s
i
z
e
=
2 to n  do
(4)    for  i
=
1 to s
i
z
e
-
1  do
(5)     j
=
s
i
z
e
-
i
(6)     for  k
=
1 to |
S
[
i
]
|  do
(7)      for  l
=
1 to |
S
[
j
]
|  do
(8)       L
A  A = k’th element of S
[
i
]
(9)       L
A  B = l’th element of S
[
j
]
(10)     S
[
s
i
z
e
]
=
S
[
s
i
z
e
]
⋃
M
e
r
g
e
(
A
,
B
)
(11)    end for
(12)   end for
(13)  end for
(14) end for
(15) return The LA with highest score among all LAs in S
[
n
]


### 2.2.Pin-Align Algorithm

As explained,Pin-Align uses dynamic programming approach to solve the local network alignment problem and overcome the deficiencies of dynamic programming such as time and space complexity by applying heuristic approach. The steps of thePin-Align algorithm are summarized as follows.(1)
Partition the input graphG
1 into smaller clusters. These clusters are dense subgraphs of G
1. The partitioning is done by using a new clustering algorithm named Hub Clustering. Clusters obtained in this step are namedHub-Clusters.
(2)
For eachH
u
b-C
l
u
s
t
e
r
i,
(a)
create local alignments of size one with BLAST bit score greater than 0, between vertices ofH
u
b-C
l
u
s
t
e
r
i and vertices of G
2; local alignments obtained by this approach are namedCandidates (C
=
L
A
G
1
,
G
2
(
S
g
1
,
S
g
2
,
M
) such that S
g
1 is a subgraph of H
u
b-C
l
u
s
t
e
r
i with size one),
(b)
collect allCandidates of subgraph S
g
1 of G
1 (such as C
=
L
A
G
1
,
G
2
(
S
g
1
,
S
g
2
,
M
)) in a new set calledCandidate-Collection and eachCandidate-Collection is represented by its subgraph of G
1 such as CC
(
S
g
1
);Candidate-Collections obtained for single nodes of G
1 are used as seeds in Step 2(c),
(c)
merge smallCandidate-Collections (seeds) to gain larger ones. Repeat this process continuously to achieve aCandidate-Collection
CC
(
H
u
b-C
l
u
s
t
e
r
i
) as the final result of merging process. Size of aCandidate or aCandidate-Collection is defined by the number of vertices of its subgraph of G
1 and cardinality of aCandidate-Collection is defined as the number of itsCandidates. In this step, eachCandidate-Collection can be merged with severalCandidate-Collections and createCandidate-Collections with larger size. For determining whichCandidate-Collections should be merged together, a new hierarchical clustering is used as a pattern of merging.TheCandidate-Collections ofHub-Clusters are namedFinal-Candidate-Collections.(3)
Based onFinal-Candidate-Collections, find final alignment using similarity graph. This graph is a special weighted bipartite graph where first and second set of vertices of it are shown by V
1 and V
2 which are the set of vertices of G
1 and G
2. The weight of each edge is computed based onFinal-Candidate-Collections.Flowchart ofPin-Align algorithm is presented in Figure 3 and its details are explained by an example on two networks A and B given in Figure 1.Figure 3
Flowchart ofPin-Align algorithm.In Step 1, in order to reduce the search space of the problem, input graphG
1
=
(
V
1
,
E
1
) is clustered into some dense subgraphs and Step 2 of the algorithm runs for each dense subgraph separately. Generally PPI networks are sparse graphs, but they have dense regions containing high degree vertices named hubs. These regions usually contain protein complexes; therefore conserved modules among different PPIs usually exist in these regions.To detect dense subgraphs in the graphG
1, a novel clustering algorithm, calledHub Clustering, is proposed. The importance of hub nodes and density of subgraphs are two major criteria for this clustering method. First, a portion of highly connected vertices are selected as hub nodes. The vertices degree of these nodes is greater than 95
% of other nodes. The hub nodes are considered as the center vertices of dense regions of graph G
1 and are supposed to be initial clusters. For other nodes of G
1, each node is joint to the nearest cluster (the cluster that contains its nearest hub). For this aim, the length of each edge is defined as the negative logarithm of its weight (from adjacency matrix), and then Dijkstra shortest path algorithm [24] is used to find the nearest cluster. The obtained clusters are namedHub-Clusters.In Step 2, each ofHub-Clusters of G
1 (obtained in Step 1) is aligned to G
2. As mentioned, Step 2(a) createsCandidates of size one based on BLAST bit score of vertices of two graphs G
1 and G
2 (BLAST bit score is a normalized score which is calculated by basic local alignment search tool, based on sequence similarity [18]). Figure 4(a) shows BLAST bit scores of proteins of networks A and B.(a) BLAST bit scores for proteins of networksA and B shown in Figure 1. (b) All possibleCandidates of size one of networks A and B. (c) All possibleCandidate-Collections of size one for networks A and B.
(a)
(b)
(c)After that, allCandidates of each vertex of G
1 are collected into aCandidate-Collection with size one as a seed in Step 2(b). In other words,Candidate-Collection of each vertex of G
1 such as S
g
1 contains allCandidates for S
g
1 from G
2 which can be aligned with S
g
1. For example,Candidates of networks A and B of Figure 1 are shown in Figure 4(b) and thoseCandidate-Collections are shown in Figure 4(c).In Step 2(c), two seeds (i.e.,Candidate-Collections
CC
(
S
g
i
) and CC
(
S
g
j
)) are merged in order to produce a new seed (new-CC) where its size is sum of sizes of CC
(
S
g
i
) and CC
(
S
g
j
). Figure 5 illustrates twoCandidate-Collections, C
a
n
d
i
d
a
t
e-C
o
l
l
e
c
t
i
o
n
2 and C
a
n
d
i
d
a
t
e-C
o
l
l
e
c
t
i
o
n
3, of Figure 4(c) and the result of merging them.Figure 5
TwoCandidate-Collections and the result of merging them.The important problem in this step is discovering the feasible combining pattern to find pairs ofCandidate-Collections where merging them generates high scoreCandidate-Collections. In order to find high scoreCandidates and avoid complex searches, combining pattern for mergingCandidate-Collections should produceCandidates with more conserved edges. Hence we use hierarchical clustering as combining patterns [25]. Hierarchical clusters are generally constructed by generating a sequence of partitions where each subcluster belongs to one supercluster in its entity.In hierarchical clustering we should determine how the distance between two clusters is computed. IfS
i
=
(
V
i
′
,
E
i
′
) and S
j
=
(
V
j
′
,
E
j
′
) are subgraphs of G
1
=
(
V
1
,
E
1
), the distance between twoCandidate-Collections
CC
(
S
i
) and CC
(
S
j
) is computed, using the following formula:
(1)
dis
CC
S
i
,
CC
S
j
=
V
i
′
+
V
j
′
∑
v
∈
V
i
′
∑
u
∈
V
j
′
(
a
v
,
u
/
e
v
,
u
)
.
In this equation, a
v
,
u is equal to one if there is an edge between vertices u and v; otherwise it is zero, and e
v
,
u is the negative logarithm of probability of interaction between two proteins v and u in the graph G
1. We use the hierarchical clustering obtained based on formula, as the combining pattern for mergingCandidate-Collections. Cardinality of newCandidate-Collections obtained in higher levels of hierarchical clustering tree is increased exponentially as a result of merging smallerCandidate-Collections, so we have to save theCandidates with highest score and discardCandidates with low scores. In Step 2(c) we use a multiobjective optimization technique for finding the highest scoreCandidates [26]. The highest scoreCandidates are obtained by sortingCandidates based on two criteria, first,Nodes-Scores; next,Structural-Scores. Finally, theCandidates with the highest scores are chosen in each step. Following, we describe this scoring schema.Node-Score.Node-score of eachCandidate
C
=
L
A
G
1
,
G
2
(
S
g
1
,
S
g
2
,
M
) is obtained by using the following equation:
(2)
NodeScore
(
C
)
=
∑
i
=
1
S
g
1
‍
BLASTBitScore
S
g
1
i
,
MV
S
g
1
i
,
M
.
In this equation, i is an iterator on vertices of S
g
1 and S
g
1
i is the ith vertex of S
g
1; MV
(
v
,
M
) indicates a vertex of S
g
2 mapped into v
∈
S
g
1 by the mapping M.Structural-Score. Due to the existence of hubs and small words in biological networks, certainly the network contains bridges. Bridges are considerable edges, which take part in most of the paths (specifically conserved paths) in the networks. Because of the importance of bridges, if S
g
1
=
(
V
1
′
,
E
1
′
) is a subgraph of G
1
=
(
V
1
,
E
1
) and S
g
2
=
(
V
2
′
,
E
2
′
) is a subgraph of G
2
=
(
V
2
,
E
2
), the structural scoring function for eachCandidate
C
=
L
A
G
1
,
G
2
(
S
g
1
,
S
g
2
,
M
) is defined as follows:
(3)
StructuralScore
(
C
)
=
∑
v
∈
V
1
′
‍
∑
u
∈
V
1
′
‍
f
v
×
f
u
α
×
P
G
1
(
v
,
u
)
P
G
2
MV
v
,
M
,
MV
u
,
M
P
G
1
MV
u
,
M
1
-
α
.
In this equation, f
(
i
) shows the number of conserved edges at vertex i in the subgraph S
g
1; α is a constant value between 0 and 1 and shows the importance of adjacent vertices degrees; P
G
(
x
,
y
) is the probability of interaction between protein x and protein y in the network G.As mentioned before, to control the exponential growth of the cardinality ofCandidate-Collections in combining process, we use a multiobjective optimization method on node score and structural score, as optimization objectives. In this way, after creating eachCandidate-Collection among allCandidates obtained in that, we select only a limited number ofCandidates (based on upon scoring functions) and discard others. ObtainedCandidate-Collections ofHub-Clusters are namedFinal-Candidate-Collections which containFinal-Candidates(Candidates ofHub-Clusters).After creating allFinal-Candidate-Collections, in Step 3 ofPin-Align Algorithm, anInitial Similarity Bipartite Graph
ISBG
(
G
1
,
G
2
)
=
(
V
1
,
V
2
,
E
) is created which consists of vertices of G
1
=
(
V
1
,
E
1
) as its first part and vertices of G
2
=
(
V
2
,
E
2
) as its second part, and E is a set of weighted edges between V
1 and V
2. The weight of each edge represents the similarity between its incident vertices. Let C
(
v
i
,
u
j
) be a set of allFinal-Candidates which maps v
i into u
j. In ISBG
(
G
1
,
G
2
), the weight of an edge e
=
{
v
i
,
u
j
}, where v
i
∈
V
1 and u
j
∈
V
2, is equal to zero if |
C
(
v
i
,
u
j
)
|
=
0; otherwise this weight is defined by the following formula:
(4)
W
v
i
,
u
j
=
Nod
e
Sim
v
i
,
u
j
+
Neighborhood
s
Sim
v
i
,
u
j
×
1
|
C
(
v
i
,
u
j
)
|
,
where Nod
e
Sim
(
v
i
,
u
j
) is the similarity between two proteins v
i and u
j and it is calculated by using the following formula:
(5)
Nod
e
Sim
(
v
i
,
u
j
)
=
BLASTBitScore
(
v
i
,
u
j
)
×
C
v
i
,
u
j
,
Neighborhood
s
Sim
(
v
i
,
u
j
) is the similarity between conserved neighborhoods of v
i and u
j and is calculated as follows:
(6)
Neighborhood
s
Sim
(
v
i
,
u
j
)
=
∑
c
∈
C
(
v
i
,
u
j
)
‍
∑
(
v
i
′
,
u
j
′
)
∈
C
N
c
(
v
i
,
u
j
)
‍
BLASTBitScore
(
v
i
′
,
u
j
′
)
.
Let N
G
(
v
) be the set of all neighbors of v (N
G
(
v
)
=
{
u
∈
V
G
∣
u
v
∈
E
(
G
)
}); then C
N
c
(
v
i
,
u
j
) forCandidate
c
=
L
A
G
1
,
G
2
(
S
g
1
,
S
g
2
,
M
) is
(7)
C
N
c
(
v
i
,
u
j
)
=
{
(
v
i
′
,
MV
(
v
i
′
,
M
)
)
∣
v
i
′
∈
N
G
1
(
v
i
)
}
.
AnInitial Similarity Bipartite Graph for networks A and B in Figure 1 is shown in Figure 6(a). After creating theInitial Similarity Bipartite Graph (ISBG), we can find just a single mapping for each vertex by finding maximum matching in this graph. The maximum matching can be found by applying the Hungarian algorithm (with polynomial time complexity) on the ISBG [27].(a) TheInitial Similarity Bipartite Graph (ISBG) between networks A and B in Figure 1 (the weights of edges are hidden for simplicity). (b) The ISBG, with duplication of first part. (c) Graph M
1, obtained from first part of duplicated ISBG by performing Hungarian algorithm.
(a)
(b)
(c)As mentioned, this approach can find just a single mapping for each vertex, although it cannot support some evolutionary functions such as duplication and diversion. To support duplication and diversion, we should consider matching of a single vertex from one part into two vertices of other parts in the ISBG. This type of matching is namedDMatch. In other words,DMatchs are paths with length 2 such as P
(
v
i
′
,
v
j
,
v
k
′
) in the ISBG which aligns v
j from one graph into both v
i
′ and v
i
′ from another graph. Here the problem is to find a set ofMatchs andDMatchs from the ISBG where sum of their weights is maximum. This problem is namedMaximum Weighted DMatching. To decrease the size of the solution space of this problem, we decrease the size of edge set of the ISBG by deleting some edges. The above procedure is performed by Algorithms 2 and 3.Algorithm 2:Find Sim
G Graph.
Input:  Initial-similarity-bipartite-graph  S
=
(
S
1
,
S
2
,
E
S
)
Output: Graph Sim
G
(1)  Bipartite-graph  S
D
1
=
S
(2)  for all vertex v
∈
S
1  do
(3)   Duplicate v in S
D
1
(4)  end for
(5)  Bipartite-graph  M
1 = Maximum-Weight-Matching(S
D
1)
(6)  Merge duplicated vertices of S
D
1 in M
1
(7)  Bipartite-graph  S
D
2
=
S
(8)  for all vertex v
∈
S
2  do
(9)   Duplicate v in S
D
2
(10) end for
(11) Bipartite-graph  M
2 = Maximum-Weight-Matching(S
D
2)
(12) Merge duplicated vertices of S
D
2 in M
2
(13) Bipartite-graph  Sim
G
=
M
1
∪
M
2
(14) return  Sim
GAlgorithm 3:Find final alignment.
Input:  Sim
G Graph M
Output: Final Alignment
(1)     for all edge {
v
1
,
v
2
}
∈
M  do
(2)     if  d
e
g(v
1) = 1  and
d
e
g
(
v
2
)
=
1  then
(3)      R
e
s
u
l
t = R
e
s
u
l
t
∪
{
v
1
,
v
2
}
(4)      M = M
∖
{
v
1
,
v
2
}
(5)     end if
(6)    end for
(7)   D
M
a
t
c
h = ϕ
(8)    P
1 = first part of M
(9)    P
2 = second part of M
(10) for all vertex v
∈
P
1  do
(11)   e
1 = first edge connected to v
(12)   e
2 = second edge connected to v  if  d
e
g
(
v
)
>
1
(13)   e
3 = third edge connected to v  if  d
e
g
(
v
)
>
2
(14)   if  d
e
g
(
v
)
=
2  then
(15)    D
M
a
t
c
h
s = D
M
a
t
c
h
s
⋃
(
v, e
1, e
2, weight(e
1) + weight(e
2))
(16)   end if
(17)   if  d
e
g
(
v
)
=
3  then
(18)    D
M
a
t
c
h
s
=
D
M
a
t
c
h
s
⋃
(
v, e
1, e
2, weight(e
1) + weight(e
2))
(19)    D
M
a
t
c
h
s
=
D
M
a
t
c
h
s
⋃
(
v, e
1, e
3, weight(e
1) + weight(e
3))
(20)   D
M
a
t
c
h
s
=
D
M
a
t
c
h
s
⋃
(
v, e
2, e
3, weight(e
2) + weight(e
3))
(21)  end if
(22) end for
(23) SortByWeight (D
M
a
t
c
h
s)
(24) for all  d
m
∈
D
M
a
t
c
h
s  do
(25)  if (d
m
∩
R
e
s
u
l
t
=
ϕ) then
(26)   R
e
s
u
l
t = R
e
s
u
l
t
∪
d
m
(27)  end if
(28) end for
(29) return  R
e
s
u
l
tAlgorithm2 gives the ISBG as input and creates theFinal Similarity Bipartite Graph. In Steps 1–4 of Algorithm 2 all vertices of one part of the ISBG are duplicated and each duplicated vertex is connected to all vertices conjunct to the main vertex with the same weight as shown in Figure 6(b); then the Hungarian algorithm is performed on this graph in Step 5 of Algorithm 2. Obtained bipartite graph is named M
1. The result of these steps for ISBG of Figure 6(a) is shown in Figure 6(c). All duplicated vertices of M
1 are merged together in Step 6 of Algorithm 2. In Steps 7–12 of Algorithm 2, the same process is implemented on the other part of the obtained ISBG and the matching M
2 is obtained. Figures 7(a) and 7(b) illustrate these steps for ISBG of Figure 6(a). Step 13 of Algorithm 2 combines M
1 and M
2 to create Si
m
G as theFinal Similarity Bipartite Braph as shown in Figure 7(c).(a) The ISBG between networksA and B in Figure 1, with duplication of second part. (b) Graph M
2, obtained from second part duplicated ISBG by performing Hungarian algorithm. (c) TheFinal Similarity Bipartite Graph (si
m
G) for networks A and B.
(a)
(b)
(c)It can be proven thatMaximum Weighted Dmatchings of graph Si
m
G are exactly similar toMaximum Weighted Dmatchings of ISBG. So Si
m
G contains all edges ofMaximum Weighted Dmatching and the degree of its vertices is at most 3. For this reason obviously the solution space of theMaximum Weighted DMatching problem on Si
m
G is considerably decreased in comparison with the ISBG.To find the final alignment using the graphSi
m
G, we use a greedy algorithm with polynomial time complexity as shown in Algorithm 3. Algorithm 3 gives theFinal Similarity Bipartite Graph
Si
m
G (obtained by Algorithm 2) as input and matches all pairs of adjacent vertices where degree of both of them is one. For other vertices, Algorithm 3 creates all possibleDmatchs and selects them in a greedy manner. Algorithm 3 utilizes the following steps for all vertices of graph Si
m
G.(1)
If the degree of the vertexv is one and degree of adjacent vertex is also one, these two vertices are assigned to each other.
(2)
If the degree of the vertexv is two and v is adjacent to v
i
′ and v
j
′, the path P
(
v
i
′
,
v
,
v
j
′
) is created as a potentialDmatch.
(3)
If the degree of the vertexv is three and v is adjacent to v
i
′, v
j
′, and v
k
′, potentialDmatchs
P
(
v
i
′
,
v
,
v
j
′
), P
(
v
i
′
,
v
,
v
k
′
), and P
(
v
j
′
,
v
,
v
k
′
) are created.The weight of a givenDMatch can be calculated by the following formula:
(8)
W
P
v
i
′
,
v
,
v
j
′
=
W
(
v
i
,
v
)
+
W
(
v
,
v
j
)
.After creating all potentialDMatchs, we sort them based on their weights; then in a successive rounds we choose the highest weightDMatchs
P
(
v
i
′
,
v
,
v
j
′
) and delete all other edges connected to v
i
′, v, or v
j
′. By this way all assignments are found and finally the local alignment of two graphs is obtained in Steps 24–27 of Algorithm 3. Therefore the output of this algorithm is the final alignment between two given graphs G
1 and G
2. The final alignment between networks A and B in Figure 1 is shown in Figure 8.Figure 8
Final alignment between networksA and B.


## 2.1. Dynamic Programming Algorithm to Align PPI Networks

In alignment of two weighted graphsG
1 and G
2 through dynamic programming technique, we generate all LAs of size one (subgraphs with a single vertex) in the first step. For obtaining LAs of larger subgraphs of G
1, we merge all possible pairs of LA of smaller subgraphs. In other words, for each subgraph of G
1 such as S
g
1, there are several pairs of distinct subgraphs (subgraphs with no common vertices) such as (
T
1
,
T
2
) where S
g
1
=
T
1
∪
T
2. Figure 2 demonstrated the merge process of two sample local alignments of networks A and B of Figure 1. We produce all possible local alignments for S
g
1 such as L
A
G
1
,
G
2
(
S
g
1
,
S
g
2
,
M
) by merging every possible local alignments of T
1 such as L
A
G
1
,
G
2
(
T
1
,
T
1
′
,
M
′
) with every possible local alignment of T
2 such as L
A
G
1
,
G
2
(
T
2
,
T
2
′
,
M
′′
). This process is done iteratively, and finally all local alignments of G
1 including BL
A
G
1
,
G
2
(
G
1
) are obtained.Inspired by dynamic programming technique, we proposeSimple-Align algorithm in Algorithm 1. This algorithm can find all BLAs; however by considering time and memory complexity, this algorithm is not feasible. To overcome this, we use several heuristics to reduce memory and time complexity and propose a new local alignment algorithm,Pin-Align, in next section.Algorithm 1:
Simple-Align algorithm.
Input: Graph G
1(V
1, E
1), Graph G
2(V
2, E
2) such that |
V
1
|
=
n
Output: Local alignment
(1)   Define S as an array of sets with length n
(2)   S
[
1
] = Set of all local alignments of size one
(3)   for  s
i
z
e
=
2 to n  do
(4)    for  i
=
1 to s
i
z
e
-
1  do
(5)     j
=
s
i
z
e
-
i
(6)     for  k
=
1 to |
S
[
i
]
|  do
(7)      for  l
=
1 to |
S
[
j
]
|  do
(8)       L
A  A = k’th element of S
[
i
]
(9)       L
A  B = l’th element of S
[
j
]
(10)     S
[
s
i
z
e
]
=
S
[
s
i
z
e
]
⋃
M
e
r
g
e
(
A
,
B
)
(11)    end for
(12)   end for
(13)  end for
(14) end for
(15) return The LA with highest score among all LAs in S
[
n
]


## 2.2.Pin-Align Algorithm

As explained,Pin-Align uses dynamic programming approach to solve the local network alignment problem and overcome the deficiencies of dynamic programming such as time and space complexity by applying heuristic approach. The steps of thePin-Align algorithm are summarized as follows.(1)
Partition the input graphG
1 into smaller clusters. These clusters are dense subgraphs of G
1. The partitioning is done by using a new clustering algorithm named Hub Clustering. Clusters obtained in this step are namedHub-Clusters.
(2)
For eachH
u
b-C
l
u
s
t
e
r
i,
(a)
create local alignments of size one with BLAST bit score greater than 0, between vertices ofH
u
b-C
l
u
s
t
e
r
i and vertices of G
2; local alignments obtained by this approach are namedCandidates (C
=
L
A
G
1
,
G
2
(
S
g
1
,
S
g
2
,
M
) such that S
g
1 is a subgraph of H
u
b-C
l
u
s
t
e
r
i with size one),
(b)
collect allCandidates of subgraph S
g
1 of G
1 (such as C
=
L
A
G
1
,
G
2
(
S
g
1
,
S
g
2
,
M
)) in a new set calledCandidate-Collection and eachCandidate-Collection is represented by its subgraph of G
1 such as CC
(
S
g
1
);Candidate-Collections obtained for single nodes of G
1 are used as seeds in Step 2(c),
(c)
merge smallCandidate-Collections (seeds) to gain larger ones. Repeat this process continuously to achieve aCandidate-Collection
CC
(
H
u
b-C
l
u
s
t
e
r
i
) as the final result of merging process. Size of aCandidate or aCandidate-Collection is defined by the number of vertices of its subgraph of G
1 and cardinality of aCandidate-Collection is defined as the number of itsCandidates. In this step, eachCandidate-Collection can be merged with severalCandidate-Collections and createCandidate-Collections with larger size. For determining whichCandidate-Collections should be merged together, a new hierarchical clustering is used as a pattern of merging.TheCandidate-Collections ofHub-Clusters are namedFinal-Candidate-Collections.(3)
Based onFinal-Candidate-Collections, find final alignment using similarity graph. This graph is a special weighted bipartite graph where first and second set of vertices of it are shown by V
1 and V
2 which are the set of vertices of G
1 and G
2. The weight of each edge is computed based onFinal-Candidate-Collections.Flowchart ofPin-Align algorithm is presented in Figure 3 and its details are explained by an example on two networks A and B given in Figure 1.Figure 3
Flowchart ofPin-Align algorithm.In Step 1, in order to reduce the search space of the problem, input graphG
1
=
(
V
1
,
E
1
) is clustered into some dense subgraphs and Step 2 of the algorithm runs for each dense subgraph separately. Generally PPI networks are sparse graphs, but they have dense regions containing high degree vertices named hubs. These regions usually contain protein complexes; therefore conserved modules among different PPIs usually exist in these regions.To detect dense subgraphs in the graphG
1, a novel clustering algorithm, calledHub Clustering, is proposed. The importance of hub nodes and density of subgraphs are two major criteria for this clustering method. First, a portion of highly connected vertices are selected as hub nodes. The vertices degree of these nodes is greater than 95
% of other nodes. The hub nodes are considered as the center vertices of dense regions of graph G
1 and are supposed to be initial clusters. For other nodes of G
1, each node is joint to the nearest cluster (the cluster that contains its nearest hub). For this aim, the length of each edge is defined as the negative logarithm of its weight (from adjacency matrix), and then Dijkstra shortest path algorithm [24] is used to find the nearest cluster. The obtained clusters are namedHub-Clusters.In Step 2, each ofHub-Clusters of G
1 (obtained in Step 1) is aligned to G
2. As mentioned, Step 2(a) createsCandidates of size one based on BLAST bit score of vertices of two graphs G
1 and G
2 (BLAST bit score is a normalized score which is calculated by basic local alignment search tool, based on sequence similarity [18]). Figure 4(a) shows BLAST bit scores of proteins of networks A and B.(a) BLAST bit scores for proteins of networksA and B shown in Figure 1. (b) All possibleCandidates of size one of networks A and B. (c) All possibleCandidate-Collections of size one for networks A and B.
(a)
(b)
(c)After that, allCandidates of each vertex of G
1 are collected into aCandidate-Collection with size one as a seed in Step 2(b). In other words,Candidate-Collection of each vertex of G
1 such as S
g
1 contains allCandidates for S
g
1 from G
2 which can be aligned with S
g
1. For example,Candidates of networks A and B of Figure 1 are shown in Figure 4(b) and thoseCandidate-Collections are shown in Figure 4(c).In Step 2(c), two seeds (i.e.,Candidate-Collections
CC
(
S
g
i
) and CC
(
S
g
j
)) are merged in order to produce a new seed (new-CC) where its size is sum of sizes of CC
(
S
g
i
) and CC
(
S
g
j
). Figure 5 illustrates twoCandidate-Collections, C
a
n
d
i
d
a
t
e-C
o
l
l
e
c
t
i
o
n
2 and C
a
n
d
i
d
a
t
e-C
o
l
l
e
c
t
i
o
n
3, of Figure 4(c) and the result of merging them.Figure 5
TwoCandidate-Collections and the result of merging them.The important problem in this step is discovering the feasible combining pattern to find pairs ofCandidate-Collections where merging them generates high scoreCandidate-Collections. In order to find high scoreCandidates and avoid complex searches, combining pattern for mergingCandidate-Collections should produceCandidates with more conserved edges. Hence we use hierarchical clustering as combining patterns [25]. Hierarchical clusters are generally constructed by generating a sequence of partitions where each subcluster belongs to one supercluster in its entity.In hierarchical clustering we should determine how the distance between two clusters is computed. IfS
i
=
(
V
i
′
,
E
i
′
) and S
j
=
(
V
j
′
,
E
j
′
) are subgraphs of G
1
=
(
V
1
,
E
1
), the distance between twoCandidate-Collections
CC
(
S
i
) and CC
(
S
j
) is computed, using the following formula:
(1)
dis
CC
S
i
,
CC
S
j
=
V
i
′
+
V
j
′
∑
v
∈
V
i
′
∑
u
∈
V
j
′
(
a
v
,
u
/
e
v
,
u
)
.
In this equation, a
v
,
u is equal to one if there is an edge between vertices u and v; otherwise it is zero, and e
v
,
u is the negative logarithm of probability of interaction between two proteins v and u in the graph G
1. We use the hierarchical clustering obtained based on formula, as the combining pattern for mergingCandidate-Collections. Cardinality of newCandidate-Collections obtained in higher levels of hierarchical clustering tree is increased exponentially as a result of merging smallerCandidate-Collections, so we have to save theCandidates with highest score and discardCandidates with low scores. In Step 2(c) we use a multiobjective optimization technique for finding the highest scoreCandidates [26]. The highest scoreCandidates are obtained by sortingCandidates based on two criteria, first,Nodes-Scores; next,Structural-Scores. Finally, theCandidates with the highest scores are chosen in each step. Following, we describe this scoring schema.Node-Score.Node-score of eachCandidate
C
=
L
A
G
1
,
G
2
(
S
g
1
,
S
g
2
,
M
) is obtained by using the following equation:
(2)
NodeScore
(
C
)
=
∑
i
=
1
S
g
1
‍
BLASTBitScore
S
g
1
i
,
MV
S
g
1
i
,
M
.
In this equation, i is an iterator on vertices of S
g
1 and S
g
1
i is the ith vertex of S
g
1; MV
(
v
,
M
) indicates a vertex of S
g
2 mapped into v
∈
S
g
1 by the mapping M.Structural-Score. Due to the existence of hubs and small words in biological networks, certainly the network contains bridges. Bridges are considerable edges, which take part in most of the paths (specifically conserved paths) in the networks. Because of the importance of bridges, if S
g
1
=
(
V
1
′
,
E
1
′
) is a subgraph of G
1
=
(
V
1
,
E
1
) and S
g
2
=
(
V
2
′
,
E
2
′
) is a subgraph of G
2
=
(
V
2
,
E
2
), the structural scoring function for eachCandidate
C
=
L
A
G
1
,
G
2
(
S
g
1
,
S
g
2
,
M
) is defined as follows:
(3)
StructuralScore
(
C
)
=
∑
v
∈
V
1
′
‍
∑
u
∈
V
1
′
‍
f
v
×
f
u
α
×
P
G
1
(
v
,
u
)
P
G
2
MV
v
,
M
,
MV
u
,
M
P
G
1
MV
u
,
M
1
-
α
.
In this equation, f
(
i
) shows the number of conserved edges at vertex i in the subgraph S
g
1; α is a constant value between 0 and 1 and shows the importance of adjacent vertices degrees; P
G
(
x
,
y
) is the probability of interaction between protein x and protein y in the network G.As mentioned before, to control the exponential growth of the cardinality ofCandidate-Collections in combining process, we use a multiobjective optimization method on node score and structural score, as optimization objectives. In this way, after creating eachCandidate-Collection among allCandidates obtained in that, we select only a limited number ofCandidates (based on upon scoring functions) and discard others. ObtainedCandidate-Collections ofHub-Clusters are namedFinal-Candidate-Collections which containFinal-Candidates(Candidates ofHub-Clusters).After creating allFinal-Candidate-Collections, in Step 3 ofPin-Align Algorithm, anInitial Similarity Bipartite Graph
ISBG
(
G
1
,
G
2
)
=
(
V
1
,
V
2
,
E
) is created which consists of vertices of G
1
=
(
V
1
,
E
1
) as its first part and vertices of G
2
=
(
V
2
,
E
2
) as its second part, and E is a set of weighted edges between V
1 and V
2. The weight of each edge represents the similarity between its incident vertices. Let C
(
v
i
,
u
j
) be a set of allFinal-Candidates which maps v
i into u
j. In ISBG
(
G
1
,
G
2
), the weight of an edge e
=
{
v
i
,
u
j
}, where v
i
∈
V
1 and u
j
∈
V
2, is equal to zero if |
C
(
v
i
,
u
j
)
|
=
0; otherwise this weight is defined by the following formula:
(4)
W
v
i
,
u
j
=
Nod
e
Sim
v
i
,
u
j
+
Neighborhood
s
Sim
v
i
,
u
j
×
1
|
C
(
v
i
,
u
j
)
|
,
where Nod
e
Sim
(
v
i
,
u
j
) is the similarity between two proteins v
i and u
j and it is calculated by using the following formula:
(5)
Nod
e
Sim
(
v
i
,
u
j
)
=
BLASTBitScore
(
v
i
,
u
j
)
×
C
v
i
,
u
j
,
Neighborhood
s
Sim
(
v
i
,
u
j
) is the similarity between conserved neighborhoods of v
i and u
j and is calculated as follows:
(6)
Neighborhood
s
Sim
(
v
i
,
u
j
)
=
∑
c
∈
C
(
v
i
,
u
j
)
‍
∑
(
v
i
′
,
u
j
′
)
∈
C
N
c
(
v
i
,
u
j
)
‍
BLASTBitScore
(
v
i
′
,
u
j
′
)
.
Let N
G
(
v
) be the set of all neighbors of v (N
G
(
v
)
=
{
u
∈
V
G
∣
u
v
∈
E
(
G
)
}); then C
N
c
(
v
i
,
u
j
) forCandidate
c
=
L
A
G
1
,
G
2
(
S
g
1
,
S
g
2
,
M
) is
(7)
C
N
c
(
v
i
,
u
j
)
=
{
(
v
i
′
,
MV
(
v
i
′
,
M
)
)
∣
v
i
′
∈
N
G
1
(
v
i
)
}
.
AnInitial Similarity Bipartite Graph for networks A and B in Figure 1 is shown in Figure 6(a). After creating theInitial Similarity Bipartite Graph (ISBG), we can find just a single mapping for each vertex by finding maximum matching in this graph. The maximum matching can be found by applying the Hungarian algorithm (with polynomial time complexity) on the ISBG [27].(a) TheInitial Similarity Bipartite Graph (ISBG) between networks A and B in Figure 1 (the weights of edges are hidden for simplicity). (b) The ISBG, with duplication of first part. (c) Graph M
1, obtained from first part of duplicated ISBG by performing Hungarian algorithm.
(a)
(b)
(c)As mentioned, this approach can find just a single mapping for each vertex, although it cannot support some evolutionary functions such as duplication and diversion. To support duplication and diversion, we should consider matching of a single vertex from one part into two vertices of other parts in the ISBG. This type of matching is namedDMatch. In other words,DMatchs are paths with length 2 such as P
(
v
i
′
,
v
j
,
v
k
′
) in the ISBG which aligns v
j from one graph into both v
i
′ and v
i
′ from another graph. Here the problem is to find a set ofMatchs andDMatchs from the ISBG where sum of their weights is maximum. This problem is namedMaximum Weighted DMatching. To decrease the size of the solution space of this problem, we decrease the size of edge set of the ISBG by deleting some edges. The above procedure is performed by Algorithms 2 and 3.Algorithm 2:Find Sim
G Graph.
Input:  Initial-similarity-bipartite-graph  S
=
(
S
1
,
S
2
,
E
S
)
Output: Graph Sim
G
(1)  Bipartite-graph  S
D
1
=
S
(2)  for all vertex v
∈
S
1  do
(3)   Duplicate v in S
D
1
(4)  end for
(5)  Bipartite-graph  M
1 = Maximum-Weight-Matching(S
D
1)
(6)  Merge duplicated vertices of S
D
1 in M
1
(7)  Bipartite-graph  S
D
2
=
S
(8)  for all vertex v
∈
S
2  do
(9)   Duplicate v in S
D
2
(10) end for
(11) Bipartite-graph  M
2 = Maximum-Weight-Matching(S
D
2)
(12) Merge duplicated vertices of S
D
2 in M
2
(13) Bipartite-graph  Sim
G
=
M
1
∪
M
2
(14) return  Sim
GAlgorithm 3:Find final alignment.
Input:  Sim
G Graph M
Output: Final Alignment
(1)     for all edge {
v
1
,
v
2
}
∈
M  do
(2)     if  d
e
g(v
1) = 1  and
d
e
g
(
v
2
)
=
1  then
(3)      R
e
s
u
l
t = R
e
s
u
l
t
∪
{
v
1
,
v
2
}
(4)      M = M
∖
{
v
1
,
v
2
}
(5)     end if
(6)    end for
(7)   D
M
a
t
c
h = ϕ
(8)    P
1 = first part of M
(9)    P
2 = second part of M
(10) for all vertex v
∈
P
1  do
(11)   e
1 = first edge connected to v
(12)   e
2 = second edge connected to v  if  d
e
g
(
v
)
>
1
(13)   e
3 = third edge connected to v  if  d
e
g
(
v
)
>
2
(14)   if  d
e
g
(
v
)
=
2  then
(15)    D
M
a
t
c
h
s = D
M
a
t
c
h
s
⋃
(
v, e
1, e
2, weight(e
1) + weight(e
2))
(16)   end if
(17)   if  d
e
g
(
v
)
=
3  then
(18)    D
M
a
t
c
h
s
=
D
M
a
t
c
h
s
⋃
(
v, e
1, e
2, weight(e
1) + weight(e
2))
(19)    D
M
a
t
c
h
s
=
D
M
a
t
c
h
s
⋃
(
v, e
1, e
3, weight(e
1) + weight(e
3))
(20)   D
M
a
t
c
h
s
=
D
M
a
t
c
h
s
⋃
(
v, e
2, e
3, weight(e
2) + weight(e
3))
(21)  end if
(22) end for
(23) SortByWeight (D
M
a
t
c
h
s)
(24) for all  d
m
∈
D
M
a
t
c
h
s  do
(25)  if (d
m
∩
R
e
s
u
l
t
=
ϕ) then
(26)   R
e
s
u
l
t = R
e
s
u
l
t
∪
d
m
(27)  end if
(28) end for
(29) return  R
e
s
u
l
tAlgorithm2 gives the ISBG as input and creates theFinal Similarity Bipartite Graph. In Steps 1–4 of Algorithm 2 all vertices of one part of the ISBG are duplicated and each duplicated vertex is connected to all vertices conjunct to the main vertex with the same weight as shown in Figure 6(b); then the Hungarian algorithm is performed on this graph in Step 5 of Algorithm 2. Obtained bipartite graph is named M
1. The result of these steps for ISBG of Figure 6(a) is shown in Figure 6(c). All duplicated vertices of M
1 are merged together in Step 6 of Algorithm 2. In Steps 7–12 of Algorithm 2, the same process is implemented on the other part of the obtained ISBG and the matching M
2 is obtained. Figures 7(a) and 7(b) illustrate these steps for ISBG of Figure 6(a). Step 13 of Algorithm 2 combines M
1 and M
2 to create Si
m
G as theFinal Similarity Bipartite Braph as shown in Figure 7(c).(a) The ISBG between networksA and B in Figure 1, with duplication of second part. (b) Graph M
2, obtained from second part duplicated ISBG by performing Hungarian algorithm. (c) TheFinal Similarity Bipartite Graph (si
m
G) for networks A and B.
(a)
(b)
(c)It can be proven thatMaximum Weighted Dmatchings of graph Si
m
G are exactly similar toMaximum Weighted Dmatchings of ISBG. So Si
m
G contains all edges ofMaximum Weighted Dmatching and the degree of its vertices is at most 3. For this reason obviously the solution space of theMaximum Weighted DMatching problem on Si
m
G is considerably decreased in comparison with the ISBG.To find the final alignment using the graphSi
m
G, we use a greedy algorithm with polynomial time complexity as shown in Algorithm 3. Algorithm 3 gives theFinal Similarity Bipartite Graph
Si
m
G (obtained by Algorithm 2) as input and matches all pairs of adjacent vertices where degree of both of them is one. For other vertices, Algorithm 3 creates all possibleDmatchs and selects them in a greedy manner. Algorithm 3 utilizes the following steps for all vertices of graph Si
m
G.(1)
If the degree of the vertexv is one and degree of adjacent vertex is also one, these two vertices are assigned to each other.
(2)
If the degree of the vertexv is two and v is adjacent to v
i
′ and v
j
′, the path P
(
v
i
′
,
v
,
v
j
′
) is created as a potentialDmatch.
(3)
If the degree of the vertexv is three and v is adjacent to v
i
′, v
j
′, and v
k
′, potentialDmatchs
P
(
v
i
′
,
v
,
v
j
′
), P
(
v
i
′
,
v
,
v
k
′
), and P
(
v
j
′
,
v
,
v
k
′
) are created.The weight of a givenDMatch can be calculated by the following formula:
(8)
W
P
v
i
′
,
v
,
v
j
′
=
W
(
v
i
,
v
)
+
W
(
v
,
v
j
)
.After creating all potentialDMatchs, we sort them based on their weights; then in a successive rounds we choose the highest weightDMatchs
P
(
v
i
′
,
v
,
v
j
′
) and delete all other edges connected to v
i
′, v, or v
j
′. By this way all assignments are found and finally the local alignment of two graphs is obtained in Steps 24–27 of Algorithm 3. Therefore the output of this algorithm is the final alignment between two given graphs G
1 and G
2. The final alignment between networks A and B in Figure 1 is shown in Figure 8.Figure 8
Final alignment between networksA and B.


## 3. Results

In this section, we intend to compare our algorithm to other well-known local alignment algorithms (NetworkBLAST [9], MaWISh [10], Graemlin [11], and Graemlin 2.0 [13]), in a way that Graemlin 2.0 compares its results, because it is the only method that compares results of all local alignment tools against KEGG Ortholog (KO) groups [22] on different data sets. The data sets contain the PPI networks data from SNDB [21] for the organism pairs (E. coli,S. typhimurium) and (E. coli,C. crescentus), PPI networks data from DIP [20] for the organism pair (human, mouse), and data from IntAct [19] database for the organism pair (yeast, fly). The comparison is proceeded based on specificity and sensitivity in terms of KO groups introduced in Graemlin 2.0 [13]. In short—as Graemlin 2.0 defined—to uniquely specify an alignment, the mapping should be transitive; that is, if protein A is aligned with proteins B and C, then protein B must also be aligned with protein C. Mathematically, this means that the mapping is an equivalency relation, so groups of aligned proteins are referred to as equivalence classes. An equivalent class is defined as correct if all protein members in the class are in the same KO group. To measure specificity, Graemlin 2.0 computed two metrics:(1)
the fraction of equivalence classes that were correct (C
eq),
(2)
the fraction of nodes that were in correct equivalence classes (C
node),and to measure sensitivity, it computed two metrics:(1)
the total number of nodes that were in correct equivalence classes (C
or),
(2)
the number of equivalence classes that contained 2 species (Tot).As we described in Step 1 of thePin-Align algorithm,Pin-Align chooses some vertices as hubs whose degrees are greater than about 95
% of total vertices. For networksS. typhimurium, C. crescentus, human, andyeast,Pin-Align chooses vertices as hubs in a way that their degrees are greater than 264, 126, 16, and 23, respectively. The reason why these degrees are greater than 95 percent of total vertices degrees is clear from cumulative frequency of their vertices degrees which is shown in charts of Figure 9. For example, in the PPI network ofS. typhimurium the degrees of about 95% of vertices are less than 264, so in this network we choose vertices with degrees greater than 264 as hubs.Figure 9
Cumulative frequency of vertices degrees in networks ofS. typhimurium, C. crescentus, human, andyeast.Table1 showsPin-Align results with different hub degrees. Column two of this table (percentage column) contains different percentages which are used for hub clustering step (Step 1).Table 1
Results ofPin-Align algorithm on four pairs of PPI networks, using different percentages in hub clustering step (Step  1).
Percentage
C
eq
C
node
C
or
Tot
(E.  coli, S.  typhimurium)
60%
0.95
0.93
1651
1779
70%
0.95
0.94
1723
1835
80%
0.95
0.94
1773
1890
90%
0.95
0.94
1782
1905
(E.  coli, C.  crescentus)
60%
0.87
0.84
666
794
70%
0.89
0.86
665
772
80%
0.88
0.85
693
811
90%
0.89
0.87
764
876
(Human, mouse)
60%
0.78
0.72
217
299
70%
0.82
0.78
248
316
80%
0.78
0.73
226
309
90%
0.82
0.78
258
329
(Yeast, fly)
60%
0.87
0.85
258
303
70%
0.89
0.87
280
323
80%
0.91
0.88
350
396
90%
0.91
0.89
416
466The results of the algorithms are demonstrated in Tables2 and 3. In these tables NB stands for NetworkBlast, MW for MaWISh, Gr for Graemlin, and Gr 2.0 for Graemlin 2.0. They show thatPin-Align is the most specific and sensitive aligner in comparison with other alignment tools like NetworkBlast, MaWISh, Graemlin, and Graemlin 2.0. Because Graemlin 2.0 for each of its comparisons to other local aligner removed equivalence classes of its output that did not have a node in common with output of another local aligner, we have different results of Graemlin 2.0. Graemlin 2.0 did this due to considerations of local aligners to nodes in conserved modules and global aligners to all nodes.Table 2
PPI networks from SNDB for the organism pairs (E.  coli, S. typhimurium) and (E.  coli, C. crescentus).
(E. coli,  S. typhimurium)
(E. coli, C. crescentus)
C
eq
C
node
C
or
Tot
C
eq
C
node
C
or
Tot
NB
0.77
0.49
457
1016
0.78
0.50
346
697
Gr2.0
0.95
0.94
627
667
0.79
0.78
447
573
MW
0.84
0.64
1309
2050
0.77
0.54
458
841
Gr2.0
0.97
0.96
1611
1678
0.77
0.76
553
727
Gr
0.80
0.77
985
1286
0.69
0.64
546
847
Gr2.0
0.96
0.95
1157
1217
0.82
0.81
608
750
Pin-Align
0.95
0.94
1782
1905
0.89
0.87
764
876Table 3
PPI networks from DIP and IntAct for the organism pairs (human, mouse) and (yeast, fly).
(Human, mouse)
(Yeast, fly)
C
eq
C
node
C
or
Tot
C
eq
C
node
C
or
Tot
NB
0.33
0.06
65
1010
0.39
0.14
43
306
Gr2.0
0.83
0.81
228
281
0.58
0.58
155
267
MW
0.59
0.36
87
241
0.45
0.37
10
27
Gr2.0
0.88
0.86
181
210
0.90
0.91
20
30
Gr
0.59
0.53
108
203
0.33
0.29
35
122
Gr2.0
0.86
0.84
151
179
0.61
0.61
57
93
Pin-Align
0.82
0.78
258
329
0.91
0.89
416
466In Table2, we use the PPI network data from SNDB for the organism pairs (E. coli,S. typhimurium) and (E. coli,C. crescentus). In Table 3 we use the PPI networks data from DIP and IntAct for the organism pairs (human,mouse) and (yeast,fly).Figure10 shows thatPin-Align also finds more correct equivalence classes than NetworkBlast, MaWISh, Graemlin, and Graemlin 2.0. By considering all the above results and comparingPin-Align to the other algorithms, it is evident thatPin-Align is more accurate in most cases based on the C
eq, C
node, C
or, and Tot measures.Figure 10
The number of correct equivalence classes that are found in alignment of organism pairs (E. coli,S. typhimurium), (E. coli,C. crescentus), (human,mouse), and (yeast,fly) byPin-Align, in comparison with Graemlin 2.0, Graemlin, MaWISh, and NetworkBlast.


## 4. Conclusions

In this paper, we presentedPin-Align, a pairwise local network alignment to improve accuracy of the alignment.Pin-Align algorithm is mainly designed based on the dynamic programming approach and has specificity and sensitivity comparable with existing tools such as NetworkBlast, Graemlin, Graemlin 2.0, and MaWISh. Our novel scoring system is based on bridges which are considerable edges due to the existence of hubs and small words in biological networks which certainly contain bridges. Bridges take part in most of the paths and consequently conserved paths in the networks. In future work, we plan to extend this approach to multiple network alignment.



---

*Source: 393908-2014-11-10.xml*