A sparse dynamic programming algorithm for alignment with non-overlapping inversions

DOI10.1051/ita:2005011zbMath1104.90052OpenAlexW2026106103MaRDI QIDQ4680734

Casimir A. Kulikowski, Alair Pereira do Lago, Ilya B. Muchnik

Publication date: 7 June 2005

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: http://www.numdam.org/item?id=ITA_2005__39_1_175_0

Mathematics Subject Classification ID

Combinatorics on words (68R15) Combinatorial optimization (90C27) Dynamic programming (90C39) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (1)

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

Cites Work

• A local algorithm for DNA sequence alignment with inversions
• Reconstructing an ancestral genome using minimum segments duplications and reversals.
• Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement
• A Space Efficient Algorithm for Sequence Alignment with Inversions
• Transforming cabbage into turnip
• A fast algorithm for computing longest common subsequences
• Sorting Permutations by Reversals and Eulerian Cycle Decompositions
• Sparse dynamic programming I
• Sparse dynamic programming II
• A Faster and Simpler Algorithm for Sorting Signed Permutations by Reversals
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A sparse dynamic programming algorithm for alignment with non-overlapping inversions