Selection of Multiple SNPs in Case-Control Association Study Using a Discretized Network Flow Approach

Recent large scale genome-wide association studies have been considered to hold promise for unraveling the genetic etiology of complex diseases. It becomes possible now to use these data to assess the influence of interactions from multiple SNPs on a disease. In this paper we formulate the multiple SNP selection problem for determining genetic risk profiles of certain diseases by formulating novel 0/1 IP formulations for this problem, and solving them using a new near-optimal and efficient discrete optimization technique called discretized network flow that has recently been developed by us. One of the highlights of our approach to solving the multiple SNP selection problem is recognizing that there could be different genetic profiles of a disease among the patient population, and it is thus desirable to classify/cluster patients with similar genetic profiles of the disease while simultaneously selecting the right genetic marker sets of the disease for each cluster. This approach coupled with the DNF technique has yielded results for several diseases with some of the highest sensitivities seen so far and specificities that are higher or comparable to state-of-the art techniques, at a fraction of the runtime of these techniques.