一种基于极值域组合的多序列联配求精算法

摘要

多序列联配(MSA)是一个NP问题,常用的方法有渐进法和迭代法,但渐进方法不能调整早期的错误,迭代方法面临怎样跳出局部最优的问题.针对多序列联配问题,提出了极值域组合思想和挖掘策略,极值域组合能够减少搜索空间,易于找到全局最优解.最后得到一种基于极值遗传算法和挖掘策略的多序列联配求精算法.算法用来自于数据库BAliBASE中的数据进行了验证.