Title: Space pruning monotonic search for the non-unique probe selection problem

Authors: Elisa Pappalardo; Beyza Ahlatcioglu Ozkok; Panos M. Pardalos

Addresses: Department of Mathematics and Computer Science, University of Catania, Catania, Italy ' Department of Mathematics, Yildiz Technical University, Istanbul, Turkey ' Department of Industrial and Systems Engineering, Center for Applied Optimization, University of Florida, Florida, USA

Abstract: Identification of targets, generally viruses or bacteria, in a biological sample is a relevant problem in medicine. Biologists can use hybridisation experiments to determine whether a specific DNA fragment, that represents the virus, is presented in a DNA solution. A probe is a segment of DNA or RNA, labelled with a radioactive isotope, dye or enzyme, used to find a specific target sequence on a DNA molecule by hybridisation. Selecting unique probes through hybridisation experiments is a difficult task, especially when targets have a high degree of similarity, for instance in a case of closely related viruses. After preliminary experiments, performed by a canonical Monte Carlo method with Heuristic Reduction (MCHR), a new combinatorial optimisation approach, the Space Pruning Monotonic Search (SPMS) method, is introduced. The experiments show that SPMS provides high quality solutions and outperforms the current state-of-the-art algorithms.

Keywords: probe selection; microarrays; hybridisation; discrete optimisation; bioinformatics; hybrid method; Monte Carlo algorithm; space pruning monotonic search; target identification; viruses; bacteria; DNA fragments; target sequences; DNA molecules.

DOI: 10.1504/IJBRA.2014.058778

International Journal of Bioinformatics Research and Applications, 2014 Vol.10 No.1, pp.59 - 74

Published online: 22 Oct 2014 *

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