| 两种带约束的序列比对算法 |
| |
| 引用本文： | 胡婕,业宁,崔静,张俊杰,张倩倩.两种带约束的序列比对算法[J].江南大学学报(自然科学版),2009,8(6):653-656. |
| |
| 作者姓名： | 胡婕 业宁 崔静 张俊杰 张倩倩 |
| |
| 作者单位： | 南京林业大学,信息科学技术学院,江苏,南京,210037 |
| |
| 基金项目： | 国家自然科学基金，江苏省自然科学基金 |
| |
| 摘 要： | 通过理论证明,得出了当距离函数中惩罚因子φ=0时的解应满足的条件,并在此基础上改进两种最长公共子序列的优化算法,使之能够求解出带约束的序列比对问题.这两种改进算法的时间复杂度分别为O(nmr)和O(nm(r+1)),空间复杂度分别为O(nmr)和O((n+m)(r+1)).推导出算法应满足在两序列中插入的空位符数目分别为(m-l)和(n-l),使比对结果中不会出现错配,保证了比对的质量.实现了基于回溯的改进算法,验证了其求解带约束的序列比对问题的有效性.
|
| 关 键 词： | 生物信息学 带约束的序列比对 距离函数 回溯 分而治之 |
Two Algorithms for Constrained Sequence Alignment Problem |
| |
| HU Jie,YE Ning,CUI Jing,ZHANG Jun-jie,ZHANG Qian-qian.Two Algorithms for Constrained Sequence Alignment Problem[J].Journal of Southern Yangtze University:Natural Science Edition,2009,8(6):653-656. |
| |
| Authors: | HU Jie YE Ning CUI Jing ZHANG Jun-jie ZHANG Qian-qian |
| |
| Abstract: | |
| |
| Keywords: | |
| 本文献已被 维普 万方数据 等数据库收录！ |
|
