A fast algorithm for computing a longest common increasing subsequence

被引：41

作者：

Yang, IH

Huang, CP

Chao, KM ^{[1
]}

机构：

[1] Natl Taiwan Univ, Dept Comp Sci & Informat Engn, Taipei 10764, Taiwan

[2] Natl Taiwan Univ, Inst Networking & Multimedia, Taipei 10764, Taiwan

来源：

INFORMATION PROCESSING LETTERS | 2005年 / 93卷 / 05期

关键词：

algorithms; computational biology; longest common subsequence; longest increasing subsequence;

D O I：

10.1016/j.ipl.2004.10.014

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

Let A = <a(1), a(2), ..., a(m)> and B = <b(1), b(2), ..., b(n)> be two sequences, where each pair of elements in the sequences is comparable. A common increasing subsequence of A and B is a subsequence <a(i1) = b(j1), a(i2) = b(j2), ..., a(i1) = b(j1)>, where i(1) < i(2) < ... < i(1) and j(1) < j(2) < ... < j(l), such that for all 1 less than or equal to k < l, we have a(ik) < a(ik+1). A longest common increasing subsequence of A and B is a common increasing subsequence of the maximum length. This paper presents an algorithm for delivering a longest common increasing subsequence in O(mn) time and O(mn) space. (C) 2004 Elsevier B.V. All rights reserved.

引用

页码：249 / 253

页数：5

共 13 条

[1]

[Anonymous], 1973, SORTING SEARCHING AR

[2] A survey of longest common subsequence algorithms [J].

Bergroth, L ;

Hakonen, H ;

Raita, T .

SPIRE 2000: SEVENTH INTERNATIONAL SYMPOSIUM ON STRING PROCESSING AND INFORMATION RETRIEVAL - PROCEEDINGS, 2000, :39-48

[3] Enumerating longest increasing subsequences and patience sorting [J].

Bespamyatnikh, S ;

Segal, M .

INFORMATION PROCESSING LETTERS, 2000, 76 (1-2) :7-11

[4]

Chvatal V., 1972, STANCS72292

[5] Alignment of whole genomes [J].

Delcher, AL ;

Kasif, S ;

Fleischmann, RD ;

Peterson, J ;

White, O ;

Salzberg, SL .

NUCLEIC ACIDS RESEARCH, 1999, 27 (11) :2369-2376

[6] Fast algorithms for large-scale genome alignment and comparison [J].

Delcher, AL ;

Phillippy, A ;

Carlton, J ;

Salzberg, SL .

NUCLEIC ACIDS RESEARCH, 2002, 30 (11) :2478-2483

[7] COMPUTING LENGTH OF LONGEST INCREASING SUBSEQUENCES [J].

FREDMAN, ML .

DISCRETE MATHEMATICS, 1975, 11 (01) :29-35

[8] FAST ALGORITHM FOR COMPUTING LONGEST COMMON SUBSEQUENCES [J].

HUNT, JW ;

SZYMANSKI, TG .

COMMUNICATIONS OF THE ACM, 1977, 20 (05) :350-353

[9]

MAMBER U, 1989, INTRO ALGORITHMS CRE

[10] A FASTER ALGORITHM COMPUTING STRING EDIT DISTANCES [J].

MASEK, WJ ;

PATERSON, MS .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1980, 20 (01) :18-31

← 1 2 →