Title: The Double Digest Problem: finding all solutions

Authors: S. Sur-Kolay, S. Banerjee, S. Mukhopadhyaya, C.A. Murthy

Addresses: Advanced Computing and Microelectronics Unit, Indian Statistical Institute, Kolkata 700108, India. ' Computation and Communication Technologies Group, Honeywell Technology Solutions (HTS), Bangalore, India. ' Department of Computer Science and Engineering, Birla Institute of Technology, Mesra, Kolkata Campus, Kolkata 700107, India. ' Machine Intelligence Unit, Indian Statistical Institute, Kolkata 700108, India

Abstract: The strongly NP-complete Double Digest Problem (DDP), for physical mapping of DNA, is now used for efficient genotyping. Existing methods: are inefficient in tackling large instances; produce only one solution while an instance may have multiple distinct solutions. In this paper, we employ the notion of equivalence among the distinct solutions to obtain almost all of them. Our method comprises two phases: finding a representative from each equivalence class using an elitist Genetic Algorithm (GA); for each representative generating the entire class efficiently. Experimental results tally for known instances. Significant reduction in search space provides notable efficiency.

Keywords: restriction mapping; DDP; double digest problem; GAs; genetic algorithms; equivalence class; bioinformatics; DNA mapping; genotyping.

DOI: 10.1504/IJBRA.2009.028684

International Journal of Bioinformatics Research and Applications, 2009 Vol.5 No.5, pp.570 - 592

Published online: 22 Sep 2009 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article