Comparing biological networks via graph compression.
BACKGROUND
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.


RESULTS
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.


CONCLUSIONS
Our proposed algorithms, which compress node-labeled networks, are useful for measuring the similarity of large biological networks.
Hayashida
Morihiro
M
Bioinformatics Center, Institute for Chemical Research, Kyoto University, Gokasho, Uji, Kyoto, Japan. morihiro@kuicr.kyoto-u.ac.jp
Akutsu
Tatsuya
T
D000465:Algorithms; D000818:Animals; D044962:Data Compression; D003628:Database Management Systems; D030562:Databases, Protein; D006801:Humans; D053858:Metabolic Networks and Pathways; D020539:Sequence Analysis, Protein; D049490:Systems Biology / Q000379:methods*