Comparing biological networks via graph compression.

DOI IR (HANDLE) HANDLE PDF Web Site View 1 Remaining Hide 1 Citations 17 References Open Access

Search this article

Description

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.

Journal

Citations (1)*help

See more

References(17)*help

See more

Related Projects

See more

Keywords

Details 詳細情報について

Report a problem

Back to top