Behshad Behzadi and Jean-Marc Steyaert

The Minisatellite Transformation Problem Revisited: A Run Length Encoded Approach

In this paper we present a more efficient algorithm for comparison of minisatellites which has complexity O(n'^3+ m'^3 + mn'^2+ nm'^2 +mn) where n and m are the lengths of the maps and n' and m' are the sizes of run-length encoded maps. We show that this algorithm makes a significant improvement for the real biological data, dividing the computing time by a factor 30 on a significant set of data.