首页 | 官方网站   微博 | 高级检索  
     

一个新的核酸序列比对算法及其在序列全局比对中的应用
引用本文:李静,张宏,薛毅,耿美英,张成岗.一个新的核酸序列比对算法及其在序列全局比对中的应用[J].生物信息学,2003,1(1):37-41.
作者姓名:李静  张宏  薛毅  耿美英  张成岗
作者单位:1. 军事医学科学院放射医学研究所,北京,100850;北京工业大学应用数理学院,北京,100022
2. 军事医学科学院放射医学研究所,北京,100850
3. 北京工业大学应用数理学院,北京,100022
基金项目:国家重点基础研究发展计划(973计划)(200CB715900),国家高技术研究发展计划(863计划)(2002AA234021,2002AAB32031),国家海外青年学者合作研究基金(30128010),国家自然科学基金重大专项(30393130),国家自然科学基金重大研究计划(90208017),国家自然科学基金面上
摘    要:目前在序列比对中所广泛使用的动态规划算法,虽然能达到最优比对结果,但却由于具有高计算复杂度O(N_2)而极大地降低了计算效率。将多阶段动态规划决策算法用于两两序列比对并用Visual BASIC编程实现,结果发现该新算法在将计算复杂度减小到O(N)的同时,也能够获得较为理想的计算精度,预期将在序列全局比对中起重要作用。

关 键 词:核酸序列  序列全局比对  空位插入  计算复杂度  多阶段智能动态规划算法
文章编号:1672-5565(2003)-01-0037-05
修稿时间:2003年10月27

A new nucleic acid sequence alignment algorithm and its application in global sequence alignment
LI Jing,ZHANG Hong,XUE Yi,GENG Mei - ying,ZHANG Cheng- gang.A new nucleic acid sequence alignment algorithm and its application in global sequence alignment[J].China Journal of Bioinformation,2003,1(1):37-41.
Authors:LI Jing  ZHANG Hong  XUE Yi  GENG Mei - ying  ZHANG Cheng- gang
Abstract: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.
Keywords:mucleotide sequence  global sequence alignment  gap insertion  computation complexity  multiple- stage intelligent dynamic programmng
本文献已被 CNKI 万方数据 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司    京ICP备09084417号-23

京公网安备 11010802026262号