Publications

"Physical Mapping of Chromosomes: A Combinatorial Problem in Molecular Biology"

F. Alizadeh, R. M. Karp, L. A. Newberg, and D. K. Weisser

ICSI Technical Report TR-92-066

September 1993

PDF

Overview:

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. Our local search techniques are extensions of similar strategies for the travelling salesman problem. We provide some computational results which support our choice of objective function. We also briefly study alternative approaches based on pairwise probabilities that two fragments overlap.