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 metadatas

Cited literature [60 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00619995
Contributor : Maxime Crochemore <>
Submitted on : Wednesday, March 20, 2013 - 6:56:28 PM
Last modification on : Wednesday, April 11, 2018 - 12:12:02 PM
Long-term archiving on : Friday, June 21, 2013 - 3:00:09 AM

File

nato11.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00619995, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

169

Files downloads

263