title: An O (N2 log N) restriction map comparison and search algorithm.
abstract: We present an O (R log P) time, O (M+P2) space algorithm for searching a restriction map with M sites for the best matches to a shorter map with P sites, where R, the number of matching site pairs, is bounded by MP. As first proposed by Waterman et al. (1984, Nucl. Acids Res. 12, 237-242) the objective function used to score matches is additive in the number of unaligned sites and the discrepancies in the distances between adjacent aligned sites. Our algorithm is basically a sparse dynamic programming computation in which "candidate lists" are used to model the future contribution of all previously computed entries to those yet to be computed. A simple modification to the algorithm computes the distance between two restriction maps with M and N sites, respectively, in O (MN (log M+log N)) time.
authors.affiliation: Department of Computer Science, University of Arizona, Tucson 85721.
authors.forename: E W
authors.initials: EW
authors.lastname: Myers
authors.forename: X
authors.initials: X
authors.lastname: Huang
mesh_terms: D000465:Algorithms; D004247:DNA / Q000235:genetics; D015183:Restriction Mapping
chemical_list: D004247:DNA