Approximation algorithms of non-unique probes selection for biological target identification

My T. Thai; Ping Deng; Weill Wu; Taieb Znati

doi:10.1063/1.2817340

Approximation algorithms of non-unique probes selection for biological target identification

My T. Thai, Ping Deng, Weill Wu, Taieb Znati

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

4 Citations (Scopus)

Abstract

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.

Original language	English
Title of host publication	Data Mining, Systems Analysis, and Optimization in Biomedicine
Pages	174-184
Number of pages	11
DOIs	https://doi.org/10.1063/1.2817340
Publication status	Published - 2007
Externally published	Yes
Event	Conference on Data Mining, Systems Analysis, and Optimization in Biomedicine, 2007 - Gainesville, FL, United States Duration: Mar 28 2007 → Mar 30 2007

Publication series

Name	AIP Conference Proceedings
Volume	953
ISSN (Print)	0094-243X
ISSN (Electronic)	1551-7616

Conference

Conference	Conference on Data Mining, Systems Analysis, and Optimization in Biomedicine, 2007
Country/Territory	United States
City	Gainesville, FL
Period	3/28/07 → 3/30/07

Keywords

D-disjunct matrix
Non-adaptive group testing
Non-unique probe
Pooling designs

ASJC Scopus subject areas

Physics and Astronomy(all)

Access to Document

10.1063/1.2817340

Cite this

Thai, MT, Deng, P, Wu, W & Znati, T 2007, Approximation algorithms of non-unique probes selection for biological target identification. in Data Mining, Systems Analysis, and Optimization in Biomedicine. AIP Conference Proceedings, vol. 953, pp. 174-184, Conference on Data Mining, Systems Analysis, and Optimization in Biomedicine, 2007, Gainesville, FL, United States, 3/28/07. https://doi.org/10.1063/1.2817340

@inproceedings{0d710681e2424e4a8f5db828ad563ada,

title = "Approximation algorithms of non-unique probes selection for biological target identification",

abstract = "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.",

keywords = "D-disjunct matrix, Non-adaptive group testing, Non-unique probe, Pooling designs",

author = "Thai, {My T.} and Ping Deng and Weill Wu and Taieb Znati",

year = "2007",

doi = "10.1063/1.2817340",

language = "English",

isbn = "9780735404670",

series = "AIP Conference Proceedings",

pages = "174--184",

booktitle = "Data Mining, Systems Analysis, and Optimization in Biomedicine",

note = "Conference on Data Mining, Systems Analysis, and Optimization in Biomedicine, 2007 ; Conference date: 28-03-2007 Through 30-03-2007",

}

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 -

Approximation algorithms of non-unique probes selection for biological target identification

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this