Skip to Main content Skip to Navigation
Conference papers

Re-Use Dynamic Programming for Sequence Alignment: An Algorithmic Toolkit

Abstract : The problem of comparing two sequences S and T to determine their similarity is one of the fundamental problems in pattern matching. In this manuscript we will be primarily concerned with sequences as our objects and with various string comparison metrics. Our goal is to survey a methodology for utilizing repetitions in sequences in order to speed up the comparison process. Within this framework we consider various methods of parsing the sequences in order to frame their repetitions, and present a toolkit of various solutions whose time complexity depends both on the chosen parsing method as well as on the string-comparison metric used for the alignment.
Document type :
Conference papers
Complete list of metadata

Cited literature [60 references]  Display  Hide  Download
Contributor : Maxime Crochemore Connect in order to contact the contributor
Submitted on : Wednesday, March 20, 2013 - 6:56:28 PM
Last modification on : Saturday, January 15, 2022 - 3:56:53 AM
Long-term archiving on: : Friday, June 21, 2013 - 3:00:09 AM


Files produced by the author(s)


  • HAL Id : hal-00619995, version 1



Maxime Crochemore, Gad M. Landau, Baruch Schieber, Michal Ziv-Ukelson. Re-Use Dynamic Programming for Sequence Alignment: An Algorithmic Toolkit. String Algorithmics, 2005, United Kingdom. pp.19-59. ⟨hal-00619995⟩



Record views


Files downloads