On almost Monge all scores matrices

DOI10.1007/s00453-018-0432-7zbMath1410.68416MaRDI QIDQ1755777

Michal Ziv-Ukelson, Dekel Tsur, Amir Carmel

Publication date: 11 January 2019

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2016/6077/

zbMATH Keywords

sequence alignment; longest common subsequences; Monge matrices; all-path score computations; DIST matrices; multiple-source shortest-paths

Mathematics Subject Classification ID

68W40: Analysis of algorithms

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

05C50: Graphs and linear algebra (matrices, eigenvalues, etc.)

68W32: Algorithms on strings

Uses Software

• PROSITE

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A space efficient algorithm for finding the best nonoverlapping alignment score
• Fast algorithms for computing tree LCS
• 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
• Geometric applications of a matrix-searching algorithm
• A special case of the \(n\)-vertex traveling-salesman problem that can be solved in O(\(n\)) time
• Perspectives of Monge properties in optimization
• An almost quadratic time algorithm for sparse spliced alignment
• Efficient all path score computations on grid graphs
• An all-substrings common subsequence algorithm
• Two algorithms for LCS consecutive suffix alignment
• On the Common Substring Alignment Problem
• Multiple-Source Shortest Paths in Embedded Graphs
• Efficient Parallel Algorithms for String Editing and Related Problems
• All Highest Scoring Paths in Weighted Grid Graphs and Their Application to Finding All Approximate Repeats in Strings
• Incremental String Comparison
• A Subquadratic Sequence Alignment Algorithm for Unrestricted Scoring Matrices
• An Algorithm for Locating Nonoverlapping Regions of Maximum Alignment Score
• Monge Property and Bounding Multivariate Probability Distribution Functions with Given Marginals and Covariances
• Fundamentals of Computation Theory
• Linear-time algorithms for max flow and multiple-source shortest paths in unit-weight planar graphs
• Combinatorial Pattern Matching