title: Improved algorithms for searching restriction maps.
abstract: We present algorithms for searching a DNA restriction enzyme map for a region that best matches a shorter 'probe' map. Our algorithms utilize a new model of map alignments, and extensive experiments prove our model superior to earlier approaches for certain applications. Let M be the number of map sites and P be the number of probe sites. Our first algorithm, which optimizes only over a restricted class of alignments, requires O(MP log P) worst-case time and O(M + P) space. Our second algorithm, which optimizes over all alignments, runs in O(MP3) time and O(M + P2) space, under reasonable assumptions about the distribution of restriction enzyme cleavage sites. Combining the algorithms gives a map-searching method that optimizes over all alignments in O(MP log P) time in practice. The algorithms' effectiveness is illustrated by searches involving a genomic restriction map of Escherichia coli.
authors.affiliation: Department of Computer Science, Pennsylvania State University, University Park 16802.
authors.forename: W
authors.initials: W
authors.lastname: Miller
authors.forename: J
authors.initials: J
authors.lastname: Barr
authors.forename: K E
authors.initials: KE
authors.lastname: Rudd
mesh_terms: D000465:Algorithms; D003198:Computer Simulation; D008433:Mathematics; D008957:Models, Genetic; D015183:Restriction Mapping