BACKGROUND
the cause and progression of human diseases such as alzheimer's disease, cancer and diabetes are likely influenced by complex interactions of multiple genes as well as environmental and lifestyle factors that are sensitive to genome variability.
single nucleotide polymorphisms  are the most prevalent form of dna variation in the human genome occurring about once per  <dig> to  <dig> bases  <cit> .
the high frequency of relatively stable snps makes them excellent biomarkers for some disease phenotypes.
while some serious diseases such as cystic fibrosis and sickle cell anemia are of predominately genetic etiology in homozygote individuals, other serious diseases are far more complex.
in more complex diseases, a combination of multiple snps , plus environmental factors, may combine to determine disease susceptibility and prognosis.
the terminology of "complex disease" is used because of the potential enormity of interacting genes that could be in the hundreds.
the genetic factors that determine disease phenotypes may be encoded in the pattern of genomic variation that is primarily snps.
cancer, mental illness, some autoimmune disorders and diabetes are among the common serious diseases thought to be significantly influenced by the spectrum of snps an individual has in certain susceptibility genes.
population variability in drug response is thought to be analogously dependent on an individual's snp profile.
therefore, the identification of particular snp patterns that are associated with susceptibility to disease or adverse drug reactions is a paramount goal of pharmacogenomics research.
given recent development of high-throughput technologies for rapid genotyping, assessment of snp patterns holds much promise for use in diagnosis, prognosis and selection of treatment intervention.
an essential bioinformatics challenge in pharmacogenomics is the discovery of snp patterns that differentiate diseased and healthy populations.
determination of the snp patterns associated with disease susceptibility or adverse drug reaction from among potentially millions of snps is a challenge for pharmacogenomics.
many methods have been described in the literature to assess the association between snps and disease  <cit> .
most of them are focused on identification of disease-related genotypes and haplotypes, where allele frequencies in cases and controls are estimated separately and then compared  <cit> .
currently, snps involved in complex diseases are not well enough understood, nor are genotype data sets adequate for development of models to reliably predict disease from snp profiles.
however, the science is sufficiently advanced that studies such as presented herein can be useful to plan experiments, and to interpret data in what may well prove to be an arduous, lengthy and iterative process of identifying snps and snp patterns useful as biomarkers.
esophageal cancer, like many other cancers, has been shown to be associated with genetic as well as environmental factors that cause dna damage.
it is the sixth leading cause of cancer worldwide and seventh among american men.
among the two main types of esophageal cancer, squamous cell carcinoma and adenocarcinoma, squamous cell carcinoma accounts for about half of all esophageal cancers.
data from studies in animals suggest that oxidative damage from factors such as smoking or gastroesophageal reflux, which cause inflammation, esophagitis, and increased cell turnover, may initiate the carcinogenic process  <cit> .
studies also suggest that substantial alcohol intake, tobacco smoking and betel quid chewing increase the risk of squamous cell carcinoma  <cit> .
we investigated the association of snps and squamous cell carcinoma of the esophagus in a case-control study of individuals from shanxi province, a region in north-central china.
shanxi has one of the highest esophageal cancer rates in the world.
the snps chosen for the study were a set of those associated with dna repair, phase i and phase ii enzymes involved in xenobiotic clearance, and with alcohol metabolism.
we developed a novel adaptation of the decision forest pattern recognition method named decision forest for snps .
the method was designated to analyze the snps-disease association based on the snp data.
importantly, the df-snps method utilizes the inherent differentiating ability of decision trees to separate disease and control population based on individual snps, the snp types, as well as combinations of snp types, that is, snp patterns.
methods
study population
incident cases of esophageal cancer were obtained from an ongoing case-control study being conducted by the national cancer institute, usa and the shanxi cancer institute, china.
esophageal cancer patients at the shanxi cancer hospital in taiyuan, shanxi province, were recruited to the case-control study.
esophageal cancer was confirmed by the pathologists at the shanxi cancer hospital and national cancer institute and all cases were esophageal squamous cell carcinoma .
controls matched on age, gender and neighbourhood were selected for each case.
the study was approved by the institutional review boards of the shanxi cancer hospital and the us national cancer institute.
after signed consent was obtained, a blood sample was collected from the participants and information on demographics and cancer risk factors including smoking, alcohol, diet, and family history were collected in an interview.
snp data
dna samples were genotyped at a commercial laboratory  by masscode mass spectrometry genotyping.
pcr primers used for genotyping were synthesized at bioserve.
oligonucleotide sequences of the primers probe can be found at .
all laboratory personnel were blinded to case-control status.
a total of  <dig> snps were chosen from dna repair, phase i, phase ii, and alcohol metabolism related genes.
the average call rate for the study was  <dig> %, and duplicate analysis of three of the snps generated  <dig> %,  <dig> %, and 100% concordance.
the prevalence of the variant allele ranged from  <dig> % to  <dig> %.
decision forest for snps
df-snps is an ensemble classification method that combines multiple decision trees to derive a classifier based on a fitted set of if-then rules.
by combining multiple heterogeneous decision trees, df-snps is effective in mitigating noise that is often prevalent in biological data, especially data from high throughput technologies, compared to single decision trees.
moreover, the algorithm is computationally inexpensive, enabling cross validation and randomization tests to readily be included.
figure  <dig> depicts a general flowchart of df-snps.
the detail information of each step in figure  <dig> is described in the following sections.
the df-snps was developed using c.
data pre-processing
it is common that the snp types for some individuals are inconclusive using most high-throughput genotyping methods, including the masscode mass spectrometry genotyping method.
this results a data set  that usually contains many missing values .
accordingly, a data pre-processing procedure is required to impute the missing data for subsequent analysis.
a two-steps data pre-processing procedure was implemented in df-snps.
first, the samples  with > 15% missing genotypes  across all snp variables  and the snp variables  with > 15% missing genotypes  across all the samples  were removed.
next, a 10-nearest neighbor method was employed to impute the missing data.
in this method, if a sample has a missing value  that is corresponding to a snp variable, we identified  <dig> samples that not only had a measure for this snp but also had the closest snp profiles calculated based on the rest of the snp variables.
the genotypes of these  <dig> samples were used to impute the missing value by voting.
there were  <dig> missing genotypes in the data set .
two snp variables  and eight samples  were removed, which resulting  <dig> % missing value in the data set for imputing.
the final data set for analysis after pre-processing contained  <dig> individuals and  <dig> snps,  <dig> cancer cases and  <dig> controls.
decision tree development
a tree was developed using the s-plus binary split method <cit> , where the snps are the independent variables grouped into three genotype categories: homozygous common, heterozygous and homozygous variant.
the method started from the root node that contained all samples and identified a snp type of all possible snps that divided the samples into two child nodes.
since this is a binary splitting of each tree node, the single snp type that best divides the node populating one branch and the other two genotypes populating the other branch.
the impurity  of a node was measured with deviance.
the process was then recursively repeated on the child nodes and the process was stopped if further splitting did not improve the purity of the child node or the node can not be further split.
figure  <dig> provides a hypothetical example to illustrate the tree development process.
if there is a snp data set with  <dig> cases and  <dig> controls, the process first identifies the best splitter, snp <dig> = heterozygous, to put  <dig> samples in the right node  and  <dig> samples in the left node .
the cases are enriched in the right node  compared to its parent node while the controls are enriched in the left node.
in the end of tree development, the cases and controls are enriched in the different terminal nodes.
multiple tree development and combination
in our previous application, multiple trees in df used distinct independent variables to maximize their difference <cit> ; the variables used in one tree were not used in any other tree.
since only a limited number of snp variables were in this application, we forced trees that selected different snp types in splitting the root node to assure heterogeneity.
that is, a snp type selected for the root splitting in one tree was not allowed for use in splitting root nodes in other trees.
however, this rule was not enforced in the subsequent splitting of the lower nodes.
to ensure the comparability of trees, their qualities were maintained to the same  by adjusting the misclassification rate in the tree development.
finally, the classification of each sample was determined by averaging the outcomes from all trees.
statistical testing
if we generate many classification models using a bootstrapping method, the relevance  of a snp, snp type or snp pattern should be directly correlate to the number of times they are used by the models.
based on this assumption, we performed  <dig> runs of 10-fold cross-validation and calculated the frequencies of each snp, snp type and snp pattern appeared in this process.
to determine the statistical significance of the findings, we also generated a null hypothesis using the same statistical procedure.
this was a randomization test, where the sample classification  was randomly scrambled to generate  <dig> pseudo data sets and the 10-fold cross-validation was then applied to each pseudo data set.
thus, null distributions were generated for each snp, snp type and snp pattern.
we then determined the critical values that corresponded to the 5% level of significance for snps, snp types and snp patterns, respectively.
the statistically significant snps, snp types and snp patterns were these whose frequencies were greater than their corresponding critical values.
RESULTS
the study population comprised  <dig> individuals genotyped for  <dig> snps, of which  <dig> were esophageal cancer patients and  <dig> were age-frequencies matched controls.
after removing individuals for which data was missing for more than 15% of genotypes, and removing snp variables that were missing data for more than 15% of the individuals, the data was reduced to  <dig> individuals  and  <dig> snp variables.
this is a binary classification problem.
the snps are the independent variables grouped into three genotype categories: homozygous common, heterozygous and homozygous variant.
using the df-snps method, we developed a classification model to differentiate the cases from the controls.
the fitted binary decision forest model thus derived contained  <dig> decision trees and exhibited high concordance , sensitivity  and specificity , indicating that the model well differentiates disease from control samples.
figure  <dig> shows that the misclassifications of the model significantly diminish as trees are added to the forest, indicating that the df method may be canceling some random variation or amplifying the nonrandom signal as trees are added.
ultimately, the 10-tree model has misclassifications of  <dig>  much less than the  <dig> misclassification of the single decision tree.
the df-snps algorithm includes functions that estimate on a relative basis the statistical significance of individual snps, snp types and snp patterns in differentiating snp case-control study data.
the rational behind this approach is that the frequency of a particular snp, snp type or snp pattern selected by the model correlates positively with the relevance  to discriminate the cases from controls.
the frequency was obtained from a multiple runs of 10-fold cross-validation procedure.
to determine the statistical significance of the disease-related snps, snp types and snp patterns, a null hypothesis was first generated where the scrambled snp data set was also subjected to the same multiple runs of 10-fold cross-validation .
then, the frequency based on the real data set was compared with the null hypothesis.
the purpose of this statistical test is to determine whether the obtained results  reject the hypothesis that they are merely a product of chance factors.
the results of this investigation are described in the following sections.
identification of individual snps relevant to the esophageal cancer
in this section, we investigated the association of individual snps with the cancer.
the snps were ranked according to frequency of use in tree node splitting in  <dig> runs of 10-fold cross-validation.
the ranking frequency for snp i ) is computed as:
where snpi =  <dig> means that snp i was used as a split rule in tree k at level l .
freq is calculated over all trees in the forest models in  <dig> runs of 10-fold cross-validation.
in this equation, snps at each lower node level are given half the frequency weight as snps at the preceding higher level.
an estimate of the frequency of occurrence required for a snp to be statistically significant at 95% confidence is obtained from the random case.
specifically, for the random case, the cumulative  <dig>  frequency of occurrence for snps rank ordered by frequency occurs for a snp with frequency of  <dig> ; snps having frequency greater than the critical value of  <dig>  are designated as significant to a 95% level of confidence.
in the case-control study, nine out of total of  <dig> snps had freq larger than  <dig> , indicating their relevance to the esophageal cancer with p <  <dig>  .
identification of snp types relevant to the esophageal cancer
in this section, we investigated the association of snp types with the cancer.
in df-snps, snp types were used to split each node in a tree, where the first split of the root node  selects the snp type best separating cases from the controls.
snp types were ranked in accordance to frequency of occurrence in the first split of a tree in  <dig> runs of 10-fold cross validation.
in the same manner as in the preceding section for snps, a critical value of  <dig>  was obtained from the randomization test to correspond to 95% confidence of significance.
of  <dig> possible snp types,  <dig> snp types were found to have frequency of occurrence greater than the critical value .
we also evaluated the odds ratio and its 95% confidence interval for snp type, which gives an estimate of how much more likely it is that an individual with the snp type is to be a cancer case than a control case.
of the  <dig>  five snp types had an odds ratio within the 95% confidence interval, indicating their significance to the esophageal cancer.
identification of snp patterns relevant to the esophageal cancer
here, we investigated the association of snp patterns  with the cancer.
in a tree, the classification of a sample is determined by only one terminal node that is descendent from the root node through a set of "if-then" rules based on k snp types .
a snp pattern was defined as a set of snp types used in a path of a set of the "if-then" rules.
we denote n-snp pattern as a snp pattern that contains n snp types .
since the snp types selected earlier for splitting nodes are more important than those selected later, a snp pattern begins at the root node and the pattern is incremented as each successive node of the tree.
thus, an n-snp pattern contains the following characteristics:  it always contains the snp pattern that splits the root node;  the snp types in a snp pattern are sequentially ordered in the path of the "if-then" rules; and  n-snp patterns are considered to be the same if they contain the same snp types, regardless of order.
we also evaluated the odds ratio and its 95% confidence interval for each n-snp pattern, which gives an estimate of how much more likely it is that an individual with a particular snp pattern is to be a cancer case than a control case.
results are given in table  <dig> for  <dig> snp patterns consisting of two snps  for which the odds ratio is within the confidence interval for distinguishing cancer cases from controls.
discussion
we developed a novel statistical approach, df-snps, that was used for an association study between snp type data and a case/control study of esophageal cancer.
using df-snps, we identified a list of snps, snp types and snp patterns that might be associated with esophageal squamous cell carcinoma.
this approach could be useful for identification of potential biomarkers based on snp data.
we have successfully developed and used the df method for various applications, including structure-activity relationship studies, microarray data analyses and proteomics data analyses  <cit> .
unlike previous applications of df, the independent variables in the snps data set are categorical rather than continuous.
moreover, each categorical variable  has only three categories , which is a difficult problem for most classification methods.
the df-snps is a variant of the df method that is specifically designed to analyze the snp-disease association.
in df-snps, as in previous df applications, multiple individual trees are combined to produce a better model.
as shown in figure  <dig>  the df model accuracy varies directly with the number of independent trees within the forest.
the 10-tree forest that was developed has high concordance, specificity and sensitivity for the fitted data.
such a model could be used to assess the cancer potential for unknown samples solely based on the snp profiles.
there are two important considerations for the use of df-snps when compared with alternative classifier methods.
first, combining identical or similar trees will not improve the quality of the forest derived from these trees and the benefit in combination can only be realized when individual trees are different or heterogeneous.
thus, each tree in df-snps uses a distinct snp type for splitting the root node, ensuring that each tree is different and encodes a different aspect of the disease-snp association.
secondly, the individual trees of similar quality  when combined may cancel some of the random noise inherent in snp type and case-control data.
the masscode mass spectrometry-based genotyping method resulted in 3–5% missing genotypes.
how to appropriately impute the missing value is important for subsequent analysis of the data generated from this technology.
accordingly, a two-step imputing method was embedded in df-snps.
first, we removed the individuals for whom most genotype data were missing, as well as removed snp variables that were not detected in many individuals.
then we imputed the missing snp genotypes for each remaining individual using a  <dig> nearest neighbor method.
this approach proved to be efficient for preprocessing the snps data set.
in df-snps, the potential cancer-related snps, snp types and snp patterns were identified on the basis of frequencies of occurrence in decision tree splitting for all trees during 10-fold cross-validation.
a randomization test was also done with cross-validation to provide a random distribution of frequencies for comparison with the fitted model.
comparison of the fitted and random frequencies provided the estimates of the statistical significance of snps, snp types and snp patterns in distinguishing cases versus controls
to investigate the relevant snps to the esophageal squamous cell carcinoma, we employed a weighted approach to calculate the frequency of each snp.
given the fact that the snps used for splitting the root node are applied to the entire data set while those used in the next split at the second level are applied to a much smaller portion of the data set , and that subsequent splits are applied to even smaller numbers, the relevance of the snps to cancer should decrease proportionally to the height of the tree level where they were selected.
we compared several weighted factors by taking into account of the tree level to calculate the frequency of snps, including  <dig>   <dig> ,  <dig>  and  <dig>  since other weighted factors potentially eliminated the snps used in the root node , the weighted factor of  <dig> was selected, indicating that the relevance  of a snp is reduced by half as moves to each subsequent lower level.
the odds ratios and corresponding confidence intervals were used to identify  <dig> snp types that distinguish cases from controls at 95% confidence .
of these, five had confidence intervals that were either > <dig> or < <dig> and thus are likely to be more significant.
of the five, two had confidence intervals < <dig>  indicating their possible association with reduced cancer potential.
three with confidence interval > <dig> are indicated to be associated with increased cancer risk.
we further found that two gadd45b e <dig> genotypes  are suggested to modify cancer risk differently, with the homozygous common genotype possibly increasing esophageal cancer risk and the heterozygous genotype possibly decreasing cancer risk.
these data suggest a potentially important role for polymorphisms of gadd45b e <dig> as a biomarker of esophageal cancer risk.
prospectively, given appropriate and sufficient data, df-snps provides a methodology that could identify the possible snp-snp associations, that is, snp patterns involved in genetic-based variation in cancer risk.
table  <dig> illustrates how such predictions would appear for the case of patterns of two snps.
of the  <dig> 2-snp patterns in table  <dig>  it is interested that the data suggests that  <dig> are associated with decreased risk and two are associated with increased risk.
also notable is that odds ratios are substantially larger for the patterns of two snps than for individual snps , possibly indicating that patterns of snps are more predictive of cancer risk than individual snps.
not surprisingly, analysis showed that odds rations vary in direct proportion to the length of snp patterns .
CONCLUSIONS
several statistical approaches including logistic regression methods have been used to analyze case/control snp data.
in this article, we propose df-snps as method to analyze snps data for purposes of biomarker identification.
df-snps is a novel variant of df that was previously developed in our lab.
df-snps was specifically structured to deal with the three genotype categories of snp data.
the df-snps algorithm incorporates the following processes:  a two-step approach to impute missing snps;  use of 10-fold cross-validation when calculating frequency of snps, snp types and snp patterns in discriminating cases from controls; and  estimating statistical significance by comparing frequencies from  with those from a random test also using 10-fold cross validation.
using df-snps, potential biomarkers could be quickly identified based on snps, snp types or snp patterns.
this method complements other methods currently in use.
authors' contributions
qx developed the method presented in the paper and wrote the first draft manuscript.
wt guided the method development and helped writing the manuscript.
hh developed the missing data imputing method and also involved the df-snps development.
lr generated the snp data set used in this study.
rp helped writing the manuscript.
lr generated the snp data set used in this study.
zzt, nh and prt conducted the case-control study.
all authors read and approved the final manuscript.
figures and tables
rs – reference snp

 the cause and progression of human diseases such as alzheimer's disease, cancer and diabetes are likely influenced by complex interactions of multiple genes as well as environmental and lifestyle factors that are sensitive to genome variability. single nucleotide polymorphisms are the most prevalent form of dna variation in the human genome occurring about once per to bases. the high frequency of relatively stable snps makes them excellent biomarkers for some disease phenotypes. while some serious diseases such as cystic fibrosis and sickle cell anemia are of predominately genetic etiology in homozygote individuals, other serious diseases are far more complex. in more complex diseases, a combination of multiple snps, plus environmental factors, may combine to determine disease susceptibility and prognosis. the terminology of "complex disease" is used because of the potential enormity of interacting genes that could be in the hundreds. the genetic factors that determine disease phenotypes may be encoded in the pattern of genomic variation that is primarily snps. cancer, mental illness, some autoimmune disorders and diabetes are among the common serious diseases thought to be significantly influenced by the spectrum of snps an individual has in certain susceptibility genes. population variability in drug response is thought to be analogously dependent on an individual's snp profile. therefore, the identification of particular snp patterns that are associated with susceptibility to disease or adverse drug reactions is a paramount goal of pharmacogenomics research. given recent development of high-throughput technologies for rapid genotyping, assessment of snp patterns holds much promise for use in diagnosis, prognosis and selection of treatment intervention. an essential bioinformatics challenge in pharmacogenomics is the discovery of snp patterns that differentiate diseased and healthy populations. determination of the snp patterns associated with disease susceptibility or adverse drug reaction from among potentially millions of snps is a challenge for pharmacogenomics. many methods have been described in the literature to assess the association between snps and disease. most of them are focused on identification of disease-related genotypes and haplotypes, where allele frequencies in cases and controls are estimated separately and then compared. currently, snps involved in complex diseases are not well enough understood, nor are genotype data sets adequate for development of models to reliably predict disease from snp profiles. however, the science is sufficiently advanced that studies such as presented herein can be useful to plan experiments, and to interpret data in what may well prove to be an arduous, lengthy and iterative process of identifying snps and snp patterns useful as biomarkers. esophageal cancer, like many other cancers, has been shown to be associated with genetic as well as environmental factors that cause dna damage. it is the sixth leading cause of cancer worldwide and seventh among american men. among the two main types of esophageal cancer, squamous cell carcinoma and adenocarcinoma, squamous cell carcinoma accounts for about half of all esophageal cancers. data from studies in animals suggest that oxidative damage from factors such as smoking or gastroesophageal reflux, which cause inflammation, esophagitis, and increased cell turnover, may initiate the carcinogenic process. studies also suggest that substantial alcohol intake, tobacco smoking and betel quid chewing increase the risk of squamous cell carcinoma. we investigated the association of snps and squamous cell carcinoma of the esophagus in a case-control study of individuals from shanxi province, a region in north-central china. shanxi has one of the highest esophageal cancer rates in the world. the snps chosen for the study were a set of those associated with dna repair, phase i and phase ii enzymes involved in xenobiotic clearance, and with alcohol metabolism. we developed a novel adaptation of the decision forest pattern recognition method named decision forest for snps. the method was designated to analyze the snps-disease association based on the snp data. importantly, the df-snps method utilizes the inherent differentiating ability of decision trees to separate disease and control population based on individual snps, the snp types, as well as combinations of snp types, that is, snp patterns. methods study population incident cases of esophageal cancer were obtained from an ongoing case-control study being conducted by the national cancer institute, usa and the shanxi cancer institute, china. esophageal cancer patients at the shanxi cancer hospital in taiyuan, shanxi province, were recruited to the case-control study. esophageal cancer was confirmed by the pathologists at the shanxi cancer hospital and national cancer institute and all cases were esophageal squamous cell carcinoma. controls matched on age, gender and neighbourhood were selected for each case. the study was approved by the institutional review boards of the shanxi cancer hospital and the us national cancer institute. after signed consent was obtained, a blood sample was collected from the participants and information on demographics and cancer risk factors including smoking, alcohol, diet, and family history were collected in an interview. snp data dna samples were genotyped at a commercial laboratory by masscode mass spectrometry genotyping. pcr primers used for genotyping were synthesized at bioserve. oligonucleotide sequences of the primers probe can be found at. all laboratory personnel were blinded to case-control status. a total of snps were chosen from dna repair, phase i, phase ii, and alcohol metabolism related genes. the average call rate for the study was %, and duplicate analysis of three of the snps generated %, %, and 100% concordance. the prevalence of the variant allele ranged from % to %. decision forest for snps df-snps is an ensemble classification method that combines multiple decision trees to derive a classifier based on a fitted set of if-then rules. by combining multiple heterogeneous decision trees, df-snps is effective in mitigating noise that is often prevalent in biological data, especially data from high throughput technologies, compared to single decision trees. moreover, the algorithm is computationally inexpensive, enabling cross validation and randomization tests to readily be included. figure depicts a general flowchart of df-snps. the detail information of each step in figure is described in the following sections. the df-snps was developed using c. data pre-processing it is common that the snp types for some individuals are inconclusive using most high-throughput genotyping methods, including the masscode mass spectrometry genotyping method. this results a data set that usually contains many missing values. accordingly, a data pre-processing procedure is required to impute the missing data for subsequent analysis. a two-steps data pre-processing procedure was implemented in df-snps. first, the samples with > 15% missing genotypes across all snp variables and the snp variables with > 15% missing genotypes across all the samples were removed. next, a 10-nearest neighbor method was employed to impute the missing data. in this method, if a sample has a missing value that is corresponding to a snp variable, we identified samples that not only had a measure for this snp but also had the closest snp profiles calculated based on the rest of the snp variables. the genotypes of these samples were used to impute the missing value by voting. there were missing genotypes in the data set. two snp variables and eight samples were removed, which resulting % missing value in the data set for imputing. the final data set for analysis after pre-processing contained individuals and snps, cancer cases and controls. decision tree development a tree was developed using the s-plus binary split method, where the snps are the independent variables grouped into three genotype categories: homozygous common, heterozygous and homozygous variant. the method started from the root node that contained all samples and identified a snp type of all possible snps that divided the samples into two child nodes. since this is a binary splitting of each tree node, the single snp type that best divides the node populating one branch and the other two genotypes populating the other branch. the impurity of a node was measured with deviance. the process was then recursively repeated on the child nodes and the process was stopped if further splitting did not improve the purity of the child node or the node can not be further split. figure provides a hypothetical example to illustrate the tree development process. if there is a snp data set with cases and controls, the process first identifies the best splitter, snp = heterozygous, to put samples in the right node and samples in the left node. the cases are enriched in the right node compared to its parent node while the controls are enriched in the left node. in the end of tree development, the cases and controls are enriched in the different terminal nodes. multiple tree development and combination in our previous application, multiple trees in df used distinct independent variables to maximize their difference; the variables used in one tree were not used in any other tree. since only a limited number of snp variables were in this application, we forced trees that selected different snp types in splitting the root node to assure heterogeneity. that is, a snp type selected for the root splitting in one tree was not allowed for use in splitting root nodes in other trees. however, this rule was not enforced in the subsequent splitting of the lower nodes. to ensure the comparability of trees, their qualities were maintained to the same by adjusting the misclassification rate in the tree development. finally, the classification of each sample was determined by averaging the outcomes from all trees. statistical testing if we generate many classification models using a bootstrapping method, the relevance of a snp, snp type or snp pattern should be directly correlate to the number of times they are used by the models. based on this assumption, we performed runs of 10-fold cross-validation and calculated the frequencies of each snp, snp type and snp pattern appeared in this process. to determine the statistical significance of the findings, we also generated a null hypothesis using the same statistical procedure. this was a randomization test, where the sample classification was randomly scrambled to generate pseudo data sets and the 10-fold cross-validation was then applied to each pseudo data set. thus, null distributions were generated for each snp, snp type and snp pattern. we then determined the critical values that corresponded to the 5% level of significance for snps, snp types and snp patterns, respectively. the statistically significant snps, snp types and snp patterns were these whose frequencies were greater than their corresponding critical values.  the study population comprised individuals genotyped for snps, of which were esophageal cancer patients and were age-frequencies matched controls. after removing individuals for which data was missing for more than 15% of genotypes, and removing snp variables that were missing data for more than 15% of the individuals, the data was reduced to individuals and snp variables. this is a binary classification problem. the snps are the independent variables grouped into three genotype categories: homozygous common, heterozygous and homozygous variant. using the df-snps method, we developed a classification model to differentiate the cases from the controls. the fitted binary decision forest model thus derived contained decision trees and exhibited high concordance, sensitivity and specificity, indicating that the model well differentiates disease from control samples. figure shows that the misclassifications of the model significantly diminish as trees are added to the forest, indicating that the df method may be canceling some random variation or amplifying the nonrandom signal as trees are added. ultimately, the 10-tree model has misclassifications of much less than the misclassification of the single decision tree. the df-snps algorithm includes functions that estimate on a relative basis the statistical significance of individual snps, snp types and snp patterns in differentiating snp case-control study data. the rational behind this approach is that the frequency of a particular snp, snp type or snp pattern selected by the model correlates positively with the relevance to discriminate the cases from controls. the frequency was obtained from a multiple runs of 10-fold cross-validation procedure. to determine the statistical significance of the disease-related snps, snp types and snp patterns, a null hypothesis was first generated where the scrambled snp data set was also subjected to the same multiple runs of 10-fold cross-validation. then, the frequency based on the real data set was compared with the null hypothesis. the purpose of this statistical test is to determine whether the obtained results reject the hypothesis that they are merely a product of chance factors. the results of this investigation are described in the following sections. identification of individual snps relevant to the esophageal cancer in this section, we investigated the association of individual snps with the cancer. the snps were ranked according to frequency of use in tree node splitting in runs of 10-fold cross-validation. the ranking frequency for snp i ) is computed as: where snpi = means that snp i was used as a split rule in tree k at level l. freq is calculated over all trees in the forest models in runs of 10-fold cross-validation. in this equation, snps at each lower node level are given half the frequency weight as snps at the preceding higher level. an estimate of the frequency of occurrence required for a snp to be statistically significant at 95% confidence is obtained from the random case. specifically, for the random case, the cumulative frequency of occurrence for snps rank ordered by frequency occurs for a snp with frequency of; snps having frequency greater than the critical value of are designated as significant to a 95% level of confidence. in the case-control study, nine out of total of snps had freq larger than, indicating their relevance to the esophageal cancer with p <. identification of snp types relevant to the esophageal cancer in this section, we investigated the association of snp types with the cancer. in df-snps, snp types were used to split each node in a tree, where the first split of the root node selects the snp type best separating cases from the controls. snp types were ranked in accordance to frequency of occurrence in the first split of a tree in runs of 10-fold cross validation. in the same manner as in the preceding section for snps, a critical value of was obtained from the randomization test to correspond to 95% confidence of significance. of possible snp types, snp types were found to have frequency of occurrence greater than the critical value. we also evaluated the odds ratio and its 95% confidence interval for snp type, which gives an estimate of how much more likely it is that an individual with the snp type is to be a cancer case than a control case. of the five snp types had an odds ratio within the 95% confidence interval, indicating their significance to the esophageal cancer. identification of snp patterns relevant to the esophageal cancer here, we investigated the association of snp patterns with the cancer. in a tree, the classification of a sample is determined by only one terminal node that is descendent from the root node through a set of "if-then" rules based on k snp types. a snp pattern was defined as a set of snp types used in a path of a set of the "if-then" rules. we denote n-snp pattern as a snp pattern that contains n snp types. since the snp types selected earlier for splitting nodes are more important than those selected later, a snp pattern begins at the root node and the pattern is incremented as each successive node of the tree. thus, an n-snp pattern contains the following characteristics: it always contains the snp pattern that splits the root node; the snp types in a snp pattern are sequentially ordered in the path of the "if-then" rules; and n-snp patterns are considered to be the same if they contain the same snp types, regardless of order. we also evaluated the odds ratio and its 95% confidence interval for each n-snp pattern, which gives an estimate of how much more likely it is that an individual with a particular snp pattern is to be a cancer case than a control case. results are given in table for snp patterns consisting of two snps for which the odds ratio is within the confidence interval for distinguishing cancer cases from controls. discussion we developed a novel statistical approach, df-snps, that was used for an association study between snp type data and a case/control study of esophageal cancer. using df-snps, we identified a list of snps, snp types and snp patterns that might be associated with esophageal squamous cell carcinoma. this approach could be useful for identification of potential biomarkers based on snp data. we have successfully developed and used the df method for various applications, including structure-activity relationship studies, microarray data analyses and proteomics data analyses. unlike previous applications of df, the independent variables in the snps data set are categorical rather than continuous. moreover, each categorical variable has only three categories, which is a difficult problem for most classification methods. the df-snps is a variant of the df method that is specifically designed to analyze the snp-disease association. in df-snps, as in previous df applications, multiple individual trees are combined to produce a better model. as shown in figure the df model accuracy varies directly with the number of independent trees within the forest. the 10-tree forest that was developed has high concordance, specificity and sensitivity for the fitted data. such a model could be used to assess the cancer potential for unknown samples solely based on the snp profiles. there are two important considerations for the use of df-snps when compared with alternative classifier methods. first, combining identical or similar trees will not improve the quality of the forest derived from these trees and the benefit in combination can only be realized when individual trees are different or heterogeneous. thus, each tree in df-snps uses a distinct snp type for splitting the root node, ensuring that each tree is different and encodes a different aspect of the disease-snp association. secondly, the individual trees of similar quality when combined may cancel some of the random noise inherent in snp type and case-control data. the masscode mass spectrometry-based genotyping method resulted in 3–5% missing genotypes. how to appropriately impute the missing value is important for subsequent analysis of the data generated from this technology. accordingly, a two-step imputing method was embedded in df-snps. first, we removed the individuals for whom most genotype data were missing, as well as removed snp variables that were not detected in many individuals. then we imputed the missing snp genotypes for each remaining individual using a nearest neighbor method. this approach proved to be efficient for preprocessing the snps data set. in df-snps, the potential cancer-related snps, snp types and snp patterns were identified on the basis of frequencies of occurrence in decision tree splitting for all trees during 10-fold cross-validation. a randomization test was also done with cross-validation to provide a random distribution of frequencies for comparison with the fitted model. comparison of the fitted and random frequencies provided the estimates of the statistical significance of snps, snp types and snp patterns in distinguishing cases versus controls to investigate the relevant snps to the esophageal squamous cell carcinoma, we employed a weighted approach to calculate the frequency of each snp. given the fact that the snps used for splitting the root node are applied to the entire data set while those used in the next split at the second level are applied to a much smaller portion of the data set, and that subsequent splits are applied to even smaller numbers, the relevance of the snps to cancer should decrease proportionally to the height of the tree level where they were selected. we compared several weighted factors by taking into account of the tree level to calculate the frequency of snps, including, and since other weighted factors potentially eliminated the snps used in the root node, the weighted factor of was selected, indicating that the relevance of a snp is reduced by half as moves to each subsequent lower level. the odds ratios and corresponding confidence intervals were used to identify snp types that distinguish cases from controls at 95% confidence. of these, five had confidence intervals that were either > or < and thus are likely to be more significant. of the five, two had confidence intervals < indicating their possible association with reduced cancer potential. three with confidence interval > are indicated to be associated with increased cancer risk. we further found that two gadd45b e genotypes are suggested to modify cancer risk differently, with the homozygous common genotype possibly increasing esophageal cancer risk and the heterozygous genotype possibly decreasing cancer risk. these data suggest a potentially important role for polymorphisms of gadd45b e as a biomarker of esophageal cancer risk. prospectively, given appropriate and sufficient data, df-snps provides a methodology that could identify the possible snp-snp associations, that is, snp patterns involved in genetic-based variation in cancer risk. table illustrates how such predictions would appear for the case of patterns of two snps. of the 2-snp patterns in table it is interested that the data suggests that are associated with decreased risk and two are associated with increased risk. also notable is that odds ratios are substantially larger for the patterns of two snps than for individual snps, possibly indicating that patterns of snps are more predictive of cancer risk than individual snps. not surprisingly, analysis showed that odds rations vary in direct proportion to the length of snp patterns.  several statistical approaches including logistic regression methods have been used to analyze case/control snp data. in this article, we propose df-snps as method to analyze snps data for purposes of biomarker identification. df-snps is a novel variant of df that was previously developed in our lab. df-snps was specifically structured to deal with the three genotype categories of snp data. the df-snps algorithm incorporates the following processes: a two-step approach to impute missing snps; use of 10-fold cross-validation when calculating frequency of snps, snp types and snp patterns in discriminating cases from controls; and estimating statistical significance by comparing frequencies from with those from a random test also using 10-fold cross validation. using df-snps, potential biomarkers could be quickly identified based on snps, snp types or snp patterns. this method complements other methods currently in use. authors' contributions qx developed the method presented in the paper and wrote the first draft manuscript. wt guided the method development and helped writing the manuscript. hh developed the missing data imputing method and also involved the df-snps development. lr generated the snp data set used in this study. rp helped writing the manuscript. lr generated the snp data set used in this study. zzt, nh and prt conducted the case-control study. all authors read and approved the final manuscript. figures and tables rs – reference snp 
we developed a novel adaptation of the decision forest pattern recognition method named decision forest for snps. the method was designated to analyze the snp data. the method could be useful to identify potential biomarkers from the snp data and complement existing methods for genotype analyses. esophageal squamous cell carcinoma is a high-mortality cancer with complex etiology and progression involving both genetic and environmental factors. we examined the association between esophageal cancer risk and patterns of snps in a case-control study for a population from shanxi province in north central china that has among the highest rates of esophageal squamous cell carcinoma in the world. the df-snps method can be used to differentiate esophageal squamous cell carcinoma cases from controls based on individual snps, snp types and snp patterns. importantly, the df-snps algorithm incorporated a randomization test for assessing the relevance of individual snps, snp types and patterns of snp types that differentiate cases from controls. the classifier in separating the cases from the controls developed with df-snps gave concordance, sensitivity and specificity, of %, % and %, respectively; suggesting its usefulness for hypothesizing what snps or combinations of snps could be involved in susceptibility to esophageal cancer. understanding how the millions of snps in the human genome are involved in conferring susceptibility or resistance to disease, or in rendering a drug efficacious or toxic in the individual is a major goal of the relatively new fields of pharmacogenomics. snps were chosen from among genes involving dna repair enzymes, and phase i and phase ii enzymes. for example, we found that the different genotypes of snp gadd45b e are all associated with cancer risk. systematic evaluation and study of single nucleotide polymorphisms made possible by high throughput genotyping technologies and bioinformatics promises to provide breakthroughs in the understanding of complex diseases.
 systematic evaluation and study of single nucleotide polymorphisms made possible by high throughput genotyping technologies and bioinformatics promises to provide breakthroughs in the understanding of complex diseases. understanding how the millions of snps in the human genome are involved in conferring susceptibility or resistance to disease, or in rendering a drug efficacious or toxic in the individual is a major goal of the relatively new fields of pharmacogenomics. esophageal squamous cell carcinoma is a high-mortality cancer with complex etiology and progression involving both genetic and environmental factors. we examined the association between esophageal cancer risk and patterns of snps in a case-control study for a population from shanxi province in north central china that has among the highest rates of esophageal squamous cell carcinoma in the world. methods high-throughput masscode mass spectrometry genotyping was done on genomic dna from individuals. snps were chosen from among genes involving dna repair enzymes, and phase i and phase ii enzymes. we developed a novel adaptation of the decision forest pattern recognition method named decision forest for snps. the method was designated to analyze the snp data.  the classifier in separating the cases from the controls developed with df-snps gave concordance, sensitivity and specificity, of %, % and %, respectively; suggesting its usefulness for hypothesizing what snps or combinations of snps could be involved in susceptibility to esophageal cancer. importantly, the df-snps algorithm incorporated a randomization test for assessing the relevance of individual snps, snp types and patterns of snp types that differentiate cases from controls. for example, we found that the different genotypes of snp gadd45b e are all associated with cancer risk.  the df-snps method can be used to differentiate esophageal squamous cell carcinoma cases from controls based on individual snps, snp types and snp patterns. the method could be useful to identify potential biomarkers from the snp data and complement existing methods for genotype analyses. 7– october second annual midsouth computational biology and bioinformatics society conference. bioinformatics: a systems approach little rock, ar, usa 