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

Maxime Crochemore (1) , Gad M. Landau (2) , Baruch Schieber (3) , Michal Ziv-Ukelson (4)

1 LIGM - Laboratoire d'Informatique Gaspard-Monge
2 University of Haifa [Haifa]
3 IBM Thomas J. Watson Research Center
4 Technion - Israel Institute of Technology [Haifa]

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.

Domaines: Algorithme et structure de données [cs.DS]

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⟩