Network Motif Detection: Algorithms, Parallel and Cloud Computing,and Related Tools

作     者：Wooyoung Kim Martin Diko Keith Rawson 

作者机构：the Department of Computing and Software Systems University of Washington Bothell 

出 版 物：《Tsinghua Science and Technology》 (清华大学学报（自然科学版（英文版）)

年 卷 期：2013年第18卷第5期

页      面：469-489页

核心收录：

学科分类：08[工学] 081201[工学-计算机系统结构] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：network motif parallel search MapReduce HDFS storm 

摘      要：Network motif is defined as a frequent and unique subgraph pattern in a network, and the search involves counting all the possible instances or listing all patterns, testing isomorphism known as NP-hard and large amounts of repeated processes for statistical evaluation. Although many efficient algorithms have been introduced, exhaustive search methods are still infeasible and feasible approximation methods are yet ***, the fast and continual growth of biological networks makes the problem more challenging. As a consequence, parallel algorithms have been developed and distributed computing has been tested in the cloud computing environment as well. In this paper, we survey current algorithms for network motif detection and existing software tools. Then, we show that some methods have been utilized for parallel network motif search algorithms with static or dynamic load balancing techniques. With the advent of cloud computing services, network motif search has been implemented with MapReduce in Hadoop Distributed File System（HDFS）, and with Storm, but without statistical testing. In this paper, we survey network motif search algorithms in general, including existing parallel methods as well as cloud computing based search, and show the promising potentials for the cloud computing based motif search methods.