带约束最长公共子序列快速算法

被引：7

作者：

业宁 ^{[1
,2
]}

朱大铭 ^{[1
]}

张倩倩 ^{[2
]}

沈丽容 ^{[2
]}

机构：

[1] 山东大学计算机科学与技术学院

[2] 南京林业大学信息科学技术学院

来源：

南京大学学报(自然科学版) | 2009年 / 45卷 / 05期

关键词：

带约束最长公共子序列; 快速算法; 对偶算法;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

081202 ;

摘要：

带约束最长公共子序列(CLCS)问题有很深的生物学应用背景,常被用来表示同源基因序列相似性的度量,但计算CLCS时间代价很高,最早的CLCS算法的时间复杂度为O(rn4),目前,最快的CLCS算法的时间复杂性为O(rn2).运用对偶原理将带约束最长公共子序列问题转换为带约束最小覆盖集问题,并建立带权的ref树结构,构造包含约束序列的约束覆盖子集,约简带约束覆盖子集并从中搜索关键路径,再通过关键路径构造CLCS,该算法将算法时间复杂度提升到O(nlogn+(q+r)L),r是约束序列的长度,q是两序列序偶的个数,L是两序列的最长公共子序列(LCS)长度.

引用

页码：576 / 584

页数：9

共 10 条

[1] 计算最大堆迭的RNA二级结构预测算法 [J].

刘振栋 ;

李恒武 ;

朱大铭 .

南京大学学报(自然科学版), 2005, (05) :532-537

[2] A simple algorithm for the constrained sequence problems [J].

Chin, FYL ;

De Santis, A ;

Ferrara, AL ;

Ho, NL ;

Kim, SK .

INFORMATION PROCESSING LETTERS, 2004, 90 (04) :175-179

[3] The constrained longest common subsequence problem [J].

Tsai, YT .

INFORMATION PROCESSING LETTERS, 2003, 88 (04) :173-176

[4] Simple and fast linear space computation of longest common subsequences [J].

Rick, C .

INFORMATION PROCESSING LETTERS, 2000, 75 (06) :275-281

[5]

An O ( ND ) difference algorithm and its variations[J] . Eugene W. Myers.Algorithmica . 1986 (1)

[6] A LONGEST COMMON SUBSEQUENCE ALGORITHM SUITABLE FOR SIMILAR TEXT STRINGS [J].

NAKATSU, N ;

KAMBAYASHI, Y ;

YAJIMA, S .

ACTA INFORMATICA, 1982, 18 (02) :171-179

[7]

Algorithms for the Longest Common Subsequence Problem[J] . Daniel S. Hirschberg.Journal of the ACM (JACM) . 1977 (4)

[8]

A fast algorithm for computing longest common subsequences[J] . James W. Hunt,Thomas G. Szymanski.Communications of the ACM . 1977 (5)

[9]

A linear space algorithm for computing maximal common subsequences[J] . D. S. Hirschberg.Communications of the ACM . 1975 (6)

[10]

The String-to-String Correction Problem[J] . Robert A. Wagner,Michael J. Fischer.Journal of the ACM (JACM) . 1974 (1)

← 1 →