A constraint logic programming framework for constructing DNA restriction maps

Restriction mapping is an important computational problem in molecular biology, particularly in genetic engineering and DNA sequencing. It is different in that it is not only a purely computational problem but involves an interaction between experimental data collection procedures and the mapping algorithms. Consequently, the problem is loosely defined and in practice requires a flexible and versatile algorithm. We describe a framework for solving many restriction mapping problems in the constraint logic programming language CLP (R) which takes advantage of the declarative and powerful features of constraint logic programming. A CLP (R) algorithm is developed for solving a simple restriction mapping problem. The algorithm is the extended to handle more complex variations of restriction mapping such as fragments with errors, circular maps, multiple enzymes and partial digests. The mapping variants are integrated within the same framework and differ in the constraints required to define the kind of map consistency. Various search heuristics and control strategies to improve the search process are also incorporated as constraints.