多序列比对问题的粒子群优化算法求解

文章提出了一新的算法,利用粒子群优化算法求解多序列比对的问题,这是粒子群优化算法在生物信息学方面的一个新的应用。文章从粒子群算法的原理和多序列比对问题模型入手,来提出怎样改造粒子群优化算法使其可以解决多序列比对问题,最后给出利用粒子群优化算法求解多序列比对的算法,及其测试结果。     

启发式序列比对算法种子长度及其灵敏度研究

序列比对是生物信息学中一个重要的研究方向,它可以确定两个或多个序列之间的相似性,进而判断其同源性并推测出序列间的进化关系。目前,启发式序列比对算法BLAST算法在实际问题用着重要应用。该算法中有一个参数叫做种子(Seeds),种子是控制比对速度和灵敏度的关键。但是种子的长度是基于经验而取的一个固定值,这个经验值并不适合于所有长度序列比对问题。因此,对于两条不用长度的序列之间实现启发式比对就需要取合理长度的种子,以便实现高效快速的比对。文中应用概率随机的思想对不同长度序列比对的种子的长度进行了分析,在此基础上对一定长度下种子的比对灵敏度做出了计算。通过理论推导和实验分析一定灵敏度下种子长度的计算结果是可行且有效的。这就给在高灵敏度(灵敏度几乎等于动态规划算法)下实现快速启发式序列比对的优化提供了保证。     

基于多策略人工蜂群的多序列比对算法

多序列比对是生物信息学中最重要和最具挑战性的任务之一.基于多序列比对是NP 完全组合优化问题,引入Tent 混沌初始化种群策略、不同蜂种的邻域搜索策略和锦标赛选择策略等,提出一种基于多策略人工蜂群的多序列比对算法.该算法应用Tent混沌初始化种群策略以使初始个体多样化并获取较好初始解;针对不同蜂种的特性设计不同的邻域搜索策略以平衡算法的全局探索和局部开发能力.同时引入序列比对的蜜源编码方法以适应多序列比对的离散性.实验结果表明,所提出算法的鲁棒性较强,能获取较好的比对性能和生物特性.     

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

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

带变异算子粒子群算法在多序列比对中的应用

多序列比对(Multiple Sequence Alignment)是进行生物序列分析的最基本任务之一。在对已有的多序列比对算法进行对比分析的基础上,提出了一种新的多序列比对优化算法—带变异算子粒子群多序列比对算法。带变异算子的粒子群算法提高了原有算法跳出局部收敛的能力,将其应用于多序列比对问题中,提高了已有的基于粒子群算法的多序列比对方法的性能,拓展了粒子群算法在多序列比对研究领域中的应用。实验证明,带变异算子粒子群多序列比对算法是有效、可行的。     

一种优化的生物序列比对算法

序列比对是生物信息学中一种基本的信息处理方法，在序列比对所使用的算法中当前重点解决的问题是如何降低算法的时间和空间复杂度。在介绍基本动态规划原理的基础上，提出了一种基于动态规划思想的优化序列比对算法。对3种算法对比实验表明，该算法在保证其生物敏感性的基础上，有效地降低了时间和空间复杂度。     

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

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

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

生物信息学是以计算机为工具对生物信息进行储存、检索和分析的科学。序列比对是生物信息学中的一个基本问题,设计快速而有效的序列比对算法是生物信息学研究的一个重要内容,通过序列比较可以发现生物序列中的功能、结构和进化的信息,序列比较的基本操作是比对。本文介绍了序列比对算法的发展现状,描述了常用的各类序列比对算法,并分析了它们的优劣。     

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

DNA多序列比对是生物信息学中的最重要的任务之一。本文针对多序列比对的特点,提出一种渐进蚁群算法,即将渐进比对算法和蚁群算法相结合。在渐进蚁群算法中,既能克服蚁群算法易于陷入局部最优解、收敛速度慢的特点,又能充分发挥渐进比对算法的优点。     

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

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

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

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

一种多序列比对分治算法DCA-ClustalW

多序列比对是生物信息学研究中最基本的一项内容,多序列比对的精确算法是一个NP-hard问题,一般研究者都侧重于设计多序列比对近似算法,最有代表性的近似算法是ClustalW;分而治之是一种重要的算法设计思想,它将复杂问题分割成更简单的子问题来解决,能有效提高算法效率。本文设计了一个DCA-ClustalW算法,对多序列比对问题,同时考虑从纵向和横向两个方面将复杂问题分割成简单易解的子问题,在BaliBase基准数据集上测试表明,该算法是可行的。     

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

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

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.     

Multiple sequence alignment with affine gap by using multi-objective genetic algorithm

Multiple sequence alignment is of central importance to bioinformatics and computational biology. Although a large number of algorithms for computing a multiple sequence alignment have been designed, the efficient computation of highly accurate and statistically significant multiple alignments is still a challenge. In this paper, we propose an efficient method by using multi-objective genetic algorithm (MSAGMOGA) to discover optimal alignments with affine gap in multiple sequence data. The main advantage of our approach is that a large number of tradeoff (i.e., non-dominated) alignments can be obtained by a single run with respect to conflicting objectives: affine gap penalty minimization and similarity and support maximization. To the best of our knowledge, this is the first effort with three objectives in this direction. The proposed method can be applied to any data set with a sequential character. Furthermore, it allows any choice of similarity measures for finding alignments. By analyzing the obtained optimal alignments, the decision maker can understand the tradeoff between the objectives. We compared our method with the three well-known multiple sequence alignment methods, MUSCLE, SAGA and MSA-GA. As the first of them is a progressive method, and the other two are based on evolutionary algorithms. Experiments on the BAliBASE 2.0 database were conducted and the results confirm that MSAGMOGA obtains the results with better accuracy statistical significance compared with the three well-known methods in aligning multiple sequence alignment with affine gap. The proposed method also finds solutions faster than the other evolutionary approaches mentioned above.     

A genetic algorithm for multiple sequence alignment

Multiple sequence alignment is an important tool in molecular sequence analysis. This paper presents genetic algorithms to solve multiple sequence alignments. Several data sets are tested and the experimental results are compared with other methods. We find our approach could obtain good performance in the data sets with high similarity and long sequences.The software can be found in http://rsdb.csie.ncu.edu.tw/tools/msa.htm.     

一种基于极值思想的多序列联配求精算法

多序列联配（MSA）是一个NP问题，为了取得一个好的联配结果，常用渐进和迭代两种方法，但渐进方法不能调整早期的错误，迭代方法面临怎样跳出局部最优的问题。该文提出了一种新的求精方法，该方法基于极值遗传算法和挖掘策略。极值遗传算法基于极值组合元素，能够减少搜索空间。易于找到全局最优解。算法实现过程中，首先用挖掘算法挖掘出已知联配中的不良序列块，然后所有的不良序列块用极值遗传算法重新联配。当初始的序列是用渐进算法联配时，新的求精方法能调整早期的一些错误，充分结合渐进和迭代算法的优点。最后算法用来自于数据库BAliBASE中数据进行了验证。