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

DOI10.1007/S10878-007-9132-YMaRDI QIDQ1029706zbMATH OpenOpenAlexDBLPWikidataFDO

Authors 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

biological sequence alignmentblock operationsdynamic programmingscoring schemesstring to string comparison

Mathematics Subject Classification ID

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

Recommendations

• Alignments with Non-overlapping Moves, Inversions and Tandem Duplications in O(n 4) Time
• A sparse dynamic programming algorithm for alignment with non-overlapping inversions
• Alignment with non-overlapping inversions on two strings
• ALIGNMENT-TO-ALIGNMENT EDITING WITH “MOVE GAP” OPERATIONS
• A Space Efficient Algorithm for Sequence Alignment with Inversions

Cites work

• A local algorithm for DNA sequence alignment with inversions
• A space-efficient algorithm for sequence alignment with inversions and reversals
• A sparse dynamic programming algorithm for alignment with non-overlapping inversions
• Algorithms on Strings, Trees and Sequences
• All Highest Scoring Paths in Weighted Grid Graphs and Their Application to Finding All Approximate Repeats in Strings
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Block edit models for approximate string matching
• Geometric applications of a matrix-searching algorithm
• scientific article; zbMATH DE number 5158525 (Why is no real title available?)
• scientific article; zbMATH DE number 2087046 (Why is no real title available?)
• scientific article; zbMATH DE number 2119725 (Why is no real title available?)
• On a cyclic string-to-string correction problem
• On the common substring alignment problem

Cited in

(5)

• A space-efficient algorithm for sequence alignment with inversions and reversals
• Alignment with non-overlapping inversions and translocations on two strings
• Alignments with Non-overlapping Moves, Inversions and Tandem Duplications in O(n 4) Time
• A sparse dynamic programming algorithm for alignment with non-overlapping inversions
• Efficient algorithms for computing the edit distance with non-overlapping inversions

Describes a project that uses

Uses Software

• Darwin

This page was built for publication: Alignments with non-overlapping moves, inversions and tandem duplications in \(O(n^{4})\) time

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