Dynamic programming algorithms for restriction map comparison

For most sequence comparison problems there is a corresponding map comparison algorithm. While map data may appear to be incompatible with dynarmc programming, we show in this paper that the rigor and eficiency of dynamic programming algorithms carry over to the map comparison algorithms. We present algorithms for restriction map comparison that deal with two types of map errors: (i) closely spaced sites for different enzymes can be ordered incorrectly, and (ii) closely spaced sites for the same enzyme can be mapped as a single site. i%e new algorithms are a natural extension of a previous map Comparison model. Dynamic programming algorithms for computing optimal global and local alignments under the new model are described. i%e new algorithms take about the same order of time as previous map comparison algorithms. Programs implementing some of the new algorithms are used to Jnd similar regions within the Escherichia coli restriction map of Kohara et al.