On almost Monge all scores matrices

DOI10.1007/s00453-018-0432-7zbMath1410.68416OpenAlexW2538271714MaRDI 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 alignmentlongest common subsequencesMonge matricesall-path score computationsDIST matricesmultiple-source shortest-paths

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Algorithms on strings (68W32)

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

This page was built for publication: On almost Monge all scores matrices