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

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

A Refining Algorithm Based on Extreme Genetic Algorithm for Multiple Sequence Alignment

The MSA (Multiple Sequence Alignment) problem is NP-hard. In order to achieve a sound alignment, progressive and iterative approaches are generally used, but progressive approaches are unable to adjust misalignments in early stages. Iterative approaches face the challenge on how to escape from local optimal alignments. This paper proposes a novel algorithm for refining multiple sequence alignment, which is based on extreme genetic algorithm (EGA) and mine strategy. EGA is based on recombining extreme elements, which reduces the search time efficiently and finds global extreme easily. Mine strategy can mine bad-aligned blocks in alignment done by other algorithms. Firstly, it mines bad-aligned blocks from multiple sequence alignment using mine strategy. Secondly, all bad-aligned blocks are realigned by EGA. When an initial alignment has been generated by progressive approaches, the novel refinement algorithm can adjust misalignments in initial alignment. A final alignment is generated by incorporating the strength of progressive and iterative approaches. The novel algorithm is tested with the datasets from BAliBASE.