Efficient all path score computations on grid graphs

DOI10.1016/J.TCS.2013.07.018MaRDI QIDQ2437757zbMATH OpenOpenAlexFDO

Authors Ury Matarazzo, Dekel Tsur, Michal Ziv-Ukelson

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 alignmentall path score computations

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Paths and cycles (05C38) Algorithms on strings (68W32)

Recommendations

• Efficient all path score computations on grid graphs
• On almost Monge all scores matrices
• scientific article; zbMATH DE number 6792426
• All Highest Scoring Paths in Weighted Grid Graphs and Their Application to Finding All Approximate Repeats in Strings
• A linear-time algorithm for the longest path problem in rectangular grid graphs

Cites work

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

Cited in

(3)

• A substring-substring LCS data structure
• Efficient all path score computations on grid graphs
• On almost Monge all scores matrices

This page was built for publication: Efficient all path score computations on grid graphs

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