Monge properties of sequence alignment

DOI10.1016/J.TCS.2011.12.068zbMATH Open1253.68374OpenAlexW1998561868MaRDI QIDQ418004FDOQ418004

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

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

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)

Cites Work

• An analysis of the Burrows—Wheeler transform
• Title not available (Why is that?)
• Compression of individual sequences via variable-rate coding
• On a cyclic string-to-string correction problem
• Efficient Parallel Algorithms for String Editing and Related Problems
• Space-Efficient and Fast Algorithms for Multidimensional Dominance Reporting and Counting
• 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
• Incremental String Comparison
• On-line dynamic programming with applications to the prediction of RNA secondary structure
• Space-efficient data-analysis queries on grids
• Two algorithms for LCS consecutive suffix alignment
• A Subquadratic Sequence Alignment Algorithm for Unrestricted Scoring Matrices
• Rapid dynamic programming algorithms for RNA secondary structure
• New Data Structures for Orthogonal Range Queries
• Semi-local longest common subsequences in subquadratic time
• Title not available (Why is that?)
• Semi-local string comparison: algorithmic techniques and applications
• An all-substrings common subsequence algorithm
• The concave least-weight subsequence problem revisited
• All Highest Scoring Paths in Weighted Grid Graphs and Their Application to Finding All Approximate Repeats in Strings
• Title not available (Why is that?)
• Fundamentals of Computation Theory
• Title not available (Why is that?)
• A new approach to pattern matching in degenerate DNA/RNA sequences and distributed pattern matching

Cited In (3)

• A Scalable Approximation Algorithm for Weighted Longest Common Subsequence
• Tropical properties of alignment matrices
• 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)