MOTIVATION: To determine the most powerful artificial intelligence techniques for automated restriction mapping, and use them to create a powerful multiple-enzyme restriction mapping tool. RESULTS: The most effective search engine utilized model-driven exhaustive search and a form of binary logic pruning based on Pratt's separation theory. Additional experimentation led to the development of an input preprocessing module which significantly speeds up searches, and an output post-processing module which enables users to analyze large solution sets and reduce their apparent complexity. AVAILABILITY: An executable version of the resultant tool, Mapper, can be downloaded from our Web site (http://www.ai.eecs.uic.edu) by selecting the 'Software' option. CONTACT: [email protected] (http://www.ai.eecs.uic.edu/ñelson).

Eight important restriction mapping programs, developed between 1978 and 1993, are analyzed and their performance evaluated. The analyses concentrate on the practical value of the programs to molecular biologists who do restriction mapping on a daily basis, rather than on theoretical efficiency. Although all of the programs could find maps consistent with the data, none were able to discriminate reliably the true map from the other consistent maps, given realistic levels of error. To alleviate this problem, we propose an expert mapping system which utilizes the same inferences and mapping techniques used by expert human mappers to reduce the number of false maps found.