You will be presented with the full text of a biomedical research paper. Please write an abstract for this paper. Your response should include the abstract and no additional text.

Paper text:
there is an increasing interest in using linear mixed models ( lmms , also known as mixed linear models , or mlms ) to test for association in genome - wide association studies ( gwas ) , because of their demonstrated effectiveness in accounting for relatedness among samples and in controlling for population stratification and other confounding factors .
however , these models present substantial computational challenges . for example , at the time this work was submitted for publication , the most efficient algorithm for computing ( effectively ) exact association test statistics ( either the wald test or the likelihood ratio test ) , implemented in the efficient mixed model association ( emma ) software , had a per - snp computational time that increases with the cube of the number of individuals ( n ) . as a result ,
a medium size gwas with a few thousand individuals and half a million snps would take years of cpu time to analyze .
( while this paper was in review , lippert et al ( 2011 ) also published an efficient algorithm for this model , implemented in software fast - lmm ; the relationship between this algorithm and ours is discussed later . )
several approximation methods have been proposed to make genome - wide analysis using linear mixed models possible .
probably the simplest and fastest of these approximations , grammar ( genome - wide rapid association using mixed model and regression ) , implemented in the software genabel , first estimates the residuals from the lmm under the null model , and then treats these residuals as phenotypes for further genome - wide analysis by a standard linear model .
this substantially reduces per - snp computation time , making it linear in the number of individuals .
zhang et al use p3d ( population parameters previously determined ) which avoids repeatedly estimating variance components when performing each test by simply using the pre - estimated variance components from the null model ; their method is implemented in the software tassel .
kang et al also avoid repeatedly estimating variance components by a slightly different strategy , which keeps the heritability estimated from the null model fixed when testing individual snps .
( this approximation , and related ideas , was also considered by previous authors , including . )
both these last two approximations have per - snp computation time that increases quadratically with the number of individuals , which makes them practical , on a single desktop computer , for gwas involving thousands of individuals .
although in some settings the approximate methods described above provide results almost identical to those of the exact method , this is not guaranteed in general , and in practice it is hard to know how accurate the approximations will be without running an exact calculation .
one possible consequence of inaccuracy in the approximation could be a reduction in power compared with exact methods .
here , we present a new , more efficient , method for exact calculations that provides numerically identical results to emma ( i.e. exact wald or likelihood ratio test statistics ) but is roughly n times faster ( computation time per snp , when using the usual genome - wide relatedness matrix , is quadratic in the number of individuals , with run time similar to emmax ) .
this makes exact calculations feasible for large gwas , obviating the need for approximate methods in most common settings .
the method and its computational complexity is described and derived in detail in the online methods section .
briefly , the method requires complete or imputed genotype data for all snps , and involves only one eigen - decomposition of the relatedness matrix at the beginning ( computational complexity o(n ) ) . for each snp tested
, it effectively replaces the expensive additional eigen - decomposition step in emma with one matrix and vector multiplication ( computational complexity o(n ) ) .
after this , like emma , each iteration of the following optimization step requires cheap operations ( complexity o(n ) ) to evaluate both first and second derivatives of the target functions .
we refer to our method as genome - wide efficient mixed model association ( gemma ) because it builds on emma and facilitates its genome - wide application .
we illustrate our method and compare the analysis results with the exact method emma and the approximation methods emmax and grammar , using two examples , a mouse gwas for high - density lipoprotein cholesterol ( hdl - c ) levels from the hybrid mouse diversity panel ( hmdp ) and a human gwas for crohn 's disease from the wellcome trust case control consortium ( wtccc ) .
table 1 summarizes the computational complexity for the four methods along with cpu time for the two data sets on a single desktop cpu .
table 1 also includes results for the recently - published fast - lmm , which can produce identical p values to emma and gemma in the same time complexity as gemma ; see below for further discussion .
as expected gemma is comparable in speed with emmax , completing the larger ( wtccc ) example in under 4 hours . to verify the correctness of our algorithm and implementation we first validate it by comparing p values calculated by gemma with those from emma on a subset of snps from both data sets . for
all snps examined the p values from the two methods match exactly ( wald test results shown in figure 1a and 1b ; likelihood ratio test not shown ) .
since gemma provides exact computations in essentially the same time as emmax , the accuracy of the approximations in emmax and other methods may seem moot .
however , in some settings , and specifically for mixed models with more than one random effect ( variance component ) , the computational trick used by gemma does not apply , and approximations along the lines of emmax may remain necessary . for this reason the accuracy of different approximation methods remains of some potential interest , and so we present a comparison between the ( wald test ) p values from gemma , emmax and grammar , genome - wide , on both the hmdp and wtccc data sets above .
the hmdp gwas represents a situation where approximation methods such as emmax or grammar may yield inaccurate test statistics .
in particular , because individuals in the data set are closely related , and the strongly associated snps contribute to a significant proportion of phenotypic variation in hdl - c , using estimates of variance components or fitted residuals from the null model for testing may be expected to yield conservative p values , leading to a potential loss of power .
our empirical comparison ( figure 1c ) confirms this : in this case , approximation by emmax leads to systematic and appreciable underestimation of the most significant p values ( almost two orders of magnitude ) , while approximation by grammar leads to dramatic underestimation of all p values .
indeed , in contrast to the exact p values , no p values generated by emmax are significant at the conventional 0.05 level after bonferroni correction , and no p values generated by grammar are significant even before bonferroni correction .
the fact that the exact p values for the most significant results are substantially more significant than the approximate p values from emmax suggests that , in this type of setting , the exact p values may produce a more powerful test ; simulation results confirm this ( supplementary fig .
, the wtccc example represents a very different situation where the approximations may be expected to yield accurate test statistics .
this is because there is relatively little population stratification in these data ( the individuals are all from the uk , and the relatedness matrix is approximately diagonal ) , and the effect sizes of the most strongly associated snps for crohn 's disease are small compared with the effect sizes in the hmdp data above .
empirical comparisons ( figure 1d ) show that , for this particular data set , the p values from emmax differ negligibly from the exact values .
taken together , the above results confirm that approximation by emmax is appreciably more accurate than grammar , even in cases , such as the wtccc data , where the sample structure is subtle .
the comparisons also demonstrate that the accuracy of the emmax approximation can vary from case to case .
consequently , the potential gain in power from doing exact vs approximate tests will also vary among datasets .
for the hmdp data , the potential gain in power from the exact calculations appears considerable , and this is confirmed by simulations ( supplementary fig .
the power gain is negligible , and as noted in ref only a small gain in power is generally expected at snps with small effect size .
of course , one nice feature of being able to do the exact tests is that it obviates the need to consider which approximations work best under what circumstances , or to consider ways in which the approximations could be improved .
we also note that the computational tricks employed here also apply to other settings , including the combined  variable selection plus random effects  model that has been widely studied for phenotype and breeding value prediction , but which , without the trick used here , is computationally challenging to fit .
in summary , we have presented an efficient method for computing exact values of standard test statistics in linear mixed models .
this method is comparable in speed with approximation methods such as emmax while yielding exact test statistics . using two examples
we illustrate our method , and show that the approximation methods can yield inaccurate p values when the sample structure is strong and/or when the marker effect size is large .
we also find that the approximation by emmax is more accurate than the approximation by grammar genome - wide ( a comparison made possible only by the availability of an efficient exact method ) .
while this work was in review , lippert et al also published an efficient method for computing likelihoods for lmms that , like our method , requires only one singular value decomposition of the relatedness matrix .
they use this method , in combination with brent 's optimization algorithm , to produce an algorithm for computing exact test statistics with effectively the same computational complexity as gemma : o(mn+cn+pn+ptcn ) , as in table 1 .
( lippert et al also suggest a further innovation , using a low - rank relatedness matrix in place of the usual relatedness matrix computed from all snps genome - wide , that produces an algorithm that is linear in n , and so feasible for very large gwas samples containing more than 100,000 individuals ; however changing the relatedness matrix in this way changes the resulting p values appreciably , and in this sense this linear complexity algorithm is not directly comparable with either gemma or emma ; see below for further discussion . ) the main additional contribution of our work here beyond that in lippert et al is that we provide , and make use of , efficient methods for evaluation of not only the likelihood , but also both its first and second derivatives .
this allows us to make use of the newton -- raphson optimization method , which has better theoretical convergence properties than brent 's algorithm ( quadratic , vs super - linear ) , potentially reducing per - snp computation time by reducing the number of iterations required for convergence , t. the practical effect of this is expected to depend on the sample size n. examining the theoretical computational complexity , if p is large ( and we assume the simplest case with no additional covariates , so c=1 ) then the per - snp complexity of the algorithms is o(nw + tn ) . thus if n is large then the n term will dominate and the number of iterations will have only a small effect of computation time ; if n is moderate then the number of iterations may play a more important role .
consistent with this , we found gemma to be 12 times faster than the lippert et al algorithm , implemented in fast - lmm , for the smaller hmdp dataset ( 33 minutes vs 6.8 hours ) , but only 2 times faster for the wtccc data ( 3.3 hours vs 6.2 hours ) .
it is possible that implementational issues , which are important but conceptually less fundamental , also contribute to this difference in speed .
besides this difference in speed , which might be considered a minor issue , by providing efficient methods to compute derivatives our work here lays the foundations for similar efficient analyses for lmms with multivariate phenotypes , where multidimensional optimization is required and evaluating the target functions alone is unlikely to suffice .
here we have focused on computations using the usual relatedness matrix , computed from all snps genome - wide , whose rank , r , is typically equal to the number of individuals n. however , as noted by lippert et al , if a lower - rank relatedness matrix is used then this reduces computing time ( computational complexity of the singular value decomposition can scale with nr ) and in some cases memory requirements ( e.g. lippert et al .
suggest using a relatedness matrix based on only a few thousand snps ; this has the nice property that required singular value decompositions can be done without computing the n by n relatedness matrix itself ) . using the usual full - rank relatedness matrix
, our current implementation of gemma can handle approximately 23,000 individuals on a machine with 64 gb memory ( in double precision ) ; using a lower - rank relatedness matrix , much larger problems could be tackled . however , we note that changing the relatedness matrix can produce much larger changes in p values than , for example , the differences between emmax and exact calculations ( e.g. supplementary fig .
2 ) , and for both the hmdp and wtccc data using a lower - rank relatedness matrix seems to compromise the ability of the lmm to control for sample structure ( supplementary table 1 ) .
thus choice of relatedness matrix could affect statistical efficiency ( both power , and correct control of type i error due to stratification or relatedness ) as well as computational efficiency .
interestingly , statistical and computational considerations may not necessarily conflict : for example , suggest that use of compressed mlm , which yields a lower - rank relatedness matrix by clustering individuals , can both reduce computation and increase power compared with the full - rank matrix . the general question of which low - rank relatedness matrices produce the best combination of computational and statistical performance seems to be an interesting avenue for further study .
linear mixed models have attracted considerable recent attention as a powerful and effective tool for accounting for population stratification and relatedness in genetic association tests . however , existing methods for exact computation of standard test statistics are computationally impractical for even moderate - sized genome - wide association studies . to deal with this several approximate methods have been proposed . here 
 , we present an efficient exact method that makes these approximations unnecessary in many settings . 
 this method is roughly n times faster than the widely - used exact method emma , where n is the sample size , making exact genome - wide association analysis computationally practical for large numbers of individuals .