Mass estimation of DNA molecules and extraction of ordered restriction maps in optical mapping imagery

L. Parida, D. Geiger

Research output: Contribution to journalArticlepeer-review


The Human Genome Project has been considered "one of the great enterprises of 20th Century Science" [8]. The ultimate goal of many efforts in molecular biology, including the Human Genome Project, is to determine the entire sequence of human DNA and to extract genetic information from it. In this context an important step is to build restriction maps (location of certain identifiable markers) of portions of the DNA [8]. Optimal Mapping [24], [17], [21], a process that fixes elongated DNA molecules onto treated surfaces, is a very promising emerging technology for rapid production of ordered restriction maps. Our modeling and solution of detection, mass estimation, and extraction of ordered restriction maps of DNA molecules attempts to understand/answer questions of significant importance to geneticists, biologists, and chemists. In this paper we first describe the vision process that identifies the DNA molecules along with the restriction sites, and then model the restriction map problem and describe the algorithm that we use to extract the maps from the data. The input to the vision process is an image of the DNA molecules. We propose a simple Markov chain to model the DNA fragments, and use Single Source Shortest Path (SSSP) algorithms to detect and measure the apparent length of the DNA fragments. This is at the heart of the imaging software in use at the laboratory for over 2 years: the practical implementation continues to undergo various fine-tuning processes. In the second part we model the ordered restriction map as a combinatorial problem which we call the Binary Flip Cut (BFC) problem. We prove hardness results for this and several of its variants and offer a practical solution using techniques from mean field annealing/EM algorithm and demonstrate its effectiveness in practice.

Original languageEnglish (US)
Pages (from-to)295-310
Number of pages16
JournalAlgorithmica (New York)
Issue number2-3
StatePublished - 1999


  • Flip cut
  • Optical mapping
  • Shortest path algorithm

ASJC Scopus subject areas

  • General Computer Science
  • Computer Science Applications
  • Applied Mathematics


Dive into the research topics of 'Mass estimation of DNA molecules and extraction of ordered restriction maps in optical mapping imagery'. Together they form a unique fingerprint.

Cite this