Lippert C, Listgarten J, Liu Y, et al. FaST linear mixed models for genome-wide association studies. Nature Methods, 2011, 8(10): 833–835. DOI: 10.1038/nmeth.1681.

我们描述了分解的光谱变换线性混合模型（FaST-LMM），这是一种全基因组关联研究（GWAS）的算法，其在运行时和记忆使用中与群组大小线性比例。在Wellcome Trust的15,000名个人数据中，FaST-LMM比当前的高效算法快了一个数量级。我们的算法可以在短短几个小时内分析120,000个人的数据，而目前的算法甚至可以在20,000个人的数据上失败（http://mscompbio.codeplex.com/）。

全基因组关联研究（GWAS）中群体结构，家庭结构和隐秘相关性的混淆问题受到广泛赞赏1。用于校正这些混杂因素的统计方法包括线性混合模型（LMM）2？0，基因组控制，基于家庭的关联测试，结构化关联和Eigenstrat7。与其他方法相比，LMM可以同时捕获所有这些混杂因素，而不知道哪些存在并且不需要将它们分开7。不幸的是，相对于更简单的模型，LMM在计算上是昂贵的。特别是，这些模型所需的运行时间和内存占用量分别作为群组大小的立方体和平方（数据集中表示的个体数量）进行缩放。这个瓶颈意味着LMM在当前或即将可用的大型数据集上运行缓慢或根本不运行。
粗略地说，LMM通过使用遗传相似性的方法来解决混杂因素，以捕捉成对的个体具有共同的致病等位基因的概率。这些措施包括基于血统10,11和实现的关系矩阵（RRM）9,10,12的身份，并且已经用少量标记样本（200？000标记）2,4进行了估计。在这里，我们利用这种采样使LMM分析适用于极大的数据集，引入LMM的重构，称为因子光谱变换LMM（FaST-LMM）。我们表明，提供（i）用于估计遗传相似性的单核苷酸多态性（SNP）的数量小于群组大小（无论要测试多少个SNP）和（ii）RRM用于确定这些相似性，然后FaSTLMM产生与标准LMM完全相同的结果，但运行时间和内存占用量仅在群组大小中呈线性。因此，FaST-LMM显着增加了可用LMM分析的数据集的大小，并且还使得当前可行的分析更快。
我们的FaST-LMM算法建立在以下观点的基础上：LMM的最大似然（或限制最大似然（REML））可以仅作为单个参数的函数重写，即遗传方差与残差方差的比值3， 13。因此，识别最大类似（或REML）参数仅仅是优化问题。算法“有效混合模型关联”（EMMA）3通过巧妙地使用频谱分解来加速对任何值的对数似然性的评估，其通常是群组大小中的立方。【EMMA的缺点】然而，该方法需要对每个测试的SNP进行新的频谱分解（立方操作）。算法“EMMA加速”（称为EMMAX）和“先前确定的群体参数”（称为P3D）4,5通过假设每个测试的SNP的方差参数相同来提供额外的计算节省，从而消除了每个SNP的昂贵的立方计算。
与这些方法相比，FaST-LMM仅需要单个频谱分解来测试所有SNP，即使不假设SNP中的方差参数相同，并且提供了内存占用和额外加速的减少。我们的方法背后的关键见解是，遗传相似性矩阵的谱分解使得转化（旋转）表型，待测试的SNP和协变量成为可能，使得旋转的数据变得不相关。然后，这些数据适合于使用线性回归模型进行分析，该模型在群组大小中具有线性的运行时间和内存占用。
通常，所需旋转矩阵中的条目数在群组大小中是二次的，并且通过谱分解计算该矩阵在群组大小中具有立方运行时间。然而，当用于构建遗传相似性矩阵的SNP的数量小于群组大小时，执行旋转所需的矩阵中的条目的数量在群组大小中是线性的（并且SNP的数量是线性的），并且计算矩阵所需的时间在群组大小中是线性的（并且SNP的数量是二次的）。直观地，可以实现这些节省，因为用于构建相似性矩阵的SNP所跨越的空间的内在维度永远不会高于这种SNP的数量和群组大小中的较小者。因此，我们总是可以在较小的空间中执行操作而不会丢失任何信息，并且计算仍然是精确的。这个基本思想以前已被利用[8,14]，但是当应用于GWAS时，每个SNP需要昂贵的计算，这使得这些方法的效率远低于FaST-LMM。
为了实现我们的线性运行时间和内存占用，遗传相似性矩阵的频谱分解必须是可计算的，而无需显式计算矩阵本身。 RRM与其他矩阵一样具有此属性（补充说明1）。在线方法中提供了更正式的FaST-LMM描述。
我们比较了FaST-LMM和EMMAX算法的非并行化实现的内存占用和运行时间（图1）。 （在“通过关联，进化和联系的特征分析”（TASSEL）包中，EMMAX实现在运行时和内存使用方面的效率不低于P3D）。在比较中，我们使用Genetic Analysis Workshop 14数据（GAW14数据;在线方法）构建具有相同SNP数量（~8,000个SNP）的合成数据集，并且大约是群组大小的1,5,10,20,50和100倍原始数据。最大的此类数据集包含123,800个人的数据。我们测试了所有SNP并将它们全部用于估计遗传相似性。 EMMAX不会在20上运行？ 50？或100？数据集，因为存储大型矩阵所需的内存超过了32千兆字节（GB）。相比之下，FaST-LMM不需要这些矩阵（因为它绕过它们的计算，只是隐式地使用它们），在最大的数据集上使用28 GB的内存完成了分析。当该大小超过用于构建RRM的8,000个SNP时，运行时结果突出显示计算对群组大小的线性依赖性。此外，即使我们重新估计每个测试的方差参数，使用我们的方法计算仍然是实用的。
已知使用由一组SNP构建的RRM没有固定效应的LMM等同于SNP在表型上的线性回归，其中权重在具有相同方差的独立正态分布上积分9,10。在该视图中，用于构建RRM的采样SNP可以被视为省略回归量并且因此是近似值。尽管如此，SNP可以在整个基因组中均匀采样，因此连锁不平衡会减少采样的影响。为了研究这个问题，我们比较了有关克罗恩病的Wellcome Trust Case Control Consortium（WTCCC）数据的有和没有抽样的关联P值。具体而言，我们测试了染色体1上的所有SNP，同时使用来自除该染色体以外的所有不同大小的SNP组（完整组（_{340,000个SNP）和均匀分布的}8,000个SNP和~4,000个SNP的样品）来计算RRM（补充说明） 2）。完整和采样集合产生的P值相似（图2）。使用全基因组显着性阈值5？10-7，不同的SNP组导致几乎相同的显着性调用。当我们使用完整集时，该算法称为24个SNP显着，并且8,000-SNP和4,000-SNP分析仅标记了一个额外的SNP并且没有遗漏任何一个。相比之下，阿米蒂奇趋势测试（ATT）标记了7个额外的SNP，并且没有任何错误。此外，完整的8,000-SNP和4,000SNP分析（分别为1.132,1.173和1.203）的统计数据相似，而ATT则为= 1.333。我们在补充图1中显示了相应的分位数 - 分位数（QQ）图。最后，使用这些SNP样本构建遗传相似性，FaST-LMM比EMMAX快一个数量级：4,000-SNP的23分钟和53分钟以及8,000-SNP -SNP FaST-LMM分析与相应EMMAX分析的260分钟和290分钟进行比较。
关于选择SNP以估计遗传相似性，均匀分布的取样的替代方案是选择与表型强相关的SNP。在WTCCC数据上，我们发现根据ATT使用200个最强相关的SNP至少与8,000-SNP样本一样，进行与完整集合的分析相同的重要调用并产生1.135的统计量。
我们设想了未来的几个方向。一种是将FaST-LMM应用于多变量分析。一旦将旋转应用于SNP，协变量和表型，那么多变量加性分析（包括使用正则化估计方法的那些）可以在群组大小中线性地实现，而没有额外的光谱分解或旋转。此外，通过仅使用频谱分解的顶部特征向量来旋转数据（具有最大特征值的那些），可以额外地减少FaST-LMM的时间复杂度。在WTCCC数据上，使用少于200个特征向量产生的单变量P值与从数千个特征向量获得的值相当。当多个人具有相同的基因型或LMM被压缩时（如压缩混合线性模型4）（补充注释1），FaST-LMM可以更有效。最后，遗传标记与基因表达之间的关联（“表达数量性状基因座”分析）的鉴定可以被认为是GWAS15的多种应用，使得我们的FaST-LMM方法适用于这种分析。