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 proceedingConference 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 languageEnglish
Title of host publicationData Mining, Systems Analysis, and Optimization in Biomedicine
Pages174-184
Number of pages11
DOIs
Publication statusPublished - 2007
Externally publishedYes
EventConference on Data Mining, Systems Analysis, and Optimization in Biomedicine, 2007 - Gainesville, FL, United States
Duration: Mar 28 2007Mar 30 2007

Publication series

NameAIP Conference Proceedings
Volume953
ISSN (Print)0094-243X
ISSN (Electronic)1551-7616

Conference

ConferenceConference on Data Mining, Systems Analysis, and Optimization in Biomedicine, 2007
Country/TerritoryUnited States
CityGainesville, FL
Period3/28/073/30/07

Keywords

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

ASJC Scopus subject areas

  • Physics and Astronomy(all)

Fingerprint

Dive into the research topics of 'Approximation algorithms of non-unique probes selection for biological target identification'. Together they form a unique fingerprint.

Cite this