Monge properties of sequence alignment

DOI10.1016/J.TCS.2011.12.068zbMath1253.68374OpenAlexW1998561868MaRDI QIDQ418004

Luís M. S. Russo

Publication date: 14 May 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2011.12.068

zbMATH Keywords

computational complexityalignmentstring matchingedit distancematrix multiplicationlongest common subsequenceMonge propertycyclic stringsincremental string comparison

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Protein sequences, DNA sequences (92D20) Algorithms on strings (68W32)

Related Items (1)

A Scalable Approximation Algorithm for Weighted Longest Common Subsequence

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On a cyclic string-to-string correction problem
• A new approach to pattern matching in degenerate DNA/RNA sequences and distributed pattern matching
• Semi-local string comparison: algorithmic techniques and applications
• Semi-local longest common subsequences in subquadratic time
• Rapid dynamic programming algorithms for RNA secondary structure
• 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 all-substrings common subsequence algorithm
• Two algorithms for LCS consecutive suffix alignment
• Space-Efficient Data-Analysis Queries on Grids
• An analysis of the Burrows—Wheeler transform
• Efficient Parallel Algorithms for String Editing and Related Problems
• New Data Structures for Orthogonal Range Queries
• The concave least-weight subsequence problem revisited
• Compression of individual sequences via variable-rate coding
• 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
• On-line dynamic programming with applications to the prediction of RNA secondary structure
• Fundamentals of Computation Theory
• Space-Efficient and Fast Algorithms for Multidimensional Dominance Reporting and Counting

This page was built for publication: Monge properties of sequence alignment