An improved algorithm for generalized comparison of minisatellites

One of the most important objects in genetic mapping and forensic studies are minisatellites. They consist of a heterogeneous tandem array of short repeat units called variants. The evolution of minisatellites is realized by tandem duplication and tandem deletion of variants. Jeffrey et al. proposed a method to obtain the sequence of variants, called maps. Bérard and Rivals designed the first algorithm of comparison of two minisatellite maps under an evolutionary model including deletion, insertion, mutation, amplification and contraction. The complexity of this first algorithm was O(n4) in time and O(n3) in space where n is the size of the maps. In this paper we propose a more efficient algorithm using the same generic evolutionary model which is O(n3) in time and O(n2) in space. Our algorithm with this better efficiency can even solve generalized and more refined models.