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 条
[31]   A Multiobjective Approach to the Weighted Longest Common Subsequence Problem [J].
Becerra, David ;
Mendivelso, Juan ;
Pinzon, Yoan .
PROCEEDINGS OF THE PRAGUE STRINGOLOGY CONFERENCE 2012, 2012, :64-74
[32]   A fast algorithm for computing a longest common increasing subsequence [J].
Yang, IH ;
Huang, CP ;
Chao, KM .
INFORMATION PROCESSING LETTERS, 2005, 93 (05) :249-253
[33]   A Fast Longest Common Subsequence Algorithm for Similar Strings [J].
Arslan, Abdullah N. .
LANGUAGE AND AUTOMATA THEORY AND APPLICATIONS, 2010, 6031 :82-93
[34]   A New Efficient Algorithm for Computing the Longest Common Subsequence [J].
Iliopoulos, Costas S. ;
Rahman, M. Sohel .
THEORY OF COMPUTING SYSTEMS, 2009, 45 (02) :355-371
[35]   An almost-linear time and linear space algorithm for the longest common subsequence problem [J].
Guo, JY ;
Hwang, FK .
INFORMATION PROCESSING LETTERS, 2005, 94 (03) :131-135
[36]   A New Efficient Algorithm for Computing the Longest Common Subsequence [J].
Costas S. Iliopoulos ;
M. Sohel Rahman .
Theory of Computing Systems, 2009, 45 :355-371
[37]   A fast longest common subsequence algorithm for biosequences alignment [J].
Liu, Wei ;
Chen, Lin .
COMPUTER AND COMPUTING TECHNOLOGIES IN AGRICULTURE, VOL 1, 2008, 258 :61-+
[38]   The longest common subsequence problem for arc-annotated sequences [J].
Jiang, T ;
Lin, GH ;
Ma, B ;
Zhang, KZ .
COMBINATORIAL PATTERN MATCHING, 2000, 1848 :154-165
[39]   Dynamic programming algorithms for the mosaic longest common subsequence problem [J].
Huang, Kuo-Si ;
Yang, Chang-Biau ;
Tseng, Kuo-Tsung ;
Peng, Yung-Hsing ;
Ann, Hsing-Yen .
INFORMATION PROCESSING LETTERS, 2007, 102 (2-3) :99-103
[40]   The longest common subsequence problem for arc-annotated sequences [J].
Jiang, Tao ;
Lin, Guohui ;
Ma, Bin ;
Zhang, Kaizhong .
Journal of Discrete Algorithms, 2004, 2 (2 SPEC. ISS.) :257-270
12345