Alignments with non-overlapping moves, inversions and tandem duplications in \(O(n^{4})\) time

DOI10.1007/s10878-007-9132-yzbMath1175.68570OpenAlexW4249374544WikidataQ56994097 ScholiaQ56994097MaRDI QIDQ1029706

Christian Ledergerber, Christophe Dessimoz

Publication date: 13 July 2009

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-007-9132-y

zbMATH Keywords

dynamic programmingbiological sequence alignmentblock operationsscoring schemesstring to string comparison

Mathematics Subject Classification ID

Dynamic programming (90C39) Protein sequences, DNA sequences (92D20) Algorithms on strings (68W32)

Uses Software

• Darwin

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On a cyclic string-to-string correction problem
• Geometric applications of a matrix-searching algorithm
• A local algorithm for DNA sequence alignment with inversions
• Block edit models for approximate string matching
• A space-efficient algorithm for sequence alignment with inversions and reversals
• On the Common Substring Alignment Problem
• All Highest Scoring Paths in Weighted Grid Graphs and Their Application to Finding All Approximate Repeats in Strings
• Algorithms on Strings, Trees and Sequences
• A sparse dynamic programming algorithm for alignment with non-overlapping inversions
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques