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

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

作　　者：邓伟林[1] 胡桂武[2] 郑启伦[2] 彭宏[2] 胡劲松[2] 

机构地区：[1]广东轻工职业技术学院计算机系,广州510300 [2]华南理工大学计算机科学与工程学院

出　　处：《计算机工程》2006年第2期200-202,共3页Computer Engineering

基　　金：国家自然科学基金资助项目(30230350);广东省自然科学基金资助项目(031454)

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

关 键 词：多序列联配 组合极值 遗传算法 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]