Efficient all path score computations on grid graphs

DOI10.1016/j.tcs.2013.07.018zbMath1282.68204MaRDI QIDQ2437757

Dekel Tsur, Michal Ziv-Ukelson, Ury Matarazzo

Publication date: 13 March 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2013.07.018

zbMATH Keywords

sequence alignment; all path score computations

Mathematics Subject Classification ID

68W40: Analysis of algorithms

68R10: Graph theory (including graph drawing) in computer science

05C38: Paths and cycles

05C85: Graph algorithms (graph-theoretic aspects)

68W32: Algorithms on strings

Related Items

A substring-substring LCS data structure, On almost Monge all scores matrices

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A space efficient algorithm for finding the best nonoverlapping alignment score
• A dynamic edit distance table
• Semi-local string comparison: algorithmic techniques and applications
• Semi-local longest common subsequences in subquadratic time
• Sparse LCS common substring alignment
• New clique and independent set algorithms for circle graphs
• An all-substrings common subsequence algorithm
• Two algorithms for LCS consecutive suffix alignment
• On the Common Substring Alignment Problem
• Efficient Parallel Algorithms for String Editing and Related Problems
• Periodic String Comparison
• All Highest Scoring Paths in Weighted Grid Graphs and Their Application to Finding All Approximate Repeats in Strings
• Incremental String Comparison
• The String-to-String Correction Problem
• A Subquadratic Sequence Alignment Algorithm for Unrestricted Scoring Matrices
• An Algorithm for Locating Nonoverlapping Regions of Maximum Alignment Score
• Fundamentals of Computation Theory