Scalable Genome Assembly through Parallel de Bruijn Graph Construction for Multiple k-mers
Identifieur interne : 000190 ( Pmc/Checkpoint ); précédent : 000189; suivant : 000191Scalable Genome Assembly through Parallel de Bruijn Graph Construction for Multiple k-mers
Auteurs : Kanak Mahadik [États-Unis] ; Christopher Wright [États-Unis] ; Milind Kulkarni [États-Unis] ; Saurabh Bagchi [États-Unis] ; Somali Chaterji [États-Unis]Source :
- Scientific Reports [ 2045-2322 ] ; 2019.
Abstract
Remarkable advancements in high-throughput gene sequencing technologies have led to an exponential growth in the number of sequenced genomes. However, unavailability of highly parallel and scalable
Url:
DOI: 10.1038/s41598-019-51284-9
PubMed: 31619717
PubMed Central: 6795807
Affiliations:
Links toward previous steps (curation, corpus...)
Links to Exploration step
PMC:6795807Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Scalable Genome Assembly through Parallel <italic>de Bruijn</italic> Graph Construction for Multiple <italic>k</italic>-mers</title><author><name sortKey="Mahadik, Kanak" sort="Mahadik, Kanak" uniqKey="Mahadik K" first="Kanak" last="Mahadik">Kanak Mahadik</name><affiliation wicri:level="1"><nlm:aff id="Aff1">Adobe Research, San Jose, USA</nlm:aff><country xml:lang="fr">États-Unis</country><wicri:regionArea>Adobe Research, San Jose</wicri:regionArea><wicri:noRegion>San Jose</wicri:noRegion></affiliation></author><author><name sortKey="Wright, Christopher" sort="Wright, Christopher" uniqKey="Wright C" first="Christopher" last="Wright">Christopher Wright</name><affiliation wicri:level="2"><nlm:aff id="Aff2"><institution-wrap><institution-id institution-id-type="ISNI">0000 0004 1937 2197</institution-id><institution-id institution-id-type="GRID">grid.169077.e</institution-id><institution>Purdue University,</institution></institution-wrap>West Lafayette, IN USA</nlm:aff><country>États-Unis</country><placeName><region type="state">Indiana</region></placeName><wicri:cityArea>West Lafayette</wicri:cityArea></affiliation></author><author><name sortKey="Kulkarni, Milind" sort="Kulkarni, Milind" uniqKey="Kulkarni M" first="Milind" last="Kulkarni">Milind Kulkarni</name><affiliation wicri:level="2"><nlm:aff id="Aff2"><institution-wrap><institution-id institution-id-type="ISNI">0000 0004 1937 2197</institution-id><institution-id institution-id-type="GRID">grid.169077.e</institution-id><institution>Purdue University,</institution></institution-wrap>West Lafayette, IN USA</nlm:aff><country>États-Unis</country><placeName><region type="state">Indiana</region></placeName><wicri:cityArea>West Lafayette</wicri:cityArea></affiliation></author><author><name sortKey="Bagchi, Saurabh" sort="Bagchi, Saurabh" uniqKey="Bagchi S" first="Saurabh" last="Bagchi">Saurabh Bagchi</name><affiliation wicri:level="2"><nlm:aff id="Aff2"><institution-wrap><institution-id institution-id-type="ISNI">0000 0004 1937 2197</institution-id><institution-id institution-id-type="GRID">grid.169077.e</institution-id><institution>Purdue University,</institution></institution-wrap>West Lafayette, IN USA</nlm:aff><country>États-Unis</country><placeName><region type="state">Indiana</region></placeName><wicri:cityArea>West Lafayette</wicri:cityArea></affiliation></author><author><name sortKey="Chaterji, Somali" sort="Chaterji, Somali" uniqKey="Chaterji S" first="Somali" last="Chaterji">Somali Chaterji</name><affiliation wicri:level="2"><nlm:aff id="Aff2"><institution-wrap><institution-id institution-id-type="ISNI">0000 0004 1937 2197</institution-id><institution-id institution-id-type="GRID">grid.169077.e</institution-id><institution>Purdue University,</institution></institution-wrap>West Lafayette, IN USA</nlm:aff><country>États-Unis</country><placeName><region type="state">Indiana</region></placeName><wicri:cityArea>West Lafayette</wicri:cityArea></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">PMC</idno><idno type="pmid">31619717</idno><idno type="pmc">6795807</idno><idno type="url">http://www.ncbi.nlm.nih.gov/pmc/articles/PMC6795807</idno><idno type="RBID">PMC:6795807</idno><idno type="doi">10.1038/s41598-019-51284-9</idno><date when="2019">2019</date><idno type="wicri:Area/Pmc/Corpus">000461</idno><idno type="wicri:explorRef" wicri:stream="Pmc" wicri:step="Corpus" wicri:corpus="PMC">000461</idno><idno type="wicri:Area/Pmc/Curation">000461</idno><idno type="wicri:explorRef" wicri:stream="Pmc" wicri:step="Curation">000461</idno><idno type="wicri:Area/Pmc/Checkpoint">000190</idno><idno type="wicri:explorRef" wicri:stream="Pmc" wicri:step="Checkpoint">000190</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en" level="a" type="main">Scalable Genome Assembly through Parallel <italic>de Bruijn</italic> Graph Construction for Multiple <italic>k</italic>-mers</title><author><name sortKey="Mahadik, Kanak" sort="Mahadik, Kanak" uniqKey="Mahadik K" first="Kanak" last="Mahadik">Kanak Mahadik</name><affiliation wicri:level="1"><nlm:aff id="Aff1">Adobe Research, San Jose, USA</nlm:aff><country xml:lang="fr">États-Unis</country><wicri:regionArea>Adobe Research, San Jose</wicri:regionArea><wicri:noRegion>San Jose</wicri:noRegion></affiliation></author><author><name sortKey="Wright, Christopher" sort="Wright, Christopher" uniqKey="Wright C" first="Christopher" last="Wright">Christopher Wright</name><affiliation wicri:level="2"><nlm:aff id="Aff2"><institution-wrap><institution-id institution-id-type="ISNI">0000 0004 1937 2197</institution-id><institution-id institution-id-type="GRID">grid.169077.e</institution-id><institution>Purdue University,</institution></institution-wrap>West Lafayette, IN USA</nlm:aff><country>États-Unis</country><placeName><region type="state">Indiana</region></placeName><wicri:cityArea>West Lafayette</wicri:cityArea></affiliation></author><author><name sortKey="Kulkarni, Milind" sort="Kulkarni, Milind" uniqKey="Kulkarni M" first="Milind" last="Kulkarni">Milind Kulkarni</name><affiliation wicri:level="2"><nlm:aff id="Aff2"><institution-wrap><institution-id institution-id-type="ISNI">0000 0004 1937 2197</institution-id><institution-id institution-id-type="GRID">grid.169077.e</institution-id><institution>Purdue University,</institution></institution-wrap>West Lafayette, IN USA</nlm:aff><country>États-Unis</country><placeName><region type="state">Indiana</region></placeName><wicri:cityArea>West Lafayette</wicri:cityArea></affiliation></author><author><name sortKey="Bagchi, Saurabh" sort="Bagchi, Saurabh" uniqKey="Bagchi S" first="Saurabh" last="Bagchi">Saurabh Bagchi</name><affiliation wicri:level="2"><nlm:aff id="Aff2"><institution-wrap><institution-id institution-id-type="ISNI">0000 0004 1937 2197</institution-id><institution-id institution-id-type="GRID">grid.169077.e</institution-id><institution>Purdue University,</institution></institution-wrap>West Lafayette, IN USA</nlm:aff><country>États-Unis</country><placeName><region type="state">Indiana</region></placeName><wicri:cityArea>West Lafayette</wicri:cityArea></affiliation></author><author><name sortKey="Chaterji, Somali" sort="Chaterji, Somali" uniqKey="Chaterji S" first="Somali" last="Chaterji">Somali Chaterji</name><affiliation wicri:level="2"><nlm:aff id="Aff2"><institution-wrap><institution-id institution-id-type="ISNI">0000 0004 1937 2197</institution-id><institution-id institution-id-type="GRID">grid.169077.e</institution-id><institution>Purdue University,</institution></institution-wrap>West Lafayette, IN USA</nlm:aff><country>États-Unis</country><placeName><region type="state">Indiana</region></placeName><wicri:cityArea>West Lafayette</wicri:cityArea></affiliation></author></analytic><series><title level="j">Scientific Reports</title><idno type="eISSN">2045-2322</idno><imprint><date when="2019">2019</date></imprint></series></biblStruct></sourceDesc></fileDesc><profileDesc><textClass></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en"><p id="Par1">Remarkable advancements in high-throughput gene sequencing technologies have led to an exponential growth in the number of sequenced genomes. However, unavailability of highly parallel and scalable <italic>de novo</italic> assembly algorithms have hindered biologists attempting to swiftly assemble high-quality complex genomes. Popular <italic>de Bruijn</italic> graph assemblers, such as IDBA-UD, generate high-quality assemblies by iterating over a set of <italic>k</italic>-values used in the construction of de Bruijn graphs (DBG). However, this process of <italic>sequentially</italic> iterating from small to large <italic>k</italic>-values slows down the process of assembly. In this paper, we propose ScalaDBG, which metamorphoses this sequential process, building DBGs for each distinct <italic>k</italic>-value in parallel. We develop an innovative mechanism to “patch” a higher <italic>k</italic>-valued graph with contigs generated from a lower <italic>k</italic>-valued graph. Moreover, ScalaDBG leverages multi-level parallelism, by both scaling up on all cores of a node, and scaling out to multiple nodes <italic>simultaneously</italic>. We demonstrate that ScalaDBG completes assembling the genome faster than IDBA-UD, but with similar accuracy on a variety of datasets (6.8X faster for one of the most complex genome in our dataset).</p></div></front><back><div1 type="bibliography"><listBibl><biblStruct><analytic><author><name sortKey="Stephens, Zd" uniqKey="Stephens Z">ZD Stephens</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Zerbino, Dr" uniqKey="Zerbino D">DR Zerbino</name></author><author><name sortKey="Birney, E" uniqKey="Birney E">E Birney</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Simpson, Jt" uniqKey="Simpson J">JT Simpson</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Gnerre, S" uniqKey="Gnerre S">S Gnerre</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Compeau, Pe" uniqKey="Compeau P">PE Compeau</name></author><author><name sortKey="Pevzner, Pa" uniqKey="Pevzner P">PA Pevzner</name></author><author><name sortKey="Tesler, G" uniqKey="Tesler G">G Tesler</name></author></analytic></biblStruct><biblStruct></biblStruct><biblStruct><analytic><author><name sortKey="Peng, Y" uniqKey="Peng Y">Y Peng</name></author><author><name sortKey="Leung, Hc" uniqKey="Leung H">HC Leung</name></author><author><name sortKey="Yiu, S M" uniqKey="Yiu S">S-M Yiu</name></author><author><name sortKey="Chin, Fy" uniqKey="Chin F">FY Chin</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Luo, R" uniqKey="Luo R">R Luo</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Bankevich, A" uniqKey="Bankevich A">A Bankevich</name></author></analytic></biblStruct><biblStruct></biblStruct><biblStruct></biblStruct><biblStruct></biblStruct><biblStruct><analytic><author><name sortKey="Chaterji, S" uniqKey="Chaterji S">S Chaterji</name></author></analytic></biblStruct><biblStruct></biblStruct><biblStruct></biblStruct><biblStruct><analytic><author><name sortKey="Boisvert, S" uniqKey="Boisvert S">S Boisvert</name></author><author><name sortKey="Laviolette, F" uniqKey="Laviolette F">F Laviolette</name></author><author><name sortKey="Corbeil, J" uniqKey="Corbeil J">J Corbeil</name></author></analytic></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></biblStruct><biblStruct><analytic><author><name sortKey="Peng, Y" uniqKey="Peng Y">Y Peng</name></author><author><name sortKey="Leung, Hc" uniqKey="Leung H">HC Leung</name></author><author><name sortKey="Yiu, S M" uniqKey="Yiu S">S-M Yiu</name></author><author><name sortKey="Chin, Fy" uniqKey="Chin F">FY Chin</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Simpson, Jt" uniqKey="Simpson J">JT Simpson</name></author><author><name sortKey="Durbin, R" uniqKey="Durbin R">R Durbin</name></author></analytic></biblStruct><biblStruct></biblStruct><biblStruct></biblStruct><biblStruct><analytic><author><name sortKey="Gurevich, A" uniqKey="Gurevich A">A Gurevich</name></author><author><name sortKey="Saveliev, V" uniqKey="Saveliev V">V Saveliev</name></author><author><name sortKey="Vyahhi, N" uniqKey="Vyahhi N">N Vyahhi</name></author><author><name sortKey="Tesler, G" uniqKey="Tesler G">G Tesler</name></author></analytic></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">Sci Rep</journal-id><journal-id journal-id-type="iso-abbrev">Sci Rep</journal-id><journal-title-group><journal-title>Scientific Reports</journal-title></journal-title-group><issn pub-type="epub">2045-2322</issn><publisher><publisher-name>Nature Publishing Group UK</publisher-name><publisher-loc>London</publisher-loc></publisher></journal-meta><article-meta><article-id pub-id-type="pmid">31619717</article-id><article-id pub-id-type="pmc">6795807</article-id><article-id pub-id-type="publisher-id">51284</article-id><article-id pub-id-type="doi">10.1038/s41598-019-51284-9</article-id><article-categories><subj-group subj-group-type="heading"><subject>Article</subject></subj-group></article-categories><title-group><article-title>Scalable Genome Assembly through Parallel <italic>de Bruijn</italic> Graph Construction for Multiple <italic>k</italic>-mers</article-title></title-group><contrib-group><contrib contrib-type="author" corresp="yes"><name><surname>Mahadik</surname><given-names>Kanak</given-names></name><address><email>mahadik@adobe.com</email></address><xref ref-type="aff" rid="Aff1">1</xref></contrib><contrib contrib-type="author"><contrib-id contrib-id-type="orcid">http://orcid.org/0000-0002-2592-0407</contrib-id><name><surname>Wright</surname><given-names>Christopher</given-names></name><xref ref-type="aff" rid="Aff2">2</xref></contrib><contrib contrib-type="author"><name><surname>Kulkarni</surname><given-names>Milind</given-names></name><xref ref-type="aff" rid="Aff2">2</xref></contrib><contrib contrib-type="author"><name><surname>Bagchi</surname><given-names>Saurabh</given-names></name><xref ref-type="aff" rid="Aff2">2</xref></contrib><contrib contrib-type="author" corresp="yes"><name><surname>Chaterji</surname><given-names>Somali</given-names></name><address><email>schaterji@schaterji.io</email></address><xref ref-type="aff" rid="Aff2">2</xref></contrib><aff id="Aff1"><label>1</label>Adobe Research, San Jose, USA</aff><aff id="Aff2"><label>2</label><institution-wrap><institution-id institution-id-type="ISNI">0000 0004 1937 2197</institution-id><institution-id institution-id-type="GRID">grid.169077.e</institution-id><institution>Purdue University,</institution></institution-wrap>West Lafayette, IN USA</aff></contrib-group><pub-date pub-type="epub"><day>16</day><month>10</month><year>2019</year></pub-date><pub-date pub-type="pmc-release"><day>16</day><month>10</month><year>2019</year></pub-date><pub-date pub-type="collection"><year>2019</year></pub-date><volume>9</volume><elocation-id>14882</elocation-id><history><date date-type="received"><day>22</day><month>3</month><year>2019</year></date><date date-type="accepted"><day>16</day><month>9</month><year>2019</year></date></history><permissions><copyright-statement>© The Author(s) 2019</copyright-statement><license license-type="OpenAccess"><license-p><bold>Open Access</bold> This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as 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 images or other third party material in this article are included in the article’s Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this license, visit <ext-link ext-link-type="uri" xlink:href="http://creativecommons.org/licenses/by/4.0/">http://creativecommons.org/licenses/by/4.0/</ext-link>.</license-p></license></permissions><abstract id="Abs1"><p id="Par1">Remarkable advancements in high-throughput gene sequencing technologies have led to an exponential growth in the number of sequenced genomes. However, unavailability of highly parallel and scalable <italic>de novo</italic> assembly algorithms have hindered biologists attempting to swiftly assemble high-quality complex genomes. Popular <italic>de Bruijn</italic> graph assemblers, such as IDBA-UD, generate high-quality assemblies by iterating over a set of <italic>k</italic>-values used in the construction of de Bruijn graphs (DBG). However, this process of <italic>sequentially</italic> iterating from small to large <italic>k</italic>-values slows down the process of assembly. In this paper, we propose ScalaDBG, which metamorphoses this sequential process, building DBGs for each distinct <italic>k</italic>-value in parallel. We develop an innovative mechanism to “patch” a higher <italic>k</italic>-valued graph with contigs generated from a lower <italic>k</italic>-valued graph. Moreover, ScalaDBG leverages multi-level parallelism, by both scaling up on all cores of a node, and scaling out to multiple nodes <italic>simultaneously</italic>. We demonstrate that ScalaDBG completes assembling the genome faster than IDBA-UD, but with similar accuracy on a variety of datasets (6.8X faster for one of the most complex genome in our dataset).</p></abstract><kwd-group kwd-group-type="npg-subject"><title>Subject terms</title><kwd>Computational models</kwd><kwd>Computational platforms and environments</kwd></kwd-group><funding-group><award-group><funding-source><institution-wrap><institution-id institution-id-type="FundRef">https://doi.org/10.13039/100000001</institution-id><institution>National Science Foundation (NSF)</institution></institution-wrap></funding-source><award-id>CCF-1337158</award-id><award-id>CCF-1150013</award-id><award-id>CCF-1337158</award-id><principal-award-recipient><name><surname>Kulkarni</surname><given-names>Milind</given-names></name><name><surname>Bagchi</surname><given-names>Saurabh</given-names></name></principal-award-recipient></award-group></funding-group><funding-group><award-group><funding-source><institution-wrap><institution-id institution-id-type="FundRef">https://doi.org/10.13039/100000093</institution-id><institution>U.S. Department of Health & Human Services | NIH | Center for Information Technology (Center for Information Technology, National Institutes of Health)</institution></institution-wrap></funding-source><award-id>1R01AI123037</award-id><principal-award-recipient><name><surname>Chaterji</surname><given-names>Somali</given-names></name></principal-award-recipient></award-group></funding-group><custom-meta-group><custom-meta><meta-name>issue-copyright-statement</meta-name><meta-value>© The Author(s) 2019</meta-value></custom-meta></custom-meta-group></article-meta></front></pmc><affiliations><list><country><li>États-Unis</li></country><region><li>Indiana</li></region></list><tree><country name="États-Unis"><noRegion><name sortKey="Mahadik, Kanak" sort="Mahadik, Kanak" uniqKey="Mahadik K" first="Kanak" last="Mahadik">Kanak Mahadik</name></noRegion><name sortKey="Bagchi, Saurabh" sort="Bagchi, Saurabh" uniqKey="Bagchi S" first="Saurabh" last="Bagchi">Saurabh Bagchi</name><name sortKey="Chaterji, Somali" sort="Chaterji, Somali" uniqKey="Chaterji S" first="Somali" last="Chaterji">Somali Chaterji</name><name sortKey="Kulkarni, Milind" sort="Kulkarni, Milind" uniqKey="Kulkarni M" first="Milind" last="Kulkarni">Milind Kulkarni</name><name sortKey="Wright, Christopher" sort="Wright, Christopher" uniqKey="Wright C" first="Christopher" last="Wright">Christopher Wright</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Sante/explor/MersV1/Data/Pmc/Checkpoint
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000190 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Pmc/Checkpoint/biblio.hfd -nk 000190 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Sante
|area= MersV1
|flux= Pmc
|étape= Checkpoint
|type= RBID
|clé= PMC:6795807
|texte= Scalable Genome Assembly through Parallel de Bruijn Graph Construction for Multiple k-mers
}}
Pour générer des pages wiki
HfdIndexSelect -h $EXPLOR_AREA/Data/Pmc/Checkpoint/RBID.i -Sk "pubmed:31619717" \
| HfdSelect -Kh $EXPLOR_AREA/Data/Pmc/Checkpoint/biblio.hfd \
| NlmPubMed2Wicri -a MersV1
| This area was generated with Dilib version V0.6.33. |  |