异构机群系统上双序列全局比对并行算法

对于处理机节点具有不同的计算速度、通信延迟和存储容量的异构机群系统,考虑通信启动开销,基于可分负载理论,提出一种双序列全局比对问题并行处理的最优分配策略,利用该策略确定出并行迭代次数和分配给各个从处理机的子序列长度。异构PC机群系统上的实验结果表明,提出的双序列全局比对并行算法优于基于平均分配策略的并行比对算法,获得良好的加速和可扩展性。     

生物信息学中一个优化的全局双序列比对算法

最早的生物信息学中序列比对算法是基于动态规划思想的Needleman-Wunsch全局双序列比对算法,由于其时间和空间复杂度巨大,不适合实际的生物序列比对.提出了一种优化的基于动态规划思想的全局双序列比对算法.实验结果表明,该算法在保证其生物敏感性的基础上,有效地降低了时间和空间复杂度.     

一种优化的三序列比对算法及并行实现

序列比对算法在许多不同的领域得到应用。当前,一个重要的应用就是比对大分子,例如DNA和蛋白质序列比对。许多情况,有必要比对三序列。DavidR.Powell就提出过一种使用线性空位罚分的优化的三序列比对算法。这个算法最早是由Ukkonen提出的,该算法基于简单打分的两序列比对。该文通过引入“检查点法”对其进行改进,并充分利用近期蓬勃发展的高性能计算技术,对算法并行化,且在cluster机上实现。     

自发荧光成像中光子传输蒙卡仿真的并行实现

在生物自发光成像领域,将基于蒙特卡罗方法的光子前向传输仿真进行并行化,提高了仿真的速度。首先介绍了所采用的一系列并行机制和串行加速算法,然后分别对并行仿真结果进行正确性验证和性能验证,并与软件MOSE、triMC3D的结果进行了对比,最后对该并行平台进行了总结和展望。     

基于动态规划的Needleman-Wunsch双序列比对算法的分析与研究

生物序列比对是生物信息学中最基础的研究课题之一.基于动态规划的Needleman-Wunsch双序列比对算法主要采用迭代算法及空位罚分规则对基因序列进行逐一比对,计算二者相似性得分,最后通过回溯分析得出序列之间的最佳比对.虽然该算法可以得到最佳比对结果,但是时间复杂度和空间复杂度较高.首先对原算法进行分析,对计算得分和...     

使用GPU加速BLAST算法初探

应用GPU通用高性能编程技术实现了一种加速BLAST算法的新方法。BLAST是目前最常用的用于生物序列查询比对的算法和软件包,其处理速度受到串行化执行和磁盘I/O等因素的影响。本文通过实验分析了BLAST软件包中的典型程序BLASTN的运行热点,并选定关键热点模块,应用CUDA编程技术对其进行并行化改造。对比实验结果表明,对于平均序列长度较大的序列库,应用GPGPU并行化可明显缩短该模块的运行时间,获得超过35倍的加速比。这说明,我们可以利用GPGPU对BLAST进行并行化加速,以满足高性能生物序列查询的需求。     

多序列比对软件T-Coffee的并行化设计与实现

T-Coffee是广泛用于核酸或氨基酸的多序列比对工具.它通过生成基本信息库,扩展库,生成指导树,渐近式比对四个阶段来完成多序列的比对.分析了T-Coffee串行算法及其复杂度,并提出了基于SMP机的并行化版本.目标是使其充分并行化,实验结果表明它明显的提高了性能,并得到了很好的相对加速比.     

基于串行FastLSA的并行算法

提出了一种基于串行Fast LSA算法的两个序列比对的并行算法。主要是对海量级的序列比对，目的是减少串行Fast LSA算法的时间和空间的复杂度。实验结果表明该算法完全可以并行化，而且空间复杂度降到线性空间。     

生物信息学中的序列比对算法

序列比对是生物信息学中基本的信息处理方法,对于发现生物序列中的功能、结构和进化信息具有重要的意义。该文对典型的双序列比对算法Smith-Waterman、FASTA、BLAST以及多序列比对算法CLUSTAL进行了描述和评价;针对目前序列比对算法普遍存在的不足,简单介绍了应用KDD技术进行序列相似性发现的定义及其处理过程。     

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

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

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

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

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

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

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

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

基于MapReduce的量子蚁群算法

量子蚁群算法是在蚁群算法的基础上结合量子计算而提出的,该算法具有较好的全局寻优能力和种群多样性。应用MapReduce的key/value编程模型,将量子蚁群算法并行化,提出了基于MapReduce的量子蚁群算法（MQACA）,并将其部署到Hadoop云计算平台上运行。对0-1背包问题的测试结果证明,随着数据规模的扩大和并行程度的提高,MQACA具有良好的加速比和并行效率。     

Genetic algorithm with ant colony optimization (GA-ACO) for multiple sequence alignment

Multiple sequence alignment, known as NP-complete problem, is among the most important and challenging tasks in computational biology. For multiple sequence alignment, it is difficult to solve this type of problems directly and always results in exponential complexity. In this paper, we present a novel algorithm of genetic algorithm with ant colony optimization for multiple sequence alignment. The proposed GA-ACO algorithm is to enhance the performance of genetic algorithm (GA) by incorporating local search, ant colony optimization (ACO), for multiple sequence alignment. In the proposed GA-ACO algorithm, genetic algorithm is conducted to provide the diversity of alignments. Thereafter, ant colony optimization is performed to move out of local optima. From simulation results, it is shown that the proposed GA-ACO algorithm has superior performance when compared to other existing algorithms.     

基于混合行为的蚁群双序列比对方法

针对基本蚁群算法在双序列比对中存在的易陷入局部最优解及收敛慢的问题,提出了一种新的基于混合行为的蚁群双序列比对算法,该算法通过增加蚂蚁行为模式来增大搜索空间,并且通过改变信息素更新策略来加快收敛速度。实验表明,该算法得到的解的全局性和收敛速度相对基本蚁群算法都有较大提高。     

基于MapReduce的混合蚁群算法研究

传统的蚁群算法在收敛速度上较慢且容易导致局部最优解,本文提出一种基于双模式的混合蚁群算法,即在算法的每次迭代中有比例地选择其中一种模式来获得蚂蚁的最优路径,可以实现在相对较少的时间内寻找出最优路径,且避免陷入局部最优解。由于蚁群算法天然具有并行化的特性,本文将混合蚁群算法与MapReduce结合,大大缩短了算法的执行时间。实验结果表明,基于MapReduce的混合蚁群算法可以实现在相对较少的时间内寻找出较优的路径。     

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

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

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

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

改进遗传蚁群算法求解优化问题的设计与实现

传统的组合优化蚁群算法在求解优化过程中要消耗大量的时间,极易陷入局部最优解和收敛速度过慢等弊端,同时还会产生大量无用的冗余迭代码,运算效率低;因此,提出一种遗传蚁群优化算法;该算法具备了遗传算法快速搜索全局能力的同时也具备了蚁群算法并行性和正反馈机制;利用遗传算法改变选择算子、交叉算子和变异算子操作来确定路径上信息素的分布,将蚁群算法用于特征选择,采用支持向量机分类器分类性能反馈用于评价特征子集解,并通过对改变信息素的迭代、参数选择和增加对信息素局部更新方式指导特征结点重新组合;仿真实验表明,该算法可以有效提高计算精度,加快收敛速度,优化全局最优解的同时增强了系统的鲁棒性和稳定性。