Physical mapping of chromosomes: a combinatorial problem in molecular biology

A fundamental tool for exploring the structure of a long DNA sequence is to construct a "library" consisting of many cloned fragments of the sequence. Each fragment can be replicated indefinitely and then "fingerprinted" to obtain partial information about its structure. A common type of fingerprinting is restriction fingerprinting, in which an enzyme called a restriction nuclease cleaves the fragment wherever a particular short sequence of nucleotides (letters `A', `G', `C', and `T') occurs, and the lengths of the resulting pieces are measured. An important combinatorial problem is to determine, from such fingerprint information, the most probable arrangement of the cloned fragments along the overall sequence. However, for a given arrangement, even the likelihood function involves a complicated multifold integral and therefore difficult to compute. We propose an approximation to the likelihood function and develop local search algorithms based on this approximate objective function. O...