Universal DNA tag systems: A combinatorial design scheme

Custom-designed DNA arrays offer the possibility of simultaneously monitori ng thousands of hybridization reactions, These arrays show great potential for many medical and scientific applications, such as polymorphism analysis and genotyping. Relatively high costs are associated with the need to spec ifically design and synthesize problem-specific arrays, Recently, an altern ative approach was suggested that utilizes fixed, universal arrays, This ap proach presents an interesting design problem-the arrays should contain as many probes as possible, while minimizing experimental errors caused by cro ss-hybridization. We use a simple thermodynamic model to cast this design p roblem in a formal mathematical framework, Employing new combinatorial idea s, we derive an efficient construction for the design problem and prove tha t our construction is near-optimal.