一个生物网络比对的启发式算法

随着各种高通量生物实验技术的发明和广泛应用,越来越多的分子生物网络数据被公布.有效而且可靠的比对这些网络对检测分子生物网络的保守性功能模块和推测物种间的进化关系有着十分重要的意义.然而,由于网络比对在理论上是NP-困难（nondeterministic polynomialtime-hard）问题,它已经成为当前计算生物学需要攻克的主要难点之一.本文提出了一个比对两个蛋白质相互作用网络的启发式算法.该算法首先通过比较两个网络中所有顶点的邻域相似性给出这两个网络的顶点相似性矩阵,然后利用该矩阵将全局网络比对问题转化为一个二部图匹配问题.众所周知,二部图匹配问题具有多项式时间复杂度算法,本文利用ILOG CPLEX软件进行求解.为了验证该算法的优越性,作者比对了水痘病毒（varicella-zoster,VZV）和卡波济（氏）肉瘤病毒（kaposi＇s sarcomaassociated herpesvirus,KSHV）的蛋白质相互作用网络,并且把比对结果同其它网络比对算法进行比较.结果证明该算法显著提高了全局网络比对的精确度.

A Heuristic Algorithm to Align Protein Interaction Networks

With the development of high throughput experimental techniques,protein-protein interaction(PPI) network data have been increasingly available.Efficient and reliable local and global alignments of these networks play central roles in detecting conserved functional motifs like pathways and complexes,as well as in inferring functional orthologs and evolutionary relationships cross species.However,because network alignment is in principle an NP-hard problem, it has become one of the foremost challenges in bioi...