Bit-Parallel Algorithm for the Block Variant of the Merged Longest Common Subsequence Problem

被引：2

作者：

Danek, Agnieszka ^{[1
]}

Deorowicz, Sebastian ^{[1
]}

机构：

[1] Silesian Tech Univ, Inst Informat, PL-44100 Gliwice, Poland

来源：

MAN-MACHINE INTERACTIONS 3 | 2014年 / 242卷

关键词：

sequence comparison; genome; longest common subsequence;

D O I：

10.1007/978-3-319-02309-0_18

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

The problem of comparison of genomic sequences is of great importance. There are various measures of similarity of sequences. One of the most popular is the length of the longest common subsequence (LCS). We propose the first bit-parallel algorithm for the variant of the LCS problem, block merged LCS, which was recently formulated in the studies on the whole genome duplication hypothesis. Practical experiments show that our proposal is from 10 to over 100 times faster than existing algorithms.

引用

页码：173 / 181

页数：9

共 50 条

[41] On the parameterized complexity of the repetition free longest common subsequence problem [J].

Blin, Guillaume ;

Bonizzoni, Paola ;

Dondi, Riccardo ;

Sikora, Florian .

INFORMATION PROCESSING LETTERS, 2012, 112 (07) :272-276

[42] The longest common subsequence problem for sequences with nested arc annotations [J].

Lin, GH ;

Chen, ZZ ;

Jiang, T ;

Wen, JJ .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2002, 65 (03) :465-480

[43] A large neighborhood search heuristic for the longest common subsequence problem [J].

Easton, Todd ;

Singireddy, Abhilash .

JOURNAL OF HEURISTICS, 2008, 14 (03) :271-283

[44] A Longest Common Subsequence based Genetic Algorithm for Courseware Design [J].

Jozan, M. Mahdi Barati ;

Taghiyareh, Fattaneh .

2013 FOURTH INTERNATIONAL CONFERENCE ON E-LEARNING AND E-TEACHING (ICELET), 2013, :40-46

[45] A linear space algorithm for computing a longest common increasing subsequence [J].

Sakai, Yoshifumi .

INFORMATION PROCESSING LETTERS, 2006, 99 (05) :203-207

[46] A large neighborhood search heuristic for the longest common subsequence problem [J].

Todd Easton ;

Abhilash Singireddy .

Journal of Heuristics, 2008, 14 :271-283

[47] Achieving TeraCUPS on Longest Common Subsequence Problem using GPGPUs [J].

Ozsoy, Adnan ;

Chauhan, Arun ;

Swany, Martin .

2013 19TH IEEE INTERNATIONAL CONFERENCE ON PARALLEL AND DISTRIBUTED SYSTEMS (ICPADS 2013), 2013, :69-77

[48] A Systolic Architecture with Linear Space Complexity for Longest Common Subsequence Problem [J].

Chen, Chuanpeng ;

Qin, Zhongping .

2009 IEEE 8TH INTERNATIONAL CONFERENCE ON ASIC, VOLS 1 AND 2, PROCEEDINGS, 2009, :33-36

[49] Batch Source-Code Plagiarism Detection Using an Algorithm for the Bounded Longest Common Subsequence Problem [J].

Campos, R. A. Castro ;

Martinez, F. J. Zaragoza .

2012 9TH INTERNATIONAL CONFERENCE ON ELECTRICAL ENGINEERING, COMPUTING SCIENCE AND AUTOMATIC CONTROL (CCE), 2012,

[50] A time efficient algorithm for finding Longest Common Subsequence from two molecular sequences [J].

Rizvi, S. A. M. ;

Agarwal, Pankaj .

2007 IEEE 33RD ANNUAL NORTHEAST BIOENGINEERING CONFERENCE, 2007, :302-+

← 1 2 3 4 5 →