期刊文献+

带约束最长公共子序列快速算法 被引量:7

A fast algorithm of constrained longest common subsequence
下载PDF
导出
摘要 带约束最长公共子序列(CLCS)问题有很深的生物学应用背景,常被用来表示同源基因序列相似性的度量,但计算CLCS时间代价很高,最早的CLCS算法的时间复杂度为O(rn4),目前,最快的CLCS算法的时间复杂性为O(rn2).运用对偶原理将带约束最长公共子序列问题转换为带约束最小覆盖集问题,并建立带权的ref树结构,构造包含约束序列的约束覆盖子集,约简带约束覆盖子集并从中搜索关键路径,再通过关键路径构造CLCS,该算法将算法时间复杂度提升到O(nlogn+(q+r)L),r是约束序列的长度,q是两序列序偶的个数,L是两序列的最长公共子序列(LCS)长度. The constrained longest common subsequence problem has deep background applications in biology. It is often used to express the measurement of similarity in homologous gene sequences, hut the time complexity on computation of constrained longest common subsequence(CLCS) is high. The time complexity of the original CLCS algorithm is O(rn^4 ), while presently the time complexity of the fastest CLCS algorithm is O(rn^2). We use the principle of primal-dual which will convert CLCS to the constrained minimal covering set problem, and then establish ref tree structure with weight, structure constrained covering subset which contains the constrained sequence. We also reduce constrained covering subset and search critical paths from it,and finally structure CLCS through critical paths. The time complexity of this algorithm will be upgraded to O(nlogn+(q+r)L), where the r is length of the constrained sequence, o is the number of ordered hairs of the two given sequences and L is the longest common subsequence(LCS) length of the two given sequences.
出处 《南京大学学报(自然科学版)》 CAS CSCD 北大核心 2009年第5期576-584,共9页 Journal of Nanjing University(Natural Science)
基金 国家自然科学基金(60573024) 江苏省自然科学基金(BK2009393)
关键词 带约束最长公共子序列 快速算法 对偶算法 constrained longest common subsequence, fast algorithm, primal-dual
  • 相关文献

参考文献14

  • 1Wagner R A, Fischer M J. The string-to-string correction problem. Journal of the ACM, 1974, 21(1) :168-173.
  • 2Hirschberg D S. A linear space algorithm for computing maximal common subsequences. Communications of the ACM, 1975, 18:341-343.
  • 3Hunt J W, Szymanski T G. A fast algorithm for computing longest common subsequences. Communications of the ACM, 1977, 20:350-353.
  • 4Hirschberg D S. Algorithms for the longest common subsequence problem. Journal of the ACM,1977, 24: 664-675.
  • 5Pevzner P A, Waterman M S. Generalized sequence alignment and duality. Advance Applied Mathematics, 1993,14 (2) :139-171.
  • 6Nakatsu N, Kambayashi Y, Yajima S. A longest common subsequence algorithm suitable for similar texts. Aeta Informatica, 1982,18 : 171 -179.
  • 7Ukkonen E. Algorithms for approximate string matching. Information and Control, 1985, 64: 100-118.
  • 8Myers E W. An O(ND) difference algorithm and its variations. Algorithmica, 1986, 1 : 251-266.
  • 9Rick C. Simple and fast linear space computation of longest common subsequences. Information Processing letters, 2000, 75:275-281.
  • 10刘振栋,李恒武,朱大铭.计算最大堆迭的RNA二级结构预测算法[J].南京大学学报(自然科学版),2005,41(5):532-537. 被引量:4

二级参考文献9

  • 1Nussinov R, Pieczenik G,Griggs J R, et al. Aigorithms for loop matchings SIAMJ. Applied Mathematics, 1978,35(1): 68- 82.
  • 2Zuker M, Stiegler P. Optimal computer folding of large RNA sequences using thermodynamics and auxiliary information. Nucleic Acids Research,1981,9: 133- 148.
  • 3Rivas E, Eddy S R. A dynamic programming algorithm for RNA structure prediction including pseudoknots. Journal of Molecular Biology, 1999,285 :2 053-2 068.
  • 4Lyngso R B, Pedersen C N. RNA pseudoknot prediction in energy based models. Journal of Computational Biology, 2001,7 : 409 - 428.
  • 5李恒武 朱大铭 马绍汉.包含伪结点的RNA二级结构预测的改进算法[J].计算机科学,2003,(9):109-111.
  • 6Jens R, Robert G. Design, implementation and evaluation of a practical pseudoknot folding algorithm based on thermodynamics. BMC Bioinformatics, 2004(5) : 104.
  • 7Turner D H, Sugimoto N, Freier S M. RNA structure prediction. Annual Review of Biophysics Biophysical Chemistry, 1988(17): 167 - 192.
  • 8PseudoBase: Theoretical Biology. http://wwwbio.leidenuniv. nl/-Batenburg/PKBGet. html, 1998.
  • 9周毅,徐柏龄.神经网络中的正交设计法研究[J].南京大学学报(自然科学版),2001,37(1):72-78. 被引量:35

共引文献3

同被引文献75

引证文献7

二级引证文献39

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部