Behshad Behzadi and Jean-Marc Steyaert
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(n^{4}) in time and O(n^{3}) in space where n is the size
of the maps. In this paper we propose a more efficient algorithm using
the same evolutionary model which is O(n^{3}) in time and O(n^{2})
in space. Our algorithm with this better efficiency can even solve
generalized and more refined models.
Home