Monge properties of sequence alignment

DOI10.1016/J.TCS.2011.12.068MaRDI QIDQ418004zbMATH OpenOpenAlexFDO

Authors 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 complexityalignmentedit distancelongest common subsequencematrix multiplicationstring matchingMonge propertycyclic stringsincremental string comparison

Mathematics Subject Classification ID

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

Recommendations

• Publication:4886031
• ALIGNMENT-TO-ALIGNMENT EDITING WITH “MOVE GAP” OPERATIONS
• scientific article; zbMATH DE number 6792426
• Parametric optimization of sequence alignment
• scientific article; zbMATH DE number 742991

Cites work

• scientific article; zbMATH DE number 4027206 (Why is no real title available?)
• scientific article; zbMATH DE number 1044854 (Why is no real title available?)
• scientific article; zbMATH DE number 3272833 (Why is no real title available?)
• A Subquadratic Sequence Alignment Algorithm for Unrestricted Scoring Matrices
• A new approach to pattern matching in degenerate DNA/RNA sequences and distributed pattern matching
• A special case of the \(n\)-vertex traveling-salesman problem that can be solved in O(\(n\)) time
• All Highest Scoring Paths in Weighted Grid Graphs and Their Application to Finding All Approximate Repeats in Strings
• An all-substrings common subsequence algorithm
• An analysis of the Burrows-Wheeler transform
• Compression of individual sequences via variable-rate coding
• Efficient Parallel Algorithms for String Editing and Related Problems
• Fast distance multiplication of unit-Monge matrices
• Fundamentals of Computation Theory
• Geometric applications of a matrix-searching algorithm
• Incremental String Comparison
• New Data Structures for Orthogonal Range Queries
• On a cyclic string-to-string correction problem
• On-line dynamic programming with applications to the prediction of RNA secondary structure
• Perspectives of Monge properties in optimization
• Rapid dynamic programming algorithms for RNA secondary structure
• Semi-local longest common subsequences in subquadratic time
• Semi-local string comparison: algorithmic techniques and applications
• Space-Efficient and Fast Algorithms for Multidimensional Dominance Reporting and Counting
• Space-efficient data-analysis queries on grids
• The concave least-weight subsequence problem revisited
• Two algorithms for LCS consecutive suffix alignment

Cited in

(7)

• A Scalable Approximation Algorithm for Weighted Longest Common Subsequence
• Tropical properties of alignment matrices
• On almost Monge all scores matrices
• Fast distance multiplication of unit-Monge matrices
• Fast distance multiplication of unit-Monge matrices
• The Demazure product extended to biwords
• Compositional properties of alignments

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q418004)