Querying large read collections in main memory: a versatile data structure
Identifieur interne : 000864 ( Ncbi/Merge ); précédent : 000863; suivant : 000865Querying large read collections in main memory: a versatile data structure
Auteurs : Nicolas Philippe [France] ; Mikaël Salson [France] ; Thierry Lecroq [France] ; Martine Léonard [France] ; Thérèse Commes [France] ; Eric Rivals [France]Source :
- BMC Bioinformatics [ 1471-2105 ] ; 2011.
Descripteurs français
- KwdFr :
- MESH :
English descriptors
- KwdEn :
- MESH :
Abstract
High Throughput Sequencing (HTS) is now heavily exploited for genome (re-) sequencing, metagenomics, epigenomics, and transcriptomics and requires different, but computer intensive bioinformatic analyses. When a reference genome is available, mapping reads on it is the first step of this analysis. Read mapping programs owe their efficiency to the use of involved genome indexing data structures, like the Burrows-Wheeler transform. Recent solutions index both the genome, and the
Here, we present a solution, named
Url:
DOI: 10.1186/1471-2105-12-242
PubMed: 21682852
PubMed Central: 3163563
Links toward previous steps (curation, corpus...)
- to stream Pmc, to step Corpus: 000A91
- to stream Pmc, to step Curation: 000A91
- to stream Pmc, to step Checkpoint: 001325
- to stream PubMed, to step Corpus: 001E67
- to stream PubMed, to step Curation: 001E67
- to stream PubMed, to step Checkpoint: 001D54
Links to Exploration step
PMC:3163563Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Querying large read collections in main memory: a versatile data structure</title>
<author><name sortKey="Philippe, Nicolas" sort="Philippe, Nicolas" uniqKey="Philippe N" first="Nicolas" last="Philippe">Nicolas Philippe</name>
<affiliation wicri:level="3"><nlm:aff id="I1">LIRMM, UMR 5506, CNRS and Université de Montpellier 2, CC 477, 161 rue Ada, 34095 Montpellier, France</nlm:aff>
<country xml:lang="fr">France</country>
<wicri:regionArea>LIRMM, UMR 5506, CNRS and Université de Montpellier 2, CC 477, 161 rue Ada, 34095 Montpellier</wicri:regionArea>
<placeName><region type="region" nuts="2">Occitanie (région administrative)</region>
<region type="old region" nuts="2">Languedoc-Roussillon</region>
<settlement type="city">Montpellier</settlement>
</placeName>
</affiliation>
<affiliation wicri:level="3"><nlm:aff id="I2">CRBM, UMR 5237 CNRS, 1919 Route de Mende, 34293 Montpellier cedex 5, France</nlm:aff>
<country xml:lang="fr">France</country>
<wicri:regionArea>CRBM, UMR 5237 CNRS, 1919 Route de Mende, 34293 Montpellier cedex 5</wicri:regionArea>
<placeName><region type="region" nuts="2">Occitanie (région administrative)</region>
<region type="old region" nuts="2">Languedoc-Roussillon</region>
<settlement type="city">Montpellier</settlement>
</placeName>
</affiliation>
</author>
<author><name sortKey="Salson, Mikael" sort="Salson, Mikael" uniqKey="Salson M" first="Mikaël" last="Salson">Mikaël Salson</name>
<affiliation wicri:level="4"><nlm:aff id="I3">LITIS EA 4108, Université de Rouen, 1 rue Thomas Becket, 76821 Mont-Saint-Aignan Cedex, France</nlm:aff>
<country xml:lang="fr">France</country>
<wicri:regionArea>LITIS EA 4108, Université de Rouen, 1 rue Thomas Becket, 76821 Mont-Saint-Aignan Cedex</wicri:regionArea>
<placeName><region type="region" nuts="2">Région Normandie</region>
<region type="old region" nuts="2">Haute-Normandie</region>
<settlement type="city">Mont-Saint-Aignan</settlement>
</placeName>
<orgName type="university">Université de Rouen</orgName>
</affiliation>
<affiliation wicri:level="3"><nlm:aff id="I4">LIFL, UMR 8022 CNRS and Université Lille 1 and INRIA Lille-Nord-Europe, Bât. M3 - UFR IEEA, 59655 Villeneuve d'Ascq Cedex, France</nlm:aff>
<country xml:lang="fr">France</country>
<wicri:regionArea>LIFL, UMR 8022 CNRS and Université Lille 1 and INRIA Lille-Nord-Europe, Bât. M3 - UFR IEEA, 59655 Villeneuve d'Ascq Cedex</wicri:regionArea>
<placeName><region type="region" nuts="2">Hauts-de-France</region>
<region type="old region" nuts="2">Nord-Pas-de-Calais</region>
<settlement type="city">Villeneuve d'Ascq</settlement>
</placeName>
</affiliation>
</author>
<author><name sortKey="Lecroq, Thierry" sort="Lecroq, Thierry" uniqKey="Lecroq T" first="Thierry" last="Lecroq">Thierry Lecroq</name>
<affiliation wicri:level="4"><nlm:aff id="I3">LITIS EA 4108, Université de Rouen, 1 rue Thomas Becket, 76821 Mont-Saint-Aignan Cedex, France</nlm:aff>
<country xml:lang="fr">France</country>
<wicri:regionArea>LITIS EA 4108, Université de Rouen, 1 rue Thomas Becket, 76821 Mont-Saint-Aignan Cedex</wicri:regionArea>
<placeName><region type="region" nuts="2">Région Normandie</region>
<region type="old region" nuts="2">Haute-Normandie</region>
<settlement type="city">Mont-Saint-Aignan</settlement>
</placeName>
<orgName type="university">Université de Rouen</orgName>
</affiliation>
</author>
<author><name sortKey="Leonard, Martine" sort="Leonard, Martine" uniqKey="Leonard M" first="Martine" last="Léonard">Martine Léonard</name>
<affiliation wicri:level="4"><nlm:aff id="I3">LITIS EA 4108, Université de Rouen, 1 rue Thomas Becket, 76821 Mont-Saint-Aignan Cedex, France</nlm:aff>
<country xml:lang="fr">France</country>
<wicri:regionArea>LITIS EA 4108, Université de Rouen, 1 rue Thomas Becket, 76821 Mont-Saint-Aignan Cedex</wicri:regionArea>
<placeName><region type="region" nuts="2">Région Normandie</region>
<region type="old region" nuts="2">Haute-Normandie</region>
<settlement type="city">Mont-Saint-Aignan</settlement>
</placeName>
<orgName type="university">Université de Rouen</orgName>
</affiliation>
</author>
<author><name sortKey="Commes, Therese" sort="Commes, Therese" uniqKey="Commes T" first="Thérèse" last="Commes">Thérèse Commes</name>
<affiliation wicri:level="3"><nlm:aff id="I2">CRBM, UMR 5237 CNRS, 1919 Route de Mende, 34293 Montpellier cedex 5, France</nlm:aff>
<country xml:lang="fr">France</country>
<wicri:regionArea>CRBM, UMR 5237 CNRS, 1919 Route de Mende, 34293 Montpellier cedex 5</wicri:regionArea>
<placeName><region type="region" nuts="2">Occitanie (région administrative)</region>
<region type="old region" nuts="2">Languedoc-Roussillon</region>
<settlement type="city">Montpellier</settlement>
</placeName>
</affiliation>
</author>
<author><name sortKey="Rivals, Eric" sort="Rivals, Eric" uniqKey="Rivals E" first="Eric" last="Rivals">Eric Rivals</name>
<affiliation wicri:level="3"><nlm:aff id="I1">LIRMM, UMR 5506, CNRS and Université de Montpellier 2, CC 477, 161 rue Ada, 34095 Montpellier, France</nlm:aff>
<country xml:lang="fr">France</country>
<wicri:regionArea>LIRMM, UMR 5506, CNRS and Université de Montpellier 2, CC 477, 161 rue Ada, 34095 Montpellier</wicri:regionArea>
<placeName><region type="region" nuts="2">Occitanie (région administrative)</region>
<region type="old region" nuts="2">Languedoc-Roussillon</region>
<settlement type="city">Montpellier</settlement>
</placeName>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">PMC</idno>
<idno type="pmid">21682852</idno>
<idno type="pmc">3163563</idno>
<idno type="url">http://www.ncbi.nlm.nih.gov/pmc/articles/PMC3163563</idno>
<idno type="RBID">PMC:3163563</idno>
<idno type="doi">10.1186/1471-2105-12-242</idno>
<date when="2011">2011</date>
<idno type="wicri:Area/Pmc/Corpus">000A91</idno>
<idno type="wicri:explorRef" wicri:stream="Pmc" wicri:step="Corpus" wicri:corpus="PMC">000A91</idno>
<idno type="wicri:Area/Pmc/Curation">000A91</idno>
<idno type="wicri:explorRef" wicri:stream="Pmc" wicri:step="Curation">000A91</idno>
<idno type="wicri:Area/Pmc/Checkpoint">001325</idno>
<idno type="wicri:explorRef" wicri:stream="Pmc" wicri:step="Checkpoint">001325</idno>
<idno type="wicri:source">PubMed</idno>
<idno type="RBID">pubmed:21682852</idno>
<idno type="wicri:Area/PubMed/Corpus">001E67</idno>
<idno type="wicri:explorRef" wicri:stream="PubMed" wicri:step="Corpus" wicri:corpus="PubMed">001E67</idno>
<idno type="wicri:Area/PubMed/Curation">001E67</idno>
<idno type="wicri:explorRef" wicri:stream="PubMed" wicri:step="Curation">001E67</idno>
<idno type="wicri:Area/PubMed/Checkpoint">001D54</idno>
<idno type="wicri:explorRef" wicri:stream="Checkpoint" wicri:step="PubMed">001D54</idno>
<idno type="wicri:Area/Ncbi/Merge">000864</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en" level="a" type="main">Querying large read collections in main memory: a versatile data structure</title>
<author><name sortKey="Philippe, Nicolas" sort="Philippe, Nicolas" uniqKey="Philippe N" first="Nicolas" last="Philippe">Nicolas Philippe</name>
<affiliation wicri:level="3"><nlm:aff id="I1">LIRMM, UMR 5506, CNRS and Université de Montpellier 2, CC 477, 161 rue Ada, 34095 Montpellier, France</nlm:aff>
<country xml:lang="fr">France</country>
<wicri:regionArea>LIRMM, UMR 5506, CNRS and Université de Montpellier 2, CC 477, 161 rue Ada, 34095 Montpellier</wicri:regionArea>
<placeName><region type="region" nuts="2">Occitanie (région administrative)</region>
<region type="old region" nuts="2">Languedoc-Roussillon</region>
<settlement type="city">Montpellier</settlement>
</placeName>
</affiliation>
<affiliation wicri:level="3"><nlm:aff id="I2">CRBM, UMR 5237 CNRS, 1919 Route de Mende, 34293 Montpellier cedex 5, France</nlm:aff>
<country xml:lang="fr">France</country>
<wicri:regionArea>CRBM, UMR 5237 CNRS, 1919 Route de Mende, 34293 Montpellier cedex 5</wicri:regionArea>
<placeName><region type="region" nuts="2">Occitanie (région administrative)</region>
<region type="old region" nuts="2">Languedoc-Roussillon</region>
<settlement type="city">Montpellier</settlement>
</placeName>
</affiliation>
</author>
<author><name sortKey="Salson, Mikael" sort="Salson, Mikael" uniqKey="Salson M" first="Mikaël" last="Salson">Mikaël Salson</name>
<affiliation wicri:level="4"><nlm:aff id="I3">LITIS EA 4108, Université de Rouen, 1 rue Thomas Becket, 76821 Mont-Saint-Aignan Cedex, France</nlm:aff>
<country xml:lang="fr">France</country>
<wicri:regionArea>LITIS EA 4108, Université de Rouen, 1 rue Thomas Becket, 76821 Mont-Saint-Aignan Cedex</wicri:regionArea>
<placeName><region type="region" nuts="2">Région Normandie</region>
<region type="old region" nuts="2">Haute-Normandie</region>
<settlement type="city">Mont-Saint-Aignan</settlement>
</placeName>
<orgName type="university">Université de Rouen</orgName>
</affiliation>
<affiliation wicri:level="3"><nlm:aff id="I4">LIFL, UMR 8022 CNRS and Université Lille 1 and INRIA Lille-Nord-Europe, Bât. M3 - UFR IEEA, 59655 Villeneuve d'Ascq Cedex, France</nlm:aff>
<country xml:lang="fr">France</country>
<wicri:regionArea>LIFL, UMR 8022 CNRS and Université Lille 1 and INRIA Lille-Nord-Europe, Bât. M3 - UFR IEEA, 59655 Villeneuve d'Ascq Cedex</wicri:regionArea>
<placeName><region type="region" nuts="2">Hauts-de-France</region>
<region type="old region" nuts="2">Nord-Pas-de-Calais</region>
<settlement type="city">Villeneuve d'Ascq</settlement>
</placeName>
</affiliation>
</author>
<author><name sortKey="Lecroq, Thierry" sort="Lecroq, Thierry" uniqKey="Lecroq T" first="Thierry" last="Lecroq">Thierry Lecroq</name>
<affiliation wicri:level="4"><nlm:aff id="I3">LITIS EA 4108, Université de Rouen, 1 rue Thomas Becket, 76821 Mont-Saint-Aignan Cedex, France</nlm:aff>
<country xml:lang="fr">France</country>
<wicri:regionArea>LITIS EA 4108, Université de Rouen, 1 rue Thomas Becket, 76821 Mont-Saint-Aignan Cedex</wicri:regionArea>
<placeName><region type="region" nuts="2">Région Normandie</region>
<region type="old region" nuts="2">Haute-Normandie</region>
<settlement type="city">Mont-Saint-Aignan</settlement>
</placeName>
<orgName type="university">Université de Rouen</orgName>
</affiliation>
</author>
<author><name sortKey="Leonard, Martine" sort="Leonard, Martine" uniqKey="Leonard M" first="Martine" last="Léonard">Martine Léonard</name>
<affiliation wicri:level="4"><nlm:aff id="I3">LITIS EA 4108, Université de Rouen, 1 rue Thomas Becket, 76821 Mont-Saint-Aignan Cedex, France</nlm:aff>
<country xml:lang="fr">France</country>
<wicri:regionArea>LITIS EA 4108, Université de Rouen, 1 rue Thomas Becket, 76821 Mont-Saint-Aignan Cedex</wicri:regionArea>
<placeName><region type="region" nuts="2">Région Normandie</region>
<region type="old region" nuts="2">Haute-Normandie</region>
<settlement type="city">Mont-Saint-Aignan</settlement>
</placeName>
<orgName type="university">Université de Rouen</orgName>
</affiliation>
</author>
<author><name sortKey="Commes, Therese" sort="Commes, Therese" uniqKey="Commes T" first="Thérèse" last="Commes">Thérèse Commes</name>
<affiliation wicri:level="3"><nlm:aff id="I2">CRBM, UMR 5237 CNRS, 1919 Route de Mende, 34293 Montpellier cedex 5, France</nlm:aff>
<country xml:lang="fr">France</country>
<wicri:regionArea>CRBM, UMR 5237 CNRS, 1919 Route de Mende, 34293 Montpellier cedex 5</wicri:regionArea>
<placeName><region type="region" nuts="2">Occitanie (région administrative)</region>
<region type="old region" nuts="2">Languedoc-Roussillon</region>
<settlement type="city">Montpellier</settlement>
</placeName>
</affiliation>
</author>
<author><name sortKey="Rivals, Eric" sort="Rivals, Eric" uniqKey="Rivals E" first="Eric" last="Rivals">Eric Rivals</name>
<affiliation wicri:level="3"><nlm:aff id="I1">LIRMM, UMR 5506, CNRS and Université de Montpellier 2, CC 477, 161 rue Ada, 34095 Montpellier, France</nlm:aff>
<country xml:lang="fr">France</country>
<wicri:regionArea>LIRMM, UMR 5506, CNRS and Université de Montpellier 2, CC 477, 161 rue Ada, 34095 Montpellier</wicri:regionArea>
<placeName><region type="region" nuts="2">Occitanie (région administrative)</region>
<region type="old region" nuts="2">Languedoc-Roussillon</region>
<settlement type="city">Montpellier</settlement>
</placeName>
</affiliation>
</author>
</analytic>
<series><title level="j">BMC Bioinformatics</title>
<idno type="eISSN">1471-2105</idno>
<imprint><date when="2011">2011</date>
</imprint>
</series>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Algorithms</term>
<term>Computational Biology (methods)</term>
<term>Computers</term>
<term>High-Throughput Nucleotide Sequencing</term>
<term>Humans</term>
<term>Software</term>
</keywords>
<keywords scheme="KwdFr" xml:lang="fr"><term>Algorithmes</term>
<term>Biologie informatique ()</term>
<term>Humains</term>
<term>Logiciel</term>
<term>Ordinateurs</term>
<term>Séquençage nucléotidique à haut débit</term>
</keywords>
<keywords scheme="MESH" qualifier="methods" xml:lang="en"><term>Computational Biology</term>
</keywords>
<keywords scheme="MESH" xml:lang="en"><term>Algorithms</term>
<term>Computers</term>
<term>High-Throughput Nucleotide Sequencing</term>
<term>Humans</term>
<term>Software</term>
</keywords>
<keywords scheme="MESH" xml:lang="fr"><term>Algorithmes</term>
<term>Biologie informatique</term>
<term>Humains</term>
<term>Logiciel</term>
<term>Ordinateurs</term>
<term>Séquençage nucléotidique à haut débit</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en"><sec><title>Background</title>
<p>High Throughput Sequencing (HTS) is now heavily exploited for genome (re-) sequencing, metagenomics, epigenomics, and transcriptomics and requires different, but computer intensive bioinformatic analyses. When a reference genome is available, mapping reads on it is the first step of this analysis. Read mapping programs owe their efficiency to the use of involved genome indexing data structures, like the Burrows-Wheeler transform. Recent solutions index both the genome, and the <italic>k</italic>
-mers of the reads using hash-tables to further increase efficiency and accuracy. In various contexts (e.g. assembly or transcriptome analysis), read processing requires to determine the sub-collection of reads that are related to a given sequence, which is done by searching for some <italic>k</italic>
-mers in the reads. Currently, many developments have focused on genome indexing structures for read mapping, but the question of read indexing remains broadly unexplored. However, the increase in sequence throughput urges for new algorithmic solutions to query large read collections efficiently.</p>
</sec>
<sec><title>Results</title>
<p>Here, we present a solution, named <italic>Gk </italic>
arrays, to index large collections of reads, an algorithm to build the structure, and procedures to query it. Once constructed, the index structure is kept in main memory and is repeatedly accessed to answer queries like "given a <italic>k</italic>
-mer, get the reads containing this <italic>k</italic>
-mer (once/at least once)". We compared our structure to other solutions that adapt uncompressed indexing structures designed for long texts and show that it processes queries fast, while requiring much less memory. Our structure can thus handle larger read collections. We provide examples where such queries are adapted to different types of read analysis (SNP detection, assembly, RNA-Seq).</p>
</sec>
<sec><title>Conclusions</title>
<p><italic>Gk </italic>
arrays constitute a versatile data structure that enables fast and more accurate read analysis in various contexts. The <italic>Gk </italic>
arrays provide a flexible brick to design innovative programs that mine efficiently genomics, epigenomics, metagenomics, or transcriptomics reads. The <italic>Gk </italic>
arrays library is available under Cecill (GPL compliant) license from <ext-link ext-link-type="uri" xlink:href="http://www.atgc-montpellier.fr/ngs/">http://www.atgc-montpellier.fr/ngs/</ext-link>
.</p>
</sec>
</div>
</front>
<back><div1 type="bibliography"><listBibl><biblStruct><analytic><author><name sortKey="Maher, C" uniqKey="Maher C">C Maher</name>
</author>
<author><name sortKey="Kumar Sinha, C" uniqKey="Kumar Sinha C">C Kumar-Sinha</name>
</author>
<author><name sortKey="Cao, X" uniqKey="Cao X">X Cao</name>
</author>
<author><name sortKey="Kalyana Sundaram, S" uniqKey="Kalyana Sundaram S">S Kalyana-Sundaram</name>
</author>
<author><name sortKey="Han, B" uniqKey="Han B">B Han</name>
</author>
<author><name sortKey="Jing, X" uniqKey="Jing X">X Jing</name>
</author>
<author><name sortKey="Sam, L" uniqKey="Sam L">L Sam</name>
</author>
<author><name sortKey="Barrette, T" uniqKey="Barrette T">T Barrette</name>
</author>
<author><name sortKey="Palanisamy, N" uniqKey="Palanisamy N">N Palanisamy</name>
</author>
<author><name sortKey="Chinnaiyan, A" uniqKey="Chinnaiyan A">A Chinnaiyan</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Blow, N" uniqKey="Blow N">N Blow</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Altschul, S" uniqKey="Altschul S">S Altschul</name>
</author>
<author><name sortKey="Gish, W" uniqKey="Gish W">W Gish</name>
</author>
<author><name sortKey="Miller, W" uniqKey="Miller W">W Miller</name>
</author>
<author><name sortKey="Myers, E" uniqKey="Myers E">E Myers</name>
</author>
<author><name sortKey="Lipman, D" uniqKey="Lipman D">D Lipman</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Burkhardt, S" uniqKey="Burkhardt S">S Burkhardt</name>
</author>
<author><name sortKey="Crauser, A" uniqKey="Crauser A">A Crauser</name>
</author>
<author><name sortKey="Ferragina, P" uniqKey="Ferragina P">P Ferragina</name>
</author>
<author><name sortKey="Lenhof, Hp" uniqKey="Lenhof H">HP Lenhof</name>
</author>
<author><name sortKey="Rivals, E" uniqKey="Rivals E">E Rivals</name>
</author>
<author><name sortKey="Vingron, M" uniqKey="Vingron M">M Vingron</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Ferragina, P" uniqKey="Ferragina P">P Ferragina</name>
</author>
<author><name sortKey="Manzini, G" uniqKey="Manzini G">G Manzini</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Hach, F" uniqKey="Hach F">F Hach</name>
</author>
<author><name sortKey="Hormozdiari, F" uniqKey="Hormozdiari F">F Hormozdiari</name>
</author>
<author><name sortKey="Alkan, C" uniqKey="Alkan C">C Alkan</name>
</author>
<author><name sortKey="Hormozdiari, F" uniqKey="Hormozdiari F">F Hormozdiari</name>
</author>
<author><name sortKey="Birol, I" uniqKey="Birol I">I Birol</name>
</author>
<author><name sortKey="Eichler, E" uniqKey="Eichler E">E Eichler</name>
</author>
<author><name sortKey="Sahinalp, S" uniqKey="Sahinalp S">S Sahinalp</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Weiner, P" uniqKey="Weiner P">P Weiner</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Manber, U" uniqKey="Manber U">U Manber</name>
</author>
<author><name sortKey="Myers, Gw" uniqKey="Myers G">GW Myers</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Gusfield, D" uniqKey="Gusfield D">D Gusfield</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Shi, F" uniqKey="Shi F">F Shi</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Ferragina, P" uniqKey="Ferragina P">P Ferragina</name>
</author>
<author><name sortKey="Gonzalez, R" uniqKey="Gonzalez R">R González</name>
</author>
<author><name sortKey="Navarro, G" uniqKey="Navarro G">G Navarro</name>
</author>
<author><name sortKey="Venturini, R" uniqKey="Venturini R">R Venturini</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Li, H" uniqKey="Li H">H Li</name>
</author>
<author><name sortKey="Durbin, R" uniqKey="Durbin R">R Durbin</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Homann, R" uniqKey="Homann R">R Homann</name>
</author>
<author><name sortKey="Fleer, D" uniqKey="Fleer D">D Fleer</name>
</author>
<author><name sortKey="Giegerich, R" uniqKey="Giegerich R">R Giegerich</name>
</author>
<author><name sortKey="Rehmsmeier, M" uniqKey="Rehmsmeier M">M Rehmsmeier</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Philippe, N" uniqKey="Philippe N">N Philippe</name>
</author>
<author><name sortKey="Boureux, A" uniqKey="Boureux A">A Boureux</name>
</author>
<author><name sortKey="Tarhio, J" uniqKey="Tarhio J">J Tarhio</name>
</author>
<author><name sortKey="Brehelin, L" uniqKey="Brehelin L">L Bréhélin</name>
</author>
<author><name sortKey="Commes, T" uniqKey="Commes T">T Commes</name>
</author>
<author><name sortKey="Rivals, E" uniqKey="Rivals E">E Rivals</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Salmela, L" uniqKey="Salmela L">L Salmela</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Denoeud, F" uniqKey="Denoeud F">F Denoeud</name>
</author>
<author><name sortKey="Aury, Jm" uniqKey="Aury J">JM Aury</name>
</author>
<author><name sortKey="Da Silva, C" uniqKey="Da Silva C">C Da Silva</name>
</author>
<author><name sortKey="Noel, B" uniqKey="Noel B">B Noel</name>
</author>
<author><name sortKey="Rogier, O" uniqKey="Rogier O">O Rogier</name>
</author>
<author><name sortKey="Delledonne, M" uniqKey="Delledonne M">M Delledonne</name>
</author>
<author><name sortKey="Morgante, M" uniqKey="Morgante M">M Morgante</name>
</author>
<author><name sortKey="Valle, G" uniqKey="Valle G">G Valle</name>
</author>
<author><name sortKey="Wincker, P" uniqKey="Wincker P">P Wincker</name>
</author>
<author><name sortKey="Scarpelli, C" uniqKey="Scarpelli C">C Scarpelli</name>
</author>
<author><name sortKey="Jaillon, O" uniqKey="Jaillon O">O Jaillon</name>
</author>
<author><name sortKey="Artiguenave, F" uniqKey="Artiguenave F">F Artiguenave</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Trapnell, C" uniqKey="Trapnell C">C Trapnell</name>
</author>
<author><name sortKey="Williams, Ba" uniqKey="Williams B">BA Williams</name>
</author>
<author><name sortKey="Pertea, G" uniqKey="Pertea G">G Pertea</name>
</author>
<author><name sortKey="Mortazavi, A" uniqKey="Mortazavi A">A Mortazavi</name>
</author>
<author><name sortKey="Kwan, G" uniqKey="Kwan G">G Kwan</name>
</author>
<author><name sortKey="Van Baren, Mj" uniqKey="Van Baren M">MJ van Baren</name>
</author>
<author><name sortKey="Salzberg, Sl" uniqKey="Salzberg S">SL Salzberg</name>
</author>
<author><name sortKey="Wold, Bj" uniqKey="Wold B">BJ Wold</name>
</author>
<author><name sortKey="Pachter, L" uniqKey="Pachter L">L Pachter</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Miller, Jr" uniqKey="Miller J">JR Miller</name>
</author>
<author><name sortKey="Koren, S" uniqKey="Koren S">S Koren</name>
</author>
<author><name sortKey="Sutton, G" uniqKey="Sutton G">G Sutton</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Conway, Tc" uniqKey="Conway T">TC Conway</name>
</author>
<author><name sortKey="Bromage, Aj" uniqKey="Bromage A">AJ Bromage</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Marcais, G" uniqKey="Marcais G">G Marcais</name>
</author>
<author><name sortKey="Kingsford, C" uniqKey="Kingsford C">C Kingsford</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Cormen, Th" uniqKey="Cormen T">TH Cormen</name>
</author>
<author><name sortKey="Leiserson, Ce" uniqKey="Leiserson C">CE Leiserson</name>
</author>
<author><name sortKey="Rivest, Rl" uniqKey="Rivest R">RL Rivest</name>
</author>
<author><name sortKey="Stein, C" uniqKey="Stein C">C Stein</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Munro, I" uniqKey="Munro I">I Munro</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Raman, R" uniqKey="Raman R">R Raman</name>
</author>
<author><name sortKey="Raman, V" uniqKey="Raman V">V Raman</name>
</author>
<author><name sortKey="Rao, S" uniqKey="Rao S">S Rao</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Manzini, G" uniqKey="Manzini G">G Manzini</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Kurtz, S" uniqKey="Kurtz S">S Kurtz</name>
</author>
<author><name sortKey="Phillippy, A" uniqKey="Phillippy A">A Phillippy</name>
</author>
<author><name sortKey="Delcher, A" uniqKey="Delcher A">A Delcher</name>
</author>
<author><name sortKey="Smoot, M" uniqKey="Smoot M">M Smoot</name>
</author>
<author><name sortKey="Shumway, M" uniqKey="Shumway M">M Shumway</name>
</author>
<author><name sortKey="Antonescu, C" uniqKey="Antonescu C">C Antonescu</name>
</author>
<author><name sortKey="Salzberg, S" uniqKey="Salzberg S">S Salzberg</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Kasai, T" uniqKey="Kasai T">T Kasai</name>
</author>
<author><name sortKey="Lee, G" uniqKey="Lee G">G Lee</name>
</author>
<author><name sortKey="Arimura, H" uniqKey="Arimura H">H Arimura</name>
</author>
<author><name sortKey="Arikawa, S" uniqKey="Arikawa S">S Arikawa</name>
</author>
<author><name sortKey="Park, K" uniqKey="Park K">K Park</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Puglisi, Sj" uniqKey="Puglisi S">SJ Puglisi</name>
</author>
<author><name sortKey="Smyth, Wf" uniqKey="Smyth W">WF Smyth</name>
</author>
<author><name sortKey="Turpin, A" uniqKey="Turpin A">A Turpin</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Schuster, Sc" uniqKey="Schuster S">SC Schuster</name>
</author>
<author><name sortKey="Miller, W" uniqKey="Miller W">W Miller</name>
</author>
<author><name sortKey="Ratan, A" uniqKey="Ratan A">A Ratan</name>
</author>
<author><name sortKey="Tomsho, Lp" uniqKey="Tomsho L">LP Tomsho</name>
</author>
<author><name sortKey="Giardine, B" uniqKey="Giardine B">B Giardine</name>
</author>
<author><name sortKey="Kasson, Lr" uniqKey="Kasson L">LR Kasson</name>
</author>
<author><name sortKey="Harris, Rs" uniqKey="Harris R">RS Harris</name>
</author>
<author><name sortKey="Petersen, Dc" uniqKey="Petersen D">DC Petersen</name>
</author>
<author><name sortKey="Zhao, F" uniqKey="Zhao F">F Zhao</name>
</author>
<author><name sortKey="Qi, J" uniqKey="Qi J">J Qi</name>
</author>
<author><name sortKey="Alkan, C" uniqKey="Alkan C">C Alkan</name>
</author>
<author><name sortKey="Kidd, Jm" uniqKey="Kidd J">JM Kidd</name>
</author>
<author><name sortKey="Sun, Y" uniqKey="Sun Y">Y Sun</name>
</author>
<author><name sortKey="Drautz, Di" uniqKey="Drautz D">DI Drautz</name>
</author>
<author><name sortKey="Bouffard, P" uniqKey="Bouffard P">P Bouffard</name>
</author>
<author><name sortKey="Muzny, Dm" uniqKey="Muzny D">DM Muzny</name>
</author>
<author><name sortKey="Reid, Jg" uniqKey="Reid J">JG Reid</name>
</author>
<author><name sortKey="Nazareth, Lv" uniqKey="Nazareth L">LV Nazareth</name>
</author>
<author><name sortKey="Wang, Q" uniqKey="Wang Q">Q Wang</name>
</author>
<author><name sortKey="Burhans, R" uniqKey="Burhans R">R Burhans</name>
</author>
<author><name sortKey="Riemer, C" uniqKey="Riemer C">C Riemer</name>
</author>
<author><name sortKey="Wittekindt, Ne" uniqKey="Wittekindt N">NE Wittekindt</name>
</author>
<author><name sortKey="Moorjani, P" uniqKey="Moorjani P">P Moorjani</name>
</author>
<author><name sortKey="Tindall, Ea" uniqKey="Tindall E">EA Tindall</name>
</author>
<author><name sortKey="Danko, Cg" uniqKey="Danko C">CG Danko</name>
</author>
<author><name sortKey="Teo, Ws" uniqKey="Teo W">WS Teo</name>
</author>
<author><name sortKey="Buboltz, Am" uniqKey="Buboltz A">AM Buboltz</name>
</author>
<author><name sortKey="Zhang, Z" uniqKey="Zhang Z">Z Zhang</name>
</author>
<author><name sortKey="Ma, Q" uniqKey="Ma Q">Q Ma</name>
</author>
<author><name sortKey="Oosthuysen, A" uniqKey="Oosthuysen A">A Oosthuysen</name>
</author>
<author><name sortKey="Steenkamp, Aw" uniqKey="Steenkamp A">AW Steenkamp</name>
</author>
<author><name sortKey="Oostuisen, H" uniqKey="Oostuisen H">H Oostuisen</name>
</author>
<author><name sortKey="Venter, P" uniqKey="Venter P">P Venter</name>
</author>
<author><name sortKey="Gajewski, J" uniqKey="Gajewski J">J Gajewski</name>
</author>
<author><name sortKey="Zhang, Y" uniqKey="Zhang Y">Y Zhang</name>
</author>
<author><name sortKey="Pugh, Bf" uniqKey="Pugh B">BF Pugh</name>
</author>
<author><name sortKey="Makova, Kd" uniqKey="Makova K">KD Makova</name>
</author>
<author><name sortKey="Nekrutenko, A" uniqKey="Nekrutenko A">A Nekrutenko</name>
</author>
<author><name sortKey="Mardis, Er" uniqKey="Mardis E">ER Mardis</name>
</author>
<author><name sortKey="Patterson, N" uniqKey="Patterson N">N Patterson</name>
</author>
<author><name sortKey="Pringle, Th" uniqKey="Pringle T">TH Pringle</name>
</author>
<author><name sortKey="Chiaromonte, F" uniqKey="Chiaromonte F">F Chiaromonte</name>
</author>
<author><name sortKey="Mullikin, Jc" uniqKey="Mullikin J">JC Mullikin</name>
</author>
<author><name sortKey="Eichler, Ee" uniqKey="Eichler E">EE Eichler</name>
</author>
<author><name sortKey="Hardison, Rc" uniqKey="Hardison R">RC Hardison</name>
</author>
<author><name sortKey="Gibbs, Ra" uniqKey="Gibbs R">RA Gibbs</name>
</author>
<author><name sortKey="Harkins, Tt" uniqKey="Harkins T">TT Harkins</name>
</author>
<author><name sortKey="Hayes, Vm" uniqKey="Hayes V">VM Hayes</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Li, H" uniqKey="Li H">H Li</name>
</author>
<author><name sortKey="Homer, N" uniqKey="Homer N">N Homer</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Schroder, J" uniqKey="Schroder J">J Schröder</name>
</author>
<author><name sortKey="Schroder, H" uniqKey="Schroder H">H Schröder</name>
</author>
<author><name sortKey="Puglisi, Sj" uniqKey="Puglisi S">SJ Puglisi</name>
</author>
<author><name sortKey="Sinha, R" uniqKey="Sinha R">R Sinha</name>
</author>
<author><name sortKey="Schmidt, B" uniqKey="Schmidt B">B Schmidt</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Ilie, L" uniqKey="Ilie L">L Ilie</name>
</author>
<author><name sortKey="Fazayeli, F" uniqKey="Fazayeli F">F Fazayeli</name>
</author>
<author><name sortKey="Ilie, S" uniqKey="Ilie S">S Ilie</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Salmela, L" uniqKey="Salmela L">L Salmela</name>
</author>
<author><name sortKey="Schroder, J" uniqKey="Schroder J">J Schröder</name>
</author>
</analytic>
</biblStruct>
</listBibl>
</div1>
</back>
</TEI>
<double pmid="21682852"><pmc><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Querying large read collections in main memory: a versatile data structure</title>
<author><name sortKey="Philippe, Nicolas" sort="Philippe, Nicolas" uniqKey="Philippe N" first="Nicolas" last="Philippe">Nicolas Philippe</name>
<affiliation wicri:level="3"><nlm:aff id="I1">LIRMM, UMR 5506, CNRS and Université de Montpellier 2, CC 477, 161 rue Ada, 34095 Montpellier, France</nlm:aff>
<country xml:lang="fr">France</country>
<wicri:regionArea>LIRMM, UMR 5506, CNRS and Université de Montpellier 2, CC 477, 161 rue Ada, 34095 Montpellier</wicri:regionArea>
<placeName><region type="region" nuts="2">Occitanie (région administrative)</region>
<region type="old region" nuts="2">Languedoc-Roussillon</region>
<settlement type="city">Montpellier</settlement>
</placeName>
</affiliation>
<affiliation wicri:level="3"><nlm:aff id="I2">CRBM, UMR 5237 CNRS, 1919 Route de Mende, 34293 Montpellier cedex 5, France</nlm:aff>
<country xml:lang="fr">France</country>
<wicri:regionArea>CRBM, UMR 5237 CNRS, 1919 Route de Mende, 34293 Montpellier cedex 5</wicri:regionArea>
<placeName><region type="region" nuts="2">Occitanie (région administrative)</region>
<region type="old region" nuts="2">Languedoc-Roussillon</region>
<settlement type="city">Montpellier</settlement>
</placeName>
</affiliation>
</author>
<author><name sortKey="Salson, Mikael" sort="Salson, Mikael" uniqKey="Salson M" first="Mikaël" last="Salson">Mikaël Salson</name>
<affiliation wicri:level="4"><nlm:aff id="I3">LITIS EA 4108, Université de Rouen, 1 rue Thomas Becket, 76821 Mont-Saint-Aignan Cedex, France</nlm:aff>
<country xml:lang="fr">France</country>
<wicri:regionArea>LITIS EA 4108, Université de Rouen, 1 rue Thomas Becket, 76821 Mont-Saint-Aignan Cedex</wicri:regionArea>
<placeName><region type="region" nuts="2">Région Normandie</region>
<region type="old region" nuts="2">Haute-Normandie</region>
<settlement type="city">Mont-Saint-Aignan</settlement>
</placeName>
<orgName type="university">Université de Rouen</orgName>
</affiliation>
<affiliation wicri:level="3"><nlm:aff id="I4">LIFL, UMR 8022 CNRS and Université Lille 1 and INRIA Lille-Nord-Europe, Bât. M3 - UFR IEEA, 59655 Villeneuve d'Ascq Cedex, France</nlm:aff>
<country xml:lang="fr">France</country>
<wicri:regionArea>LIFL, UMR 8022 CNRS and Université Lille 1 and INRIA Lille-Nord-Europe, Bât. M3 - UFR IEEA, 59655 Villeneuve d'Ascq Cedex</wicri:regionArea>
<placeName><region type="region" nuts="2">Hauts-de-France</region>
<region type="old region" nuts="2">Nord-Pas-de-Calais</region>
<settlement type="city">Villeneuve d'Ascq</settlement>
</placeName>
</affiliation>
</author>
<author><name sortKey="Lecroq, Thierry" sort="Lecroq, Thierry" uniqKey="Lecroq T" first="Thierry" last="Lecroq">Thierry Lecroq</name>
<affiliation wicri:level="4"><nlm:aff id="I3">LITIS EA 4108, Université de Rouen, 1 rue Thomas Becket, 76821 Mont-Saint-Aignan Cedex, France</nlm:aff>
<country xml:lang="fr">France</country>
<wicri:regionArea>LITIS EA 4108, Université de Rouen, 1 rue Thomas Becket, 76821 Mont-Saint-Aignan Cedex</wicri:regionArea>
<placeName><region type="region" nuts="2">Région Normandie</region>
<region type="old region" nuts="2">Haute-Normandie</region>
<settlement type="city">Mont-Saint-Aignan</settlement>
</placeName>
<orgName type="university">Université de Rouen</orgName>
</affiliation>
</author>
<author><name sortKey="Leonard, Martine" sort="Leonard, Martine" uniqKey="Leonard M" first="Martine" last="Léonard">Martine Léonard</name>
<affiliation wicri:level="4"><nlm:aff id="I3">LITIS EA 4108, Université de Rouen, 1 rue Thomas Becket, 76821 Mont-Saint-Aignan Cedex, France</nlm:aff>
<country xml:lang="fr">France</country>
<wicri:regionArea>LITIS EA 4108, Université de Rouen, 1 rue Thomas Becket, 76821 Mont-Saint-Aignan Cedex</wicri:regionArea>
<placeName><region type="region" nuts="2">Région Normandie</region>
<region type="old region" nuts="2">Haute-Normandie</region>
<settlement type="city">Mont-Saint-Aignan</settlement>
</placeName>
<orgName type="university">Université de Rouen</orgName>
</affiliation>
</author>
<author><name sortKey="Commes, Therese" sort="Commes, Therese" uniqKey="Commes T" first="Thérèse" last="Commes">Thérèse Commes</name>
<affiliation wicri:level="3"><nlm:aff id="I2">CRBM, UMR 5237 CNRS, 1919 Route de Mende, 34293 Montpellier cedex 5, France</nlm:aff>
<country xml:lang="fr">France</country>
<wicri:regionArea>CRBM, UMR 5237 CNRS, 1919 Route de Mende, 34293 Montpellier cedex 5</wicri:regionArea>
<placeName><region type="region" nuts="2">Occitanie (région administrative)</region>
<region type="old region" nuts="2">Languedoc-Roussillon</region>
<settlement type="city">Montpellier</settlement>
</placeName>
</affiliation>
</author>
<author><name sortKey="Rivals, Eric" sort="Rivals, Eric" uniqKey="Rivals E" first="Eric" last="Rivals">Eric Rivals</name>
<affiliation wicri:level="3"><nlm:aff id="I1">LIRMM, UMR 5506, CNRS and Université de Montpellier 2, CC 477, 161 rue Ada, 34095 Montpellier, France</nlm:aff>
<country xml:lang="fr">France</country>
<wicri:regionArea>LIRMM, UMR 5506, CNRS and Université de Montpellier 2, CC 477, 161 rue Ada, 34095 Montpellier</wicri:regionArea>
<placeName><region type="region" nuts="2">Occitanie (région administrative)</region>
<region type="old region" nuts="2">Languedoc-Roussillon</region>
<settlement type="city">Montpellier</settlement>
</placeName>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">PMC</idno>
<idno type="pmid">21682852</idno>
<idno type="pmc">3163563</idno>
<idno type="url">http://www.ncbi.nlm.nih.gov/pmc/articles/PMC3163563</idno>
<idno type="RBID">PMC:3163563</idno>
<idno type="doi">10.1186/1471-2105-12-242</idno>
<date when="2011">2011</date>
<idno type="wicri:Area/Pmc/Corpus">000A91</idno>
<idno type="wicri:explorRef" wicri:stream="Pmc" wicri:step="Corpus" wicri:corpus="PMC">000A91</idno>
<idno type="wicri:Area/Pmc/Curation">000A91</idno>
<idno type="wicri:explorRef" wicri:stream="Pmc" wicri:step="Curation">000A91</idno>
<idno type="wicri:Area/Pmc/Checkpoint">001325</idno>
<idno type="wicri:explorRef" wicri:stream="Pmc" wicri:step="Checkpoint">001325</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en" level="a" type="main">Querying large read collections in main memory: a versatile data structure</title>
<author><name sortKey="Philippe, Nicolas" sort="Philippe, Nicolas" uniqKey="Philippe N" first="Nicolas" last="Philippe">Nicolas Philippe</name>
<affiliation wicri:level="3"><nlm:aff id="I1">LIRMM, UMR 5506, CNRS and Université de Montpellier 2, CC 477, 161 rue Ada, 34095 Montpellier, France</nlm:aff>
<country xml:lang="fr">France</country>
<wicri:regionArea>LIRMM, UMR 5506, CNRS and Université de Montpellier 2, CC 477, 161 rue Ada, 34095 Montpellier</wicri:regionArea>
<placeName><region type="region" nuts="2">Occitanie (région administrative)</region>
<region type="old region" nuts="2">Languedoc-Roussillon</region>
<settlement type="city">Montpellier</settlement>
</placeName>
</affiliation>
<affiliation wicri:level="3"><nlm:aff id="I2">CRBM, UMR 5237 CNRS, 1919 Route de Mende, 34293 Montpellier cedex 5, France</nlm:aff>
<country xml:lang="fr">France</country>
<wicri:regionArea>CRBM, UMR 5237 CNRS, 1919 Route de Mende, 34293 Montpellier cedex 5</wicri:regionArea>
<placeName><region type="region" nuts="2">Occitanie (région administrative)</region>
<region type="old region" nuts="2">Languedoc-Roussillon</region>
<settlement type="city">Montpellier</settlement>
</placeName>
</affiliation>
</author>
<author><name sortKey="Salson, Mikael" sort="Salson, Mikael" uniqKey="Salson M" first="Mikaël" last="Salson">Mikaël Salson</name>
<affiliation wicri:level="4"><nlm:aff id="I3">LITIS EA 4108, Université de Rouen, 1 rue Thomas Becket, 76821 Mont-Saint-Aignan Cedex, France</nlm:aff>
<country xml:lang="fr">France</country>
<wicri:regionArea>LITIS EA 4108, Université de Rouen, 1 rue Thomas Becket, 76821 Mont-Saint-Aignan Cedex</wicri:regionArea>
<placeName><region type="region" nuts="2">Région Normandie</region>
<region type="old region" nuts="2">Haute-Normandie</region>
<settlement type="city">Mont-Saint-Aignan</settlement>
</placeName>
<orgName type="university">Université de Rouen</orgName>
</affiliation>
<affiliation wicri:level="3"><nlm:aff id="I4">LIFL, UMR 8022 CNRS and Université Lille 1 and INRIA Lille-Nord-Europe, Bât. M3 - UFR IEEA, 59655 Villeneuve d'Ascq Cedex, France</nlm:aff>
<country xml:lang="fr">France</country>
<wicri:regionArea>LIFL, UMR 8022 CNRS and Université Lille 1 and INRIA Lille-Nord-Europe, Bât. M3 - UFR IEEA, 59655 Villeneuve d'Ascq Cedex</wicri:regionArea>
<placeName><region type="region" nuts="2">Hauts-de-France</region>
<region type="old region" nuts="2">Nord-Pas-de-Calais</region>
<settlement type="city">Villeneuve d'Ascq</settlement>
</placeName>
</affiliation>
</author>
<author><name sortKey="Lecroq, Thierry" sort="Lecroq, Thierry" uniqKey="Lecroq T" first="Thierry" last="Lecroq">Thierry Lecroq</name>
<affiliation wicri:level="4"><nlm:aff id="I3">LITIS EA 4108, Université de Rouen, 1 rue Thomas Becket, 76821 Mont-Saint-Aignan Cedex, France</nlm:aff>
<country xml:lang="fr">France</country>
<wicri:regionArea>LITIS EA 4108, Université de Rouen, 1 rue Thomas Becket, 76821 Mont-Saint-Aignan Cedex</wicri:regionArea>
<placeName><region type="region" nuts="2">Région Normandie</region>
<region type="old region" nuts="2">Haute-Normandie</region>
<settlement type="city">Mont-Saint-Aignan</settlement>
</placeName>
<orgName type="university">Université de Rouen</orgName>
</affiliation>
</author>
<author><name sortKey="Leonard, Martine" sort="Leonard, Martine" uniqKey="Leonard M" first="Martine" last="Léonard">Martine Léonard</name>
<affiliation wicri:level="4"><nlm:aff id="I3">LITIS EA 4108, Université de Rouen, 1 rue Thomas Becket, 76821 Mont-Saint-Aignan Cedex, France</nlm:aff>
<country xml:lang="fr">France</country>
<wicri:regionArea>LITIS EA 4108, Université de Rouen, 1 rue Thomas Becket, 76821 Mont-Saint-Aignan Cedex</wicri:regionArea>
<placeName><region type="region" nuts="2">Région Normandie</region>
<region type="old region" nuts="2">Haute-Normandie</region>
<settlement type="city">Mont-Saint-Aignan</settlement>
</placeName>
<orgName type="university">Université de Rouen</orgName>
</affiliation>
</author>
<author><name sortKey="Commes, Therese" sort="Commes, Therese" uniqKey="Commes T" first="Thérèse" last="Commes">Thérèse Commes</name>
<affiliation wicri:level="3"><nlm:aff id="I2">CRBM, UMR 5237 CNRS, 1919 Route de Mende, 34293 Montpellier cedex 5, France</nlm:aff>
<country xml:lang="fr">France</country>
<wicri:regionArea>CRBM, UMR 5237 CNRS, 1919 Route de Mende, 34293 Montpellier cedex 5</wicri:regionArea>
<placeName><region type="region" nuts="2">Occitanie (région administrative)</region>
<region type="old region" nuts="2">Languedoc-Roussillon</region>
<settlement type="city">Montpellier</settlement>
</placeName>
</affiliation>
</author>
<author><name sortKey="Rivals, Eric" sort="Rivals, Eric" uniqKey="Rivals E" first="Eric" last="Rivals">Eric Rivals</name>
<affiliation wicri:level="3"><nlm:aff id="I1">LIRMM, UMR 5506, CNRS and Université de Montpellier 2, CC 477, 161 rue Ada, 34095 Montpellier, France</nlm:aff>
<country xml:lang="fr">France</country>
<wicri:regionArea>LIRMM, UMR 5506, CNRS and Université de Montpellier 2, CC 477, 161 rue Ada, 34095 Montpellier</wicri:regionArea>
<placeName><region type="region" nuts="2">Occitanie (région administrative)</region>
<region type="old region" nuts="2">Languedoc-Roussillon</region>
<settlement type="city">Montpellier</settlement>
</placeName>
</affiliation>
</author>
</analytic>
<series><title level="j">BMC Bioinformatics</title>
<idno type="eISSN">1471-2105</idno>
<imprint><date when="2011">2011</date>
</imprint>
</series>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass></textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en"><sec><title>Background</title>
<p>High Throughput Sequencing (HTS) is now heavily exploited for genome (re-) sequencing, metagenomics, epigenomics, and transcriptomics and requires different, but computer intensive bioinformatic analyses. When a reference genome is available, mapping reads on it is the first step of this analysis. Read mapping programs owe their efficiency to the use of involved genome indexing data structures, like the Burrows-Wheeler transform. Recent solutions index both the genome, and the <italic>k</italic>
-mers of the reads using hash-tables to further increase efficiency and accuracy. In various contexts (e.g. assembly or transcriptome analysis), read processing requires to determine the sub-collection of reads that are related to a given sequence, which is done by searching for some <italic>k</italic>
-mers in the reads. Currently, many developments have focused on genome indexing structures for read mapping, but the question of read indexing remains broadly unexplored. However, the increase in sequence throughput urges for new algorithmic solutions to query large read collections efficiently.</p>
</sec>
<sec><title>Results</title>
<p>Here, we present a solution, named <italic>Gk </italic>
arrays, to index large collections of reads, an algorithm to build the structure, and procedures to query it. Once constructed, the index structure is kept in main memory and is repeatedly accessed to answer queries like "given a <italic>k</italic>
-mer, get the reads containing this <italic>k</italic>
-mer (once/at least once)". We compared our structure to other solutions that adapt uncompressed indexing structures designed for long texts and show that it processes queries fast, while requiring much less memory. Our structure can thus handle larger read collections. We provide examples where such queries are adapted to different types of read analysis (SNP detection, assembly, RNA-Seq).</p>
</sec>
<sec><title>Conclusions</title>
<p><italic>Gk </italic>
arrays constitute a versatile data structure that enables fast and more accurate read analysis in various contexts. The <italic>Gk </italic>
arrays provide a flexible brick to design innovative programs that mine efficiently genomics, epigenomics, metagenomics, or transcriptomics reads. The <italic>Gk </italic>
arrays library is available under Cecill (GPL compliant) license from <ext-link ext-link-type="uri" xlink:href="http://www.atgc-montpellier.fr/ngs/">http://www.atgc-montpellier.fr/ngs/</ext-link>
.</p>
</sec>
</div>
</front>
<back><div1 type="bibliography"><listBibl><biblStruct><analytic><author><name sortKey="Maher, C" uniqKey="Maher C">C Maher</name>
</author>
<author><name sortKey="Kumar Sinha, C" uniqKey="Kumar Sinha C">C Kumar-Sinha</name>
</author>
<author><name sortKey="Cao, X" uniqKey="Cao X">X Cao</name>
</author>
<author><name sortKey="Kalyana Sundaram, S" uniqKey="Kalyana Sundaram S">S Kalyana-Sundaram</name>
</author>
<author><name sortKey="Han, B" uniqKey="Han B">B Han</name>
</author>
<author><name sortKey="Jing, X" uniqKey="Jing X">X Jing</name>
</author>
<author><name sortKey="Sam, L" uniqKey="Sam L">L Sam</name>
</author>
<author><name sortKey="Barrette, T" uniqKey="Barrette T">T Barrette</name>
</author>
<author><name sortKey="Palanisamy, N" uniqKey="Palanisamy N">N Palanisamy</name>
</author>
<author><name sortKey="Chinnaiyan, A" uniqKey="Chinnaiyan A">A Chinnaiyan</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Blow, N" uniqKey="Blow N">N Blow</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Altschul, S" uniqKey="Altschul S">S Altschul</name>
</author>
<author><name sortKey="Gish, W" uniqKey="Gish W">W Gish</name>
</author>
<author><name sortKey="Miller, W" uniqKey="Miller W">W Miller</name>
</author>
<author><name sortKey="Myers, E" uniqKey="Myers E">E Myers</name>
</author>
<author><name sortKey="Lipman, D" uniqKey="Lipman D">D Lipman</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Burkhardt, S" uniqKey="Burkhardt S">S Burkhardt</name>
</author>
<author><name sortKey="Crauser, A" uniqKey="Crauser A">A Crauser</name>
</author>
<author><name sortKey="Ferragina, P" uniqKey="Ferragina P">P Ferragina</name>
</author>
<author><name sortKey="Lenhof, Hp" uniqKey="Lenhof H">HP Lenhof</name>
</author>
<author><name sortKey="Rivals, E" uniqKey="Rivals E">E Rivals</name>
</author>
<author><name sortKey="Vingron, M" uniqKey="Vingron M">M Vingron</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Ferragina, P" uniqKey="Ferragina P">P Ferragina</name>
</author>
<author><name sortKey="Manzini, G" uniqKey="Manzini G">G Manzini</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Hach, F" uniqKey="Hach F">F Hach</name>
</author>
<author><name sortKey="Hormozdiari, F" uniqKey="Hormozdiari F">F Hormozdiari</name>
</author>
<author><name sortKey="Alkan, C" uniqKey="Alkan C">C Alkan</name>
</author>
<author><name sortKey="Hormozdiari, F" uniqKey="Hormozdiari F">F Hormozdiari</name>
</author>
<author><name sortKey="Birol, I" uniqKey="Birol I">I Birol</name>
</author>
<author><name sortKey="Eichler, E" uniqKey="Eichler E">E Eichler</name>
</author>
<author><name sortKey="Sahinalp, S" uniqKey="Sahinalp S">S Sahinalp</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Weiner, P" uniqKey="Weiner P">P Weiner</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Manber, U" uniqKey="Manber U">U Manber</name>
</author>
<author><name sortKey="Myers, Gw" uniqKey="Myers G">GW Myers</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Gusfield, D" uniqKey="Gusfield D">D Gusfield</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Shi, F" uniqKey="Shi F">F Shi</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Ferragina, P" uniqKey="Ferragina P">P Ferragina</name>
</author>
<author><name sortKey="Gonzalez, R" uniqKey="Gonzalez R">R González</name>
</author>
<author><name sortKey="Navarro, G" uniqKey="Navarro G">G Navarro</name>
</author>
<author><name sortKey="Venturini, R" uniqKey="Venturini R">R Venturini</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Li, H" uniqKey="Li H">H Li</name>
</author>
<author><name sortKey="Durbin, R" uniqKey="Durbin R">R Durbin</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Homann, R" uniqKey="Homann R">R Homann</name>
</author>
<author><name sortKey="Fleer, D" uniqKey="Fleer D">D Fleer</name>
</author>
<author><name sortKey="Giegerich, R" uniqKey="Giegerich R">R Giegerich</name>
</author>
<author><name sortKey="Rehmsmeier, M" uniqKey="Rehmsmeier M">M Rehmsmeier</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Philippe, N" uniqKey="Philippe N">N Philippe</name>
</author>
<author><name sortKey="Boureux, A" uniqKey="Boureux A">A Boureux</name>
</author>
<author><name sortKey="Tarhio, J" uniqKey="Tarhio J">J Tarhio</name>
</author>
<author><name sortKey="Brehelin, L" uniqKey="Brehelin L">L Bréhélin</name>
</author>
<author><name sortKey="Commes, T" uniqKey="Commes T">T Commes</name>
</author>
<author><name sortKey="Rivals, E" uniqKey="Rivals E">E Rivals</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Salmela, L" uniqKey="Salmela L">L Salmela</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Denoeud, F" uniqKey="Denoeud F">F Denoeud</name>
</author>
<author><name sortKey="Aury, Jm" uniqKey="Aury J">JM Aury</name>
</author>
<author><name sortKey="Da Silva, C" uniqKey="Da Silva C">C Da Silva</name>
</author>
<author><name sortKey="Noel, B" uniqKey="Noel B">B Noel</name>
</author>
<author><name sortKey="Rogier, O" uniqKey="Rogier O">O Rogier</name>
</author>
<author><name sortKey="Delledonne, M" uniqKey="Delledonne M">M Delledonne</name>
</author>
<author><name sortKey="Morgante, M" uniqKey="Morgante M">M Morgante</name>
</author>
<author><name sortKey="Valle, G" uniqKey="Valle G">G Valle</name>
</author>
<author><name sortKey="Wincker, P" uniqKey="Wincker P">P Wincker</name>
</author>
<author><name sortKey="Scarpelli, C" uniqKey="Scarpelli C">C Scarpelli</name>
</author>
<author><name sortKey="Jaillon, O" uniqKey="Jaillon O">O Jaillon</name>
</author>
<author><name sortKey="Artiguenave, F" uniqKey="Artiguenave F">F Artiguenave</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Trapnell, C" uniqKey="Trapnell C">C Trapnell</name>
</author>
<author><name sortKey="Williams, Ba" uniqKey="Williams B">BA Williams</name>
</author>
<author><name sortKey="Pertea, G" uniqKey="Pertea G">G Pertea</name>
</author>
<author><name sortKey="Mortazavi, A" uniqKey="Mortazavi A">A Mortazavi</name>
</author>
<author><name sortKey="Kwan, G" uniqKey="Kwan G">G Kwan</name>
</author>
<author><name sortKey="Van Baren, Mj" uniqKey="Van Baren M">MJ van Baren</name>
</author>
<author><name sortKey="Salzberg, Sl" uniqKey="Salzberg S">SL Salzberg</name>
</author>
<author><name sortKey="Wold, Bj" uniqKey="Wold B">BJ Wold</name>
</author>
<author><name sortKey="Pachter, L" uniqKey="Pachter L">L Pachter</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Miller, Jr" uniqKey="Miller J">JR Miller</name>
</author>
<author><name sortKey="Koren, S" uniqKey="Koren S">S Koren</name>
</author>
<author><name sortKey="Sutton, G" uniqKey="Sutton G">G Sutton</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Conway, Tc" uniqKey="Conway T">TC Conway</name>
</author>
<author><name sortKey="Bromage, Aj" uniqKey="Bromage A">AJ Bromage</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Marcais, G" uniqKey="Marcais G">G Marcais</name>
</author>
<author><name sortKey="Kingsford, C" uniqKey="Kingsford C">C Kingsford</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Cormen, Th" uniqKey="Cormen T">TH Cormen</name>
</author>
<author><name sortKey="Leiserson, Ce" uniqKey="Leiserson C">CE Leiserson</name>
</author>
<author><name sortKey="Rivest, Rl" uniqKey="Rivest R">RL Rivest</name>
</author>
<author><name sortKey="Stein, C" uniqKey="Stein C">C Stein</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Munro, I" uniqKey="Munro I">I Munro</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Raman, R" uniqKey="Raman R">R Raman</name>
</author>
<author><name sortKey="Raman, V" uniqKey="Raman V">V Raman</name>
</author>
<author><name sortKey="Rao, S" uniqKey="Rao S">S Rao</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Manzini, G" uniqKey="Manzini G">G Manzini</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Kurtz, S" uniqKey="Kurtz S">S Kurtz</name>
</author>
<author><name sortKey="Phillippy, A" uniqKey="Phillippy A">A Phillippy</name>
</author>
<author><name sortKey="Delcher, A" uniqKey="Delcher A">A Delcher</name>
</author>
<author><name sortKey="Smoot, M" uniqKey="Smoot M">M Smoot</name>
</author>
<author><name sortKey="Shumway, M" uniqKey="Shumway M">M Shumway</name>
</author>
<author><name sortKey="Antonescu, C" uniqKey="Antonescu C">C Antonescu</name>
</author>
<author><name sortKey="Salzberg, S" uniqKey="Salzberg S">S Salzberg</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Kasai, T" uniqKey="Kasai T">T Kasai</name>
</author>
<author><name sortKey="Lee, G" uniqKey="Lee G">G Lee</name>
</author>
<author><name sortKey="Arimura, H" uniqKey="Arimura H">H Arimura</name>
</author>
<author><name sortKey="Arikawa, S" uniqKey="Arikawa S">S Arikawa</name>
</author>
<author><name sortKey="Park, K" uniqKey="Park K">K Park</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Puglisi, Sj" uniqKey="Puglisi S">SJ Puglisi</name>
</author>
<author><name sortKey="Smyth, Wf" uniqKey="Smyth W">WF Smyth</name>
</author>
<author><name sortKey="Turpin, A" uniqKey="Turpin A">A Turpin</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Schuster, Sc" uniqKey="Schuster S">SC Schuster</name>
</author>
<author><name sortKey="Miller, W" uniqKey="Miller W">W Miller</name>
</author>
<author><name sortKey="Ratan, A" uniqKey="Ratan A">A Ratan</name>
</author>
<author><name sortKey="Tomsho, Lp" uniqKey="Tomsho L">LP Tomsho</name>
</author>
<author><name sortKey="Giardine, B" uniqKey="Giardine B">B Giardine</name>
</author>
<author><name sortKey="Kasson, Lr" uniqKey="Kasson L">LR Kasson</name>
</author>
<author><name sortKey="Harris, Rs" uniqKey="Harris R">RS Harris</name>
</author>
<author><name sortKey="Petersen, Dc" uniqKey="Petersen D">DC Petersen</name>
</author>
<author><name sortKey="Zhao, F" uniqKey="Zhao F">F Zhao</name>
</author>
<author><name sortKey="Qi, J" uniqKey="Qi J">J Qi</name>
</author>
<author><name sortKey="Alkan, C" uniqKey="Alkan C">C Alkan</name>
</author>
<author><name sortKey="Kidd, Jm" uniqKey="Kidd J">JM Kidd</name>
</author>
<author><name sortKey="Sun, Y" uniqKey="Sun Y">Y Sun</name>
</author>
<author><name sortKey="Drautz, Di" uniqKey="Drautz D">DI Drautz</name>
</author>
<author><name sortKey="Bouffard, P" uniqKey="Bouffard P">P Bouffard</name>
</author>
<author><name sortKey="Muzny, Dm" uniqKey="Muzny D">DM Muzny</name>
</author>
<author><name sortKey="Reid, Jg" uniqKey="Reid J">JG Reid</name>
</author>
<author><name sortKey="Nazareth, Lv" uniqKey="Nazareth L">LV Nazareth</name>
</author>
<author><name sortKey="Wang, Q" uniqKey="Wang Q">Q Wang</name>
</author>
<author><name sortKey="Burhans, R" uniqKey="Burhans R">R Burhans</name>
</author>
<author><name sortKey="Riemer, C" uniqKey="Riemer C">C Riemer</name>
</author>
<author><name sortKey="Wittekindt, Ne" uniqKey="Wittekindt N">NE Wittekindt</name>
</author>
<author><name sortKey="Moorjani, P" uniqKey="Moorjani P">P Moorjani</name>
</author>
<author><name sortKey="Tindall, Ea" uniqKey="Tindall E">EA Tindall</name>
</author>
<author><name sortKey="Danko, Cg" uniqKey="Danko C">CG Danko</name>
</author>
<author><name sortKey="Teo, Ws" uniqKey="Teo W">WS Teo</name>
</author>
<author><name sortKey="Buboltz, Am" uniqKey="Buboltz A">AM Buboltz</name>
</author>
<author><name sortKey="Zhang, Z" uniqKey="Zhang Z">Z Zhang</name>
</author>
<author><name sortKey="Ma, Q" uniqKey="Ma Q">Q Ma</name>
</author>
<author><name sortKey="Oosthuysen, A" uniqKey="Oosthuysen A">A Oosthuysen</name>
</author>
<author><name sortKey="Steenkamp, Aw" uniqKey="Steenkamp A">AW Steenkamp</name>
</author>
<author><name sortKey="Oostuisen, H" uniqKey="Oostuisen H">H Oostuisen</name>
</author>
<author><name sortKey="Venter, P" uniqKey="Venter P">P Venter</name>
</author>
<author><name sortKey="Gajewski, J" uniqKey="Gajewski J">J Gajewski</name>
</author>
<author><name sortKey="Zhang, Y" uniqKey="Zhang Y">Y Zhang</name>
</author>
<author><name sortKey="Pugh, Bf" uniqKey="Pugh B">BF Pugh</name>
</author>
<author><name sortKey="Makova, Kd" uniqKey="Makova K">KD Makova</name>
</author>
<author><name sortKey="Nekrutenko, A" uniqKey="Nekrutenko A">A Nekrutenko</name>
</author>
<author><name sortKey="Mardis, Er" uniqKey="Mardis E">ER Mardis</name>
</author>
<author><name sortKey="Patterson, N" uniqKey="Patterson N">N Patterson</name>
</author>
<author><name sortKey="Pringle, Th" uniqKey="Pringle T">TH Pringle</name>
</author>
<author><name sortKey="Chiaromonte, F" uniqKey="Chiaromonte F">F Chiaromonte</name>
</author>
<author><name sortKey="Mullikin, Jc" uniqKey="Mullikin J">JC Mullikin</name>
</author>
<author><name sortKey="Eichler, Ee" uniqKey="Eichler E">EE Eichler</name>
</author>
<author><name sortKey="Hardison, Rc" uniqKey="Hardison R">RC Hardison</name>
</author>
<author><name sortKey="Gibbs, Ra" uniqKey="Gibbs R">RA Gibbs</name>
</author>
<author><name sortKey="Harkins, Tt" uniqKey="Harkins T">TT Harkins</name>
</author>
<author><name sortKey="Hayes, Vm" uniqKey="Hayes V">VM Hayes</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Li, H" uniqKey="Li H">H Li</name>
</author>
<author><name sortKey="Homer, N" uniqKey="Homer N">N Homer</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Schroder, J" uniqKey="Schroder J">J Schröder</name>
</author>
<author><name sortKey="Schroder, H" uniqKey="Schroder H">H Schröder</name>
</author>
<author><name sortKey="Puglisi, Sj" uniqKey="Puglisi S">SJ Puglisi</name>
</author>
<author><name sortKey="Sinha, R" uniqKey="Sinha R">R Sinha</name>
</author>
<author><name sortKey="Schmidt, B" uniqKey="Schmidt B">B Schmidt</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Ilie, L" uniqKey="Ilie L">L Ilie</name>
</author>
<author><name sortKey="Fazayeli, F" uniqKey="Fazayeli F">F Fazayeli</name>
</author>
<author><name sortKey="Ilie, S" uniqKey="Ilie S">S Ilie</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Salmela, L" uniqKey="Salmela L">L Salmela</name>
</author>
<author><name sortKey="Schroder, J" uniqKey="Schroder J">J Schröder</name>
</author>
</analytic>
</biblStruct>
</listBibl>
</div1>
</back>
</TEI>
</pmc>
<pubmed><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Querying large read collections in main memory: a versatile data structure.</title>
<author><name sortKey="Philippe, Nicolas" sort="Philippe, Nicolas" uniqKey="Philippe N" first="Nicolas" last="Philippe">Nicolas Philippe</name>
<affiliation wicri:level="3"><nlm:affiliation>LIRMM, UMR 5506, CNRS and Université de Montpellier 2, CC 477, 161 rue Ada, 34095 Montpellier, France.</nlm:affiliation>
<country xml:lang="fr">France</country>
<wicri:regionArea>LIRMM, UMR 5506, CNRS and Université de Montpellier 2, CC 477, 161 rue Ada, 34095 Montpellier</wicri:regionArea>
<placeName><region type="region" nuts="2">Occitanie (région administrative)</region>
<region type="old region" nuts="2">Languedoc-Roussillon</region>
<settlement type="city">Montpellier</settlement>
</placeName>
</affiliation>
</author>
<author><name sortKey="Salson, Mikael" sort="Salson, Mikael" uniqKey="Salson M" first="Mikaël" last="Salson">Mikaël Salson</name>
</author>
<author><name sortKey="Lecroq, Thierry" sort="Lecroq, Thierry" uniqKey="Lecroq T" first="Thierry" last="Lecroq">Thierry Lecroq</name>
</author>
<author><name sortKey="Leonard, Martine" sort="Leonard, Martine" uniqKey="Leonard M" first="Martine" last="Léonard">Martine Léonard</name>
</author>
<author><name sortKey="Commes, Therese" sort="Commes, Therese" uniqKey="Commes T" first="Thérèse" last="Commes">Thérèse Commes</name>
</author>
<author><name sortKey="Rivals, Eric" sort="Rivals, Eric" uniqKey="Rivals E" first="Eric" last="Rivals">Eric Rivals</name>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">PubMed</idno>
<date when="2011">2011</date>
<idno type="RBID">pubmed:21682852</idno>
<idno type="pmid">21682852</idno>
<idno type="doi">10.1186/1471-2105-12-242</idno>
<idno type="wicri:Area/PubMed/Corpus">001E67</idno>
<idno type="wicri:explorRef" wicri:stream="PubMed" wicri:step="Corpus" wicri:corpus="PubMed">001E67</idno>
<idno type="wicri:Area/PubMed/Curation">001E67</idno>
<idno type="wicri:explorRef" wicri:stream="PubMed" wicri:step="Curation">001E67</idno>
<idno type="wicri:Area/PubMed/Checkpoint">001D54</idno>
<idno type="wicri:explorRef" wicri:stream="Checkpoint" wicri:step="PubMed">001D54</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en">Querying large read collections in main memory: a versatile data structure.</title>
<author><name sortKey="Philippe, Nicolas" sort="Philippe, Nicolas" uniqKey="Philippe N" first="Nicolas" last="Philippe">Nicolas Philippe</name>
<affiliation wicri:level="3"><nlm:affiliation>LIRMM, UMR 5506, CNRS and Université de Montpellier 2, CC 477, 161 rue Ada, 34095 Montpellier, France.</nlm:affiliation>
<country xml:lang="fr">France</country>
<wicri:regionArea>LIRMM, UMR 5506, CNRS and Université de Montpellier 2, CC 477, 161 rue Ada, 34095 Montpellier</wicri:regionArea>
<placeName><region type="region" nuts="2">Occitanie (région administrative)</region>
<region type="old region" nuts="2">Languedoc-Roussillon</region>
<settlement type="city">Montpellier</settlement>
</placeName>
</affiliation>
</author>
<author><name sortKey="Salson, Mikael" sort="Salson, Mikael" uniqKey="Salson M" first="Mikaël" last="Salson">Mikaël Salson</name>
</author>
<author><name sortKey="Lecroq, Thierry" sort="Lecroq, Thierry" uniqKey="Lecroq T" first="Thierry" last="Lecroq">Thierry Lecroq</name>
</author>
<author><name sortKey="Leonard, Martine" sort="Leonard, Martine" uniqKey="Leonard M" first="Martine" last="Léonard">Martine Léonard</name>
</author>
<author><name sortKey="Commes, Therese" sort="Commes, Therese" uniqKey="Commes T" first="Thérèse" last="Commes">Thérèse Commes</name>
</author>
<author><name sortKey="Rivals, Eric" sort="Rivals, Eric" uniqKey="Rivals E" first="Eric" last="Rivals">Eric Rivals</name>
</author>
</analytic>
<series><title level="j">BMC bioinformatics</title>
<idno type="eISSN">1471-2105</idno>
<imprint><date when="2011" type="published">2011</date>
</imprint>
</series>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Algorithms</term>
<term>Computational Biology (methods)</term>
<term>Computers</term>
<term>High-Throughput Nucleotide Sequencing</term>
<term>Humans</term>
<term>Software</term>
</keywords>
<keywords scheme="KwdFr" xml:lang="fr"><term>Algorithmes</term>
<term>Biologie informatique ()</term>
<term>Humains</term>
<term>Logiciel</term>
<term>Ordinateurs</term>
<term>Séquençage nucléotidique à haut débit</term>
</keywords>
<keywords scheme="MESH" qualifier="methods" xml:lang="en"><term>Computational Biology</term>
</keywords>
<keywords scheme="MESH" xml:lang="en"><term>Algorithms</term>
<term>Computers</term>
<term>High-Throughput Nucleotide Sequencing</term>
<term>Humans</term>
<term>Software</term>
</keywords>
<keywords scheme="MESH" xml:lang="fr"><term>Algorithmes</term>
<term>Biologie informatique</term>
<term>Humains</term>
<term>Logiciel</term>
<term>Ordinateurs</term>
<term>Séquençage nucléotidique à haut débit</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">High Throughput Sequencing (HTS) is now heavily exploited for genome (re-) sequencing, metagenomics, epigenomics, and transcriptomics and requires different, but computer intensive bioinformatic analyses. When a reference genome is available, mapping reads on it is the first step of this analysis. Read mapping programs owe their efficiency to the use of involved genome indexing data structures, like the Burrows-Wheeler transform. Recent solutions index both the genome, and the k-mers of the reads using hash-tables to further increase efficiency and accuracy. In various contexts (e.g. assembly or transcriptome analysis), read processing requires to determine the sub-collection of reads that are related to a given sequence, which is done by searching for some k-mers in the reads. Currently, many developments have focused on genome indexing structures for read mapping, but the question of read indexing remains broadly unexplored. However, the increase in sequence throughput urges for new algorithmic solutions to query large read collections efficiently.</div>
</front>
</TEI>
</pubmed>
</double>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Sante/explor/MersV1/Data/Ncbi/Merge
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000864 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Ncbi/Merge/biblio.hfd -nk 000864 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Sante |area= MersV1 |flux= Ncbi |étape= Merge |type= RBID |clé= PMC:3163563 |texte= Querying large read collections in main memory: a versatile data structure }}
Pour générer des pages wiki
HfdIndexSelect -h $EXPLOR_AREA/Data/Ncbi/Merge/RBID.i -Sk "pubmed:21682852" \ | HfdSelect -Kh $EXPLOR_AREA/Data/Ncbi/Merge/biblio.hfd \ | NlmPubMed2Wicri -a MersV1
![]() | This area was generated with Dilib version V0.6.33. | ![]() |