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

DOI10.1016/J.DAM.2015.10.040zbMATH Open1353.90173arXiv1312.2217OpenAlexW1482862754MaRDI QIDQ313774FDOQ313774

Szymon Grabowski

Publication date: 12 September 2016

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

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.

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

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

zbMATH Keywords

longest common subsequencesequence similaritysparse dynamic programmingtabulation

Mathematics Subject Classification ID

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

Cites Work

• A faster algorithm computing string edit distances
• A fast algorithm for computing longest common subsequences
• An information-theoretic lower bound for the longest common subsequence problem
• Fast and compact regular expression matching
• Efficient algorithms for finding interleaving relationship between sequences
• Bounds for the String Editing Problem
• Sparse dynamic programming I
• A Subquadratic Sequence Alignment Algorithm for Unrestricted Scoring Matrices
• BIT-PARALLEL ALGORITHMS FOR THE MERGED LONGEST COMMON SUBSEQUENCE PROBLEM
• Title not available (Why is that?)
• Transposition invariant string matching
• Speeding up transposition-invariant string matching

Cited In (11)

• Title not available (Why is that?)
• A Faster Subquadratic Algorithm for the Longest Common Increasing Subsequence Problem
• Linear-space S-table algorithms for the longest common subsequence problem
• Title not available (Why is that?)
• Title not available (Why is that?)
• A hardness result and new algorithm for the longest common palindromic subsequence problem
• Approximating Longest Common Subsequence in Linear Time: Beating the $\sqrt{{n}}$ Barrier
• An efficient algorithm for LCS problem between two arbitrary sequences
• Sparse Dynamic Programming for Longest Common Subsequence from Fragments
• Locally consistent decomposition of strings with applications to edit distance sketching
• Efficient merged longest common subsequence algorithms for similar sequences

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)