The restriction mapping problem revisited

Pandurangan, Gopal ; Ramesh, H. (2002) The restriction mapping problem revisited Journal of Computer and System Sciences, 65 (3). pp. 526-544. ISSN 0022-0000

Full text not available from this repository.

Official URL:

Related URL:


In computational molecular biology, the aim of restriction mapping is to locate the restriction sites of a given enzyme on a DNA molecule. Double digest and partial digest are two well-studied techniques for restriction mapping. While double digest is NP-complete, there is no known polynomial-time algorithm for partial digest. Another disadvantage of the above techniques is that there can be multiple solutions for reconstruction. In this paper, we study a simple technique called labeled partial digest for restriction mapping. We give a fast polynomial time (O(n2 log n) (worst-case) algorithm for finding all the n sites of a DNA molecule using this technique. An important advantage of the algorithm is the unique reconstruction of the DNA molecule from the digest. The technique is also robust in handling errors in fragment lengths which arises in the laboratory. We give a robust O(n4) worst-case algorithm that can provably tolerate an absolute error of O(Δ/n) (where Δ is the minimum inter-site distance), while giving a unique reconstruction. We test our theoretical results by simulating the performance of the algorithm on a real DNA molecule. Motivated by the similarity to the labeled partial digest problem, we address a related problem of interest—the de novo peptide sequencing problem (ACM-SIAM Symposium on Discrete Algorithms (SODA), 2000, pp. 389–398), which arises in the reconstruction of the peptide sequence of a protein molecule. We give a simple and efficient algorithm for the problem without using dynamic programming. The algorithm runs in time O(k log k), where k is the number of ions and is an improvement over the algorithm in Chen et al.

Item Type:Article
Source:Copyright of this article belongs to Elsevier Science.
ID Code:102331
Deposited On:09 Mar 2018 11:23
Last Modified:09 Mar 2018 11:23

Repository Staff Only: item control page