Monge properties of sequence alignment
type: Item
instance of: scholarly article
title: Monge properties of sequence alignment
zbMATH Open document ID: 1253.68374
author: Luís M. S. Russo
published in: Theoretical Computer Science
publication date: 2012-05-14T00:00:00Z
Mathematics Subject Classification ID: 68W32
Mathematics Subject Classification ID: 68W30
Mathematics Subject Classification ID: 92D20
zbMATH DE Number: 6034858
zbMATH Keywords: cyclic strings
zbMATH Keywords: edit distance
zbMATH Keywords: longest common subsequence
zbMATH Keywords: computational complexity
zbMATH Keywords: string matching
zbMATH Keywords: Monge property
zbMATH Keywords: matrix multiplication
zbMATH Keywords: alignment
zbMATH Keywords: incremental string comparison
MaRDI profile type: Publication
full work available at URL: j.tcs.2011.12.068
OpenAlex ID: W1998561868
cites work: Perspectives of Monge properties in optimization
cites work: A special case of the \(n\)-vertex traveling-salesman problem that can be solved in O(\(n\)) time
cites work: Geometric applications of a matrix-searching algorithm
cites work: Q4347080
cites work: Rapid dynamic programming algorithms for RNA secondary structure
cites work: Efficient Parallel Algorithms for String Editing and Related Problems
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: On a cyclic string-to-string correction problem
cites work: Incremental String Comparison
cites work: Fundamentals of Computation Theory
cites work: Two algorithms for LCS consecutive suffix alignment
cites work: An all-substrings common subsequence algorithm
cites work: Q5417707
cites work: Semi-local string comparison: algorithmic techniques and applications
cites work: Q5557602
cites work: The concave least-weight subsequence problem revisited
cites work: On-line dynamic programming with applications to the prediction of RNA secondary structure
cites work: A Subquadratic Sequence Alignment Algorithm for Unrestricted Scoring Matrices
cites work: Q3768703
cites work: A new approach to pattern matching in degenerate DNA/RNA sequences and distributed pattern matching
cites work: Space-Efficient and Fast Algorithms for Multidimensional Dominance Reporting and Counting
cites work: New Data Structures for Orthogonal Range Queries
cites work: Space-Efficient Data-Analysis Queries on Grids
cites work: An analysis of the Burrows—Wheeler transform
cites work: Compression of individual sequences via variable-rate coding
DOI: 10.1016/J.TCS.2011.12.068
description: scientific article; zbMATH DE number 6034858