PHYSICAL MAPPING OF CHROMOSOMES - A COMBINATORIAL PROBLEM IN MOLECULAR-BIOLOGY

This paper is concerned wth the physical mapping of DNA molecules usin g data about the hybridization of oligonucleotide probes to a library of clones. In mathematical terms, the DNA molecule corresponds to an i nterval on the real line, each clone to a subinterval, and each probe occurs at a finite set of points within the interval. A stochastic mod el for the occurrences of the probes and the locations of the clones i s assumed. Given a matrix of incidences between probes and clones, the task is to reconstruct the most likely interleaving of the clones. Co mbinatorial algorithms are presented for solving approximations to thi s problem, and computational results are presented.