On almost Monge all scores matrices
type: Item
instance of: scholarly article
title: On almost Monge all scores matrices
zbMATH Open document ID: 1410.68416
author: Amir Carmel
author: Dekel Tsur
author: Michal Ziv-Ukelson
published in: Algorithmica
publication date: 2019-01-11T00:00:00Z
full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2016/6077/
Mathematics Subject Classification ID: 68W32
Mathematics Subject Classification ID: 05C50
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68W40
zbMATH DE Number: 7000178
zbMATH Keywords: sequence alignment
zbMATH Keywords: longest common subsequences
zbMATH Keywords: DIST matrices
zbMATH Keywords: Monge matrices
zbMATH Keywords: all-path score computations
zbMATH Keywords: multiple-source shortest-paths
describes a project that uses: PROSITE
MaRDI profile type: Publication
OpenAlex ID: W2538271714
cites work: Geometric applications of a matrix-searching algorithm
cites work: An all-substrings common subsequence algorithm
cites work: Efficient Parallel Algorithms for String Editing and Related Problems
cites work: A space efficient algorithm for finding the best nonoverlapping alignment score
cites work: Perspectives of Monge properties in optimization
cites work: Multiple-source shortest paths in embedded graphs
cites work: A Subquadratic Sequence Alignment Algorithm for Unrestricted Scoring Matrices
cites work: Linear-time algorithms for max flow and multiple-source shortest paths in unit-weight planar graphs
cites work: Q5390005
cites work: Monge Property and Bounding Multivariate Probability Distribution Functions with Given Marginals and Covariances
cites work: Fundamentals of Computation Theory
cites work: An Algorithm for Locating Nonoverlapping Regions of Maximum Alignment Score
cites work: Combinatorial Pattern Matching
cites work: A dynamic edit distance table
cites work: Multiple-source shortest paths in planar graphs
cites work: Q3084802
cites work: Q3601062
cites work: Incremental String Comparison
cites work: Two algorithms for LCS consecutive suffix alignment
cites work: Sparse LCS common substring alignment
cites work: On the common substring alignment problem
cites work: Efficient all path score computations on grid graphs
cites work: Fast algorithms for computing tree LCS
cites work: A special case of the \(n\)-vertex traveling-salesman problem that can be solved in O(\(n\)) time
cites work: An almost quadratic time algorithm for sparse spliced alignment
cites work: All Highest Scoring Paths in Weighted Grid Graphs and Their Application to Finding All Approximate Repeats in Strings
cites work: Semi-local longest common subsequences in subquadratic time
cites work: Semi-local string comparison: algorithmic techniques and applications
DOI: 10.1007/S00453-018-0432-7
description: scientific article; zbMATH DE number 7000178