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

摘要

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