Optimization of probe coverage for high-resolution oligonucleotide aCGH.
BACKGROUND
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.


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 in-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.


BACKGROUND
Address requests to the authors.
Lipson
Doron
D
Computer Science Department Technion, Israel. dlipson@cs.technion.ac.il
Yakhini
Zohar
Z
Aumann
Yonatan
Y
D001483:Base Sequence; D002874:Chromosome Mapping / Q000379:methods*; D015342:DNA Probes / Q000235:genetics*; D018628:Gene Dosage / Q000235:genetics*; D017404:In Situ Hybridization, Fluorescence / Q000379:methods*; D008969:Molecular Sequence Data; D020411:Oligonucleotide Array Sequence Analysis / Q000379:methods*; D015203:Reproducibility of Results; D012680:Sensitivity and Specificity; D016415:Sequence Alignment / Q000379:methods*; D017422:Sequence Analysis, DNA / Q000379:methods*
D015342:DNA Probes