Physical mapping of chromosomes: A combinatorial problem in molecular biology

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

Research output: Contribution to journalArticlepeer-review

38 Scopus citations


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

Original languageEnglish (US)
Pages (from-to)52-76
Number of pages25
Issue number1-2
StatePublished - Feb 1995
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics


  • Clone
  • DNA
  • Local search
  • Maximum likelihood
  • Oligonucleotide
  • Physical mapping
  • Probe
  • Traveling-salesman problem


Dive into the research topics of 'Physical mapping of chromosomes: A combinatorial problem in molecular biology'. Together they form a unique fingerprint.

Cite this