New tabulation and sparse dynamic programming based techniques for sequence similarity problems

DOI10.1016/J.DAM.2015.10.040MaRDI QIDQ313774zbMATH OpenOpenAlexFDO

Authors Szymon Grabowski

Publication date 12 September 2016

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1312.2217

zbMATH Keywords

longest common subsequencesequence similaritysparse dynamic programmingtabulation

Mathematics Subject Classification ID

Applications of mathematical programming (90C90) Dynamic programming (90C39)

Abstract: Calculating the length of a longest common subsequence (LCS) of two strings $A$ and $B$ of length $n$ and $m$ is a classic research topic, with many worst-case oriented results known. We present two algorithms for LCS length calculation with respectively $O(mnloglogn/lo{g}^{2}n)$ and $O(mn/lo{g}^{2}n+r)$ time complexity, the latter working for $r=o(mn/(lognloglogn))$, where $r$ is the number of matches in the dynamic programming matrix. We also describe conditions for a given problem sufficient to apply our techniques, with several concrete examples presented, namely the edit distance, LCTS and MerLCS problems.

Recommendations

• A fast longest common subsequence algorithm for similar strings
• Efficient algorithms for the longest common subsequence in \(k\)-length substrings
• Fast linear-space computations of longest common subsequences
• A New Efficient Algorithm for Computing the Longest Common Subsequence
• A new efficient algorithm for computing the longest common subsequence

Cites work

• scientific article; zbMATH DE number 5170141 (Why is no real title available?)
• A Subquadratic Sequence Alignment Algorithm for Unrestricted Scoring Matrices
• A fast algorithm for computing longest common subsequences
• A faster algorithm computing string edit distances
• An information-theoretic lower bound for the longest common subsequence problem
• Bit-parallel algorithms for the merged longest common subsequence problem
• Bounds for the String Editing Problem
• Efficient algorithms for finding interleaving relationship between sequences
• Fast and compact regular expression matching
• Sparse dynamic programming I
• Speeding up transposition-invariant string matching
• Transposition invariant string matching

Cited in

(12)

• Multivariate fine-grained complexity of longest common subsequence
• A Faster Subquadratic Algorithm for the Longest Common Increasing Subsequence Problem
• Linear-space S-table algorithms for the longest common subsequence problem
• scientific article; zbMATH DE number 7758340 (Why is no real title available?)
• Computing longest common square subsequences
• scientific article; zbMATH DE number 5024642 (Why is no real title available?)
• A hardness result and new algorithm for the longest common palindromic subsequence problem
• An efficient algorithm for LCS problem between two arbitrary sequences
• Sparse Dynamic Programming for Longest Common Subsequence from Fragments
• Efficient merged longest common subsequence algorithms for similar sequences
• Locally consistent decomposition of strings with applications to edit distance sketching
• Approximating longest common subsequence in linear time: beating the \(\sqrt{n}\) barrier

This page was built for publication: New tabulation and sparse dynamic programming based techniques for sequence similarity problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q313774)