TY - GEN
T1 - Approximation algorithms of non-unique probes selection for biological target identification
AU - Thai, My T.
AU - Deng, Ping
AU - Wu, Weill
AU - Znati, Taieb
PY - 2007
Y1 - 2007
N2 - 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.
AB - 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.
KW - D-disjunct matrix
KW - Non-adaptive group testing
KW - Non-unique probe
KW - Pooling designs
UR - http://www.scopus.com/inward/record.url?scp=71449123162&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=71449123162&partnerID=8YFLogxK
U2 - 10.1063/1.2817340
DO - 10.1063/1.2817340
M3 - Conference contribution
AN - SCOPUS:71449123162
SN - 9780735404670
T3 - AIP Conference Proceedings
SP - 174
EP - 184
BT - Data Mining, Systems Analysis, and Optimization in Biomedicine
T2 - Conference on Data Mining, Systems Analysis, and Optimization in Biomedicine, 2007
Y2 - 28 March 2007 through 30 March 2007
ER -