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

A Multiple Sequence Alignment Algorithm DCA-ClustalW

作　　者：业宁[1,2] 张倩倩[2] 许翠云[2] 

机构地区：[1]山东大学计算机科学与技术学院,济南250061 [2]南京林业大学信息科学技术学院,南京210037

出　　处：《计算机与数字工程》2010年第11期30-33,80,共5页Computer & Digital Engineering

基　　金：江苏省自然科学基金(编号:BK2009393)资助

摘　　要：多序列比对是生物信息学研究中最基本的一项内容,多序列比对的精确算法是一个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.

关 键 词：多序列比对 分而治之 ClustalW 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]