渐进方法结合蚁群算法求解多序列比对问题

在所有多重序列比对算法中,渐进比对方法由于简单的算法和高效的计算在生物信息学中得到了广泛的应用。但是渐进方法最大的缺点是在早期阶段形成的错误不能在后期的计算中纠正过来。针对这个问题,我们设计了ProAnt比对算法,即渐进方法和蚁群算法相结合来求解多重序列比对问题。首先,对输入的多个序列进行预处理,用蚁群算法和概率一致性更新计算出所有字符对在最终比对中出现的概率,称为“后验概率”,计算后验概率是为了预防早期错误的发生。然后我们将后验概率作为字符对之间的匹配得分,用渐进方法得到最终的比对结果。用BAliBASE数据库对算法进行测试,实验结果显示,该算法能够在保持合理的运算时间的前提下显著改善渐进比对方法的正确性。     

基于迭代渐进多序列比对算法研究

提出一种新的迭代渐进多序列比对算法IPMSA。采用公共多序列比对数据库BAIiBASE中142组蛋白质序列作为比对测试数据,并与ClustalW进行比较。比对结果的统计分析表明,IPMSA算法的比对准确率高于ClustalW。     

基于改进蚁群算法的多序列比对

提出一种基于改进蚁群算法的多序列比对方法。该算法改变了信息素的更新方式、字符的选择方法、蚂蚁在蚁巢和食物之间往返搜索以及随机分配蚂蚁开始序列等。实验结果表明,改进后的算法不仅有效地克服了基本蚁群多序列比对算法中的停滞现象,而且即使在运行的后期,仍然能以极大的概率搜索较好解。     

基于改进的蚁群算法的多序列比对

该文将蚁群算法进行了改进,将其应用于多序列比对,只根据信息素的强度对序列比对进行信息素强度的局部和全局动态更新,在避免了多序列比对容易陷入局部最优解的前提下,提高了收敛速度。同时,本算法应用在多序列比对中的最大优势是减少了传统算法在多序列比对问题中的生成系统树的步骤,减少了多序列比对过程的复杂度,在没有降低比对结果精确度的同时,提高了比对效率。     

一种新的迭代渐进多序列比对算法

该文提出一种新的迭代渐进多序列比对算法IPMSA。该算法先用渐进方法进行多序列比对,然后通过迭代策略,利用上一轮多序列比对结果修正指导树,产生新一轮比对。重复这一过程,直到指导树不再发生变化或满足事先设定的迭代次数为止。以比对数据库BAliBASE中多蛋白质家族1idy为例,对IPMSA算法和ClustalW算法进行的比较研究表明,该算法能更有效地比对分歧较大的序列,并改进其系统发育树。     

自适应蚁群算法在DNA序列比对中应用研究

研究基因DNA序列比对校准问题。由于DNA序列数据量较大,给序列比对造成了很大的复杂性,而传统的聚类算法在分析DNA序列比对数据时的低效性和分类精度低问题缺陷,提出了一种基于改进的自适应蚁群算法的DNA序列比对算法。首先给出一个计分函数和一个得分策略,再任意给出一对DNA序列,建立一个序列比对矩阵。根据蚂蚁所走过的方向和得分比例来计算序列,同时信息素的变化量采用矩阵来存储,经过有限次迭代,蚂蚁找到一条最优路径,最终一条就是与原来DNA最相似的DNA链。实验结果表明,改进的算法具有一定的时间和精度的优越性,更适于解决大规模DNA序列数据比对问题。     

多重序列比对的蚁群算法

序列多重比对是生物信息学特别是生物序列分析中的一个重要的操作.提出了一种解决多重序列比对的蚁群算法,利用了人工蚂蚁逐个选择各个序列中的字符进行配对.在算法中,蚂蚁根据信息素、字符匹配得分以及位置偏差等信息决定选择各序列中的字符的概率,通过信息素的更新与调节相结合的策略,以及参数的动态自适应调节方法,较为有效地解决了局部收敛的问题,加强了算法寻求全局最优解的能力.实验显示,该算法可以有效解决多重序列比对问题.     

基于信息素智能更新的蚁群双序列比对算法

序列比对算法是生物信息学中重要的研究方向之一。提出了一种基于信息素智能更新的蚁群双序列比队算法,该算法利用历史最优信息来更新信息素,避免出现早熟现象,加速算法的后期收敛。实验表明该方法是有效性和可行的。     

自适应蚁群算法在序列比对中的应用

序列比对是生物信息学的重要研究工具。蚁群算法是一种新型的模拟进化算法,并被成功地应用于旅行商问题(TSP)等组合优化问题中。该文将蚁群算法应用于序列比对,并提出基于自适应调整信息素的改进算法。仿真结果表明这种新的比对算法是有效的,而它的改进算法的效果更为理想。     

基于蚁群遗传算法的氨基酸序列比对方法

蚁群遗传算法是在蚁群算法的基础上用遗传算法对其参数进行优化而产生的一种改进算法。把蚁群遗传算法应用于生物信息学中的氨基酸序列比对上,从而提出了一种新颖的蚁群遗传序列比对算法,实验结果表明这种新颖的序列比对算法是非常有效的。     

求解多重序列比对问题的蚁群算法

多重序列比对是生物信息学特别是生物序列分析中一个重要的基本操作。提出求解多重序列比对问题的蚁群算法,利用人工蚂蚁逐个选择各个序列中的字符进行配对。在算法中,蚂蚁根据信息素、字符匹配得分以及位置偏差等信息决定选择各序列中字符的概率,通过信息素的更新与调节相结合的策略较为有效地解决了局部收敛的问题,加强了算法寻求全局最优解的能力。另外在该算法的基础上,提出了基于分治策略的多序列比对蚁群求解算法,不但减少了原算法的计算时间,而且显著改善了算法所求得的解的质量。     

一种新型求解多序列比对问题的方法

多序列比对问题是生物信息科学中一个非常重要且具挑战性的课题,并已经被证明属于问题.为了克服以往算法中的求解速度慢的缺点,本文提出了一种基于遗传算法和蚁群算法的算法来求解的新方法,在单独使用遗传算法的基础上再使用蚁群算法来进行局部搜索以便更快速地求得解.实验结果表明,遗传-蚁群算法能有效地求解多序列比对问题.     

基于序列结构信息的多序列比对算法

在介绍生物信息学中多序列比对定义和原理的基础上,给出了序列结构信息集的表示形式和基于序列结构信息的度量函数,该函数只与参加比对序列自身信息有关,不受主观因素的影响,能更客观、有效地反映生物序列之间的进化距离.通过利用该函数计算序列间的进化距离,在渐进比对的基础上,采用迭代策略,不断修正指导树,进而提高比对的准确性,避免了局部最优问题.最后,通过实验模拟,本算法在保证不提高计算时间复杂度的基础上,提高了序列比对的准确性,同时也很好地反映了生物学意义.     

Ant Colony Optimization based clustering methodology

In this work we consider spatial clustering problem with no a priori information. The number of clusters is unknown, and clusters may have arbitrary shapes and density differences. The proposed clustering methodology addresses several challenges of the clustering problem including solution evaluation, neighborhood construction, and data set reduction. In this context, we first introduce two objective functions, namely adjusted compactness and relative separation. Each objective function evaluates the clustering solution with respect to the local characteristics of the neighborhoods. This allows us to measure the quality of a wide range of clustering solutions without a priori information. Next, using the two objective functions we present a novel clustering methodology based on Ant Colony Optimization (ACO-C). ACO-C works in a multi-objective setting and yields a set of non-dominated solutions. ACO-C has two pre-processing steps: neighborhood construction and data set reduction. The former extracts the local characteristics of data points, whereas the latter is used for scalability. We compare the proposed methodology with other clustering approaches. The experimental results indicate that ACO-C outperforms the competing approaches. The multi-objective evaluation mechanism relative to the neighborhoods enhances the extraction of the arbitrary-shaped clusters having density variations.     

基于改进蚁群算法的多约束QoS路由优化研究

本文建立了多约束QoS路由模型，并对基本蚁群算法的信息素更新策略进行了改进，提出了一种基于改追蚁群算法的多约束QoS路由优化算法，实例计算结果证明了算法的有效性。     

基于蚁群算法的网格资源发现模型研究

本文通过对传统的网格资源发现存在的问题进行分析,针对其不足,引入蚁群算法,提出基于蚁群算法的网格资源发现模型（AA_GRRM）,设计并分析AA_GRRM的体系结构,并对其关键模块分析设计,以提高网格资源发现效率。     

基于多蚁群的并行ACO算法

通过改变蚁群优化(ACO)算法行为,提出一种新的ACO并行化策略——并行多蚁群ACO算法。针对蚁群算法存在停滞现象的缺点,改进选择策略,实现具有自适应并行机制的选择和搜索策略,以加强其全局搜索能力。并行处理采用数据并行的手段,能减少处理器间的通信时间并获得更好的解。以对称TSP测试集为对象进行比较实验,结果表明,该算法相对于串行算法及现有的并行算法具有一定的优势。     

基于细粒度模型的并行蚁群优化算法

蚁群优化算法的研究和应用已取得了不少重要成果,然而在大规模优化应用中还存在搜索时间长的问题,为此研究了一种基于细粒度模型的并行蚁群算法。实验结果表明,该算法与最新的改进算法相比,搜索速度提高数十倍至数百倍以上。     

基于优化蚁群算法的机器人路径规划

研究机器人导航中的路径规划问题,运用栅格法和图论思想建立环境模型,在该模型中通过蚁群算法进行路径寻优,提出用遗传算法的思想改进已有蚁群算法,即GAA算法。仿真实验结果表明,该算法能有效地提高机器人的路径搜索速度及路径优化、路径平滑等方面的指标。