Integer Linear Programming in Designing Universal Arrays with Multiplexed Applications

Single nucleotide polymorphisms (SNPs) are variations in a single nucleotide within a generally conserved genomic sequence across the population. SNPs can be genotyped using a universal DNA tag array. But cross-hybridization involving assay-specific components disrupts this process. The problem of identifying the most economic experimental con-figuration of the assay specific components that avoids cross hybridization can be formulated as an optimization problem. More specifically, the problem translates into the problem of covering the vertices of one side of a bipartite graph by a minimum number of balanced subgraphs of maximum degree one. The problem was shown to be NP-complete by Ben-Dor et.al.. In this paper, we give integer linear programming formulation of this problem. We also provide an integer linear programming formulation of a mathematically related problem.