摘要
目前在序列比对中所广泛使用的动态规划算法,虽然能达到最优比对结果,但却由于具有高计算复杂度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.
出处
《生物信息学》
2003年第1期37-41,共5页
Chinese Journal of Bioinformatics
基金
国家重点基础研究发展计划(973计划)(200CB715900)
国家高技术研究发展计划(863计划)(2002AA234021
2002AAB32031)
国家海外青年学者合作研究基金(30128010)
国家自然科学基金重大专项(30393130)
国家自然科学基金重大研究计划(90208017)
国家自然科学基金面上
关键词
核酸序列
序列全局比对
空位插入
计算复杂度
多阶段智能动态规划算法
mucleotide sequence
global sequence alignment
gap insertion
computation complexity
multiple- stage intelligent dynamic programmng
