一个新的核酸序列比对算法及其在序列全局比对中的应用  

A new nucleic acid sequence alignment algorithm and its application in global sequence alignment

作　　者：李静[1] 张宏[1] 薛毅[2] 耿美英[2] 张成岗[1] 

机构地区：[1]军事医学科学院放射医学研究所 [2]北京工业大学应用敷理学院,北京100022

出　　处：《生物信息学》2003年第1期37-41,共5页Chinese Journal of Bioinformatics

基　　金：国家重点基础研究发展计划(973计划)(200CB715900);国家高技术研究发展计划(863计划)(2002AA234021;2002AAB32031);国家海外青年学者合作研究基金(30128010);国家自然科学基金重大专项(30393130);国家自然科学基金重大研究计划(90208017);国家自然科学基金面上

摘　　要：目前在序列比对中所广泛使用的动态规划算法,虽然能达到最优比对结果,但却由于具有高计算复杂度O(N_2)而极大地降低了计算效率。将多阶段动态规划决策算法用于两两序列比对并用Visual BASIC编程实现,结果发现该新算法在将计算复杂度减小到O(N)的同时,也能够获得较为理想的计算精度,预期将在序列全局比对中起重要作用。The presently widely used dynamic programming algorithm in sequence alignment,although can obtain optimal or near optimal result, the computation efficiency of the algorithm is greatly deduced due to its extremely high computation complexity O(N2) .Here we applied the multiple- stage dynamic programming algorithm in pairwiae alignment to devise a new algorithm named SAMIDP and developed the corresponding program using in Visual BASIC language. We find that SAMIDP could not only reduce the computation complexity to O(N),but also obtain even satisfactory aocuncy.lt is expected that the new algorithm will be important in global sequence alignment.

关 键 词：核酸序列 序列全局比对 空位插入 计算复杂度 多阶段智能动态规划算法 

分 类 号：Q754[生物学—分子生物学]