Abstract
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 configuration 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. [1]. 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.