BACKGROUND
systems biology focuses on the study of complex interactions in biological systems, rather than the study of individual molecules such as dna, rna, proteins and metabolites  <cit> .
one of the goals of systems biology is understanding the structures of all molecules and their interactions in a system level.
therefore major challenges are understanding the dynamic structures of small molecules and determining their functions in a living cell.
various types of biological interactions have been expressed in networks, which include transcriptional regulatory networks, signaling pathways, metabolic networks and protein-protein interaction  networks.
biological networks share some of structural properties of other complex networks, or have specific features of scale-free and small-world effect  <cit> .
however, the properties have been questioned by lacroix et al.
<cit>  with a number of reasons including the incompleteness of networks and inconsistent link generation for the graphs.
therefore, the analysis extends to other network properties such as network clusters and network motifs.
as biological networks are massive and the size is still increasing, dividing the network into a number of clusters helps reveal specific local properties.
network motif, as another concept describing local properties of a network, is defined as a small connected subgraph appearing frequently and uniquely in a network.
similar to a protein sequence motif, network motif is defined as a over-repeated pattern, but it requires much more computation as the process involves isomorphic testing and repeated processes for uniqueness determination.
network alignment  <cit>  and network querying  <cit>  are analogous to network motifs, but while network motifs are defined with only structural information, network alignment and network querying require both of the topological and biological information.
previous network motif discovery algorithms include exact counting and approximation algorithms: exhaustive recursive search   <cit> , enumerate subgraphs   <cit>  and compact topological motifs  <cit>  are exact counting algorithms.
for efficient detection, several approximation algorithms have been provided including edge sampling   <cit> , randomized version of esu from a search tree   <cit> , and tree-filtering search which is nemofinder <cit> .
furthermore, parallel search algorithms have been developed to realize feasible exact counting algorithms  <cit> .
network motifs are used for many applications in biological networks.
feed-forward-loop  and bifan network motifs are identified as the typical patterns in different types of biological networks  <cit> .
przulj et al.
<cit>  used network motifs as a relative graphlet frequency distance to distinguish different protein-protein interaction networks.
also motif frequencies are exploited as classifiers for network model selection  <cit> .
milo et al.
<cit>  studied that networks of different biological and technological domains have been classified into different superfamilies on the basis of motif significance profiles.
to predict protein-protein interactions, albert i. and albert r.  <cit>  used network motifs successfully.
in the study by conant and wagner  <cit> , network motifs in transcriptional regulatory networks are not evolutionary conserved while network motifs in ppi networks are evolutionary related.
on the other hand, network motifs are extended to 'motif modes' each of which has a certain topology and a specific functional property  <cit> .
through a number of network motif applications, however, we notice several problems regarding the biological meanings of network motifs, on top of the computational challenge for the detection.
first, the biological quality of network motifs are not validated thoroughly.
a network motif is selected only by its structural uniqueness and just small number of instances of the type are biologically exemplified.
second, only small portion of network motif instances are used for applications and others are ignored.
third, non-motifs, that is, structurally insignificant subgraphs, have not been analyzed in any studies, which are filtered out before applying to any applications.
fourth, it is still questionable what the network motifs really represent in biological networks.
as we believe that the biological quality of network motifs are also significant, we define a biological network motif in this paper.
throughout this paper, we refer a network motif as a structural network motif to distinguish it from a biological network motif.
unlike structural network motifs, biological network motifs are biologically significant small connected subgraphs regardless of the structure.
the biological significance is unspecified in the definition, as it will be assigned flexibly by a goal of the application.
we introduce edgego-bnm, edgebetweenness-bnm, nmf-bnm, nmfgo-bnm and voltage-bnm algorithms for efficient discovery of biological network motifs, and design new evaluation measures named, 'motifs included in complex', 'motifs included in functional module' and 'go term clustering score'.
our algorithms compete with existing algorithms including esu, rand-esu and mfinder, and the performance are compared based on the new measures introduced in this paper.
the main idea for our algorithms is to reduce the number of subgraphs to search by removing a number of edges from the original network and, at the same time, increase the discovery rate for biological network motifs.
experimental results with a couple of s. cerevisiae ppi networks demonstrate that edgego-bnm and edgebetweenness-bnm algorithms perform better than other algorithms in most of the measures.
in addition, we show that all of our algorithms are applicable to the discovery of structural network motifs as well.
the work has three contributions to the study of network motifs: 1)we question biological meanings of network motifs which have not been focused by existing detection algorithms.
new motif search algorithms and evaluation measures are developed based on these questions.
2)we design several algorithms combining the topological and biological information in a network.
the algorithms further enrich existing algorithms in a biological context.
3)we develop a number of evaluation measures which qualify biological importance of network motifs.
as we know of, this is the first time to suggest systematical evaluation measures for network motifs.
with these contributions, we hope that our work gives some guidelines for the researches of network motifs in biological networks.
RESULTS
in this paper, we define biological network motifs as biological meaningful network motifs and develop edgego-bnm,edgebetweenness-bnm, nmf-bnm, nmfgo-bnm and voltage-bnm algorithms for an efficient detection of biological network motifs.
for clarification, traditional network motifs are referred as structural network motifs throughout this paper.
the performance of each algorithm is compared based on three evaluation measures such as 'motifs included in complex', 'motifs included in functional module', 'go  term clustering score' which we design to assess biological quality of network motifs.
detail description of algorithms and evaluation measures are described in the "methods."
data sets
we test the performance of each algorithm with a couple of ppi of s. cerevisiae .
we download a yeast core data, referred to 'scere20101010' from dip database  <cit>  which has  <dig>  proteins and  <dig>  interactions and call this as dip core network.
a network of  <dig> proteins and  <dig>  with high confidence level of interactions, introduced as a high-throughput data in  <cit>  and obtained from the authors of  <cit> , is also used in this experiment.
as it was conventionally referred to y2k, it is called y2k network.
since the increase of network motif size boosts the computational time and the number of motifs exponentially, we set the size of subgraphs as four to five for practical experiments.
there are  <dig> types of isomorphic graphs for undirected 4-node subgraphs and  <dig> types for undirected 5-node subgraphs.
undirected 4-node subgraph types are labeled using nauty program  <cit>  as appeared in figure  <dig>
comparison of the algorithms against different evaluation measures
we first enumerate all subgraphs of size four or five with esu algorithm  <cit>  and evaluate them with the evaluation measures introduced in this paper and name the experiment as an esu.
then we run edgego-bnm, edgebetweenness-bnm, nmf-bnm, nmfgo-bnm and voltage-bnm algorithms and measure them with the same evaluation measures.
furthermore, we add experiments with two existing approximation algorithms; rand-esu and mfinder.
rand-esu searches subgraphs in a tree structure and it skips over some of the branches during its search.
mfinder randomly picks edges until it reaches the desired number of subgraphs.
esu algorithm enumerates all subgraphs and all other algorithms produce roughly 30% of total subgraphs by adjusting parameters.
additionally, we run fanmod  <cit> , which is a software implementing esu, and investigate the topological properties for each type of subgraph in order to observe the relationships between biological network motifs and structural network motifs.
table  <dig> compares the performances of  <dig> different algorithms for 4-node biological network motifs from dip core network, accessed by the following biological measures;'motifs included in complex', 'motifs included in functional module' and 'go term clustering scores for bp, mf and cc.'
the results of esu, rand-esu and mfinder algorithms are also provided as well for comparison purpose.
the best result for each measure is marked as bolded in the table.
edgebetweenness-bnm algorithm provides highest rates for 'motifs included in complex' measure, but edgego-bnm algorithm produces overall the best values compared to others.
it is reasonable for the edgego-bnm and nmfgo-bnm algorithms have good scores for go term clustering score measures as they include go term information.
however, it is interesting to see that edgebetweenness-bnm algorithm provides relatively good scores for all of the evaluation measures when this algorithm considers only topological property of the network.
this suggests that the structural property helps infer meaningful biological information as well.
we provide the results with 5-node biological network motifs as well in table  <dig>  similar to the results in table  <dig>  edgebetweennes-bnm algorithm is the best for the 'motifs included in complex' term and edgego-bnm is best for the rest of measures.
edgebetweenness-bnm performs best in 'motif included in complex' measure while edgego-bnm performs best in other measures.
edgebetweenness-bnm performs best in 'motif included in complex' measure while edgego-bnm pe forms best in other measures.
to see if the results are consistent with other network, we search biological network motifs in the y2k network as well.
the results are shown in table  <dig> of 4-node subgraph and table  <dig> of 5-node subgraph.
consistent with dip core network, edgego-bnm algorithm provides overall good scores except 'motifs included in complex' term and 'mf go term clustering score'.
edgebetweenness-bnm algorithm is superior for the 'motifs included in complex' term too.
it is interesting to see that nmfgo-bnm shows good scores as well in the y2k network, which is because that nmf tends to produce better results with smaller data set.
it is also appealing that the random-edge-selection algorithm  beats the random-vertex-select algorithm .
this implies that edges are more important aspect for explaining its biological meanings.
edgebetweenness-bnm performs best in 'motif included in complex' measure.
nmfbo-bnm performs best on 'mf' and 'cc clustering score' measures.
edgego-bnm performs best in the 'motif included in functional module measure 'bp, cc clustering score' measures.
however all the algorithms perform poorly in 'mf clustering score' measure, with less than  <dig>
edgebetweenness-bnm performs best in 'motif included in complex' measure while edgego-bnm performs best in other measures.
relationship between biological and structural network motifs
we also investigate the relationship between structural network motifs and biological network motifs in this work.
table  <dig> is the table generated by fanmod  <cit>  to observe the statistical properties of each 4-node subgraph type in the dip core network.
the first column is the label for each type generated by nauty program  <cit>  and figure  <dig> shows shape for each label of subgraph.
second column indicates the percentage of each type appears in the dip core network and the next two columns show the average frequencies and standard deviation of each type, out of  <dig>   <dig> randomized graphs.
last two columns of z-score and p-value show the structural statistics of each type.
as a subgraph type of z-score larger than  <dig>  or p-value smaller than  <dig>  is a network motif, in dip core network, the five types of c^, cn, cf, c~, and cr are network motifs.
figure  <dig> shows relative frequencies for each subgraph types, where the horizonal axis lists all six types and vertical axis indicates its relative frequency.
each line refers to a result of each algorithm, differentiated by colors.
all of the algorithms except esu reduce the total number of subgraph search to 30%, but the relative frequencies are almost same as those of esu.
in fact, when we plug each of the reduced network, which is the by-product of each algorithm, in fanmod, the same five types of subgraphs  are detected as network motifs.
it proves that our algorithms are applicable to find structural network motifs as well, but more efficiently.
each type of 4-node subgraph shows its significance based on its structural uniqueness.
the label is generated by nauty program  <cit>  and the corresponding shape is shown in figure  <dig>  all types except cr are structural network motifs by definition.
we analyze y2k network as well to see a relevance of structural network motif and biological network motif.
table  <dig> generated by fanmod identifies top three subgraphs as network motifs, labeled c~, c^ and cn.
similar to dip core network, all of the algorithms preserve relative frequencies for each type as appeared in figure  <dig> and fanmod confirms that the same three types are still the structural network motifs in the reduced y2k networks as well.
each type of 4-node subgraph shows its significance based on its structural uniqueness.
the label is generated by nauty program  <cit>  and the corresponding shape is shown in figure  <dig>  in this network, the first three types are detected as network motifs.
biological significance for biological network motifs
we provide one example which demonstrates that edgego-bnm is especially good for discovering biological network motifs included in protein functional modules.
this example also shows that structurally non-motifs cannot be ignored as many of the instances have biological significance.
table  <dig> shows the recall value of 4-node biological network motifs included in a 'rrna processing' functional module in yeast, based on different subgraph type and algorithms.
we exactly count the numbers of motifs included in 'rrna processing' with esu algorithm first.
then all other algorithms are compared with the recall in equation .
except esu, all algorithms only search 30% of subgraphs in the original network.
however, edgego-bnm recovers over 90% of motifs included in functional module.
we note that the non-motif types of cr, cf and cr have a number of instances for this functional match, indicating structural uniqueness is insufficient to discover its biological significance.
recall = discovered number of motifs included in a ’rrna processing’ with the algorithmtrue number of motifs included in a rrna processing
in table  <dig>  the first column lists all the algorithms conducted in this paper, and the other columns show the recall of subgraphs included in 'rrna processing' functional module according to each subgraph type.
the 'rrna processing' functional module consists of  <dig> proteins in the yeast.
all algorithms except esu search only 30% of subgraphs out of the total subgraphs searched with esu algorithm but edgego-bnm recovers over 90% of subgraphs included in 'rrna processing'.
furthermore, we observe that although the cr, cf, cr are structural network non-motifs, about 50% of subgraphs included into the 'rrna processing' are these non-motifs.
this example shows that even non-motifs also have biological meanings, therefore the structural network motif defined by its structural uniqueness is insufficient to explain biological meanings.
CONCLUSIONS
in this paper, we provide new approaches to finding network motifs in biological networks.
structural network motifs are defined as frequently and uniquely repeated small connected subgraph in a network.
however, motivated by several issues brought up while a number of network motif applications are investigated, we propose to find biologically meaningful network motifs.
hence, we define biological network motifs as biologically meaningful k-node subgraphs, develop a number of algorithms for efficient detection of biological network motifs and introduce new evaluation measures.
the algorithms reduce the number of subgraph search and increase the detection rates of biological network motifs at the same time.
the algorithms are categorized into two classes: edge-removing algorithms and network clustering algorithms.
edgego-bnm and edgebetweenness-bnm are algorithms which remove a number of edges based on go term and edge betweenness score, respectively.
nmf-bnm, nmfgo-bnm and voltage-bnm algorithms partition the network based on its topological property or go term relevance.
all the algorithms introduced in this paper improve existing algorithms for high quality structural network motif detection.
we also introduce a number of evaluation measures which measure biological significance of each subgraph: 'motifs included in complex', 'motifs included in functional module' and 'go term clustering score.'
biological meanings of those biological network motifs are assigned based on these evaluation measures.
we ran the algorithms on two ppi network of s. cerevisiae, and compared them with our new measures.
an existing exhaustive search and other two existing approximation algorithms are also provided to be compared with our algorithms.
edgego-bnm shows overall good results in all the measures, but edgebetweenness-bnm is the best in the 'motifs included in complex' measure.
the works in this paper can be studied further.
currently, the parameters of various algorithms in this paper are adjusted only to obtain a desired number of subgraphs.
in near future, various impacts of the parameters on the results should be investigated.
besides the parameters, the balance between topological and biological information will be an important factor for a better algorithm.
on the other hand, current evaluation measures are limited to ppi networks.
comprehensive evaluation measures should be designed to apply various types of biological networks.
meanwhile, the work should be extended to weighted or direct networks for more comprehensive analysis of biological network motifs.

 systems biology focuses on the study of complex interactions in biological systems, rather than the study of individual molecules such as dna, rna, proteins and metabolites. one of the goals of systems biology is understanding the structures of all molecules and their interactions in a system level. therefore major challenges are understanding the dynamic structures of small molecules and determining their functions in a living cell. various types of biological interactions have been expressed in networks, which include transcriptional regulatory networks, signaling pathways, metabolic networks and protein-protein interaction networks. biological networks share some of structural properties of other complex networks, or have specific features of scale-free and small-world effect. however, the properties have been questioned by lacroix et al. with a number of reasons including the incompleteness of networks and inconsistent link generation for the graphs. therefore, the analysis extends to other network properties such as network clusters and network motifs. as biological networks are massive and the size is still increasing, dividing the network into a number of clusters helps reveal specific local properties. network motif, as another concept describing local properties of a network, is defined as a small connected subgraph appearing frequently and uniquely in a network. similar to a protein sequence motif, network motif is defined as a over-repeated pattern, but it requires much more computation as the process involves isomorphic testing and repeated processes for uniqueness determination. network alignment and network querying are analogous to network motifs, but while network motifs are defined with only structural information, network alignment and network querying require both of the topological and biological information. previous network motif discovery algorithms include exact counting and approximation algorithms: exhaustive recursive search, enumerate subgraphs and compact topological motifs are exact counting algorithms. for efficient detection, several approximation algorithms have been provided including edge sampling, randomized version of esu from a search tree, and tree-filtering search which is nemofinder. furthermore, parallel search algorithms have been developed to realize feasible exact counting algorithms. network motifs are used for many applications in biological networks. feed-forward-loop and bifan network motifs are identified as the typical patterns in different types of biological networks. przulj et al. used network motifs as a relative graphlet frequency distance to distinguish different protein-protein interaction networks. also motif frequencies are exploited as classifiers for network model selection. milo et al. studied that networks of different biological and technological domains have been classified into different superfamilies on the basis of motif significance profiles. to predict protein-protein interactions, albert i. and albert r. used network motifs successfully. in the study by conant and wagner, network motifs in transcriptional regulatory networks are not evolutionary conserved while network motifs in ppi networks are evolutionary related. on the other hand, network motifs are extended to'motif modes' each of which has a certain topology and a specific functional property. through a number of network motif applications, however, we notice several problems regarding the biological meanings of network motifs, on top of the computational challenge for the detection. first, the biological quality of network motifs are not validated thoroughly. a network motif is selected only by its structural uniqueness and just small number of instances of the type are biologically exemplified. second, only small portion of network motif instances are used for applications and others are ignored. third, non-motifs, that is, structurally insignificant subgraphs, have not been analyzed in any studies, which are filtered out before applying to any applications. fourth, it is still questionable what the network motifs really represent in biological networks. as we believe that the biological quality of network motifs are also significant, we define a biological network motif in this paper. throughout this paper, we refer a network motif as a structural network motif to distinguish it from a biological network motif. unlike structural network motifs, biological network motifs are biologically significant small connected subgraphs regardless of the structure. the biological significance is unspecified in the definition, as it will be assigned flexibly by a goal of the application. we introduce edgego-bnm, edgebetweenness-bnm, nmf-bnm, nmfgo-bnm and voltage-bnm algorithms for efficient discovery of biological network motifs, and design new evaluation measures named,'motifs included in complex','motifs included in functional module' and'go term clustering score'. our algorithms compete with existing algorithms including esu, rand-esu and mfinder, and the performance are compared based on the new measures introduced in this paper. the main idea for our algorithms is to reduce the number of subgraphs to search by removing a number of edges from the original network and, at the same time, increase the discovery rate for biological network motifs. experimental results with a couple of s. cerevisiae ppi networks demonstrate that edgego-bnm and edgebetweenness-bnm algorithms perform better than other algorithms in most of the measures. in addition, we show that all of our algorithms are applicable to the discovery of structural network motifs as well. the work has three contributions to the study of network motifs: 1)we question biological meanings of network motifs which have not been focused by existing detection algorithms. new motif search algorithms and evaluation measures are developed based on these questions. 2)we design several algorithms combining the topological and biological information in a network. the algorithms further enrich existing algorithms in a biological context. 3)we develop a number of evaluation measures which qualify biological importance of network motifs. as we know of, this is the first time to suggest systematical evaluation measures for network motifs. with these contributions, we hope that our work gives some guidelines for the researches of network motifs in biological networks.  in this paper, we define biological network motifs as biological meaningful network motifs and develop edgego-bnm,edgebetweenness-bnm, nmf-bnm, nmfgo-bnm and voltage-bnm algorithms for an efficient detection of biological network motifs. for clarification, traditional network motifs are referred as structural network motifs throughout this paper. the performance of each algorithm is compared based on three evaluation measures such as'motifs included in complex','motifs included in functional module','go term clustering score' which we design to assess biological quality of network motifs. detail description of algorithms and evaluation measures are described in the "methods." data sets we test the performance of each algorithm with a couple of ppi of s. cerevisiae. we download a yeast core data, referred to'scere20101010' from dip database which has proteins and interactions and call this as dip core network. a network of proteins and with high confidence level of interactions, introduced as a high-throughput data in and obtained from the authors of, is also used in this experiment. as it was conventionally referred to y2k, it is called y2k network. since the increase of network motif size boosts the computational time and the number of motifs exponentially, we set the size of subgraphs as four to five for practical experiments. there are types of isomorphic graphs for undirected 4-node subgraphs and types for undirected 5-node subgraphs. undirected 4-node subgraph types are labeled using nauty program as appeared in figure comparison of the algorithms against different evaluation measures we first enumerate all subgraphs of size four or five with esu algorithm and evaluate them with the evaluation measures introduced in this paper and name the experiment as an esu. then we run edgego-bnm, edgebetweenness-bnm, nmf-bnm, nmfgo-bnm and voltage-bnm algorithms and measure them with the same evaluation measures. furthermore, we add experiments with two existing approximation algorithms; rand-esu and mfinder. rand-esu searches subgraphs in a tree structure and it skips over some of the branches during its search. mfinder randomly picks edges until it reaches the desired number of subgraphs. esu algorithm enumerates all subgraphs and all other algorithms produce roughly 30% of total subgraphs by adjusting parameters. additionally, we run fanmod, which is a software implementing esu, and investigate the topological properties for each type of subgraph in order to observe the relationships between biological network motifs and structural network motifs. table compares the performances of different algorithms for 4-node biological network motifs from dip core network, accessed by the following biological measures;'motifs included in complex','motifs included in functional module' and'go term clustering scores for bp, mf and cc.' the results of esu, rand-esu and mfinder algorithms are also provided as well for comparison purpose. the best result for each measure is marked as bolded in the table. edgebetweenness-bnm algorithm provides highest rates for'motifs included in complex' measure, but edgego-bnm algorithm produces overall the best values compared to others. it is reasonable for the edgego-bnm and nmfgo-bnm algorithms have good scores for go term clustering score measures as they include go term information. however, it is interesting to see that edgebetweenness-bnm algorithm provides relatively good scores for all of the evaluation measures when this algorithm considers only topological property of the network. this suggests that the structural property helps infer meaningful biological information as well. we provide the results with 5-node biological network motifs as well in table similar to the results in table edgebetweennes-bnm algorithm is the best for the'motifs included in complex' term and edgego-bnm is best for the rest of measures. edgebetweenness-bnm performs best in'motif included in complex' measure while edgego-bnm performs best in other measures. edgebetweenness-bnm performs best in'motif included in complex' measure while edgego-bnm pe forms best in other measures. to see if the results are consistent with other network, we search biological network motifs in the y2k network as well. the results are shown in table of 4-node subgraph and table of 5-node subgraph. consistent with dip core network, edgego-bnm algorithm provides overall good scores except'motifs included in complex' term and'mf go term clustering score'. edgebetweenness-bnm algorithm is superior for the'motifs included in complex' term too. it is interesting to see that nmfgo-bnm shows good scores as well in the y2k network, which is because that nmf tends to produce better results with smaller data set. it is also appealing that the random-edge-selection algorithm beats the random-vertex-select algorithm. this implies that edges are more important aspect for explaining its biological meanings. edgebetweenness-bnm performs best in'motif included in complex' measure. nmfbo-bnm performs best on'mf' and'cc clustering score' measures. edgego-bnm performs best in the'motif included in functional module measure'bp, cc clustering score' measures. however all the algorithms perform poorly in'mf clustering score' measure, with less than edgebetweenness-bnm performs best in'motif included in complex' measure while edgego-bnm performs best in other measures. relationship between biological and structural network motifs we also investigate the relationship between structural network motifs and biological network motifs in this work. table is the table generated by fanmod to observe the statistical properties of each 4-node subgraph type in the dip core network. the first column is the label for each type generated by nauty program and figure shows shape for each label of subgraph. second column indicates the percentage of each type appears in the dip core network and the next two columns show the average frequencies and standard deviation of each type, out of randomized graphs. last two columns of z-score and p-value show the structural statistics of each type. as a subgraph type of z-score larger than or p-value smaller than is a network motif, in dip core network, the five types of c^, cn, cf, c~, and cr are network motifs. figure shows relative frequencies for each subgraph types, where the horizonal axis lists all six types and vertical axis indicates its relative frequency. each line refers to a result of each algorithm, differentiated by colors. all of the algorithms except esu reduce the total number of subgraph search to 30%, but the relative frequencies are almost same as those of esu. in fact, when we plug each of the reduced network, which is the by-product of each algorithm, in fanmod, the same five types of subgraphs are detected as network motifs. it proves that our algorithms are applicable to find structural network motifs as well, but more efficiently. each type of 4-node subgraph shows its significance based on its structural uniqueness. the label is generated by nauty program and the corresponding shape is shown in figure all types except cr are structural network motifs by definition. we analyze y2k network as well to see a relevance of structural network motif and biological network motif. table generated by fanmod identifies top three subgraphs as network motifs, labeled c~, c^ and cn. similar to dip core network, all of the algorithms preserve relative frequencies for each type as appeared in figure and fanmod confirms that the same three types are still the structural network motifs in the reduced y2k networks as well. each type of 4-node subgraph shows its significance based on its structural uniqueness. the label is generated by nauty program and the corresponding shape is shown in figure in this network, the first three types are detected as network motifs. biological significance for biological network motifs we provide one example which demonstrates that edgego-bnm is especially good for discovering biological network motifs included in protein functional modules. this example also shows that structurally non-motifs cannot be ignored as many of the instances have biological significance. table shows the recall value of 4-node biological network motifs included in a'rrna processing' functional module in yeast, based on different subgraph type and algorithms. we exactly count the numbers of motifs included in'rrna processing' with esu algorithm first. then all other algorithms are compared with the recall in equation. except esu, all algorithms only search 30% of subgraphs in the original network. however, edgego-bnm recovers over 90% of motifs included in functional module. we note that the non-motif types of cr, cf and cr have a number of instances for this functional match, indicating structural uniqueness is insufficient to discover its biological significance. recall = discovered number of motifs included in a ’rrna processing’ with the algorithmtrue number of motifs included in a rrna processing in table the first column lists all the algorithms conducted in this paper, and the other columns show the recall of subgraphs included in'rrna processing' functional module according to each subgraph type. the'rrna processing' functional module consists of proteins in the yeast. all algorithms except esu search only 30% of subgraphs out of the total subgraphs searched with esu algorithm but edgego-bnm recovers over 90% of subgraphs included in'rrna processing'. furthermore, we observe that although the cr, cf, cr are structural network non-motifs, about 50% of subgraphs included into the'rrna processing' are these non-motifs. this example shows that even non-motifs also have biological meanings, therefore the structural network motif defined by its structural uniqueness is insufficient to explain biological meanings.  in this paper, we provide new approaches to finding network motifs in biological networks. structural network motifs are defined as frequently and uniquely repeated small connected subgraph in a network. however, motivated by several issues brought up while a number of network motif applications are investigated, we propose to find biologically meaningful network motifs. hence, we define biological network motifs as biologically meaningful k-node subgraphs, develop a number of algorithms for efficient detection of biological network motifs and introduce new evaluation measures. the algorithms reduce the number of subgraph search and increase the detection rates of biological network motifs at the same time. the algorithms are categorized into two classes: edge-removing algorithms and network clustering algorithms. edgego-bnm and edgebetweenness-bnm are algorithms which remove a number of edges based on go term and edge betweenness score, respectively. nmf-bnm, nmfgo-bnm and voltage-bnm algorithms partition the network based on its topological property or go term relevance. all the algorithms introduced in this paper improve existing algorithms for high quality structural network motif detection. we also introduce a number of evaluation measures which measure biological significance of each subgraph:'motifs included in complex','motifs included in functional module' and'go term clustering score.' biological meanings of those biological network motifs are assigned based on these evaluation measures. we ran the algorithms on two ppi network of s. cerevisiae, and compared them with our new measures. an existing exhaustive search and other two existing approximation algorithms are also provided to be compared with our algorithms. edgego-bnm shows overall good results in all the measures, but edgebetweenness-bnm is the best in the'motifs included in complex' measure. the works in this paper can be studied further. currently, the parameters of various algorithms in this paper are adjusted only to obtain a desired number of subgraphs. in near future, various impacts of the parameters on the results should be investigated. besides the parameters, the balance between topological and biological information will be an important factor for a better algorithm. on the other hand, current evaluation measures are limited to ppi networks. comprehensive evaluation measures should be designed to apply various types of biological networks. meanwhile, the work should be extended to weighted or direct networks for more comprehensive analysis of biological network motifs. 
we provide new approaches to finding network motifs in biological networks. however, we believe that the biological quality of network motifs is also very important. molecular level of biological data can be constructed into system level of data as biological networks. we believe that our work gives some guidelines of network motifs research for the biological networks. we define biological network motifs as biologically significant subgraphs and traditional network motifs are differentiated as structural network motifs in this paper. experimental results show that edgego-bnm and edgebetweenness-bnm perform better than existing algorithms and all of our algorithms are applicable to find structural network motifs as well. our algorithms efficiently detect biological network motifs and further improve existing algorithms to find high quality structural network motifs, which would be impossible using existing algorithms. the performances of the algorithms are compared based on our new evaluation measures in biological contexts. we develop five algorithms, namely, edgego-bnm, edgebetweenness-bnm, nmf-bnm, nmfgo-bnm and voltage-bnm, for efficient detection of biological network motifs, and introduce several evaluation measures including motifs included in complex, motifs included in functional module and go term clustering score in this paper. network motifs are defined as over-represented small connected subgraphs in networks and they have been used for many biological applications.
 molecular level of biological data can be constructed into system level of data as biological networks. network motifs are defined as over-represented small connected subgraphs in networks and they have been used for many biological applications. since network motif discovery involves computationally challenging processes, previous algorithms have focused on computational efficiency. however, we believe that the biological quality of network motifs is also very important.  we define biological network motifs as biologically significant subgraphs and traditional network motifs are differentiated as structural network motifs in this paper. we develop five algorithms, namely, edgego-bnm, edgebetweenness-bnm, nmf-bnm, nmfgo-bnm and voltage-bnm, for efficient detection of biological network motifs, and introduce several evaluation measures including motifs included in complex, motifs included in functional module and go term clustering score in this paper. experimental results show that edgego-bnm and edgebetweenness-bnm perform better than existing algorithms and all of our algorithms are applicable to find structural network motifs as well.  we provide new approaches to finding network motifs in biological networks. our algorithms efficiently detect biological network motifs and further improve existing algorithms to find high quality structural network motifs, which would be impossible using existing algorithms. the performances of the algorithms are compared based on our new evaluation measures in biological contexts. we believe that our work gives some guidelines of network motifs research for the biological networks. 12- july biocomp - the international conference on bioinformatics and computational biology las vegas, nv, usa 