Practical block sequence alignment with moves
Julien Bourdaillet, Jean‐Gabriel Ganascia, Marie Curie · 2007
Abstract. In this paper we study a sequence alignment problem motivated by textual genetic criticism, a humanities discipline where the notion of edit distance with moves has been rediscovered by philologists. We present a formulation of the problem and show that the usual notion of edit distance with moves does not address it correctly because it is harder. We present a heuristic algorithm for this problem and compare it with a greedy algorithm which computes the edit distance with moves. We show that our algorithm is superior for this task of block sequence alignment with moves. 1