An Analysis on Computation of Longest Common Subsequence Algorithm

被引：0

作者：

Kawade, Gaurav ^{[1
]}

Sahu, Santosh ^{[1
]}

Upadhye, Sachin ^{[1
]}

Korde, Nilesh ^{[1
]}

Motghare, Manish ^{[1
]}

机构：

[1] Shri Ramdeobaba Coll Engn & Management, Dept Comp Applicat, Nagpur, Maharashtra, India

来源：

PROCEEDINGS OF THE INTERNATIONAL CONFERENCE ON INTELLIGENT SUSTAINABLE SYSTEMS (ICISS 2017) | 2017年

关键词：

Longest common subsequence; Dynamic Programming; Memory Management; Time complexity; Space complexity;

D O I：

暂无

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

There are many algorithms for computing the longest common subsequence, which are especially used in comparing files, text, comparison of DNA and protein sequences. In this paper we had done comparison among various algorithms which works on two or more strings. In our second approach we had done comparison of algorithms which is able to work on thousands of strings. As per the latest condition there are very few algorithm which works on multiple strings. The spotlight is on development of algorithm which is space efficient and reduced time complexity. In conclusion of the work we put the new proposals for the development of new algorithms for more strings.

引用

页码：982 / 987

页数：6

共 17 条

[1] BASIC LOCAL ALIGNMENT SEARCH TOOL [J].

ALTSCHUL, SF ;

GISH, W ;

MILLER, W ;

MYERS, EW ;

LIPMAN, DJ .

JOURNAL OF MOLECULAR BIOLOGY, 1990, 215 (03) :403-410

[2] A fast and simple algorithm for computing the longest common subsequence of run-length encoded strings [J].

Ann, Hsing-Yen ;

Yang, Chang-Biau ;

Tseng, Chiou-Ting ;

Hor, Chiou-Yi .

INFORMATION PROCESSING LETTERS, 2008, 108 (06) :360-364

[3]

[Anonymous], IEEE T PARALLEL DIST

[4] THE LONGEST COMMON SUBSEQUENCE PROBLEM REVISITED [J].

APOSTOLICO, A ;

GUERRA, C .

ALGORITHMICA, 1987, 2 (03) :315-336

[5]

Chin F. Y. L., 1990, J IN P, V13

[6] ALGORITHMS FOR LONGEST COMMON SUBSEQUENCE PROBLEM [J].

HIRSCHBERG, DS .

JOURNAL OF THE ACM, 1977, 24 (04) :664-675

[7] NEW ALGORITHMS FOR THE LCS PROBLEM [J].

HSU, WJ ;

DU, MW .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1984, 29 (02) :133-152

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

HUNT, JW ;

SZYMANSKI, TG .

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

[9]

KUO S, 1989, ACM SIGIR FORUM, V23, P89

[10] A FILE COMPARISON PROGRAM [J].

MILLER, W ;

MYERS, EW .

SOFTWARE-PRACTICE & EXPERIENCE, 1985, 15 (11) :1025-1040

← 1 2 →