You will be presented with the full text of a biomedical research paper. Please write an abstract for this paper. Your response should include the abstract and no additional text.

Paper text:
proteins in a 
 highly connected subgraph of a protein interaction network usually share a 
 common function .
therefore , a highly connected subgraph such as clique and 
 near - clique in a protein interaction network can be used to predict the 
 function of uncharacterized proteins in the highly connected subgraph . finding 
 a clique with a maximum size in a graph is an np - hard 
 problem 
  .
there are several heuristic algorithms for the 
 maximum clique problem [ 2 , 3 ] , but most of them focus on finding a complete 
 subgraph ( i.e. , clique ) and can not be used to find near - cliques .
several topological analysis methods have been 
 developed for identifying biologically meaningful groups from protein 
 interaction networks or for assessing the reliability of protein interactions . 
 a recent program called cfinder [ 4 , 5 ] finds overlapping cliques in protein 
 interaction networks .
it allows a protein to belong to more than one clique , but can not find near - cliques .
our study shows that the near - cliques can reveal 
 higher functional coherence than the overlapping cliques .
the primary focus of this study is to find functional 
 groups by identifying cliques and near - cliques in protein interaction networks . 

 can we 
 efficiently find all cliques and near - cliques ? " and  does a dense 
 subgraph such as clique and near - clique indeed represent a functional module or 
 protein complex ? "
this paper presents an algorithm for finding 
 near - cliques and its application to the interaction network of yeast proteins .
a clique is a complete graph 
 g = ( n , e)in which every 
 node is connected to every other node in the graph . in our previous work , we 
 developed a heuristic algorithm and implemented the algorithm in a program 
 called interviewer , which identifies all edge - disjoint cliques ( i.e. , 
 cliques that do not share an edge ) .
our experience with protein interaction networks 
 suggests that a near - clique as well as a clique often represents a biologically 
 meaningful unit such as functional module or protein complex .
a near - clique is 
 almost a clique but is not a clique due to a few missing edges .
we consider 
 near - cliques of the following   basic types , which are biologically meaningful clusters ( see figure 1 ) .
when a 
 protein outside a clique interacts with two or more proteins in the clique , the 
 protein and the clique forms a near - clique . when a 
 clique shares a protein with other cliques , the cliques form a near - clique .
when two or 
 more cliques interact with a common protein outside them and the protein has at 
 least two interactions with each clique , the cliques and the protein form a 
 near - clique .
the near - cliques of types a and c can be refined using 
 the indegree and outdegree of a node ( there is no change to the near - clique of 
 type b ) . for a node 
 x in subgraph 
 g  g , 
 indegree(x , g ) is the number 
 of the edges connecting node 
 x to other nodes 
 in 
 g , and 
 outdegree(x , g ) is the number 
 of edges connecting node 
 x to other nodes 
 that are in 
 g but not in 
 g. we use the definition of a community in a strong 
 sense   to find more near - cliques in a graph .   
a subgraph g 
  is a community 
 in a strong sense if 
 indegree ( x , g ) > outdegree ( x , g ) for every x in g .
the original definition of a strong community misses 
 many near - cliques due to a single node in the communities .
for example , in 
 figure 2a , node 
 x can not belong 
 to a near - clique since 
 indegree(x , g ) = 3 < outdegree(x , g ) = 4 . likewise ,
node 
 x in figure 2b 
 can not belong to a near - clique because indegree 
 ( x , g ) < outdegree ( x , g ) .
thus , nodes with only one edge connected to them and 
 their edges are removed from the graph when we search near - cliques in the 
 graph . in the graph of figure 2a , nodes 
 p , 
 q , 
 r , and 
 s and their edges 
 are removed . after removing them , node 
 x and the 
 existing clique form a near - clique of type a. a cluster 
 that satisfies 
 indegree(x , g )  0.5|g| for every 
 x in g , where 
 |g| is the number 
 of nodes in 
 g ,
the example shown in figure 2b becomes a near - clique since 
 it satisfies 
 indegree ( x , g )  0.5|g| even if it does 
 not satisfy 
 indegree ( x , g ) < outdegree ( x , g ) .
therefore , a near - clique 
 g of basic types 
 a and c should satisfy at least one of the 
 following conditions . 
 

indegree ( x , g )  outdegree ( x , g ) for every 
 x in 
 g.  
 indegree ( x , g )  0.5|g| . 
  

indegree ( x , g )  outdegree ( x , g ) for every 
 x in 
 g.   
 indegree ( x , g )  0.5|g| .
after finding all edge - disjoint cliques first , we 
 identify near - cliques as follows .
more detailed description of finding 
 near - cliques are outlined in algorithms 1 and 2 . in the algorithms ,
assign every 
 node of a clique the index of the clique containing the node .
when a node of 
 a clique has already an assigned clique index , assign the index to all nodes of 
 the clique , and merge two cliques into a near - clique of type 
 b. when a node 
 x outside a 
 clique forms a basic near - clique 
 g of type a due 
 to the interactions with two or more proteins in the clique , and either 
 indegree ( x , g )  outdegree ( x , g ) or 
 indegree i(x , g )  0.5|g| is true , assign 
 the index of the clique to the node.when two or 
 more cliques form a near - clique 
 g due to two or 
 more interactions with a common protein outside the cliques , and either 
 indegree ( x , g )  outdegree ( x , g ) or 
 indegree is i(x , g )    0.5|g| is true , merge 
 the cliques and the protein into a near - clique of type c. a near - clique is 
 formed by selecting nodes with the same clique index ( cidx ) as those 
 nodes with 
 cidx > 0 . 
  
assign every 
 node of a clique the index of the clique containing the node .  
when a node of 
 a clique has already an assigned clique index , assign the index to all nodes of 
 the clique , and merge two cliques into a near - clique of type 
 b.   when a node 
 x outside a 
 clique forms a basic near - clique 
 g of type a due 
 to the interactions with two or more proteins in the clique , and either 
 indegree ( x , g )  outdegree ( x , g ) or 
 indegree i(x , g )  0.5|g| is true , assign 
 the index of the clique to the node .
when two or 
 more cliques form a near - clique 
 g due to two or 
 more interactions with a common protein outside the cliques , and either 
 indegree ( x , g )  outdegree ( x , g ) or 
 indegree is i(x , g )    0.5|g| is true , merge 
 the cliques and the protein into a near - clique of type c. a near - clique is 
 formed by selecting nodes with the same clique index ( cidx ) as those 
 nodes with 
 cidx > 0 .  
since the most relevant processes form a group of 
 proteins of moderate size in biological networks , we obtain near - cliques 
 smaller than the maximum size specified by a user
. that is , when a near - clique 
 bigger than the maximum size is found ( e.g. , near - clique with more than 50 
 nodes ) , it is split into smaller near - cliques ( 3 near - cliques in figure 2c ) . 

when our program finds a big 
 near - clique with the minimum clique size set to 
 k , we rerun the program on the big near - clique with the 
 minimum clique size set to 
 k + 1 to find a new 
 clique and a near - clique with the clique . after removing the new near - clique 
 from the original , big near - clique
, we run the program again with the minimum 
 clique size set to 
 k. the big near - clique shown in figure 2c is split 
 into 3 small near - cliques with at least 4 proteins each .
we tested the algorithms on the data with 8,397 
 interactions between 4,380 yeast proteins , which is the combined data of ito et 
 al .
, uetz et al . , and mips ( http://mips.gsf.de ) with redundant data 
 removed .
to every protein in the near - cliques , we assigned the functional 
 categories of the functional catalog ( funcat ) version 2.0 , which 
 includes 97 functional categories .
there are six 
 levels of hierarchy in the funcat structure . in the data with 8,397 interactions between 4,380 
 yeast proteins
, we found 100 near - cliques with the minimum size of a clique set 
 to 3 and the maximum size of a near - clique set to 40 .
only one near - clique 
 contains more than 40 proteins , and so it was split into 17 small near - cliques , 
 resulting in total 116 near - cliques . figure 3 shows an example of the network 
 of yeast protein interactions with 6 near - cliques .
proteins in each near - clique 
 share at least one function with other proteins within the near - clique . as shown in table 1 , 68 ( 59% ) out of the 116 
 near - cliques have at least one function shared by all the proteins in the 
 near - cliques ( 100% sharing ) , and 39 near - cliques have a function shared by more 
 than 50% of the proteins in the near - cliques , supporting data are 
 available at http://wilab.inha.ac.kr/ppi/homepage.mht . only 
 9 near - cliques have no function shared by 
 > 50% of the 
 proteins in the near - cliques .
as shown in figure 4 , the functional coherence of 
 each near - clique is high .
the functional coherence was computed by the ratios 
 of the number of proteins having a specific functional category to the group 
 size ( i.e. , the number of proteins in the group ) .
interestingly , most near - cliques found by our 
 algorithm belong to multifunctional categories .
for example , two functional 
 categories are common to all the proteins in a near - clique of figure 5 . as 
 shown in table 2 ,
the near - clique identified as group 93 by our program is 
 involved in both stress response ( functional category 32.01 ) and biosynthesis 
 of vitamins , cofactors , and prosthetic groups ( functional category 01.07.01 ) .
so , we compared the near - cliques identified by 
 our algorithms with known yeast protein complexes , which are cataloged in the 
 mips saccharomyces cerevisiae genome database 
 ( http://mips.gsf.de/genre/proj/yeast ) . for each near - clique
, we found a 
 best - matching protein complex by minimizing the probability of a random overlap 
 between the two , using the following equation [ 4 , 5 ] : ( 1)poverlap=(n2k)(nn2n1k)(nn1 ) , 
 where 
 n1 , 
 n2 are the sizes 
 of a known protein complex and a computed module , 
 k is the number 
 of their common proteins , and 
 n is the size of 
 the network .
as shown in table 3 , 65 near - cliques ( 56% of the total 
 116 near - cliques ) identified by our algorithm show a good agreement ( 
 ln(poverlap ) <  14 ) with the 
 protein complexes cataloged in mips . to compare the functional coherence of the groups 
 found by our program with that of cliques found by cfinder , we tested both 
 programs on the same dataset .
75.9% of the groups identified by our program 
 have at least two functional categories shared by all the proteins in the 
 groups , whereas 63.1% of the groups identified by cfinder have at least two 
 functional categories shared by all the proteins in the groups ( table 4 ) .
this result 
 indicates that our program finds groups with stronger functional coherence than 
 cfinder .
table 5 shows the actual running times of our program 
 and cfinder on three datasets of yeast protein interactions .
our program is 
 faster than cfinder on all datasets , and the difference in speed becomes more 
 obvious as the dataset becomes bigger .
identifying 
 hidden topological structures of protein interaction networks often unveil 
 biologically relevant functional groups and structural complexes .
we developed 
 an efficient heuristic algorithm for finding cliques and near - cliques in 
 protein interaction networks . from the interaction data of yeast proteins , the 
 algorithm identified 116 near - cliques .
comparison with the experimental data 
 showed that 59% of the near - cliques have at least one function shared by all 
 the proteins within a near - clique , and that 56% of the near - cliques show a good 
 agreement with known protein complexes , which are cataloged in the mips 
 saccharomyces cerevisiae genome database .
biological processes are often performed by a group of proteins rather than by individual proteins , and proteins 
 in a same biological group form a densely connected subgraph in a protein - protein interaction network . 
 therefore , 
 finding a densely connected subgraph provides useful information to predict the function or protein complex of uncharacterized proteins in the highly connected subgraph . 
 we have developed an efficient algorithm and program for finding cliques and near - cliques in a protein - protein interaction network . 
 analysis of the interaction network of yeast proteins using the algorithm demonstrates that 59% of the near - cliques identified by our algorithm have at least one function shared by all the proteins within a near - clique , and that 56% of the near - cliques show a good agreement with the experimentally determined protein complexes catalogued in mips .