Comparing biological networks via graph compression.
Comparing biological networks via graph compression.
复制标题
DOI：
10.1186/1752-0509-4-s2-s13
复制
发表时间：
2010-09-13
影响因子：
--
通讯作者：
Akutsu T
中科院分区：
文献类型：
--
作者：
Hayashida M;Akutsu T
各种生物数据的比较是生物信息学和系统生物学中的主要问题之一。数据压缩方法已被应用于大序列数据和蛋白质结构数据的比较。由于大型生物网络的全局结构比较困难，尝试将数据压缩方法应用于生物网络的比较是合理的。在现有的压缩方法中，由于重叠边的选择存在一定的模糊性，压缩结果的唯一性得不到保证。本文提出了一种比较大型生物网络的新的有效方法--CompressEdge和CompressVertics。在所提出的方法中，通过迭代收缩相同的边和连通的边集来压缩原始网络结构。然后，通过级联网络的压缩比来衡量两个网络的相似性。将所提出的方法应用于几种生物的代谢网络的比较，并与现有的方法进行了比较。这些结果表明，我们的方法可以有效地衡量代谢网络之间的相似性。我们提出的算法对节点标记网络进行了压缩，对于测量大型生物网络的相似性是有用的。
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.