BACKGROUND
expression quantitative trait loci  mapping aims at identifying single nucleotide polymorphisms  that influence the expression level of genes.
it has been widely applied to analyze the genetic basis of gene expression and molecular mechanisms underlying complex traits  <cit> .
in a typical eqtl study, the association between each expression trait and each snp is assessed separately .
this approach does not consider the interactions among snps and among genes.
however, multiple snps may interact with each other and jointly influence the phenotypes  <cit> .
this assumption will inevitably miss complex cases where multiple genetic variants jointly affect the co-expressions of multiple genes.
it has been observed in biological experiments that the joint effect of multiple snps to a phenotype may be non-additive  <cit> , and genes from the same biological pathway are usually co-regulated  <cit>  by the same genetic basis.
the biological process contains both individual effects and joint effects between snps and genes  <cit> .
a straightforward approach to detect associations between sets of snps and a gene expression level can be done using the standard gene set enrichment analysis  <cit> .
wu et al.
<cit>  further proposed the variance component models for snp set testing.
braun et al.
employed aggregation-based approaches to cluster snps  <cit> .
in  <cit> , listgarten et al.
further considered the potential confounding factors.
however, there are two limitations for these approaches.
first, these methods typically only consider snps from pre-defined pathways or gene ontology categories, which are far from being complete.
second, these methods can only detect the mapping of snp set and a single gene expression level.
to better elucidate the genetic basis of gene expression, it is a crucial challenge to understand how multiple modestly-associated snps interact to influence the a group of genes  <cit> .
in this paper, we refer to this kind of eqtl mapping to find associations between group of snps and group of gene expression levels as the group-wise eqtl mapping.
an example is shown in fig.
<dig>  note that an ideal model should allow overlaps between snp sets and between gene sets, that is, a snp or gene may participate in multiple individual and group-wise associations  <cit> .
in literature, group-wise eqtl mapping has attracted increasing research interest recently.
for example, xu et al.
<cit>  proposed a two-graph-guided multi-task lasso approach to infer group-wise eqtl mapping.
however, it required the grouping information of both snps and genes available as prior knowledge, which may not be practical for many applications.
besides, it is not able to correct the effects of confounding factors.
fig.
<dig> an illustration of individual and group-wise associations.
ellipses represent the groups of snps and genes.
blue arrows between snps and genes represent identified associations
in this paper, we propose a novel method, geqtl, to automatically detect individual and group-wise associations in eqtl studies.
it uses a two-layer feature selection strategy and adopts efficient optimization techniques, which make it suitable for large scale studies.
moreover, geqtl can automatically infer the optimal number of group-wise associations.
we perform extensive experiments on both simulated datasets and yeast datasets to demonstrate the effectiveness and efficiency of the proposed method.
methods
preliminaries
important notations used in this paper are listed in table  <dig>  in this paper, for each sample, the data of snps and genes are denoted by column vectors.
let x=t denote the k snps.
here, xi∈{ <dig> ,2} denotes a random variable corresponding to the i-th snp .
let z=t denote the n genes in the study.
zj denotes a continuous random variable corresponding to the j-th gene expression.
let x={xh|1≤h≤h}∈ℝk×h be the snp matrix.
we use z={zh|1≤h≤h}∈ℝn×h to denote the matrix of gene expression levels.
h denotes the number of samples in consideration.
k
n
h
m
x
z
y
x∈ℝk×h
z∈ℝn×h
a∈ℝm×k
b∈ℝn×m
c∈ℝn×k
α,β,γ,ρ
r∈ℝn×k
bold term means vector or matrix while non-bold term means scalar
the traditional linear regression model for association mapping between x and z is
z=wx+μ+ε,
where z is a linear function of x with coefficient matrix w, μ is an n× <dig> translation factor vector.
and ε is the additive noise of gaussian distribution with zero-mean and variance γi, where γ is a scalar.
that is, ε∼n.
in association studies, sparsity is a reasonable assumption because only a small fraction of genetic variants are expected to be associated with a set of gene expression traits.
this can be modeled as a feature selection problem.
for example, the standard lasso  <cit>  can be used in association mapping, which applies ℓ <dig> penalty on w for sparsity.
if both x and z are standardized, the objective function of lasso is formulated as
minw||z−wx||f2+η||w|| <dig>
where ||·||f denotes the frobenius norm, ||·|| <dig> is the ℓ1-norm.
η is the empirical parameter for the ℓ <dig> penalty.
w is the parameter  matrix parameterizing the space of linear functions mapping from x to z.
confounding factors, such as unobserved covariates, experimental artifacts and unknown environmental perturbations, may mask real signals and lead to spurious findings.
lors  <cit>  uses a low-rank matrix l∈ℝn×h to account for the variations caused by hidden factors.
the objective function of lors is
minw,l||z−wx−l||f2+η||w||1+ρ||l||∗,
where ||·||∗ is the nuclear norm  <cit> .
ρ is the regularization parameter to control the rank of l. l is a low-rank matrix assuming that there are only a small number of hidden factors influencing the gene expression levels.
when we fix {w, we can optimize {l} by using singular value decomposition  according to the following lemma.
lemma <dig>
suppose that matrix o has rank r. the solution to the optimization problem
mins12||o−s||f2+λ||s||∗
is given by s^=hλ, where hλ=udλvt with dλ=diag, udvt is the singular value decomposition  of o, d=diag, and +=max,0),.
thus, for fixed w, the formula for updating l is
l←hλ
both lasso and lors do not consider the existence of group-wise associations.
below, we will introduce the proposed model to infer both group-wise and individual associations for eqtl mapping.
geqtl
in geqtl, individual associations between snps and genes are modeled by following the lasso-based strategy.
group-wise associations are inferred using a two-layer feature selection method.
since multiple snps may have joint effect on a group of genes, and such effect may be accomplished through complex biological processes, we introduce latent variables to bridge sets of snps and sets of genes.
specifically, we assume that there exist latent factors regulating the gene expression level, which serve as bridges between the snps and the genes.
the latent variables are denoted by y=t.
here, m ) is the total number of latent variables representing group-wise associations.
the relationship between x and y can be represented as
y=ax+ε <dig>
where
ε1∼n <dig> σ12im.
a∈ℝm×k denotes the matrix of coefficients between x and y. σ12im denotes the variances of the additive noise.
im is an identity matrix.
here we drop the intercept terms because the input data x and z are normalized to zero mean and unit variance as preprocessing.
similarly, the relationship between y and z can be represented as
z=by+cx+ε <dig>
where
ε2∼n <dig> σ22in.
b∈ℝn×m denotes the matrix of coefficients between y and z, c∈ℝn×k denotes the matrix of coefficients between x and z to encode the individual associations.
note that eq.
decouples the associations between snps and genes into two parts: one for individual associations represented as cx, and another for group-wise associations represented as by.
next, we infer the group-wise associations by a two-layer feature selection strategy.
we first remove the individual associations and denote
z~=z−cx.
thus z~ contains only group-wise effects.
next let
y=ax.
thus y represents a low-rank transformation of the original snp matrix.
each row of y represents a group of snps.
from eq.
, we have the following multiple-input-multiple-output  linear system
z~=by+e,
where e is a gaussian white-noise term.
in eq.
and , a and b should be sparse since a single gene is often influenced by a small number of snps and vice versa  <cit> .
therefore, the overall objective function is
mina,b,c,lloss+ρ||l||∗+α||a||1+β||b||1+γ||c|| <dig>
where α,β,γ,ρ are the regularization parameters, and the loss function is
loss=||z−l−x||f <dig>
here, we choose different penalties for a,b,c because the sparsities of different matrices are typically of different scales.
optimization
the optimization for l can be achieved by following a similar approach as in  <cit> .
to optimize a,b,c, many tools can be used to optimize the ℓ <dig> penalized objective function, e.g., the orthant-wise limited-memory quasi-newton  algorithm  <cit> .
due to space limitation, we omit the details.
in the next, we devise optimization techniques that can dramatically improve the computational efficiency of geqtl.
boosting the computational efficiency
given a large number of snps and gene expression traits, scalability of the algorithm is a crucial issue.
we propose two improved models, geqtl + and geqtl-ridge, which optimize the search for significant individual associations, which is the main computational bottleneck of the algorithm.
geqtl +
in a typical eqtl study, we usually have m≪min.
thus, the bottleneck of the algorithm is to optimize c. our strategy is to confine the space of c. the intuition is that we only permit a small fraction of elements in c to be nonzero.
it has been shown that if z and x are standardized with zero mean and unit sum of squares, then r=abs is equal to the gene-snp correlations |)  <cit> .
since for many test statistics, e.g., t, f, r <dig>  and lr, for the simple linear regression problem can be expressed as functions of the sample correlation rgs, e.g., r2=r <dig>  and t=rn−21−r <dig>  we can find a threshold according to the required p-value, such that test statistics exceeding the threshold are significant at the required significance level.
the test statistics for every gene-snp pair in r are compared with the threshold, and only those elements whose r are greater than the threshold are optimized.
we denote r∈ℝn×k as the indicator matrix indicating which elements in c can be nonzero .
geqtl-ridge
when n and k are extremely large, optimizing c may still be time-consuming, since it may take many iterations to converge with the ℓ <dig> constraint.
next, we introduce geqtl-ridge, which further improves the time efficiency with slight decrease in accuracy.
the key idea is to use ridge regression for individual associations so that we can get a closed form solution for c. the objective function is shown in the following.
mina,b,c,lloss+ρ||l||∗+α||a||1+β||b||1+γ||c|| <dig> s.t.i,jisnozeroonlyifi,jis <dig>
theorem <dig>
the solution of c in eq.
is
ci←dixtpipitxxtpi+γik−1pit,
where
ci=i,:,di=i,:,  d=z−l−bax,  and pi is defined as in formula .
the proof of the theorem  <dig> is in the following section.
proof of theorem 1
proof.
recall that any ridge regression problem
mina||b−aq||22+||aΓ|| <dig>
where a is a row vector and q has linearly independent rows, has the following solution
a=bqt− <dig>
note that
loss=||d−cx||f2=∑i=1n||di−cix|| <dig>
where d=z−l−bax, ci=i,: and di=i,:.
we have
mincloss=∑i=1nminci||di−cix|| <dig>
taking into account that j can be nonzero only if i,j is  <dig>  we introduce pi, where pi has k rows and li=∑j=1ki,j columns.
and
s,t= <dig> ifi,sisthet-th1ini,:; <dig> otherwise.
then ci=cipipit, ||di−cix||22+γ||ci||22=||di−pitx||22+γ||cipi|| <dig>  and
minci||di−cix||22+γ||ci|| <dig> s.t.jisnozeroonlyifi,jis <dig>
is solved by
ci=pit=dixtpipitxxtpi+γik−1pit.
therefore,
mincloss+γ||c|| <dig> s.t.i,jisnozeroonlyifi,jis <dig>
is solved by c=c1t,…,cntt, which leads to the update formula given in eq.
.
determining the number of hidden variables
in eq.
, we use ba+c to formulate the overall associations between snps and expression traits.
two group-wise associations will not share the same group of snps , since otherwise these two group-wise associations can be combined into one.
therefore, every group-wise association should be unique and irreplaceable.
hence, following two conditions should be satisfied
a has linearly independent rows.
since m≪k, this condition is equivalent to that a has full rank;
b has linearly independent columns.
since m≪n, this condition is equivalent to that b has full rank.
when these two conditions are met, we have
m=rank=rank=rank.
the last equality holds because both a and b have full rank.
we have the following observation.
the singular value decomposition  of ba has the form
ba=uΣvt,  where u and v are unitary  matrices, and Σ is a rectangular diagonal matrix with non-negative real numbers on the diagonal, which corresponds to singular values of ba.
since u and v are unitary and hence have full rank, we have
rank=rankuΣvt=rank=the number of nonzero singular values ofba.
we compute ba by minimizing eq.
, which gives
ba=xtxxt− <dig>
combine , , and , we find
m=the number of nonzero singular values ofz−l−cxxtxxt− <dig>
due to the existence of noise, we should allow small singular values to be considered as zero.
therefore, we can draw a plot with singular values of xtxxt− <dig> in descending order and set m to be k, if the first k singular values are large and significantly greater than the -th singular value.
based on the discussion above, in order to find optimal m, we can first use lasso to infer the initial value of c. then, using eq.
<dig>  we can infer the optimal m at this stage.
after that, we can optimize new c, and calculate new optimal m. we can repeat this procedure until m became stable or reach maximal number of iterations.
RESULTS
in this section, we perform extensive experimental study using both simulated and real eqtl datasets to evaluate the performance of our methods.
for comparison, we select several state-of-the-art eqtl methods, including two-graph guided multi-task lasso   <cit> , fast-lmm  <cit> , set-eqtl  <cit> , lors  <cit> , matrix eqtl  <cit>  and lasso  <cit> .
note that we did not compare with our previous work, gdl, in  <cit>  because it needs to incorporate many prior knowledge, that is not relevant to this work.
for all the methods, the tuning parameters are learned using cross validation.
the discussion of setting proper number of group-wise associations m is included in the additional file  <dig>  the shrinkage of the coefficients is also presented in the additional file  <dig>
simulated data
we use a similar setup for simulation study to that in  <cit> .
first,  <dig> snps are randomly selected from the yeast eqtl dataset  <cit> .
this gives birth to the matrix x.
<dig> gene expression profiles are generated by zj∗=βj∗x+Ξj∗+ej∗ , where ej∗∼n  is used to simulate the gaussian noise.
to simulate the effects of confounding factors, we use Ξj∗, drawn from n. in this paper, we set τ= <dig> .
Λ is given by fft.
here, f∈ℝh×j and fij∼n.
j denotes hidden factor number.
in this paper, we set j to  <dig>
in the left most of fig.
<dig>  we illustrate β. here, we set the association strength to  <dig>  totally, there exist four group-wise associations with different scales.
the diagonal line represents the individual signals in cis-regulation.
fig.
<dig> ground truth of matrix w and associations estimated by geqtl.
the x-axis represents snps and y-axis represents traits.
normalized absolute values of regression coefficients are used.
darker color implies stronger association.
number of group-wise associations m = 4
in fig.
<dig>  we report the associations inferred by geqtl.
recall that group-wise associations can be inferred from matrix a and b, and individual associations can be inferred from matrix c. it is obvious that geqtl can detect both group-wise and individual signals.
we use snr=varvar to denote the signal-to-noise ratio  <cit>  in the eqtl datasets.
here, we fix j= <dig> τ= <dig> .
the snr’s are controlled by using different ϕ’s.
using  <dig> simulated datasets with different snr’s, we compare the proposed methods with the selected methods.
because fast-lmm requires the input of genomic locations information , we will compare it on the real data set.
the results are averaged over  <dig> different simulated datasets.
ba+c is used to represent the association matrix in our method.
figure  <dig> shows the roc curve of tpr-fpr  for performance comparison.
typically, we care more about the tpr when the fpr is small because it is important to evaluate the performance of model when controlling the maximum tolerated fpr.
thus, in fig.
<dig>  the roc of interest for eqtl are generally shown in the range .
the corresponding areas under the tpr-fpr curve are shown in fig.
<dig>
fig.
<dig> the roc curve of fpr-tpr with different signal-to-noise ratios
fig.
<dig> the aucs curve
it can be seen that geqtl and geqtl + outperform all alternative methods by a large margin since they considers both individual and group-wise associations.
we also observe that geqtl-ridge is not as good as geqtl and geqtl +.
this is because geqtl-ridge does not provide a sparse solution for individual associations.
mtlasso2g is comparable to lors.
lors can correct the effects of the confounders, however, it is not able to detect group-wise mappings.
we also observe that by decoupling individual and group-wise associations, the proposed models  are more robust to noise than other methods.
yeast eqtl data
we also validated geqtl using the bench mark dataset–yeast  eqtl dataset.
the dataset contains  <dig> yeast segregants generated from a cross of two inbred strains  <cit> .
originally, it contains  <dig> gene epxressions and  <dig> snps.
snps with > <dig> % missing values in the remaining snps are imputed using the function fill.geno in r/qtl  <cit> .
the neighboring snps with the same genotype profiles are combined, resulting in  <dig> genotype profiles.
remove gene expression traits with missing values, we get  <dig> expression profiles.
cis- and trans- analysis
we follow the standard cis-enrichment analysis that is used in  <cit>  for evaluation.
moreover, we use the trans-enrichment with a similar strategy  <cit> .
genes regulated by transcription factors  are treated as trans-acting signals.
in table  <dig>  we report the pairwise comparison using cis- and trans- enrichment analysis.
we do not list geqtl separately from geqtl+, since geqtl+ is a faster version of geqtl.
in this table, the methods are sorted  in decreasing order of performance.
a p-value shows how significant a method on the left column outperforms a method in the top row in terms of cis and trans enrichments.
we observe that geqtl + has significantly better cis-enrichment scores than the other models.
for trans-enrichment, geqtl + is the best, and mtlasso2g comes in second, outperforming fast-lmm, set-eqtl, lors, matrix eqtl and lasso.
lors outperforms matrix eqtl and lasso for both cis- and trans-enrichment.
this is because lors considers confounding factors while matrix eqtl and lasso does not.
in total, these methods each detected about  <dig> associations according to non-zero w values.
we estimate fdr using  <dig> permutations as proposed in  <cit> .
with fdr ≤  <dig> , geqtl + obtains about  <dig> significant associations.
the plots of all identified significant associations for different methods are given in fig.
<dig>  obviously, we can see that c+b×a and c of geqtl + report weaker trans-regulatory bands while stronger cis-regulatory signals than other competitors.
fig.
<dig> significant associations reported on yeast eqtl dataset
gene ontology enrichment analysis on detected group-wise associations for yeast
we further evaluate the quality of detected groups of genes by measuring the correlations between the detected groups of genes and the go  categories  <cit> .
specifically, the go enrichment test is calculated by david  <cit> .
in this paper, gene sets reported by our algorithm with calibrated p-values less than  <dig>  are considered as significantly enriched.
since set-eqtl is the only previous approach capable of detecting group-wise association mapping, we compare the groups of genes detected by geqtl and those by set-eqtl.
for set-eqtl,  <dig> out of  <dig> gene sets are significantly enriched.
by contrast,  <dig> out of  <dig> gene sets reported by geqtl are significantly enriched.
this well illustrates that the effectiveness of geqtl to infer group-wise associations.
the number of snps in each group reported by geqtl and their genomic locations are shown in fig.
<dig>  we can clearly observe that snps in the same group are often physically close to each other.
this is reasonable because snps nearby usually jointly affect the expression level of a set of genes that achieves a specific cell function  <cit> .
fig.
<dig> genomic positions of snps in each snp group
reproducibility of eqtls between studies
to further evaluate the identified associations, we investigate the consistency of calls between two independent studies  <cit> .
we examine the reproducibility based on the following two criteria  <cit> :
reproducibility of detected snp-gene associations: let l <dig> and l <dig> be the sets of snp-gene associations detected in the two yeast datasets, respectively.
we can rank the associations according to the weights .
let l1t and l2t be the top t most significant associations from the two datasets.
the reproducibility is defined as |l1t⋂l2t|t.
reproducibility of trans regulatory hotspots: for each snp, we count the number of associated genes from the detected snp-gene associations.
we use this number as the regulatory degree of each snp.
for fast-lmm, snp-gene pairs with a q-value <  <dig>  are considered significant associations.
we also tried different cutoffs for fast-lmm , the results are similar.
snps with large regulatory degrees are often referred to as hotspots.
we sort snps in descending order of their regulatory degrees.
we denote the sorted snps lists as s <dig> and s <dig> for the two yeast datasets.
let s1t and s2t be the top t snps in the sorted snp lists.
the trans calling consistency of reported hotspots is denoted by |s1t⋂s2t|t.
in fig.
7a, we show the consistency of the top  <dig> associations between different studies.
in fig.
7b, we list the reproducibility of trans regulatory hotspots reported by different approaches.
overall, geqtl + yielded results with greater consistency all other methods.
this well illustrates the superiority of geqtl +.
fig.
<dig> reproducibility of eqtls between two independent yeast eqtl datasets
CONCLUSIONS
in literature, much efforts have been done on eqtl mapping.
traditional eqtl mapping approaches can not detect the group-wise associations between sets of snps and sets of genes.
to achieve that, we propose a fast approach, geqtl, to detect both individual and group-wise associations for eqtl mapping.
geqtl can also correct the effects of potential confounders.
we also introduce efficient algorithms to scale up the computation so that the algorithms are able to tackle large scale data sets.
additionally, the proposed model provides an effective strategy to automatically infer the proper number of group-wise associations.
we perform extensive experiments on both simulated datasets and yeast datasets to demonstrate the effectiveness and efficiency of the proposed method.
inferring individual and group-wise associations also helps us better explain the genetic basis of gene expression.
due to scalability issue, our model simply assume random errors between different genes are independent and have the same variance.
that is the reason why current model only identified a small number of group-wise associations.
our future work will further incorporate the relationships between genes by integrating gene co-expression network or protein-protein-interaction network.
data availability
the software is publicly available at http://www.cs.unc.edu/~weicheng/bioinformatics_code.zip.
additional file
additional file  <dig> sparse regression models for unraveling group and individual associations in eqtl mapping.
competing interests
the authors declare that they have no competing interests.
authors’ contributions
conceived and designed the experiments: wc.
performed the experiments: wc.
analyzed the data: wc ys.
contributed reagents/materials/analysis tools: wc.
wrote the paper: wc zx ww ys.
all authors have read and approved the final version of the paper.
this work is partially supported by nsf iis- <dig>  nih u01hg008488- <dig>  nih r01gm115833- <dig>  nsf career, nsf iis- <dig>  and nsf iis- <dig>

 expression quantitative trait loci mapping aims at identifying single nucleotide polymorphisms that influence the expression level of genes. it has been widely applied to analyze the genetic basis of gene expression and molecular mechanisms underlying complex traits. in a typical eqtl study, the association between each expression trait and each snp is assessed separately. this approach does not consider the interactions among snps and among genes. however, multiple snps may interact with each other and jointly influence the phenotypes. this assumption will inevitably miss complex cases where multiple genetic variants jointly affect the co-expressions of multiple genes. it has been observed in biological experiments that the joint effect of multiple snps to a phenotype may be non-additive, and genes from the same biological pathway are usually co-regulated by the same genetic basis. the biological process contains both individual effects and joint effects between snps and genes. a straightforward approach to detect associations between sets of snps and a gene expression level can be done using the standard gene set enrichment analysis. wu et al. further proposed the variance component models for snp set testing. braun et al. employed aggregation-based approaches to cluster snps. in, listgarten et al. further considered the potential confounding factors. however, there are two limitations for these approaches. first, these methods typically only consider snps from pre-defined pathways or gene ontology categories, which are far from being complete. second, these methods can only detect the mapping of snp set and a single gene expression level. to better elucidate the genetic basis of gene expression, it is a crucial challenge to understand how multiple modestly-associated snps interact to influence the a group of genes. in this paper, we refer to this kind of eqtl mapping to find associations between group of snps and group of gene expression levels as the group-wise eqtl mapping. an example is shown in fig. note that an ideal model should allow overlaps between snp sets and between gene sets, that is, a snp or gene may participate in multiple individual and group-wise associations. in literature, group-wise eqtl mapping has attracted increasing research interest recently. for example, xu et al. proposed a two-graph-guided multi-task lasso approach to infer group-wise eqtl mapping. however, it required the grouping information of both snps and genes available as prior knowledge, which may not be practical for many applications. besides, it is not able to correct the effects of confounding factors. fig. an illustration of individual and group-wise associations. ellipses represent the groups of snps and genes. blue arrows between snps and genes represent identified associations in this paper, we propose a novel method, geqtl, to automatically detect individual and group-wise associations in eqtl studies. it uses a two-layer feature selection strategy and adopts efficient optimization techniques, which make it suitable for large scale studies. moreover, geqtl can automatically infer the optimal number of group-wise associations. we perform extensive experiments on both simulated datasets and yeast datasets to demonstrate the effectiveness and efficiency of the proposed method. methods preliminaries important notations used in this paper are listed in table in this paper, for each sample, the data of snps and genes are denoted by column vectors. let x=t denote the k snps. here, xi∈{,2} denotes a random variable corresponding to the i-th snp. let z=t denote the n genes in the study. zj denotes a continuous random variable corresponding to the j-th gene expression. let x={xh|1≤h≤h}∈ℝk×h be the snp matrix. we use z={zh|1≤h≤h}∈ℝn×h to denote the matrix of gene expression levels. h denotes the number of samples in consideration. k n h m x z y x∈ℝk×h z∈ℝn×h a∈ℝm×k b∈ℝn×m c∈ℝn×k α,β,γ,ρ r∈ℝn×k bold term means vector or matrix while non-bold term means scalar the traditional linear regression model for association mapping between x and z is z=wx+μ+ε, where z is a linear function of x with coefficient matrix w, μ is an n× translation factor vector. and ε is the additive noise of gaussian distribution with zero-mean and variance γi, where γ is a scalar. that is, ε∼n. in association studies, sparsity is a reasonable assumption because only a small fraction of genetic variants are expected to be associated with a set of gene expression traits. this can be modeled as a feature selection problem. for example, the standard lasso can be used in association mapping, which applies ℓ penalty on w for sparsity. if both x and z are standardized, the objective function of lasso is formulated as minw||z−wx||f2+η||w|| where ||·||f denotes the frobenius norm, ||·|| is the ℓ1-norm. η is the empirical parameter for the ℓ penalty. w is the parameter matrix parameterizing the space of linear functions mapping from x to z. confounding factors, such as unobserved covariates, experimental artifacts and unknown environmental perturbations, may mask real signals and lead to spurious findings. lors uses a low-rank matrix l∈ℝn×h to account for the variations caused by hidden factors. the objective function of lors is minw,l||z−wx−l||f2+η||w||1+ρ||l||∗, where ||·||∗ is the nuclear norm. ρ is the regularization parameter to control the rank of l. l is a low-rank matrix assuming that there are only a small number of hidden factors influencing the gene expression levels. when we fix {w, we can optimize {l} by using singular value decomposition according to the following lemma. lemma suppose that matrix o has rank r. the solution to the optimization problem mins12||o−s||f2+λ||s||∗ is given by s^=hλ, where hλ=udλvt with dλ=diag, udvt is the singular value decomposition of o, d=diag, and +=max,0),. thus, for fixed w, the formula for updating l is l←hλ both lasso and lors do not consider the existence of group-wise associations. below, we will introduce the proposed model to infer both group-wise and individual associations for eqtl mapping. geqtl in geqtl, individual associations between snps and genes are modeled by following the lasso-based strategy. group-wise associations are inferred using a two-layer feature selection method. since multiple snps may have joint effect on a group of genes, and such effect may be accomplished through complex biological processes, we introduce latent variables to bridge sets of snps and sets of genes. specifically, we assume that there exist latent factors regulating the gene expression level, which serve as bridges between the snps and the genes. the latent variables are denoted by y=t. here, m ) is the total number of latent variables representing group-wise associations. the relationship between x and y can be represented as y=ax+ε where ε1∼n σ12im. a∈ℝm×k denotes the matrix of coefficients between x and y. σ12im denotes the variances of the additive noise. im is an identity matrix. here we drop the intercept terms because the input data x and z are normalized to zero mean and unit variance as preprocessing. similarly, the relationship between y and z can be represented as z=by+cx+ε where ε2∼n σ22in. b∈ℝn×m denotes the matrix of coefficients between y and z, c∈ℝn×k denotes the matrix of coefficients between x and z to encode the individual associations. note that eq. decouples the associations between snps and genes into two parts: one for individual associations represented as cx, and another for group-wise associations represented as by. next, we infer the group-wise associations by a two-layer feature selection strategy. we first remove the individual associations and denote z~=z−cx. thus z~ contains only group-wise effects. next let y=ax. thus y represents a low-rank transformation of the original snp matrix. each row of y represents a group of snps. from eq., we have the following multiple-input-multiple-output linear system z~=by+e, where e is a gaussian white-noise term. in eq. and, a and b should be sparse since a single gene is often influenced by a small number of snps and vice versa. therefore, the overall objective function is mina,b,c,lloss+ρ||l||∗+α||a||1+β||b||1+γ||c|| where α,β,γ,ρ are the regularization parameters, and the loss function is loss=||z−l−x||f here, we choose different penalties for a,b,c because the sparsities of different matrices are typically of different scales. optimization the optimization for l can be achieved by following a similar approach as in. to optimize a,b,c, many tools can be used to optimize the ℓ penalized objective function, e.g., the orthant-wise limited-memory quasi-newton algorithm. due to space limitation, we omit the details. in the next, we devise optimization techniques that can dramatically improve the computational efficiency of geqtl. boosting the computational efficiency given a large number of snps and gene expression traits, scalability of the algorithm is a crucial issue. we propose two improved models, geqtl + and geqtl-ridge, which optimize the search for significant individual associations, which is the main computational bottleneck of the algorithm. geqtl + in a typical eqtl study, we usually have m≪min. thus, the bottleneck of the algorithm is to optimize c. our strategy is to confine the space of c. the intuition is that we only permit a small fraction of elements in c to be nonzero. it has been shown that if z and x are standardized with zero mean and unit sum of squares, then r=abs is equal to the gene-snp correlations |). since for many test statistics, e.g., t, f, r and lr, for the simple linear regression problem can be expressed as functions of the sample correlation rgs, e.g., r2=r and t=rn−21−r we can find a threshold according to the required p-value, such that test statistics exceeding the threshold are significant at the required significance level. the test statistics for every gene-snp pair in r are compared with the threshold, and only those elements whose r are greater than the threshold are optimized. we denote r∈ℝn×k as the indicator matrix indicating which elements in c can be nonzero. geqtl-ridge when n and k are extremely large, optimizing c may still be time-consuming, since it may take many iterations to converge with the ℓ constraint. next, we introduce geqtl-ridge, which further improves the time efficiency with slight decrease in accuracy. the key idea is to use ridge regression for individual associations so that we can get a closed form solution for c. the objective function is shown in the following. mina,b,c,lloss+ρ||l||∗+α||a||1+β||b||1+γ||c|| s.t.i,jisnozeroonlyifi,jis theorem the solution of c in eq. is ci←dixtpipitxxtpi+γik−1pit, where ci=i,:,di=i,:, d=z−l−bax, and pi is defined as in formula. the proof of the theorem is in the following section. proof of theorem 1 proof. recall that any ridge regression problem mina||b−aq||22+||aΓ|| where a is a row vector and q has linearly independent rows, has the following solution a=bqt− note that loss=||d−cx||f2=∑i=1n||di−cix|| where d=z−l−bax, ci=i,: and di=i,:. we have mincloss=∑i=1nminci||di−cix|| taking into account that j can be nonzero only if i,j is we introduce pi, where pi has k rows and li=∑j=1ki,j columns. and s,t= ifi,sisthet-th1ini,:; otherwise. then ci=cipipit, ||di−cix||22+γ||ci||22=||di−pitx||22+γ||cipi|| and minci||di−cix||22+γ||ci|| s.t.jisnozeroonlyifi,jis is solved by ci=pit=dixtpipitxxtpi+γik−1pit. therefore, mincloss+γ||c|| s.t.i,jisnozeroonlyifi,jis is solved by c=c1t,…,cntt, which leads to the update formula given in eq.. determining the number of hidden variables in eq., we use ba+c to formulate the overall associations between snps and expression traits. two group-wise associations will not share the same group of snps, since otherwise these two group-wise associations can be combined into one. therefore, every group-wise association should be unique and irreplaceable. hence, following two conditions should be satisfied a has linearly independent rows. since m≪k, this condition is equivalent to that a has full rank; b has linearly independent columns. since m≪n, this condition is equivalent to that b has full rank. when these two conditions are met, we have m=rank=rank=rank. the last equality holds because both a and b have full rank. we have the following observation. the singular value decomposition of ba has the form ba=uΣvt, where u and v are unitary matrices, and Σ is a rectangular diagonal matrix with non-negative real numbers on the diagonal, which corresponds to singular values of ba. since u and v are unitary and hence have full rank, we have rank=rankuΣvt=rank=the number of nonzero singular values ofba. we compute ba by minimizing eq., which gives ba=xtxxt− combine,, and, we find m=the number of nonzero singular values ofz−l−cxxtxxt− due to the existence of noise, we should allow small singular values to be considered as zero. therefore, we can draw a plot with singular values of xtxxt− in descending order and set m to be k, if the first k singular values are large and significantly greater than the -th singular value. based on the discussion above, in order to find optimal m, we can first use lasso to infer the initial value of c. then, using eq. we can infer the optimal m at this stage. after that, we can optimize new c, and calculate new optimal m. we can repeat this procedure until m became stable or reach maximal number of iterations.  in this section, we perform extensive experimental study using both simulated and real eqtl datasets to evaluate the performance of our methods. for comparison, we select several state-of-the-art eqtl methods, including two-graph guided multi-task lasso, fast-lmm, set-eqtl, lors, matrix eqtl and lasso. note that we did not compare with our previous work, gdl, in because it needs to incorporate many prior knowledge, that is not relevant to this work. for all the methods, the tuning parameters are learned using cross validation. the discussion of setting proper number of group-wise associations m is included in the additional file the shrinkage of the coefficients is also presented in the additional file simulated data we use a similar setup for simulation study to that in. first, snps are randomly selected from the yeast eqtl dataset. this gives birth to the matrix x. gene expression profiles are generated by zj∗=βj∗x+Ξj∗+ej∗, where ej∗∼n is used to simulate the gaussian noise. to simulate the effects of confounding factors, we use Ξj∗, drawn from n. in this paper, we set τ=. Λ is given by fft. here, f∈ℝh×j and fij∼n. j denotes hidden factor number. in this paper, we set j to in the left most of fig. we illustrate β. here, we set the association strength to totally, there exist four group-wise associations with different scales. the diagonal line represents the individual signals in cis-regulation. fig. ground truth of matrix w and associations estimated by geqtl. the x-axis represents snps and y-axis represents traits. normalized absolute values of regression coefficients are used. darker color implies stronger association. number of group-wise associations m = 4 in fig. we report the associations inferred by geqtl. recall that group-wise associations can be inferred from matrix a and b, and individual associations can be inferred from matrix c. it is obvious that geqtl can detect both group-wise and individual signals. we use snr=varvar to denote the signal-to-noise ratio in the eqtl datasets. here, we fix j= τ=. the snr’s are controlled by using different ϕ’s. using simulated datasets with different snr’s, we compare the proposed methods with the selected methods. because fast-lmm requires the input of genomic locations information, we will compare it on the real data set. the results are averaged over different simulated datasets. ba+c is used to represent the association matrix in our method. figure shows the roc curve of tpr-fpr for performance comparison. typically, we care more about the tpr when the fpr is small because it is important to evaluate the performance of model when controlling the maximum tolerated fpr. thus, in fig. the roc of interest for eqtl are generally shown in the range. the corresponding areas under the tpr-fpr curve are shown in fig. fig. the roc curve of fpr-tpr with different signal-to-noise ratios fig. the aucs curve it can be seen that geqtl and geqtl + outperform all alternative methods by a large margin since they considers both individual and group-wise associations. we also observe that geqtl-ridge is not as good as geqtl and geqtl +. this is because geqtl-ridge does not provide a sparse solution for individual associations. mtlasso2g is comparable to lors. lors can correct the effects of the confounders, however, it is not able to detect group-wise mappings. we also observe that by decoupling individual and group-wise associations, the proposed models are more robust to noise than other methods. yeast eqtl data we also validated geqtl using the bench mark dataset–yeast eqtl dataset. the dataset contains yeast segregants generated from a cross of two inbred strains. originally, it contains gene epxressions and snps. snps with > % missing values in the remaining snps are imputed using the function fill.geno in r/qtl. the neighboring snps with the same genotype profiles are combined, resulting in genotype profiles. remove gene expression traits with missing values, we get expression profiles. cis- and trans- analysis we follow the standard cis-enrichment analysis that is used in for evaluation. moreover, we use the trans-enrichment with a similar strategy. genes regulated by transcription factors are treated as trans-acting signals. in table we report the pairwise comparison using cis- and trans- enrichment analysis. we do not list geqtl separately from geqtl+, since geqtl+ is a faster version of geqtl. in this table, the methods are sorted in decreasing order of performance. a p-value shows how significant a method on the left column outperforms a method in the top row in terms of cis and trans enrichments. we observe that geqtl + has significantly better cis-enrichment scores than the other models. for trans-enrichment, geqtl + is the best, and mtlasso2g comes in second, outperforming fast-lmm, set-eqtl, lors, matrix eqtl and lasso. lors outperforms matrix eqtl and lasso for both cis- and trans-enrichment. this is because lors considers confounding factors while matrix eqtl and lasso does not. in total, these methods each detected about associations according to non-zero w values. we estimate fdr using permutations as proposed in. with fdr ≤, geqtl + obtains about significant associations. the plots of all identified significant associations for different methods are given in fig. obviously, we can see that c+b×a and c of geqtl + report weaker trans-regulatory bands while stronger cis-regulatory signals than other competitors. fig. significant associations reported on yeast eqtl dataset gene ontology enrichment analysis on detected group-wise associations for yeast we further evaluate the quality of detected groups of genes by measuring the correlations between the detected groups of genes and the go categories. specifically, the go enrichment test is calculated by david. in this paper, gene sets reported by our algorithm with calibrated p-values less than are considered as significantly enriched. since set-eqtl is the only previous approach capable of detecting group-wise association mapping, we compare the groups of genes detected by geqtl and those by set-eqtl. for set-eqtl, out of gene sets are significantly enriched. by contrast, out of gene sets reported by geqtl are significantly enriched. this well illustrates that the effectiveness of geqtl to infer group-wise associations. the number of snps in each group reported by geqtl and their genomic locations are shown in fig. we can clearly observe that snps in the same group are often physically close to each other. this is reasonable because snps nearby usually jointly affect the expression level of a set of genes that achieves a specific cell function. fig. genomic positions of snps in each snp group reproducibility of eqtls between studies to further evaluate the identified associations, we investigate the consistency of calls between two independent studies. we examine the reproducibility based on the following two criteria: reproducibility of detected snp-gene associations: let l and l be the sets of snp-gene associations detected in the two yeast datasets, respectively. we can rank the associations according to the weights. let l1t and l2t be the top t most significant associations from the two datasets. the reproducibility is defined as |l1t⋂l2t|t. reproducibility of trans regulatory hotspots: for each snp, we count the number of associated genes from the detected snp-gene associations. we use this number as the regulatory degree of each snp. for fast-lmm, snp-gene pairs with a q-value < are considered significant associations. we also tried different cutoffs for fast-lmm, the results are similar. snps with large regulatory degrees are often referred to as hotspots. we sort snps in descending order of their regulatory degrees. we denote the sorted snps lists as s and s for the two yeast datasets. let s1t and s2t be the top t snps in the sorted snp lists. the trans calling consistency of reported hotspots is denoted by |s1t⋂s2t|t. in fig. 7a, we show the consistency of the top associations between different studies. in fig. 7b, we list the reproducibility of trans regulatory hotspots reported by different approaches. overall, geqtl + yielded results with greater consistency all other methods. this well illustrates the superiority of geqtl +. fig. reproducibility of eqtls between two independent yeast eqtl datasets  in literature, much efforts have been done on eqtl mapping. traditional eqtl mapping approaches can not detect the group-wise associations between sets of snps and sets of genes. to achieve that, we propose a fast approach, geqtl, to detect both individual and group-wise associations for eqtl mapping. geqtl can also correct the effects of potential confounders. we also introduce efficient algorithms to scale up the computation so that the algorithms are able to tackle large scale data sets. additionally, the proposed model provides an effective strategy to automatically infer the proper number of group-wise associations. we perform extensive experiments on both simulated datasets and yeast datasets to demonstrate the effectiveness and efficiency of the proposed method. inferring individual and group-wise associations also helps us better explain the genetic basis of gene expression. due to scalability issue, our model simply assume random errors between different genes are independent and have the same variance. that is the reason why current model only identified a small number of group-wise associations. our future work will further incorporate the relationships between genes by integrating gene co-expression network or protein-protein-interaction network. data availability the software is publicly available at http://www.cs.unc.edu/~weicheng/bioinformatics_code.zip. additional file additional file sparse regression models for unraveling group and individual associations in eqtl mapping. competing interests the authors declare that they have no competing interests. authors’ contributions conceived and designed the experiments: wc. performed the experiments: wc. analyzed the data: wc ys. contributed reagents/materials/analysis tools: wc. wrote the paper: wc zx ww ys. all authors have read and approved the final version of the paper. this work is partially supported by nsf iis- nih u01hg008488- nih r01gm115833- nsf career, nsf iis- and nsf iis- 
a major drawback of this approach is that it cannot model the joint effect of a set of snps on a set of genes, which may correspond to biological pathways. geqtl can also correct the effects of potential confounders. as a promising tool for dissecting the genetic basis of common diseases, expression quantitative trait loci study has attracted increasing research interest. the results show that geqtl can effectively detect both individual and group-wise signals and outperforms the state-of-the-arts by a large margin. moreover, our method can automatically infer the proper number of group-wise associations. this paper well illustrates that decoupling individual and group-wise associations for association mapping is able to improve eqtl mapping accuracy, and inferring individual and group-wise associations. our method employs computationally efficient technique, thus it is able to fulfill large scale studies. to alleviate this limitation, in this paper, we propose geqtl, a sparse regression method that can detect both group-wise and individual associations between snps and expression traits. traditional eqtl methods focus on testing the associations between individual single-nucleotide polymorphisms and gene expression traits. we perform extensive experiments on both simulated datasets and yeast datasets to demonstrate the effectiveness and efficiency of the proposed method.
 as a promising tool for dissecting the genetic basis of common diseases, expression quantitative trait loci study has attracted increasing research interest. traditional eqtl methods focus on testing the associations between individual single-nucleotide polymorphisms and gene expression traits. a major drawback of this approach is that it cannot model the joint effect of a set of snps on a set of genes, which may correspond to biological pathways.  to alleviate this limitation, in this paper, we propose geqtl, a sparse regression method that can detect both group-wise and individual associations between snps and expression traits. geqtl can also correct the effects of potential confounders. our method employs computationally efficient technique, thus it is able to fulfill large scale studies. moreover, our method can automatically infer the proper number of group-wise associations. we perform extensive experiments on both simulated datasets and yeast datasets to demonstrate the effectiveness and efficiency of the proposed method. the results show that geqtl can effectively detect both individual and group-wise signals and outperforms the state-of-the-arts by a large margin.  this paper well illustrates that decoupling individual and group-wise associations for association mapping is able to improve eqtl mapping accuracy, and inferring individual and group-wise associations. electronic supplementary material the online version of this article contains supplementary material, which is available to authorized users. keywords eqtl mappinggroup-wise associationcomputation efficiencyissue-copyright-statement© the author 2016 