A versatile divide and conquer technique for optimal string alignment

DOI10.1016/S0020-0190(99)00053-8zbMATH Open1339.68337WikidataQ62654267 ScholiaQ62654267MaRDI QIDQ294680FDOQ294680

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

Recommendations

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

zbMATH Keywords

dynamic programmingedit distancesequence alignment

Mathematics Subject Classification ID

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

Cited In (3)

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

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)