Efficient algorithms for the longest common subsequence in <i>k</i>-length substrings

作     者：Deorowicz, Sebastian Grabowski, Szymon 

作者机构：Silesian Tech Univ Inst Informat PL-44100 Gliwice Poland Lodz Univ Technol Inst Appl Comp Sci PL-90924 Lodz Poland 

出 版 物：《INFORMATION PROCESSING LETTERS》 (信息处理快报)

年 卷 期：2014年第114卷第11期

页      面：634-638页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Polish National Science Center [DEC-2011/03/B/ST6/01588] 

主　　题：Algorithms Combinatorial problems LCSk Sparse dynamic programming 

摘      要：Finding the longest common subsequence in k-length substrings (LCSk) is a recently proposed problem motivated by computational biology. This is a generalization of the well-known LCS problem in which matching symbols from two sequences A and B are replaced with matching non-overlapping substrings of length k from A and B. We propose several algorithms for LCSk, being non-trivial incarnations of the major concepts known from LCS research (dynamic programming, sparse dynamic programming, tabulation). Our algorithms make use of a linear-time and linear-space preprocessing finding the occurrences of all the substrings of length k from one sequence in the other sequence. (C) 2014 Elsevier B.V. All rights reserved.