From Indexing Data Structures to de Bruijn Graphs
Identifieur interne : 000136 ( Hal/Corpus ); précédent : 000135; suivant : 000137From Indexing Data Structures to de Bruijn Graphs
Auteurs : Bastien Cazaux ; Thierry Lecroq ; Eric RivalsSource :
English descriptors
- mix :
Abstract
New technologies have tremendously increased sequencing throughput com-pared to traditional techniques, thereby complicating DNA assembly. Hence, as-sembly programs resort to de Bruijn graphs (dBG) of k-mers of short reads to compute a set of long contigs, each being a putative segment of the sequenced molecule. Other types of DNA sequence analysis, as well as preprocessing of the reads for assembly, use classical data structures to index all substrings of the reads. It is thus interesting to exhibit algorithms that directly build a dBG of order k from a pre-existing index, and especially a contracted version of the dBG, where non branching paths are condensed into single nodes. Here, we formalise the relation-ship between suffix trees/arrays and dBGs, and exhibit linear time algorithms for constructing the full or contracted dBGs. Finally, we provide hints explaining why this bridge between indexes and dBGs enables to dynamically update the order k of the graph.
Url:
DOI: 10.1007/978-3-319-07566-2_10
Links to Exploration step
Hal:lirmm-01081429Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">From Indexing Data Structures to de Bruijn Graphs</title><author><name sortKey="Cazaux, Bastien" sort="Cazaux, Bastien" uniqKey="Cazaux B" first="Bastien" last="Cazaux">Bastien Cazaux</name><affiliation><hal:affiliation type="researchteam" xml:id="struct-388224" status="VALID"><orgName>Méthodes et Algorithmes pour la Bioinformatique</orgName><orgName type="acronym">MAB</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.lirmm.fr/recherche/equipes/mab</ref></desc><listRelation><relation active="#struct-181" type="direct"></relation><relation name="UMR5506" active="#struct-441569" type="indirect"></relation><relation name="UMR5506" active="#struct-410122" type="indirect"></relation></listRelation><tutelles><tutelle active="#struct-181" type="direct"><org type="laboratory" xml:id="struct-181" status="VALID"><idno type="RNSR">199111950H</idno><orgName>Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier</orgName><orgName type="acronym">LIRMM</orgName><date type="start">1995</date><desc><address><addrLine>CC 477, 161 rue Ada, 34095 Montpellier Cedex 5</addrLine><country key="FR"></country></address><ref type="url">http://www.lirmm.fr</ref></desc><listRelation><relation name="UMR5506" active="#struct-441569" type="direct"></relation><relation name="UMR5506" active="#struct-410122" type="direct"></relation></listRelation></org></tutelle><tutelle name="UMR5506" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle><tutelle name="UMR5506" active="#struct-410122" type="indirect"><org type="institution" xml:id="struct-410122" status="VALID"><orgName>Université de Montpellier</orgName><orgName type="acronym">UM</orgName><desc><address><addrLine>163 rue Auguste Broussonnet - 34090 Montpellier</addrLine><country key="FR"></country></address><ref type="url">http://www.umontpellier.fr/</ref></desc></org></tutelle></tutelles></hal:affiliation></affiliation></author><author><name sortKey="Lecroq, Thierry" sort="Lecroq, Thierry" uniqKey="Lecroq T" first="Thierry" last="Lecroq">Thierry Lecroq</name><affiliation><hal:affiliation type="laboratory" xml:id="struct-23832" status="VALID"><orgName>Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes</orgName><orgName type="acronym">LITIS</orgName><desc><address><addrLine>Avenue de l'Université UFR des Sciences et Techniques 76800 Saint-Etienne du Rouvray</addrLine><country key="FR"></country></address><ref type="url">http://www.litislab.eu</ref></desc><listRelation><relation active="#struct-300317" type="direct"></relation><relation name="EA4108" active="#struct-300318" type="direct"></relation><relation active="#struct-301288" type="direct"></relation><relation active="#struct-301232" type="indirect"></relation></listRelation><tutelles><tutelle active="#struct-300317" type="direct"><org type="institution" xml:id="struct-300317" status="VALID"><orgName>Université du Havre</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle name="EA4108" active="#struct-300318" type="direct"><org type="institution" xml:id="struct-300318" status="VALID"><orgName>Université de Rouen</orgName><desc><address><addrLine> 1 rue Thomas Becket - 76821 Mont-Saint-Aignan</addrLine><country key="FR"></country></address><ref type="url">http://www.univ-rouen.fr/</ref></desc></org></tutelle><tutelle active="#struct-301288" type="direct"><org type="department" xml:id="struct-301288" status="VALID"><orgName>Institut National des Sciences Appliquées - Rouen</orgName><orgName type="acronym">INSA Rouen</orgName><desc><address><country key="FR"></country></address></desc><listRelation><relation active="#struct-301232" type="direct"></relation></listRelation></org></tutelle><tutelle active="#struct-301232" type="indirect"><org type="institution" xml:id="struct-301232" status="VALID"><orgName>Institut National des Sciences Appliquées</orgName><orgName type="acronym">INSA</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle></tutelles></hal:affiliation></affiliation></author><author><name sortKey="Rivals, Eric" sort="Rivals, Eric" uniqKey="Rivals E" first="Eric" last="Rivals">Eric Rivals</name><affiliation><hal:affiliation type="laboratory" xml:id="struct-213159" status="VALID"><orgName>Institut de Biologie Computationnelle</orgName><orgName type="acronym">IBC</orgName><desc><address><addrLine>95 rue de la Galéra, 34095 Montpellier</addrLine><country key="FR"></country></address><ref type="url">http://www.ibc-montpellier.fr/</ref></desc><listRelation><relation active="#struct-92114" type="direct"></relation><relation active="#struct-300009" type="direct"></relation><relation active="#struct-11574" type="direct"></relation><relation active="#struct-441569" type="direct"></relation><relation active="#struct-410122" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-92114" type="direct"><org type="institution" xml:id="struct-92114" status="VALID"> <orgName>Institut National de la Recherche Agronomique</orgName> <orgName type="acronym">INRA</orgName> <desc> <address> <country key="FR"></country> </address> <ref type="url">http://www.inra.fr</ref> </desc></org></tutelle><tutelle active="#struct-300009" type="direct"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle><tutelle active="#struct-11574" type="direct"><org type="institution" xml:id="struct-11574" status="VALID"> <orgName>Centre de Coopération Internationale en Recherche Agronomique pour le Développement</orgName> <orgName type="acronym">CIRAD</orgName> <desc> <address> <addrLine>42, rue Scheffer 75116 Paris</addrLine> <country key="FR"></country> </address> <ref type="url">http://www.cirad.fr</ref> </desc></org></tutelle><tutelle active="#struct-441569" type="direct"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle><tutelle active="#struct-410122" type="direct"><org type="institution" xml:id="struct-410122" status="VALID"><orgName>Université de Montpellier</orgName><orgName type="acronym">UM</orgName><desc><address><addrLine>163 rue Auguste Broussonnet - 34090 Montpellier</addrLine><country key="FR"></country></address><ref type="url">http://www.umontpellier.fr/</ref></desc></org></tutelle></tutelles></hal:affiliation></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">HAL</idno><idno type="RBID">Hal:lirmm-01081429</idno><idno type="halId">lirmm-01081429</idno><idno type="halUri">https://hal-lirmm.ccsd.cnrs.fr/lirmm-01081429</idno><idno type="url">https://hal-lirmm.ccsd.cnrs.fr/lirmm-01081429</idno><idno type="doi">10.1007/978-3-319-07566-2_10</idno><date when="2014-06-16">2014-06-16</date><idno type="wicri:Area/Hal/Corpus">000136</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">From Indexing Data Structures to de Bruijn Graphs</title><author><name sortKey="Cazaux, Bastien" sort="Cazaux, Bastien" uniqKey="Cazaux B" first="Bastien" last="Cazaux">Bastien Cazaux</name><affiliation><hal:affiliation type="researchteam" xml:id="struct-388224" status="VALID"><orgName>Méthodes et Algorithmes pour la Bioinformatique</orgName><orgName type="acronym">MAB</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.lirmm.fr/recherche/equipes/mab</ref></desc><listRelation><relation active="#struct-181" type="direct"></relation><relation name="UMR5506" active="#struct-441569" type="indirect"></relation><relation name="UMR5506" active="#struct-410122" type="indirect"></relation></listRelation><tutelles><tutelle active="#struct-181" type="direct"><org type="laboratory" xml:id="struct-181" status="VALID"><idno type="RNSR">199111950H</idno><orgName>Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier</orgName><orgName type="acronym">LIRMM</orgName><date type="start">1995</date><desc><address><addrLine>CC 477, 161 rue Ada, 34095 Montpellier Cedex 5</addrLine><country key="FR"></country></address><ref type="url">http://www.lirmm.fr</ref></desc><listRelation><relation name="UMR5506" active="#struct-441569" type="direct"></relation><relation name="UMR5506" active="#struct-410122" type="direct"></relation></listRelation></org></tutelle><tutelle name="UMR5506" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle><tutelle name="UMR5506" active="#struct-410122" type="indirect"><org type="institution" xml:id="struct-410122" status="VALID"><orgName>Université de Montpellier</orgName><orgName type="acronym">UM</orgName><desc><address><addrLine>163 rue Auguste Broussonnet - 34090 Montpellier</addrLine><country key="FR"></country></address><ref type="url">http://www.umontpellier.fr/</ref></desc></org></tutelle></tutelles></hal:affiliation></affiliation></author><author><name sortKey="Lecroq, Thierry" sort="Lecroq, Thierry" uniqKey="Lecroq T" first="Thierry" last="Lecroq">Thierry Lecroq</name><affiliation><hal:affiliation type="laboratory" xml:id="struct-23832" status="VALID"><orgName>Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes</orgName><orgName type="acronym">LITIS</orgName><desc><address><addrLine>Avenue de l'Université UFR des Sciences et Techniques 76800 Saint-Etienne du Rouvray</addrLine><country key="FR"></country></address><ref type="url">http://www.litislab.eu</ref></desc><listRelation><relation active="#struct-300317" type="direct"></relation><relation name="EA4108" active="#struct-300318" type="direct"></relation><relation active="#struct-301288" type="direct"></relation><relation active="#struct-301232" type="indirect"></relation></listRelation><tutelles><tutelle active="#struct-300317" type="direct"><org type="institution" xml:id="struct-300317" status="VALID"><orgName>Université du Havre</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle name="EA4108" active="#struct-300318" type="direct"><org type="institution" xml:id="struct-300318" status="VALID"><orgName>Université de Rouen</orgName><desc><address><addrLine> 1 rue Thomas Becket - 76821 Mont-Saint-Aignan</addrLine><country key="FR"></country></address><ref type="url">http://www.univ-rouen.fr/</ref></desc></org></tutelle><tutelle active="#struct-301288" type="direct"><org type="department" xml:id="struct-301288" status="VALID"><orgName>Institut National des Sciences Appliquées - Rouen</orgName><orgName type="acronym">INSA Rouen</orgName><desc><address><country key="FR"></country></address></desc><listRelation><relation active="#struct-301232" type="direct"></relation></listRelation></org></tutelle><tutelle active="#struct-301232" type="indirect"><org type="institution" xml:id="struct-301232" status="VALID"><orgName>Institut National des Sciences Appliquées</orgName><orgName type="acronym">INSA</orgName><desc><address><country key="FR"></country></address></desc></org></tutelle></tutelles></hal:affiliation></affiliation></author><author><name sortKey="Rivals, Eric" sort="Rivals, Eric" uniqKey="Rivals E" first="Eric" last="Rivals">Eric Rivals</name><affiliation><hal:affiliation type="laboratory" xml:id="struct-213159" status="VALID"><orgName>Institut de Biologie Computationnelle</orgName><orgName type="acronym">IBC</orgName><desc><address><addrLine>95 rue de la Galéra, 34095 Montpellier</addrLine><country key="FR"></country></address><ref type="url">http://www.ibc-montpellier.fr/</ref></desc><listRelation><relation active="#struct-92114" type="direct"></relation><relation active="#struct-300009" type="direct"></relation><relation active="#struct-11574" type="direct"></relation><relation active="#struct-441569" type="direct"></relation><relation active="#struct-410122" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-92114" type="direct"><org type="institution" xml:id="struct-92114" status="VALID"> <orgName>Institut National de la Recherche Agronomique</orgName> <orgName type="acronym">INRA</orgName> <desc> <address> <country key="FR"></country> </address> <ref type="url">http://www.inra.fr</ref> </desc></org></tutelle><tutelle active="#struct-300009" type="direct"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle><tutelle active="#struct-11574" type="direct"><org type="institution" xml:id="struct-11574" status="VALID"> <orgName>Centre de Coopération Internationale en Recherche Agronomique pour le Développement</orgName> <orgName type="acronym">CIRAD</orgName> <desc> <address> <addrLine>42, rue Scheffer 75116 Paris</addrLine> <country key="FR"></country> </address> <ref type="url">http://www.cirad.fr</ref> </desc></org></tutelle><tutelle active="#struct-441569" type="direct"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle><tutelle active="#struct-410122" type="direct"><org type="institution" xml:id="struct-410122" status="VALID"><orgName>Université de Montpellier</orgName><orgName type="acronym">UM</orgName><desc><address><addrLine>163 rue Auguste Broussonnet - 34090 Montpellier</addrLine><country key="FR"></country></address><ref type="url">http://www.umontpellier.fr/</ref></desc></org></tutelle></tutelles></hal:affiliation></affiliation></author></analytic><idno type="DOI">10.1007/978-3-319-07566-2_10</idno></biblStruct></sourceDesc></fileDesc><profileDesc><textClass><keywords scheme="mix" xml:lang="en"><term>assembly</term><term>construction algorithms</term><term>contracted de Bruijn graph</term><term>dynamic update</term><term>index data structures</term><term>k-mer</term><term>overlap</term><term>suffix array</term><term>suffix tree</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">New technologies have tremendously increased sequencing throughput com-pared to traditional techniques, thereby complicating DNA assembly. Hence, as-sembly programs resort to de Bruijn graphs (dBG) of k-mers of short reads to compute a set of long contigs, each being a putative segment of the sequenced molecule. Other types of DNA sequence analysis, as well as preprocessing of the reads for assembly, use classical data structures to index all substrings of the reads. It is thus interesting to exhibit algorithms that directly build a dBG of order k from a pre-existing index, and especially a contracted version of the dBG, where non branching paths are condensed into single nodes. Here, we formalise the relation-ship between suffix trees/arrays and dBGs, and exhibit linear time algorithms for constructing the full or contracted dBGs. Finally, we provide hints explaining why this bridge between indexes and dBGs enables to dynamically update the order k of the graph.</div></front></TEI><hal api="V3"><titleStmt><title xml:lang="en">From Indexing Data Structures to de Bruijn Graphs</title><author role="aut"><persName><forename type="first">Bastien</forename><surname>Cazaux</surname></persName><email>cazaux@lirmm.fr</email><idno type="idhal">cazaux-bastien</idno><idno type="halauthor">1095364</idno><affiliation ref="#struct-388224"></affiliation><affiliation ref="#struct-213159"></affiliation></author><author role="aut"><persName><forename type="first">Thierry</forename><surname>Lecroq</surname></persName><email>Thierry.Lecroq@univ-rouen.fr</email><idno type="halauthor">477079</idno><affiliation ref="#struct-23832"></affiliation></author><author role="aut"><persName><forename type="first">Eric</forename><surname>Rivals</surname></persName><email>Eric.Rivals@lirmm.fr</email><ptr type="url" target="http://www.lirmm.fr/~rivals/"></ptr><idno type="idhal">eric-rivals</idno><idno type="halauthor">1097563</idno><idno type="ORCID">http://orcid.org/0000-0003-3791-3973</idno><affiliation ref="#struct-213159"></affiliation><affiliation ref="#struct-388224"></affiliation></author><editor role="depositor"><persName><forename>Eric</forename><surname>Rivals</surname></persName><email>rivals@lirmm.fr</email></editor><funder ref="#projanr-23506"></funder><funder>This work is also supported by Défi MASTODONS SePhHaDe from CNRS and Labex NumEV.</funder></titleStmt><editionStmt><edition n="v1" type="current"><date type="whenSubmitted">2014-11-07 17:47:40</date><date type="whenWritten">2014-03-05</date><date type="whenModified">2016-01-20 14:42:20</date><date type="whenReleased">2014-11-12 12:51:30</date><date type="whenProduced">2014-06-16</date><date type="whenEndEmbargoed">2014-11-07</date><ref type="file" target="https://hal-lirmm.ccsd.cnrs.fr/lirmm-01081429/document"><date notBefore="2014-11-07"></date></ref><ref type="file" subtype="author" n="1" target="https://hal-lirmm.ccsd.cnrs.fr/lirmm-01081429/file/cpm-dbg-auteurs.pdf"><date notBefore="2014-11-07"></date></ref></edition><respStmt><resp>contributor</resp><name key="113912"><persName><forename>Eric</forename><surname>Rivals</surname></persName><email>rivals@lirmm.fr</email></name></respStmt></editionStmt><publicationStmt><distributor>CCSD</distributor><idno type="halId">lirmm-01081429</idno><idno type="halUri">https://hal-lirmm.ccsd.cnrs.fr/lirmm-01081429</idno><idno type="halBibtex">cazaux:lirmm-01081429</idno><idno type="halRefHtml">Kulikov, Alexander S.; Kuznetsov, Sergei O.; Pevzner, Pavel. CPM: Combinatorial Pattern Matching, Jun 2014, Moscow, Russia. Springer International Publishing, CPM'2014: 25th Annual Symposium on Combinatorial Pattern Matching, LNCS (8486), pp.89-99, 2014, Combinatorial Pattern Matching. <http://www.springer.com/computer/image+processing/book/978-3-319-07565-5>. <10.1007/978-3-319-07566-2_10></idno><idno type="halRef">Kulikov, Alexander S.; Kuznetsov, Sergei O.; Pevzner, Pavel. CPM: Combinatorial Pattern Matching, Jun 2014, Moscow, Russia. Springer International Publishing, CPM'2014: 25th Annual Symposium on Combinatorial Pattern Matching, LNCS (8486), pp.89-99, 2014, Combinatorial Pattern Matching. <http://www.springer.com/computer/image+processing/book/978-3-319-07565-5>. <10.1007/978-3-319-07566-2_10></idno><availability status="restricted"><licence target="http://creativecommons.org/licenses/by-nc-nd/">Attribution - NonCommercial - NoDerivatives</licence></availability></publicationStmt><seriesStmt><idno type="stamp" n="CIRAD">CIRAD - Centre de coopération internationale en recherche agronomique pour le développement</idno><idno type="stamp" n="CNRS">CNRS - Centre national de la recherche scientifique</idno><idno type="stamp" n="INRIA">INRIA - Institut National de Recherche en Informatique et en Automatique</idno><idno type="stamp" n="UNIV-LEHAVRE">Université du Havre</idno><idno type="stamp" n="UNIV-ROUEN">Université de Rouen</idno><idno type="stamp" n="INRA">INRA - Institut national de la recherche agronomique</idno><idno type="stamp" n="LITIS">Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes</idno><idno type="stamp" n="IBC">Institut de Biologie Computationnelle</idno><idno type="stamp" n="MAB" p="LIRMM">Méthodes et Algorithmes pour la Bioinformatique</idno><idno type="stamp" n="IRD">IRD - Institut de recherche pour le développement</idno><idno type="stamp" n="COMUE-NORMANDIE">Normandie Université</idno><idno type="stamp" n="LIRMM">Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier</idno></seriesStmt><notesStmt><note type="audience" n="2">International</note><note type="invited" n="0">No</note><note type="popular" n="0">No</note><note type="peer" n="1">Yes</note><note type="proceedings" n="1">Yes</note></notesStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">From Indexing Data Structures to de Bruijn Graphs</title><author role="aut"><persName><forename type="first">Bastien</forename><surname>Cazaux</surname></persName><email>cazaux@lirmm.fr</email><idno type="idHal">cazaux-bastien</idno><idno type="halAuthorId">1095364</idno><affiliation ref="#struct-388224"></affiliation><affiliation ref="#struct-213159"></affiliation></author><author role="aut"><persName><forename type="first">Thierry</forename><surname>Lecroq</surname></persName><email>Thierry.Lecroq@univ-rouen.fr</email><idno type="halAuthorId">477079</idno><affiliation ref="#struct-23832"></affiliation></author><author role="aut"><persName><forename type="first">Eric</forename><surname>Rivals</surname></persName><email>Eric.Rivals@lirmm.fr</email><ptr type="url" target="http://www.lirmm.fr/~rivals/"></ptr><idno type="idHal">eric-rivals</idno><idno type="halAuthorId">1097563</idno><idno type="ORCID">http://orcid.org/0000-0003-3791-3973</idno><affiliation ref="#struct-213159"></affiliation><affiliation ref="#struct-388224"></affiliation></author></analytic><monogr><title level="m">CPM'2014: 25th Annual Symposium on Combinatorial Pattern Matching</title><meeting><title>CPM: Combinatorial Pattern Matching</title><date type="start">2014-06-16</date><date type="end">2014-06-18</date><settlement>Moscow</settlement><country key="RU">Russia</country></meeting><respStmt><resp>conferenceOrganizer</resp><name>Moscow State University</name></respStmt><editor>Kulikov, Alexander S.</editor><editor>Kuznetsov, Sergei O.</editor><editor>Pevzner, Pavel</editor><imprint><publisher>Springer International Publishing</publisher><biblScope unit="serie">Combinatorial Pattern Matching</biblScope><biblScope unit="volume">LNCS</biblScope><biblScope unit="issue">8486</biblScope><biblScope unit="pp">89-99</biblScope><date type="datePub">2014</date></imprint></monogr><idno type="doi">10.1007/978-3-319-07566-2_10</idno><ref type="publisher">http://www.springer.com/computer/image+processing/book/978-3-319-07565-5</ref></biblStruct></sourceDesc><profileDesc><langUsage><language ident="en">English</language></langUsage><textClass><keywords scheme="author"><term xml:lang="en">suffix tree</term><term xml:lang="en">suffix array</term><term xml:lang="en">assembly</term><term xml:lang="en">index data structures</term><term xml:lang="en">dynamic update</term><term xml:lang="en">k-mer</term><term xml:lang="en">overlap</term><term xml:lang="en">contracted de Bruijn graph</term><term xml:lang="en">construction algorithms</term></keywords><classCode scheme="halDomain" n="info.info-bi">Computer Science [cs]/Bioinformatics [q-bio.QM]</classCode><classCode scheme="halDomain" n="info">Computer Science [cs]</classCode><classCode scheme="halDomain" n="info.info-ds">Computer Science [cs]/Data Structures and Algorithms [cs.DS]</classCode><classCode scheme="halTypology" n="COMM">Conference papers</classCode></textClass><abstract xml:lang="en">New technologies have tremendously increased sequencing throughput com-pared to traditional techniques, thereby complicating DNA assembly. Hence, as-sembly programs resort to de Bruijn graphs (dBG) of k-mers of short reads to compute a set of long contigs, each being a putative segment of the sequenced molecule. Other types of DNA sequence analysis, as well as preprocessing of the reads for assembly, use classical data structures to index all substrings of the reads. It is thus interesting to exhibit algorithms that directly build a dBG of order k from a pre-existing index, and especially a contracted version of the dBG, where non branching paths are condensed into single nodes. Here, we formalise the relation-ship between suffix trees/arrays and dBGs, and exhibit linear time algorithms for constructing the full or contracted dBGs. Finally, we provide hints explaining why this bridge between indexes and dBGs enables to dynamically update the order k of the graph.</abstract></profileDesc></hal></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/France/explor/LeHavreV1/Data/Hal/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000136 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Hal/Corpus/biblio.hfd -nk 000136 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/France
|area= LeHavreV1
|flux= Hal
|étape= Corpus
|type= RBID
|clé= Hal:lirmm-01081429
|texte= From Indexing Data Structures to de Bruijn Graphs
}}
| This area was generated with Dilib version V0.6.25. |  |