An algorithm for searching restriction maps.
This paper presents an algorithm that searches a DNA restriction enzyme map for regions that approximately match a shorter 'probe' map. Both the map and the probe consist of a sequence of address-enzyme pairs denoting restriction sites, and the algorithm penalizes a potential match for undetected or missing sites and for discrepancies in the distance between adjacent sites. The algorithm was designed specifically for comparing relatively short DNA sequences with a long restriction map, a problem that will become increasing common as large physical maps are generated. The algorithm has been used to extract information from a restriction map of the entire Escherichia coli genome.
Department of Computer Science, Pennsylvania State University, University Park 16802.
W
W
Miller
J
J
Ostell
K E
KE
Rudd
D000465:Algorithms; D015183:Restriction Mapping; D014584:User-Computer Interface