动态规划法进行基因双序列比对的探索和实现

大理大学学报 ›› 2019, Vol. 4 ›› Issue (12): 6-11.

动态规划法进行基因双序列比对的探索和实现

1.大理大学数学与计算机学院，云南大理671003；2.云南省昆虫生物医药研发重点实验室，
云南大理671000；3.云南省2011协同创新平台，云南大理671003

收稿日期:2019-02-18 出版日期:2019-12-15 发布日期:2019-12-15
作者简介:张晓玲，副教授，主要从事程序设计语言、数据结构和高性能算法研究.
基金资助:
大理大学“中国西南药用昆虫及蛛形类资源开发利用2011协同创新中心”2017年度开放课题（理大校办
发〔2018〕16号）；云南省科技厅应用基础研究计划资助项目（2017FA050）；云南省地方本科高校（部分）基础
研究联合专项（2018FH001-064）

Exploration and Realization of Gene Double Sequence Alignment by Dynamic Programming

1. College of Mathematics and Computer, Dali University, Dali, Yunnan 671003, China; 2. Yunnan Provincial Key Laboratory of
Entomological Biopharmaceutial R&D, Dali, Yunnan 671000, China; 3. Yunnan Province 2011 Cooperative Innovation Platform, Dali,
Yunnan 671003, China

Received:2019-02-18 Online:2019-12-15 Published:2019-12-15

摘要/Abstract

摘要： 动态规划法是生物信息学中一个最流行的解决方法，序列的比较、基因的识别、蛋白质序列的重排以及蛋白质结构和
功能的分析等很多生物信息学中的问题都可以通过动态规划法解决，但是动态规划法消耗的时间太长，因此一般用于双序列
比对问题的求解中。通过分析序列比对的特征，结合动态规划法的思想，实现了用动态规划法进行同源DNA双序列比对。给
出了具体比对的过程，并列出了算法的实现步骤。

关键词: 序列比对, 动态规划法, 最优子结构性质, 最优对准

Abstract: Dynamic programming is one of the most popular methods in bioinformatics. Many bioinformatics problems, such as
sequence comparison, gene recognition, protein sequence rearrangement, and protein structure and function analysis, can be solved by
dynamic programming, but dynamic programming consumes too much time, so it is generally used to solve double sequence alignment
problems. In this paper, by analyzing the characteristics of sequence alignment and combining with the idea of dynamic programming
method, the homologous DNA double sequence alignment using dynamic programming method is realized. The specific process of
comparison is given, and the implementation steps of the algorithm are listed.

Key words: sequence alignment, dynamic programming, optimal substructure properties, optimal alignment

张晓玲，杨健. 动态规划法进行基因双序列比对的探索和实现[J]. 大理大学学报, 2019, 4(12): 6-11.

Zhang Xiaoling, Yang Jian. Exploration and Realization of Gene Double Sequence Alignment by Dynamic Programming[J]. Journal of Dali University, 2019, 4(12): 6-11.

参考文献

〔1〕DURBIN R，EDDY S，KROGH A，et al. 生物序列分析，
蛋白质和核酸的概率论模型〔M〕. 北京：清华大学出版
社，2002.
〔2〕龚琪，曹金璇，芦天亮. 基于序列比对的勒索病毒同源性
分析〔J〕. 计算机与现代化，2018（2）：1-5.
〔3〕仇瑛姿. 基因序列匹配算法发展及应用〔J〕. 科技创新与
应用，2018（13）：63-64.
〔4〕NEEDLEMAN S B，WUNSCH C D. A General Method
Applicable to the Search for Similarities in the Amino Acid
Sequence of Two Proteins〔J〕. Journal of MolecularBiology，
1970，48（3）：443-453.
〔5〕HIRSCHBERG D. A Linear Space Algorithm for Comput?
ing Maximal Common Subsequenees〔J〕. Comrn ACM，
1975，18（6）：341-343.
〔6〕HIRSCHBERG D S. Serial Computations of Levenshtein
Distances〔M〕/Apostolico A，Galil Z. Pattern Matching
Algorithms. New York：Oxofrd University Press，1997：123-
141.
〔7〕唐玉荣，汪懋华. 基于动态规划的快速序列比对算
法〔J〕. 生物数学学报，2005，20（2）：207-212.
〔8〕姜鲜桃. 双序列比对Needleman-Wunsch 算法研究〔D〕.
呼和浩特：内蒙古农业大学，2017.
〔9〕李丹. 双序列比对算法的研究与改进〔J〕. 电子技术与软
件工程，2017（18）：148.
〔10〕王红梅. 算法设计与分析〔M〕. 北京：清华大学出版社，
2009：115-134.
〔11〕柳富明. 基于动态规划法的原油长输管道最优化
设计〔J〕. 管道技术与设备，2018，151（3）：9-11.
〔12〕NEAPOLITAN R E. 算法基础〔M〕. 贾洪峰，译. 5 版.
北京：人民邮电出版社，2016：58-88.
〔13〕UKKONEN E. On Approximate String Matching〔J〕. Found
Comput Theory，1983，158（6）：487-495.
〔14〕罗志兵. 基于动态规划的基因双序列比对研究〔J〕.
现代计算机，2017（32）：28-33.
〔15〕MOUNT D W. Bioinformatics：Sequence and Genome
Analysis〔M〕. 钟扬，王莉，张亮，主译. 北京：高等教育出
版社，2003.