基于遗传算法的一种生物序列比对方法  

Approach to biological sequence alignment based on genetic algorithm

作　　者：敖友云[1] 迟洪钦[1] 

机构地区：[1]上海师范大学数理信息学院,上海200234

出　　处：《计算机工程与设计》2006年第19期3647-3648,3651,共3页Computer Engineering and Design

摘　　要：生物序列比对是对DNA(或RNA,蛋白质)序列,寻找和确定它们的相似部分或稳定区域。二重序列比对问题可采用动态规划方法求得其最优解;多重序列比对问题是一个NP完全的组合优化问题,有待进一步探索与研究。通过合理的编码表示,采用相应的遗传算子,设计了一种求生物序列比对的遗传算法。并对几组DNA序列进行了测试。The key of biological sequence （DNA, RNA, or Protein） alignment is to find their similar part or stable region. Pair-wise sequence alignment is solved by dynamic programming while multiple sequence alignment belongs to NP-complete combinatorial optimization problem and is still solved completely. An approach to biological sequence alignment based on genetic algorithm is presented by employing a suitable chromosome representation and its corresponding genetic operators. And several groups of sequences in the literature are tested.

关 键 词：生物序列比对 多重序列比对 遗传算法 生物信息学 组合优化 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]