Physical Mapping of Chromosomes: A Combinatorial Problem in Molecular Biology

TitlePhysical Mapping of Chromosomes: A Combinatorial Problem in Molecular Biology
Publication TypeTechnical Report
Year of Publication1993
AuthorsAlizadeh, F., Karp R. M., Newberg L. A., & Weisser D. K.
Other Numbers771

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 traveling 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.

Bibliographic Notes

ICSI Technical Report TR-92-066

Abbreviated Authors

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

ICSI Publication Type

Technical Report