protein - protein interactions ( ppi ) are of central importance for virtually every process in a living cell .
for example , information about these interactions improves our understanding of diseases and can provide the basis for new therapeutic approaches .
one of fundamental goals of system biology is to understand how proteins in the cell interact with each other .
for example , to find all pairwise interactions for a species with 5000 proteins , one needs to do 12497500 pairwise tests .
high - throughput experimental techniques ( e.g. , yeast two - hybrid and coimmunoprecipitation test ) can be helpful in this case .
integrated probability models are also used to predict the protein - protein interactions [ 1 , 2 ] .
quite a few databases , dip , intact , biogrid , hprd , and intpro , are public available for collecting and storing ppi network data .
researchers [ 1 , 814 ] are trying to identify conserved patterns such as ortholog groups and functional similar pathways / complexes across species using ppi network data .  
the exact solution of identifying conserved regions across species , that is , the network alignment problem , is np - hard [ 1 , 814 ] .
. a powerful way of representing and analyzing all ppi network data is to use network models and classical graph - theoretical approaches [ 16 , 17 ] . in a ppi network ,
each protein is represented as a node and a direct physical interaction between proteins by an edge . when identifying conserved patterns across ppi networks , highly similar sequence proteins ( homologues ) are firstly identified , then conserved interactions are clustered , and finally functional similarities of each cluster should be validated .
an interesting hypothesis is that highly similar sequence proteins ( homologues ) within a species and across species may perform similar functions .
statistical and computational analyses of these networks by combination with gene expression data can be used for inferring biological function categories , gene ontology , orthologs , clusters , and so forth [ 1 , 814 , 18 ] . statistical and comparative analysis of ppi networks across species is proved to be a valuable tool [ 1 , 814 ] .
such analysis provides more information and easier tools beyond traditional sequence - based comparative genomic analyses .
such an analysis can identify conserved interaction regions , predict protein interactions and functions , and provide gene ontology ( go ) enrichment and so forth .
most of previous network alignment tools focus on conserved functional patterns cross species [ 1 , 8 , 11 , 12 ] or on maximizing the overall match between ppi networks globally such as isorank   and isorank - m . the existing tools firstly find the conserved interaction regions by search algorithms and then validate the results by gene annotations such as gene ontology ( go )   or kegg ortholog ( ko ) groups .
we observe that results that are good for one annotation ( ko , e.g. ) may not be good for another ( go ) . also scoring functions that work for one set of parameters of an alignment may not work for others [ 8 ,
researchers are still trying to improve the speed and accuracy of network alignment . in view of this
, we introduce an iterative connected - components based algorithm , hopemap , aiming to improve the speed , scalability , and accuracy of the alignment and also propose a generic scoring system . in this paper , we explore a new approach to comparative analysis of ppi networks with focus on clustering and validating functional homologues ( genome ) with conserved interactions ( interactome ) .
we firstly consider the network alignment to globally identify conserved interaction in the close homologues . by close homologues , we mean proteins in the same homologs are highly similar in terms of sequence similarity , for example , blast e value is much smaller than e. to this end , ko groups   ( and inparanoid   for pairwise ) are used for clustering ortholog groups across species .
even if protein - protein interaction databases continue to grow in size and species coverage , the size of true homologous groups will not increase too much but stay manageable .
for example , the current common number of ko terms for baker 's yeast ( 4738 proteins in ppi network ) and fruit fly ( 7165 proteins in ppi network ) is about 767 .
ko group is a dynamic system that can easily accept new genes once they are identified .
as shown in figure 2 , we propose a graph - based algorithm for the network alignment .
this clustering and alignment algorithm combines information of homolog ( genomic similarity ) , physical interactions conservation , and equivalent functions ( hope ) , and we call our main algorithm hopemap . 

( 1 ) input : graph g = ( v , e ) , start node v0 ( 2 ) index = 0  //
dfs node number counter ( 3 )   s = empty  // an empty stack of nodes(4 )   tarjan ( v0 )  // start a dfs at the start node(5 )   procedure tarjan ( v)(6 )  v.index = index 
// set the depth index for v ( 7 )  v.lowlink = index(8 )  index = index + 1(9 )  s.push ( v )  //
push v on the stack(10 )  for all ( v , v ) in e do  // consider successors of v ( 11 )  if ( v.index is undefined )  // was successor v visited ?
recurse(13 )  v.lowlink = min ( v.lowlink , v.lowlink)(14 )  elseif ( v in s )  //
is v on the stack?(15 )  v.lowlink = min ( v.lowlink , v.index)(16 )  if ( v.lowlink = = v.index )  // is v the root of an scc?(17 )  print 
scc:(18 )  repeat(19 )  v = s.pop(20 )  print v(21 )  until ( v = = v ) 
  ( 1 ) input : graph g = ( v , e ) , start node v0   ( 2 ) index = 0  //
dfs node number counter   ( 3 )   s = empty  // an empty stack of nodes ( 4 )   tarjan ( v0 )  // start a dfs at the start node ( 5 )   procedure tarjan ( v ) ( 6 )  v.index = index  // set the depth index for v   ( 7 )  v.lowlink = index ( 8)  index = index + 1 ( 9 )  s.push ( v )  // push v on the stack ( 10 )  for all ( v , v ) in e do  //
consider successors of v   ( 11 )  if ( v.index is undefined )  // was successor v visited ?  
( 12 )  tarjan ( v )  // recurse ( 13 )  v.lowlink = min ( v.lowlink , v.lowlink ) ( 14 )  elseif ( v in s )  // is v on the stack ? ( 15 )  v.lowlink = min ( v.lowlink , v.index ) ( 16 )  if ( v.lowlink = = v.index )  // is v the root of an scc ? ( 21 )  until ( v = = v ) our contributions may be in threefolds : ( 1 ) developing a fast , accurate , and general tool for the network alignment , which can work for both pairwise and multiple species .
fast means linear computation cost ; accurate means the aligned results are highly correct in terms of known functional annotations ; general means the clustering algorithm is parameter - free and can work for other networks as well . ( 2 ) proposing a generic scoring system , an open system to accept new features and to refine the identified conserved regions across species .
( 3 ) introducing a multiple - validating approach for functional homologues using known annotated orthologs and pathways / complexes .
the existing tools firstly find the conserved interaction regions by search algorithms and then validate the results by gene annotations ( go , ko ) . observing that the size of true orthologs cross species
is small comparing to the total number of proteins in all species , we take a different approach in three steps : starting from the similar orthologous clusters across species , finding conserved interaction regions iteratively with a generic scoring system , and validating results across multiple known functional annotations . using known ortholog clustering results such as ko groups
reduces the computational cost of finding sequence similar proteins . applying connected - components based algorithm
to find conserved region across species assures a fast approach to maximize matches across species ; it is also a parameter - free clustering algorithm , unlike most of existing tools , which need setting different sets of parameters for different alignment .
the generic scoring function is an open system ; currently it combines evolutionary evidence such as genomic , interaction , and functional similarities .
in general , network alignment may be classified using following criterions : in terms of the number of networks aligned : pairwise or multiple;in terms of number of nodes aligned simultaneously : local or global;in terms of guided models : divergence / duplication evolution , neighbouring topology in the ppi networks , and functional categories mips ( or go , ko , orthologs , etc . ) . in terms of the number of networks aligned : pairwise or multiple ; in terms of number of nodes aligned simultaneously : local or global ; in terms of guided models : divergence / duplication evolution , neighbouring topology in the ppi networks , and functional categories mips ( or go , ko , orthologs , etc . ) . 

our tool currently focuses on global pairwise alignment guided by interacting and functional similar homologues .
extending our tool to multiple alignments is easy . the history and some future directions in the network alignment were reviewed in .
alignment of protein - protein interaction networks passed through two generations : in the first generation , conserved pathways / complexes between two species are indentified , often called pairwise alignment .
pathblast   is one of the pioneering works in this field and one of the first generation tools in this line .
networkblast   extends pathblast to align up to three networks and introduces probability model for interactions .
graemlin 1.0 introduces an integration probability model to predict the interactions and can align more than three networks .
above - mentioned tools are also called local alignment because their search algorithms for the conserved regions start from small local regions and then greedily expand . later
, isorank introduces the global alignment concept by adopting google pagerank algorithm idea to the network alignment . comparing to global alignment that finds maximum matches across species ,
another key issue for local search algorithms ( networkblast , networkblast - m , graemlin 1.0 , and mawish ) is that they produce many overlapped subnetworks which need to be filtered .
the paper   applies graph kernels for pairwise alignment , and   extends mawish pairwise alignment . the first generation aligning tools focus on identifying conserved interaction regions across species .
however , the accuracy , scalability , and scoring functions of the first generation tools still have limitations . most of aligned results do not have high sensitivity or specificity in terms of biological relevance
the first generation tools also used very crude measurement for the specificity and sensitivity ; for example , a cluster that has more than three proteins with same complexes ids in mips ( networkblast ) or kegg ( graemlin 1.0 ) is called a pure cluster or correct equivalence class ; and if more than half proteins in a cluster have same go terms , the cluster is called go enrichment . the second generation aligning tools , such as graemlin 2.0 and networkblast - m , are trying to improve both accuracy and speed .
previous tools other than networkblast - m are also called progressive alignment approach with exponential possible representations of every set of potential orthologous proteins , which make them slow and inefficient of using memory .
the computational cost of major algorithm in graemlin 2.0 is claimed to be linear with the number of proteins and ppis in all the species .
our major algorithm is linear with the number of nodes and edges in the alignment graph , which will be introduced later . as reported in graemlin 2.0 , which may be the only one to compare results of all tools against ko groups , the specificity of networkblast , graemlin 1.0 , mawish , isorank , and graemlin 2.0 is varying from species to species with average accuracy ( 42% , 53% , 57% , 70% , and 81% ) .
however , only ko ( graemlin 2.0 ) or go terms ( networkblast - m ) are used in each tool .
it is known that a tool that works fine for one term ( ko or go ) may be not good for another term ( mips funcats , e.g. ) .
we introduce multiple validation through more than one functional annotation ; that is , we align networks using ko groups and validate through go terms and mips   complexes .
networkblast and graemlin 1.0 combine testing and prediction of interaction probabilities in their scoring functions .
notice most of scoring systems need manual parameters tuning , and graemlin 2.0 develops an automatic parameters learning scoring system .
while there are some variations from one tool to another , the major ideas are similar : combing gene - sequence information and ppi network information to find conserved interaction regions across species . generally speaking , firstly similar sequences proteins ( based on blast scores )
are put into equivalence class groups which may have one - to - many proteins from a single species , then alignment tools are used to identify conserved interaction regions across species , and finally ko groups or go terms are used to validate the results .
each ppi network may be represented as an undirected graph g = ( v , e ) where v is the set of nodes and e is the set of edges .
( g may be a weighted graph ; i.e. , a weight measure w(e ) may be associated with each edge e in e ) .
the biological interpretation of network alignment is to find functional orthologs or homologues across different organisms . in analogy with sequence alignment
, local and global network alignment is defined in [ 9 , 13 , 14 ] . in this paper ,
network comparative study or alignment helps to interpret cellular machineries such as identifying common conserved interaction pathways or complexes across two or more species . although the general problem is np - hard , heuristic methods with the combination of sequence , interaction , and functional similarities can be developed to tackle it .
a network alignment graph can be built across two or more species based on protein sequence similarity , interaction conservation , and functional coherence .
the nodes in the alignment graph represent sets of proteins , ideally one from each species and edges for the conserved ppis across the compared species .
the heart of network alignment algorithms is to find the highly conserved interaction regions across homologs among different species . as shown in figure 3 , using ko group for similarity , three nodes alignment graph of species a and b can be built , and each node in the alignment graph has two proteins in this example . then alignment graph can be simplified as a normal graph , and connected - components based graph algorithm therefore can be applied .
once connected components are found in the simple graph , we can go back to alignment graph and original protein interaction network of each species to identify conserved patterns in each species .
we use them as the starting point of alignment to find interactions conserved between orthologs across species .
the results are more biological relevant and can be evaluated through known functional categories or gene ontology . in graph theory ,
a connected component of an undirected graph is a subgraph in which any two vertices are connected to each other by paths , and which is connected to no additional vertices .
especially a graph that is itself connected has exactly one connected component , consisting of the whole graph .
it is straightforward to compute the connected components of a graph in linear time using either breadth - first search or depth - first search . to find all the connected components of a graph , loop through its vertices , starting a new breadth first or depth first search whenever the loop reaches a vertex that has not already been included in a previously found connected component .
our algorithm , called hopemap , can be described as follows ( figure 5 shows the five - step flow of hopemap ) .
obtaining the ppi networks data and preprocessing them , dip , intact , and sndb , and uniprot , are some of ppi network databases .
we need to find all protein pairs that are interacting with each other in a species and store them in a sparse matrix to save space .
all - against - all blast scores for all the species can be obtained for homolog clustering of the next step .
finding highly similar sequences proteins across species . using homolog clustering to identify homolog groups across different species based on all - virus - all blast scores and ortholog annotations . to this end
our approach can use any reliable ortholog annotations available ; it is an open system .
ko groups are one of the best - known functional ortholog group annotations across species .
besides sequence similarity ( homolog ) , all the genes in the same ko groups perform same functions .
once homolog groups are identified across species , a network alignment graph can be built based on them .
the nodes in the graph represent sets of proteins , ideally one from each species in the same homolog group and edges for the conserved ppis across the compared species .
one way of adding edges between node pairs ( a1 , a2 ) and ( a2 , b2 ) is when both ( a1 , b1 ) and ( a2 , b2 ) are directly interacting with each other in their ppi networks .
the major algorithm is based on finding connected components ( clusters ) in the alignment graph .
the basic idea of the connected - component algorithm ( pseudocode 1 ) is a depth - first search begins from a start node .
the strongly connected components form the subtrees of the search tree , the roots of which are the roots of the strongly connected components . the nodes are placed on a stack in the order in which they are visited .
when the search returns from a subtree , the nodes are taken from the stack , and it is determined whether each node is the root of a strongly connected component . if a node is the root of a strongly connected component , then it and all of the nodes are taken off before it forms that strongly connected component .
once connected components ( clusters ) in the alignment graph are identified , our scoring system is used to find high scores subnetworks ( clusters ) .
our scoring functions of clusters combine genomic similarity score , interaction conservation , and functional coherence .
it is a normalized function with values in interval [ 0 , 1 ] , so that it is convenient to compare the scores of different clusters .
the scoring function of a cluster c is defined as 
 ( 1)score(c )  =  w1s(c)+w2i(c)+w3f(c ) , 
 where s(c ) is the sequence similarity score or the average confidence of homolog nodes in cluster c , i(c ) is the interaction conservation coefficient of cluster c , f(c ) is the functional coherence score of cluster c , ( w1 , w2 , w3 ) is the corresponding weight coefficient of s(c ) ,  i(c ) , and f(c ) , and one - third for each is set as the default . 

for each node ( one protein from each species ) of cluster c in the alignment graph , we can find their confidence score based on blast scores or ortholog confidence score as follows : 
 ( 2)s(c)=k=1k=|c|s(k)|c| , 
 where s(k ) is the similarity ( or ortholog ) confidence score of node k in cluster c and |c| is the size of cluster c. normalization of confidence scores can be done as follows : the average blast score of each cluster is defined as the total blast scores of all nodes in a cluster divided by the size of the cluster .
if a node 's blast e value is smaller than the average blast score , its confidence value is set to 1 ; otherwise , its confidence value is set to ratio of the average blast score to its e value .
the confidence score of a cluster in the alignment graph is set to 1 if all nodes of the cluster are in the same known ortholog annotation such as ko groups or inparanoid ; otherwise the confidence score is set to zero .
the conserved interactions are edges connecting all nodes in an identified cluster of the alignment graph .
we use only the ratio of direct interactions conserved in a local cluster ; that is , if all the proteins in a cluster are directly connected , i(c ) is set to 1.0 ; otherwise , i(c ) is set to the portion of the direct interactions conserved in the clusters .
i(c ) is formally defined as 
 ( 3)i(c)=i(c)|c|(|c|1)/2 , 
 where i(c ) is the total number of conserved interactions ( defined previously ) , that is , the total number of edges in cluster c , |c| is the number of nodes in the cluster c , and |c|(|c|  1)/2 is cliqueness measurement of the cluster c ; that is , if cluster c is a clique ( a complete graph ) , then there are ( |c|(|c|  1)/2 ) interactions ( edges ) connecting all nodes . since we are comparing scores of all identified subnetworks , normalization ( similar to the sequence similarity ) may be needed ; that is , we compute the interaction conservation coefficient i(c ) first for all the clusters , and then we normalize the i(c ) over all clusters . if the i(c ) of a cluster is larger than the average i(c ) , the i(c ) is reset as 1.0 ; otherwise , the i(c ) is reset to the ratio of its original value to the average value of all clusters . 
 functional coherence scoring f(c ) : node and edge scoring . known
functional annotations such as go terms , funcats and complexes in mips , pathways / complexes in kegg can be used as functional coherence score of a cluster .
currently , we use set intersection over union of the number of go biological process terms covered in a cluster of a local species as the f(c ) as follows : 
 ( 4)f(c)=intersection(goprocesstermsinc)union(goprocesstermsinc ) . 

the larger the f(c ) , the higher the significance of the cluster c in go process coherence .
normalization similar to the one used in sequence similarity scores can be applied here for all compared species too . 
 statistical significance assessment . to measure the statistical significance of the score functions , for each cluster ( or ortholog pairs ) , we randomly sample n clusters of the same size and compute the corresponding scores .
then we find empirical p value of each cluster using the methods introduced in [ 28 , 29 ] .
typically , the empirical p value can be estimated as p = ( r + 1)/(n + 1 ) where n is the total number of random samples and r is the number of these samples that produce a test statistic greater than or equal to the value for the actual data . finally the score function can be formulated as follows : 
 ( 5)score(c)=w1rs(c)+1ns(c)+1  + w2ri(c)+1ni(c)+1+w3rf(c)+1nf(c)+1 , 
 where ns(c ) is the number of sample clusters ( ortholog pairs ) , rs(c)is the number of clusters which have values larger than s(c ) , and ( ni(c ) , ri(c ) ) and ( nf(c ) , rf(c ) ) are similarly for i(c ) and f(c ) , respectively . for equality and simplicity , one - third
( 1 )  s(c ) currently measures the functional ortholog groups across species using ko groups .
shows how well the nodes in the alignment graph belong to the same functional orthologs .
( 2 )  i(c ) is used to measure the interaction conservation across species . the higher the i(c ) is , the more interaction conservation is in a cluster .
( 3 ) using s(c ) + i(c ) is enough to identify the maximum ( global ) conserved interaction regions across species .
( 4 )  f(c ) currently measures roughly the functional coherence of a cluster in terms of go biological processes .
the higher the f(c ) is , the more significant of the cluster is regarding go terms .
using f(c ) alone , we can filter some clusters with low scores ( e.g. , zeros ) to improve the specificity of all identified clusters regarding functional coherence .
( 5 ) iteration may be needed to improve the results based on the combination of three factors .
since our homolog groups are based on known annotation ko groups , currently we evaluate functional coherence of the identified local clusters in each species using gene ontology ( go ) .
this is part of local alignment and refinement . to this end , go termfinder tool   is used , which computes empirical enrichment p values and corrected values for multiple testing using the false discovery rate procedure .
similar to networkblast - m , to measure the specificity of the results in terms of biological process in go , the percent of process coherent clusters in each species is computed .
the number of distinct go categories covered in all the clusters is used as the sensitivity metric .
other known functional annotations such as funcats and complexes in mips , pathways / complexes in kegg may also be used as multiple validation . after the fourth step , local alignment in each species can be iteratively applied to improve the score of a cluster if necessary . if an identified cluster has score less than a threshold ( e.g. , 0.5 ) , our hopemap algorithm can be used iteratively to refine clusters until the score of each cluster is higher than the threshold . or go biological process terms covered in each cluster can be used as the indicator to keep or remove the cluster . to be more specific
, we can use the intersection over union ( i / u ) number of go biological process terms covered in each cluster as the threshold to keep or remove the cluster regarding go terms . if the value of i / u is zero
only two iterations are currently needed for the convergence . our major algorithm is based on strongly connected components , and it is well known that the computational cost of strongly connected - components algorithm is linear with the number of nodes and edges in the alignment graph [ 31 , 32 ] .
same as the interactome data is incomplete and noisy , the information for the protein / gene sequences , similarity , functional categories , and orthology groups currently is incomplete and inconsistent from databases to databases . even names and ids are not used globally but locally from one database to another .
notice that the number of protein interactions in biogrid is much larger than those in dip ( isorank used both ) .
so more numbers ( quantity ) of interactions conservation found in one tool may not mean that the results are better ( in quality ) than others .
we download the ppi interaction data from dip and the stanford network database ( sndb ) .
we ran pairwise alignments of yeast ( sce ) and fly ( dme ) dip networks , escherichia coli k12 ( eco ) and salmonella typhimurium lt2 ( stm ) sndb networks , and e. coli ( eco ) and caulobacter crescentus ( ccr ) sndb networks .
we also ran a three - way alignment of the yeast ( sce ) , fly ( dme ) , and worm ( cel ) dip networks .
table 2 provides a summary of all ppi networks analyzed in this paper . in table 3
, results of 1 , 117 clusters with node size larger than one , were obtained from the supplementary material of original publication   using networkblast and inparanoid ortholog groups .
the results of 2 hopemap - bestpairs were obtained using the same node data from 117 clusters but choosing 1314 best matching ortholog pairs only ; edges are added between node pairs ( yeast1 , fly1 ) and ( yeast2 , fly2 ) only when there are edges between both yeast pairs ( yeast1 , yeast2 ) and fly pairs ( fly1 , fly2 ) .
results of 3 were obtained using hopemap , the same data from 1 , and similar way as networkblast to add edges in the alignment graph .
the results of 4 , hopemap - ko , were obtained using ko groups as ortholog groups , and no more interactions are added in original ppi networks from dip .
networkblast used different techniques to add edges in the alignment graph , so that its total number of conserved regions is larger than hopemap .
notice that the number of conserved regions is just a crude indicator since it depends on the size of regions .
table 3 shows that specificity and sensitivity in go terms of hopemap is comparable to networkblast , while hopemap is simpler and faster .
using ko groups in hopemap improves the specificity . in table 4 , we use ppi network data from sndb for two pairs , e. coli k12 ( eco)/s .
typhimurium ( stm ) and e. coli k12 ( eco)/c . crescenttus ( ccr ) .
the total number of conserved regions only includes those sizes larger than two for eco / stm , while regions with size larger than one are included for eco / ccr .
the comparison of ko groups against other tools is provided in tables 5 and 6 . in table 5
, we provide specificity comparison in terms of ko groups for different global alignment tools ( comparing to other local alignment tools which are also available in graemlin 2.0 ) .
the metrics of specificity and sensitivity in terms of ko groups are introduced in graemlin 2.0 . in short
, an equivalence class is defined as correct if all protein members in it are in the same ko group .
then the fraction of equivalence classes that were correct is shown as ceq , while the fraction of nodes that were in correct equivalence classes is cnode in table 5 .
other results than hopemap are from original publication of graemlin 2.0 table where gr2.0 is graemlin 2.0 , iso is isorank , and grg is another version of graemlin introduced in graemlin 2.0 . in table 6 , we provide sensitivity comparison in terms of ko groups for different global alignment tools .
same names annotations are used as table 5 . here cor standards for the total number of nodes in correct equivalence classes , and tot is the total number of equivalence classes with r species for r = 2 , 
, n. since hopemap uses ko groups for homologue clustering , the results have higher specificity and sensitivity than other tools .
one observation is that all these measure and calculation of enrichment are imperfect measures of specificity and sensitivity , but they work as rough guides to validate that an aligner is not sacrificing specificity to increase sensitivity or vice versa . in table 7 , we provide alignment comparison of yeast / fly / worm for networkblast , networkblast - m , and hopemap .
the results of networkblast and networkblast - m are from original publication of networkblast - m .
one reason may be that the ppi network data is incomplete for it : only about 3393 ppis are recorded in dip for 3029 proteins of c. elegans ( worm ) . for adding edges in alignment graph , hopemap uses the following rule : for any node pair , node  ( y1 , f1 , w1 ) , and node  ( y2 , f2 , w2 ) , the edge between them added at least two pairs from three species that are directly interacting , and another pair has distance at most two in its original ppi networks .
networkblast and networkblast - m used different techniques to add edges in the alignment graph .
table 7 shows that in term of specificity , hopemap is comparable to networkblast and networkblast - m ( which has higher specificity and sensitivity than graemlin 2.0 as reported in networkblast - m ) .
hopemap is faster than networkblast and networkblast - m . in table 8 , we provide another functional annotation validation . using mips complexes and funcats , we compared the identified clusters of yeast / fly using hopemap - bestpairs in table 3 , where all members in a cluster that are also in mips complexes are counted as 100% coverage ; otherwise the cluster is said not to be covered in mips complexes .
then we find the percent of total clusters identifed by hopemap is also covered in mips complexes and funcat . 

table 9 shows typical running time of hopmap pairwise alignment when using a desktop that has 2  ghz pentium cpu , 1  g byte memory , and 300  g byte hard disk .
based on genome similarity across different species , interactome conservations , and functional coherence , we developed a pairwise network alignment tool , called hopemap , to improve the speed , accuracy , and generality of the alignment .
hopemap is fast ; it is linear in terms of the number of nodes and edges in the alignment graph .
our results show that hopemap has specificity and sensitivity comparable with the existing best - performing tools .
especifically , in terms of go terms ' enrichment , hopemap performs comparably with networkblast , and hopemap has higher specificity and sensitivity in terms of ko groups ' enrichment than the other tools .
 a number of tools for the alignment of protein - protein interaction ( ppi ) networks have laid the foundation for ppi network analysis . 
 most of alignment tools focus on finding conserved interaction regions across the ppi networks through either local or global mapping of similar sequences . 
 researchers are still trying to improve the speed , scalability , and accuracy of network alignment . in view of this 
 , we introduce a connected - components based fast algorithm , hopemap , for network alignment . observing that the size of true orthologs across species is small comparing to the total number of proteins in all species , we take a different approach based on a precompiled list of homologs identified by ko terms . applying this approach to s. cerevisiae ( yeast ) and d. melanogaster ( fly ) , e. coli k12 and s. typhimurium , e. coli k12 and c. crescenttus 
 , we analyze all clusters identified in the alignment . 
 the results are evaluated through up - to - date known gene annotations , gene ontology ( go ) , and kegg ortholog groups ( ko ) . comparing to existing tools , 
 our approach is fast with linear computational cost , highly accurate in terms of ko and go terms specificity and sensitivity , and can be extended to multiple alignments easily . 
1. Introduction
2. Network Alignment Problem Formulation
3. Our Algorithm: HopeMap
4. Results Analysis
5. Conclusion