Space pruning monotonic search for the non-unique probe selection problem.
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.
Department of Mathematics and Computer Science, University of Catania, Catania, Italy.
Elisa
E
Pappalardo
Department of Mathematics, Yildiz Technical University, Istanbul, Turkey.
Beyza Ahlatcioglu
BA
Ozkok
Department of Industrial and Systems Engineering, Center for Applied Optimization, University of Florida, Florida, USA.
Panos M
PM
Pardalos
D000465:Algorithms; D001483:Base Sequence; D015342:DNA Probes / Q000235:genetics*; D004279:DNA, Viral / Q000235:genetics*; D003627:Data Interpretation, Statistical; D017403:In Situ Hybridization / Q000379:methods*; D008969:Molecular Sequence Data; D017422:Sequence Analysis, DNA / Q000379:methods*
D015342:DNA Probes; D004279:DNA, Viral
DNA fragments; DNA molecules; Monte Carlo algorithm; bacteria; bioinformatics; discrete optimisation; hybrid method; hybridisation; microarrays; probe selection; space pruning monotonic search; target identification; target sequences; viruses