{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T16:59:02Z","timestamp":1648659542029},"reference-count":10,"publisher":"World Scientific Pub Co Pte Lt","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. Bioinform. Comput. Biol."],"published-print":{"date-parts":[[2007,8]]},"abstract":"<jats:p> We study the problem of selecting control clones in DNA array hybridization experiments. The problem arises in the OFRG method for analyzing microbial communities. The OFRG method performs classification of rRNA gene clones using binary fingerprints created from a series of hybridization experiments, where each experiment consists of hybridizing a collection of arrayed clones with a single oligonucleotide probe. This experiment produces analog signals, one for each clone, which then need to be classified, that is, converted into binary values 1 and 0 that represent hybridization and non-hybridization events. In addition to the sample rRNA gene clones, the array contains a number of control clones needed to calibrate the classification procedure of the hybridization signals. These control clones must be selected with care to optimize the classification process. We formulate this as a combinatorial optimization problem called Balanced Covering. We prove that the problem is \u2115\u2119-hard, and we show some results on hardness of approximation. We propose approximation algorithms based on randomized rounding, and we show that, with high probability, our algorithms approximate well the optimum solution. The experimental results confirm that the algorithms find high quality control clones. The algorithms have been implemented and are publicly available as part of the software package called CloneTools. <\/jats:p>","DOI":"10.1142\/s0219720007002977","type":"journal-article","created":{"date-parts":[[2007,9,3]],"date-time":"2007-09-03T11:29:33Z","timestamp":1188818973000},"page":"937-961","source":"Crossref","is-referenced-by-count":0,"title":["ALGORITHMIC APPROACHES TO SELECTING CONTROL CLONES IN DNA ARRAY HYBRIDIZATION EXPERIMENTS"],"prefix":"10.1142","volume":"05","author":[{"given":"QI","family":"FU","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of California, Riverside, CA 92521, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"ELIZABETH","family":"BENT","sequence":"additional","affiliation":[{"name":"Department of Plant Pathology, University of California, Riverside, CA 92521, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"JAMES","family":"BORNEMAN","sequence":"additional","affiliation":[{"name":"Department of Plant Pathology, University of California, Riverside, CA 92521, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"MAREK","family":"CHROBAK","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of California, Riverside, CA 92521, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"NEAL E.","family":"YOUNG","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of California, Riverside, CA 92521, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,21]]},"reference":[{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/17.suppl_1.S39"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2004.11.887"},{"key":"rf6","volume-title":"Computers and Intractability. A Guide to the Theory of NP-Completeness","author":"Garey M. R.","year":"1979"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bti452"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/28.10.e47"},{"key":"rf10","unstructured":"L.\u00a0Valinsky, Molecular Microbial Ecology Manual, 2nd edn., eds. G. A.\u00a0Kowalchuk (Kluwer Academic Publishers, Dordrecht, The Netherlands, 2004)\u00a0pp. 569\u2013585."},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1128\/AEM.68.12.5999-6004.2002"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1128\/AEM.68.7.3243-3250.2002"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1093\/hmg\/ddg230"}],"container-title":["Journal of Bioinformatics and Computational Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0219720007002977","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T02:41:50Z","timestamp":1565145710000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0219720007002977"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,8]]},"references-count":10,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2011,11,21]]},"published-print":{"date-parts":[[2007,8]]}},"alternative-id":["10.1142\/S0219720007002977"],"URL":"https:\/\/doi.org\/10.1142\/s0219720007002977","relation":{},"ISSN":["0219-7200","1757-6334"],"issn-type":[{"value":"0219-7200","type":"print"},{"value":"1757-6334","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,8]]}}}