Assigning probes into a small number of pools separable by electrophoresis

Abstract

We show how to computationally find the probes and assign them into pools for a whole genome such that (i) each gene has a specific probe suitable for amplification and hybridization, and (ii) the expression level measurement can be done in a minimal number of pools separable by electrophoresis in order to minimize the total experiment cost of the measurement. Our main result is a polynomial-time approximation algorithm for assigning the probes into pools. We demonstrate the feasibility of the procedure by selecting probes for the yeast genome and assigning them into less than 100 pools. The probe sequences and their assignment into pools are available for academic research on request from the authors.