| 一种基于动态规划的全局双序列比对优化算法 |
| |
| 引用本文： | 李镍岚,李其申,张永. 一种基于动态规划的全局双序列比对优化算法[J]. 数字社区&智能家居, 2007, 1(6): 1594-1596 |
| |
| 作者姓名： | 李镍岚 李其申 张永 |
| |
| 作者单位： | 南昌航空工业学院计算机学院 江西南昌330063 |
| |
| 基金项目： | 博士启动基金(EA200506141) |
| |
| 摘 要： | 序列比对是生物信息处理中非常重要的一类方法,基本的序列比对算法是基于动态规划思想提出的。本文提出了一种基于动态规划思想的全局双序列比对优化算法(Optimized Global Pairwise Sequence Alignment based on the idea of Dynamic Programming)OGP-SADP,在保持基本动态规划敏感性的前提下,GOPSA方法计算替换矩阵时只需存储当前相邻两列的元素,同时引用checkpoint技术以减少计算迭代次数,有效降低了时间复杂度和空间复杂度。
|
| 关 键 词： | 生物信息学 序列全局比对 动态规划 替换矩阵 |
| 文章编号： | 1009-3044(2007)06-11594-03 |
| 修稿时间： | 2007-02-08 |
An Optimized Global Pairwise Sequence Alignment Based on the Dynamic Programming |
| |
| LI Nie-lan,LI Qi-shen,ZHANG Yong. An Optimized Global Pairwise Sequence Alignment Based on the Dynamic Programming[J]. Digital Community & Smart Home, 2007, 1(6): 1594-1596 |
| |
| Authors: | LI Nie-lan LI Qi-shen ZHANG Yong |
| |
| Abstract: | Sequence alignment is an important information disposal method in bioinformatics, and the basic sequence alignment is presented with the idea of dynamic programming. In this paper, we present an Optimized Global Pairwise Sequence Alignment based on the Dynamic Programming (OGPSADP). In the premise of basic dynamic sensitivity, the method of OGPSADP compute its score matrix by only store current neighboring rows, decrease the number of iterative computation with checkpoint technology, it efficiently reduce the time complexity and space complexity. |
| |
| Keywords: | bioinformatics global sequence alignment dynamic programming score matrix |
| 本文献已被 CNKI 等数据库收录！ |
|
