一种多序列比对分治算法DCA-ClustalW

A Multiple Sequence Alignment Algorithm DCA-ClustalW

多序列比对是生物信息学研究中最基本的一项内容,多序列比对的精确算法是一个NP-hard问题,一般研究者都侧重于设计多序列比对近似算法,最有代表性的近似算法是ClustalW;分而治之是一种重要的算法设计思想,它将复杂问题分割成更简单的子问题来解决,能有效提高算法效率。本文设计了一个DCA-ClustalW算法,对多序列比对问题,同时考虑从纵向和横向两个方面将复杂问题分割成简单易解的子问题,在BaliBase基准数据集上测试表明,该算法是可行的。

Multiple sequence alignment is the most basic of bioinformatics problem.The multiple sequence alignment algorithms is a NP-hard problem,and researchers now focus on the design of approximation algorithm for multiple sequence alignment.The most representative approximation algorithm is ClustalW.The other hand,the divide and conquer algorithm have been attracted attention.A large problem is divided into simpler problems,can be solved effectively.This paper will combine the DCA and ClustalW,and designed a DCA-ClustalW algorithm taking into account both vertical and horizontal,and seek a compromise between the two.Testing in BaliBase dataset shows that the method is feasible.