摘要
多序列比对(MSA)是一个典型的NP完全问题,星比对是一种有效的多序列比对算法。文章针对MSA问题提出了将遗传算法与星比对算法结合在一起的混合算法,该算法充分发挥了遗传算法和星比对算法的优越性,可提高求解MSA问题的计算精度和计算速度,整个算法模拟了自然界进化的周期性,较好的解决了群体的多样性和收敛深度的矛盾。实验表明,该算法是有效的。
Multiple Sequence Alignment (MSA) is a typical NP-Complete problem. Star alignment is an effective algorithm for MSA. In this paper,the mixed algorithm of genetic algorithm and Star alignment algorithm are brought forward. The new algorithm not only sufficiently exerts the advantages of the two algorithms,but also improves the computing precision and speed. The algorithm simulates the recurrence of nature evolution process,and solves the contradiction between the diversity of population and the convergence speed. Experiments show the algorithm is effective.
出处
《计算机应用》
CSCD
北大核心
2004年第5期90-91,112,共3页
journal of Computer Applications
基金
国家自然科学基金项目 (3 0 2 3 0 3 50 )
关键词
多序列比对
生物信息学
遗传算法
星比对
算子
Multiple Sequence Alignment(MSA)
genetic algorithm
bioinformatics
star alignment
operator