BACKGROUND
the volume of genomic data generated from genome-wide association studies  is growing at an exponential rate, in large part due to the decreasing cost of high-throughput genotyping technologies.
a gwas measures hundreds of thousands of single nucleotide polymorphism  across the human genome; a snp is the commonest type of genetic variation that results when a single nucleotide is replaced by another in the genome sequence.
the goal of a gwas is typically biomarker discovery, that is, to discover snps that either singly or in combination are associated with the disease of interest.
the high dimensionality of gwas data poses statistical and computational challenges in identifying associations between snps and disease efficiently and accurately.
the typical analysis of gwas data involves the application of a univariate feature ranking method that evaluates each snp’s strength of association with disease independently of all other snps.
for example, the chi squared statistic is used to assess the expected and observed genotypes of a snp in cases and controls in a gwas, and ranks snps according to the p-value.
univariate methods have the advantage of being are computationally efficient; however, they cannot capture interactions among genes and such interactions may play an important role in genetic basis of disease.
moreover, univariate methods may be associated with lack of reproducibility across datasets; that is, snps found to be relevant in one study do not show an association in another.
multivariate feature ranking methods evaluate each snp’s strength of association with disease in the context of other snps.
for example, relief is capable of detecting complex snp-snp dependencies even in the absence of main effects.
however, multivariate methods are computationally demanding since they consider the strength of association with disease of combinations of snps.
this paper describes the application of an efficient and stable multivariate machine learning method called label propagation .
lp has been applied successfully on other types of biological data, including gene expression and protein concentration data  <cit> ; however, to our knowledge, the method has not been applied to datasets with a very large number of features as found in gwass.
we apply lp to two alzheimer’s disease gwas datasets.
we conjectured that it would be efficient, produce reproducible rankings of snps and perform well.
a positive result would support using lp in analyzing other genome-wide datasets, including next-generation genome-wide datasets that contain even larger number of snps.
the following sections provide background information about genome-wide association studies, feature ranking methods, and alzheimer’s disease.
genome-wide association studies
in a gwas, high-throughput genotyping technologies are used to assay hundreds of thousands or even millions of snps across the genome in a cohort of cases and controls.
since the advent of gwass many common diseases, including alzheimer’s disease, diabetes, and heart disease have been studied with the goal of identifying the underlying genetic variations.
the success of gwass in identifying genetic variants associated with a disease rests on the common disease-common variant hypothesis.
this hypothesis posits that common diseases are caused usually by relatively common genetic variants and individually many of these variants have low penetrance and hence have small to moderate association with the disease  <cit> .
in the past decade, gwass have been moderately successful and have identified approximately  <dig>  common disease-associated snvs, and several hundred of the snvs have been replicated  <cit> .
a possible reason for the moderate success of gwass is the common disease-rare variant hypothesis, which posits that many rare variants underlie common diseases and each variant causes disease in relatively few individuals with high penetrance  <cit> .
however, larger sample sizes and new analytical methods will likely make gwass useful for detecting rare variants as well  <cit> .
feature selection and feature ranking methods
high-throughput genotyping and other biological technologies offer the promise of identifying sets of features that represent biomarkers for use in biomedical applications.
the challenge with these high-dimensional data is that the selection of a small set of features or the ranking of all features requires robust feature selection and feature ranking methods.
a range of selection and feature ranking methods have been developed and a recent review of the methods is provided in  <cit> .
there are two major families of feature selection methods, namely, filter methods and wrapper methods.
filter methods evaluate features directly independent of how the features will be used subsequently.
in contrast, wrapper methods evaluate features in the context of the how they will be used.
for example, if features are to be used subsequently to develop a classification model, a wrapper method evaluates the goodness of features in terms of their ability to improve the performance of the classification model.
filter methods assess the relevance of features by examining only the intrinsic properties of the data.
univariate filter methods compute the relevance of each feature independently of other features.
they are computationally fast and scale to high-dimensional data because the complexity is linear in the number of features and interactions between features are ignored.
typically, such methods compute a statistic or a score for each feature such as chi squared or information gain.
multivariate filter methods model correlations and dependencies among the features; they are computationally somewhat slower and may be less scalable to high-dimensional data.
examples of multivariate methods include correlation-based feature selection and markov blanket feature selection.
the chi squared statistic is commonly used in snp analysis is a univariate filter method.
this test measures whether outcome distributions are significantly different among snp states, indicating features that have an impact on disease.
the chi squared statistic is very fast to compute and has a simple statistical interpretation.
however, it cannot detect higher-order effects such as snps that interact to produce an effect on disease.
the relief method  <cit>  is a multivariate filter method that has been applied to snp data to rank snps.
this method computes the relevance of a snp by examining patterns in a local neighborhood of training samples.
the method examines whether, among reasonably similar samples, a change in snp state is accompanied by a change in the disease state.
relief can detect multivariate interaction effects by means of the neighborhood locality measure, but does so at the cost of increased computation time.
relief has been adapted in several ways for application to snp data.
the most recently described adaptations of relief include spatially uniform relieff   <cit>  and sigmoid weighted relieff   <cit>  that were developed specifically for application to high-dimensional snp data.
logistic regression is another commonly used multivariate method that has been applied to many bioinformatics tasks for both classification and feature ranking.
more recently, sparse logistic regression  models which are implicitly feature-selective have been developed for high-dimensional data.
slr uses l1-norm regularization that drives the weights of many of the features to zero, and has been used successfully as a feature selection method in high-dimensional biomedical data, including fmri imaging data  <cit>  and genomic data  <cit> .
one challenge of feature ranking in genomic data arises from the observation that a group of snps that are in linkage disequilibrium  will be statistically correlated and can lead to redundancy when many of the top-ranked variants represent the same genetic signal.
this is particularly an issue with univariate tests like chi squared, which operate solely on observational data counts.
with such a test, snps that have near-identical case–control distributions will be assigned near-identical scores.
the problem is mitigated somewhat by multivariate methods that utilize locality or other inference.
by considering the context of each attribute, even snps with near-identical case–control distributions may be assigned different scores based on the context of surrounding snps.
alzheimer’s disease
alzheimer’s disease  is a neurodegenerative disease characterized by slowly progressing memory failure, confusion, poor judgment, and ultimately, death  <cit> .
it is the most common form of dementia associated with aging.
there are two forms of ad, called familial ad and sporadic ad.
the rarer form is early-onset familial ad, which typically begins before 65 years of age.
the genetic basis of early-onset ad is well established, and it exhibits an autosomal dominant mode of inheritance.
most familial cases of ad are accounted for by mutations in one of three genes .
sporadic ad, also called late-onset ad , is the commoner form of ad, accounting for approximately 95% of all ad cases.
the onset of load symptoms typically occurs after 65 years age.
load has a heritable component, but has a more genetically complex mechanism than familial ad.
the strongest consistently replicated genetic risk factor for load is the apolipoprotein e  gene.
two genetic loci  together determine the allele of the apoe gene, which are called apoe* <dig>  apoe* <dig> and apoe* <dig>  the apoe* <dig> allele is a load risk factor, while the apoe* <dig> allele is associated with reduced risk  <cit> .
in the past several years, gwass have identified several additional genetic loci associated with load.
over a dozen significantly associated loci have been published in the literature, resulting from meta-analyses of several ad gwass  <cit> .
label propagation
this section first provides an overview of the label propagation and then provides more details of the method.
overview
lp is a machine learning method that can be used for prediction  and as a multivariate feature ranking method .
it is graph-based algorithm that represents the data as a bipartite graph.
a bipartite graph contains two sets of nodes  and edges that link nodes from one set to nodes in the other set.
the sample nodes are labeled with case/control status, and lp diffuses the labels across graph edges to the feature nodes and back again, until a stable solution is reached.
the solution results in a final labeling of all nodes in the graph, including the feature nodes, which balances the diffusion of the labels with consistency with the original labeling.
the labeling of the feature nodes can be used to rank the features, and the labeling of the sample nodes can be used as predictions.
the lp method scales well for thousands of samples and features.
it has complexity o, where n is the number of samples, f is the number of features and k is the number of iterations required for convergence.
typically, k is much smaller than n or f, which makes lp a relatively fast method.
lp is able to handle missing data and both continuous and discrete data.
because of its wide applicability, fast running time, and multivariate nature, lp has been applied to several bioinformatics problems.
lp has been used in breast cancer gene expression data in order to find functional modules of co-expressed genes  <cit> .
it has been applied to gene function prediction, utilizing known gene functions and interactions to infer the function of other genes  <cit> .
it has shown success in classifying patients with alzheimer’s disease using protein array data  <cit> .
to our knowledge, lp has not been applied to snp data.
unique challenges in the snp domain include a much larger feature space , as well as the discrete, nominal nature of snp states .
algorithmic details
we represent a gwas dataset as a bipartite graph g =  which consists of two sets of nodes v and u where nodes in v represent samples  and nodes in u represent features .
note that if a snp has three states  than it will be represented by three nodes in u. in addition to the two sets of nodes, the graph contains a set of edges e where each edge links a node in v with a node in u. an edge e that links node v with node u is associated with a link weight w = <dig>  these edges connect sample nodes to feature nodes, representing the presence of snp state u in individual v. initial labels y and y are applied to nodes, and take values {- <dig>   <dig>  +1}, representing known training information about case/control status , or a lack of information .
an example graph initialization is shown in figure  <dig>
given the graph initialization, the propagation algorithm finds an optimal assignment of node labels f and f, which minimizes the objective function
qf=∑v,u∈ewv,ufvdv-fudu2+μ∑v∈vfv-yv2+∑u∈ufu-yu <dig>
where μ is a parameter controlling the relative effect of the two parts of the cost function.
the first part of the equation is a smoothness constraint, ensuring that strongly connected nodes in v and u get similar labels.
here, d and d are the degree of each node in v and u, such that d = ∑  ∈ ew and d = ∑  ∈ ew.
the second part of the equation is a fitting constraint.
for labeled nodes, this ensures that nodes labels are consistent with the initial labeling.
for unlabeled nodes, this term constrains the overall cost.
in the discrete-label case where f → {- <dig>   <dig>  +1}, the optimization of this cost function is np-hard.
by relaxing the labels so that f → r, however, the optimization of this equation becomes straightforward as derived in zhou  <cit> , and has the solution f∗ = - 1y.
here, i is the identity matrix and s is the normalized connectivity matrix s=0dv-1/2wdu-1/2du-1/2wtdv-1/ <dig>  where w is the |v| × |u| sized matrix of edge weights and dv and du are the |v| × |v| and |u| × |u| diagonal matrices containing node degrees, respectively.
while the solution may be computed directly by algebraic evaluation, it requires the inversion of a t × t matrix where t is the total number of nodes in the network .
this requires between o and o time, depending on the inversion method used.
instead, we use an iterative procedure that diffuses node labels from one node set to another.
first, the normalized graph laplacian is computed as b=dv-12wdu- <dig>  this is a special encoding of the graph which represents node degrees and adjacency.
it has an interpretation as a random walk transition matrix, allowing labels to travel across graph edges.
the node labels on v and u are computed iteratively as
ft+1v=1-αyv+αbftuandft+1u=1-αyu+αbftv
where α is a user-specified parameter in the range  <cit>  that controls the balance between the initial labeling y and the diffusion of current labels f. this procedure ultimately converges to the same optimized node labeling as the direct algebraic evaluation.
the complexity of the direct algebraic evaluation is at least o2), while the complexity of the iterative procedure is o, where k is the number of iterations required for convergence.
the exact value of k depends on the properties of the graph as well as the convergence criteria, but was found to be orders of magnitude less than both |v| and |u| even when analyzing large graphs  with large alpha .
the final labeling of the nodes indicates association with the case or control group.
nodes with scores near + <dig> are associated with the case group, nodes with scores near - <dig> are associated with the control group, and nodes with scores near  <dig> are uninformative.
for sample nodes, this score can be viewed as a prediction of case/control status based on genetic information.
for feature nodes, this score can be interpreted as an association test that can be used to find biologically significant markers.
the feature node scores may be ordered to obtain a ranking of feature according to their association with the outcome.
methods
this section provides details of the datasets and the experimental design, the evaluation measures we used to evaluate lp, and the comparison methods including chi squared, swrf, and slr.
datasets
synthetic dataset
we created a synthetic dataset containing  <dig>  snps and a binary phenotype that is a function of  <dig> of those snps .
of the  <dig> snps,  <dig> of them were modeled as more common snps with mafs that were sampled uniformly from the range  <dig>  to  <dig>  with odds ratios in the range  <dig>  to  <dig>  and  <dig> snps were modeled as rare snps that were sampled uniformly from the range  <dig>  to  <dig>  and odds ratios in the range  <dig> to  <dig>  the remaining  <dig> snvs  ranged from common to rare, but do not have an effect on the disease.
phenotype status was assigned using an additive threshold model, with each causal snp conferring an independent risk of disease.
we created a set of  <dig>  individuals and in that set  <dig> % of individuals had a positive phenotype.
the comparable number of samples and features make this model fairly robust to variations across instantiations of the data, reducing the need for multiple runs to observe “average” statistical performance.
gwas datasets
we used two different load gwas datasets.
the first dataset comes from the university of pittsburgh alzheimer’s disease research center   <cit> .
this dataset consists of  <dig>  individuals of which  <dig>  were diagnosed with load and  <dig> were healthy age-matched controls.
in the original study  <dig> , <dig> snps were measured and after quality controls were applied by the original investigators  <dig>  snps located on autosomal chromosomes were retained for analysis.
the second dataset comes from the translational genomics research institute  located in phoenix, arizona  <cit> .
this dataset consists of three cohorts containing a total of  <dig>  individuals of which  <dig> were diagnosed with load and  <dig> were healthy age-matched controls.
in the original study  <dig>  snps were measured for each individual and after quality controls were applied by the original investigators  <dig>  autosomal snps were retained for analysis.
principal components analysis of each dataset indicated no significant population stratification between the cases and the controls.
between the datasets, however, differing allele frequencies are exhibited as indicated by clustering in the principal components analysis of the combined data.
because of this, we do not combine the datasets for a unified analysis, but still use cross-dataset learning to test generalizability of results.
for the ranking reproducibility and cross-dataset classification experiments, we retained from both datasets only those snps that were measured in both studies.
there are  <dig>  snps that are common across the two datasets.
in addition, we performed smaller-scale experiments on snps from chromosome  <dig>  which is known to contain several genetic variants that are associated with load.
there are  <dig>  snps in chromosome  <dig> in the adrc dataset and  <dig>  snps in the tgen dataset, and  <dig>  snps are common across the two datasets.
experimental methods
we compared the performance of lp to the performance of three control methods, which were chi squared, swrf, and slr.
we applied the four methods to the synthetic data to rank snps associated with the phenotype.
after ranking, we plotted precision-recall and roc curves to examine how well the truly associated snps were ranked.
for the real data, we applied each method to two gwas datasets to rank snps that are predictive of load.
we performed the experiments on a small-scale subset of the data consisting of only those snps in chromosome  <dig> which contains several well established load-related snps, and on the full genome-wide data.
we evaluated the rankings produced by the four methods by classification performance and feature reproducibility across the two datasets.
in addition, we examined the top-ranked snps from each method for previous evidence in the literature that they are associated with load.
classification performance
meaningful features should be predictive of disease, and classifiers developed from highly predictive snps should have good performance in discriminating between cases and controls.
we evaluated the predictive performance of the top-ranked snps for each feature ranking method and dataset by measuring the performance of a series of classification models that were developed using progressively larger number of top-ranked snps.
given a set of top-ranked snps obtained from a ranking method applied to a training dataset, we applied the k-nearest neighbor  classification method to a test dataset containing genotypes for the corresponding snps.
we evaluated the performance of knn using fivefold cross-validation.
the dataset was randomly partitioned into five approximately equal sets such that each set had a similar proportion of individuals who developed load.
we applied the ranking method on four sets taken together as the training data, and evaluated the classifer performance of the top-ranked snps on the remaining test data.
we repeated this process for each possible test set to obtain a load prediction for each individual in the dataset.
we used the predictions to compute the area under the receiver operating characteristic curve  which is a widely used measure of classification performance.
in addition, we performed cross-dataset validation experiments on the filtered dataset containing the common snps.
here, snps were ranked on one dataset, and the top-ranked snps were used to derive a knn classifier on the other dataset.
these experiments show the generalizability and robustness of the methods, quantifying how well inference on one dataset can be applied to another cohort.
the lp method is presented with a parameterization of α =  <dig> .
this parameterization was selected after testing several values between  <dig>  and  <dig>  on the small-scale tgen dataset.
the setting of  <dig>  puts more emphasis on matching the case/control training labels while still utilizing some network diffusion, and is suitable for finding discriminative snps.
smaller values of alpha lead to rankings that are indistinct from the chi squared test, while larger values lead to uninformative, uniform feature scores.
feature reproducibility
with the predictive power of the top-ranked snps established, we evaluated the feature ranking methods for reproducibility across the two datasets.
for the genome-wide datasets, we reduced them so that they contained only the genotypes for the  <dig>  snps that were common to both.
we ran each feature ranking method separately on each of the reduced datasets and examined the ranked snps for reproducibility.
given two ranked list of snps obtained by applying a feature ranking method to the two reduced datasets we examined the ranked lists for common snps in the top-ranked  <dig> snps,  <dig> snps,  <dig> snps, and so on.
reproducibility was calculated as the number of snps in common to both lists divided by the total number of snps in a list, yielding a value in the range from  <dig>  to  <dig> .
this metric only checks for presence or absence of snp in a list, and ignores actual ranks within the list.
the lp method is presented for multiple setting of α, ranging from  <dig>  to  <dig> .
evidence from the literature
we examined the top-ranked snps for biological significance and evidence of previously documented association with load.
we used several publically available databases and resources including snpedia  <cit> , genecards  <cit> , and dbsnp  <cit>  to search for links between the variants and load.
in addition to snps directly named in the literature as having an association with load, we also considered a wider degree of plausible associations.
for each snp, we searched whether it was in strong linkage disequilibrium with load-related snps, whether the snp was in a load-related gene, whether the associated gene was part of a strongly conserved, load-related family, or whether the variant has been associated with brain development or other neurological conditions.
computational efficiency
we ran all four methods on a pc with a  <dig>  ghz intel processor and 4 gb of ram.
all methods were implemented in java, except for the slr method, which is a matlab package  <cit> .
for each feature ranking method, we recorded the time required to score features on one training fold of the adrc dataset.
RESULTS
synthetic data
figure  <dig> shows the precision-recall and roc curves obtained from the four ranking methods on the synthetic dataset.
all methods do quite well in retrieving the  <dig> causal snps.
the slr method performs the best on this dataset, showing excellent retrieval even for small-effect snps.
the other methods perform well, identifying nearly all of the large-effect snps at the top of the ranking.
the small-effect size snps fall somewhat lower in the ranking, as indicated by the tail in the precision-recall graphs for three of the methods.
all four methods perform similarly in the roc space, achieving similar true positive rates for a given false positive rate.
the shape of the roc graph again indicates that all of the methods rank most of the valid snps at the top of the list, but only find the small-effect size snps after many false positives.
these results provide support that each of the methods is able to find valid associations in snp data over a range of mafs and effect sizes.
gwas classification performance
figure  <dig> shows the aucs obtained for the four ranking methods obtained from application of the knn classifier on the two load datasets.
generally, lp achieves equal or higher aucs than chi squared and swrf, and similar aucs to slr.
on the small-scale datasets  lp achieves statistically significantly higher aucs at the 5% significance level when compared to chi squared and swrf in the range from  <dig> to  <dig> top-ranked snps .
on the genome-wide datasets, similar statistically significantly higher aucs were achieved by lp in the range from  <dig> to  <dig> top-ranked snps .
lp has a statistically significantly lower auc than chi squared or swrf in only two experiments, when using just  <dig> or  <dig> snps in the adrc dataset.
when using at least  <dig> snps, lp always significantly outperforms either chi squared or swrf, or both.
the slr method does not perform significantly differently from lp in all experiments that use more than one snp for classification.
the entries are the cross-fold classification aucs and the 95% confidence intervals obtained from application of the knn classifier to a specified number of top-ranked snps.
bold cells indicate where lp significantly outperforms at least one of the other methods.
the slr method is implicitly feature-selective, reducing the feature space to under  <dig> features for all experiments .
for all four ranking methods, the classification performance shows the general trend of higher aucs with a moderate number of snps used in the classifier, and lower aucs at very small and very large numbers of snps.
compared to the other methods, lp’s performance drops far more slowly with increasing the number of snps in the classifier.
this is a useful property for a feature ranking method, because the number of features to be used in a classifier can be a difficult number to choose.
with too few features relevant snps may be missed, and with too many features irrelevant snps may be included.
the lp method picks features which limit the amount of noise introduced, widening the useful performance range of the classifier.
this reduces the chance of missing a relevant biomarker because of an overly restrictive feature selection threshold.
results for the cross-dataset experiments are found in table  <dig>  similar classification aucs to the cross-validated experiments indicate that the selected features are robust between datasets, having meaning even in other patient cohorts.
several algorithms have trouble identifying a useful snp in the # <dig> rank, possibly explained by stratification between the patient populations.
good performance is quickly achieved, however, providing further support that the selected variants are valid.
the entries are the cross-dataset classification aucs and the 95% confidence intervals.
feature selection was applied to one dataset, and the top-ranked features were used to derive and evaluate a knn classifier on the other dataset.
the slr method is implicitly feature-selective, reducing the feature space to under  <dig> features for all experiments .
gwas feature reproducibility
figure  <dig> shows the reproducibility results on the small-scale and genome-wide datasets.
chi squared identifies the first few snps reproducibly; these are snps that are located in genes apolipoprotein-e  and apolipoprotein-c  and are known to have large effects sizes.
beyond the first few snps, however, the reproducibility of chi squared drops rapidly to a level which is effectively random.
the swrf method produces somewhat reproducible results in the small-scale chromosome  <dig> datasets, but is no better than random for the genome-wide datasets.
the slr method selects on the order of  <dig> snps for each filtered dataset, and is not shown on the reproducibility graph.
for each slr experiment, there are only two overlapping snps in each selected list, which are the two major loci on apoe.
all other snps selected by slr are not reproduced from one dataset to another.
lp, in contrast to these methods, shows good reproducibility for many of the top-ranked snps, and does so even in the high-dimensional datasets.
the method has low reproducibility for the first few snps but quickly surpasses chi squared, swrf, and slr.
for higher values of α, lp has higher reproducibility.
for α close to  <dig>  diffusion of labels plays a small role in determining the ranking and lp behaves like a supervised method that computes a correlation measure.
when α is close to  <dig>  label diffusion has a greater effect on the ranking, and clusters in the data have a greater effect, yielding higher reproducibility.
by utilizing the dense connectedness of nodes in modules of snps, lp produces more reproducible results.
evidence from the literature
among the  <dig> top-ranked snps, several snps have previously known ad associations or have evidence for biologically plausibility of being involved in ad .
for both datasets, lp identified the highest number of plausibly associated snps.
in the tgen dataset,  <dig> of top  <dig> snps identified by lp had evidence of being associated with load, whether through direct association tests, co-location in associated genes, or through functional effects.
in contrast, only  <dig> of the top  <dig> snps identified by chi squared had evidence of being associated with load, slr identified  <dig> associated snps, and swrf identified  <dig> associated snps.
in the adrc dataset,  <dig> of the top  <dig> snps identified by lp had evidence of being associated with load.
chi squared also identified  <dig> load-related snps among the top 25; however,  <dig> of them are from a tightly clustered group of snps in chromosome  <dig> near the apoe locus, and do not represent a diverse genetic signal.
slr finds  <dig> associated snps in the adrc data, and swrf finds only  <dig>  for both datasets, the remaining snps not found in the literature are generally located in relatively unstudied intergenic regions of the genome.
computational efficiency
of the four ranking methods, chi squared is the fastest and took approximately 4 minutes to run on one training fold for the adrc dataset.
the swrf method was the slowest and took almost 2 days to run.
the slr method was also slow, taking 11 hours and 29 minutes to complete.
lp ran in  <dig> minutes for α =  <dig> , and took  <dig> minutes for α =  <dig> .
discussion
the results on the synthetic data show that lp performs comparably to the control methods that included chi squared, swrf, and slr.
the slr method performed particularly well in identifying small-effect snps in the synthetic data compared to lp and the other control methods.
on the gwas datasets, lp performed significantly better than chi squared and swrf in terms of classification performance, reproducibility, and identified more snps among the top  <dig> ranked snps that had prior evidence of being associated with load.
when compared to slr, lp had similar classification performance, but had better reproducibility and identified more snps among the top  <dig> ranked snps that had prior evidence of being associated with load.
in terms of computational efficiency lp is somewhat slower than chi squared, but is significantly faster than swrf and slr, and is sufficiently fast that it can be effectively applied to real genome-wide datasets.
overall, lp performs better than each of the control algorithms in one or more of the performance metrics tested, and does not perform significantly worse in any of them.
lp’s top-ranked features are reproducible across datasets, and provide good classification performance.
the underlying genetic mechanisms and patterns of inheritance used in the graph-based lp method are also not as susceptible to changes in experimental protocol as more traditional methods.
in contrast, chi squared computes a univariate statistic for each snp, and is susceptible to errors in the data .
lp, on the other hand, produces a score that depends on the distribution of all variants throughout the dataset.
this score is not as susceptible to small errors because the largely correct training information is able to diffuse across the network and mitigate mistakes.
the network propagation method also allows for more diverse genetic signals to be scored highly.
chi squared ranks snps in strong ld closely together because it operates solely on the observational data counts.
lp, on the other hand, can propagate influence from other parts of the network through sample nodes, meaning that even snps exhibited by mostly the same individuals can get different scores.
the lp method can be extended to handle significantly stratified data by using correction factors as described in  <cit> .
in this method, principal components of variation are determined, and phenotypes and genotypes are adjusted to zero out this variation.
phenotype adjustment is simple, requiring only a re-labeling of the sample nodes.
genotype adjustment in lp is more complex, requiring edge weights other than  <dig> and  <dig> to be encoded.
one limitation of this paper is that we examined only two datasets related to a single disease.
in future research, we plan to investigate the performance of lp on additional load gwas datasets as well as gwas datasets from other diseases.
CONCLUSIONS
biomarker discovery in gwas data is a challenging problem with the potential for many false positives and the lack of reproducibility across datasets.
lp had excellent comparative performance among the four feature ranking methods we applied in this paper, based on the results of classification accuracy, reproducibility, biological validity, and running time.
the lp method is effective in all of these performance measures across a range of experimental conditions, while the other methods tested are weak in at least one of these areas.
these results provide support for including lp in the methods that are used to rank snps in high-dimensional gwas datasets.
abbreviations
adrc: alzheimer disease research center; auc: area under the  curve; knn: k-nearest-neighbor classifier; gwas: genome-wide association study; load: late-onset alzheimer’s disease; lp: label propagation; maf: minor allele frequency; slr: sparse logistic regression; snp: single nucleotide polymorphism; swrf: sigmoid weighted relieff; tgen: translational genomics research institute.
competing interests
the authors declare that they have no competing interests.
authors’ contributions
mes designed the study, performed the experiments and drafted the manuscript, mik and sv designed the study and edited the manuscript, mmb edited the manuscript.
all authors read and approved the final manuscript.
supplementary material
additional file 1
top  <dig> snps as ranked by each algorithm  on two load datasets .
each snp rsid is listed with the associated chromosome and gene, as well as any connection to load in the literature.
click here for file
acknowledgements
this research was funded by nlm grant t <dig> lm <dig> to the university of pittsburgh biomedical informatics training program, and nih grants ag <dig>  ag <dig> and ag <dig> to the university of pittsburgh.

 the volume of genomic data generated from genome-wide association studies is growing at an exponential rate, in large part due to the decreasing cost of high-throughput genotyping technologies. a gwas measures hundreds of thousands of single nucleotide polymorphism across the human genome; a snp is the commonest type of genetic variation that results when a single nucleotide is replaced by another in the genome sequence. the goal of a gwas is typically biomarker discovery, that is, to discover snps that either singly or in combination are associated with the disease of interest. the high dimensionality of gwas data poses statistical and computational challenges in identifying associations between snps and disease efficiently and accurately. the typical analysis of gwas data involves the application of a univariate feature ranking method that evaluates each snp’s strength of association with disease independently of all other snps. for example, the chi squared statistic is used to assess the expected and observed genotypes of a snp in cases and controls in a gwas, and ranks snps according to the p-value. univariate methods have the advantage of being are computationally efficient; however, they cannot capture interactions among genes and such interactions may play an important role in genetic basis of disease. moreover, univariate methods may be associated with lack of reproducibility across datasets; that is, snps found to be relevant in one study do not show an association in another. multivariate feature ranking methods evaluate each snp’s strength of association with disease in the context of other snps. for example, relief is capable of detecting complex snp-snp dependencies even in the absence of main effects. however, multivariate methods are computationally demanding since they consider the strength of association with disease of combinations of snps. this paper describes the application of an efficient and stable multivariate machine learning method called label propagation. lp has been applied successfully on other types of biological data, including gene expression and protein concentration data; however, to our knowledge, the method has not been applied to datasets with a very large number of features as found in gwass. we apply lp to two alzheimer’s disease gwas datasets. we conjectured that it would be efficient, produce reproducible rankings of snps and perform well. a positive result would support using lp in analyzing other genome-wide datasets, including next-generation genome-wide datasets that contain even larger number of snps. the following sections provide background information about genome-wide association studies, feature ranking methods, and alzheimer’s disease. genome-wide association studies in a gwas, high-throughput genotyping technologies are used to assay hundreds of thousands or even millions of snps across the genome in a cohort of cases and controls. since the advent of gwass many common diseases, including alzheimer’s disease, diabetes, and heart disease have been studied with the goal of identifying the underlying genetic variations. the success of gwass in identifying genetic variants associated with a disease rests on the common disease-common variant hypothesis. this hypothesis posits that common diseases are caused usually by relatively common genetic variants and individually many of these variants have low penetrance and hence have small to moderate association with the disease. in the past decade, gwass have been moderately successful and have identified approximately common disease-associated snvs, and several hundred of the snvs have been replicated. a possible reason for the moderate success of gwass is the common disease-rare variant hypothesis, which posits that many rare variants underlie common diseases and each variant causes disease in relatively few individuals with high penetrance. however, larger sample sizes and new analytical methods will likely make gwass useful for detecting rare variants as well. feature selection and feature ranking methods high-throughput genotyping and other biological technologies offer the promise of identifying sets of features that represent biomarkers for use in biomedical applications. the challenge with these high-dimensional data is that the selection of a small set of features or the ranking of all features requires robust feature selection and feature ranking methods. a range of selection and feature ranking methods have been developed and a recent review of the methods is provided in. there are two major families of feature selection methods, namely, filter methods and wrapper methods. filter methods evaluate features directly independent of how the features will be used subsequently. in contrast, wrapper methods evaluate features in the context of the how they will be used. for example, if features are to be used subsequently to develop a classification model, a wrapper method evaluates the goodness of features in terms of their ability to improve the performance of the classification model. filter methods assess the relevance of features by examining only the intrinsic properties of the data. univariate filter methods compute the relevance of each feature independently of other features. they are computationally fast and scale to high-dimensional data because the complexity is linear in the number of features and interactions between features are ignored. typically, such methods compute a statistic or a score for each feature such as chi squared or information gain. multivariate filter methods model correlations and dependencies among the features; they are computationally somewhat slower and may be less scalable to high-dimensional data. examples of multivariate methods include correlation-based feature selection and markov blanket feature selection. the chi squared statistic is commonly used in snp analysis is a univariate filter method. this test measures whether outcome distributions are significantly different among snp states, indicating features that have an impact on disease. the chi squared statistic is very fast to compute and has a simple statistical interpretation. however, it cannot detect higher-order effects such as snps that interact to produce an effect on disease. the relief method is a multivariate filter method that has been applied to snp data to rank snps. this method computes the relevance of a snp by examining patterns in a local neighborhood of training samples. the method examines whether, among reasonably similar samples, a change in snp state is accompanied by a change in the disease state. relief can detect multivariate interaction effects by means of the neighborhood locality measure, but does so at the cost of increased computation time. relief has been adapted in several ways for application to snp data. the most recently described adaptations of relief include spatially uniform relieff and sigmoid weighted relieff that were developed specifically for application to high-dimensional snp data. logistic regression is another commonly used multivariate method that has been applied to many bioinformatics tasks for both classification and feature ranking. more recently, sparse logistic regression models which are implicitly feature-selective have been developed for high-dimensional data. slr uses l1-norm regularization that drives the weights of many of the features to zero, and has been used successfully as a feature selection method in high-dimensional biomedical data, including fmri imaging data and genomic data. one challenge of feature ranking in genomic data arises from the observation that a group of snps that are in linkage disequilibrium will be statistically correlated and can lead to redundancy when many of the top-ranked variants represent the same genetic signal. this is particularly an issue with univariate tests like chi squared, which operate solely on observational data counts. with such a test, snps that have near-identical case–control distributions will be assigned near-identical scores. the problem is mitigated somewhat by multivariate methods that utilize locality or other inference. by considering the context of each attribute, even snps with near-identical case–control distributions may be assigned different scores based on the context of surrounding snps. alzheimer’s disease alzheimer’s disease is a neurodegenerative disease characterized by slowly progressing memory failure, confusion, poor judgment, and ultimately, death. it is the most common form of dementia associated with aging. there are two forms of ad, called familial ad and sporadic ad. the rarer form is early-onset familial ad, which typically begins before 65 years of age. the genetic basis of early-onset ad is well established, and it exhibits an autosomal dominant mode of inheritance. most familial cases of ad are accounted for by mutations in one of three genes. sporadic ad, also called late-onset ad, is the commoner form of ad, accounting for approximately 95% of all ad cases. the onset of load symptoms typically occurs after 65 years age. load has a heritable component, but has a more genetically complex mechanism than familial ad. the strongest consistently replicated genetic risk factor for load is the apolipoprotein e gene. two genetic loci together determine the allele of the apoe gene, which are called apoe* apoe* and apoe* the apoe* allele is a load risk factor, while the apoe* allele is associated with reduced risk. in the past several years, gwass have identified several additional genetic loci associated with load. over a dozen significantly associated loci have been published in the literature, resulting from meta-analyses of several ad gwass. label propagation this section first provides an overview of the label propagation and then provides more details of the method. overview lp is a machine learning method that can be used for prediction and as a multivariate feature ranking method. it is graph-based algorithm that represents the data as a bipartite graph. a bipartite graph contains two sets of nodes and edges that link nodes from one set to nodes in the other set. the sample nodes are labeled with case/control status, and lp diffuses the labels across graph edges to the feature nodes and back again, until a stable solution is reached. the solution results in a final labeling of all nodes in the graph, including the feature nodes, which balances the diffusion of the labels with consistency with the original labeling. the labeling of the feature nodes can be used to rank the features, and the labeling of the sample nodes can be used as predictions. the lp method scales well for thousands of samples and features. it has complexity o, where n is the number of samples, f is the number of features and k is the number of iterations required for convergence. typically, k is much smaller than n or f, which makes lp a relatively fast method. lp is able to handle missing data and both continuous and discrete data. because of its wide applicability, fast running time, and multivariate nature, lp has been applied to several bioinformatics problems. lp has been used in breast cancer gene expression data in order to find functional modules of co-expressed genes. it has been applied to gene function prediction, utilizing known gene functions and interactions to infer the function of other genes. it has shown success in classifying patients with alzheimer’s disease using protein array data. to our knowledge, lp has not been applied to snp data. unique challenges in the snp domain include a much larger feature space, as well as the discrete, nominal nature of snp states. algorithmic details we represent a gwas dataset as a bipartite graph g =  which consists of two sets of nodes v and u where nodes in v represent samples and nodes in u represent features. note that if a snp has three states than it will be represented by three nodes in u. in addition to the two sets of nodes, the graph contains a set of edges e where each edge links a node in v with a node in u. an edge e that links node v with node u is associated with a link weight w = these edges connect sample nodes to feature nodes, representing the presence of snp state u in individual v. initial labels y and y are applied to nodes, and take values {- +1}, representing known training information about case/control status, or a lack of information. an example graph initialization is shown in figure  given the graph initialization, the propagation algorithm finds an optimal assignment of node labels f and f, which minimizes the objective function qf=∑v,u∈ewv,ufvdv-fudu2+μ∑v∈vfv-yv2+∑u∈ufu-yu where μ is a parameter controlling the relative effect of the two parts of the cost function. the first part of the equation is a smoothness constraint, ensuring that strongly connected nodes in v and u get similar labels. here, d and d are the degree of each node in v and u, such that d = ∑  ∈ ew and d = ∑  ∈ ew. the second part of the equation is a fitting constraint. for labeled nodes, this ensures that nodes labels are consistent with the initial labeling. for unlabeled nodes, this term constrains the overall cost. in the discrete-label case where f → {- +1}, the optimization of this cost function is np-hard. by relaxing the labels so that f → r, however, the optimization of this equation becomes straightforward as derived in zhou, and has the solution f∗ = - 1y. here, i is the identity matrix and s is the normalized connectivity matrix s=0dv-1/2wdu-1/2du-1/2wtdv-1/ where w is the |v| × |u| sized matrix of edge weights and dv and du are the |v| × |v| and |u| × |u| diagonal matrices containing node degrees, respectively. while the solution may be computed directly by algebraic evaluation, it requires the inversion of a t × t matrix where t is the total number of nodes in the network. this requires between o and o time, depending on the inversion method used. instead, we use an iterative procedure that diffuses node labels from one node set to another. first, the normalized graph laplacian is computed as b=dv-12wdu- this is a special encoding of the graph which represents node degrees and adjacency. it has an interpretation as a random walk transition matrix, allowing labels to travel across graph edges. the node labels on v and u are computed iteratively as ft+1v=1-αyv+αbftuandft+1u=1-αyu+αbftv where α is a user-specified parameter in the range that controls the balance between the initial labeling y and the diffusion of current labels f. this procedure ultimately converges to the same optimized node labeling as the direct algebraic evaluation. the complexity of the direct algebraic evaluation is at least o2), while the complexity of the iterative procedure is o, where k is the number of iterations required for convergence. the exact value of k depends on the properties of the graph as well as the convergence criteria, but was found to be orders of magnitude less than both |v| and |u| even when analyzing large graphs with large alpha. the final labeling of the nodes indicates association with the case or control group. nodes with scores near + are associated with the case group, nodes with scores near - are associated with the control group, and nodes with scores near are uninformative. for sample nodes, this score can be viewed as a prediction of case/control status based on genetic information. for feature nodes, this score can be interpreted as an association test that can be used to find biologically significant markers. the feature node scores may be ordered to obtain a ranking of feature according to their association with the outcome. methods this section provides details of the datasets and the experimental design, the evaluation measures we used to evaluate lp, and the comparison methods including chi squared, swrf, and slr. datasets synthetic dataset we created a synthetic dataset containing snps and a binary phenotype that is a function of of those snps. of the snps, of them were modeled as more common snps with mafs that were sampled uniformly from the range to with odds ratios in the range to and snps were modeled as rare snps that were sampled uniformly from the range to and odds ratios in the range to the remaining snvs ranged from common to rare, but do not have an effect on the disease. phenotype status was assigned using an additive threshold model, with each causal snp conferring an independent risk of disease. we created a set of individuals and in that set % of individuals had a positive phenotype. the comparable number of samples and features make this model fairly robust to variations across instantiations of the data, reducing the need for multiple runs to observe “average” statistical performance. gwas datasets we used two different load gwas datasets. the first dataset comes from the university of pittsburgh alzheimer’s disease research center. this dataset consists of individuals of which were diagnosed with load and were healthy age-matched controls. in the original study, snps were measured and after quality controls were applied by the original investigators snps located on autosomal chromosomes were retained for analysis. the second dataset comes from the translational genomics research institute located in phoenix, arizona. this dataset consists of three cohorts containing a total of individuals of which were diagnosed with load and were healthy age-matched controls. in the original study snps were measured for each individual and after quality controls were applied by the original investigators autosomal snps were retained for analysis. principal components analysis of each dataset indicated no significant population stratification between the cases and the controls. between the datasets, however, differing allele frequencies are exhibited as indicated by clustering in the principal components analysis of the combined data. because of this, we do not combine the datasets for a unified analysis, but still use cross-dataset learning to test generalizability of results. for the ranking reproducibility and cross-dataset classification experiments, we retained from both datasets only those snps that were measured in both studies. there are snps that are common across the two datasets. in addition, we performed smaller-scale experiments on snps from chromosome which is known to contain several genetic variants that are associated with load. there are snps in chromosome in the adrc dataset and snps in the tgen dataset, and snps are common across the two datasets. experimental methods we compared the performance of lp to the performance of three control methods, which were chi squared, swrf, and slr. we applied the four methods to the synthetic data to rank snps associated with the phenotype. after ranking, we plotted precision-recall and roc curves to examine how well the truly associated snps were ranked. for the real data, we applied each method to two gwas datasets to rank snps that are predictive of load. we performed the experiments on a small-scale subset of the data consisting of only those snps in chromosome which contains several well established load-related snps, and on the full genome-wide data. we evaluated the rankings produced by the four methods by classification performance and feature reproducibility across the two datasets. in addition, we examined the top-ranked snps from each method for previous evidence in the literature that they are associated with load. classification performance meaningful features should be predictive of disease, and classifiers developed from highly predictive snps should have good performance in discriminating between cases and controls. we evaluated the predictive performance of the top-ranked snps for each feature ranking method and dataset by measuring the performance of a series of classification models that were developed using progressively larger number of top-ranked snps. given a set of top-ranked snps obtained from a ranking method applied to a training dataset, we applied the k-nearest neighbor classification method to a test dataset containing genotypes for the corresponding snps. we evaluated the performance of knn using fivefold cross-validation. the dataset was randomly partitioned into five approximately equal sets such that each set had a similar proportion of individuals who developed load. we applied the ranking method on four sets taken together as the training data, and evaluated the classifer performance of the top-ranked snps on the remaining test data. we repeated this process for each possible test set to obtain a load prediction for each individual in the dataset. we used the predictions to compute the area under the receiver operating characteristic curve which is a widely used measure of classification performance. in addition, we performed cross-dataset validation experiments on the filtered dataset containing the common snps. here, snps were ranked on one dataset, and the top-ranked snps were used to derive a knn classifier on the other dataset. these experiments show the generalizability and robustness of the methods, quantifying how well inference on one dataset can be applied to another cohort. the lp method is presented with a parameterization of α = . this parameterization was selected after testing several values between and on the small-scale tgen dataset. the setting of puts more emphasis on matching the case/control training labels while still utilizing some network diffusion, and is suitable for finding discriminative snps. smaller values of alpha lead to rankings that are indistinct from the chi squared test, while larger values lead to uninformative, uniform feature scores. feature reproducibility with the predictive power of the top-ranked snps established, we evaluated the feature ranking methods for reproducibility across the two datasets. for the genome-wide datasets, we reduced them so that they contained only the genotypes for the snps that were common to both. we ran each feature ranking method separately on each of the reduced datasets and examined the ranked snps for reproducibility. given two ranked list of snps obtained by applying a feature ranking method to the two reduced datasets we examined the ranked lists for common snps in the top-ranked snps, snps, snps, and so on. reproducibility was calculated as the number of snps in common to both lists divided by the total number of snps in a list, yielding a value in the range from to. this metric only checks for presence or absence of snp in a list, and ignores actual ranks within the list. the lp method is presented for multiple setting of α, ranging from to. evidence from the literature we examined the top-ranked snps for biological significance and evidence of previously documented association with load. we used several publically available databases and resources including snpedia, genecards, and dbsnp to search for links between the variants and load. in addition to snps directly named in the literature as having an association with load, we also considered a wider degree of plausible associations. for each snp, we searched whether it was in strong linkage disequilibrium with load-related snps, whether the snp was in a load-related gene, whether the associated gene was part of a strongly conserved, load-related family, or whether the variant has been associated with brain development or other neurological conditions. computational efficiency we ran all four methods on a pc with a  ghz intel processor and 4 gb of ram. all methods were implemented in java, except for the slr method, which is a matlab package. for each feature ranking method, we recorded the time required to score features on one training fold of the adrc dataset.  synthetic data figure  shows the precision-recall and roc curves obtained from the four ranking methods on the synthetic dataset. all methods do quite well in retrieving the causal snps. the slr method performs the best on this dataset, showing excellent retrieval even for small-effect snps. the other methods perform well, identifying nearly all of the large-effect snps at the top of the ranking. the small-effect size snps fall somewhat lower in the ranking, as indicated by the tail in the precision-recall graphs for three of the methods. all four methods perform similarly in the roc space, achieving similar true positive rates for a given false positive rate. the shape of the roc graph again indicates that all of the methods rank most of the valid snps at the top of the list, but only find the small-effect size snps after many false positives. these results provide support that each of the methods is able to find valid associations in snp data over a range of mafs and effect sizes. gwas classification performance figure  shows the aucs obtained for the four ranking methods obtained from application of the knn classifier on the two load datasets. generally, lp achieves equal or higher aucs than chi squared and swrf, and similar aucs to slr. on the small-scale datasets lp achieves statistically significantly higher aucs at the 5% significance level when compared to chi squared and swrf in the range from to top-ranked snps. on the genome-wide datasets, similar statistically significantly higher aucs were achieved by lp in the range from to top-ranked snps. lp has a statistically significantly lower auc than chi squared or swrf in only two experiments, when using just or snps in the adrc dataset. when using at least snps, lp always significantly outperforms either chi squared or swrf, or both. the slr method does not perform significantly differently from lp in all experiments that use more than one snp for classification. the entries are the cross-fold classification aucs and the 95% confidence intervals obtained from application of the knn classifier to a specified number of top-ranked snps. bold cells indicate where lp significantly outperforms at least one of the other methods. the slr method is implicitly feature-selective, reducing the feature space to under features for all experiments. for all four ranking methods, the classification performance shows the general trend of higher aucs with a moderate number of snps used in the classifier, and lower aucs at very small and very large numbers of snps. compared to the other methods, lp’s performance drops far more slowly with increasing the number of snps in the classifier. this is a useful property for a feature ranking method, because the number of features to be used in a classifier can be a difficult number to choose. with too few features relevant snps may be missed, and with too many features irrelevant snps may be included. the lp method picks features which limit the amount of noise introduced, widening the useful performance range of the classifier. this reduces the chance of missing a relevant biomarker because of an overly restrictive feature selection threshold. results for the cross-dataset experiments are found in table  similar classification aucs to the cross-validated experiments indicate that the selected features are robust between datasets, having meaning even in other patient cohorts. several algorithms have trouble identifying a useful snp in the # rank, possibly explained by stratification between the patient populations. good performance is quickly achieved, however, providing further support that the selected variants are valid. the entries are the cross-dataset classification aucs and the 95% confidence intervals. feature selection was applied to one dataset, and the top-ranked features were used to derive and evaluate a knn classifier on the other dataset. the slr method is implicitly feature-selective, reducing the feature space to under features for all experiments. gwas feature reproducibility figure  shows the reproducibility results on the small-scale and genome-wide datasets. chi squared identifies the first few snps reproducibly; these are snps that are located in genes apolipoprotein-e and apolipoprotein-c and are known to have large effects sizes. beyond the first few snps, however, the reproducibility of chi squared drops rapidly to a level which is effectively random. the swrf method produces somewhat reproducible results in the small-scale chromosome datasets, but is no better than random for the genome-wide datasets. the slr method selects on the order of snps for each filtered dataset, and is not shown on the reproducibility graph. for each slr experiment, there are only two overlapping snps in each selected list, which are the two major loci on apoe. all other snps selected by slr are not reproduced from one dataset to another. lp, in contrast to these methods, shows good reproducibility for many of the top-ranked snps, and does so even in the high-dimensional datasets. the method has low reproducibility for the first few snps but quickly surpasses chi squared, swrf, and slr. for higher values of α, lp has higher reproducibility. for α close to diffusion of labels plays a small role in determining the ranking and lp behaves like a supervised method that computes a correlation measure. when α is close to label diffusion has a greater effect on the ranking, and clusters in the data have a greater effect, yielding higher reproducibility. by utilizing the dense connectedness of nodes in modules of snps, lp produces more reproducible results. evidence from the literature among the top-ranked snps, several snps have previously known ad associations or have evidence for biologically plausibility of being involved in ad. for both datasets, lp identified the highest number of plausibly associated snps. in the tgen dataset, of top snps identified by lp had evidence of being associated with load, whether through direct association tests, co-location in associated genes, or through functional effects. in contrast, only of the top snps identified by chi squared had evidence of being associated with load, slr identified associated snps, and swrf identified associated snps. in the adrc dataset, of the top snps identified by lp had evidence of being associated with load. chi squared also identified load-related snps among the top 25; however, of them are from a tightly clustered group of snps in chromosome near the apoe locus, and do not represent a diverse genetic signal. slr finds associated snps in the adrc data, and swrf finds only for both datasets, the remaining snps not found in the literature are generally located in relatively unstudied intergenic regions of the genome. computational efficiency of the four ranking methods, chi squared is the fastest and took approximately 4 minutes to run on one training fold for the adrc dataset. the swrf method was the slowest and took almost 2 days to run. the slr method was also slow, taking 11 hours and 29 minutes to complete. lp ran in minutes for α =, and took minutes for α =. discussion the results on the synthetic data show that lp performs comparably to the control methods that included chi squared, swrf, and slr. the slr method performed particularly well in identifying small-effect snps in the synthetic data compared to lp and the other control methods. on the gwas datasets, lp performed significantly better than chi squared and swrf in terms of classification performance, reproducibility, and identified more snps among the top ranked snps that had prior evidence of being associated with load. when compared to slr, lp had similar classification performance, but had better reproducibility and identified more snps among the top ranked snps that had prior evidence of being associated with load. in terms of computational efficiency lp is somewhat slower than chi squared, but is significantly faster than swrf and slr, and is sufficiently fast that it can be effectively applied to real genome-wide datasets. overall, lp performs better than each of the control algorithms in one or more of the performance metrics tested, and does not perform significantly worse in any of them. lp’s top-ranked features are reproducible across datasets, and provide good classification performance. the underlying genetic mechanisms and patterns of inheritance used in the graph-based lp method are also not as susceptible to changes in experimental protocol as more traditional methods. in contrast, chi squared computes a univariate statistic for each snp, and is susceptible to errors in the data. lp, on the other hand, produces a score that depends on the distribution of all variants throughout the dataset. this score is not as susceptible to small errors because the largely correct training information is able to diffuse across the network and mitigate mistakes. the network propagation method also allows for more diverse genetic signals to be scored highly. chi squared ranks snps in strong ld closely together because it operates solely on the observational data counts. lp, on the other hand, can propagate influence from other parts of the network through sample nodes, meaning that even snps exhibited by mostly the same individuals can get different scores. the lp method can be extended to handle significantly stratified data by using correction factors as described in. in this method, principal components of variation are determined, and phenotypes and genotypes are adjusted to zero out this variation. phenotype adjustment is simple, requiring only a re-labeling of the sample nodes. genotype adjustment in lp is more complex, requiring edge weights other than and to be encoded. one limitation of this paper is that we examined only two datasets related to a single disease. in future research, we plan to investigate the performance of lp on additional load gwas datasets as well as gwas datasets from other diseases.  biomarker discovery in gwas data is a challenging problem with the potential for many false positives and the lack of reproducibility across datasets. lp had excellent comparative performance among the four feature ranking methods we applied in this paper, based on the results of classification accuracy, reproducibility, biological validity, and running time. the lp method is effective in all of these performance measures across a range of experimental conditions, while the other methods tested are weak in at least one of these areas. these results provide support for including lp in the methods that are used to rank snps in high-dimensional gwas datasets. abbreviations adrc: alzheimer disease research center; auc: area under the curve; knn: k-nearest-neighbor classifier; gwas: genome-wide association study; load: late-onset alzheimer’s disease; lp: label propagation; maf: minor allele frequency; slr: sparse logistic regression; snp: single nucleotide polymorphism; swrf: sigmoid weighted relieff; tgen: translational genomics research institute. competing interests the authors declare that they have no competing interests. authors’ contributions mes designed the study, performed the experiments and drafted the manuscript, mik and sv designed the study and edited the manuscript, mmb edited the manuscript. all authors read and approved the final manuscript. supplementary material additional file 1 top snps as ranked by each algorithm on two load datasets. each snp rsid is listed with the associated chromosome and gene, as well as any connection to load in the literature. click here for file acknowledgements this research was funded by nlm grant t lm to the university of pittsburgh biomedical informatics training program, and nih grants ag ag and ag to the university of pittsburgh.
ranking and identifying biomarkers that are associated with disease from genome-wide measurements holds significant promise for understanding the genetic basis of common diseases. these results provide support for including lp in the methods that are used to rank snps in genome-wide datasets. performance was measured by evaluating the top-ranked snps in terms of classification performance, reproducibility between the two datasets, and prior evidence of being associated with load. on gwas data, lp performed significantly better than chi squared and swrf in classification performance in the range from to top-ranked snps for both datasets, and not significantly different from slr. the large number of single nucleotide polymorphisms in genome-wide studies, however, makes this task computationally challenging when the ranking is to be done in a multivariate fashion. this paper evaluates the performance of a multivariate graph-based method called label propagation that efficiently ranks snps in genome-wide data. the performance of lp was evaluated on a synthetic dataset and two late onset alzheimer’s disease genome-wide datasets, and the performance was compared to that of three control methods. lp performed considerably better in ranking snps in two high-dimensional genome-wide datasets when compared to three control methods. bioinformaticsgenome-wide association studyfeature rankinglabel propagationpredictionreproducibilitysingle nucleotide polymorphismalzheimer’s disease it had better performance in the evaluation measures we used, and is computationally efficient to be applied practically to data from genome-wide studies. the control methods included chi squared, which is a commonly used univariate method, as well as a relief method called swrf and a sparse logistic regression method, which are both multivariate ranking methods. on the synthetic data lp performed comparably to the control methods.
 ranking and identifying biomarkers that are associated with disease from genome-wide measurements holds significant promise for understanding the genetic basis of common diseases. the large number of single nucleotide polymorphisms in genome-wide studies, however, makes this task computationally challenging when the ranking is to be done in a multivariate fashion. this paper evaluates the performance of a multivariate graph-based method called label propagation that efficiently ranks snps in genome-wide data.  the performance of lp was evaluated on a synthetic dataset and two late onset alzheimer’s disease genome-wide datasets, and the performance was compared to that of three control methods. the control methods included chi squared, which is a commonly used univariate method, as well as a relief method called swrf and a sparse logistic regression method, which are both multivariate ranking methods. performance was measured by evaluating the top-ranked snps in terms of classification performance, reproducibility between the two datasets, and prior evidence of being associated with load. on the synthetic data lp performed comparably to the control methods. on gwas data, lp performed significantly better than chi squared and swrf in classification performance in the range from to top-ranked snps for both datasets, and not significantly different from slr. lp also had greater ranking reproducibility than chi squared, swrf, and slr. among the top-ranked snps that were identified by lp, there were snps in one dataset that had evidence in the literature of being associated with load, and snps in the other, which was higher than for the other methods.  lp performed considerably better in ranking snps in two high-dimensional genome-wide datasets when compared to three control methods. it had better performance in the evaluation measures we used, and is computationally efficient to be applied practically to data from genome-wide studies. these results provide support for including lp in the methods that are used to rank snps in genome-wide datasets. bioinformaticsgenome-wide association studyfeature rankinglabel propagationpredictionreproducibilitysingle nucleotide polymorphismalzheimer’s disease 