Kavosh: a new algorithm for finding network motifs
Kavosh: a new algorithm for finding network motifs
复制标题
DOI：
10.1186/1471-2105-10-318
复制
发表时间：
2009-10-04
影响因子：
3
通讯作者：
Masoudi-Nejad, Ali
中科院分区：
文献类型：
--
作者：
Kashani, Zahra Razaghi Moghadam;Ahrabian, Hayedeh;Masoudi-Nejad, Ali
背景：复杂网络的研究涉及许多科学领域，对理解生物过程尤为重要。网络中的基元是小的连通子图，其出现频率明显高于随机网络。近年来，它们作为揭示复杂网络结构设计原理的一个有用概念而受到广泛关注。结果：提出了一种新的网络模体搜索算法（Kavosh算法），该算法能以较少的内存和CPU时间找到k-大小的网络模体，并能有效地搜索出k-大小的网络模体.我们的算法是基于计数一个给定图（有向或无向）的所有k大小的子图。最后，在E. coli和革兰氏阳性菌S.结论：通过与三种常用的基序发现工具的比较，证明了本文算法的有效性。为了进行比较，考虑了CPU时间、存储器使用和所获得的模体的相似性。另外，Kavosh算法可以用来寻找大于8的模体，而其他算法大多对大于8的模体有限制。Kavosh源代码和帮助文件可在http://Lbb.ut.ac.ir/Download/LBBsoft/Kavosh/上免费获得。
Background: Complex networks are studied across many fields of science and are particularly important to understand biological processes. Motifs in networks are small connected sub-graphs that occur significantly in higher frequencies than in random networks. They have recently gathered much attention as a useful concept to uncover structural design principles of complex networks. Existing algorithms for finding network motifs are extremely costly in CPU time and memory consumption and have practically restrictions on the size of motifs.Results: We present a new algorithm (Kavosh), for finding k-size network motifs with less memory and CPU time in comparison to other existing algorithms. Our algorithm is based on counting all k-size sub-graphs of a given graph (directed or undirected). We evaluated our algorithm on biological networks of E. coli and S. cereviciae, and also on non-biological networks: a social and an electronic network.Conclusion: The efficiency of our algorithm is demonstrated by comparing the obtained results with three well-known motif finding tools. For comparison, the CPU time, memory usage and the similarities of obtained motifs are considered. Besides, Kavosh can be employed for finding motifs of size greater than eight, while most of the other algorithms have restriction on motifs with size greater than eight. The Kavosh source code and help files are freely available at: http://Lbb.ut.ac.ir/Download/LBBsoft/Kavosh/.