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 条
  • [21] OpenMP Implementation of Parallel Longest Common Subsequence Algorithm for Mathematical Expression Retrieval
    Perepu, Pavan Kumar
    PARALLEL PROCESSING LETTERS, 2021, 31 (02)
  • [22] Thermodynamical approach to the longest common subsequence problem
    Amsalu, Saba
    Matzinger, Heinrich
    Vachkovskaia, Marina
    JOURNAL OF STATISTICAL PHYSICS, 2008, 131 (06) : 1103 - 1120
  • [23] Thermodynamical Approach to the Longest Common Subsequence Problem
    Saba Amsalu
    Heinrich Matzinger
    Marina Vachkovskaia
    Journal of Statistical Physics, 2008, 131 : 1103 - 1120
  • [24] An Analysis on Computation of Longest Common Subsequence Algorithm
    Kawade, Gaurav
    Sahu, Santosh
    Upadhye, Sachin
    Korde, Nilesh
    Motghare, Manish
    PROCEEDINGS OF THE INTERNATIONAL CONFERENCE ON INTELLIGENT SUSTAINABLE SYSTEMS (ICISS 2017), 2017, : 982 - 987
  • [25] A Fast On-Line Algorithm for the Longest Common Subsequence Problem with Constant Alphabet
    Sakai, Yoshifumi
    IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, 2012, E95A (01): : 354 - 361
  • [26] An efficient and hardware-implementable systolic algorithm for the longest common subsequence problem
    Hu, Shu-Hua
    Wang, Cong-Wei
    Chen, Hsing-Lung
    PROCEEDINGS OF 2008 INTERNATIONAL CONFERENCE ON MACHINE LEARNING AND CYBERNETICS, VOLS 1-7, 2008, : 3150 - +
  • [27] NEW SYSTOLIC ARRAYS FOR THE LONGEST COMMON SUBSEQUENCE PROBLEM
    LIN, YC
    PARALLEL COMPUTING, 1994, 20 (09) : 1323 - 1334
  • [28] Algorithms for computing variants of the longest common subsequence problem
    Iliopoulos, Costas S.
    Rahman, A. Sohel
    THEORETICAL COMPUTER SCIENCE, 2008, 395 (2-3) : 255 - 267
  • [29] A hyper-heuristic for the Longest Common Subsequence problem
    Tabataba, Farzaneh Sadat
    Mousavi, Sayyed Rasoul
    COMPUTATIONAL BIOLOGY AND CHEMISTRY, 2012, 36 : 42 - 54
  • [30] A Multiobjective Approach to the Weighted Longest Common Subsequence Problem
    Becerra, David
    Mendivelso, Juan
    Pinzon, Yoan
    PROCEEDINGS OF THE PRAGUE STRINGOLOGY CONFERENCE 2012, 2012, : 64 - 74
12345