Sparse LCS common substring alignment

DOI10.1016/j.ipl.2003.09.006zbMath1178.68186OpenAlexW2120581723WikidataQ56813215 ScholiaQ56813215MaRDI QIDQ1029026

Michal Ziv-Ukelson, Baruch Schieber, Gad M. Landau

Publication date: 9 July 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2003.09.006

zbMATH Keywords

algorithmssparsityLCScommon substring alignment

Mathematics Subject Classification ID

Searching and sorting (68P10) Nonnumerical algorithms (68W05)

Related Items (8)

Dynamic programming algorithms for the mosaic longest common subsequence problem ⋮ Efficient algorithms for finding interleaving relationship between sequences ⋮ Linear-space S-table algorithms for the longest common subsequence problem ⋮ Efficient all path score computations on grid graphs ⋮ On almost Monge all scores matrices ⋮ LCS approximation via embedding into locally non-repetitive strings ⋮ Unnamed Item ⋮ LCS Approximation via Embedding into Local Non-repetitive Strings

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A space efficient algorithm for finding the best nonoverlapping alignment score
• A linear-time algorithm for concave one-dimensional dynamic programming
• The longest common subsequence problem revisited
• Geometric applications of a matrix-searching algorithm
• Speeding up dynamic programming with applications to molecular biology
• Visualization and analysis of clickstream data of online stores for understanding web merchandising
• On the Common Substring Alignment Problem
• An Almost Linear Time Algorithm for Generalized Matrix Searching
• Sequence comparison with mixed convex and concave costs
• A fast algorithm for computing longest common subsequences
• Algorithms for the Longest Common Subsequence Problem
• All Highest Scoring Paths in Weighted Grid Graphs and Their Application to Finding All Approximate Repeats in Strings
• Algorithms on Strings, Trees and Sequences
• Sparse dynamic programming I
• An Algorithm for Locating Nonoverlapping Regions of Maximum Alignment Score

This page was built for publication: Sparse LCS common substring alignment