An efficient dynamic programming algorithm and implementation for RNA secondary structure prediction

	An efficient dynamic programming algorithm and implementation for RNA secondary structure prediction
	Tan, GM; Liu, XC; Sun, NH
	2005
发表期刊	COMPUTATIONAL SCIENCE - ICCS 2005, PT 2
ISSN	0302-9743
卷号	3515 页码:869-876
摘要	RNA secondary structure prediction based on free energy rules for stacking and loop conformation remains a major computational method. The basic dynamic programming algorithm needs O(n(4)) time to calculate the minimum free energy for RNA secondary structure. To date, there are two variants for handling this problem: either the internal loops are bounded by a maximal size k giving a time complexity of O(n(2)*k(2)), or one uses the trick of Rune Lyngso, which makes use of the regularities of loop energies, to reduce time complexity to O(n(3)) without restriction. We propose a new dynamic programming algorithm for RNA secondary structure prediction by analyzing energy rules. Through only additional O(n) space, this algorithm eliminates redundant calculation in the energy calculation of internal loop with unrestricted/restricted size and reduces the time complexity of this part from O(n(4)) to O(n(3)), then the overall time complexity to O(n(3)).
收录类别	SCI
语种	英语
WOS研究方向	Computer Science
WOS类目	Computer Science, Theory & Methods
WOS记录号	WOS:000230023800111
出版者	SPRINGER-VERLAG BERLIN
引用统计
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/9928
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Tan, GM
作者单位	Chinese Acad Sci, Inst Comp Technol, Beijing 100864, Peoples R China
推荐引用方式 GB/T 7714	Tan, GM,Liu, XC,Sun, NH. An efficient dynamic programming algorithm and implementation for RNA secondary structure prediction[J]. COMPUTATIONAL SCIENCE - ICCS 2005, PT 2,2005,3515:869-876.
APA	Tan, GM,Liu, XC,&Sun, NH.(2005).An efficient dynamic programming algorithm and implementation for RNA secondary structure prediction.COMPUTATIONAL SCIENCE - ICCS 2005, PT 2,3515,869-876.
MLA	Tan, GM,et al."An efficient dynamic programming algorithm and implementation for RNA secondary structure prediction".COMPUTATIONAL SCIENCE - ICCS 2005, PT 2 3515(2005):869-876.