AℓEDA Group, Department of Computer Science and Engineering, Bangladesh University of Engineering and Technology (BUET) Dhaka-1000, Bangladesh

---

Abstract—The longest common subsequence problem has been widely studied and used to find out the relationship between sequences. In this paper, we study the interleaving relationship between sequences, that is, we measure the relationship among three sequences, where two of those are interleaved in different ways and then the interleaved sequences are subsequently matched with the third remaining sequence, as pairwise longest common subsequence problems. Given a target sequence T and two other sequences A and B, we need to find out the LCS between M(A,B) and T, where M(A,B) denotes the mergedsequence which consists of A and B. We first present an improved O((Rr + Pm) log log r) time algorithm, where we consider only the matches between sequences; here |T| = n, |A| = m and |B| = r (m  r); R is the total number of ordered pairs of positions at which the two strings A and T match and P denotes the total number of ordered pairs of positions at which the two strings B and T match. Basing on the same idea, we also propose an improved algorithm to solve a block constrained variation of the problem. Running time of the blocked version is O(max{R log log r,P log log r}), where  denotes the number of blocks in A and  denotes the number of blocks in B. However, these improved algorithms do not provide best output in every cases. Therefore we finally fabricate a hybrid algorithm which utilizes the advantages of our proposed algorithms and previous state of the arts algorithms to provide best output in every possible cases, from both time efficiency and space efficiency.

Index Terms—Bioinformatics, Dynamic Programming, Longest Common Subsequence, Merged Sequence, Block Constraint

[PDF]

Cite: AHM Mahfuzur Rahman, M. Sohel Rahman, "Effective Sparse Dynamic Programming Algorithms for Merged and Block Merged LCS Problems," Journal of Computers vol. 9, no. 8, pp. 1743-1754, 2014.