Links to Exploration step
Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Accelerating metagenomic read classification on CUDA-enabled GPUs</title>
<author><name sortKey="Kobus, Robin" sort="Kobus, Robin" uniqKey="Kobus R" first="Robin" last="Kobus">Robin Kobus</name>
<affiliation><nlm:aff id="Aff1">Institute of Computer Science, Johannes Gutenberg University Mainz, Staudingerweg 9, Mainz, 55435 Germany</nlm:aff>
</affiliation>
</author>
<author><name sortKey="Hundt, Christian" sort="Hundt, Christian" uniqKey="Hundt C" first="Christian" last="Hundt">Christian Hundt</name>
<affiliation><nlm:aff id="Aff1">Institute of Computer Science, Johannes Gutenberg University Mainz, Staudingerweg 9, Mainz, 55435 Germany</nlm:aff>
</affiliation>
</author>
<author><name sortKey="Muller, Andre" sort="Muller, Andre" uniqKey="Muller A" first="André" last="Müller">André Müller</name>
<affiliation><nlm:aff id="Aff1">Institute of Computer Science, Johannes Gutenberg University Mainz, Staudingerweg 9, Mainz, 55435 Germany</nlm:aff>
</affiliation>
</author>
<author><name sortKey="Schmidt, Bertil" sort="Schmidt, Bertil" uniqKey="Schmidt B" first="Bertil" last="Schmidt">Bertil Schmidt</name>
<affiliation><nlm:aff id="Aff1">Institute of Computer Science, Johannes Gutenberg University Mainz, Staudingerweg 9, Mainz, 55435 Germany</nlm:aff>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">PMC</idno>
<idno type="pmid">28049411</idno>
<idno type="pmc">5209836</idno>
<idno type="url">http://www.ncbi.nlm.nih.gov/pmc/articles/PMC5209836</idno>
<idno type="RBID">PMC:5209836</idno>
<idno type="doi">10.1186/s12859-016-1434-6</idno>
<date when="2017">2017</date>
<idno type="wicri:Area/Pmc/Corpus">000262</idno>
<idno type="wicri:explorRef" wicri:stream="Pmc" wicri:step="Corpus" wicri:corpus="PMC">000262</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en" level="a" type="main">Accelerating metagenomic read classification on CUDA-enabled GPUs</title>
<author><name sortKey="Kobus, Robin" sort="Kobus, Robin" uniqKey="Kobus R" first="Robin" last="Kobus">Robin Kobus</name>
<affiliation><nlm:aff id="Aff1">Institute of Computer Science, Johannes Gutenberg University Mainz, Staudingerweg 9, Mainz, 55435 Germany</nlm:aff>
</affiliation>
</author>
<author><name sortKey="Hundt, Christian" sort="Hundt, Christian" uniqKey="Hundt C" first="Christian" last="Hundt">Christian Hundt</name>
<affiliation><nlm:aff id="Aff1">Institute of Computer Science, Johannes Gutenberg University Mainz, Staudingerweg 9, Mainz, 55435 Germany</nlm:aff>
</affiliation>
</author>
<author><name sortKey="Muller, Andre" sort="Muller, Andre" uniqKey="Muller A" first="André" last="Müller">André Müller</name>
<affiliation><nlm:aff id="Aff1">Institute of Computer Science, Johannes Gutenberg University Mainz, Staudingerweg 9, Mainz, 55435 Germany</nlm:aff>
</affiliation>
</author>
<author><name sortKey="Schmidt, Bertil" sort="Schmidt, Bertil" uniqKey="Schmidt B" first="Bertil" last="Schmidt">Bertil Schmidt</name>
<affiliation><nlm:aff id="Aff1">Institute of Computer Science, Johannes Gutenberg University Mainz, Staudingerweg 9, Mainz, 55435 Germany</nlm:aff>
</affiliation>
</author>
</analytic>
<series><title level="j">BMC Bioinformatics</title>
<idno type="eISSN">1471-2105</idno>
<imprint><date when="2017">2017</date>
</imprint>
</series>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass></textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en"><sec><title>Background</title>
<p>Metagenomic sequencing studies are becoming increasingly popular with prominent examples including the sequencing of human microbiomes and diverse environments. A fundamental computational problem in this context is read classification; i.e. the assignment of each read to a taxonomic label. Due to the large number of reads produced by modern high-throughput sequencing technologies and the rapidly increasing number of available reference genomes software tools for fast and accurate metagenomic read classification are urgently needed.</p>
</sec>
<sec><title>Results</title>
<p>We present cuCLARK, a read-level classifier for CUDA-enabled GPUs, based on the fast and accurate classification of metagenomic sequences using reduced <italic>k</italic>
-mers (CLARK) method. Using the processing power of a single Titan X GPU, cuCLARK can reach classification speeds of up to 50 million reads per minute. Corresponding speedups for species- (genus-)level classification range between 3.2 and 6.6 (3.7 and 6.4) compared to multi-threaded CLARK executed on a 16-core Xeon CPU workstation.</p>
</sec>
<sec><title>Conclusion</title>
<p>cuCLARK can perform metagenomic read classification at superior speeds on CUDA-enabled GPUs. It is free software licensed under GPL and can be downloaded at <ext-link ext-link-type="uri" xlink:href="https://github.com/funatiq/cuclark">https://github.com/funatiq/cuclark</ext-link>
free of charge.</p>
</sec>
</div>
</front>
<back><div1 type="bibliography"><listBibl><biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct><analytic><author><name sortKey="Ounit, R" uniqKey="Ounit R">R Ounit</name>
</author>
<author><name sortKey="Wanamaker, S" uniqKey="Wanamaker S">S Wanamaker</name>
</author>
<author><name sortKey="Close, Tj" uniqKey="Close T">TJ Close</name>
</author>
<author><name sortKey="Lonardi, S" uniqKey="Lonardi S">S Lonardi</name>
</author>
</analytic>
</biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct><analytic><author><name sortKey="Wilton, R" uniqKey="Wilton R">R Wilton</name>
</author>
<author><name sortKey="Budavari, T" uniqKey="Budavari T">T Budavari</name>
</author>
<author><name sortKey="Langmead, B" uniqKey="Langmead B">B Langmead</name>
</author>
<author><name sortKey="Wheelan, Sj" uniqKey="Wheelan S">SJ Wheelan</name>
</author>
<author><name sortKey="Salzberg, Sl" uniqKey="Salzberg S">SL Salzberg</name>
</author>
<author><name sortKey="Szalay, As" uniqKey="Szalay A">AS Szalay</name>
</author>
</analytic>
</biblStruct>
<biblStruct></biblStruct>
<biblStruct><analytic><author><name sortKey="Liu, Y" uniqKey="Liu Y">Y Liu</name>
</author>
<author><name sortKey="Schmidt, B" uniqKey="Schmidt B">B Schmidt</name>
</author>
<author><name sortKey="Maskell, Dl" uniqKey="Maskell D">DL Maskell</name>
</author>
</analytic>
</biblStruct>
<biblStruct></biblStruct>
<biblStruct><analytic><author><name sortKey="Li, D" uniqKey="Li D">D Li</name>
</author>
<author><name sortKey="Liu, Cm" uniqKey="Liu C">CM Liu</name>
</author>
<author><name sortKey="Luo, R" uniqKey="Luo R">R Luo</name>
</author>
<author><name sortKey="Sadakane, K" uniqKey="Sadakane K">K Sadakane</name>
</author>
<author><name sortKey="Lam, Tw" uniqKey="Lam T">TW Lam</name>
</author>
</analytic>
</biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct><analytic><author><name sortKey="Huang, W" uniqKey="Huang W">W Huang</name>
</author>
<author><name sortKey="Li, L" uniqKey="Li L">L Li</name>
</author>
<author><name sortKey="Myers, Jr" uniqKey="Myers J">JR Myers</name>
</author>
<author><name sortKey="Marth, Gt" uniqKey="Marth G">GT Marth</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Shcherbina, A" uniqKey="Shcherbina A">A Shcherbina</name>
</author>
</analytic>
</biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
</listBibl>
</div1>
</back>
</TEI>
<pmc article-type="research-article"><pmc-dir>properties open_access</pmc-dir>
<front><journal-meta><journal-id journal-id-type="nlm-ta">BMC Bioinformatics</journal-id>
<journal-id journal-id-type="iso-abbrev">BMC Bioinformatics</journal-id>
<journal-title-group><journal-title>BMC Bioinformatics</journal-title>
</journal-title-group>
<issn pub-type="epub">1471-2105</issn>
<publisher><publisher-name>BioMed Central</publisher-name>
<publisher-loc>London</publisher-loc>
</publisher>
</journal-meta>
<article-meta><article-id pub-id-type="pmid">28049411</article-id>
<article-id pub-id-type="pmc">5209836</article-id>
<article-id pub-id-type="publisher-id">1434</article-id>
<article-id pub-id-type="doi">10.1186/s12859-016-1434-6</article-id>
<article-categories><subj-group subj-group-type="heading"><subject>Software</subject>
</subj-group>
</article-categories>
<title-group><article-title>Accelerating metagenomic read classification on CUDA-enabled GPUs</article-title>
</title-group>
<contrib-group><contrib contrib-type="author" corresp="yes"><name><surname>Kobus</surname>
<given-names>Robin</given-names>
</name>
<address><email>rkobus@students.uni-mainz.de</email>
</address>
<xref ref-type="aff" rid="Aff1"></xref>
</contrib>
<contrib contrib-type="author"><name><surname>Hundt</surname>
<given-names>Christian</given-names>
</name>
<address><email>hundt@uni-mainz.de</email>
</address>
<xref ref-type="aff" rid="Aff1"></xref>
</contrib>
<contrib contrib-type="author"><name><surname>Müller</surname>
<given-names>André</given-names>
</name>
<address><email>muellan@uni-mainz.de</email>
</address>
<xref ref-type="aff" rid="Aff1"></xref>
</contrib>
<contrib contrib-type="author"><name><surname>Schmidt</surname>
<given-names>Bertil</given-names>
</name>
<address><email>bertil.schmidt@uni-mainz.de</email>
</address>
<xref ref-type="aff" rid="Aff1"></xref>
</contrib>
<aff id="Aff1">Institute of Computer Science, Johannes Gutenberg University Mainz, Staudingerweg 9, Mainz, 55435 Germany</aff>
</contrib-group>
<pub-date pub-type="epub"><day>3</day>
<month>1</month>
<year>2017</year>
</pub-date>
<pub-date pub-type="pmc-release"><day>3</day>
<month>1</month>
<year>2017</year>
</pub-date>
<pub-date pub-type="collection"><year>2017</year>
</pub-date>
<volume>18</volume>
<elocation-id>11</elocation-id>
<history><date date-type="received"><day>9</day>
<month>9</month>
<year>2016</year>
</date>
<date date-type="accepted"><day>16</day>
<month>12</month>
<year>2016</year>
</date>
</history>
<permissions><copyright-statement>© The Author(s) 2017</copyright-statement>
<license license-type="OpenAccess"><license-p><bold>Open Access</bold>
This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (<ext-link ext-link-type="uri" xlink:href="http://creativecommons.org/licenses/by/4.0/">http://creativecommons.org/licenses/by/4.0/</ext-link>
), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made. The Creative Commons Public Domain Dedication waiver (<ext-link ext-link-type="uri" xlink:href="http://creativecommons.org/publicdomain/zero/1.0/">http://creativecommons.org/publicdomain/zero/1.0/</ext-link>
) applies to the data made available in this article, unless otherwise stated.</license-p>
</license>
</permissions>
<abstract id="Abs1"><sec><title>Background</title>
<p>Metagenomic sequencing studies are becoming increasingly popular with prominent examples including the sequencing of human microbiomes and diverse environments. A fundamental computational problem in this context is read classification; i.e. the assignment of each read to a taxonomic label. Due to the large number of reads produced by modern high-throughput sequencing technologies and the rapidly increasing number of available reference genomes software tools for fast and accurate metagenomic read classification are urgently needed.</p>
</sec>
<sec><title>Results</title>
<p>We present cuCLARK, a read-level classifier for CUDA-enabled GPUs, based on the fast and accurate classification of metagenomic sequences using reduced <italic>k</italic>
-mers (CLARK) method. Using the processing power of a single Titan X GPU, cuCLARK can reach classification speeds of up to 50 million reads per minute. Corresponding speedups for species- (genus-)level classification range between 3.2 and 6.6 (3.7 and 6.4) compared to multi-threaded CLARK executed on a 16-core Xeon CPU workstation.</p>
</sec>
<sec><title>Conclusion</title>
<p>cuCLARK can perform metagenomic read classification at superior speeds on CUDA-enabled GPUs. It is free software licensed under GPL and can be downloaded at <ext-link ext-link-type="uri" xlink:href="https://github.com/funatiq/cuclark">https://github.com/funatiq/cuclark</ext-link>
free of charge.</p>
</sec>
</abstract>
<kwd-group xml:lang="en"><title>Keywords</title>
<kwd>Metagenomics</kwd>
<kwd>Taxonomic assignment</kwd>
<kwd>Exact <italic>k</italic>
-mer matching</kwd>
<kwd>CUDA</kwd>
<kwd>GPUs</kwd>
</kwd-group>
<custom-meta-group><custom-meta><meta-name>issue-copyright-statement</meta-name>
<meta-value>© The Author(s) 2017</meta-value>
</custom-meta>
</custom-meta-group>
</article-meta>
</front>
<body><sec id="Sec1"><title>Background</title>
<p>Metagenomic read classification is a common and increasingly important bioinformatics technique where short DNA reads stemming from a genomic sample are automatically annotated with a taxonomic label such as species or genus identifiers by mapping them onto a large set of reference genomes. Metagenomic sequencing studies are gaining popularity with prominent examples including the sequencing of human microbiomes [<xref ref-type="bibr" rid="CR1">1</xref>
] and diverse environments like seawater [<xref ref-type="bibr" rid="CR2">2</xref>
] in order to analyze their composition and to study their temporal variation. Precise knowledge about the individual components of a sample enables researchers to understand the interaction with surrounding environments or to gain information about the integrity of the analyzed system.</p>
<p>With DNA sequencing becoming faster and cheaper, the amount of recorded data is expected to rapidly grow in the foreseeable future. As an example, online services such as <italic>μ</italic>
Biome (see <ext-link ext-link-type="uri" xlink:href="https://ubiome.com">https://ubiome.com</ext-link>
) are currently performing the sequencing and analysis of a human gut sample for less than US$ 100. Thus, the design and implementation of exceedingly fast and precise metagenomic read classification algorithms remains an important topic for academic research and commercial solutions.</p>
<p>A number of approaches have been proposed to solve the read classification problem by employing machine learning techniques on top of nearest neighbor information between probed reads and reference genomes. BLAST [<xref ref-type="bibr" rid="CR3">3</xref>
] and BLAST-based methods like MEGAN [<xref ref-type="bibr" rid="CR4">4</xref>
] use inexact alignment of the sequences. PhymmBL [<xref ref-type="bibr" rid="CR5">5</xref>
] uses BLAST in combination with probabilistic models, while NBC [<xref ref-type="bibr" rid="CR6">6</xref>
] examines the composition of a sequence in consideration of Bayes’ rule. Unfortunately, these approaches are too slow for classifying the huge amounts of reads produced by current <italic>next-generation sequencing</italic>
(NGS) technologies.</p>
<p>The recently introduced Kraken [<xref ref-type="bibr" rid="CR7">7</xref>
] and CLARK [<xref ref-type="bibr" rid="CR8">8</xref>
] methods represent a major improvement in terms of classification speed (running almost three orders-of-magnitude faster than alignment-based approaches such as MegaBLAST). Both tools analyze each read by querying its <italic>k</italic>
-mers against a pre-built database. In case of Kraken, this database contains all <italic>k</italic>
-mers of the considered reference genomes, which are subsequently mapped to their <italic>lowest common ancestor</italic>
(LCA) in a taxonomic tree. For each input read a subtree containing all its <italic>k</italic>
-mer’s LCA taxa is constructed and examined to classify a read. CLARK employs a pre-built database of target genomes exclusively consisting of unique <italic>k</italic>
-mers. Ambiguous <italic>k</italic>
-mers shared among multiple targets are ignored. Note that a target can consist of multiple genomes, e.g. by treating genomes from the same genus as a single target. Finally, the best fitting candidate of the target genomes is used to label the input sequence.</p>
<p>CLARK and Kraken can be run in several user-defined classification modes. For example the <italic>full mode</italic>
of CLARK provides a complete analysis of the input sequences and therefore reaches the highest sensitivity. Further it provides confidence scores, which allow to abstain from uncertain classifications thus increasing precision. The remaining modes skip parts of the work to speedup the classification procedure at the cost of sensitivity. Apart from the aforementioned modes the user can specify a sampling factor controlling the ratio of target <italic>k</italic>
-mers to be considered during classification.</p>
<p>A recent benchmark study [<xref ref-type="bibr" rid="CR9">9</xref>
] showed that <italic>k</italic>
-mer based approaches performed among the best in a comparison of 14 tested tools in terms of both read assignment accuracy at genus/phylum level and classification speed. Kraken and CLARK can process NGS data with a speed of around 1 million reads per minute (depending on the read length) on a single CPU core. However, as metagenomic sequencing transcends from research labs to clinical and industrial applications even higher processing speeds are needed. For example, the estimation of species abundance in DNA sequences from a metagenomic sample usually requires a statistical method running on top of a read-level classifier where this classifier needs to be called excessively as a subroutine [<xref ref-type="bibr" rid="CR10">10</xref>
].</p>
<p><italic>Graphics processing units</italic>
(GPUs) can provide up to one order-of-magnitude higher peak performance compared to CPUs through massive fine-grained parallelism at a highly competitive price-performance ratio. Using programming languages such as CUDA, they can be used for general-purpose applications. Successful examples of GPUs applied to NGS read analysis include read mapping [<xref ref-type="bibr" rid="CR11">11</xref>
], RNA-Seq spliced alignment [<xref ref-type="bibr" rid="CR12">12</xref>
], error correction [<xref ref-type="bibr" rid="CR13">13</xref>
], <italic>k</italic>
-mer counting [<xref ref-type="bibr" rid="CR14">14</xref>
], and assembly [<xref ref-type="bibr" rid="CR15">15</xref>
]. In this paper, we show how CUDA-enabled GPUs can be used to accelerate metagenomic read classification. The limited size of video RAM attached to a GPU makes the storage of large databases challenging: they have to be distributed among several GPUs or split into smaller parts that are queried successively. Among the two considered methods (Kraken and CLARK), CLARK uses a smaller database and further allows to partition the database into smaller parts, which can be queried in batches. As a result, we have chosen the CLARK method as candidate for our GPU parallelization.</p>
<p>This work presents the design and implementation of computation schemes for massively parallel accelerators in order to accelerate read classification. Our software tool, cuCLARK, features support for multiple GPUs and further provides a light version allowing for the execution on legacy workstations with only 4 GB of RAM and 1 GB of video RAM. Using a number of datasets we show that cuCLARK running on a single Titan X GPU can classify up to 50 million reads per minute. It outperforms multi-threaded CLARK for species- (genus-)level classification running on a high-end 16-core Xeon E5-2683 v4 CPU by a factor between 3.2 and 5.1 (3.7 and 5.2) including all data transfers over the relatively slow PCIe bus, which is often a bottleneck for accelerators. Note that classification results of cuCLARK and CLARK are identical except for the ordering of equally scored targets.</p>
</sec>
<sec id="Sec2"><title>Implementation</title>
<p>cuCLARK provides similar functionality and usability to CLARK producing compliant output to CPU-based CLARK’s <italic>full mode</italic>
. It produces output in the same format and thus enables the user to take advantage of the post-processing scripts bundled with CLARK. Moreover, cuCLARK provides the same command line flags specifying common parameters such as <italic>k</italic>
-mer length and database sampling factor in order to facilitate the easy integration into already existing bioinformatics pipelines.</p>
<p>In contrast to that, a number of implementation details of CLARK’s classification algorithm had to be modified. In order to fully utilize the compute capabilities of a modern GPU, the execution needs to be highly parallel and make use of all its available resources. Efficient memory access and management are key for accelerating read classification, since the algorithm is dominated by random accesses to a large reference genome database. This database typically exceeds the amount of memory available on a single GPU. cuCLARK supports classification on a workstation with a single GPU and compute nodes with multiple GPUs.</p>
<p>Despite the differences in implementation, CLARK and cuCLARK produce the same target scores for each input object. The only discrepancy in the output derives from the case where multiple targets reach the same score for the same object. It can therefore happen that the programs choose different assignments if two or more targets reach the highest score. In these cases it is not possible to determine which target is the right one to choose as classification result and cuCLARK (as well as CLARK) reports the same lowest possible confidence score (which depends on the two highest target scores). Users may request the extended output which includes all target scores for each object for further analysis.</p>
<sec id="Sec3"><title>Database construction</title>
<p>Initially, a database is build in a pre-processing step. This is achieved by creating an index of all <italic>k</italic>
-mers contained in the target (<italic>reference genome</italic>
) sequences and collecting their number of occurrences per target. After all targets have been processed, any <italic>k</italic>
-mers that are shared by multiple targets are removed from the index. The remaining <italic>k</italic>
-mers are therefore called <italic>target-specific</italic>
or <italic>discriminative</italic>
. In the classification stage, the <italic>k</italic>
-mers of the input objects (<italic>reads</italic>
) are compared to these specific <italic>k</italic>
-mers.</p>
<p>The database construction method of cuCLARK modifies the CLARK database structure as follows. Instead of storing each <italic>k</italic>
-mer or its reverse complement depending on which appears first, we always choose the canonical <italic>k</italic>
-mer which is the lexicographically smaller of the two. This choice is also done for each <italic>k</italic>
-mer of a query read during the classification stage. Instead of querying the <italic>k</italic>
-mer first and the reverse complement in case of a miss, we always determine the canonical <italic>k</italic>
-mer, which helps to avoid branch divergence of the parallel execution. The database files which are stored on disk have the same format as CLARK’s and can be used instead of its own. Note that, cuCLARK’s database files can be used with CLARK but not vice versa.</p>
<p>While the creation process of the database is almost the same as in CLARK, we have changed the database pre-loading for classification. The hash table of CLARK consists of key-value pairs in a vector for each bucket. The buckets are themselves stored in a large vector. This nested container format is unsuitable for CUDA accelerators. Our approach uses an array for all keys and another one for all values. Values are accessed by pointers calculated by a prefix sum of the bucket sizes from the original hash table. This not only enables fast loading because the database files are already laid out the same as the arrays, it also allows for cache friendly traversing of consecutive keys when querying the database. This compressed form of the hash table is possible because the buckets do not change in size after their initial construction. Our data layout provides an additional advantage: If the database does not fit into the memory of a single GPU, it will need to be split up into several parts. This can be easily achieved by dividing the arrays in chunks and calculating the value pointers accordingly. Figure <xref rid="Fig1" ref-type="fig">1</xref>
shows the database structure of cuCLARK.
<fig id="Fig1"><label>Fig. 1</label>
<caption><p>Database Structure of cuCLARK. The quotients of the discriminative k-mers and the corresponding targets are loaded into <italic>one large array</italic>
each. For each k-mer remainder we calculate the pointer to the first element of its hash table bucket</p>
</caption>
<graphic xlink:href="12859_2016_1434_Fig1_HTML" id="MO1"></graphic>
</fig>
</p>
<p>We use page-locked host memory to store the database in RAM to improve the transfer bandwidth to the graphics memory over the PCIe bus. The program is able to make use of multiple accelerator cards and adjusts the size of the database chunks according to their memory sizes. If the combined memory of all available cards is not sufficient to hold the whole database, we have to query the parts in separate stages.</p>
</sec>
<sec id="Sec4"><title>Classification process</title>
<p>Before we can put the GPU to work, the input files need to be processed by the CPU. CLARK divides the input by the number of CPU threads if executed in multi-core mode. We have taken the idea one step further and partition the files into a user-defined number of batches. It is advisable to choose a multiple of the number of threads in order to achieve good load balancing. The benefit of smaller batches is a lower memory consumption per input chunk. This enables us to use most of the graphics memory for the database itself when processing batches on the GPU.</p>
<p>FASTA or FASTQ are accepted input file formats. First the length of the contained DNA sequences is determined in order to allocate sufficient memory for both input sequences and classification results. We again use page-locked host memory to achieve higher throughput.</p>
<p>Next, base-pair symbols {A,C,G,T} are encoded into a two-bit representation. If a sequence contains an ambiguous character (N) it is split into the parts preceding and following this character. Sequences or sequence parts which are shorter than <italic>k</italic>
and therefore do not contain any complete <italic>k</italic>
-mer are disregarded. Next, the sequence data of a batch is transferred to graphics memory for classification.</p>
<p>Aside from higher transfer speeds the use of page-locked memory allows for batches to be processed asynchronously by the GPU. This means after a CPU thread has prepared all sequence data of a batch, the batch is scheduled for classification on the GPU and the CPU can continue with the next batch without having to wait for the GPU to finish (see Fig. <xref rid="Fig2" ref-type="fig">2</xref>
).
<fig id="Fig2"><label>Fig. 2</label>
<caption><p>Asynchronous execution on the GPU. The processing on the GPU can be performed asynchronously to the CPU. Memory transfers (<italic>green arrows</italic>
) and classification are handled by the GPU while the CPU already prepares the next batch</p>
</caption>
<graphic xlink:href="12859_2016_1434_Fig2_HTML" id="MO2"></graphic>
</fig>
</p>
<p>The classification process consists of multiple steps. First each GPU queries the batches against the database part it currently holds. Subsequently, the results of all individual GPUs are collected. If the database doesn’t fit into graphics memory in one piece, we swap database chunks and query the batches again. The number of cycles we need depends on the database size and the amount of available GPU memory. After the whole database has been consulted and the results have been merged, we find the two best targets for each NGS read. Identical Analogous to CLARK, we use the target with the most hits to classify a read and calculate the confidence score from the hit counts of the best and second best target. Figure <xref rid="Fig3" ref-type="fig">3</xref>
illustrates the classification cycle for a single batch on four GPUs.
<fig id="Fig3"><label>Fig. 3</label>
<caption><p>Classification cycle for a single batch. Each GPU queries the batch against a different database part. Then we merge the query results of the individual GPUs with the result of the previous cycle. After we merged all results in the last cycle, we can finally get the classification result. All kernels are explained in Section <xref rid="Sec5" ref-type="sec">CUDA implementation</xref>
</p>
</caption>
<graphic xlink:href="12859_2016_1434_Fig3_HTML" id="MO3"></graphic>
</fig>
</p>
</sec>
<sec id="Sec5"><title>CUDA implementation</title>
<p>The CUDA programming model requires the use of kernels, which can be executed in parallel by a large number of threads on the GPU. The threads are grouped in blocks, where each block has access to a fixed amount of shared memory. This fast but small memory can be accessed simultaneously by all threads of a block for caching data from the global graphics memory or to store intermediate results. A significant speed-up can be achieved compared to repeatedly accessing the same global memory region. The drawback of the limited amount of shared memory is that less blocks can be processed concurrently if they require too much memory each. In the following we describe the CUDA kernels we have implemented for the classification described above.</p>
<sec id="Sec6"><title>Query kernel</title>
<p>The query kernel uses one thread block for each sequence (NGS read). The threads in the block first initialize the counters for all targets (reference genomes) in shared memory. Subsequently, they load the sequence data into shared memory in a coalesced manner. CUDA threads construct consecutive <italic>k</italic>
-mers from the sequence, where each thread is responsible for a single <italic>k</italic>
-mer at a time. Each thread compares the <italic>k</italic>
-mer with its reverse complement to determines the canonical <italic>k</italic>
-mer. The resulting <italic>k</italic>
-mer is queried against the database.</p>
<p>The query is successful if the <italic>k</italic>
-mer has been found in the part of the database currently available to the GPU. In this case a target scores a hit and we increment the hit counter for this target. Here we have to use an atomic add operation, because queries of multiple threads might need to update the counter of the same target. Each atomic operation covers two neighboring counters, because CUDA atomics operate with at least 32 bits and we use 16-bit variables for the counters to minimize shared memory consumption. The query kernel is illustrated in Fig. <xref rid="Fig4" ref-type="fig">4</xref>
.
<fig id="Fig4"><label>Fig. 4</label>
<caption><p>Query kernel. <italic>(1)</italic>
The threads load the sequence data, <italic>(2)</italic>
construct the k-mers and <italic>(3)</italic>
query the database. <italic>(4)</italic>
Hits are scored in shared memory first, <italic>(5)</italic>
the compact results get transferred to global memory</p>
</caption>
<graphic xlink:href="12859_2016_1434_Fig4_HTML" id="MO4"></graphic>
</fig>
</p>
<p>After all <italic>k</italic>
-mers have been queried, the threads perform a parallel compaction [<xref ref-type="bibr" rid="CR16">16</xref>
] of the target scores in shared memory. This means that all non-zero counters are grouped together to store them efficiently. All counters of value zero offer no additional information and do not need to be saved. The compact results are written to global memory. This strategy greatly reduces the storage space needed as well as the number of accesses to global graphics memory.</p>
<p>In-between the steps we have to synchronize the threads of a block to ensure that all threads have performed the instructions up to this point.</p>
</sec>
<sec id="Sec7"><title>Merge kernel</title>
<p>The merge kernel is used to combine the compacted target scores. Every call of the kernel merges the results of two GPUs into one, so we can perform a parallel reduction of the results in <inline-formula id="IEq1"><alternatives><tex-math id="M1">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\mathcal O(\log _{2} d)$\end{document}</tex-math>
<mml:math id="M2"><mml:mi mathvariant="script">O</mml:mi>
<mml:mo>(</mml:mo>
<mml:munder><mml:mrow><mml:mo>log</mml:mo>
</mml:mrow>
<mml:mrow><mml:mn>2</mml:mn>
</mml:mrow>
</mml:munder>
<mml:mi>d</mml:mi>
<mml:mo>)</mml:mo>
</mml:math>
<inline-graphic xlink:href="12859_2016_1434_Article_IEq1.gif"></inline-graphic>
</alternatives>
</inline-formula>
steps, where <italic>d</italic>
is the number of GPUs we use for classification. Each thread in the kernel processes the scores of one sequence. If we have to swap database chunks, the combined scores for each batch are stored in page-locked host memory. After another part has been queried, the results are merged with the previous scores. The merge kernel is illustrated in Fig. <xref rid="Fig5" ref-type="fig">5</xref>
.
<fig id="Fig5"><label>Fig. 5</label>
<caption><p>Merge kernel. Each thread combines two compacted target scores for the same sequence into one</p>
</caption>
<graphic xlink:href="12859_2016_1434_Fig5_HTML" id="MO5"></graphic>
</fig>
</p>
</sec>
<sec id="Sec8"><title>Result kernel</title>
<p>The result kernel concludes the GPU stage of the classification process. After all database parts have been examined and the target scores have been merged, we identify the two targets with the highest hit counts for each input sequence. Similar to the merge kernel, we use one thread per sequence to scan the scores (see Fig. <xref rid="Fig6" ref-type="fig">6</xref>
). After the result kernel has finished, the results are copied back to the host for printing.
<fig id="Fig6"><label>Fig. 6</label>
<caption><p>Result kernel. Each thread gets the index and the score of the two best targets for a sequence. It also calculates the sum of all scores for this sequence</p>
</caption>
<graphic xlink:href="12859_2016_1434_Fig6_HTML" id="MO6"></graphic>
</fig>
</p>
</sec>
</sec>
<sec id="Sec9"><title>Printing results</title>
<p>After the CPU has scheduled all batches for GPU processing and managed all database swaps, it is ready to print results to an output file. The printing can start after the results of the first batch are available in host memory. Typically the GPUs finish the next batch before the CPU is done printing, so the output process can continue without delay.</p>
<p>In the case that we do not have to swap database parts and each batch is only queried once, we have decided to start printing earlier. After the first batch is scheduled, one CPU thread is immediately assigned to printing while the others continue to process the input file. Thus, we avoid the CPU running idle and further increase the overall execution speed.</p>
<p>While we do not offer all different modes of CLARK, it is still possible to change the sampling factor for loading the database. This can help to increase the speed of the program. Additionally, we provide a light version of our program. It uses a significantly smaller database in order to be executed on systems with a small amount of memory. In our case this involves a CPU with about 4 GB of RAM and a CUDA-enabled GPU with at least 1 GB of graphics memory.</p>
</sec>
</sec>
<sec id="Sec10"><title>Results and discussion</title>
<sec id="Sec11"><title>Experimental setup</title>
<p>Experimental results have been obtained by running CLARK (version 1.2.3), cuCLARK and Kraken (version 0.10.5-beta) on a workstation featuring an Intel Xeon E5-2683v4 16-core processor, 128 GB of DDR4 RAM and a CUDA-capable GPU, namely a Pascal-based NVIDIA Titan X with 12 GB of GDRR5X graphics memory. Additionally, we have tested the scalability of cuCLARK with an Intel Xeon E5-2670v2 CPU with 64 GB of DDR3 RAM and four Kepler-based NVIDIA GeForce GTX Titan GPUs each providing 6 GB of GDDR5 video RAM.</p>
<p>To analyze the classification speed of our program we have used simulated metagenome data with different read lengths. The datasets <italic>HiSeq</italic>
and <italic>MiSeq</italic>
have already been used to evaluate the performance of both Kraken [<xref ref-type="bibr" rid="CR7">7</xref>
] and CLARK [<xref ref-type="bibr" rid="CR8">8</xref>
]. We have furthermore created <italic>wgsim200</italic>
and <italic>wgsim250</italic>
with wgsim [<xref ref-type="bibr" rid="CR17">17</xref>
] using default settings. While the first two datasets consist of a combination of bacterial whole-genome shotgun reads originating from the corresponding Illumina sequencing platforms, the other two datasets have been created from ten complete bacterial and archaeal genomes randomly picked from the NCBI RefSeq database. The four sets contain 10 million reads each with an average length of 92 base-pairs (bps) for HiSeq, 157 bps for MiSeq and an equal length of 200 bps and 250 bps for all reads in wgsim200 and wgsim250, respectively.</p>
<p>Additionally, we have created a simulated 454 pyrosequencing dataset <italic>art454</italic>
with ART [<xref ref-type="bibr" rid="CR18">18</xref>
], using its built-in GS FLX Titanium profile. We have further created a simulated dataset <italic>fqIon</italic>
with FASTQSim’s [<xref ref-type="bibr" rid="CR19">19</xref>
] Ion Torrent default characterization. For these two datasets we have used ten randomly selected bacterial and archaeal genomes using a fold coverage of 100x. This resulted in 4,841,892 reads with an average length of 347 bps and 9,626,266 reads with an average 159 bps length, respectively. Note that 454 and Ion Torrent platforms as well as the corresponding simulators produce reads with a much higher variance in length compared to Illumina sequencers. fqIon for example features read lengths ranging from 1 to 264 bps.</p>
</sec>
<sec id="Sec12"><title>Full mode</title>
<p>For the speed comparison, we have executed read classification with CLARK, cuCLARK, and Kraken for the datasets described above. CLARK is run in full mode and Kraken in default mode with preloaded database. We have used the default <italic>k</italic>
-mer length of <italic>k</italic>
=31 for all three programs. We have classified against the NCBI RefSeq [<xref ref-type="bibr" rid="CR20">20</xref>
] database of December 2015 consisting of 2785 bacterial genomes. This corresponds to 683 distinct targets at genus-level and 1463 targets at species-level for CLARK and cuCLARK. Runtime results for both taxonomic levels are reported in the Tables <xref rid="Tab1" ref-type="table">1</xref>
and <xref rid="Tab2" ref-type="table">2</xref>
.
<table-wrap id="Tab1"><label>Table 1</label>
<caption><p>Classification speed of CLARK, Kraken, and cuCLARK at species-level measured in terms of 10<sup>6</sup>
classified sequences (reads) per minute</p>
</caption>
<table frame="hsides" rules="groups"><thead><tr><th align="left"></th>
<th align="left">CPU threads</th>
<th align="left">GPUs</th>
<th align="left">HiSeq Speed</th>
<th align="left">MiSeq Speed</th>
<th align="left">wgsim200 Speed</th>
<th align="left">wgsim250 Speed</th>
<th align="left">art454 Speed</th>
<th align="left">fqIon Speed</th>
</tr>
</thead>
<tbody><tr><td align="left">CLARK</td>
<td align="left">1</td>
<td align="left">-</td>
<td align="left">1.89</td>
<td align="left">0.88</td>
<td align="left">0.68</td>
<td align="left">0.54</td>
<td align="left">0.29</td>
<td align="left">0.74</td>
</tr>
<tr><td align="left">CLARK</td>
<td align="left">16</td>
<td align="left">-</td>
<td align="left">15.74</td>
<td align="left">9.74</td>
<td align="left">8.15</td>
<td align="left">6.82</td>
<td align="left">4.05</td>
<td align="left">9.47</td>
</tr>
<tr><td align="left">Kraken</td>
<td align="left">1</td>
<td align="left">-</td>
<td align="left">2.37</td>
<td align="left">1.33</td>
<td align="left">1.15</td>
<td align="left">0.89</td>
<td align="left">0.64</td>
<td align="left">1.32</td>
</tr>
<tr><td align="left">Kraken</td>
<td align="left">16</td>
<td align="left">-</td>
<td align="left">12.6</td>
<td align="left">13.74</td>
<td align="left">14.45</td>
<td align="left">11.95</td>
<td align="left">8.75</td>
<td align="left">15.48</td>
</tr>
<tr><td align="left">cuCLARK</td>
<td align="left">8</td>
<td align="left">1</td>
<td align="left">49.69</td>
<td align="left">42.27</td>
<td align="left">38.02</td>
<td align="left">34.5</td>
<td align="left">26.84</td>
<td align="left">41.01</td>
</tr>
<tr><td align="left">cuCLARK/CLARK</td>
<td align="left"></td>
<td align="left"></td>
<td align="left">3.2</td>
<td align="left">4.3</td>
<td align="left">4.7</td>
<td align="left">5.1</td>
<td align="left">6.6</td>
<td align="left">4.3</td>
</tr>
<tr><td align="left">cuCLARK/Kraken</td>
<td align="left"></td>
<td align="left"></td>
<td align="left">3.9</td>
<td align="left">3.1</td>
<td align="left">2.6</td>
<td align="left">2.9</td>
<td align="left">3.1</td>
<td align="left">2.7</td>
</tr>
</tbody>
</table>
<table-wrap-foot><p>The bottom two rows report the speedups between cuCLARK over CLARK and Kraken executed with 16 CPU threads</p>
</table-wrap-foot>
</table-wrap>
<table-wrap id="Tab2"><label>Table 2</label>
<caption><p>Classification speed of CLARK, Kraken, and cuCLARK at genus-level measured in terms of 10<sup>6</sup>
classified sequences (reads) per minute</p>
</caption>
<table frame="hsides" rules="groups"><thead><tr><th align="left"></th>
<th align="left">CPU threads</th>
<th align="left">GPUs</th>
<th align="left">HiSeq Speed</th>
<th align="left">MiSeq Speed</th>
<th align="left">wgsim200 Speed</th>
<th align="left">wgsim250 Speed</th>
<th align="left">art454 Speed</th>
<th align="left">fqIon Speed</th>
</tr>
</thead>
<tbody><tr><td align="left">CLARK</td>
<td align="left">1</td>
<td align="left">-</td>
<td align="left">1.66</td>
<td align="left">0.75</td>
<td align="left">0.65</td>
<td align="left">0.51</td>
<td align="left">0.26</td>
<td align="left">0.68</td>
</tr>
<tr><td align="left">CLARK</td>
<td align="left">16</td>
<td align="left">-</td>
<td align="left">13.46</td>
<td align="left">8.96</td>
<td align="left">8.07</td>
<td align="left">6.52</td>
<td align="left">3.9</td>
<td align="left">9.4</td>
</tr>
<tr><td align="left">Kraken</td>
<td align="left">1</td>
<td align="left">-</td>
<td align="left">2.37</td>
<td align="left">1.33</td>
<td align="left">1.15</td>
<td align="left">0.89</td>
<td align="left">0.64</td>
<td align="left">1.32</td>
</tr>
<tr><td align="left">Kraken</td>
<td align="left">16</td>
<td align="left">-</td>
<td align="left">12.6</td>
<td align="left">13.74</td>
<td align="left">14.45</td>
<td align="left">11.95</td>
<td align="left">8.75</td>
<td align="left">15.48</td>
</tr>
<tr><td align="left">cuCLARK</td>
<td align="left">8</td>
<td align="left">1</td>
<td align="left">49.27</td>
<td align="left">41.22</td>
<td align="left">37.23</td>
<td align="left">33.89</td>
<td align="left">25.13</td>
<td align="left">39.93</td>
</tr>
<tr><td align="left">cuCLARK/CLARK</td>
<td align="left"></td>
<td align="left"></td>
<td align="left">3.7</td>
<td align="left">4.6</td>
<td align="left">4.6</td>
<td align="left">5.2</td>
<td align="left">6.4</td>
<td align="left">4.2</td>
</tr>
<tr><td align="left">cuCLARK/Kraken</td>
<td align="left"></td>
<td align="left"></td>
<td align="left">3.9</td>
<td align="left">3</td>
<td align="left">2.6</td>
<td align="left">2.8</td>
<td align="left">2.9</td>
<td align="left">2.6</td>
</tr>
</tbody>
</table>
<table-wrap-foot><p>The two bottom rows report the speedups of cuCLARK over CLARK and Kraken executed with 16 CPU threads</p>
</table-wrap-foot>
</table-wrap>
</p>
<p>Classification speed in the tables are measured in terms of 10<sup>6</sup>
classified sequences (reads) per minute. We report the best results of three consecutive runs of the programs with the same input. This was done in order to mitigate runtime differences caused by I/O or cache problems. The measurements do not take the building or loading time of the database into account. The three programs have been executed in single- and multi-threaded configurations. cuCLARK has been executed on a Titan X for single GPU experiments.</p>
<p>For cuCLARK we have decided to process the input files in 16 batches, so the space required for each batch is small enough to leave most graphics memory for the database parts. Since the Titan X’s graphics memory (12 GB) is not sufficient to fit the complete databases of size 38.5 GB (species-level) and 39.91 GB (genus-level) respectively, we need four cycles to process the whole database.</p>
<p>The measurements in Table <xref rid="Tab1" ref-type="table">1</xref>
show that classification speed generally decreases with increasing read length, since longer reads contain more <italic>k</italic>
-mers. CLARK and Kraken both scale reasonably well with the number of CPU threads. For instance, CLARK is able to achieve speedups between 8.4-14.0 for the tested datasets when running with 16 threads compared to single-threaded execution. Scaling improves with longer read length.</p>
<p>For cuCLARK we see the same behavior as for CLARK, that classification speeds depend on the sequence length. For our program, however, the differences between the data sets are not as big. For example it is only 18% slower for MiSeq compared to HiSeq.</p>
<p>To further increase the speed of cuCLARK, we use multiple CPU threads to process the input files. We do not change the number of batches, that each file is split into, but instead distribute them among several CPU threads. This way we can provide the GPUs with batches of data at a faster rate which results in a higher overall classification speed. Using eight CPU threads and one GPU, cuCLARK achieves speed-ups of between 3.2 and 6.6 (3.7 and 6.4) when compared to multi-threaded CLARK using 16 CPU threads for species (genus) level classification. The speed-up increases with the read length of the data sets. The genus-level classification speeds for CLARK and cuCLARK are slightly slower than for species level. This is caused by the larger database, which leads to longer queries on average.</p>
<p>If executed with a low number of threads, Kraken is 1.3-1.8 times faster than CLARK at the species- or genus-level with the same thread count. For MiSeq, wgsim200„ wgsim250 and fqIon Kraken using 16 threads is still 1.4-1.8 times faster than CLARK with the same number of threads. Kraken performs especially well for art454, where it is 2.2-2.5 times faster than CLARK in single- and multi-threaded execution. cuCLARK is 2.6-3.9 (2.6-3.1) times faster than Kraken running with 16 CPU threads for species (genus)-level classification.</p>
</sec>
<sec id="Sec13"><title>Dependency On database size</title>
<p>When loading the database with a sampling factor of <italic>s</italic>
=6, we can investigate the performance on smaller database sizes. A sampling factor of <italic>s</italic>
=1 is equivalent to the default behaviour of loading the whole database. Using a sampling factor <italic>s</italic>
>1 whole buckets are skipped and thus many queries result in an immediate miss. As a result, the average query speed increases. Due to this, CLARK is able to improve its runtime by 58% for the execution with 16 threads. Moreover, it needs about 52 GB less RAM for the classification.</p>
<p>For cuCLARK the main benefit of the smaller database is that we can completely fit it into graphics memory. Thus, we only need to query the batches once and do not need to swap database parts on-the-fly. We observe that the gain in speed for the single-threaded execution is relatively small. Therefore, the speed of cuCLARK is obviously bound by I/O operations executed on the CPU. For this reason we have implemented the early printing feature for the multi-threaded mode. During concurrent execution we can hide parts of the time needed for the file output and thus increase overall speed. Using multiple CPU threads we obtain a speedup of 51%-53% instead of only 37% improvement over the single-threaded version. Note that printing early is only possible if we do not need to query the batches against another database part.</p>
<p>Among all sampling factors the main memory consumption of CLARK is in general reasonably higher than cuCLARK’s although they both store the same database entries and consequently produce compliant results. This can be explained as follows. CLARK’s nested data structures require more bytes for the storage of individual buckets due to sub-optimal memory alignment. In fact we use less than half the amount of RAM as CLARK by consecutively storing the buckets in one contiguous array. This reduction in memory consumption can be observed for the whole database as well as the sampled one (see Table <xref rid="Tab3" ref-type="table">3</xref>
).
<table-wrap id="Tab3"><label>Table 3</label>
<caption><p>Classification speed for different sampling factors at species-level for the HiSeq dataset in terms of 10<sup>6</sup>
sequences/min and corresponding main memory consumption</p>
</caption>
<table frame="hsides" rules="groups"><thead><tr><th align="left">HiSeq</th>
<th align="left">CPU threads</th>
<th align="left">GPUs</th>
<th align="left">Speed</th>
<th align="left">RAM usage</th>
<th align="left">GRAM usage</th>
</tr>
</thead>
<tbody><tr><td align="left">CLARK (s=1)</td>
<td align="left">16</td>
<td align="left">-</td>
<td align="left">15.74</td>
<td align="left">86.5 GB</td>
<td align="left">-</td>
</tr>
<tr><td align="left">CLARK (s=6)</td>
<td align="left">16</td>
<td align="left">-</td>
<td align="left">24.8</td>
<td align="left">34.7 GB</td>
<td align="left">-</td>
</tr>
<tr><td align="left">Kraken</td>
<td align="left">16</td>
<td align="left">-</td>
<td align="left">12.6</td>
<td align="left">73.8 GB</td>
<td align="left">-</td>
</tr>
<tr><td align="left">cuCLARK (s=1)</td>
<td align="left">1</td>
<td align="left">1</td>
<td align="left">44.26</td>
<td align="left">39.9 GB</td>
<td align="left">9.7 GB</td>
</tr>
<tr><td align="left">cuCLARK (s=1)</td>
<td align="left">8</td>
<td align="left">1</td>
<td align="left">49.69</td>
<td align="left">39.9 GB</td>
<td align="left">9.7 GB</td>
</tr>
<tr><td align="left">cuCLARK (s=6)</td>
<td align="left">1</td>
<td align="left">1</td>
<td align="left">60.51</td>
<td align="left">14.1 GB</td>
<td align="left">11.9 GB</td>
</tr>
<tr><td align="left">cuCLARK (s=6)</td>
<td align="left">8</td>
<td align="left">1</td>
<td align="left">75.96</td>
<td align="left">14.1 GB</td>
<td align="left">11.9 GB</td>
</tr>
</tbody>
</table>
</table-wrap>
</p>
</sec>
<sec id="Sec14"><title>Light versions</title>
<p>Furthermore, we have classified the data sets with the light versions of CLARK and cuCLARK, which construct a much smaller database and need less than 4 GB of RAM. We have used the full mode for CLARK light and default <italic>k</italic>
-mer length (<italic>k</italic>
=27). For cuCLARK light the reduced database is smaller than 720 MB and leaves enough space for batch data even on graphics cards with only 1 GB of memory. The resulting speeds for the light versions are presented in Table <xref rid="Tab4" ref-type="table">4</xref>
.
<table-wrap id="Tab4"><label>Table 4</label>
<caption><p>Classification speed comparison between CLARK light and cuCLARK light at species-level in terms of 10<sup>6</sup>
classified sequences/min</p>
</caption>
<table frame="hsides" rules="groups"><thead><tr><th align="left"></th>
<th align="left">CPU threads</th>
<th align="left">GPUs</th>
<th align="left">HiSeq Speed</th>
<th align="left">MiSeq Speed</th>
<th align="left">wgsim200 Speed</th>
<th align="left">wgsim250 Speed</th>
<th align="left">art454 Speed</th>
<th align="left">fqIon Speed</th>
</tr>
</thead>
<tbody><tr><td align="left">CLARK light</td>
<td align="left">1</td>
<td align="left">-</td>
<td align="left">5.85</td>
<td align="left">3.06</td>
<td align="left">2.64</td>
<td align="left">2.08</td>
<td align="left">1.08</td>
<td align="left">2.66</td>
</tr>
<tr><td align="left">CLARK light</td>
<td align="left">16</td>
<td align="left">-</td>
<td align="left">27.32</td>
<td align="left">19.48</td>
<td align="left">16.47</td>
<td align="left">13.95</td>
<td align="left">8.21</td>
<td align="left">18.45</td>
</tr>
<tr><td align="left">cuCLARK light</td>
<td align="left">8</td>
<td align="left">1</td>
<td align="left">75.46</td>
<td align="left">69.76</td>
<td align="left">62.62</td>
<td align="left">59.23</td>
<td align="left">54.12</td>
<td align="left">65.27</td>
</tr>
<tr><td align="left">cuCLARK light/CLARK light</td>
<td align="left"></td>
<td align="left"></td>
<td align="left">2.8</td>
<td align="left">3.6</td>
<td align="left">3.8</td>
<td align="left">4.2</td>
<td align="left">6.6</td>
<td align="left">3.5</td>
</tr>
</tbody>
</table>
<table-wrap-foot><p>The bottom row reports the speedup of cuCALRK light compared to CLARK light executed with 16 CPU threads</p>
</table-wrap-foot>
</table-wrap>
</p>
</sec>
<sec id="Sec15"><title>Scalability</title>
<p>In order to investigate the scalability of our implementation we have run cuCLARK on multiple GPUs attached to one workstation. The up to four Kepler-based GeForce GTX Titans each provide 6 GB of video RAM. The increased amount of total memory allows for the querying of a larger part of the database at once resulting in less cycles to process the whole database. Using a single GPU we need seven cycles to process the whole species database, four cycles for two GPUs and two cycles for four GPUs, respectively.</p>
<p>Since I/O is independent of the number of used GPUs, the higher speeds observed when using multiple GPUs result from the simultaneous processing of database parts. This leads to a reduced number of work steps per graphics device. The speed-up increases with the read length of the datasets, as depicted in Fig. <xref rid="Fig7" ref-type="fig">7</xref>
. Due to the increased length of reads the classification can attain a higher efficiency. We achieve a speedup of 1.4 to 1.8 with two GPUs and a speedup of 1.8 to 2.6 with four GPUs compared to the classification on one GPU.
<fig id="Fig7"><label>Fig. 7</label>
<caption><p>cuCLARK GPU scaling. Speed-up of cuCLARK from one to two and four GPUs for the different datasets. Four NVIDIA GeForce GTX Titan with 6 GB graphic memory were used for this experiment</p>
</caption>
<graphic xlink:href="12859_2016_1434_Fig7_HTML" id="MO7"></graphic>
</fig>
</p>
</sec>
</sec>
<sec id="Sec16" sec-type="conclusion"><title>Conclusion</title>
<p>The rapidly growing field of metagenomic sequencing creates an urgent need for exceedingly fast and precise computational tools to analyze the ever-increasing amount of recorded data. In this context, taxonomic read assignment is a frequently repeated and important task. Thus, novel short read classifiers relying on efficient algorithmic design specifically suited for the execution on modern hardware accelerators are of high importance for academic research and commercial bioinformatics solutions.</p>
<p>We have introduced cuCLARK, a hybrid metagenomic read classifier executed on multi-core CPU and massively parallel GPUs. It can assign taxonomic labels at the speed of up to 50 million reads per minute using a single GPU, while producing identical results to the established CLARK tool.</p>
<p>The execution speed can be maximized if the available graphics devices provide enough memory to fit the entire database of discriminative <italic>k</italic>
-mers. In this case asynchronous read classification on GPUs can be accelerated to an extent that the program’s speed is solely limited by the I/O operations executed on the CPU. Therefore, multi-threaded processing of input and output allows for the further increasing of performance since CPU-based I/O can be efficiently overlapped with GPU-based classification.</p>
<p>If cuCLARK is executed on GPUs with relatively small video RAM sizes, it needs several classification cycles to process the whole database. This leads to lower speeds, because the input sequences need to be queried successively against multiple parts of the database. In our experiments we needed four cycles, when using a GPU with 12 GB of memory and the NCBI RefSeq database of December 2015. In this configuration achieved speedups for species-level classification range between 3.2 and 6.6 (2.6 and 3.3) on a single Titan X GPU compared to CLARK (Kraken) when executed with 16 threads on a Xeon E5-2683v4 16-core CPU.</p>
<p>The light mode of cuCLARK is able to reach even higher speeds than the full version. It proved to be a superior alternative to CLARK light if the user can provide a suitable graphics device. cuCLARK light is up to 6.6 times faster on a single GPU than CLARK light using 16 CPU threads.</p>
<p>As our experiments have shown, the classification speed of our program heavily correlates with the amount of available video RAM and the memory bandwidth. Future accelerator cards from the professional Tesla branch, e.g the to be released Tesla P100 chip, will feature 16 GB of high bandwidth stacked memory [<xref ref-type="bibr" rid="CR21">21</xref>
]. This novel memory type allows for significantly higher bandwidths in comparison to current GDDR5 and GDDR5X modules. Thus a possible direction of future research could be the investigation of the impact of high bandwidth memory on the performance of hash-based short read classifiers.</p>
</sec>
</body>
<back><glossary><title>Abbreviations</title>
<def-list><def-item><term>bps</term>
<def><p>Base pairs</p>
</def>
</def-item>
<def-item><term>CPU</term>
<def><p>Central processing unit</p>
</def>
</def-item>
<def-item><term>CUDA</term>
<def><p>Compute unified device architecture</p>
</def>
</def-item>
<def-item><term>GPU</term>
<def><p>Graphics processing unit</p>
</def>
</def-item>
<def-item><term>LCA</term>
<def><p>Lowest common ancestor</p>
</def>
</def-item>
<def-item><term>NCBI</term>
<def><p>National center for biotechnology information</p>
</def>
</def-item>
<def-item><term>NGS</term>
<def><p>Next-generation sequencing</p>
</def>
</def-item>
<def-item><term>PCIe</term>
<def><p>Peripheral component interconnect express</p>
</def>
</def-item>
</def-list>
</glossary>
<ack><title>Acknowledgements</title>
<p>Not applicable.</p>
<sec id="d29e1661"><title>Funding</title>
<p>Not applicable.</p>
</sec>
<sec id="d29e1666"><title>Availability of data and materials</title>
<p><list list-type="bullet"><list-item><p><bold>Project name:</bold>
cuCLARK</p>
</list-item>
<list-item><p><bold>Project home page:</bold>
https://github.com/funatiq/cuclark</p>
</list-item>
<list-item><p><bold>Operating system(s):</bold>
Linux 64-bit</p>
</list-item>
<list-item><p><bold>Programming language:</bold>
C++, CUDA</p>
</list-item>
<list-item><p><bold>Other requirements:</bold>
CUDA-capable GPU</p>
</list-item>
<list-item><p><bold>License:</bold>
GNU GPL</p>
</list-item>
<list-item><p><bold>Any restrictions to use by non-academics:</bold>
None</p>
</list-item>
</list>
</p>
</sec>
<sec id="d29e1715"><title>Authors’ contributions</title>
<p>RK implemented and tested cuCLARK, performed the experiments and wrote the draft of the manuscript. BS proposed the project. BS, CH and AM supervised the project and edited the manuscript. All authors read and approved the final manuscript.</p>
</sec>
<sec id="d29e1720"><title>Consent for publication</title>
<p>Not applicable.</p>
</sec>
<sec id="d29e1725"><title>Ethics approval and consent to participate</title>
<p>Not applicable.</p>
</sec>
</ack>
<ref-list id="Bib1"><title>References</title>
<ref id="CR1"><label>1</label>
<mixed-citation publication-type="other">Huttenhower C, Gevers D, Knight R, Abubucker S, Badger JH, Chinwalla AT. Structure, function and diversity of the healthy human microbiome. Nature. 2012:486. doi:10.1038/nature11234.</mixed-citation>
</ref>
<ref id="CR2"><label>2</label>
<mixed-citation publication-type="other">Venter JC, Remington K, Heidelberg JF, Halpern AL, Rusch D, Eisen JA. Environmental genome shotgun sequencing of the sargasso sea. Science. 2004:304. doi:10.1126/science.1093857.</mixed-citation>
</ref>
<ref id="CR3"><label>3</label>
<mixed-citation publication-type="other">Altschul SF, Gish W, Miller W, Myers EW, Lipman DJ. Basic local alignment search tool. J Mol Biol. 1990:215. doi:10.1016/S0022-2836(05)80360-2.</mixed-citation>
</ref>
<ref id="CR4"><label>4</label>
<mixed-citation publication-type="other">Huson DH, Auch AF, Qi J, Schuster SC. MEGAN analysis of metagenomic data. Genome Res. 2007:17. doi:10.1101/gr.5969107.</mixed-citation>
</ref>
<ref id="CR5"><label>5</label>
<mixed-citation publication-type="other">Brady A, Salzberg S. PhymmBL expanded: confidence scores, custom databases, parallelization and more. Nat Methods. 2011:8. doi:10.1038/nmeth0511-367.</mixed-citation>
</ref>
<ref id="CR6"><label>6</label>
<mixed-citation publication-type="other">Rosen GL, Reichenberger ER, Rosenfeld AM. NBC: the naive bayes classification tool webserver for taxonomic classification of metagenomic reads. Bioinformatics. 2011:27. doi:10.1093/bioinformatics/btq619.</mixed-citation>
</ref>
<ref id="CR7"><label>7</label>
<mixed-citation publication-type="other">Wood D, Salzberg S. Kraken: ultrafast metagenomic sequence classification using exact alignments. Genome Biol. 2014:15. doi:10.1186/gb-2014-15-3-r46.</mixed-citation>
</ref>
<ref id="CR8"><label>8</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Ounit</surname>
<given-names>R</given-names>
</name>
<name><surname>Wanamaker</surname>
<given-names>S</given-names>
</name>
<name><surname>Close</surname>
<given-names>TJ</given-names>
</name>
<name><surname>Lonardi</surname>
<given-names>S</given-names>
</name>
</person-group>
<article-title>CLARK: fast and accurate classification of metagenomic and genomic sequences using discriminative k-mers</article-title>
<source>BMC Genomics</source>
<year>2015</year>
<volume>16</volume>
<issue>1</issue>
<fpage>1</fpage>
<lpage>13</lpage>
<pub-id pub-id-type="doi">10.1186/s12864-015-1419-2</pub-id>
<pub-id pub-id-type="pmid">25553907</pub-id>
</element-citation>
</ref>
<ref id="CR9"><label>9</label>
<mixed-citation publication-type="other">Lindgreen S, Adair KL, Gardner PP. An evaluation of the accuracy and speed of metagenome analysis tools. Sci Rep. 2016:6. doi:10.1038/srep19233.</mixed-citation>
</ref>
<ref id="CR10"><label>10</label>
<mixed-citation publication-type="other">Lu J, Breitwieser FP, Thielen P, Salzberg SL. Bracken: Estimating species abundance in metagenomics data. bioRxiv. 2016:051813. doi:10.1101/051813.</mixed-citation>
</ref>
<ref id="CR11"><label>11</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Wilton</surname>
<given-names>R</given-names>
</name>
<name><surname>Budavari</surname>
<given-names>T</given-names>
</name>
<name><surname>Langmead</surname>
<given-names>B</given-names>
</name>
<name><surname>Wheelan</surname>
<given-names>SJ</given-names>
</name>
<name><surname>Salzberg</surname>
<given-names>SL</given-names>
</name>
<name><surname>Szalay</surname>
<given-names>AS</given-names>
</name>
</person-group>
<article-title>Arioc: high-throughput read alignment with gpu-accelerated exploration of the seed-and-extend search space</article-title>
<source>PeerJ</source>
<year>2015</year>
<volume>3</volume>
<fpage>808</fpage>
<pub-id pub-id-type="doi">10.7717/peerj.808</pub-id>
</element-citation>
</ref>
<ref id="CR12"><label>12</label>
<mixed-citation publication-type="other">Medina I, Tárraga J, Martínez H, Barrachina S, Castillo M, Paschall J, Salavert-Torres J, Blanquer-Espert I, Hernández-García V, Quintana-Ortí ES, et al.Highly sensitive and ultrafast read mapping for rna-seq analysis. DNA Research; 23(2).</mixed-citation>
</ref>
<ref id="CR13"><label>13</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Liu</surname>
<given-names>Y</given-names>
</name>
<name><surname>Schmidt</surname>
<given-names>B</given-names>
</name>
<name><surname>Maskell</surname>
<given-names>DL</given-names>
</name>
</person-group>
<article-title>Decgpu: distributed error correction on massively parallel graphics processing units using cuda and mpi</article-title>
<source>BMC Bioinforma</source>
<year>2011</year>
<volume>12</volume>
<issue>1</issue>
<fpage>1</fpage>
<pub-id pub-id-type="doi">10.1186/1471-2105-12-1</pub-id>
</element-citation>
</ref>
<ref id="CR14"><label>14</label>
<mixed-citation publication-type="other">Erbert M, Rechner S, Müller-Hannemann M. Gerbil: A Fast and Memory-Efficient k-mer Counter with GPU-Support. CoRR. 2016; abs/1607.06618: <ext-link ext-link-type="uri" xlink:href="http://arxiv.org/abs/1607.06618">http://arxiv.org/abs/1607.06618</ext-link>
.</mixed-citation>
</ref>
<ref id="CR15"><label>15</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Li</surname>
<given-names>D</given-names>
</name>
<name><surname>Liu</surname>
<given-names>CM</given-names>
</name>
<name><surname>Luo</surname>
<given-names>R</given-names>
</name>
<name><surname>Sadakane</surname>
<given-names>K</given-names>
</name>
<name><surname>Lam</surname>
<given-names>TW</given-names>
</name>
</person-group>
<article-title>Megahit: an ultra-fast single-node solution for large and complex metagenomics assembly via succinct de bruijn graph</article-title>
<source>Bioinformatics</source>
<year>2015</year>
<volume>31</volume>
<issue>10</issue>
<fpage>1674</fpage>
<lpage>6</lpage>
<pub-id pub-id-type="doi">10.1093/bioinformatics/btv033</pub-id>
<pub-id pub-id-type="pmid">25609793</pub-id>
</element-citation>
</ref>
<ref id="CR16"><label>16</label>
<mixed-citation publication-type="other">Spataro D. Stream Compaction on GPU - Efficient Implementation - CUDA. <ext-link ext-link-type="uri" xlink:href="http://www.davidespataro.it/cuda-stream-compaction-efficient-implementation/">http://www.davidespataro.it/cuda-stream-compaction-efficient-implementation/</ext-link>
. Accessed 05 May 2016.</mixed-citation>
</ref>
<ref id="CR17"><label>17</label>
<mixed-citation publication-type="other">Li H. Wgsim. <ext-link ext-link-type="uri" xlink:href="https://github.com/lh3/wgsim">https://github.com/lh3/wgsim</ext-link>
. Accessed 13 July 2016.</mixed-citation>
</ref>
<ref id="CR18"><label>18</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Huang</surname>
<given-names>W</given-names>
</name>
<name><surname>Li</surname>
<given-names>L</given-names>
</name>
<name><surname>Myers</surname>
<given-names>JR</given-names>
</name>
<name><surname>Marth</surname>
<given-names>GT</given-names>
</name>
</person-group>
<article-title>Art: a next-generation sequencing read simulator</article-title>
<source>Bioinformatics</source>
<year>2012</year>
<volume>28</volume>
<issue>4</issue>
<fpage>593</fpage>
<lpage>4</lpage>
<pub-id pub-id-type="doi">10.1093/bioinformatics/btr708</pub-id>
<pub-id pub-id-type="pmid">22199392</pub-id>
</element-citation>
</ref>
<ref id="CR19"><label>19</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Shcherbina</surname>
<given-names>A</given-names>
</name>
</person-group>
<article-title>Fastqsim: platform-independent data characterization and in silico read generation for ngs datasets</article-title>
<source>BMC Research Notes</source>
<year>2014</year>
<volume>7</volume>
<issue>1</issue>
<fpage>533</fpage>
<pub-id pub-id-type="doi">10.1186/1756-0500-7-533</pub-id>
<pub-id pub-id-type="pmid">25123167</pub-id>
</element-citation>
</ref>
<ref id="CR20"><label>20</label>
<mixed-citation publication-type="other">RefSeq: NCBI Reference Sequence Database. <ext-link ext-link-type="uri" xlink:href="ftp://ftp.ncbi.nih.gov/genomes/archive/old_refseq/Bacteria/all.fna.tar.gz">ftp://ftp.ncbi.nih.gov/genomes/archive/old_refseq/Bacteria/all.fna.tar.gz</ext-link>
.</mixed-citation>
</ref>
<ref id="CR21"><label>21</label>
<mixed-citation publication-type="other">Harris M. Inside Pascal: NVIDIA’s Newest Computing Platform. <ext-link ext-link-type="uri" xlink:href="https://devblogs.nvidia.com/parallelforall/inside-pascal/">https://devblogs.nvidia.com/parallelforall/inside-pascal/</ext-link>
. Accessed 05 Apr 2016.</mixed-citation>
</ref>
</ref-list>
</back>
</pmc>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Sante/explor/MersV1/Data/Pmc/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 0002625 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Pmc/Corpus/biblio.hfd -nk 0002625 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Sante |area= MersV1 |flux= Pmc |étape= Corpus |type= RBID |clé= |texte= }}
![]() | This area was generated with Dilib version V0.6.33. | ![]() |