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

DOI10.1051/ITA:2005011MaRDI QIDQ4680734zbMATH OpenOpenAlexFDO

Authors Alair Pereira do Lago, Casimir A. Kulikowski, 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, https://eudml.org/doc/245917, https://semanticscholar.org/paper/b3ac92b1731db90bb284bef26b9b4eb738b71dd9

Mathematics Subject Classification ID

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

Recommendations

• A Space Efficient Algorithm for Sequence Alignment with Inversions
• A local algorithm for DNA sequence alignment with inversions
• Alignments with non-overlapping moves, inversions and tandem duplications in \(O(n^{4})\) time
• Alignment with non-overlapping inversions on two strings
• Alignments with Non-overlapping Moves, Inversions and Tandem Duplications in O(n 4) Time

Cites work

• scientific article; zbMATH DE number 1615283 (Why is no real title available?)
• scientific article; zbMATH DE number 3557227 (Why is no real title available?)
• scientific article; zbMATH DE number 1263193 (Why is no real title available?)
• scientific article; zbMATH DE number 1303563 (Why is no real title available?)
• scientific article; zbMATH DE number 1830749 (Why is no real title available?)
• A Faster and Simpler Algorithm for Sorting Signed Permutations by Reversals
• A Space Efficient Algorithm for Sequence Alignment with Inversions
• A fast algorithm for computing longest common subsequences
• A local algorithm for DNA sequence alignment with inversions
• Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement
• Reconstructing an ancestral genome using minimum segments duplications and reversals.
• Sorting Permutations by Reversals and Eulerian Cycle Decompositions
• Sparse dynamic programming I
• Sparse dynamic programming II
• Transforming cabbage into turnip

Cited in

(12)

• Alignment with non-overlapping inversions on two strings
• A local algorithm for DNA sequence alignment with inversions
• A space-efficient algorithm for sequence alignment with inversions and reversals
• Alignments with Non-overlapping Moves, Inversions and Tandem Duplications in O(n 4) Time
• Efficient matching of biological sequences allowing for non-overlapping inversions
• scientific article; zbMATH DE number 5171901 (Why is no real title available?)
• Alignments with non-overlapping moves, inversions and tandem duplications in \(O(n^{4})\) time
• Alignment with non-overlapping inversions and translocations on two strings
• An Algorithm for Locating Nonoverlapping Regions of Maximum Alignment Score
• An efficient algorithm to detect common ancestor genes for non-overlapping inversion and applications
• A Space Efficient Algorithm for Sequence Alignment with Inversions
• A space efficient algorithm for finding the best nonoverlapping alignment score

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

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