一种高效的生物网络概率模体发现算法

针对概率模体发现算法中非树形子图的挖掘和在得分函数最大化的过程中得分函数值计算的2个难点.首先提出基于划分的非树形子图的搜索算法,其次将子图同构应用于最小错配的求解以缩小智能优化算法对得分函数求解的解空间,最后将基于模拟退火算法和遗传算法的混合算法应用于得分函数的求解过程.在大肠杆菌基因调控网络中的实验结果表明,与其他算法相比,混合智能算法可以大大减少非树形子图的搜索时间,并以相对较快的收敛速度收敛到一个较优的解,因此所提出的方法有效地提高了概率模体发现的效率.

An efficient algorithm for discovering probability motifs in biological networks

Mining nontreelike subgraphs and computing the scoring function are two major bottlenecks in probability motif discovery algorithm.To solve the problem a nontreelike subgraph searching algorithm based on partition is proposed in this paper.And the isomorphism of subgraphs is used for computing the minimum pairwise mismatch to narrow down the searching space when using intelligent optimization algorithm to obtain the most similar subgraphs.Finally,a hybrid algorithm based on the genetic algorithm and the simulated annealing algorithm is applied in the scoring function computing.Experimental results on E.COLI data set show that the proposed algorithm of nontreelike subgraph searching takes less time than the other algorithms,and the hybrid intelligent optimization algorithm converges faster and results in a better solution than a pure simulated annealing algorithm.The methods proposed can identify probability network motifs from the real biological networks data with higher efficiency.