BACKGROUND
recent high-throughput experimental techniques, such as yeast two-hybrid system  <cit>  and mass spectrometry  <cit> , have made remarkable advances in identifying protein-protein interactions on a genome-wide scale.
since the evidence of protein-protein interactions provides insights into the underlying mechanisms of biological processes within a cell, the availability of a large amount interaction data has introduced a new paradigm towards functional characterization of proteins on a system level.
a protein interactome network is structured by the set of genome-wide protein-protein interactions determined in each organism.
a wide range of computational approaches  <cit>  have attempted to analyze the interaction networks effectively for the purpose of predicting protein function or detecting functional modules.
however, unraveling the complex connectivity has been a critical challenge.
the false positive interactions, which typically appear in high-throughput experimental data, and functionally inconsistent interacting pairs  <cit>  have reinforced the complexity.
thus, refining the noisy data and restructuring the complex network into a well-organized data format should be crucial pre-processes to enhance the network analysis.
in recent years, it has been investigated that protein interaction networks are characterized by intrinsic features  <cit> , such as high modularity and hub-oriented structure.
a network comprises a collection of functional modules that are interpreted as sets of proteins participating in the same function  <cit> .
in general, a module is considered as a sub-graph whose nodes are densely connected with each other and sparsely connected with the others.
density-based clustering methods have been proposed to seek densely connected sub-graphs using various density functions  <cit> .
however, they are not able to capture the global patterns of functional organizations from protein interaction networks.
functional modules are typically organized in a recursive manner such that a module includes one or more sub-modules having more specific functions.
hierarchical clustering methods have thus been applied to the networks for finding functional organizations <cit> .
the bottom-up approaches iteratively merge nodes or sub-networks, whereas the top-down approaches recursively divide the network into sub-networks.
however, as a critical drawback, they are typically sensitive to complex connectivity and noisy data.
hubs in a scale-free network  <cit>  play a central role in characterizing its structure.
intramodule hubs  have high connectivity to the members in a module, and intermodule hubs  bridge different modules  <cit> .
previous studies have observed that such hubs in protein interaction networks are essential in terms of functionality  <cit>  and, in particular, intramodule hubs have low evolutionary rates  <cit> .
the concepts of modules and hubs, extending from specific  to general , suggest the potential structure of a hierarchy that might be hidden in complex interaction networks.
how can we then effectively extract the hierarchical structure of proteins from the complex network to reveal the global picture of functional organizations?
in this study, we present a novel method for restructuring a complex interactome network into a hierarchical data format in order to reveal functional hubs and organizations.
our algorithm uses a weighted interaction network as an input.
because the network includes a significant number of false positive connections, the reliability or intensity of interactions should be assessed and assigned into the edges as weights.
for network restructuring, we design a path strength model which proposes the quantification of functional similarity between two proteins.
the interactome network having complex connectivity is then dynamically converted into a hub-oriented tree structure by the definition of path-strength-based centrality.
from the hierarchical structure, we score hub confidence for each node, and generate hierarchically organized clusters of proteins.
unlike degree as a local significance measure, the hub confidence estimates the global significance of nodes.
it is thus capable of selecting hubs that are located in critical positions of the network.
the experimental results demonstrate that the hubs with high confidence are essential for performing functions.
in network topology, they mostly bridge different functional modules.
furthermore, our approach has higher accuracy in identifying functional modules than other hierarchical clustering methods.
methods
path strength model
the path strength s of a path p is defined as the product of the weighted probabilities that each node on p chooses its succeeding node.
the weighted probability from a node vi to vj is the ratio of the weight between vi and vj to the sum of the weights between vi and its directly connected neighbors.
where p = 〈v <dig>  v <dig> …, vn〉wi denotes the weight of the edge between vi and v, which is normalized into the range between  <dig> and  <dig>  dwt represents the shape parameter that indicates the weighted degree of the node vi.
the weighted degree of vi is the sum of the edge weights between vi and its neighbors.
λ is the scale parameter which depends on the specific type, structure and properties of the input network.
to make the problem simple, the scale parameter will be set by  <dig>  based on the assumption that the shape parameter does not force the starting and ending nodes of p, formula  <dig> then becomes:
the path strength of a path p thus has a positive relationship with the weights of the edges on p, and a negative relationship with the weighted degrees of the nodes on p. formula  <dig> also implies that the path strength has an inverse relationship with the length of p because the weighted probability, wi / dwt, is in the range between  <dig> and  <dig>  inclusive.
as the length of p increases, the product of the weighted probability decreases monotonically.
in the same manner, as the average degree of the nodes on p increases, the path strength of p is likely to decrease.
next, we formulate the functional similarity measurement between proteins based on the path strength model.
the functional similarity ℱ between two proteins a and b in an interactome network is described as the maximum path strength between them.
since any node pair selected in a small world network  <cit>  are directly or indirectly connected with a relatively small path length, the maximum path length between them is typically limited.
however, formula  <dig> still has a computational problem when it enumerates all possible paths between a and b. to solve the computational complexity, we restrict the maximal boundary of path length.
we define the k-length path strength sk as the maximum strength of all distinct paths with length k between a and b.
using a user-specified threshold θ to set the maximal boundary of k, the functional similarity ℱ  between a and b is calculated by the maximum k-length path strength.
where l ≤ k ≤ l + θ and l is the shortest path length between a and b. based on the assumption that edge weights represent the likelihood of functional linkage of interacting protein pairs, formula  <dig> measures the potential of functional association between two proteins, directly or indirectly connected in a protein interactome network.
network restructuring
based on the path strength model and functional similarity measurement, we calculate the centrality for each node.
the centrality c of a node a in a network g is defined as the sum of the functional similarity scores between a and the other nodes in v.
formula  <dig> captures not only the nodes centrally located in the network but also the core proteins that functionally have a strong influence on the others.
our strategy for the network restructuring is to place the nodes with higher centrality on the upper level in a hierarchical tree structure.
we define the set of ancestor nodes t of a node a as the nodes whose centrality is greater than the centrality of a.
among the nodes in t, the node that are functionally the most similar with a becomes the parent node p of a.
selecting a parent node for each node by formula  <dig> then efficiently constructs a hierarchical tree structure.
the node having the highest centrality among all the nodes in the network has no parent and becomes the root node.
this hierarchical structure is dynamically converted on network growth, depending on the distribution of the path-strength-based centrality of nodes.
identifying hubs and clustering proteins
we apply the tree structure of a protein interaction network to identify hub proteins.
for each node a, we obtain the set of child nodes d of a.
we then recursively trace down the tree structure starting from a and combine every child node set to produce a set of all descendant nodes la of a
using this formula for all nodes except leaf nodes, we finally generate the list of descendant sets.
according to connectivity patterns, hubs have been categorized into intramodule hubs and intermodule hubs, as discussed.
we here provide a new definition of hubs, called structural hubs.
these hubs are the core nodes to support the hierarchical structure representing a protein interactome network.
the structural hubs are selected by estimation of hub confidence.
the hub confidence h of a node a is calculated by the sum of the functional similarity scores between a and the members of la, divided by the functional similarity score between a and its parent node.
if a is the root node, we use the sum of the functional similarity scores between a and all the other nodes as its hub confidence.
the hub confidence in formula  <dig> quantifies how likely the node is to be a structural hub.
since an edge weight represents the functional consistency between two ending nodes, the structural hubs have a significant role in not only maintaining topology but also functionality.
we finally generate clusters as functional modules from the tree structure.
we iteratively select a structural hub a with the highest hub confidence score and output la as a cluster until the hub confidence of the selected node a reaches a user-specified threshold.
the clusters are hierarchically arranged based on the positions of their hubs in the tree structure.
the schematic view of our approach is illustrated in figure  <dig> using a synthetic network with  <dig> nodes.
in the input network  <dig> , the weight for each edge is described as its thickness.
after the weighted network is restructured to a hierarchy  <dig> , the structural hubs are identified by scoring the hub confidence  <dig> , and the nodes are grouped to reveal hierarchically organized functional modules  <dig> .
in the hierarchical structure, the depth of a node denotes the maximum path length from the node to a leaf node.
the depth of a cluster is then defined as the maximum depth of nodes in the cluster, i.e., the maximum depth of nodes in a depth-k cluster is k. for example, in figure  <dig>  and  <dig> ,  { d, f} is a depth- <dig> cluster, and {e, d, f, g, h} is a depth- <dig> cluster.
in typical, the functional module with a smaller depth is conceptually more specific and topologically denser in the network.
RESULTS
data sources
currently, genome-wide protein-protein interaction data of several model organisms are publicly available in a number ofopen databases, for example, biogrid  <cit> , mips  <cit> , dip  <cit> , mint  <cit>  and intact  <cit> .
they have been mostly generated by high-throughput methods.
however, because of unreliability of the high-throughput experimental data, we tested our algorithm using the core protein-protein interaction data of saccharomyces cerevisiae from dip, which were curated by other biological information such as protein sequences and expression profiles.
they include total  <dig> distinct proteins and  <dig> interactions between them.
since our approach requires a weighted interaction network as an input, we pre-computed the edge weight for each interaction in three different ways.
first, we explored statistical significance of the alternative indirect connections for each pair of interacting proteins.
suppose n and n are the sets of directly connected neighboring nodes of vi and vj.
to estimate the weight wi,j of the interaction between vi and vj, we used p—value from the hypergeometric distribution.
formula  <dig> indicates the probability that at least |n ∩ n| proteins in |n| are included in |n| by random chance.
in other words, it means the probability that two nodes vi and vj have alternative indirect paths with length- <dig>  the weight wi,j of the interaction between vi and vj can be then computed by
next, we applied gene co-expression profiles for interacting proteins.
the gene expression data were obtained from smd  <cit> , and the coherence of expressions was calculated by the pearson coefficient.
finally, we adopted annotations in the go  <cit>  database.
the semantic similarity measure  <cit>  was used to compute the functional similarity of each pair of interacting proteins.
we assessed the edge weights in terms of functional consistency, the ratio of common functions to all distinct functions that the interacting proteins have.
as the functional information of proteins, the annotation data on the 2nd-level functional categories from mips  <cit>  were used.
after arranging all interactions by their weights in descending order, we plotted the cumulative functional consistency with respect to the selected number of interactions in figure  <dig>  comparing to the semantic similarity-based weighting scheme, the approach for statistical significance in connectivity did not select well both of the top 10% of the most functionally consistent interactions and the bottom 20% of the least consistent interactions.
weighting interactions by the co-expression-based method was also unsuccessful in the range between top 10% and 30%, and below 70%.
however, in general, positive relationships are shown between functional consistency and the weights computed by these methods across all the range.
evaluation of path strength model
we evaluated the effectiveness of our path strength model and functional similarity measurement in the weighted interaction network.
for the calculation of functional similarity ℱ , we have to enumerate all k-length paths sk between two proteins a and b for all possible k. however, the impact of sk on s in formula  <dig> significantly decreases with the increment of k. in the experiment with randomly selected  <dig>  protein pairs, the functional similarity rapidly decreases by the increment of path length, and is close to  <dig> with the path length of greater than  <dig>  as shown in figure  <dig>  for efficient computation of functional similarity between a and b, we thus selected the maximum path strength by limiting the maximal k to  where l is the shortest path length between them.
in other words, we considered the paths between two nodes with length- l,  and .
we investigated the relationship between path strength and functional consistency to show whether a stronger path is still functionally more consistent.
we first measured functional similarity for all possible pairs of proteins by formula  <dig>  selected  <dig>  pairs randomly, and then computed the cumulative functional consistency of each selected pair in the same way described above.
at this time, we used the weighted interaction networks produced by the third method integrated with go annotations using the semantic similarity measure.
in the arrangement of the selected protein pairs by their functional similarity in a descending order, the change of cumulative functional consistency was shown in figure  <dig>  the average functional consistency monotonically decreases as more pairs are included.
it indicates that the pair having higher functional similarity on our path strength model are functionally more consistent.
the average functional consistency in figure  <dig> is lower than that in figure  <dig> because all possible paths regardless of their path length were considered in figure  <dig>  whereas only length- <dig> paths  were tested in figure  <dig>  however, the average functional consistency in figure  <dig> is not very low because any two proteins are connected with each other in a few steps in a typical interaction network characterized by the small-world property  <cit> .
the results in figure  <dig> and  <dig> signify that our model is correctly designed to measure functional similarity between two proteins through network connectivity.
topological significance of structural hubs
we implemented the conversion of the weighted interaction network to a hierarchical tree structure by formula  <dig>  we then identified the structural hub proteins based on their hub confidence scores in formula  <dig>  to make topological assessment of the structural hubs, we tested network vulnerability on random and hub attacks.
it has been known that typical scale-free networks are robust on random attacks, but vulnerable on targeted attacks to the hubs.
for this experiment, we observed the fractions of the largest component when we repeatedly disrupted a randomly selected node, a hub with the highest degree and a structural hub with the highest hub confidence score, respectively.
overall, a protein interaction network is more vulnerable on structural hub attacks than random attacks.
it is noticeable that the hub confidence measure is effective at selecting topologically significant hub proteins in complex networks.
in general, hub confidence has a positive relationship with node degree.
however, some low-degree structural hubs with high hub confidence can be detected by our algorithm.
whereas degree is a factor for local significance of nodes in network topology, the hub confidence formula measures the global significance of nodes to select hubs in the hierarchical structure.
biological essentiality of hub proteins
we biologically validated the structural hubs by lethality which implies the essentiality for performing function.
the lethality has been determined by gene knockout experiments.
we obtained the list of lethal proteins from mips  <cit> .
in the same way, we enumerated the nodes by degree and hub confidence in a descending order, and monitored the proportion of lethal proteins for every  <dig> nodes.
in figure  <dig>  we plotted the alteration of cumulative lethality.
in contrast to the result of topological assessment, top  <dig> structural hubs have higher lethality than the same number of degree-based hubs.
in particular, the proportion of lethal proteins in top  <dig> structural hubs is 50% higher than in top  <dig> degree-based hubs.
however, structural hubs in the rank between  <dig> and  <dig> have lower lethality than degree-based hubs.
it indicates that our structural hub confidence measure ranked highly lethal proteins in top  <dig>  and moved down high-degree but non-lethal proteins to the rank between  <dig> and  <dig>
importantly, most structural hub proteins perform several different functions.
we examined functional overlapping rates of the hubs.
among the functional categories in a hierarchy from mips, we extracted the ones on the 3rd-level from the top and their annotations.
we then inspected how many categories each hub protein appears in.
figure  <dig> shows the functional overlapping rates of the proteins ordered by hub confidence.
the average overlapping rate of  <dig>  proteins is around  <dig> .
however, the rate increases to  <dig>  for top  <dig> structural hubs, and becomes even greater than  <dig>  for top  <dig> structural hubs.
this result suggests that, in network topology, structural hubs mostly bridge different functional modules regardless of their degree.
modularity of clusters
we implemented clustering of proteins using the tree structure converted from a protein interaction network, and inspected whether the output clusters are likely to be functional modules.
modularity of a sub-network has been commonly estimated by the ratio of the number of edges within the sub-network to the number of all edges starting from the nodes in the sub-network.
however, in this estimation, the modularity depends on the number of nodes in the sub-network.
for example, suppose a network g has  <dig> nodes.
sub-networks g′ and g″ of g consist of  <dig> and  <dig> nodes, respectively.
a node in g″ has a higher probability having links to the nodes within the same sub-network  and a lower probability having links to the nodes outside of the sub-network , comparing to a node in g′.
we thus normalized the formula of modularity by the probability of a node in the sub-network being linked to the members in the same sub-network.
we grouped the output clusters with regard to their depth, and averaged the normalized modularity for each group.
as already remarked in methods, the depth of a cluster has an inverse relationship with its functional specificity.
it is also expected that a more specific functional module in a hierarchy has higher modularity in network topology, i.e., a sub-module y in a module x has denser intraconnections than x. the experimental result is shown in figure  <dig>  as the cluster depth decreases, the modularity has a monotonic increase.
in particular, it rapidly increases when the depth is less than  <dig>  this result satisfies our expectation of the modularity pattern in a hierarchy.
it strongly implies that the hierarchy structured by our approach corresponds to the functional organizations in a protein interaction network.
to evaluate clustering accuracy, we used the f-measure, which is the harmonic mean of precision and recall.
suppose an output cluster x is mapped to an actual functional modules fi.
recall, which is also called a true positive rate or sensitivity, is the proportion of common members between x and fi to the size of fi.
precision, which is also called a positive predictive value, is the proportion of common members between x and fi to the size of x
for direct comparison of each functional module with clusters in the same level in a hierarchy, the f-measure is an appropriate evaluation method since it gives a higher chance to score high when the functional module has the similar size with a cluster.
as actual functional modules, we used the annotations on the 2nd-level, 3rd-level and 4th-level functions in a hierarchy from mips.
starting from the most general functions on the 1st-level, functions become more specific as the level increases.
then, for each function, we selected a cluster with the best match by f-measure.
we finally calculated the average f-measure across the functions on each level.
table  <dig> shows the clustering accuracy of our network-conversion approach.
for more specific functions, i.e., higher-level functions, we achieved higher accuracy.
it indicates that our approach more accurately generated the small-sized clusters for specific functions.
comparing the accuracy of two competing methods of hierarchical clustering: edge-betweenness algorithm  <cit>  and prodistin  <cit> , our network-conversion approach outperforms the other methods across all levels of functions as shown in table  <dig>  we additionally evaluated the output clusters comparing to protein complexes from mips.
the gap of clustering accuracy between our approach and the competing methods becomes even larger.
CONCLUSIONS
decomposing, converting and synthesizing complex systems are fundamental tasks for modeling their structural behavior.
recently, such approaches in protein interaction networks has been widely attempted to understand biological processes and functional organizations within a cell.
we have studied the methodology for converting a protein interactome network into an effective structure for the purpose of functional knowledge discovery.
for this task, we designed the path strength model and exploited the novel concept of centrality.
the generated hierarchical tree structure can be applied to selecting functionally essential hub proteins and identifying functional modules.
unlike other hierarchical clustering methods, our approach dynamically explores the entire hierarchical structure of proteins in a global view.
all the individual parent-child relationships between proteins in the hierarchy are meaningful and comparable.
the performance of our approach can be more improved by developing the advanced methods, which efficiently integrate a massive amount of current heterogeneous biological data and accurately analyze the reliability of functional associations between interacting proteins.
authors contributions
yrc designed and implemented the method, analyzed the results, and drafted the manuscript.
az coordinated the project, analyzed the results, and revised the final manuscript.
competing interests
the authors declare that they have no competing interests.

 recent high-throughput experimental techniques, such as yeast two-hybrid system and mass spectrometry, have made remarkable advances in identifying protein-protein interactions on a genome-wide scale. since the evidence of protein-protein interactions provides insights into the underlying mechanisms of biological processes within a cell, the availability of a large amount interaction data has introduced a new paradigm towards functional characterization of proteins on a system level. a protein interactome network is structured by the set of genome-wide protein-protein interactions determined in each organism. a wide range of computational approaches have attempted to analyze the interaction networks effectively for the purpose of predicting protein function or detecting functional modules. however, unraveling the complex connectivity has been a critical challenge. the false positive interactions, which typically appear in high-throughput experimental data, and functionally inconsistent interacting pairs have reinforced the complexity. thus, refining the noisy data and restructuring the complex network into a well-organized data format should be crucial pre-processes to enhance the network analysis. in recent years, it has been investigated that protein interaction networks are characterized by intrinsic features, such as high modularity and hub-oriented structure. a network comprises a collection of functional modules that are interpreted as sets of proteins participating in the same function. in general, a module is considered as a sub-graph whose nodes are densely connected with each other and sparsely connected with the others. density-based clustering methods have been proposed to seek densely connected sub-graphs using various density functions. however, they are not able to capture the global patterns of functional organizations from protein interaction networks. functional modules are typically organized in a recursive manner such that a module includes one or more sub-modules having more specific functions. hierarchical clustering methods have thus been applied to the networks for finding functional organizations. the bottom-up approaches iteratively merge nodes or sub-networks, whereas the top-down approaches recursively divide the network into sub-networks. however, as a critical drawback, they are typically sensitive to complex connectivity and noisy data. hubs in a scale-free network play a central role in characterizing its structure. intramodule hubs have high connectivity to the members in a module, and intermodule hubs bridge different modules. previous studies have observed that such hubs in protein interaction networks are essential in terms of functionality and, in particular, intramodule hubs have low evolutionary rates. the concepts of modules and hubs, extending from specific to general, suggest the potential structure of a hierarchy that might be hidden in complex interaction networks. how can we then effectively extract the hierarchical structure of proteins from the complex network to reveal the global picture of functional organizations? in this study, we present a novel method for restructuring a complex interactome network into a hierarchical data format in order to reveal functional hubs and organizations. our algorithm uses a weighted interaction network as an input. because the network includes a significant number of false positive connections, the reliability or intensity of interactions should be assessed and assigned into the edges as weights. for network restructuring, we design a path strength model which proposes the quantification of functional similarity between two proteins. the interactome network having complex connectivity is then dynamically converted into a hub-oriented tree structure by the definition of path-strength-based centrality. from the hierarchical structure, we score hub confidence for each node, and generate hierarchically organized clusters of proteins. unlike degree as a local significance measure, the hub confidence estimates the global significance of nodes. it is thus capable of selecting hubs that are located in critical positions of the network. the experimental results demonstrate that the hubs with high confidence are essential for performing functions. in network topology, they mostly bridge different functional modules. furthermore, our approach has higher accuracy in identifying functional modules than other hierarchical clustering methods. methods path strength model the path strength s of a path p is defined as the product of the weighted probabilities that each node on p chooses its succeeding node. the weighted probability from a node vi to vj is the ratio of the weight between vi and vj to the sum of the weights between vi and its directly connected neighbors. where p = 〈v v …, vn〉wi denotes the weight of the edge between vi and v, which is normalized into the range between and dwt represents the shape parameter that indicates the weighted degree of the node vi. the weighted degree of vi is the sum of the edge weights between vi and its neighbors. λ is the scale parameter which depends on the specific type, structure and properties of the input network. to make the problem simple, the scale parameter will be set by based on the assumption that the shape parameter does not force the starting and ending nodes of p, formula then becomes: the path strength of a path p thus has a positive relationship with the weights of the edges on p, and a negative relationship with the weighted degrees of the nodes on p. formula also implies that the path strength has an inverse relationship with the length of p because the weighted probability, wi / dwt, is in the range between and inclusive. as the length of p increases, the product of the weighted probability decreases monotonically. in the same manner, as the average degree of the nodes on p increases, the path strength of p is likely to decrease. next, we formulate the functional similarity measurement between proteins based on the path strength model. the functional similarity ℱ between two proteins a and b in an interactome network is described as the maximum path strength between them. since any node pair selected in a small world network are directly or indirectly connected with a relatively small path length, the maximum path length between them is typically limited. however, formula still has a computational problem when it enumerates all possible paths between a and b. to solve the computational complexity, we restrict the maximal boundary of path length. we define the k-length path strength sk as the maximum strength of all distinct paths with length k between a and b. using a user-specified threshold θ to set the maximal boundary of k, the functional similarity ℱ between a and b is calculated by the maximum k-length path strength. where l ≤ k ≤ l + θ and l is the shortest path length between a and b. based on the assumption that edge weights represent the likelihood of functional linkage of interacting protein pairs, formula measures the potential of functional association between two proteins, directly or indirectly connected in a protein interactome network. network restructuring based on the path strength model and functional similarity measurement, we calculate the centrality for each node. the centrality c of a node a in a network g is defined as the sum of the functional similarity scores between a and the other nodes in v. formula captures not only the nodes centrally located in the network but also the core proteins that functionally have a strong influence on the others. our strategy for the network restructuring is to place the nodes with higher centrality on the upper level in a hierarchical tree structure. we define the set of ancestor nodes t of a node a as the nodes whose centrality is greater than the centrality of a. among the nodes in t, the node that are functionally the most similar with a becomes the parent node p of a. selecting a parent node for each node by formula then efficiently constructs a hierarchical tree structure. the node having the highest centrality among all the nodes in the network has no parent and becomes the root node. this hierarchical structure is dynamically converted on network growth, depending on the distribution of the path-strength-based centrality of nodes. identifying hubs and clustering proteins we apply the tree structure of a protein interaction network to identify hub proteins. for each node a, we obtain the set of child nodes d of a. we then recursively trace down the tree structure starting from a and combine every child node set to produce a set of all descendant nodes la of a using this formula for all nodes except leaf nodes, we finally generate the list of descendant sets. according to connectivity patterns, hubs have been categorized into intramodule hubs and intermodule hubs, as discussed. we here provide a new definition of hubs, called structural hubs. these hubs are the core nodes to support the hierarchical structure representing a protein interactome network. the structural hubs are selected by estimation of hub confidence. the hub confidence h of a node a is calculated by the sum of the functional similarity scores between a and the members of la, divided by the functional similarity score between a and its parent node. if a is the root node, we use the sum of the functional similarity scores between a and all the other nodes as its hub confidence. the hub confidence in formula quantifies how likely the node is to be a structural hub. since an edge weight represents the functional consistency between two ending nodes, the structural hubs have a significant role in not only maintaining topology but also functionality. we finally generate clusters as functional modules from the tree structure. we iteratively select a structural hub a with the highest hub confidence score and output la as a cluster until the hub confidence of the selected node a reaches a user-specified threshold. the clusters are hierarchically arranged based on the positions of their hubs in the tree structure. the schematic view of our approach is illustrated in figure using a synthetic network with nodes. in the input network, the weight for each edge is described as its thickness. after the weighted network is restructured to a hierarchy, the structural hubs are identified by scoring the hub confidence, and the nodes are grouped to reveal hierarchically organized functional modules. in the hierarchical structure, the depth of a node denotes the maximum path length from the node to a leaf node. the depth of a cluster is then defined as the maximum depth of nodes in the cluster, i.e., the maximum depth of nodes in a depth-k cluster is k. for example, in figure and, { d, f} is a depth- cluster, and {e, d, f, g, h} is a depth- cluster. in typical, the functional module with a smaller depth is conceptually more specific and topologically denser in the network.  data sources currently, genome-wide protein-protein interaction data of several model organisms are publicly available in a number ofopen databases, for example, biogrid, mips, dip, mint and intact. they have been mostly generated by high-throughput methods. however, because of unreliability of the high-throughput experimental data, we tested our algorithm using the core protein-protein interaction data of saccharomyces cerevisiae from dip, which were curated by other biological information such as protein sequences and expression profiles. they include total distinct proteins and interactions between them. since our approach requires a weighted interaction network as an input, we pre-computed the edge weight for each interaction in three different ways. first, we explored statistical significance of the alternative indirect connections for each pair of interacting proteins. suppose n and n are the sets of directly connected neighboring nodes of vi and vj. to estimate the weight wi,j of the interaction between vi and vj, we used p—value from the hypergeometric distribution. formula indicates the probability that at least |n ∩ n| proteins in |n| are included in |n| by random chance. in other words, it means the probability that two nodes vi and vj have alternative indirect paths with length- the weight wi,j of the interaction between vi and vj can be then computed by next, we applied gene co-expression profiles for interacting proteins. the gene expression data were obtained from smd, and the coherence of expressions was calculated by the pearson coefficient. finally, we adopted annotations in the go database. the semantic similarity measure was used to compute the functional similarity of each pair of interacting proteins. we assessed the edge weights in terms of functional consistency, the ratio of common functions to all distinct functions that the interacting proteins have. as the functional information of proteins, the annotation data on the 2nd-level functional categories from mips were used. after arranging all interactions by their weights in descending order, we plotted the cumulative functional consistency with respect to the selected number of interactions in figure comparing to the semantic similarity-based weighting scheme, the approach for statistical significance in connectivity did not select well both of the top 10% of the most functionally consistent interactions and the bottom 20% of the least consistent interactions. weighting interactions by the co-expression-based method was also unsuccessful in the range between top 10% and 30%, and below 70%. however, in general, positive relationships are shown between functional consistency and the weights computed by these methods across all the range. evaluation of path strength model we evaluated the effectiveness of our path strength model and functional similarity measurement in the weighted interaction network. for the calculation of functional similarity ℱ, we have to enumerate all k-length paths sk between two proteins a and b for all possible k. however, the impact of sk on s in formula significantly decreases with the increment of k. in the experiment with randomly selected protein pairs, the functional similarity rapidly decreases by the increment of path length, and is close to with the path length of greater than as shown in figure for efficient computation of functional similarity between a and b, we thus selected the maximum path strength by limiting the maximal k to where l is the shortest path length between them. in other words, we considered the paths between two nodes with length- l, and. we investigated the relationship between path strength and functional consistency to show whether a stronger path is still functionally more consistent. we first measured functional similarity for all possible pairs of proteins by formula selected pairs randomly, and then computed the cumulative functional consistency of each selected pair in the same way described above. at this time, we used the weighted interaction networks produced by the third method integrated with go annotations using the semantic similarity measure. in the arrangement of the selected protein pairs by their functional similarity in a descending order, the change of cumulative functional consistency was shown in figure the average functional consistency monotonically decreases as more pairs are included. it indicates that the pair having higher functional similarity on our path strength model are functionally more consistent. the average functional consistency in figure is lower than that in figure because all possible paths regardless of their path length were considered in figure whereas only length- paths were tested in figure however, the average functional consistency in figure is not very low because any two proteins are connected with each other in a few steps in a typical interaction network characterized by the small-world property. the results in figure and signify that our model is correctly designed to measure functional similarity between two proteins through network connectivity. topological significance of structural hubs we implemented the conversion of the weighted interaction network to a hierarchical tree structure by formula we then identified the structural hub proteins based on their hub confidence scores in formula to make topological assessment of the structural hubs, we tested network vulnerability on random and hub attacks. it has been known that typical scale-free networks are robust on random attacks, but vulnerable on targeted attacks to the hubs. for this experiment, we observed the fractions of the largest component when we repeatedly disrupted a randomly selected node, a hub with the highest degree and a structural hub with the highest hub confidence score, respectively. overall, a protein interaction network is more vulnerable on structural hub attacks than random attacks. it is noticeable that the hub confidence measure is effective at selecting topologically significant hub proteins in complex networks. in general, hub confidence has a positive relationship with node degree. however, some low-degree structural hubs with high hub confidence can be detected by our algorithm. whereas degree is a factor for local significance of nodes in network topology, the hub confidence formula measures the global significance of nodes to select hubs in the hierarchical structure. biological essentiality of hub proteins we biologically validated the structural hubs by lethality which implies the essentiality for performing function. the lethality has been determined by gene knockout experiments. we obtained the list of lethal proteins from mips. in the same way, we enumerated the nodes by degree and hub confidence in a descending order, and monitored the proportion of lethal proteins for every nodes. in figure we plotted the alteration of cumulative lethality. in contrast to the result of topological assessment, top structural hubs have higher lethality than the same number of degree-based hubs. in particular, the proportion of lethal proteins in top structural hubs is 50% higher than in top degree-based hubs. however, structural hubs in the rank between and have lower lethality than degree-based hubs. it indicates that our structural hub confidence measure ranked highly lethal proteins in top and moved down high-degree but non-lethal proteins to the rank between and importantly, most structural hub proteins perform several different functions. we examined functional overlapping rates of the hubs. among the functional categories in a hierarchy from mips, we extracted the ones on the 3rd-level from the top and their annotations. we then inspected how many categories each hub protein appears in. figure shows the functional overlapping rates of the proteins ordered by hub confidence. the average overlapping rate of proteins is around. however, the rate increases to for top structural hubs, and becomes even greater than for top structural hubs. this result suggests that, in network topology, structural hubs mostly bridge different functional modules regardless of their degree. modularity of clusters we implemented clustering of proteins using the tree structure converted from a protein interaction network, and inspected whether the output clusters are likely to be functional modules. modularity of a sub-network has been commonly estimated by the ratio of the number of edges within the sub-network to the number of all edges starting from the nodes in the sub-network. however, in this estimation, the modularity depends on the number of nodes in the sub-network. for example, suppose a network g has nodes. sub-networks g′ and g″ of g consist of and nodes, respectively. a node in g″ has a higher probability having links to the nodes within the same sub-network and a lower probability having links to the nodes outside of the sub-network, comparing to a node in g′. we thus normalized the formula of modularity by the probability of a node in the sub-network being linked to the members in the same sub-network. we grouped the output clusters with regard to their depth, and averaged the normalized modularity for each group. as already remarked in methods, the depth of a cluster has an inverse relationship with its functional specificity. it is also expected that a more specific functional module in a hierarchy has higher modularity in network topology, i.e., a sub-module y in a module x has denser intraconnections than x. the experimental result is shown in figure as the cluster depth decreases, the modularity has a monotonic increase. in particular, it rapidly increases when the depth is less than this result satisfies our expectation of the modularity pattern in a hierarchy. it strongly implies that the hierarchy structured by our approach corresponds to the functional organizations in a protein interaction network. to evaluate clustering accuracy, we used the f-measure, which is the harmonic mean of precision and recall. suppose an output cluster x is mapped to an actual functional modules fi. recall, which is also called a true positive rate or sensitivity, is the proportion of common members between x and fi to the size of fi. precision, which is also called a positive predictive value, is the proportion of common members between x and fi to the size of x for direct comparison of each functional module with clusters in the same level in a hierarchy, the f-measure is an appropriate evaluation method since it gives a higher chance to score high when the functional module has the similar size with a cluster. as actual functional modules, we used the annotations on the 2nd-level, 3rd-level and 4th-level functions in a hierarchy from mips. starting from the most general functions on the 1st-level, functions become more specific as the level increases. then, for each function, we selected a cluster with the best match by f-measure. we finally calculated the average f-measure across the functions on each level. table shows the clustering accuracy of our network-conversion approach. for more specific functions, i.e., higher-level functions, we achieved higher accuracy. it indicates that our approach more accurately generated the small-sized clusters for specific functions. comparing the accuracy of two competing methods of hierarchical clustering: edge-betweenness algorithm and prodistin, our network-conversion approach outperforms the other methods across all levels of functions as shown in table we additionally evaluated the output clusters comparing to protein complexes from mips. the gap of clustering accuracy between our approach and the competing methods becomes even larger.  decomposing, converting and synthesizing complex systems are fundamental tasks for modeling their structural behavior. recently, such approaches in protein interaction networks has been widely attempted to understand biological processes and functional organizations within a cell. we have studied the methodology for converting a protein interactome network into an effective structure for the purpose of functional knowledge discovery. for this task, we designed the path strength model and exploited the novel concept of centrality. the generated hierarchical tree structure can be applied to selecting functionally essential hub proteins and identifying functional modules. unlike other hierarchical clustering methods, our approach dynamically explores the entire hierarchical structure of proteins in a global view. all the individual parent-child relationships between proteins in the hierarchy are meaningful and comparable. the performance of our approach can be more improved by developing the advanced methods, which efficiently integrate a massive amount of current heterogeneous biological data and accurately analyze the reliability of functional associations between interacting proteins. authors contributions yrc designed and implemented the method, analyzed the results, and drafted the manuscript. az coordinated the project, analyzed the results, and revised the final manuscript. competing interests the authors declare that they have no competing interests. 
this algorithm measures functional similarity between proteins based on the path strength model, and reveals a hub-oriented tree structure hidden in the complex network. protein-protein interactions play a key role in biological processes of proteins within a cell. our experimental results in the yeast protein interactome network demonstrate that the selected hubs are essential proteins for performing functions. unlike previous hierarchical clustering methods, this approach dynamically explores the hierarchical structure of proteins in a global view. a wide range of computational approaches have been applied to interactome network analysis for uncovering functional organizations and pathways. elucidating the structural roles of modules and hubs is a critical step in complex interactome network analysis. we propose a novel approach to convert the complex structure of an interactome network into hierarchical ordering of proteins. in this study, we systematically analyzed complex interactome network structures for retrievingfunctional information. it is well-applicable to the interactome networks in high-level organisms because of its efficiency and scalability. in network topology, they have a role in bridging different functional modules. decomposing, converting, and synthesizing complex interaction networks are fundamental tasks for modeling their structural behaviors. we score hub confidence and identify functional modules in the tree structure of proteins, retrieved by our algorithm. furthermore, our approach has high accuracy in identifying functional modules hierarchically distributed. it has been investigated that protein interaction networks are typically characterized by intrinsic topological features: high modularity and hub-oriented structure.
 protein-protein interactions play a key role in biological processes of proteins within a cell. recent high-throughput techniques have generated protein-protein interaction data in a genome-scale. a wide range of computational approaches have been applied to interactome network analysis for uncovering functional organizations and pathways. however, they have been challenged because ofcomplex connectivity. it has been investigated that protein interaction networks are typically characterized by intrinsic topological features: high modularity and hub-oriented structure. elucidating the structural roles of modules and hubs is a critical step in complex interactome network analysis.  we propose a novel approach to convert the complex structure of an interactome network into hierarchical ordering of proteins. this algorithm measures functional similarity between proteins based on the path strength model, and reveals a hub-oriented tree structure hidden in the complex network. we score hub confidence and identify functional modules in the tree structure of proteins, retrieved by our algorithm. our experimental results in the yeast protein interactome network demonstrate that the selected hubs are essential proteins for performing functions. in network topology, they have a role in bridging different functional modules. furthermore, our approach has high accuracy in identifying functional modules hierarchically distributed.  decomposing, converting, and synthesizing complex interaction networks are fundamental tasks for modeling their structural behaviors. in this study, we systematically analyzed complex interactome network structures for retrievingfunctional information. unlike previous hierarchical clustering methods, this approach dynamically explores the hierarchical structure of proteins in a global view. it is well-applicable to the interactome networks in high-level organisms because of its efficiency and scalability. 1– november ieee international conference on bioinformatics and biomedicine washington, dc, usa 