Approximation algorithms of non-unique probes selection for biological target identification
My T. Thai, Ping Deng, Weili Wu, Taieb F. Znati, Onur Şeref, O. Erhun Kundakcioglu, Pãnos M. Pardalos · AIP conference proceedings · 2007
Non‐unique probes are used to identify the targets, i.e., viruses, present in a given sample. Since the number of selected non‐unique probes is equal to the number of hybridization experiments, it is important to find a minimum set of non‐unique probes, which is NP‐complete. Using d‐disjunct matrix, we present two (1+(d+1)logn)‐approximation algorithms to identify at most d targets. Based on our selected non‐unique probes, we also present the decoding algorithms with linear time complexity. In addition, our solutions are fault tolerant. The proposed algorithms can identify at most d targets in the presence of experimental errors.