现有的大多数网络模体发现算法发现网络中的确切模体,但是由于生物数据是不完整的,有噪声的,而且生命过程具有动态性,概率网络模体具有更实际的意义.本文提出了非树型网络模体发现算法,寻找由一组相似子图组成的概率网络模体.在该算法中,首先提出子图挖掘算法ESN挖掘网络中所有给定规模的非树型子图,然后进行多图比对,最后基于统计模型和对应的得分函数,用模拟退火算法求得网络模体.对E.coil和Yeast的基因调控网络的仿真实验表明,该算法能够高效地发现生物网络中的概率模体.%Most existing network motif discovery algorithms detect exact motifs. Because biological networks are incomplete and noise,and the life process is dynamic,probability network motifs are of great importance. In this paper, we propose a non-treelike network motif discovery algorithm, which focuses on network motifs derived from families of mutually similar but not necessarily identical patterns. In our approach, we first present a subgraph mining algorithm ESN for searching all non-treelike subgraphs of a given size.Then multiple graph alignment is performed on a set of subgraphs with a same size.Finally,a simulated annealing algorithm is used to derive network motifs, based on a statistical model and its corresponding scoring function. Experimental evaluation on transcriptional regulatory networks of E. coli and Yeast shows that our algorithm achieves good performance.
展开▼
