Abstract
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 language | English (US) |
---|---|
Pages (from-to) | 295-310 |
Number of pages | 16 |
Journal | Algorithmica (New York) |
Volume | 25 |
Issue number | 2-3 |
DOIs | |
State | Published - 1999 |
Keywords
- Flip cut
- Optical mapping
- Shortest path algorithm
ASJC Scopus subject areas
- General Computer Science
- Computer Science Applications
- Applied Mathematics