HashESU:一种生物网络模体识别高效方法  

HashESU: Efficient Algorithm for Identifying Motifs in Biological Networks

作　　者：赵静[1] 钟诚[1] 

机构地区：[1]广西大学计算机与电子信息学院,南宁530004

出　　处：《小型微型计算机系统》2015年第9期2042-2046,共5页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(61462005)资助;广西自然科学基金项目(2014GXNSFAA118396)资助;广西研究生教育创新计划项目(YCSZ2014034)资助;广西教育厅-广西大学博士点建设基金项目(P11900119)资助

摘　　要：通过模体识别可以获得生物网络结构和功能,生物网络模体识别过程涉及到子图枚举和子图同构的问题,计算量非常大.提出一种高效的网络模体识别算法Hash ESU,它使用经典算法ESU枚举子图,采用Hash表结构保存生成的子图,利用每个新增结点与已经确定的结点之间的关系,生成子图标识关键字SIK并映射到Hash表中,每个SIK只在第一次生成时才需要调用同构计算,以大大减少调用NAUTY算法进行同构检测的次数、更快地进行查找和插入子图操作,进而加快模体识别的速度.实验结果表明,在模体识别结果质量相同的前提下,Hash ESU算法的运行效率明显优于著名的ESU算法和使用四分树结构存储子图的Quate Xelero算法.Netw ork motifs identification is helpful for understanding the structure and function of biological netw orks. Identifying the motifs using subgraph enumeration and subgraph isomorphism is intensive-computation and time-consuming. An efficient netw orks motifs identification algorithm Hash ESU is proposed. Hash ESU uses classical algorithm ESU to enumerate the sub-graphs,constructs hash table structure to store the sub-graphs and uses the relationship betw een the new node and old one in the subgraph to generate a subgraph identification key SIK w hich be mapped to the hash table. Generating SIK at the first time only calls isomorphism algorithm.The times to call NAUTY isomorphism algorithm can be greatly reduced and the subgraphs are fast searched and inserted to accelerate the motif identification. Experimental results show that on the premise of the motif identification results w ith the same quality,the execution efficiency of Hash ESU algorithm is superior to ESU algorithm and Quate Xelero algorithm using quaternary tree structure.

关 键 词：生物网络 模体识别 子图枚举 子图同构 HASHING 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]