基于生物网络的频繁Hamilton子图挖掘算法  

An algorithm for finding Hamilton subgraph in biological network

作　　者：董安国[1] 高琳[2] 邱在秦[3] 赵建帮[2] 周晓峰[2] 

机构地区：[1]长安大学理学院,陕西西安710064 [2]西安电子科技大学计算机学院,陕西西安710071 [3]西安石油大学理学院,陕西西安710065

出　　处：《西北农林科技大学学报（自然科学版）》2008年第5期185-190,共6页Journal of Northwest A&F University(Natural Science Edition)

基　　金：国家自然科学基金项目(60574039);长安大学科技发展基金项目(07J04)

摘　　要：【目的】在生物网络的功能模体发现问题中涉及到频繁子图的挖掘,而功能模体通常是一个非树型结构的子图,甚至具有Hamilton回路。为了减少挖掘出子图的结果集,提高频繁子图挖掘的效率,分析了在生物网络中挖掘频繁Hamilton子图的算法。【方法】对网络连接矩阵构造了一种运算,得到网络路径信息,通过对路径的合并,搜索出网络中所有的Hamilton子图。【结果】在理论分析和证明的基础上,给出了2-路径和3-路径的搜索算法,进而构造了Hamilton子图的搜索算法,并对算法的复杂度进行了分析,最后将算法应用于真实生物网络,找出了频繁Hamilton子图。【结论】与现有子图搜索算法相比,由于搜索的只是Hamilton子图,减少了搜索结果集,同时引入了代数运算并构造了矩阵的快速迭代算法,提高了挖掘效率,试验结果也验证了算法的高效性。[Objective] When referred to functional motif discovery in biological networks, the most important step is to find subgraphs with an enhanced number of internal links with feedback,such as nontreelike and Hamiltonian circle structure. To improve the efficiency of frequent subgraph mining, the algorithm for mining subgraph with the nature of Hamiltonian circle was provided. [Method] A matrix theory-based approach was developed for such subgraphs and the properties of Hamiltonian subgraphs waer studied. [Result] Then the algorithms were provided for searching the 2-path and 3-path based on the properties to find subgraph with Hamiltonian cycle. Also, the complexity of the algorithm were analyzed and the algorithms to real biological network were applied. [Conclusion] The simulation results show that our algorithms have high efficiency compared with the existing algorithm since the strategy was adopted to reduce the number of subgraph under the constraint of Hamiltonian circle.

关 键 词：生物网络 HAMILTON回路 Hamilton子图 频繁Hamilton子图 

分 类 号：TP311.12[自动化与计算机技术—计算机软件与理论]