跳到主要内容

GPrimer:一个基于gpu的快速管道,用于qPCR实验引物设计

摘要

背景

有效的高质量引物的设计对于QPCR实验至关重要。MrPrimer是一种强大的管道,基于MapReduce,将底漆设计与偏移序列上的目标序列和同源性测试相结合。它需要整个序列DB作为输入,返回DB中存在的所有可行性和有效的引物对。由于MrPrimer设计的引物在QPCR分析中的有效性,它已被广泛用于开发许多在线设计工具和建立底漆数据库。然而,MrPrimer的计算速度太慢,无法处理呈指数增长的序列DBS的尺寸,因此必须得到改善。

结果

我们为primer设计开发了一个快速的基于gpu的管道(GPrimer),它接受与MRPrimer相同的输入并返回相同的输出。MRPrimer总共由七个MapReduce步骤组成,其中有两个步骤非常耗时。GPrimer利用gpu的计算能力显著提高了这两个步骤的速度。特别地,它设计了数据结构,用于GPU中合并内存访问和GPU线程之间的工作负载平衡,并以流方式在主存和GPU内存之间复制数据结构。对于human RefSeq DB,与运行在6台机器集群上的MRPrimer相比,GPrimer在4个gpu的单机上实现了整个步骤57倍的加速,在最耗时的步骤上实现了557倍的加速。

结论

我们提出了一种基于GPU的管道,用于引物设计,其将整个序列DB作为输入,一次返回DB中存在的所有可行性和有效的引物对,而无需使用炖工具即可额外的步骤。软件可用https://github.com/qhtjrmin/gprimer.git.

背景

定量聚合酶链式反应(QPCR)(也称为实时PCR)是一种标准技术,广泛用于实时检测特异性DNA分子的大规模扩增。其应用包括病毒检测[1]、转基因生物检测[2、病原体发现[3.],并验证感兴趣基因表达的变化[4]。为了在qPCR实验中获得最好的结果,设计高质量的引物是最重要的。MRPRIMER [5]是一个基于mapreduce的强大管道,结合了目标序列的引物设计和脱靶序列的同源性测试。一般来说,高质量的引物不仅要满足单对过滤约束(如引物长度、熔融温度、GC含量等)才能正确扩增目标序列,而且要通过同源性检测才能不扩增脱靶序列。与使用BLAST-like工具将同源性测试作为额外步骤的传统方法不同,MRPrimer将整个序列DB和过滤约束作为输入,返回DB中存在的所有可行和有效的引物对,而无需使用BLAST-like工具进行额外步骤。MRPrimer与Primer3Plus等传统的引物设计工具相比,能够一次性找到DB中存在的所有可行有效的引物对[6primerblast [7],发现仅在单个序列中存在引物对。由于MrPrimer在QPCR分析中设计的引物的有效性,许多工具包括MRPRIMERW [8],mrprimerv [1]和mrprimerw2 [9]已基于MrPrimer开发并广泛使用。MRPRIMERW是一个基于Web的设计工具,允许用户轻松获得最佳的素物对和Taqman探针,用于批量QPCR实验,这些实验应该满足一组严格和均匀的约束以及通过同源性测试。MRPRIMERV是一种管道,可以通过将病毒序列DB和宿主(例如,人,骆驼)序列DB作为输入来构建1818个RNA病毒的引物数据库。MRPRIMERW2是一种增强的基于Web的设计工具,支持外显子跨越设计,避免SNP站点,输入Fasta序列和多目标设计。

尽管MRPRimer管道用作上述底漆设计工具的核心发动机,但它具有主要缺点,即其计算速度太慢以处理大规模序列DBS。MrPrimer是一个基于MapReduce的管道,也有许多其他基于MapReduce的管道,用于序列数据分析,包括CloudBurst [10.],gatk [11.], DistMap [12.], MegaSeq [13.],卤莽[14.], Halvade-RNA [15.],铁路RNA [16.狂欢[17.], MEC [18.]和Kch [19.]。最初,MRPrimer被提议基于运行在机器集群上的MapReduce框架,用于快速和可伸缩的数据处理。然而,随着测序技术的进步,序列db的大小呈指数级增长,MRPrimer可能需要很长时间才能从序列db中设计出所有引物对。例如,在MRPrimerV的研究中[1[MrPrimer甚至需要超过21,684个人基因序列的两周以上的超级计算机(第500六年六月,2016年6月的第500次超级计算机的排名第454次)。

为了解决MRPrimer计算速度慢的问题,我们提出了一个在单机上运行的基于gpu的管道来进行primer设计,称为gprimer.,它采用相同的输入,并返回MRPrimer的相同输出。

MRPrimer总共由7个MapReduce步骤组成,其中2个步骤计算量大,非常耗时。GPrimer利用gpu的计算能力显著提高了这两个步骤的速度。使用gpu处理剩下的步骤可能会降低性能,因为主内存和gpu之间的数据通信开销,因此,GPrimer只使用cpu处理这些步骤。为了利用GPU, GPrimer设计了两种数据结构(1)合并GPU中的内存访问和(2)GPU线程之间的工作负载平衡,以及(3)以流方式在主存和GPU内存之间复制数据结构,以隐藏数据通信开销。对于human RefSeq DB,与运行在6台机器集群上的MRPrimer相比,GPrimer在4个gpu的单机上实现了整个步骤57倍的加速,在最耗时的步骤上实现了557倍的加速。序列数据分析有很多基于gpu的方法,包括GPU-BLAST [20.],g-blastn [21.],h-blast [22.], SOAP3-dp [23.], sBWT [24.],gcup [25.],arioc [26.], YAMDA [27.]和nvidia parabricks [28.]。但是,据我们所知,目前还没有基于gpu的管道(或方法)用于入门设计,而GPrimer是第一个。

在本文中,我们简要介绍了MrPrimer,并概述了我们的GPRIMER关于如何改善MRPRIMER。然后,我们介绍了有关算法和数据结构的详细信息,以利用GPU的计算功率为两个耗时的步骤。我们评估了Gprimer的表现与MrPrimer相比,并对GPRIMER进行了缩小分析进行了一些实验。最后,我们得出结论。

回顾MRPrimer

MRPRIMER [5]是一个基于mapreduce的[29.七个步骤组成的管道(图。1一种)。它需要一个序列数据库和一组过滤约束作为输入,然后,在七个步骤之后,返回在DB中存在的所有可行性和有效的引物对。

图1
图1

MrPrimer和Gprimer的管道

步骤1(候选引物生成)作为候选引物提取在每个序列的最小长度和最大长度之间的所有可能的局部序列。长度由用户(例如,19-23 BP)指定为输入。此步骤还将其反向互补引物提取,同时用符号'*'标记它们。在该步骤中产生的候选引物不仅用于步骤2(即,其他单滤波),还用于步骤3和4(即,近似串匹配)。因此,此步骤刚刚生成所有可能的子句,没有其他单个过滤。步骤2(单滤波)将单滤波约束应用于从步骤1传递的每个引物,并过滤出违反任何过滤约束的引物。约束包括熔化温度,GC含量,自互补,3'末端自互补,连续的残留物和Gibbs自由能,其被用户视为输入。Step 3 (5’ cross-hybridization filtering) eliminates a candidate primer that is the same as any subsequence of an off-target sequence at the 3’ end and has only a few mismatches (up to four mismatches) at the 5’ end, and so, might cross-hybridize with the off-target sequence due to the high similarity between them, especially at the 3’ end.

步骤4(通用交叉杂交滤波)消除了与偏移序列的任何子序列类似的候选引物。此步骤需要两个底漆,C1(步骤1的输出)和C3(步骤3的输出)。我们表示两个引物之间的错配残留物的数量k。为了更高效的计算,这个步骤将每个primer分成一组更小的不相交的片段(称为种子)。根据[30.,31.), (32.),是长度的引物\(| \ textit {p} | \)最多k不匹配必须包含至少至少匹配的种子(\lfloor |P| / (k+1) \rfloor\)残留物(1,5,8]。所有引物都来自C1C3通过MapReduce的搭扣步骤收集具有常见种子,并检查一对引物是否相同。除外kMapReduce减少步骤中的残留物。在步骤4之后,仍然可能是违反一般交叉杂交滤波约束的假阳性引物。这是由于MapReduce的分布式计算导致的。为了完全过滤滤出这种引物,步骤5(重复除去)在引物方面重新排列步骤4的结果,并消除在任何种子方面不通过步骤4的引物。在增加的同时重复执行一系列步骤4和5k从1到最大失配残基数(即,#maxmismatch.),通常设置为2 [1,5,8]。

步骤6(成对过滤)将步骤5的结果重新排列为一组引物,其中每组由从同一组输入序列中提取的引物组成。然后,将每组引物分为正向引物和反向引物两组,使用步骤1中所述的标记,并在它们之间进行自连接,对每对引物应用成对过滤约束。约束条件包括长度差、熔化温度差、产品尺寸、对互补、3 '端对互补,用户指定为输入。从步骤6传递的引物对可能不是同等有效,即使他们满足所有给定的约束条件,并通过同源性测试。因此,第7步(排名)通过计算每个引物对的惩罚分数来确定它们的排名。罚分的计算采用Primer3Plus的方法[6]。

实现

概述GPrimer

GPRimer旨在使用MRPRimer执行相同的任务,因此使用MrPrimer返回相同的结果。但是,与依赖于分布式计算的MrPrimer不同,GPRimer利用GPU计算来处理引物设计所需的大规模计算。基本上,MrPrimer通过MapReduce的Map和Shuffle步骤进行了一组具有相同密钥的值,并在MapReduce的reduce步骤中对该组值执行某个函数,这是由许多具有它们自己的主要进程完成的memory spaces (i.e., heaps). In contrast, GPrimer groups the set of values using hash maps and performs the function using a lot of CPU or GPU threads within the same main memory space.

GPRIMER总共执行如图1中的五个步骤。1B,其中GPRIMER的步骤4对应于MRPRimer的步骤4和5,并且GPRimer的步骤5对应于MRPRimer的步骤6和7。自从gprimer.runs in the same memory space, Step 5 of MRPrimer for removing duplicates is not necessary, and also, Step 7 of MRPrimer (i.e., scoring and output formatting) can be performed together with Step 6 of MRPrimer (i.e., pair filtering) as a single step (i.e., Step 5) in GPrimer. Since the general cross-hybridization filtering and pair filtering are the most time-consuming steps, GPrimer performs the Steps 4 and 5 using GPU threads and the remaining Steps 1, 2 and 3 using CPU threads. Performing the Steps 1, 2 and 3 using GPU threads does not improve the performance much due to the overhead of copying data back and forth between main memory and GPU memory.

步骤1-3:使用CPU线程构建哈希贴图和处理

步骤1从候选引物中提取来自序列DB的所有可能的子序列,因为MrPrimer确实。我们表示步骤1的输出C1,步骤2的输出为C2, 等等。数字2A显示了一个例子C1, 在哪里P是一个引物,sid是序列的idP发生和发生pos这个位置P发生在顺序中sid。每一行C1只是一个级联P,sid, 和pos。符号“+”是一个连接操作,在本文中我们只使用字符“+”进行连接操作。数字2A也显示了一个例子C1', 哪一个P是引物,又是什么sidset.是序列id的集合在哪里P发生。使用另一个字符' - '连接的ID集。C1'C1的一组行作为步骤1的输出C1拥有相同的P和删除posC1用于输入步骤2的输入C1'用于交叉杂交滤波的步骤3和4的输入。

图2
figure2

步骤1和哈希图的输出示例。一个步骤1的输出示例。b在GPrimer中使用的哈希映射示例

步骤2对每个候选底漆应用六个过滤约束C1。对于满足过滤限制的候选底漆,我们构建了两个哈希映射,Primerh.左撇子。数字2B显示了两个哈希图的示例。前哈希地图,Primerh.有一个底漆P作为一个关键和一对sidset.在哪里P发生和有效的作为一个值,在哪里有效的表示是否P有效或没有,所有有效的价值Primerh.被初始化为1(即,真的)。该散列映射将在步骤3和步骤4中使用。在每一步,有效的未通过的底漆变为0.后者哈希图,左撇子有一个引物的后缀(即,后缀)作为钥匙和一组引物(即,pset.),后缀以值的形式发生。这个哈希映射只在步骤3中使用。另外两个散列映射,行集的C1通过步骤2存储为C2,在步骤4中使用。

步骤3过滤掉具有共同后缀但不同的候选引物sidset.和其他引物一起。它可以通过执行二进制连接之间C1'Primerh., 在哪里C1'包含DB中的所有可能的子项。详细地,我们通过查找哈希映射来执行二进制加入左撇子Primerh.在阅读每一行时C1'。例如,我们假设我们已经读了一行GCT + 3.C1'在图中。2。我们也假设没有引物GCT.Primerh.左撇子因为它在步骤2中被过滤掉了。引物有后缀CT等等,我们查找后缀左撇子找到一组引物{* tct.}。通过查阅引物* tct.Primerh.,我们发现底漆有4 - 5作为sidset.,这与...不同sidset.GCT.,也就是说,3。这意味着引物* tct.可能不仅放大序列\(\ {4,5 \} \)而且还有湿法实验中的序列3。因此,我们设置了有效的* tct.设置为0 (false)Primerh.。当我们读完下一行时* TCT + 4 - 5C1',我们知道底漆* tct.是无效的吗Primerh.所以跳过往上看左撇子。在实施方面,表格C1'被划分为多个子表,多个CPU线程读取自己的子表并更新Primerh.如果我们使用用于查找和设置的原子操作,那里没有种族条件有效的Primerh.

第4步:构建阵列和一般交叉杂交滤波

步骤4由以下两个阶段组成:准备数据结构并执行一般交叉杂交滤波。在第一阶段,它建立(1)一个哈希地图拍拍,(2)由步骤3的结果构建的一组数组(很快,ArraySc3.)和(3)从步骤1的结果构建的一组阵列(不久,ArraySc1)。在第二阶段,它使用一般的交叉杂交滤波使用拍拍,ArraySc3., 和ArraySc1,同时越来越多k从1到#maxmismatch.

哈希图拍拍是由有效行(即,有效的= 1)Primerh.通过提取所有可能的种子P。在图中。2B,拍拍时显示散列映射的示例\(k = 1 \),则种子的长度为\(\ lfloor 3/2 \ rfloor = 1 \)。钥匙拍拍是一个串联种子,指数(位置在哪里种子发生在P)和| |P|(的长度P)。的价值拍拍,也就是说,pset.包含一组长度的引物|P|,种子发生在指数。例如,在第一行中拍拍意味着一组长度3的底漆在其中种子一个在位置0处发生的是{AAC,ATG}。每一组具有相同密钥的引物都以这种方式分组。例如,对于human RefSeq DB,总共形成了3,309,154个组\(k = 1 \),总共形成77,418个组\(k = 2 \)拍拍主要用于建筑吗ArraySc3.ArraySc1

数组的集合,ArraySc3.,由四个阵列组成,p3offset.,P3.,sidset3offset., 和Sidset3.如图1所示。3.一种。建造ArraySc3.,我们首先对键进行排序拍拍按照长度的升序pset.,即,引物的数量。密钥的顺序用于处理GPU计算的工作量平衡,我们称之为工作量订单。然后,我们建立阵列P3.Sidset3.根据工作量订单。例如,如果我们假设T + 1 + 3有最短的pset., 和a + 0 + 3有第二个最短的pset.在哈希地图拍拍,然后P3.以。。开始pset.T + 1 + 3下一个pset.a + 0 + 3。同样地,Sidset3.以。。开始sidset.T + 1 + 3Primerh.(例如,1-2)下一个sidset.a + 0 + 3Primerh.(例如,2-3-4)。这两个p3offset.sidset3offset.只是指针阵列P3.Sidset3.分别用于GPU计算中的聚结的内存访问。

图3
图3

步骤4中使用的阵列示例。一个ArraySc3.:根据步骤3的结果构建的数组集。bArraySc1:由步骤1的结果构建的一组阵列

阵列输出用于存储一般交叉杂交滤波的结果,其长度与P3.由于滤波的目标是每个引物。它被初始化为1,这意味着在一般交叉杂交滤波期间有效和更新。通常,有多个元素输出对于相同的引物(例如,至少三个元素阿格)。

数组的集合,ArraySc1,由四个阵列组成,P1offset,P1.,sidset1offset, 和Sidset1.如图1所示。3.湾这两个P1.Sidset1.数组也按照上面提到的相同的工作负载顺序构建。按照相同的顺序执行之间的二进制连接ArraySc3.ArraySc1使用GPU计算快速且大规模。P1.Sidset1.是使用的Psidset.C1'(步骤1的输出)分别P3.Sidset3.是使用的pset.拍拍sidset.Primerh., 分别。详细地,我们提取一组密钥(即,种子+指数+|P|)和价值(即,pset.)来自每一行C1',如果相应的密钥存在拍拍,并建立P1.Sidset1.以便遵循工作量订单(例如,第一个T + 1 + 3第二个a + 0 + 3)。中的信息ArraySc1就变成了把它包括进去ArraySc3.由于前者使用步骤1的结果构建,而后者使用步骤3的结果构建。

所有的数据结构,拍拍,ArraySc3.ArraySc1需要为每个人建造k在图中。1b.也就是说,GPrimer使用所构造的数据结构执行第一个通用交叉杂交过滤\(k = 1 \)然后使用数据结构进行第二次过滤\(k = 2 \)。第一次过滤后使用\(k = 1 \),Primerh.是基于输出这样,如果是一个元素输出引物为0时,有效的相应的底漆Primerh.也被设置为0 (false)。一个新的拍拍应该为\(k = 2 \)由于种子的长度拍拍变短k增加。因此,ArraySc3.ArraySc1应该基于新的新建拍拍和更新Primerh.。的输出数组也应初始化。

如果输入序列DB的大小足够小,只能使用单个GPU处理,步骤4的过程相对简单:在主存储器中准备数据结构,复制两个ArraySc3.ArraySc1到GPU存储器,并执行GPU内核功能以进行一般交叉杂交滤波。但是,如果一次与多个GPU一起处理DB的大小太大,则该过程需要更复杂。Gprimer利用GPU的流处理功能,使步骤4在DB的大小和GPU的数量方面可扩展。

数字4a显示了GPrimer在磁盘、主存和gpu之间的数据结构流。基本上,GPrimer将整体分割ArraySc3.并将每个chunk复制到每个GPU(称为chunk-copy)。我们假设chunk的数量等于gpu的数量(记为)。我们表示赋给。的块y-th gpu(简单地gpu\(^ {(y)} \)),ArraySc3.\(^ {(y)} \)。在图中。3.一个,每个键(即,种子+指数+|P|)及其相应的子阵列p3offset.,P3.,sidset3offset., 和Sidset3.是独立工作量的最小单位。因此,ArraySc3.在键之间的边界处分成多个块的大小几乎相等。gprimer分裂输出进入块并以类似的方式将每个块复制到每个GPU。

图4
装具

步骤4中的数据流和平铺线。一个磁盘,主内存和GPU之间的数据流。b在三种类型的GPU操作方面的多个GPU流的时间表:H2D(主机到设备)复制,内核执行和D2H(设备到主机)复制

在的情况下ArraySc1,表C1'被分成多个小区C1'\ (_x \),我们表示这一部分ArraySc1从中建造C1'\ (_x \)以便按照工作量顺序ArraySc1\ (_ {x} \)。我们可以再次分开ArraySc1\ (_ {x} \)分成多个不相交的块ArraySc1\(_ {x} ^ {(y)} \)这样的钥匙的范围ArraySc1\(_ {x} ^ {(y)} \)和的一样吗ArraySc3.\(^ {(y)} \)。gprimer副本ArraySc1\(_ {0} ^ {(y)} \)到GPU.\(^ {(y)} \)(\(0 \le y < Q\)),副本ArraySc1\(_ {1} ^ {(y)} \)到GPU.\(^ {(y)} \)(\(0 \le y < Q\)依此类推(称为流副本)。

这里,流副本意味着GPU内核函数用于一对ArraySc3.\(^ {(y)} \)ArraySc1\(_ {x} ^ {(y)} \)在GPU同时在GPU中执行ArraySc1\(_ {z} ^ {(y)} \)准备并复制到GPU (\(x )。对于流副本,我们需要使用多个GPU流,其中GPU流是指以下三种类型的操作的有序序列:H2D Copy,内核执行和D2H复制[33.]。数字4b显示GPU中多个GPU流的时间线\(^ {(y)} \)。绿色的H2D框对应于流复制ArraySc1\(_ {x} ^ {(y)} \)到GPU和执行GPU内核功能的紫色框。一旦内核函数处理了ArraySc1\(_ {x} ^ {(y)} \),其结果(即引物的有效性)在输出\(^ {(y)} \)在GPU记忆中。因此,我们需要同步输出通过复制输出\(^ {(y)} \)来自GPU.\(^ {(y)} \)合并它们的主内存(橙色D2H框)。完成特定的步骤4之后k,Primerh.是基于输出在主内存。我们假设到目前为止ArraySc3.可以适合多个gpu的内存,它实际上是为所有输入db我们已经测试。如果它不适合,GPrimer分割ArraySc3.进入多个部分,使得每个部分可以适合并重复上述过程,如嵌套环路方法。

算法1介绍了步骤4的GPU内核函数的伪代码,这可能看起来很复杂,但实际上很简单。该功能主要依赖于GPU存储器中的结合内存访问效率,因此,其大部分线都是关于识别要访问的存储器地址。在该功能中,基本处理单元是GPU线程,并且要处理的基本数据单元是键(即,种子+指数+|P|)。为简单起见,我们表示ArraySc3.\(^ {(y)} \),ArraySc1\(_ {x} ^ {(y)} \), 和输出\(^ {(y)} \),因为ArraySc3.,ArraySc1, 和输出, 分别。两个阵列,ArraySc3.ArraySc1,可以由每个键划分。例如,在图1中。2a,蓝色部分对应于键\(t + 1 + 3 \),红色部分是钥匙\(a + 0 + 3 \)。该功能需要工作负责人k作为输入和更新并返回输出数组作为输出。参数工作负责人是确定每个线程是否处理单个键的边界(每个线程模式),或者线程块进程的所有线程使用单个键(块线程模式)。具有较小指数的键组工作负责人(例如,索引\(a + 0 + 3 \)图1中为1。2a)使用算法1.在每个线程模式中处理。我们将解释如何确定工作负责人后来更详细。

雕像

由于它是GPU内核功能,因此所有GPU线程都执行相同的整个函数(第1行)。在第2行时,每个线程获取基于其自己的索引(即ThreadIDX),线程块(即,blockdim)的大小和块的索引(即,blockidx)的键的索引。在线程处理其自己的密钥(第4-23行)之后,它得到下一个密钥(第24行)的索引,并重复处理密钥。线程获取开始和结束指数P3.(第4-5行)和在中的开始和结束指数P1.(第6-7行)。然后,它检查每对引物之间P3 [P3.开始:P3.结束] 和P1 [P1开始:P1结束](第8-11线)。对于特定的对PRIMER3.PRIMER1,它获得了开始和结束指数sidset3offset.(12-13行)和中的开始和结束指数sidset1offset(第14-15行)。然后,它设置了输出(]PRIMER3.0,即无效,(第18行),如果PRIMER3.类似于PRIMER1最多k不匹配残留(第17行),同时,PRIMER1放大任何目标序列PRIMER3.不放大(第16行)。第16-19行中的逻辑已在前面的研究中呈现[1,5,8]。

表格1以对的数量表示步骤4的计算量PRIMER3.PRIMER1要被处理,即算法中的第12-21行的执行次数。对于人和鼠标超过1.4万亿,这表明步骤4确实计算密集型。

表1步骤4为六种物种的计算量。

现在,我们来解释一下参数工作负责人,它是确定每个线程是否处理单个键(每个线程模式),或者线程块进程的所有线程使用单个键(块线程模式)。具有较小指数的键组工作负责人(例如,索引\(a + 0 + 3 \)图1中为1。3.a)在每个线程模式下处理。阵列中每个键的引物数的分布P3.(或者P1.)非常偏好。例如,每个键的最小底漆是1,而最大数量为8786,用于人类Refseq DB(\ \) (k = 2)。这意味着一些GPU线程处理几个键,而其他一些GPU线程处理千键。在后一线线程完成函数之前,前线无关,这可能会严重降低GPU计算的利用率,因此降低步骤4的性能。使用每个线程模式或块线程的混合方法mode depending on the workload (i.e., the number of primers per key) can alleviate this problem. SinceP3.已经按工作负载进行了排序,那么P1.也几乎按工作负载排序,我们可以为具有较小逻辑的键执行每个线程模式而不是工作负责人以及其他键的块线程模式。在块线程模式中,我们通常将块的数量设置为1024和块的大小为1024线程。也就是说,最多可以使用每键1024个线程处理1024个密钥。

每个键引物的数量有增加的趋势k自成种的独特种子的数量减少k增加。因此,我们设置了工作负责人\(k = 2 \)相比\(k = 1 \)。我们启发式落实工作负责人到第85百分位数\(k = 1 \),同时将其设置为20百分位数\(k = 2 \)。也就是说,如果总共有100个键,工作负责人变成85\(k = 1 \)。对于人Refseq DB,第85百分位数的键的引物的数量为22(\(k = 1 \)),第20百分位数是164(\(k = 2 \))。这意味着使用单个线程处理具有多达22和164个引物的键\(k = 1 \)\(k = 2 \), 分别。

步骤5:配对过滤和排名

通过使用多个异步GPU流掩盖PCI-e通信开销来处理步骤5以及步骤4,使用多个异步GPU流覆盖PCI-E通信开销,并使用负载平衡工作负责人。在第4步的末尾,GPrimer简单地读取C2并将行写入C4如果它是有效的是1的Primerh.。步骤5采用步骤4的结果,即,C4,并将其分组为sid。对于构造数组,GPRimer计算每个的前向(或反向)引物的数量sid小组C4并对群体进行排序C4按照每组引物的数量(即工作负载顺序)的升序顺序。数字5A显示了一个例子C4按工作负载顺序排序。

图5
figure5

步骤5中使用的数据结构示例。一个分类C4b阵列的前引物。c逆向引物的阵列。d阵列为分数的引物

GPRIMER构造两种阵列,一个用于前进引物,另一个用于反向引物,使用C4并对正向引物(FPs)和反向引物(rp)之间的所有可能对应用5对过滤约束。然后,对于所有满足约束的有效FP和RP对,GPrimer计算它们的分数,根据它们的分数对它们进行排序,并将格式化后的结果存储为输出。具体来说,它构造了三个数组,FPoffset,《外交政策》FPOS.,对于前后引物和三个阵列,rpoffset.,rp.rpo例如,根据工作量订单,对于反向引物。例如,《外交政策》以。。开始CGT.为该集团SID:7下一个{ATG,AAC.}为组SID:2在图中。5b。同样地,rp.以。。开始 {CAA,GAC.} 为了SID:7下一个{TCA,TCG.} 为了SID:2在图中。5C。Gprimer还准备了调用的数组分数用于存储FPS和RPS之间的所有可能对的分数(图。5d)。通过扫描两者FPoffsetrpoffset.一旦,我们可以构建记分组,即指针数组分数。它被初始化为\( - 1.0 \),这意味着相应的对是无效的。如果一对引物有效,则满足对滤波约束的,如果计算其分数并将其分配给数组中的相应元素分数

步骤5的GPU内核功能在FP和RP之间处理一对引物。例如,在图1中。5B-D,第一个GPU线程(keyidx.= 0)在蓝色和第二个GPU线程中处理两对引物(keyidx = 1)处理四对红色引物。准确的工作量应该是引物对的数量,但为简便起见,我们将正向引物的数量作为工作量。步骤5中工作负载的分布比步骤4中更加倾斜。数字6A,B显示人类和鼠标的工作负载分布,其中x-AXIS是keyidx.(例如,集团)y-AXIS是每组的前向引物(即工作负载)的数​​量。这些数字表明许多序列(组)具有相对较小的工作量,而几个序列具有非常大的工作量。数字6C, d显示人类和老鼠的详细分布,其中x-axis是工作负载,和y-axis是每个工作量的序列数。基于此观察,我们使用两个工作负载阈值,smallthreshold.大雷斯克莱尔德对于步骤5,而不是步骤4中使用的单个阈值。我们为具有较小索引的组执行每个线程模式smallthreshold.以及具有索引之间的组的块线程模式smallthreshold.大雷斯克莱尔德。对于具有更大指数的小组大雷斯克莱尔德,我们将一个GPU进程的所有线程组成一个单独的组(所有线程模式)。我们通常将块的数量设置为1024,以及块线程和全线模式的块的大小为512线程。对于人类,团体keyidx.[0:114]在每个线程模式下处理,该组keyidx.[114:51925]在块线程模式中,以及组keyidx.[51925:]在全线模式下。最后一组包含17767个前进引物和17713个反向引物,并在全线模式下使用512千线进行处理总共超过300万对的引物。

图6.
figure6

步骤5中的工作量分发。一个b代表人类和小鼠Refseq DBS的每组工作负载分布分别。cd代表人类和鼠标Refseq DBS每个工作量的序列数的分布

在步骤4中,Gprimer流副本ArraySc1对于GPU,如果它不适合GPU内存。同样,在步骤5中,如果它们不适合GPU存储器,则在步骤5中,GPrimer流副本复制六个阵列和两个阵列,用于GPU的分数。由于每个组是步骤5中的独立工作负载,因此GPRIMER流将阵列复制到不同的GPU中的分离组。合成的分数阵列在每个GPU被复制回主存储器进行同步。根据它们的得分对它们进行排序(即排序)是由CPU线程完成的。

结果

实验设置和数据集

MRPRIMER [5在一个由六台服务器组成的集群上使用MapReduce进行评估:一台主服务器和五台从服务器。每台机器配备两个Intel Xeon 10核cpu、512gb主存和6tb磁盘。我们在每台机器上使用了40个Map进程和40个Reduce进程(即总共200个Map进程和200个Reduce进程)。GPrimer使用一台配备相同cpu、相同主内存的单机进行评估,但8个NVIDIA GTX 1080ti gpu拥有11 GB的设备内存。

表2每个步骤中数据的大小(输入:序列的个数,C1- - - - - -C4:行数,输出:引物的数量)

对于数据集,我们使用MRNA序列DBS用于六种物种 - 人,小鼠,大鼠,斑马鱼,牛和猪 - 来自NCBI参考序列(REFSEQ)数据库(http://www.ncbi.nlm.nih.gov/refseq/)。使用的RefSeq db共包含138,375个mRNA序列,这些序列以NM作为GenBank登录号的前缀(人类版本于2018年11月21日更新,其他人版本于2018年11月7日更新)。表格2总结每个步骤中数据的大小。输出中的行数变得大于C4因为每一行不是一个引物,而是一对引物。

与MRPrimer的性能比较

我们评估了Gprimer和MrPrimer的经过时间。数字7A显示GPRimer的加速与MRPrimer相比所有物种的所有步骤。在该图中,使用八个GPU的加速度高于使用四个GPU,但差异并不多,这将在下一节中解释。随着输入序列DB的尺寸增加,例如从猪到人,加速也变大。我们可以说,对于更大的序列DB,它是一种理想的性能,更加改善。数字7b显示步骤1-3的加速,其中Gprimer仅使用CPU线程作为MRPRimer。与MrPrimer相比,GPRimer提高了两次的性能,即使GPRimer利用20个CPU内核,而MrPrimer共使用100个CPU核心。性能改进主要是由于GPRIMER中的线程在相同的内存空间中计算,而MRPRIMER中的那些在不同的存储空间中计算,具有网络通信的一些开销。数字7C显示步骤4的加速,即一般交叉杂交(GCH)滤波步骤。我们执行了两次GCH滤波,即\(k = 1 \)\(k = 2 \),并概括两次评估。加速度非常大,特别是人类最多607次。就经过的时间而言,对于人类而言,Gprimer使用四个GPU大约需要11分钟,而MrPrimer大约需要100小时。这表明我们对实施中描述的步骤4的方法非常有效地利用GPU的计算能力。数字7D示出了步骤5,即对滤波和排序步骤的加速,其中加速约为10.因此,与步骤1-3相比,步骤5更加计算,但与步骤4相比,计算密集较小。

图7.
figure7

与MrPrimer相比,Gprimer的加速。一个加速所有步骤;b加速步骤1-3(不使用gpu);c加速步骤4;d加速步骤5

GPRIMER改变GPU数量的表现

数字8A显示人类的步骤4的步骤4,用于改变使用的GPU的数量。步骤4按五个子步骤执行:建筑物拍拍,准备ArraySc3.,探索ArraySc1反对ArraySc3.、更新Primerh.和写作C4。在图中,探测的子步骤ArraySc1不仅包括执行GPU内核功能的时间,还包括构建每个块的时间ArraySc1在主内存中使用CPU并将其流传输到GPU内存中。事实上,三种不同类型的操作,即建设,流媒体和执行,为ArraySc1在时间表中重叠。探测的时候ArraySc1随着GPU的数量增加而降低,因为子步骤在GPU中执行。但是,四个或八个GPU的时间没有太大减少,因为建筑和流媒体的开销ArraySc1变大。仅执行GPU内核函数的时间与GPU数量成反比递减,如表所示3.。在这里,当GPU的数量变得两次时,时间减少了时间超过两次的原因是内存使用ArraySc3.在每个GPU中,随着GPU数量的增加而减少,因此我们可以通过增加一块的大小来减少GPU内核函数的执行次数ArraySc1。准备的子步骤ArraySc3.意味着建筑ArraySc3.在主内存和Chuct复制它GPU内存中。随着GPU的数量增加,块的大小ArraySc3.分配给每个GPU减少,因此,该子步骤的时间也减少。无论GPU的数量如何,其他三个子步骤的时间几乎相同。

图8
figure8

在GPRIMER的步骤4和5中的子步骤中的代表​​经过时间,同时改变人Refseq DB的GPU数。图中的每个条形图都表示经过的总时间。探测C1相一个过滤和评分阶段进入b是执行GPU操作的阶段

数字8b表示GPrimer步骤5的运行时间。步骤5按照构建数组、筛选评分、编写排名三个子步骤的顺序进行。图中,过滤评分的子步骤是由gpu处理的,所以它的时间近似与gpu的数量成反比递减。相反,另外两个子步骤的运行时间几乎是相同的,不管图形处理器的数量,因为它们与图形处理器计算无关。

表3在执行人员Refseq的GPU内核函数的经过时间

工作量平衡和流媒体复制的有效性

为了充分利用GPU,GPRIMER依赖于GPU内的聚合的内存访问,GPU线程之间的工作负载平衡,以及主存储器和GPU内存之间的流复制数据。在三种技术中,我们在本节中检查工作量平衡和流复制的有效性。很难打开和脱落结合的内存访问,因此我们跳过检查其有效性。数字9显示使用GPU的Gprimer性能的细分,即使用GPU,即探测ArraySc1步骤4和步骤5的过滤和评分。我们评估了以下四个版本的GPrimer的运行时间:只使用流复制(S),只使用工作负载平衡(B),既不使用工作负载平衡也不使用流复制(什么都不使用),以及同时使用(S+B)。不使用流复制意味着在GPU内核函数执行完成后进行同步复制。不使用工作负载平衡意味着只在单一模式下处理键或组,特别是对于步骤4只使用每个线程模式,对于步骤5只使用块线程模式,而不考虑阈值。由于GPU内存不足,我们不能在步骤5中只使用每个线程模式。在图中。9a,我们可以看到工作负载平衡比流式复制更重要,以便进行性能。在图中。9b,步骤5中的工作负载平衡和流复制的效率低于步骤4。具体来说,流复制的效率较低,因为流复制的数据的大小更小,流复制的数据流更简单。工作负载均衡的效率也较低,因为就处理工作负载的偏度而言,块线程模式总体上是三种模式(各线程模式、块线程模式和全线程模式)中最好的单一模式。

图9.
figure9

在打开和关闭两种技术,工作负载均衡(B)和流复印时,四次不同版本的GPRImer的经过时间。对人和小鼠Refseq DB进行实验(以x轴表示)

内存使用情况

表格4显示了GPrimer中主要数据结构的内存使用(以MByte为单位)。哈希映射,Primerh.,左撇子, 和拍拍,在主记忆中。剩余的数据结构都在GPU存储器中。正如您所看到的,大小ArraySc3.+输出甚至足以适合人类和鼠标的GPU记忆,所以流媒体ArraySc1到GPU只需要一次完成一次。最大的数据结构是一对分数记分组,但由于它们被分配,计算并将其复制回主存储器以足够小以符合GPU内存以符合GPU存储器的情况,因此不会发生内存问题。

表4主要数据结构的内存使用情况(MB)

表格5显示MRPRIMER和鼠标REFSEQ DB的MRPRIMER和GPRIMER的内存开销。由于MrPrimer不维护单独的主要数据结构,因此我们在每个步骤中测量了两者的峰值主内存使用。对于MrPrimer,我们总结了使用六台机器的内存使用情况。我们注意到步骤6和7中GPRImer的峰值存储器(即,约85 GB)小于数据结构的大小分数记分组(即,112 GB)在表格中4。这是因为GPrimer并不生成分数记分组而不是一步一步地以更小的尺寸生成它们,以便能够装入GPU内存。

表5 MILPER和GPRIMER在鼠标REFSEQ DB的每个步骤中的峰值存储器用法(在MB中)

结论

在本文中,我们提出了一个快速的基于gpu的管道设计,称为GPrimer,可以显著提高现有的基于MapReduce的MRPrimer管道的性能。GPrimer接受相同的输入数据,并返回与MRPrimer完全相同的输出。也就是说,GPrimer与MRPrimer具有完全相同的引物设计特异性。GPrimer和MRPrimer之间的唯一区别是设计引物的速度。MRPrimer是一个基于mapreduce的管道,而GPrimer是一个基于gpu的管道。由于本文提出的数据结构和算法,对人类RefSeq DB, GPrimer达到57倍的加速整个步骤和557倍的加速最耗费时间的一步,也就是说,同源性测试步骤,使用单一机器4 gpu,相比之下MRPrimer 6台机器的一个集群上运行。GPrimer不仅明显优于MRPrimer,而且随着序列DB大小的增加,其改进更明显。由于GPrimer与MRPrimer具有完全相同的引物设计特异性,所以GPrimer在特异性方面也优于MRPrimer所优于的其他引物设计软件。因此,我们认为GPrimer可以用于基于web的RNA病毒检测引物设计工具和引物数据库,以处理指数级增长的序列db的大小。

可用性和需求

  • 项目名称:GPRIMER。

  • 项目主页:欧宝直播官网apphttp://github.com/qhtjrmin/gprimer.

  • 操作系统:Linux Ubuntu 16.04 LTS或更高。

  • 编程语言:c++ 11, CUDA。

  • 其他要求:CUDA工具包版本8或更高版本。NVIDIA驱动程序(V384或更高版本),GCC / G ++ 4.8.x或更高版本。

  • 许可证:BSD-3-Clase。

  • 非学者使用限制:不适用。

数据和材料的可用性

使用的输入数据集来自NCBI参考序列(REFSEQ)数据库(http://www.ncbi.nlm.nih.gov/refseq/)),目前研究中使用的数据集可在GitHub存储库中使用,http://github.com/qhtjrmin/gprimer.。在BSD-3-SAUND许可下,所提出的工具GPRimer的源代码可从相同的Github存储库中获取。

缩写

PCR:

聚合酶链反应

DB:

数据库

中央处理器:

中央处理器

GPU:

图形处理单元

CUDA:

计算统一的设备架构

参考文献

  1. 1。

    Kim H,Kang N,K,Kim D,Koo J,Kim MS。MRPRIMERV:用于RNA病毒检测的PCR引物数据库。核酸RES。2017; 45:475-81。

    文章谷歌学术

  2. 2。

    Holst-Jensen A,RønningBS,Berdal KG,LøvsethA。用于筛选和定量转基因生物(GMOS)的PCR技术。肛癌生物山化学。2003; 375:985-93。

    CAS文章谷歌学术

  3. 3.

    实时荧光定量PCR技术的应用和局限性。Trends Mol Med. 2002; 8:257-60。

    CAS文章谷歌学术

  4. 4.

    王X,Spandidos A,Wang H,种子B. primerbank:用于定量基因表达分析的PCR引物数据库,2012年更新。核酸RES。2014; 40:1144-9。

    CAS文章谷歌学术

  5. 5。

    Kim H, Kang N, Chon KW, Kim S, Lee N, Koo J, Kim MS. Mrprimer:一种基于mapreduce的方法,用于彻底设计有效且有序的PCR引物。核酸杂志2015;99:33-54。

    谷歌学术

  6. 6。

    Untergasser A,Nijveen H,Rao X,Bisseling T,Geurts R,Leunissen Ja。primer3plus,一个增强的web界面到primer3。核酸RES。2007; 35:71-4。

    文章谷歌学术

  7. 7。

    Ye J,Coulouris G,Zaretskaya I,Cutcutache I,Rozen S,Madden TL。PRIMER-BLAST:用于为聚合酶链反应设计靶特异性引物的工具。BMC Bioinf。2012; 13:134。

    CAS文章谷歌学术

  8. 8。

    Kim H,Kang N,K,Koo J,Kim Ms。MRPRIMERW:用于多目标QPCR实验的有效高质量引物的快速设计的工具。核酸RES。2016; 44:259-66。

    文章谷歌学术

  9. 9.

    Jeon H, Bae J, Hwang SH, Whang KY, Lee HS, Kim H, Kim MS. MRPrimerW2:一种增强的工具,用于快速设计有效的高质量QPCR实验引物,具有多种搜索模式。核酸研究:2019;47:14 - 22。

    文章谷歌学术

  10. 10。

    Schatz MC。CloudBurst:用MapReduce高度敏感的读取映射。生物信息学。2009; 25:1363-9。

    CAS文章谷歌学术

  11. 11.

    马克南(McKenna A, Hanna M, Banks E, Sivachenko A, Cibulskis K, Kernytsky A, et al.)基因组分析工具包:用于分析下一代DNA测序数据的mapreduce框架。基因组研究》2010;20:1297 - 303。

    CAS文章谷歌学术

  12. 12.

    Pandey RV,SchlöttererC. Distmap:在Hadoop集群上分布式短读映射的工具包。Plos一个。2013; 8:72614。

    文章谷歌学术

  13. 13。

    Puckelwartz MJ, Pesce LL, Nelakuditi V, Dellefave-Castillo L, Golbus JR, Day SM等。全基因组分析并行化的超级计算。生物信息学。2014;30:1508-13。

    CAS文章谷歌学术

  14. 14。

    Decap D,Reurumes J,Herzeel C,Costanza P,Fastier J.Halvade:使用MapReduce进行可扩展序列分析。生物信息学。2015; 31:2482-8。

    CAS文章谷歌学术

  15. 15.

    Decap D,Reurumers J,Herzeel C,Costanza P,Fastier J.Halvade-RNA:使用MapReduce从转录组数据调用并行变体。cplos一个。2017; 12:0174575。

    谷歌学术

  16. 16。

    Nellore A, Collado-Torres L, Jaffe AE, Alquicira-Hernández J, Wilks C, Pritt J, et al.;Rail-RNA: rna序列剪接和覆盖的可扩展分析。生物信息学。2017;33:4033-40。

    CASPubMed.谷歌学术

  17. 17。

    ExpósitoRR,Veiga J,González-domínguezJ,TouriñoJ.Mardre:基于高效的Mapreduce的云中的重复DNA读取。生物信息学。2017; 33:2762-4。

    文章谷歌学术

  18. 18。

    赵立,陈Q,李W,江P,黄L,Li J.MapReduce用于下一代测序数据的准确纠错。生物信息学。2017; 33:3844-51。

    CAS文章谷歌学术

  19. 19。

    Ferraro Petrillo U,Roscigno G,Cattaneo G,Giancarlo R.通过高效Hadoop集群算法的大型基因组序列收集的信息和语言分析。生物信息学。2018; 34:1826-33。

    文章谷歌学术

  20. 20。

    Vouzis PD。V SN Gpu-blast:使用图形处理器加速蛋白质序列比对。生物信息学。2011;27:182-8。

    CAS文章谷歌学术

  21. 21。

    赵克,楚X. g-Blastn:通过图形处理器加速核苷酸对齐。生物信息学。2014; 30:1384-91。

    CAS文章谷歌学术

  22. 22。

    叶伟,陈勇,张勇,徐勇- H-BLAST:一种基于gpu的异构计算机快速蛋白质序列比对工具包。生物信息学。2017;33:1130-8。

    CASPubMed.谷歌学术

  23. 23。

    SLUO R,WONG T,朱茹,刘厘米,朱X,吴娥,TITH HF。SOAP3-DP:基于快速,准确和敏感的GPU短读对准器。生物信息学。2013; 8:65632。

    谷歌学术

  24. 24。

    常春,周山,吴永昌,洪涛,李永利,杨春,洪建辉。SBWT:内存高效实现硬件加速友好的Schindler转换,用于快速生物序列映射。生物信息学。2016;32:3498 - 500。

    CAS文章谷歌学术

  25. 25。

    GCUP:基于gpu的hiv-1共受体快速预测下一代测序。生物信息学。2014;30:3272-3。

    CAS文章谷歌学术

  26. 26.

    威尔顿河,李克,费因伯格AP,Szalay。艾克:GPU加速对齐的短亚硫酸盐处理的读数。生物信息学。2018; 34:2673-5。

    CAS文章谷歌学术

  27. 27.

    Quang D, Guan Y, Parker SC. Yamda:使用深度学习库和gpu实现基于em的主题发现的千倍加速。生物信息学。2018;34:3578 - 80。

    CAS文章谷歌学术

  28. 28.

    Tongsima S, Ngamphiw C, Sethia A为精确医学加速基因组学发现[白皮书]。英伟达;2019

  29. 29。

    Dean J.S G MapReace:大集群上的简化数据处理。公共交流。2008; 51:107-13。

    文章谷歌学术

  30. 30。

    Baeza-yates Ra,Perleberg Ch。快速实用的近似字符串匹配。inf process lett。1996年; 59:21-7。

    文章谷歌学术

  31. 31。

    Kim Ms,Whang Ky,Lee JG,Lee MJ N-Gram / 2L:空间和时间高效的两级N-GRAM倒置索引结构。:在:2005年非常大的数据基础上第31届国际会议的会议记录; 325-336

  32. 32。

    Kim M,Whang K,Lee J. n-Gram / 2L-近似:用于近似串匹配的两级n-gram反转索引结构。计算SYST SCI ENG。2007; 22:365。

    谷歌学术

  33. 33。

    Kirk D,HWU WM。编程大量平行处理器。3 ed。旧金山:摩根Kaufmann出版物公司;2016年。

    谷歌学术

下载参考

确认

本工作得到了韩国政府(MSIT)资助的韩国国家研究基金(MSIT)(2018年第2018年第2010.1060031号),通过科学部资助的韩国国家研究基金会,基础科学研究计划,ICT与未来规划(2017年第2017年的第2017年第2017630号)以及韩国政府(MSIT)资助的信息与通信技术规划与评估(IITP)赠款所(MSIT)(基于GPU的超快多型图数据库资助发动机SW)。

资金

本工作得到了韩国政府(MSIT)资助的韩国国家研究基金(MSIT)(2018年第2018年第2010.1060031号),通过科学部资助的韩国国家研究基金会,基础科学研究计划(NRF)基础科学研究计划,ICT与未来规划(2017年第2017年的第2017年第2017630号)以及韩国政府(MSIT)资助的信息与通信技术规划与评估(IITP)赠款所(MSIT)(基于GPU的超快多型图数据库资助发动机SW)。资金机构没有参与研究的设计;数据收集,分析和解释;并写稿件。

作者信息

隶属关系

作者

贡献

JB实施了软件工具,进行了稿件的撰写,并进行了绩效评估。HJ准备了数据集,并帮助验证工具。不断得到MSK的反馈和建议,并对手稿进行了批判性的修改。所有作者声明他们已经阅读并批准了最终稿件。

通讯作者

对应于Min-Soo金

伦理宣言

伦理批准和同意参与

不适用。

同意出版物

不适用。

利益争夺

提交人声明他们没有竞争利益。

附加信息

出版商的注意事项

欧宝体育黑玩家《自然》杂志对已出版的地图和附属机构的管辖权主张保持中立。

权利和权限

开放访问本文是基于知识共享署名4.0国际许可,允许使用、共享、适应、分布和繁殖在任何媒介或格式,只要你给予适当的信贷原始作者(年代)和来源,提供一个链接到创作共用许可证,并指出如果变化。本文中的图像或其他第三方材料包括在文章的创作共用许可中,除非在材料的信用线中另有说明。如果材料没有包含在文章的创作共用许可证中,而您的预期使用不被法律法规允许或超过允许的使用,您将需要直接获得版权持有人的许可。如欲浏览本许可证的副本,请浏览http://creativecommons.org/licenses/by/4.0/。Creative Commons公共领域奉献豁免(http://creativecommons.org/publicdomain/zero/1.0/)适用于本文中提供的数据,除非另有用入数据的信用额度。

重印和权限

关于这篇文章

通过十字标记验证货币和真实性

引用这篇文章

GPrimer:一种基于gpu的快速管道,用于qPCR实验引物设计。欧宝娱乐合法吗22,220(2021)。https://doi.org/10.1186/s12859-021-04133-4

下载引用

关键字

  • 底漆设计
  • GPU计算
  • 序列分析
\