BACKGROUND
development of algorithms for comparing various kinds of biological data is one of the important topics in bioinformatics and systems biology.
methods for comparison of dna and/or protein sequences have been extensively studied and have been applied to analyses of real sequence data quite successfully.
due to increased interests in systems biology, extensive studies have recently been done on comparison of biological networks.
for comparison of metabolic networks, ogata et al.
developed a method based on clustering  <cit> , tohsato et al.
extended a multiple sequence alignment technique to multiple alignment of metabolic pathways using a scoring scheme based on ec  numbers  <cit> , pinter et al.
applied a tree matching technique to alignment of metabolic pathways  <cit> , and wernicke and rasche developed a simple backtracking algorithm utilizing the local diversity property  <cit> .
for comparison of protein-protein interaction networks, kelley et al.
developed pathblast using dynamic programming  <cit> , liang et al.
developed netalign using a clique-based method for computing maximal common subgraphs  <cit> , li et al.
developed mnaligner using integer quadratic programming  <cit> , singh et al.
developed isorank algorithm based on google's pagerank method  <cit> , and zaslavskiy et al.
developed a gradient ascent-based method and a message passing-based method  <cit> .
on the other hand, data compression methods have been applied to comparison of large sequence data  <cit>  and protein structure data  <cit> .
since it is still difficult to compare global structures of large biological networks and data compression-based methods can be applied to comparison of large-scale sequence data, it is reasonable to try to apply data compression methods to comparison of biological networks.
in this paper, we propose such methods.
in order to apply data compression to biological networks, data compression methods for graphs are required.
for compression of graphs, adler and mitzenmacher developed a method based of huffman coding of vertices  <cit> , peshkin developed graphitour based on iterative contractions of identical edges  <cit> , and cook and holder developed subdue based on contraction of frequent subgraphs and mdl  principle  <cit> , which was further extended to edif for lossless compression by yang et al.
<cit> .
however, the method by adler and mitzenmacher does not seem to be useful for comparison of networks because it does not make much use of structural information.
in graphitour, the uniqueness of compression results is not guaranteed because there is some ambiguity in selection of overlapping edges , which is not suitable for comparison of network structures.
this point is also unclear in edif and subdue.
therefore, we develop in this paper novel graph compression methods for which it is guaranteed that two isomorphic graphs are compressed in the same way.
using these compression methods, we measure the similarity of two networks by means of the universal similarity metric  proposed by li et al.
<cit> .
usm is defined using kolmogorov complexity which represents the amount of information contained in data, and is obtained by removing redundant parts maximally.
therefore, kolmogorov complexities are approximated by compression sizes.
we apply the proposed methods to comparison of metabolic networks, and compare the results with those of graphitour.
the results of hierarchical clustering for several organisms suggest that the proposed methods outperforms graphitour, and can adequately measure the similarities between metabolic networks.
methods
graph compression method
since our proposed methods are based on graphitour, we briefly review the graphitour algorithm  <cit> .
graphitour is based on iterative contractions of identical edges.
in order to efficiently contract edges, graphitour selects edges appearing most frequently, and solves an instance of maximum cardinality matching problem, which finds as many edges as possible such that no two edges share a common vertex.
procedure compressedge
input: undirected graph g with labeled vertices v and edges e ;
output: induced compression rules r and compressed graph;
begin
r := ∅;
s := {l} for each label l ∈ l;
while |e| > 0
ε := { ∈ e|  =  where , l <dig> ≥ l2};
ε := {ε| no two edges in ε share a common vertex};
if ε = ∅ then return ;
εmost := {ε ∈ ε| |ε| ≥ |ε| for all ε ∈ ε};
selectε such that s ∪ s <s ∪ s
or  ∪ s = s ∪ s and  < ) for all ε ∈ εmost,
where l <dig> ≥ l <dig>  l <dig> ≥ l4;
add a new label ln to l such that ln >l for all l ∈ l;
s := s ∪ s;
r = r ∪ {ln ← };
for each edge e ∈ ε
substitutee with a new vertex labeled with ln;
return ;
end
this proposed algorithm avoids contraction of edges which share a common vertex.
in the example of figure  <dig>  our algorithm does not choose edges whose endpoints are 'a' and 'b', instead chooses the second candidate edges whose endpoints are 'a' and 'a', and obtains the graph of  as the result.
it should be noted that the proposed algorithm does not solve the maximum cardinality matching problem because it selects only edges such that all edges with the same labels do not share a common vertex.
however, it is not sufficient to uniquely determine contracted edges because there can be more than one set which has the same number of edges, that is, |εmost| >  <dig>  therefore, we introduce a total order to sets of labels to determine the priority of edges.
each edge has a pair of labels  corresponding to two endpoints of the edge.
let s <dig> and s <dig> be sets of labels.
we can define a total order for s <dig> and s <dig> as follows.
first, we sort s <dig> and s <dig> by descending order, respectively.
we compare i-th elements  , of s <dig> and s <dig>  and define s <dig> <s <dig> if  < and  =  hold for some i. the proposed algorithm selects edges with the smallest set of labels from εmost according to the total order.
for example, if we compare s <dig> = {l <dig>  l3} with s <dig> = {l <dig>  l2} under l <dig> <l <dig> <l <dig>  s <dig> and s <dig> are sorted as  and , respectively, and we have s <dig> <s <dig>
when edges with  are contracted, a new label ln is added to l, where ln >l for all l  ∈ l. in computational experiments, morgan index  <cit>  based on graph structures is assigned to each vertex.
however, new added labels themselves do not reflect the original graph structure.
therefore, in order to make effective use of the total order of original labels, we introduce a set of labels for each label l, s , which consists of only original labels.
then, s  is defined to be s  ∪ s  when  is substituted with ln.
the algorithm compares s  ∪ s with s  ∪ s  before comparing edges of  and .
for example, for the graph of figure 1d, the algorithm selects edges with  as contracted edges because it appears most frequently.
however, if there is another edge with  than shown in figure 1d, edges of  and  are compared.
we suppose that 'a'<'b'<'c'<'aa' and 'aa' was obtained by contracting edges with .
then, the corresponding sets to  and , s <dig> = s ∪ s = {'a','a','b'} and s <dig> = s ∪ s = {'b','b'}, are compared, sorted as {'b','a','a'} and {'b','b'}, respectively, and we have s <dig> <s <dig>  then, edges with  are selected, and contracted to vertices with a new label 'aab', where 'aab'>'aa' and s  = s  ∪ s = {'a','a','b'}.
extension to contraction of multiple edges
in the previous algorithm, identical edges are contracted at each iteration.
in this section, we propose another algorithm, which we call compressvertices, to contract identical sets of multiple connected edges.
in order to uniquely determine the contracted sets of connected edges, we must introduce a total order to a set of edges.
for that purpose, we apply degree sequence  <cit> , which is defined to be the non-increasing sequence of degrees of vertices.
for example, the degree sequence of figure 1a is .
moreover, in order to distinguish labels of vertices, we introduce the non-increasing sequence of pairs of the degree and the label for each vertex included in the set of edges, which we call dl-sequence.
in dl-sequence, the degree is not calculated for the original graph, but is for the set of edges, and we define the inequality of elements of dl-sequence by;  >  if d <dig> >d <dig> or .
then, we can define a total order for dl-sequences  and  by and  hold for some i. for example, the dl-sequence of two connected edges of  and  in figure 1a, that is a–a–b, is , , ).
here, in the example, if the edges are substituted with a new vertex, a self loop is remained to the new vertex due to the edge of  as shown in figure 1e.
the remained edges should be also contracted.
therefore, we modify compressedge, and propose the following algorithm to contract identical sets of vertices and the edges between the vertices instead of individual edges.
in the example of figure 1e, the graph of figure 1f is obtained by this algorithm.
procedure compressvertices
input: maximum number of vertices m and undirected graph g with labeled vertices v and edges e
output: induced compression rules r and compressed graph;
begin
r := ∅;
s := {l} for each label l ∈ l;
while |e| > 0
v = ∅; m := 2;
whilev = ∅ and m ≤ m
:= selectvertices;
m := m + 1;
if v = ∅ then return ;
add a new label ln to l such that ln >l for all l ∈ l;
r = r ∪ {ln ← dli};
for each set of vertices u ∈ v
substituteu with a new vertex labeled with ln;
return ;
end
subprocedure selectvertices
begin
v, …, )) := {{ν <dig>  …, νm} ⊂ v | ν <dig>  …, νm are connected and = dli};
v := {v| u <dig> ∩ u <dig> = ∅ for all u <dig> u <dig> ∈ v};
if v = ∅ then return ;
vmost := {v ∈ v| |v| ≥ |v| for all v ∈ v};
selectv such that
or  for all v ∈ vmost;
return ,dli);
end
first, the algorithm tries to find two vertices and the edge between the vertices to be contracted.
if it does not find such two vertices, it tries to find more than two vertices and the edges between the vertices until it finds or up to the given number of vertices, m. figure  <dig> shows an example of contraction by the algorithm.
the graph of  contains  <dig> edges labeled with 'a' and 'b',  <dig> edges with 'a' and 'c', and  <dig> edges with 'b' and 'c'.
however, it cannot select any edge because they are overlapping each other.
therefore, it tries to find three vertices to be contracted.
shows the candidate sets of vertices {' a', 'b', 'c '} and three edges , , and , which appear most frequently two times in the graph.
however, they are overlapping again.
finally, it selects the candidate sets of , vertices {'a', 'b', 'b'} and two edges of , which appear also most frequently.
shows the graph contracted from the graph  by substituting the selected vertices and edges with a new vertex labeled with 'abb'.
compressvertices of m =  <dig> is equivalent to compressedge.
it should be noted that the algorithm uniquely determines the contracted sets of connected edges in each iteration although different subgraphs can be substituted with vertices of the same label in m ≥  <dig>  for example, both graphs of a-b-a-b and a-a-b-b are represented as , , , ) in dl-sequence.
it is to be noted that for three vertices, different subgraphs cannot have the same dl-sequence.
the algorithm is still efficient because it compares dl-sequences instead of comparing subgraphs, where subgraph isomorphism problem is known to be in np-complete.
similarity measure
the universal similarity metric  was proposed by li et al.
<cit> , and has been applied to several biological data  <cit> .
usm between two objects o <dig> and o <dig> is defined using kolmogorov complexity k as follows:
where  denote shortest programs for generating o <dig> o <dig>  respectively.
kolmogorov complexity k of an object o is defined to be the length of the shortest program p for a universal turing machine u which outputs o, and the conditional kolmogorov complexity of o <dig> given o <dig> is defined to be the length of the shortest program p which outputs o <dig> when o <dig> is given as follows:
it should be noted that k is considered as a measure of the amount of information that the object o contains.
since it is not possible to obtain these kolmogorov complexities for real data, we approximate k of a graph g by c = |r| + |ec|, where |r| means the number of rules extracted from g by our method, and |ec| means the number of remaining edges after the compression of g. the conditional kolmogorov complexity k of g <dig> given g <dig> can be approximated to be c − c as in  <cit> , where g <dig> ∪ g <dig> means the concatenated graph g′ of g <dig> and g <dig> such that v′ = v <dig> ∪ v <dig>  e′ = e <dig> ∪ e <dig>  |v′| = |v1| + |v2| and |e′| = |e1| + |e2|.
even if there are identical vertices  between g <dig> and g <dig>  they are added to v′ as different vertices.
substituting k of eq.
with c, the approximated usm for graph compression, gusm, between two graphs g <dig> and g <dig> is given as follows:
it should be noted that gu sm =  <dig> if |ec| = <dig> for c. if g <dig> and g <dig> are similar, then g <dig> and g <dig> are generated from almost the same set of rules r, that is, c ≈ c ≈ c ≈ |r|, and gu sm approaches to  <dig>
RESULTS
to evaluate the proposed measure, we used metabolic pathways for several organisms, h. sapiens, m. musculus, a. thaliana, d. melanogaster, c. elegans, e. coli, s. cerevisiae, and b. subtilis, from the kegg database  <cit>  .
we used chemical compounds as nodes and chemical reactions as edges.
for evaluation purposes, it is not appropriate to use protein-protein interaction networks because the accuracy of the networks is not sufficient  <cit> .
furthermore, we compared the results with those of graphitour because other methods such as pathblast  <cit> , netalign  <cit> , and mnaligner  <cit>  do not give the similarity of networks, and focus on finding interesting subnetworks or most similar subnetworks to a query network.
statistics of metabolic pathways for several organisms, h. sapiens, m. musculus, a. thaliana, d. melanogaster, c. elegans, e. coli, s. cerevisiae, and b. subtilis.
in our first computational experiment, all nodes in the metabolic networks were labeled with chemical compounds, and there was only one edge having the same labels, that is, |ε| =  <dig>  then, our compression algorithm for g produced rules r and the remaining graph gc as c = |r| + |ec| = |e|.
this means that g is not compressed.
many other methods also cannot select frequent subnetworks for such networks.
since we would like to compare network structures for the metabolic networks, we replaced labels with morgan index  <cit> .
figure  <dig> shows an example of calculation of morgan index.
first,  <dig> is assigned to each node.
next, the sum of values of adjacent nodes is assigned for each node.
this iteration is repeated until the number of different values of morgan index does not increase.
we call the index obtained in this way the original morgan index.
morgan index obtained by one iteration of this procedure is equivalent to the degree of each node, and morgan index depends on graph structures.
we fixed the number of iterations of the morgan index procedure, applied our compression algorithms to individual and concatenated metabolic networks, g <dig>  g <dig>  g <dig> ∪ g <dig>  and calculated gu sm  from c, c and c. to confirm that our compression algorithms work for measuring the similarity of metabolic networks, we obtained hierarchical clustering results using the nearest neighbor  method, and compared them with actual phylogenetic trees and hierarchical clustering results by graphitour.
moreover, we performed such experiments with several numbers of iterations from  <dig> to  <dig> because the number of iterations of the original morgan index is at most  <dig> for the metabolic networks.
furthermore, the proposed methods are efficient.
the computational time was at most  <dig> seconds in compressedge,  <dig> seconds in compressvertices, even for the concatenated network of h. sapiens and m. musculus with morgan index of  <dig> iterations.
these experiments were done in a single processor core on a pc with xeon x <dig>  <dig> ghz cpus and 8gb memory under the linux  operating system, where the g++ compiler was used with optimization option -o <dig>
we also compared our proposed methods with simple methods based on node and edge numbers.
we calculated distances between two organisms as the differences of the number of nodes or edges, and obtained hierarchical clustering results using the nearest neighbor method.
we can see from the results  that h. sapiens was the nearest to m. musculus, but other relations were different from actual phylogenetic trees.
this result shows that our proposed methods are better than those based on node or edge numbers.
in addition, our methods generate rules to contract edges iteratively.
it means that they try to find hierarchical substructures for a given graph.
we defined the similarity between graphs, gusm, based on the number of such rules.
it can be considered that gusm implies whether hierarchical substructures are also similar, or not.
we proposed two methods, compressedge and compressvertices, where m denotes the maximum number of vertices to be contracted at a time.
it should be noted that the minimum number is  <dig> because a vertex itself cannot be contracted.
compressedge is equivalent to compressvertices.
if a graph has many overlapping edges, compressedge ) would not extract many rules, that is, many edges are not contracted and are remained.
consider a graph g that all edges of g are overlapping.
the similarity between g and itself, gu sm , must be  <dig>  however, gu sm  =  <dig> because any edge of g is not contracted, c  = |ec| and c  = 2|ec|.
therefore, compressvertices for m >  <dig> is needed.
CONCLUSIONS
in this paper, we have proposed novel methods for compressing biological networks.
one of the important properties of the proposed methods is that isomorphic networks are compressed in the same way.
unlike many other methods comparing biological networks, our methods are able to give the similarity metric of their networks.
moreover, our methods are very efficient because they do not compare subgraphs directly.
we have applied the proposed compression methods to comparison of metabolic networks, and compared the results with those of an existing method.
the results suggest that the proposed compression methods are useful for comparison of biological networks.
our proposed methods were applied to only undirected graphs in this paper.
however, it is possible to extend our algorithms to deal with directed graphs.
it is easy to extend compressedge, and the modified method can still be efficient.
our methods are efficient as well as graphitour, and it is important to keep the efficiency after extending them.
metabolic networks can also be represented as directed graphs and undirected graphs using chemical compounds as nodes and the relation between compounds  as edges.
it is an interesting issue to examine whether our methods are robust for any representation of a network.
it is considered in general that random networks are more difficult to be compressed than scale-free networks.
however, our methods cannot compress metabolic networks that are known as scale-free networks because all nodes in metabolic networks are labeled with distinct chemical compounds, and there is only one edge having the same labels.
our proposed methods are useful only for comparison of networks.
if the same labels can appear multiple times, it is expected that our methods can also differentiate these networks.
however, it is difficult to compare them in a simple way because the compression size depends on the distribution of node labels.
since we do not have realistic models for generation of random and scale-free networks with node labels, application of our proposed methods to differentiation of random networks from scale-free networks is left as future work.
though we have applied the methods to comparison of networks, the application is not limited to comparison.
it might be applied to detection of network motifs with hierarchical structures because our method iteratively compresses edges .
one drawback of our proposed compression methods is that it is not a lossless compression method .
therefore, improvement of the method towards lossless compression is also important future work.
availability
the source code of comparevertices is available through the supplementary information web page .
competing interests
the authors declare that they have no competing interests.
authors' contributions
methods were developed by mh and ta.
the manuscript was prepared by mh and ta.

 development of algorithms for comparing various kinds of biological data is one of the important topics in bioinformatics and systems biology. methods for comparison of dna and/or protein sequences have been extensively studied and have been applied to analyses of real sequence data quite successfully. due to increased interests in systems biology, extensive studies have recently been done on comparison of biological networks. for comparison of metabolic networks, ogata et al. developed a method based on clustering, tohsato et al. extended a multiple sequence alignment technique to multiple alignment of metabolic pathways using a scoring scheme based on ec numbers, pinter et al. applied a tree matching technique to alignment of metabolic pathways, and wernicke and rasche developed a simple backtracking algorithm utilizing the local diversity property. for comparison of protein-protein interaction networks, kelley et al. developed pathblast using dynamic programming, liang et al. developed netalign using a clique-based method for computing maximal common subgraphs, li et al. developed mnaligner using integer quadratic programming, singh et al. developed isorank algorithm based on google's pagerank method, and zaslavskiy et al. developed a gradient ascent-based method and a message passing-based method. on the other hand, data compression methods have been applied to comparison of large sequence data and protein structure data. since it is still difficult to compare global structures of large biological networks and data compression-based methods can be applied to comparison of large-scale sequence data, it is reasonable to try to apply data compression methods to comparison of biological networks. in this paper, we propose such methods. in order to apply data compression to biological networks, data compression methods for graphs are required. for compression of graphs, adler and mitzenmacher developed a method based of huffman coding of vertices, peshkin developed graphitour based on iterative contractions of identical edges, and cook and holder developed subdue based on contraction of frequent subgraphs and mdl principle, which was further extended to edif for lossless compression by yang et al.. however, the method by adler and mitzenmacher does not seem to be useful for comparison of networks because it does not make much use of structural information. in graphitour, the uniqueness of compression results is not guaranteed because there is some ambiguity in selection of overlapping edges, which is not suitable for comparison of network structures. this point is also unclear in edif and subdue. therefore, we develop in this paper novel graph compression methods for which it is guaranteed that two isomorphic graphs are compressed in the same way. using these compression methods, we measure the similarity of two networks by means of the universal similarity metric proposed by li et al.. usm is defined using kolmogorov complexity which represents the amount of information contained in data, and is obtained by removing redundant parts maximally. therefore, kolmogorov complexities are approximated by compression sizes. we apply the proposed methods to comparison of metabolic networks, and compare the results with those of graphitour. the results of hierarchical clustering for several organisms suggest that the proposed methods outperforms graphitour, and can adequately measure the similarities between metabolic networks. methods graph compression method since our proposed methods are based on graphitour, we briefly review the graphitour algorithm. graphitour is based on iterative contractions of identical edges. in order to efficiently contract edges, graphitour selects edges appearing most frequently, and solves an instance of maximum cardinality matching problem, which finds as many edges as possible such that no two edges share a common vertex. procedure compressedge input: undirected graph g with labeled vertices v and edges e; output: induced compression rules r and compressed graph; begin r:= ∅; s:= {l} for each label l ∈ l; while |e| > 0 ε:= { ∈ e| = where, l ≥ l2}; ε:= {ε| no two edges in ε share a common vertex}; if ε = ∅ then return; εmost:= {ε ∈ ε| |ε| ≥ |ε| for all ε ∈ ε}; selectε such that s ∪ s <s ∪ s or ∪ s = s ∪ s and < ) for all ε ∈ εmost, where l ≥ l l ≥ l4; add a new label ln to l such that ln >l for all l ∈ l; s:= s ∪ s; r = r ∪ {ln ← }; for each edge e ∈ ε substitutee with a new vertex labeled with ln; return; end this proposed algorithm avoids contraction of edges which share a common vertex. in the example of figure our algorithm does not choose edges whose endpoints are'a' and'b', instead chooses the second candidate edges whose endpoints are'a' and'a', and obtains the graph of as the result. it should be noted that the proposed algorithm does not solve the maximum cardinality matching problem because it selects only edges such that all edges with the same labels do not share a common vertex. however, it is not sufficient to uniquely determine contracted edges because there can be more than one set which has the same number of edges, that is, |εmost| > therefore, we introduce a total order to sets of labels to determine the priority of edges. each edge has a pair of labels corresponding to two endpoints of the edge. let s and s be sets of labels. we can define a total order for s and s as follows. first, we sort s and s by descending order, respectively. we compare i-th elements, of s and s and define s <s if < and = hold for some i. the proposed algorithm selects edges with the smallest set of labels from εmost according to the total order. for example, if we compare s = {l l3} with s = {l l2} under l <l <l s and s are sorted as and, respectively, and we have s <s when edges with are contracted, a new label ln is added to l, where ln >l for all l ∈ l. in computational experiments, morgan index based on graph structures is assigned to each vertex. however, new added labels themselves do not reflect the original graph structure. therefore, in order to make effective use of the total order of original labels, we introduce a set of labels for each label l, s, which consists of only original labels. then, s is defined to be s ∪ s when is substituted with ln. the algorithm compares s ∪ s with s ∪ s before comparing edges of and. for example, for the graph of figure 1d, the algorithm selects edges with as contracted edges because it appears most frequently. however, if there is another edge with than shown in figure 1d, edges of and are compared. we suppose that'a'<'b'<'c'<'aa' and'aa' was obtained by contracting edges with. then, the corresponding sets to and, s = s ∪ s = {'a','a','b'} and s = s ∪ s = {'b','b'}, are compared, sorted as {'b','a','a'} and {'b','b'}, respectively, and we have s <s then, edges with are selected, and contracted to vertices with a new label'aab', where'aab'>'aa' and s = s ∪ s = {'a','a','b'}. extension to contraction of multiple edges in the previous algorithm, identical edges are contracted at each iteration. in this section, we propose another algorithm, which we call compressvertices, to contract identical sets of multiple connected edges. in order to uniquely determine the contracted sets of connected edges, we must introduce a total order to a set of edges. for that purpose, we apply degree sequence, which is defined to be the non-increasing sequence of degrees of vertices. for example, the degree sequence of figure 1a is. moreover, in order to distinguish labels of vertices, we introduce the non-increasing sequence of pairs of the degree and the label for each vertex included in the set of edges, which we call dl-sequence. in dl-sequence, the degree is not calculated for the original graph, but is for the set of edges, and we define the inequality of elements of dl-sequence by; > if d >d or. then, we can define a total order for dl-sequences and by and hold for some i. for example, the dl-sequence of two connected edges of and in figure 1a, that is a–a–b, is,, ). here, in the example, if the edges are substituted with a new vertex, a self loop is remained to the new vertex due to the edge of as shown in figure 1e. the remained edges should be also contracted. therefore, we modify compressedge, and propose the following algorithm to contract identical sets of vertices and the edges between the vertices instead of individual edges. in the example of figure 1e, the graph of figure 1f is obtained by this algorithm. procedure compressvertices input: maximum number of vertices m and undirected graph g with labeled vertices v and edges e output: induced compression rules r and compressed graph; begin r:= ∅; s:= {l} for each label l ∈ l; while |e| > 0 v = ∅; m:= 2; whilev = ∅ and m ≤ m:= selectvertices; m:= m + 1; if v = ∅ then return; add a new label ln to l such that ln >l for all l ∈ l; r = r ∪ {ln ← dli}; for each set of vertices u ∈ v substituteu with a new vertex labeled with ln; return; end subprocedure selectvertices begin v, …, )):= {{ν …, νm} ⊂ v | ν …, νm are connected and = dli}; v:= {v| u ∩ u = ∅ for all u u ∈ v}; if v = ∅ then return; vmost:= {v ∈ v| |v| ≥ |v| for all v ∈ v}; selectv such that or for all v ∈ vmost; return,dli); end first, the algorithm tries to find two vertices and the edge between the vertices to be contracted. if it does not find such two vertices, it tries to find more than two vertices and the edges between the vertices until it finds or up to the given number of vertices, m. figure shows an example of contraction by the algorithm. the graph of contains edges labeled with'a' and'b', edges with'a' and'c', and edges with'b' and'c'. however, it cannot select any edge because they are overlapping each other. therefore, it tries to find three vertices to be contracted. shows the candidate sets of vertices {' a','b','c'} and three edges,, and, which appear most frequently two times in the graph. however, they are overlapping again. finally, it selects the candidate sets of, vertices {'a','b','b'} and two edges of, which appear also most frequently. shows the graph contracted from the graph by substituting the selected vertices and edges with a new vertex labeled with'abb'. compressvertices of m = is equivalent to compressedge. it should be noted that the algorithm uniquely determines the contracted sets of connected edges in each iteration although different subgraphs can be substituted with vertices of the same label in m ≥ for example, both graphs of a-b-a-b and a-a-b-b are represented as,,, ) in dl-sequence. it is to be noted that for three vertices, different subgraphs cannot have the same dl-sequence. the algorithm is still efficient because it compares dl-sequences instead of comparing subgraphs, where subgraph isomorphism problem is known to be in np-complete. similarity measure the universal similarity metric was proposed by li et al., and has been applied to several biological data. usm between two objects o and o is defined using kolmogorov complexity k as follows: where denote shortest programs for generating o o respectively. kolmogorov complexity k of an object o is defined to be the length of the shortest program p for a universal turing machine u which outputs o, and the conditional kolmogorov complexity of o given o is defined to be the length of the shortest program p which outputs o when o is given as follows: it should be noted that k is considered as a measure of the amount of information that the object o contains. since it is not possible to obtain these kolmogorov complexities for real data, we approximate k of a graph g by c = |r| + |ec|, where |r| means the number of rules extracted from g by our method, and |ec| means the number of remaining edges after the compression of g. the conditional kolmogorov complexity k of g given g can be approximated to be c − c as in, where g ∪ g means the concatenated graph g′ of g and g such that v′ = v ∪ v e′ = e ∪ e |v′| = |v1| + |v2| and |e′| = |e1| + |e2|. even if there are identical vertices between g and g they are added to v′ as different vertices. substituting k of eq. with c, the approximated usm for graph compression, gusm, between two graphs g and g is given as follows: it should be noted that gu sm = if |ec| = for c. if g and g are similar, then g and g are generated from almost the same set of rules r, that is, c ≈ c ≈ c ≈ |r|, and gu sm approaches to  to evaluate the proposed measure, we used metabolic pathways for several organisms, h. sapiens, m. musculus, a. thaliana, d. melanogaster, c. elegans, e. coli, s. cerevisiae, and b. subtilis, from the kegg database. we used chemical compounds as nodes and chemical reactions as edges. for evaluation purposes, it is not appropriate to use protein-protein interaction networks because the accuracy of the networks is not sufficient. furthermore, we compared the results with those of graphitour because other methods such as pathblast, netalign, and mnaligner do not give the similarity of networks, and focus on finding interesting subnetworks or most similar subnetworks to a query network. statistics of metabolic pathways for several organisms, h. sapiens, m. musculus, a. thaliana, d. melanogaster, c. elegans, e. coli, s. cerevisiae, and b. subtilis. in our first computational experiment, all nodes in the metabolic networks were labeled with chemical compounds, and there was only one edge having the same labels, that is, |ε| = then, our compression algorithm for g produced rules r and the remaining graph gc as c = |r| + |ec| = |e|. this means that g is not compressed. many other methods also cannot select frequent subnetworks for such networks. since we would like to compare network structures for the metabolic networks, we replaced labels with morgan index. figure shows an example of calculation of morgan index. first, is assigned to each node. next, the sum of values of adjacent nodes is assigned for each node. this iteration is repeated until the number of different values of morgan index does not increase. we call the index obtained in this way the original morgan index. morgan index obtained by one iteration of this procedure is equivalent to the degree of each node, and morgan index depends on graph structures. we fixed the number of iterations of the morgan index procedure, applied our compression algorithms to individual and concatenated metabolic networks, g g g ∪ g and calculated gu sm from c, c and c. to confirm that our compression algorithms work for measuring the similarity of metabolic networks, we obtained hierarchical clustering results using the nearest neighbor method, and compared them with actual phylogenetic trees and hierarchical clustering results by graphitour. moreover, we performed such experiments with several numbers of iterations from to because the number of iterations of the original morgan index is at most for the metabolic networks. furthermore, the proposed methods are efficient. the computational time was at most seconds in compressedge, seconds in compressvertices, even for the concatenated network of h. sapiens and m. musculus with morgan index of iterations. these experiments were done in a single processor core on a pc with xeon x ghz cpus and 8gb memory under the linux operating system, where the g++ compiler was used with optimization option -o we also compared our proposed methods with simple methods based on node and edge numbers. we calculated distances between two organisms as the differences of the number of nodes or edges, and obtained hierarchical clustering results using the nearest neighbor method. we can see from the results that h. sapiens was the nearest to m. musculus, but other relations were different from actual phylogenetic trees. this result shows that our proposed methods are better than those based on node or edge numbers. in addition, our methods generate rules to contract edges iteratively. it means that they try to find hierarchical substructures for a given graph. we defined the similarity between graphs, gusm, based on the number of such rules. it can be considered that gusm implies whether hierarchical substructures are also similar, or not. we proposed two methods, compressedge and compressvertices, where m denotes the maximum number of vertices to be contracted at a time. it should be noted that the minimum number is because a vertex itself cannot be contracted. compressedge is equivalent to compressvertices. if a graph has many overlapping edges, compressedge ) would not extract many rules, that is, many edges are not contracted and are remained. consider a graph g that all edges of g are overlapping. the similarity between g and itself, gu sm, must be however, gu sm = because any edge of g is not contracted, c = |ec| and c = 2|ec|. therefore, compressvertices for m > is needed.  in this paper, we have proposed novel methods for compressing biological networks. one of the important properties of the proposed methods is that isomorphic networks are compressed in the same way. unlike many other methods comparing biological networks, our methods are able to give the similarity metric of their networks. moreover, our methods are very efficient because they do not compare subgraphs directly. we have applied the proposed compression methods to comparison of metabolic networks, and compared the results with those of an existing method. the results suggest that the proposed compression methods are useful for comparison of biological networks. our proposed methods were applied to only undirected graphs in this paper. however, it is possible to extend our algorithms to deal with directed graphs. it is easy to extend compressedge, and the modified method can still be efficient. our methods are efficient as well as graphitour, and it is important to keep the efficiency after extending them. metabolic networks can also be represented as directed graphs and undirected graphs using chemical compounds as nodes and the relation between compounds as edges. it is an interesting issue to examine whether our methods are robust for any representation of a network. it is considered in general that random networks are more difficult to be compressed than scale-free networks. however, our methods cannot compress metabolic networks that are known as scale-free networks because all nodes in metabolic networks are labeled with distinct chemical compounds, and there is only one edge having the same labels. our proposed methods are useful only for comparison of networks. if the same labels can appear multiple times, it is expected that our methods can also differentiate these networks. however, it is difficult to compare them in a simple way because the compression size depends on the distribution of node labels. since we do not have realistic models for generation of random and scale-free networks with node labels, application of our proposed methods to differentiation of random networks from scale-free networks is left as future work. though we have applied the methods to comparison of networks, the application is not limited to comparison. it might be applied to detection of network motifs with hierarchical structures because our method iteratively compresses edges. one drawback of our proposed compression methods is that it is not a lossless compression method. therefore, improvement of the method towards lossless compression is also important future work. availability the source code of comparevertices is available through the supplementary information web page. competing interests the authors declare that they have no competing interests. authors' contributions methods were developed by mh and ta. the manuscript was prepared by mh and ta. 
in existing compression methods, the uniqueness of compression results is not guaranteed because there is some ambiguity in selection of overlapping edges. these results suggest that our methods can efficiently measure the similarities between metabolic networks. the proposed methods are applied to comparison of metabolic networks of several organisms, h. sapiens, m. musculus, a. thaliana, d. melanogaster, c. elegans, e. coli, s. cerevisiae, and b. subtilis, and are compared with an existing method. comparison of various kinds of biological data is one of the main problems in bioinformatics and systems biology. since it is still difficult to compare global structures of large biological networks, it is reasonable to try to apply data compression methods to comparison of biological networks. this paper proposes novel efficient methods, compressedge and compressvertices, for comparing large biological networks. our proposed algorithms, which compress node-labeled networks, are useful for measuring the similarity of large biological networks. data compression methods have been applied to comparison of large sequence data and protein structure data. in the proposed methods, an original network structure is compressed by iteratively contracting identical edges and sets of connected edges. – september optimization and systems biology zhangjiajie, china
 comparison of various kinds of biological data is one of the main problems in bioinformatics and systems biology. data compression methods have been applied to comparison of large sequence data and protein structure data. since it is still difficult to compare global structures of large biological networks, it is reasonable to try to apply data compression methods to comparison of biological networks. in existing compression methods, the uniqueness of compression results is not guaranteed because there is some ambiguity in selection of overlapping edges.  this paper proposes novel efficient methods, compressedge and compressvertices, for comparing large biological networks. in the proposed methods, an original network structure is compressed by iteratively contracting identical edges and sets of connected edges. then, the similarity of two networks is measured by a compression ratio of the concatenated networks. the proposed methods are applied to comparison of metabolic networks of several organisms, h. sapiens, m. musculus, a. thaliana, d. melanogaster, c. elegans, e. coli, s. cerevisiae, and b. subtilis, and are compared with an existing method. these results suggest that our methods can efficiently measure the similarities between metabolic networks.  our proposed algorithms, which compress node-labeled networks, are useful for measuring the similarity of large biological networks. – september optimization and systems biology zhangjiajie, china 