Physical Mapping of DNA

Title: Physical Mapping of DNA

Research Question: How can we efficiently determine the physical map of a DNA sequence using restriction enzymes?

Methodology: The study proposes a new approach called the Enhanced Double Digest (EDD) problem. It uses the lengths of the fragments created by two restriction enzymes and some additional length information. The EDD problem is solved in linear time if the lengths in the third set (created by both enzymes) are all distinct. The algorithm is also generalized to handle a small number of duplicate lengths.

Results: The research shows that the EDD problem can be solved in linear time when the lengths in the third set are distinct. It is also proven to be NP-hard, meaning that it is computationally difficult and likely impossible to solve in an efficient way.

Implications: The EDD problem provides an efficient method for determining the physical map of a DNA sequence when the lengths in the third set are distinct. The NP-hardness of the problem indicates that more advanced methods may be needed for cases where the lengths are not distinct. This research contributes to the field of computational biology and DNA physical mapping, providing a practical approach to a complex problem.

Link to Article: https://arxiv.org/abs/0102010v1 Authors: arXiv ID: 0102010v1