A Multiobjective Approach to the Weighted Longest Common Subsequence Problem

被引：0

作者：

Becerra, David ^{[1
]}

Mendivelso, Juan ^{[1
]}

Pinzon, Yoan ^{[1
]}

机构：

[1] Univ Nacl Colombia, Fac Ingn, Dept Comp Sci & Ind Engn, Res Grp Algorithms & Combinatories ALGOS UN, Carrera 30 45-03,Edificio 453,Oficina 207, Bogota, Colombia

来源：

PROCEEDINGS OF THE PRAGUE STRINGOLOGY CONFERENCE 2012 | 2012年

关键词：

longest common subsequence; weighted sequences; multiobjective optimization; bioinformatics; ALGORITHMS;

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Finding the Longest Common Subsequence in Weighted Sequences (WLCS) is an important problem in computational biology and bioinformatics. In this paper, we model this problem as a multiobjective optimization problem. As a result, we propose a novel and efficient algorithm that not only finds a WLCS but also the set of all possible solutions. The time complexity of the algorithm depends primarily on the number of length-1 common subsequences between the two input weighted sequences.

引用

页码：64 / 74

页数：11

共 15 条

[1]

Amir A, 2006, LECT NOTES COMPUT SC, V4009, P365

[2] Weighted LCS [J].

Amir, Amihood ;

Gotthilf, Zvi ;

Shalom, B. Riva .

JOURNAL OF DISCRETE ALGORITHMS, 2010, 8 (03) :273-281

[3]

[Anonymous], 1997, ACM SIGACT NEWS

[4]

Bhowmick S., 2010, Journal of Physics: Conference Series, V256, DOI 10.1088/1742-6596/256/1/012012

[5] Exemplar longest common subsequence [J].

Bonizzoni, Paola ;

Della Vedova, Gianluca ;

Dondi, Riccardo ;

Fertin, Guillaume ;

Rizzi, Raffaella ;

Vialette, Stephane .

IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS, 2007, 4 (04) :535-543

[6]

Cygan M, 2011, LECT NOTES COMPUT SC, V6661, P455

[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]

Iliopoulos CS, 2006, FUND INFORM, V71, P259

[10]

Iliopoulos CS, 2004, INT FED INFO PROC, V155, P265

← 1 2 →