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

生物蛋白质相互作用网络,简称PPI网络,是一种生物信息学中用来表示蛋白质之间相互作用关系的图模型。不同物种PPI网络之间的比对,有着重要的生物学意义,一个好的PPI网络比对算法,显得尤为重要。针对该问题,首次提出了LOBM(Local Optimization based on Bipartite graph Matching)算法。LOBM是一种能够局部优化既有比对结果,并且利用二分图匹配这一经典图论模型,来提高既有比对算法的比对效果。实验表明,LOBM相比一些现有的比对算法,在比对结果上有较大的提升。     

基于层次聚类的生物网络全局比对算法

生物网络比对是研究生物进化过程的重要手段,不同物种间的比对不仅有助于理解物种的知识转移,同时也有助于进行功能预测和检测保守功能成分。然而,现有比对算法很难实现拓扑度量和生物度量同时最优。设计JAlign算法,将拓扑相似性与归一化序列相似性相结合构成目标函数,基于种子-扩展算法和模块检测进行全局比对。在种子筛选阶段,利用Jerarca聚类算法划分功能模块,借助目标函数计算模块间的相似性进行最优模块匹配,并从匹配结果中提取部分节点对作为种子节点。在扩展阶段,将比对从种子节点扩展至其邻居节点,在选择节点对进行扩展比对时综合考虑节点之间的连接关系、度差值、节点相似性等因素。在此基础上,为避免遗漏分散节点,找到剩余未匹配的节点构建二分图,以贪心方式进行最大加权二分图匹配,并将匹配结果合并到比对集合中,完成最终匹配。实验结果表明,JAlign算法能够实现拓扑度量和生物度量的良好平衡,其边正确性指标、诱导保守子结构得分、对称子结构得分和生物质量使用功能一致性指标均优于L-GRAAL、SPINAL和ModuleAlign算法,在时间效率上也具有优势。     

用于成对PPI网络比对的分治与整合算法

生物网络比对是分析不同生物间进化关系的重要手段,它可以揭示不同物种间的保守功能并为物种间的注释转移提供重要信息。网络比对与子图同构类似,是一个NP-hard问题。本文提出了一种新的分治与整合策略的生物网络比对算法。首先进行模块划分,并根据已有的比对信息计算模块相似性;然后根据模块间结点的子比对获取候选结果集,最终通过超图匹配获得比对结果。使用已有的比对信息的集体行为预估模块间的相似性,大大提高了模块匹配的效率。基于路径和结点的得分函数保证了模块内结点的相似性。对于不同网络间结点的相似性,分别从结点自身和结点间的差异进行相似性判断。与现有算法相比,本文算法在生物和拓扑指标上均表现最佳。     

基于消息传递接口的大规模生物网络比对并行化算法

为有效降低生物网络比对算法的时间复杂度,提出一种基于可扩展的蛋白质相互作用网络比对(SPINAL)算法的消息传递接口(MPI)并行化实现方法。该方法将MPI并行化思想运用在SPINAL算法中,在多核环境中采用并行排序代替算法原本的排序方式,并结合负载均衡策略合理分配任务。实验结果表明,与未使用并行排序以及负载均衡策略相比,该方法在处理大规模生物网络比对时能有效地缩短计算时间,提高运算效率,对于不同组比对数据都有较为稳定的优化保障,具有良好的可扩展性。     

基于遗传算法的一种生物序列比对方法

生物序列比对是对DNA（或RNA,蛋白质）序列,寻找和确定它们的相似部分或稳定区域.二重序列比对问题可采用动态规划方法求得其最优解;多重序列比对问题是一个NP完全的组合优化问题,有待进一步探索与研究.通过合理的编码表示,采用相应的遗传算子,设计了一种求生物序列比对的遗传算法.并对几组DNA序列进行了测试.     

基于遗传算法与星比对的多序列比对混合算法

多序列比对(MSA)是一个典型的NP完全问题,星比对是一种有效的多序列比对算法。文章针对MSA问题提出了将遗传算法与星比对算法结合在一起的混合算法,该算法充分发挥了遗传算法和星比对算法的优越性,可提高求解MSA问题的计算精度和计算速度,整个算法模拟了自然界进化的周期性,较好的解决了群体的多样性和收敛深度的矛盾。实验表明,该算法是有效的。     

基于网络遗传算法的全局优化

本文在分析当前全局优化方法研究现状的基础上,提出了一种改进的遗传算法――网络遗传算法,应用简单实例说明了网络遗传算法的具体操作,同时应用大量数值实例证明了网络遗传算法解决全局优化问题的可行性、正确性、有效性。     

基于遗传算法的多序列比对算法研究

本文使用遗传算法解决多序列比对问题,并进一步研究了各种遗传算子在比对过程中所起的作用,对算法进行了改进。最后实现了一个多序列比对程序,对实验结果进行分析。     

引入序列信息的残基相互作用网络比对算法

残基相互作用网络比对,对于研究蛋白质结构与功能的关系具有重要意义.在基于网络拓扑信息进行网络比对的MAGNA算法基础上,将蛋白质的序列信息（即残基匹配度）引入到其优化函数中,确定拓扑信息和序列信息对比对的影响程度,提出适合于残基相互作用网络比对的SI-MAGNA算法.实验结果表明,SI-MAGNA算法比现有的基于网络拓扑信息的经典比对方法（GRAAL、MI-GRAAL、MAGNA和CytoGEDEVO）具有更高的边正确性（edge correctness,简称EC）.最后,使用SI-MAGNA算法对来自不同耐热温度的生物的同源蛋白质进行网络比对和分析,探索蛋白质结构对其热稳定性的影响.     

一种基于动态加权PPI网络的关键蛋白质识别算法

与静态PPI网络相比,动态PPI网络更能体现蛋白质之间相互作用的真实情况,并有效降低PPI网络中的假阴性。现有的关键蛋白质预测方法主要应用在静态PPI网络,忽视了PPI网络的动态特性。为有效预测关键蛋白质,利用基因表达数据提取蛋白质的动态信息,再结合静态PPI网络构建动态PPI网络,然后引入GO术语对网络加权,并基于动态加权PPI网络提出一种新的预测方法-DWE。该方法以蛋白质在动态网络中的动态加权边之和与蛋白质在动态网络中出现的次数的比值衡量蛋白质在网络中的关键性。实验结果表明动态加权PPI网络有助于提高关键蛋白质的预测精度,且DWE方法优于其他几种关键蛋白质预测方法。     

一种多搜索策略的多生物序列比对自适应遗传算法

多生物序列比对是用来计算生物序列间相似性的重要工具，本文在引入熵来度量种群多样性的基础上，提出了一种多搜索策略的自适应遗传算法，其交叉和变异概率随着熵的变化进行自动调整，并且综合考虑了利用动态规划算法来设计遗传操作算子．实验结果表明，这个算法具有较强的全局搜索能力和局部搜索能力，并且能有效的克服未成熟收敛问题．     

基于蛋白质相互作用界面的比对算法研究

蛋白质相互作用界面是蛋白质相互作用产生的物理载体。考虑蛋白质相互作用界面间的结构相似性对于研究蛋白质功能,信号传导网络和药物设计具有非常重要的意义,而现有的蛋白质结构比对算法仅适用于蛋白质单体的全局空间结构。我们给出了基于整数二次规划模型的方法来考虑蛋白质相互作用界面的比对问题,该方法整合了蛋白质序列的进化信息、结构信息,并用进化谱的相似性来对比对上的残基打分以衡量其进化保守性。通过计算实验,发现进化上和结构上保守的残基有可能就是对于蛋白质结合起重要作用的残基,即热点。     

PPI网络的改进谱聚类算法

蛋白质相互作用(PPI)网络是生物信息学的一个新的研究领域。近年来谱聚类算法在未知蛋白质的功能预测方面发挥了重要作用,但是它要求事先确定聚类数目,为此提出了一种基于边的得分搜索的谱聚类算法。该算法采用谱聚类方法对数据进行预处理,并通过构造蛋白质节点之间的边的得分矩阵找到数据样本之间的相关性,同时融入粒子群算法来确定边的得分的最佳选择阈值,最后用广度优先遍历结点的方法得到聚类结果。算法在PPI网络数据集上进行了测试,结果表明该算法不但可以自动确定聚类数目,而且聚类结果的正确率和F-measure值都得到了提高。     

一种基于遗传算法的片上网络映射算法

片上网络NoC以其高可扩展性成为片上多核的互连解决方案。IP核到NoC结点的映射是片上网络设计的重要阶段。映射对芯片的性能和功耗有重要的影响。本文详细阐述了映射算法的研究现状,给出了映射算法的分类方法,并且分析各种方法的特点。最后,给出一种采用顺序表示的基于遗传算法的NoC映射算法。实验结果表明,该映射算法能够取得较好的准确性和较高的效率。     

一种改进的基于加权网络的蛋白质复合物识别算法

不断增长的蛋白质相互作用数据使我们能够采用计算方法预测蛋白质复合物。然而,由于实验条件和技术的限制,现有的PPI网络中包含噪声。为了降低噪声对复合物识别所产生的负面影响,提出了一种改进的名为WPC的算法,用于从加权网络中识别蛋白质复合物。给定一个选定节点,所有邻居节点组成候选集,候选集中节点的邻居节点组成邻居集。对于候选集中的节点,若该节点在候选集与邻居集间的加权比低于设定阈值,则将该点剔除。处理后的候选集被标记为复合物。对于没有包含在任何复合物中的节点,如果节点在某一复合物内的平均加权度超过一个自适应的阈值,则将其补充到该复合物中。对WPC算法和现有的几种经典蛋白质复合物识别算法的性能进行了综合比较。实验结果表明,WPC算法的性能优于几种对比的复合物识别算法。     

一种基于动态规划的全局双序列比对优化算法

序列比对是生物信息处理中非常重要的一类方法,基本的序列比对算法是基于动态规划思想提出的。本文提出了一种基于动态规划思想的全局双序列比对优化算法(Optimized Global Pairwise Sequence Alignment based on the idea of Dynamic Programming)OGP-SADP,在保持基本动态规划敏感性的前提下,GOPSA方法计算替换矩阵时只需存储当前相邻两列的元素,同时引用checkpoint技术以减少计算迭代次数,有效降低了时间复杂度和空间复杂度。     

一种基于遗传算法的无线传感器网络定位新算法

针对无线传感器网络节点自身定位问题,提出一种基于遗传算法的新定位算法.该算法假设无线传感器网络中有一定比例的位置已知的节点,通过分析未知节点及其无线射程范围内的已知节点之间的通讯约束和几何关系,建立以未知节点位置为参数的优化设计数学模型,使用遗传算法求解此模型得出未知节点的位置,并通过修改遗传算法参数来提高遗传算法收敛速度.理论分析和试验结果表明,本算法具有很强的健壮性,未知节点的失效和新节点的加入不会影响算法的性能,并且算法定位精度高,条件简单,适合各种规模的无线传感器网络的节点定位.     

基于标准结构熵的PPI网络可靠性研究*

由蛋白质相互作用构成的PPI网络的拓扑特性分析是后基因组时代最重要的研究课题之一。应用标准网络结构熵对DIP数据库中七个物种的八个PPI网络的异质性和可靠性进行分析与研究。分析结果表明,这些PPI网络具有典型的无尺度特性,对随机移除不超过10%的顶点都具有很好的鲁棒性,但对有选择地移除2%的高度顶点就开始表现出极弱的抗攻击性。     

基于遗传算法的蛋白质复合物识别算法

蛋白质互作用网络是一种典型的复杂网络,呈现了明显的社区结构。网络中的社区对应于功能模块,通常被看作蛋白质复合物。蛋白质复合物识别对预测蛋白质功能,解释特定生物进程具有重要作用。基于种子节点扩展的图聚类方法在蛋白质复合物识别中应用广泛。针对此类算法最终结果受种子节点的影响较大,并且在簇的形成过程中搜索空间有限等问题,提出了一种基于遗传算法的蛋白质复合物识别算法GAGC(genetic algorithm based graph clustering),其中个体表示聚类结果(类别之间可能存在重叠节点),以F-measure值作为种群进化的目标函数。算法采用IPCA(improvement development clustering algorithm)算法产生初始种群;针对初始种群,设计了染色体对齐方式以进行交叉操作产生下一代种群。通过与DPClus、MCODE、IPCA、Cluster One、HC-PIN、CFinder等经典算法的对比实验表明,GAGC算法能够扩大图聚类算法的搜索空间,提高解的多样性,进而提高蛋白质复合物检测的性能。