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

DOI10.1016/J.DAM.2015.10.040zbMath1353.90173arXiv1312.2217OpenAlexW1482862754MaRDI QIDQ313774

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)

Related Items (8)

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 ⋮ Efficient merged longest common subsequence algorithms for similar sequences ⋮ Linear-space S-table algorithms for the longest common subsequence problem ⋮ Unnamed Item ⋮ An efficient algorithm for LCS problem between two arbitrary sequences ⋮ A Faster Subquadratic Algorithm for the Longest Common Increasing Subsequence Problem ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Speeding up transposition-invariant string matching
• A faster algorithm computing string edit distances
• 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
• A fast algorithm for computing longest common subsequences
• Sparse dynamic programming I
• A Subquadratic Sequence Alignment Algorithm for Unrestricted Scoring Matrices
• BIT-PARALLEL ALGORITHMS FOR THE MERGED LONGEST COMMON SUBSEQUENCE PROBLEM
• Transposition invariant string matching

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