A versatile divide and conquer technique for optimal string alignment

DOI10.1016/S0020-0190(99)00053-8MaRDI QIDQ294680zbMATH OpenWikidataFDO

Authors David R. Powell, Lloyd Allison, Trevor I. Dix

Publication date 16 June 2016

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL http://www.sciencedirect.com/science/article/pii/S0020019099000538?np=y

zbMATH Keywords

dynamic programmingedit distancesequence alignment

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms on strings (68W32)

Recommendations

• Fast linear-space computations of longest common subsequences
• On computing all suboptimal alignments
• Linear-space algorithms that build local alignments from fragments
• Time and space efficient algorithms for constrained sequence alignment
• A linear-space algorithm for the substring constrained alignment problem

Cited in

(3)

• Using Hirschberg's algorithm to generate random alignments of strings
• A linear-space algorithm for the substring constrained alignment problem
• Finding consensus and optimal alignment of circular strings

This page was built for publication: A versatile divide and conquer technique for optimal string alignment

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