Kim W Y, Kurmar S
Computing and Software Systems, School of Science, Technology, Engineering, and Mathematics, University of Washington Bothell, Bothell, WA 98011-8246, United States.
Methods. 2015 Jul 15;83:71-9. doi: 10.1016/j.ymeth.2015.04.007. Epub 2015 Apr 11.
A network motif is defined as an over-represented subgraph pattern in a network. Network motif based techniques have been widely applied in analyses of biological networks such as transcription regulation networks (TRNs), protein-protein interaction networks (PPIs), and metabolic networks. The detection of network motifs involves the computationally expensive enumeration of subgraphs, NP-complete graph isomorphism testing, and significance testing through the generation of many random graphs to determine the statistical uniqueness of a given subgraph. These computational obstacles make network motif analysis unfeasible for many real-world applications. We observe that the fast growth of biotechnology has led to the rapid accretion of molecules (vertices) and interactions (edges) to existing biological network databases. Even with a small percentage of additions, revised networks can have a large number of differing motif instances. Currently, no existing algorithms recalculate motif instances in 'updated' networks in a practical manner. In this paper, we introduce a sensible method for efficiently recalculating motif instances by performing motif enumeration from only updated vertices and edges. Preliminary experimental results indicate that our method greatly reduces computational time by eliminating the repeated enumeration of overlapped subgraph instances detected in earlier versions of the network. The software program implementing this algorithm, defined as SUNMI (Sensible Update of Network Motif Instances), is currently a stand-alone java program and we plan to upgrade it as a web-interactive program that will be available through http://faculty.washington.edu/kimw6/research.htm in near future. Meanwhile it is recommended to contact authors to obtain the stand-alone SUNMI program.
网络基序被定义为网络中过度呈现的子图模式。基于网络基序的技术已广泛应用于生物网络分析，如转录调控网络（TRN）、蛋白质 - 蛋白质相互作用网络（PPI）和代谢网络。网络基序的检测涉及计算成本高昂的子图枚举、NP完全的图同构测试，以及通过生成许多随机图来进行显著性测试，以确定给定子图的统计独特性。这些计算障碍使得网络基序分析对于许多实际应用来说不可行。我们观察到生物技术的快速发展导致现有生物网络数据库中分子（顶点）和相互作用（边）的迅速增加。即使只有一小部分的增加，修订后的网络也可能有大量不同的基序实例。目前，没有现有算法能够以实际可行的方式在“更新”的网络中重新计算基序实例。在本文中，我们介绍了一种明智的方法，通过仅从更新的顶点和边进行基序枚举来有效地重新计算基序实例。初步实验结果表明，我们的方法通过消除在网络早期版本中检测到的重叠子图实例的重复枚举，大大减少了计算时间。实现该算法的软件程序，定义为SUNMI（网络基序实例的明智更新），目前是一个独立的Java程序，我们计划将其升级为一个网络交互式程序，在不久的将来可通过http://faculty.washington.edu/kimw6/research.htm获得。同时，建议联系作者以获取独立的SUNMI程序。
