{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T14:14:42Z","timestamp":1742393682227},"reference-count":17,"publisher":"Oxford University Press (OUP)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007,1,15]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Motivation: The resolution at which genomic alterations can be mapped by means of oligonucleotide aCGH (array-based comparative genomic hybridization) is limited by two factors: the availability of high-quality probes for the target genomic sequence and the array real-estate. Optimization of the probe selection process is required for arrays that are designed to probe specific genomic regions in very high resolution without compromising probe quality constraints.<\/jats:p><jats:p>Results: In this paper we describe a well-defined optimization problem associated with the problem of probe selection for high-resolution aCGH arrays. We propose the whenever possible \u2208-cover as a formulation that faithfully captures the requirement of probe selection problem, and provide a fast randomized algorithm that solves the optimization problem in O(n logn) time, as well as a deterministic algorithm with the same asymptotic performance. We apply the method in a typical high-definition array design scenario and demonstrate its superiority with respect to alternative approaches.<\/jats:p><jats:p>Availability: Address requests to the authors.<\/jats:p><jats:p>Contact: \u00a0dlipson@cs.technion.ac.il<\/jats:p>","DOI":"10.1093\/bioinformatics\/btl316","type":"journal-article","created":{"date-parts":[[2007,1,19]],"date-time":"2007-01-19T18:51:12Z","timestamp":1169232672000},"page":"e77-e83","source":"Crossref","is-referenced-by-count":11,"title":["Optimization of probe coverage for high-resolution oligonucleotide aCGH"],"prefix":"10.1093","volume":"23","author":[{"given":"Doron","family":"Lipson","sequence":"first","affiliation":[{"name":"Computer Science Department 1 \u00a0 1 \u00a0 \u00a0 Technion, Israel"}]},{"given":"Zohar","family":"Yakhini","sequence":"additional","affiliation":[{"name":"Computer Science Department 1 \u00a0 1 \u00a0 \u00a0 Technion, Israel"},{"name":"Agilent Laboratories 2 \u00a0 2 \u00a0 \u00a0 CA, USA"}]},{"given":"Yonatan","family":"Aumann","sequence":"additional","affiliation":[{"name":"Computer Science Department, Bar-Ilan University 3 \u00a0 3 \u00a0 \u00a0 Israel"}]}],"member":"286","published-online":{"date-parts":[[2007,1,15]]},"reference":[{"key":"2023041107132958200_","doi-asserted-by":"crossref","first-page":"495","DOI":"10.1007\/BF01187037","article-title":"Selecting distances in the plane","volume":"9","author":"Agarwal","year":"1993","journal-title":"Algorithmica"},{"key":"2023041107132958200_","doi-asserted-by":"crossref","first-page":"6877","DOI":"10.1038\/sj.onc.1205836","article-title":"Chromosomal imbalances in human lung cancer","volume":"21","author":"Balsara","year":"2002","journal-title":"Oncogene"},{"key":"2023041107132958200_","doi-asserted-by":"crossref","first-page":"17765","DOI":"10.1073\/pnas.0407979101","article-title":"Comparative genomic hybridization using oligonucleotide microarrays and total genomic DNA","volume":"101","author":"Barrett","year":"2004","journal-title":"PNAS"},{"key":"2023041107132958200_","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1101\/gr.2012304","article-title":"High-resolution analysis of DNA copy number using oligonucleotide microarrays","volume":"14","author":"Bignell","year":"2004","journal-title":"Genome Res."},{"key":"2023041107132958200_","doi-asserted-by":"crossref","first-page":"4744","DOI":"10.1158\/0008-5472.CAN-04-1241","article-title":"High-resolution global profiling of genomic alterations with long oligonucleotide microarray","volume":"64","author":"Brennan","year":"2004","journal-title":"Cancer Res."},{"key":"2023041107132958200_","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1137\/0207013","article-title":"Selecting the kth element in x + y and x1 + x2+ \u2026 + xm","volume":"7","author":"Johnson","year":"1978","journal-title":"SIAM J. Comput."},{"key":"2023041107132958200_","first-page":"41","article-title":"Comparative genomic hybridization: a rapid new method for detecting and mapping DNA amplification in tumors","volume":"4","author":"Kallioniemi","year":"1993","journal-title":"Semin Cancer Biol."},{"key":"2023041107132958200_","doi-asserted-by":"crossref","first-page":"996","DOI":"10.1101\/gr.229102","article-title":"The human genome browser at UCSC","volume":"12","author":"Kent","year":"2002","journal-title":"Genome Res."},{"key":"2023041107132958200_","doi-asserted-by":"crossref","first-page":"1067","DOI":"10.1093\/bioinformatics\/17.11.1067","article-title":"Selection of optimal DNA oligos for gene expression arrays","volume":"17","author":"Li","year":"2002","journal-title":"Bioinformatics"},{"key":"2023041107132958200_","first-page":"491","article-title":"Designing specific oligonucleotide probes for the entire S. cerevisiae transcriptome. In Second Workshop on Algorithms in Bioinformatics (WABI 02)","volume":"2452","author":"Lipson","year":"2002","journal-title":"LNCS"},{"key":"2023041107132958200_","doi-asserted-by":"crossref","first-page":"2291","DOI":"10.1101\/gr.1349003","article-title":"Representational oligonucleotide microarray analysis: s high-resolution method to detect genome copy number variation","volume":"13","author":"Lucito","year":"2003","journal-title":"Genome Res."},{"key":"2023041107132958200_","doi-asserted-by":"crossref","first-page":"11237","DOI":"10.1073\/pnas.1534744100","article-title":"Probe selection for high-density oligonucleotide arrays","volume":"100","author":"Mei","year":"2002","journal-title":"PNAS"},{"key":"2023041107132958200_","first-page":"2765","article-title":"Chromosomal imbalance maps of malignant solid tumors: a cytogenetic survey of 3185 neoplasms","volume":"57","author":"Mertens","year":"2002","journal-title":"Cancer Res."},{"key":"2023041107132958200_","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1038\/2524","article-title":"High resolution analysis of DNA copy number variation using comparative genomic hybridization to microarrays","volume":"20","author":"Pinkel","year":"1998","journal-title":"Nat. Genet."},{"key":"2023041107132958200_","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1038\/12640","article-title":"Genome-wide analysis of DNA copy-number changes using cDNA microarrays","volume":"23","author":"Pollack","year":"1999","journal-title":"Nat. Genet."},{"key":"2023041107132958200_","doi-asserted-by":"crossref","first-page":"3057","DOI":"10.1093\/nar\/gkg426","article-title":"Oligoarray 2.0: design of oligonucleotide probes for DNA microarrays using a thermodynamic approach","volume":"31","author":"Rouillard","year":"2003","journal-title":"Nucleic Acids Res."},{"key":"2023041107132958200_","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1016\/0020-0190(89)90166-X","article-title":"l-infinity interdistance selection by parametric search","volume":"30","author":"Salowe","year":"1989","journal-title":"Inform. Process. Lett."}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/23\/2\/e77\/49820205\/bioinformatics_23_2_e77.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/23\/2\/e77\/49820205\/bioinformatics_23_2_e77.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,10]],"date-time":"2023-05-10T13:03:55Z","timestamp":1683723835000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/23\/2\/e77\/203472"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,1,15]]},"references-count":17,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2007,1,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btl316","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2007,1,15]]},"published":{"date-parts":[[2007,1,15]]}}}