基于局部优化与二分图匹配的PPI网络比对算法

摘要

Biological protein interaction network,referred to as PPI network,is a graph model used in bioinformatics to represent the interaction between proteins.The comparison between different species PPI networks has important biological significance.A good PPI network alignment algorithm is particularly important.In view of this problem,this paper presented LOBM algorithm for the first time.LOBM is a kind of matching algorithm which can optimize the existing comparison results,and use the bipartite graph to match the classical graph theory model to improve the matching effect.The experiments result showed that compared with some of the existing alignment algorithm,the comparison results of LOBM have a greater improvement.%生物蛋白质相互作用网络,简称PPI网络,是一种生物信息学中用来表示蛋白质之间相互作用关系的图模型.不同物种PPI网络之间的比对,有着重要的生物学意义,一个好的PPI网络比对算法,显得尤为重要.针对该问题,首次提出了LOBM(Local Optimization based on Bipartite graph Matching)算法.LOBM是一种能够局部优化既有比对结果,并且利用二分图匹配这一经典图论模型,来提高既有比对算法的比对效果.实验表明,LOBM相比一些现有的比对算法,在比对结果上有较大的提升.