BACKGROUND
single nucleotide polymorphisms  are single nucleotide variations of dna base pairs.
researchers often use snps as genetic markers in disease studies.
it has been well established in the field that snp profiles characterize a variety of diseases.
by investigating snp profiles associated with a disease trait, researchers would be able to reveal relevant genes.
however, in many complex diseases, snps have shown little penetrance individually; on the other hand, their interactions are suspected to possess stronger associations with complex diseases.
some snps, which have no direct impact on health, may be linked to nearby genes which do have effects.
researchers hypothesize that many common diseases in humans are not caused by one genetic variation within a single gene, but are determined by complex interactions among multiple genes.
since the sheer volume of data generated by snp studies is difficult to be manually analyzed, an efficient computational model is required to detect or indicate which pattern is most likely associated with the disease.
then, it will just be a matter of time before physicians can screen individuals for susceptibility to a disease by analyzing their dna samples for specific snp patterns, and further design some experiments to target the genes that implicate the disease.
recently, many methods have been proposed to identify snp interaction patterns associated with diseases.
to name a few studies, beam  <cit>  designed a bayesian marker partition model and used mcmc sampling strategy to estimate the model parameters; mdr  <cit>  applied an exhaustive search model to evaluate all possible multi-snp interactions under some given thresholds; the penalized regression  <cit>  used a variant of logistic regression model with quadratic penalization; cpm  <cit>  used a combinatorial partitioning method for finding the interacted snps; rpm  <cit>  extended cpm by using some heuristics to reduce the search space; monte carlo logic regression  <cit>  combined the logic regression and mcmc in searching the snp interactions; bgta  <cit>  proposed a screening algorithm to repeatedly evaluate a large number of randomly generated marker subsets.
hapforest  <cit>  used a forest-based approach to identifying haplotype-haplotype interactions.
although these methods perform well on small data sets, most of them  are unable to efficiently detect the multi-snp interactions in genome wide association study.
beam has successfully demonstrated its capability of handling large data sets using synthetic data.
when the authors applied beam to an amd  study  <cit> , however, beam did not report any interactions.
one possible reason is that the number of samples is not sufficient to detect the statistically significant interactions.
another possible reason is that beam treats local snp interactions  equally with global gene interactions during mcmc sampling, which could miss some critical haplotype effects in a genome wide association study because haplotype effects generally appear more frequently than global gene interactions.
given a genome wide association study with thousands of snps and a limited number of samples, it is difficult to detect and evaluate the multi-snp interactions in a traditional statistic manner.
the feasible solution is to first find a small set of relatively more relevant snps and then evaluate the interactions within it.
this procedure was applied in hapforest  <cit>  to infer the haplotype-haplotype interaction.
however, the typical feature selection models, which use univariate ranking on feature importance and arbitrary threshold to select relevant features, cannot be applied because they will filter out those snps that have weak marginal effects, while their joint behavior may significantly contribute to disease traits.
in this paper, we introduce an alternative learning approach  to hierarchically rank the multi-snp interactions from local genomic regions to global genome.
megasnphunter takes case-control genotype data as input and produces a ranked list of multi-snp interactions.
in particular, the whole genome is first partitioned into multiple short subgenomes and each subgenome covers the genomic area of possible haplotype effects in practical.
for each subgenome, megasnphunter builds a boosting tree classifier based on multi-snp interactions and measures the importance of snps one the basis of their contributions in the classifier.
the method keeps relatively more important snps from all subgenomes and let them compete with each other in the same way at the next level.
the competition terminates when the number of selected snps is less than the size of a subgenome.
at the last step, megasnphunter extracts and reports the valuable multi-snp interactions.
RESULTS
the performance of megasnphunter is evaluated through comparative studies with existing work.
the goal of megasnphunter is to discover the multi-snp interactions from genome wide studies.
among many recently proposed methods, beam is the best one which could handle the large scale data set and finish in a reasonable time.
therefore, we mainly compare our method with beam in this paper using synthetic data generated on the basis of epistasis models and the data sets from two real studies on complex diseases.
in the experiments on two real studies, one uses a genome wide study on parkinson disease .
the other experiment chooses the rheumatoid arthritis study  <cit>  from wellcome trust case control consortium  using affymetrix genechip 500k mapping array set.
in our experiments, a snp marker can take one of the following four states:  <dig> ,  <dig> ,  <dig> , and  <dig> .
the class label is either  <dig>  or  <dig> .
experiment on simulation study
simulation studies are developed to validate the performance of our approach in correctly determining the associated snps defined by an epistatic model.
to make the fair comparison, we use the simulation program provided in beam package and follow the same procedure in  <cit>  to generate the data based on two epistatic models .
for each model, we choose  <dig> settings  and for each setting, we generate  <dig> data sets, and each data set includes  <dig> snps and contains  <dig> samples .
the performances of both megasnphunter and beam are illustrated in figure  <dig>  in most settings, megasnphunter performs the same or slightly better than beam.
ideally, the results on the genome wide simulation would be more convincing but such a simulation is computationally expensive.
in general, the goal of simulation study is to provide the evidence for validity of our approach.
in practice, the real data is very complex and the snp interactions in the real data may not match any epistatic model.
therefore, our approach does not assume any epistatic model.
we believe the most effective criterion for judging the epistatic interaction is that the joint effect is much more significant than the marginal effects of individual snps.
the next two experiments would show the effectiveness of our approach on the real data.
experiment on parkinson study
parkinson disease is a chronic neurodegenerative disease with a cumulative prevalence of greater than  <dig>  percent.
the primary symptoms of parkinson's disease include tremors, rigidity, slow movement, poor balance, and difficulty walking.
in this experiment, we choose the study in  <cit>  which provides around  <dig>  genotypes in  <dig> samples.
both beam and megasnphunter are tested on this data set.
beam could not identify any interaction while our megasnphunter selected  <dig> significant snp interactions.
megasnphunter is first run on each chromosome with  <dig> fold cross validation.
cross validation is a model evaluation method that estimates how well the model built from some training data is going to perform on unseen data.
the  <dig> fold cross validation is conducted every time when the boosting tree classifier is built in the whole hierarchical procedure.
in our test, the samples are randomly sampled into  <dig> subsets and each validation uses  <dig> subsets to train the model and the left one to test the performance.
the output from every validation is a classifier and a list of ranked snps.
after  <dig> validations are finished, a post process is invoked to isolate those snps whose genotype association χ <dig> p values reach a critical value , and those snps whose interaction's genotype association χ <dig> p values are above a critical value .
the top ranked snps among the selected  <dig> snps are reported in table  <dig> with genotype association χ <dig> p values.
the selected interactions with genotype association χ2p values are reported in table  <dig>  to handle the multiple test issue, we conduct an extra permutation-based test  on both single snp and snp interactions to correct p values.
this table reports the top ranked snps and their genotype association χ <dig> p values.
this table reports the selected interactions and their genotype association χ <dig> p values.
we observe that among  <dig> snps involved in the selected interactions in table  <dig>  only three of them  have noticeable marginal effects in table  <dig>  for the other  <dig> snps, their joint effects are much more significant than the corresponding individual snp effects.
figure  <dig> shows the genotype distribution of two snps  and the genotype distribution under the interaction.
figure  <dig> displays the same information for the interaction between rs <dig> and rs <dig>  these figures clearly illustrate how the two weak snps significantly affect disease traits .
experiment on rheumatoid arthritis study
the wellcome trust case control consortium  is a collaboration of many british research groups.
to date, the wtccc has examined the genetic signals of seven common human diseases: rheumatoid arthritis, hypertension, crohn's disease, coronary artery disease, bipolar disorder, and type  <dig> and type  <dig> diabetes.
the rheumatoid arthritis study  <cit>  contains around  <dig> k genotypes in  <dig> samples .
we use the same procedure mentioned above to conduct the experiment.
the top ranked snps among the selected  <dig> snps are reported in table  <dig> with genotype association χ <dig> p values.
the selected interactions with genotype association χ <dig> p values are reported in table  <dig>  the top interaction identified in megasnphunter is between rs <dig> and rs <dig>  its genotype association χ <dig> p value is  <dig>  * 10- <dig>  the genotype distribution of cases and controls for these two snps and the distribution under their interaction are plotted in figure  <dig>
this table reports the top ranked snps and their genotype association χ <dig> p values.
this table reports the selected interactions and their genotype association χ <dig> p values.
both rs <dig> and rs <dig> are located on the gene gpc <dig>  which is a member of the glypican gene family and encodes a product structurally related to gpc <dig>  <cit> .
in a latest study of rheumatoid arthritis  <cit> , gpc <dig> displays strong expression.
the connection between our finding and previous work may imply a complex rheumatoid arthritis associated pattern.
more evidences from biological aspect are under investigation.
again, beam could not report any significant interaction.
the reason that beam could not report any interaction is partly because the data from the real studies are too complex to be formulated by one bayesian marker partition model and the distribution assumptions in beam may not be true for the real data.
the results from both experiments on real data sets empirically justify that our method performs better than beam with respect to finding snp interactions in genome wide association studies.
running time comparison
another attracting point of our megasnphunter is that it runs faster than beam.
suppose the number of snps in each subgenome is w, the number of snps is m, and the number of samples is n. then the number of subgenomes is mw +  <dig>  the time for training one boosting tree classifier using one subgenome is o).
then the time for learning at the first level is o).
the expected number of snps at the second level is m <dig>  and m2d− <dig> at the dth level.
then the time for the learning at the dth level is o).
the total running time is o · n · log) that is equivalent to o).
it approximates to  <dig>  *  <dig> for the rheumatoid arthritis study, which is much less than the complexity o  of beam, where i is the number of iterations in mcmc sampling and is set to 108as default value for a data set with medium size .
theoretically, i is determined by o with d denoting the number of interacting snps .
discrimination ability on real data sets
as for the discrimination power of megasnphunter, table  <dig> and table  <dig> report the prediction accuracies for both experiments on real data sets.
they also report the prediction accuracies for each chromosome based on selected snps and the prediction accuracies from randomized tests for comparison.
the randomized tests randomly select the same number of snps as our method has selected for each chromosome and the whole genome, and collect the prediction accuracies using 10-fold cv.
the reported accuracies for randomized tests are the averages of  <dig> runs.
in both tables, we observe that the randomly selected snps from both real data sets can only achieve around 50% prediction accuracy on average.
we realize that there are many false positives in selected snps because megasnphunter can achieve good performance on every chromosome.
how to reduce the false positive error is a challenging problem in genome wide association studies.
although our method does not directly address this issue, nevertheless our method is able to reduce the number of possibly disease-associated snps and rank those snps based on their relevances to the disease trait.
extra filters can be applied to remove false positives.
the classification performance of megasnphunter on parkinson study.
the classification performance of megasnphunter on wtccc study.
the parameter setting of megasnphunter
there are four main parameters in the models, including the depth of trees, the threshold for selecting snps from trees, the subgenome size and the overlap between subgenome.
<dig>  the depth of trees indicates the depth of snp interaction.
since most significant interactions are depth  <dig>  so as long as the depth of trees is above  <dig>  the results would not be changed.
megasnphunter uses  <dig> as default setting.
<dig>  the size of subgenome depends on the density of snp data.
each subgenome should cover the genomic area of possible haplotype effects in practical.
before we start the experiment, we collect some statistics on how many snps are genotyped for one gene.
this number will be used as the size of subgenome.
<dig>  the overlap between subgenomes is used to solve the boundary problem between genes.
half of the size of subgenome is the best choice.
both the size of subgenome and the overlap between subgenomes depend on the priori knowledge on epistatic interactions.
<dig>  the threshold for selecting snps from trees is a very critical parameter to the method.
our goal is to find interactions among snps with weak marginal effects.
if the threshold is too stringent, then too many snps will be filtered out, while the loose threshold will allow too many snps to be selected.
in our method, two strategies are applied to deal with this issue.
• the first strategy is to select all snps involved in the classifier.
this is usually used in the situation where most snps are clearly irrelevant with diseases.
however, in the worst case, the classifier may use all snps in training.
if too many snps are selected in the classifier, the second strategy will be applied.
• the second strategy uses a threshold to select relevant snps.
this threshold is the critical value of χ <dig> statistic.
the default setting for single snp is  <dig> ,  <dig> * <dig>  for a pair of interacted snps, and so on so forth.
discussion
the advantages of megasnphunter
the development of megasnphunter was triggered by the limitations of existing works on finding high order snp interactions from genome wide studies.
given a genome wide study containing thousands of markers, most existing methods either fail to report the statistically significant interactions due to the limited samples, or can not terminate in a reasonable time due to the explosive search space.
megasnphunter addresses these issues by hierarchically reducing the number of relevant snps and then extracting the interactions.
megasnphunter displays many advantages over the existing methods:
• the hierarchical learning strategy can extract both local snp interactions and global gene interactions in an efficient manner without exhaustive enumeration;
• megasnphunter uses a classifier built on snp interactions to rank the relevances of snps, which is superior to the univariate feature selection techniques on finding the snps with weak marginal effects but significant joint effects;
• megasnphunter is a non parametric method.
it does not assume any prior distributions as required by many parametric-statistical methods;
• megasnphunter does not assume any particular epistasis models, which is very important for real studies because the models of snp interactions are unknown and likely to be very complex.
our method only assumes that the further the distance between two snps, the less possibility they interact with each other.
• megasnphunter could be applied for discrimination, where we can use the selected snps to build a classifier for discriminating two or more classes of samples.
the limitations of megasnphunter
the big advantage of megasnphunter is to find the interactions between snps with weak marginal effects.
to handle the high dimension of genome wide data, megasnphunter partitions the whole genome into multiple short subgenomes and select the relative more important snps from each subgenome.
if the interacted snps are not located in the same subgenome, megasnphunter requires that their marginal effects must be above the medium of marginal effects of their resided subgenomes.
we think this is a soft constraint because in reality, most snps in the genome do not contribute to any trait variation.
if either of interacted snps only has trivial marginal effect, it would have little chance to survive and meet its counterpart in the next level.
in the real application, megasnphunter could incorporate some search strategies proposed in  <cit>  as a preprocess to reduce the search space.
these search strategies first find disease-associated snps with noticeable marginal evidence.
then an exhaustive search procedure can be applied to find interactions among them.
these strategies complements our method.
we could start from using them to find interactions between snps with strong marginal effects and next run megasnphunter to find interactions between snps with weak marginal effects.
future studies
there are several issues we need to address in the future work.
since our method assumes that the strength of interaction is inversely proportional to the distance of snps, most findings in our results are local effects.
the interactions between snps far in distance have already drawn many researchers' attention.
we plan to develop new methods to find the global snp interactions.
an efficient sampling strategy is one possible solution.
another critical issue is how to reduce false positives.
we plan to incorporate the haplotype information and pathway information to help reduce the false positive error in future study.
CONCLUSIONS
in this paper, we propose a novel hierarchical learning algorithm  to find high order snp interactions in genome wide association studies.
we evaluate megasnphunter through comparative studies on simulated data and the data sets from two real studies including a genome wide study on parkinson disease  <cit>  and the rheumatoid arthritis study from wtccc  <cit> .
in the simulation experiment, megasnphunter displays the comparable performance while in the experiments on two real studies, beam could not report any interaction patterns but our megasnphunter identifies many interactions among snps whose joint effects are more significant than the individual snp effects.
in summary, the hierarchical nature of our non-parametric learning scheme enables our new method to search for interaction patterns more efficiently than existing methods.
in this sense, our method is a powerful tool for whole genome data analysis.

 single nucleotide polymorphisms are single nucleotide variations of dna base pairs. researchers often use snps as genetic markers in disease studies. it has been well established in the field that snp profiles characterize a variety of diseases. by investigating snp profiles associated with a disease trait, researchers would be able to reveal relevant genes. however, in many complex diseases, snps have shown little penetrance individually; on the other hand, their interactions are suspected to possess stronger associations with complex diseases. some snps, which have no direct impact on health, may be linked to nearby genes which do have effects. researchers hypothesize that many common diseases in humans are not caused by one genetic variation within a single gene, but are determined by complex interactions among multiple genes. since the sheer volume of data generated by snp studies is difficult to be manually analyzed, an efficient computational model is required to detect or indicate which pattern is most likely associated with the disease. then, it will just be a matter of time before physicians can screen individuals for susceptibility to a disease by analyzing their dna samples for specific snp patterns, and further design some experiments to target the genes that implicate the disease. recently, many methods have been proposed to identify snp interaction patterns associated with diseases. to name a few studies, beam designed a bayesian marker partition model and used mcmc sampling strategy to estimate the model parameters; mdr applied an exhaustive search model to evaluate all possible multi-snp interactions under some given thresholds; the penalized regression used a variant of logistic regression model with quadratic penalization; cpm used a combinatorial partitioning method for finding the interacted snps; rpm extended cpm by using some heuristics to reduce the search space; monte carlo logic regression combined the logic regression and mcmc in searching the snp interactions; bgta proposed a screening algorithm to repeatedly evaluate a large number of randomly generated marker subsets. hapforest used a forest-based approach to identifying haplotype-haplotype interactions. although these methods perform well on small data sets, most of them are unable to efficiently detect the multi-snp interactions in genome wide association study. beam has successfully demonstrated its capability of handling large data sets using synthetic data. when the authors applied beam to an amd study, however, beam did not report any interactions. one possible reason is that the number of samples is not sufficient to detect the statistically significant interactions. another possible reason is that beam treats local snp interactions equally with global gene interactions during mcmc sampling, which could miss some critical haplotype effects in a genome wide association study because haplotype effects generally appear more frequently than global gene interactions. given a genome wide association study with thousands of snps and a limited number of samples, it is difficult to detect and evaluate the multi-snp interactions in a traditional statistic manner. the feasible solution is to first find a small set of relatively more relevant snps and then evaluate the interactions within it. this procedure was applied in hapforest to infer the haplotype-haplotype interaction. however, the typical feature selection models, which use univariate ranking on feature importance and arbitrary threshold to select relevant features, cannot be applied because they will filter out those snps that have weak marginal effects, while their joint behavior may significantly contribute to disease traits. in this paper, we introduce an alternative learning approach to hierarchically rank the multi-snp interactions from local genomic regions to global genome. megasnphunter takes case-control genotype data as input and produces a ranked list of multi-snp interactions. in particular, the whole genome is first partitioned into multiple short subgenomes and each subgenome covers the genomic area of possible haplotype effects in practical. for each subgenome, megasnphunter builds a boosting tree classifier based on multi-snp interactions and measures the importance of snps one the basis of their contributions in the classifier. the method keeps relatively more important snps from all subgenomes and let them compete with each other in the same way at the next level. the competition terminates when the number of selected snps is less than the size of a subgenome. at the last step, megasnphunter extracts and reports the valuable multi-snp interactions.  the performance of megasnphunter is evaluated through comparative studies with existing work. the goal of megasnphunter is to discover the multi-snp interactions from genome wide studies. among many recently proposed methods, beam is the best one which could handle the large scale data set and finish in a reasonable time. therefore, we mainly compare our method with beam in this paper using synthetic data generated on the basis of epistasis models and the data sets from two real studies on complex diseases. in the experiments on two real studies, one uses a genome wide study on parkinson disease. the other experiment chooses the rheumatoid arthritis study from wellcome trust case control consortium using affymetrix genechip 500k mapping array set. in our experiments, a snp marker can take one of the following four states:,,, and. the class label is either or. experiment on simulation study simulation studies are developed to validate the performance of our approach in correctly determining the associated snps defined by an epistatic model. to make the fair comparison, we use the simulation program provided in beam package and follow the same procedure in to generate the data based on two epistatic models. for each model, we choose settings and for each setting, we generate data sets, and each data set includes snps and contains samples. the performances of both megasnphunter and beam are illustrated in figure in most settings, megasnphunter performs the same or slightly better than beam. ideally, the results on the genome wide simulation would be more convincing but such a simulation is computationally expensive. in general, the goal of simulation study is to provide the evidence for validity of our approach. in practice, the real data is very complex and the snp interactions in the real data may not match any epistatic model. therefore, our approach does not assume any epistatic model. we believe the most effective criterion for judging the epistatic interaction is that the joint effect is much more significant than the marginal effects of individual snps. the next two experiments would show the effectiveness of our approach on the real data. experiment on parkinson study parkinson disease is a chronic neurodegenerative disease with a cumulative prevalence of greater than percent. the primary symptoms of parkinson's disease include tremors, rigidity, slow movement, poor balance, and difficulty walking. in this experiment, we choose the study in which provides around genotypes in samples. both beam and megasnphunter are tested on this data set. beam could not identify any interaction while our megasnphunter selected significant snp interactions. megasnphunter is first run on each chromosome with fold cross validation. cross validation is a model evaluation method that estimates how well the model built from some training data is going to perform on unseen data. the fold cross validation is conducted every time when the boosting tree classifier is built in the whole hierarchical procedure. in our test, the samples are randomly sampled into subsets and each validation uses subsets to train the model and the left one to test the performance. the output from every validation is a classifier and a list of ranked snps. after validations are finished, a post process is invoked to isolate those snps whose genotype association χ p values reach a critical value, and those snps whose interaction's genotype association χ p values are above a critical value. the top ranked snps among the selected snps are reported in table with genotype association χ p values. the selected interactions with genotype association χ2p values are reported in table to handle the multiple test issue, we conduct an extra permutation-based test on both single snp and snp interactions to correct p values. this table reports the top ranked snps and their genotype association χ p values. this table reports the selected interactions and their genotype association χ p values. we observe that among snps involved in the selected interactions in table only three of them have noticeable marginal effects in table for the other snps, their joint effects are much more significant than the corresponding individual snp effects. figure shows the genotype distribution of two snps and the genotype distribution under the interaction. figure displays the same information for the interaction between rs and rs these figures clearly illustrate how the two weak snps significantly affect disease traits. experiment on rheumatoid arthritis study the wellcome trust case control consortium is a collaboration of many british research groups. to date, the wtccc has examined the genetic signals of seven common human diseases: rheumatoid arthritis, hypertension, crohn's disease, coronary artery disease, bipolar disorder, and type and type diabetes. the rheumatoid arthritis study contains around k genotypes in samples. we use the same procedure mentioned above to conduct the experiment. the top ranked snps among the selected snps are reported in table with genotype association χ p values. the selected interactions with genotype association χ p values are reported in table the top interaction identified in megasnphunter is between rs and rs its genotype association χ p value is * 10- the genotype distribution of cases and controls for these two snps and the distribution under their interaction are plotted in figure this table reports the top ranked snps and their genotype association χ p values. this table reports the selected interactions and their genotype association χ p values. both rs and rs are located on the gene gpc which is a member of the glypican gene family and encodes a product structurally related to gpc. in a latest study of rheumatoid arthritis, gpc displays strong expression. the connection between our finding and previous work may imply a complex rheumatoid arthritis associated pattern. more evidences from biological aspect are under investigation. again, beam could not report any significant interaction. the reason that beam could not report any interaction is partly because the data from the real studies are too complex to be formulated by one bayesian marker partition model and the distribution assumptions in beam may not be true for the real data. the results from both experiments on real data sets empirically justify that our method performs better than beam with respect to finding snp interactions in genome wide association studies. running time comparison another attracting point of our megasnphunter is that it runs faster than beam. suppose the number of snps in each subgenome is w, the number of snps is m, and the number of samples is n. then the number of subgenomes is mw + the time for training one boosting tree classifier using one subgenome is o). then the time for learning at the first level is o). the expected number of snps at the second level is m and m2d− at the dth level. then the time for the learning at the dth level is o). the total running time is o · n · log) that is equivalent to o). it approximates to * for the rheumatoid arthritis study, which is much less than the complexity o of beam, where i is the number of iterations in mcmc sampling and is set to 108as default value for a data set with medium size. theoretically, i is determined by o with d denoting the number of interacting snps. discrimination ability on real data sets as for the discrimination power of megasnphunter, table and table report the prediction accuracies for both experiments on real data sets. they also report the prediction accuracies for each chromosome based on selected snps and the prediction accuracies from randomized tests for comparison. the randomized tests randomly select the same number of snps as our method has selected for each chromosome and the whole genome, and collect the prediction accuracies using 10-fold cv. the reported accuracies for randomized tests are the averages of runs. in both tables, we observe that the randomly selected snps from both real data sets can only achieve around 50% prediction accuracy on average. we realize that there are many false positives in selected snps because megasnphunter can achieve good performance on every chromosome. how to reduce the false positive error is a challenging problem in genome wide association studies. although our method does not directly address this issue, nevertheless our method is able to reduce the number of possibly disease-associated snps and rank those snps based on their relevances to the disease trait. extra filters can be applied to remove false positives. the classification performance of megasnphunter on parkinson study. the classification performance of megasnphunter on wtccc study. the parameter setting of megasnphunter there are four main parameters in the models, including the depth of trees, the threshold for selecting snps from trees, the subgenome size and the overlap between subgenome. the depth of trees indicates the depth of snp interaction. since most significant interactions are depth so as long as the depth of trees is above the results would not be changed. megasnphunter uses as default setting. the size of subgenome depends on the density of snp data. each subgenome should cover the genomic area of possible haplotype effects in practical. before we start the experiment, we collect some statistics on how many snps are genotyped for one gene. this number will be used as the size of subgenome. the overlap between subgenomes is used to solve the boundary problem between genes. half of the size of subgenome is the best choice. both the size of subgenome and the overlap between subgenomes depend on the priori knowledge on epistatic interactions. the threshold for selecting snps from trees is a very critical parameter to the method. our goal is to find interactions among snps with weak marginal effects. if the threshold is too stringent, then too many snps will be filtered out, while the loose threshold will allow too many snps to be selected. in our method, two strategies are applied to deal with this issue. • the first strategy is to select all snps involved in the classifier. this is usually used in the situation where most snps are clearly irrelevant with diseases. however, in the worst case, the classifier may use all snps in training. if too many snps are selected in the classifier, the second strategy will be applied. • the second strategy uses a threshold to select relevant snps. this threshold is the critical value of χ statistic. the default setting for single snp is, * for a pair of interacted snps, and so on so forth. discussion the advantages of megasnphunter the development of megasnphunter was triggered by the limitations of existing works on finding high order snp interactions from genome wide studies. given a genome wide study containing thousands of markers, most existing methods either fail to report the statistically significant interactions due to the limited samples, or can not terminate in a reasonable time due to the explosive search space. megasnphunter addresses these issues by hierarchically reducing the number of relevant snps and then extracting the interactions. megasnphunter displays many advantages over the existing methods: • the hierarchical learning strategy can extract both local snp interactions and global gene interactions in an efficient manner without exhaustive enumeration; • megasnphunter uses a classifier built on snp interactions to rank the relevances of snps, which is superior to the univariate feature selection techniques on finding the snps with weak marginal effects but significant joint effects; • megasnphunter is a non parametric method. it does not assume any prior distributions as required by many parametric-statistical methods; • megasnphunter does not assume any particular epistasis models, which is very important for real studies because the models of snp interactions are unknown and likely to be very complex. our method only assumes that the further the distance between two snps, the less possibility they interact with each other. • megasnphunter could be applied for discrimination, where we can use the selected snps to build a classifier for discriminating two or more classes of samples. the limitations of megasnphunter the big advantage of megasnphunter is to find the interactions between snps with weak marginal effects. to handle the high dimension of genome wide data, megasnphunter partitions the whole genome into multiple short subgenomes and select the relative more important snps from each subgenome. if the interacted snps are not located in the same subgenome, megasnphunter requires that their marginal effects must be above the medium of marginal effects of their resided subgenomes. we think this is a soft constraint because in reality, most snps in the genome do not contribute to any trait variation. if either of interacted snps only has trivial marginal effect, it would have little chance to survive and meet its counterpart in the next level. in the real application, megasnphunter could incorporate some search strategies proposed in as a preprocess to reduce the search space. these search strategies first find disease-associated snps with noticeable marginal evidence. then an exhaustive search procedure can be applied to find interactions among them. these strategies complements our method. we could start from using them to find interactions between snps with strong marginal effects and next run megasnphunter to find interactions between snps with weak marginal effects. future studies there are several issues we need to address in the future work. since our method assumes that the strength of interaction is inversely proportional to the distance of snps, most findings in our results are local effects. the interactions between snps far in distance have already drawn many researchers' attention. we plan to develop new methods to find the global snp interactions. an efficient sampling strategy is one possible solution. another critical issue is how to reduce false positives. we plan to incorporate the haplotype information and pathway information to help reduce the false positive error in future study.  in this paper, we propose a novel hierarchical learning algorithm to find high order snp interactions in genome wide association studies. we evaluate megasnphunter through comparative studies on simulated data and the data sets from two real studies including a genome wide study on parkinson disease and the rheumatoid arthritis study from wtccc. in the simulation experiment, megasnphunter displays the comparable performance while in the experiments on two real studies, beam could not report any interaction patterns but our megasnphunter identifies many interactions among snps whose joint effects are more significant than the individual snp effects. in summary, the hierarchical nature of our non-parametric learning scheme enables our new method to search for interaction patterns more efficiently than existing methods. in this sense, our method is a powerful tool for whole genome data analysis. 
although many works have been done to identify and quantify the importance of multi-snp interactions, few of them could handle the genome wide data due to the combinatorial explosive search space and the difficulty to statistically evaluate the high-order interactions given limited samples. to our knowledge, megasnphunter is the first approach that is capable of identifying the disease-associated snp interactions from wtccc studies and is promising for practical disease prognosis. the first experiment uses synthetic data generated on the basis of epistasis models. the experimental results on both synthetic data and two real data sets demonstrate that our proposed approach outperforms the best solution that is currently available in handling large-scale snp data both in terms of speed and in terms of detection of potential interactions that were not identified before. the second one uses a genome wide study on parkinson disease. the interactions of multiple single nucleotide polymorphisms are highly hypothesized to affect an individual's susceptibility to complex diseases. megasnphunter outperforms the best solution in this area and reports many potential interactions for the two real studies. the third one chooses the rheumatoid arthritis study from wellcome trust case control consortium using affymetrix genechip 500k mapping array set.
 the interactions of multiple single nucleotide polymorphisms are highly hypothesized to affect an individual's susceptibility to complex diseases. although many works have been done to identify and quantify the importance of multi-snp interactions, few of them could handle the genome wide data due to the combinatorial explosive search space and the difficulty to statistically evaluate the high-order interactions given limited samples.  three comparative experiments are designed to evaluate the performance of megasnphunter. the first experiment uses synthetic data generated on the basis of epistasis models. the second one uses a genome wide study on parkinson disease. the third one chooses the rheumatoid arthritis study from wellcome trust case control consortium using affymetrix genechip 500k mapping array set. megasnphunter outperforms the best solution in this area and reports many potential interactions for the two real studies.  the experimental results on both synthetic data and two real data sets demonstrate that our proposed approach outperforms the best solution that is currently available in handling large-scale snp data both in terms of speed and in terms of detection of potential interactions that were not identified before. to our knowledge, megasnphunter is the first approach that is capable of identifying the disease-associated snp interactions from wtccc studies and is promising for practical disease prognosis. 