Physical mapping of chromosomes: A combinatorial problem in molecular biology

Farid Alizadeh, Richard M. Karp, Lee A. Newberg, Deborah K. Weisser

Research output: Contribution to conferencePaperpeer-review

41 Scopus citations

Abstract

Our purpose is to reconstruct the relative placement of the clones along the DNA molecule; this information is lost in the construction of the clone library. In this article we restrict ourselves to the noiseless case, in which the data are free of experimental error. We also restrict ourselves to hybridization data. However, many of our algorithmic techniques can be extended to incorporate noise and restriction fragment data. Our experiments seem to hint at the following phenomenon. For small values of m, there is simply not enough information in the data to reveal the placement of clones, and therefore, all algorithms are expected to perform poorly. For very large m, the argument of section 6 shows that even the most simple-minded method such as the greedy algorithm is likely to find the true permutation. However, it seems that there is a range of values for m, depending on the underlying placement, where the result of the c++c- objective is superior to those of the greedy or the traveling salesman heuristics.

Original languageEnglish (US)
Pages371-381
Number of pages11
StatePublished - 1993
Externally publishedYes
EventProceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms - Austin, TX, USA
Duration: Jan 25 1993Jan 27 1993

Other

OtherProceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms
CityAustin, TX, USA
Period1/25/931/27/93

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Fingerprint

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

Cite this