Streaming histogram sketching for rapid microbiome analytics
Identifieur interne : 000398 ( Pmc/Corpus ); précédent : 000397; suivant : 000399Streaming histogram sketching for rapid microbiome analytics
Auteurs : Will Pm Rowe ; Anna Paola Carrieri ; Cristina Alcon-Giner ; Shabhonam Caim ; Alex Shaw ; Kathleen Sim ; J. Simon Kroll ; Lindsay J. Hall ; Edward O. Pyzer-Knapp ; Martyn D. WinnSource :
- Microbiome [ 2049-2618 ] ; 2019.
Abstract
The growth in publically available microbiome data in recent years has yielded an invaluable resource for genomic research, allowing for the design of new studies, augmentation of novel datasets and reanalysis of published works. This vast amount of microbiome data, as well as the widespread proliferation of microbiome research and the looming era of clinical metagenomics, means there is an urgent need to develop analytics that can process huge amounts of data in a short amount of time.
To address this need, we propose a new method for tyrhe compact representation of microbiome sequencing data using similarity-preserving sketches of streaming k-mer spectra. These sketches allow for dissimilarity estimation, rapid microbiome catalogue searching and classification of microbiome samples in near real time.
We apply streaming histogram sketching to microbiome samples as a form of dimensionality reduction, creating a compressed ‘histosketch’ that can efficiently represent microbiome k-mer spectra. Using public microbiome datasets, we show that histosketches can be clustered by sample type using the pairwise Jaccard similarity estimation, consequently allowing for rapid microbiome similarity searches via a locality sensitive hashing indexing scheme.
Furthermore, we use a ‘real life’ example to show that histosketches can train machine learning classifiers to accurately label microbiome samples. Specifically, using a collection of 108 novel microbiome samples from a cohort of premature neonates, we trained and tested a random forest classifier that could accurately predict whether the neonate had received antibiotic treatment (97% accuracy, 96% precision) and could subsequently be used to classify microbiome data streams in less than 3 s.
Our method offers a new approach to rapidly process microbiome data streams, allowing samples to be rapidly clustered, indexed and classified. We also provide our implementation, Histosketching Using Little K-mers (HULK), which can histosketch a typical 2 GB microbiome in 50 s on a standard laptop using four cores, with the sketch occupying 3000 bytes of disk space. (
Url:
DOI: 10.1186/s40168-019-0653-2
PubMed: 30878035
PubMed Central: 6420756
Links to Exploration step
PMC:6420756Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Streaming histogram sketching for rapid microbiome analytics</title>
<author><name sortKey="Rowe, Will Pm" sort="Rowe, Will Pm" uniqKey="Rowe W" first="Will Pm" last="Rowe">Will Pm Rowe</name>
<affiliation><nlm:aff id="Aff1"><institution-wrap><institution-id institution-id-type="ISNI">0000 0001 0727 2226</institution-id>
<institution-id institution-id-type="GRID">grid.482271.a</institution-id>
<institution>Scientific Computing Department,</institution>
<institution>STFC Daresbury Laboratory,</institution>
</institution-wrap>
Warrington, UK</nlm:aff>
</affiliation>
</author>
<author><name sortKey="Carrieri, Anna Paola" sort="Carrieri, Anna Paola" uniqKey="Carrieri A" first="Anna Paola" last="Carrieri">Anna Paola Carrieri</name>
<affiliation><nlm:aff id="Aff2"><institution-wrap><institution-id institution-id-type="GRID">grid.14467.30</institution-id>
<institution>IBM Research,</institution>
<institution>The Hartree Centre,</institution>
</institution-wrap>
Warrington, UK</nlm:aff>
</affiliation>
</author>
<author><name sortKey="Alcon Giner, Cristina" sort="Alcon Giner, Cristina" uniqKey="Alcon Giner C" first="Cristina" last="Alcon-Giner">Cristina Alcon-Giner</name>
<affiliation><nlm:aff id="Aff3"><institution-wrap><institution-id institution-id-type="GRID">grid.420132.6</institution-id>
<institution>Quadram Institute Bioscience,</institution>
<institution>Norwich Research Park,</institution>
</institution-wrap>
Norwich, UK</nlm:aff>
</affiliation>
</author>
<author><name sortKey="Caim, Shabhonam" sort="Caim, Shabhonam" uniqKey="Caim S" first="Shabhonam" last="Caim">Shabhonam Caim</name>
<affiliation><nlm:aff id="Aff3"><institution-wrap><institution-id institution-id-type="GRID">grid.420132.6</institution-id>
<institution>Quadram Institute Bioscience,</institution>
<institution>Norwich Research Park,</institution>
</institution-wrap>
Norwich, UK</nlm:aff>
</affiliation>
</author>
<author><name sortKey="Shaw, Alex" sort="Shaw, Alex" uniqKey="Shaw A" first="Alex" last="Shaw">Alex Shaw</name>
<affiliation><nlm:aff id="Aff4"><institution-wrap><institution-id institution-id-type="ISNI">0000 0001 2113 8111</institution-id>
<institution-id institution-id-type="GRID">grid.7445.2</institution-id>
<institution>Department of Medicine, Section of Paediatrics,</institution>
<institution>Imperial College London,</institution>
</institution-wrap>
London, UK</nlm:aff>
</affiliation>
</author>
<author><name sortKey="Sim, Kathleen" sort="Sim, Kathleen" uniqKey="Sim K" first="Kathleen" last="Sim">Kathleen Sim</name>
<affiliation><nlm:aff id="Aff4"><institution-wrap><institution-id institution-id-type="ISNI">0000 0001 2113 8111</institution-id>
<institution-id institution-id-type="GRID">grid.7445.2</institution-id>
<institution>Department of Medicine, Section of Paediatrics,</institution>
<institution>Imperial College London,</institution>
</institution-wrap>
London, UK</nlm:aff>
</affiliation>
</author>
<author><name sortKey="Kroll, J Simon" sort="Kroll, J Simon" uniqKey="Kroll J" first="J. Simon" last="Kroll">J. Simon Kroll</name>
<affiliation><nlm:aff id="Aff4"><institution-wrap><institution-id institution-id-type="ISNI">0000 0001 2113 8111</institution-id>
<institution-id institution-id-type="GRID">grid.7445.2</institution-id>
<institution>Department of Medicine, Section of Paediatrics,</institution>
<institution>Imperial College London,</institution>
</institution-wrap>
London, UK</nlm:aff>
</affiliation>
</author>
<author><name sortKey="Hall, Lindsay J" sort="Hall, Lindsay J" uniqKey="Hall L" first="Lindsay J." last="Hall">Lindsay J. Hall</name>
<affiliation><nlm:aff id="Aff3"><institution-wrap><institution-id institution-id-type="GRID">grid.420132.6</institution-id>
<institution>Quadram Institute Bioscience,</institution>
<institution>Norwich Research Park,</institution>
</institution-wrap>
Norwich, UK</nlm:aff>
</affiliation>
</author>
<author><name sortKey="Pyzer Knapp, Edward O" sort="Pyzer Knapp, Edward O" uniqKey="Pyzer Knapp E" first="Edward O." last="Pyzer-Knapp">Edward O. Pyzer-Knapp</name>
<affiliation><nlm:aff id="Aff2"><institution-wrap><institution-id institution-id-type="GRID">grid.14467.30</institution-id>
<institution>IBM Research,</institution>
<institution>The Hartree Centre,</institution>
</institution-wrap>
Warrington, UK</nlm:aff>
</affiliation>
</author>
<author><name sortKey="Winn, Martyn D" sort="Winn, Martyn D" uniqKey="Winn M" first="Martyn D." last="Winn">Martyn D. Winn</name>
<affiliation><nlm:aff id="Aff1"><institution-wrap><institution-id institution-id-type="ISNI">0000 0001 0727 2226</institution-id>
<institution-id institution-id-type="GRID">grid.482271.a</institution-id>
<institution>Scientific Computing Department,</institution>
<institution>STFC Daresbury Laboratory,</institution>
</institution-wrap>
Warrington, UK</nlm:aff>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">PMC</idno>
<idno type="pmid">30878035</idno>
<idno type="pmc">6420756</idno>
<idno type="url">http://www.ncbi.nlm.nih.gov/pmc/articles/PMC6420756</idno>
<idno type="RBID">PMC:6420756</idno>
<idno type="doi">10.1186/s40168-019-0653-2</idno>
<date when="2019">2019</date>
<idno type="wicri:Area/Pmc/Corpus">000398</idno>
<idno type="wicri:explorRef" wicri:stream="Pmc" wicri:step="Corpus" wicri:corpus="PMC">000398</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en" level="a" type="main">Streaming histogram sketching for rapid microbiome analytics</title>
<author><name sortKey="Rowe, Will Pm" sort="Rowe, Will Pm" uniqKey="Rowe W" first="Will Pm" last="Rowe">Will Pm Rowe</name>
<affiliation><nlm:aff id="Aff1"><institution-wrap><institution-id institution-id-type="ISNI">0000 0001 0727 2226</institution-id>
<institution-id institution-id-type="GRID">grid.482271.a</institution-id>
<institution>Scientific Computing Department,</institution>
<institution>STFC Daresbury Laboratory,</institution>
</institution-wrap>
Warrington, UK</nlm:aff>
</affiliation>
</author>
<author><name sortKey="Carrieri, Anna Paola" sort="Carrieri, Anna Paola" uniqKey="Carrieri A" first="Anna Paola" last="Carrieri">Anna Paola Carrieri</name>
<affiliation><nlm:aff id="Aff2"><institution-wrap><institution-id institution-id-type="GRID">grid.14467.30</institution-id>
<institution>IBM Research,</institution>
<institution>The Hartree Centre,</institution>
</institution-wrap>
Warrington, UK</nlm:aff>
</affiliation>
</author>
<author><name sortKey="Alcon Giner, Cristina" sort="Alcon Giner, Cristina" uniqKey="Alcon Giner C" first="Cristina" last="Alcon-Giner">Cristina Alcon-Giner</name>
<affiliation><nlm:aff id="Aff3"><institution-wrap><institution-id institution-id-type="GRID">grid.420132.6</institution-id>
<institution>Quadram Institute Bioscience,</institution>
<institution>Norwich Research Park,</institution>
</institution-wrap>
Norwich, UK</nlm:aff>
</affiliation>
</author>
<author><name sortKey="Caim, Shabhonam" sort="Caim, Shabhonam" uniqKey="Caim S" first="Shabhonam" last="Caim">Shabhonam Caim</name>
<affiliation><nlm:aff id="Aff3"><institution-wrap><institution-id institution-id-type="GRID">grid.420132.6</institution-id>
<institution>Quadram Institute Bioscience,</institution>
<institution>Norwich Research Park,</institution>
</institution-wrap>
Norwich, UK</nlm:aff>
</affiliation>
</author>
<author><name sortKey="Shaw, Alex" sort="Shaw, Alex" uniqKey="Shaw A" first="Alex" last="Shaw">Alex Shaw</name>
<affiliation><nlm:aff id="Aff4"><institution-wrap><institution-id institution-id-type="ISNI">0000 0001 2113 8111</institution-id>
<institution-id institution-id-type="GRID">grid.7445.2</institution-id>
<institution>Department of Medicine, Section of Paediatrics,</institution>
<institution>Imperial College London,</institution>
</institution-wrap>
London, UK</nlm:aff>
</affiliation>
</author>
<author><name sortKey="Sim, Kathleen" sort="Sim, Kathleen" uniqKey="Sim K" first="Kathleen" last="Sim">Kathleen Sim</name>
<affiliation><nlm:aff id="Aff4"><institution-wrap><institution-id institution-id-type="ISNI">0000 0001 2113 8111</institution-id>
<institution-id institution-id-type="GRID">grid.7445.2</institution-id>
<institution>Department of Medicine, Section of Paediatrics,</institution>
<institution>Imperial College London,</institution>
</institution-wrap>
London, UK</nlm:aff>
</affiliation>
</author>
<author><name sortKey="Kroll, J Simon" sort="Kroll, J Simon" uniqKey="Kroll J" first="J. Simon" last="Kroll">J. Simon Kroll</name>
<affiliation><nlm:aff id="Aff4"><institution-wrap><institution-id institution-id-type="ISNI">0000 0001 2113 8111</institution-id>
<institution-id institution-id-type="GRID">grid.7445.2</institution-id>
<institution>Department of Medicine, Section of Paediatrics,</institution>
<institution>Imperial College London,</institution>
</institution-wrap>
London, UK</nlm:aff>
</affiliation>
</author>
<author><name sortKey="Hall, Lindsay J" sort="Hall, Lindsay J" uniqKey="Hall L" first="Lindsay J." last="Hall">Lindsay J. Hall</name>
<affiliation><nlm:aff id="Aff3"><institution-wrap><institution-id institution-id-type="GRID">grid.420132.6</institution-id>
<institution>Quadram Institute Bioscience,</institution>
<institution>Norwich Research Park,</institution>
</institution-wrap>
Norwich, UK</nlm:aff>
</affiliation>
</author>
<author><name sortKey="Pyzer Knapp, Edward O" sort="Pyzer Knapp, Edward O" uniqKey="Pyzer Knapp E" first="Edward O." last="Pyzer-Knapp">Edward O. Pyzer-Knapp</name>
<affiliation><nlm:aff id="Aff2"><institution-wrap><institution-id institution-id-type="GRID">grid.14467.30</institution-id>
<institution>IBM Research,</institution>
<institution>The Hartree Centre,</institution>
</institution-wrap>
Warrington, UK</nlm:aff>
</affiliation>
</author>
<author><name sortKey="Winn, Martyn D" sort="Winn, Martyn D" uniqKey="Winn M" first="Martyn D." last="Winn">Martyn D. Winn</name>
<affiliation><nlm:aff id="Aff1"><institution-wrap><institution-id institution-id-type="ISNI">0000 0001 0727 2226</institution-id>
<institution-id institution-id-type="GRID">grid.482271.a</institution-id>
<institution>Scientific Computing Department,</institution>
<institution>STFC Daresbury Laboratory,</institution>
</institution-wrap>
Warrington, UK</nlm:aff>
</affiliation>
</author>
</analytic>
<series><title level="j">Microbiome</title>
<idno type="eISSN">2049-2618</idno>
<imprint><date when="2019">2019</date>
</imprint>
</series>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass></textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en"><sec><title>Background</title>
<p id="Par1">The growth in publically available microbiome data in recent years has yielded an invaluable resource for genomic research, allowing for the design of new studies, augmentation of novel datasets and reanalysis of published works. This vast amount of microbiome data, as well as the widespread proliferation of microbiome research and the looming era of clinical metagenomics, means there is an urgent need to develop analytics that can process huge amounts of data in a short amount of time.</p>
<p id="Par2">To address this need, we propose a new method for tyrhe compact representation of microbiome sequencing data using similarity-preserving sketches of streaming k-mer spectra. These sketches allow for dissimilarity estimation, rapid microbiome catalogue searching and classification of microbiome samples in near real time.</p>
</sec>
<sec><title>Results</title>
<p id="Par3">We apply streaming histogram sketching to microbiome samples as a form of dimensionality reduction, creating a compressed ‘histosketch’ that can efficiently represent microbiome k-mer spectra. Using public microbiome datasets, we show that histosketches can be clustered by sample type using the pairwise Jaccard similarity estimation, consequently allowing for rapid microbiome similarity searches via a locality sensitive hashing indexing scheme.</p>
<p id="Par4">Furthermore, we use a ‘real life’ example to show that histosketches can train machine learning classifiers to accurately label microbiome samples. Specifically, using a collection of 108 novel microbiome samples from a cohort of premature neonates, we trained and tested a random forest classifier that could accurately predict whether the neonate had received antibiotic treatment (97% accuracy, 96% precision) and could subsequently be used to classify microbiome data streams in less than 3 s.</p>
</sec>
<sec><title>Conclusions</title>
<p id="Par5">Our method offers a new approach to rapidly process microbiome data streams, allowing samples to be rapidly clustered, indexed and classified. We also provide our implementation, Histosketching Using Little K-mers (HULK), which can histosketch a typical 2 GB microbiome in 50 s on a standard laptop using four cores, with the sketch occupying 3000 bytes of disk space. (<ext-link ext-link-type="uri" xlink:href="https://github.com/will-rowe/hulk">https://github.com/will-rowe/hulk</ext-link>
).</p>
</sec>
</div>
</front>
<back><div1 type="bibliography"><listBibl><biblStruct></biblStruct>
<biblStruct><analytic><author><name sortKey="Thompson, Lr" uniqKey="Thompson L">LR Thompson</name>
</author>
<author><name sortKey="Sanders, Jg" uniqKey="Sanders J">JG Sanders</name>
</author>
<author><name sortKey="Mcdonald, D" uniqKey="Mcdonald D">D McDonald</name>
</author>
<author><name sortKey="Amir, A" uniqKey="Amir A">A Amir</name>
</author>
<author><name sortKey="Ladau, J" uniqKey="Ladau J">J Ladau</name>
</author>
<author><name sortKey="Locey, Kj" uniqKey="Locey K">KJ Locey</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Rusch, Db" uniqKey="Rusch D">DB Rusch</name>
</author>
<author><name sortKey="Halpern, Al" uniqKey="Halpern A">AL Halpern</name>
</author>
<author><name sortKey="Sutton, G" uniqKey="Sutton G">G Sutton</name>
</author>
<author><name sortKey="Heidelberg, Kb" uniqKey="Heidelberg K">KB Heidelberg</name>
</author>
<author><name sortKey="Williamson, S" uniqKey="Williamson S">S Williamson</name>
</author>
<author><name sortKey="Yooseph, S" uniqKey="Yooseph S">S Yooseph</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Mulcahy O Rady, H" uniqKey="Mulcahy O Rady H">H Mulcahy-O’Grady</name>
</author>
<author><name sortKey="Workentine, Ml" uniqKey="Workentine M">ML Workentine</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Forbes, Jd" uniqKey="Forbes J">JD Forbes</name>
</author>
<author><name sortKey="Knox, Nc" uniqKey="Knox N">NC Knox</name>
</author>
<author><name sortKey="Peterson, C L" uniqKey="Peterson C">C-L Peterson</name>
</author>
<author><name sortKey="Reimer, Ar" uniqKey="Reimer A">AR Reimer</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Greninger, Al" uniqKey="Greninger A">AL Greninger</name>
</author>
<author><name sortKey="Naccache, Sn" uniqKey="Naccache S">SN Naccache</name>
</author>
<author><name sortKey="Federman, S" uniqKey="Federman S">S Federman</name>
</author>
<author><name sortKey="Yu, G" uniqKey="Yu G">G Yu</name>
</author>
<author><name sortKey="Mbala, P" uniqKey="Mbala P">P Mbala</name>
</author>
<author><name sortKey="Bres, V" uniqKey="Bres V">V Bres</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Kakkanatt, C" uniqKey="Kakkanatt C">C Kakkanatt</name>
</author>
<author><name sortKey="Benigno, M" uniqKey="Benigno M">M Benigno</name>
</author>
<author><name sortKey="Jackson, Vm" uniqKey="Jackson V">VM Jackson</name>
</author>
<author><name sortKey="Huang, Pl" uniqKey="Huang P">PL Huang</name>
</author>
<author><name sortKey="Ng, K" uniqKey="Ng K">K Ng</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Morgan, Xc" uniqKey="Morgan X">XC Morgan</name>
</author>
<author><name sortKey="Huttenhower, C" uniqKey="Huttenhower C">C Huttenhower</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Dubinkina, Vb" uniqKey="Dubinkina V">VB Dubinkina</name>
</author>
<author><name sortKey="Ischenko, Ds" uniqKey="Ischenko D">DS Ischenko</name>
</author>
<author><name sortKey="Ulyantsev, Vi" uniqKey="Ulyantsev V">VI Ulyantsev</name>
</author>
<author><name sortKey="Tyakht, Av" uniqKey="Tyakht A">AV Tyakht</name>
</author>
<author><name sortKey="Alexeev, Dg" uniqKey="Alexeev D">DG Alexeev</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Benoit, G" uniqKey="Benoit G">G Benoit</name>
</author>
<author><name sortKey="Peterlongo, P" uniqKey="Peterlongo P">P Peterlongo</name>
</author>
<author><name sortKey="Mariadassou, M" uniqKey="Mariadassou M">M Mariadassou</name>
</author>
<author><name sortKey="Drezen, E" uniqKey="Drezen E">E Drezen</name>
</author>
<author><name sortKey="Schbath, S" uniqKey="Schbath S">S Schbath</name>
</author>
<author><name sortKey="Lavenier, D" uniqKey="Lavenier D">D Lavenier</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Anvar, Sy" uniqKey="Anvar S">SY Anvar</name>
</author>
<author><name sortKey="Khachatryan, L" uniqKey="Khachatryan L">L Khachatryan</name>
</author>
<author><name sortKey="Vermaat, M" uniqKey="Vermaat M">M Vermaat</name>
</author>
<author><name sortKey="Van Galen, M" uniqKey="Van Galen M">M van Galen</name>
</author>
<author><name sortKey="Pulyakhina, I" uniqKey="Pulyakhina I">I Pulyakhina</name>
</author>
<author><name sortKey="Ariyurek, Y" uniqKey="Ariyurek Y">Y Ariyurek</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Libbrecht, Mw" uniqKey="Libbrecht M">MW Libbrecht</name>
</author>
<author><name sortKey="Noble, Ws" uniqKey="Noble W">WS Noble</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Seth, S" uniqKey="Seth S">S Seth</name>
</author>
<author><name sortKey="V Lim Ki, N" uniqKey="V Lim Ki N">N Välimäki</name>
</author>
<author><name sortKey="Kaski, S" uniqKey="Kaski S">S Kaski</name>
</author>
<author><name sortKey="Honkela, A" uniqKey="Honkela A">A Honkela</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Ondov, Bd" uniqKey="Ondov B">BD Ondov</name>
</author>
<author><name sortKey="Treangen, Tj" uniqKey="Treangen T">TJ Treangen</name>
</author>
<author><name sortKey="Melsted, P" uniqKey="Melsted P">P Melsted</name>
</author>
<author><name sortKey="Mallonee, Ab" uniqKey="Mallonee A">AB Mallonee</name>
</author>
<author><name sortKey="Bergman, Nh" uniqKey="Bergman N">NH Bergman</name>
</author>
<author><name sortKey="Koren, S" uniqKey="Koren S">S Koren</name>
</author>
</analytic>
</biblStruct>
<biblStruct></biblStruct>
<biblStruct><analytic><author><name sortKey="Brown, T" uniqKey="Brown T">T Brown</name>
</author>
<author><name sortKey="Irber, L" uniqKey="Irber L">L Irber</name>
</author>
</analytic>
</biblStruct>
<biblStruct></biblStruct>
<biblStruct><analytic><author><name sortKey="Bovee, R" uniqKey="Bovee R">R Bovee</name>
</author>
<author><name sortKey="Greenfield, N" uniqKey="Greenfield N">N Greenfield</name>
</author>
</analytic>
</biblStruct>
<biblStruct></biblStruct>
<biblStruct><analytic><author><name sortKey="Wu, W" uniqKey="Wu W">W Wu</name>
</author>
<author><name sortKey="Li, B" uniqKey="Li B">B Li</name>
</author>
<author><name sortKey="Chen, L" uniqKey="Chen L">L Chen</name>
</author>
<author><name sortKey="Zhang, C" uniqKey="Zhang C">C Zhang</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Ioffe, S" uniqKey="Ioffe S">S Ioffe</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Yang, D" uniqKey="Yang D">D Yang</name>
</author>
<author><name sortKey="Li, B" uniqKey="Li B">B Li</name>
</author>
<author><name sortKey="Rettig, L" uniqKey="Rettig L">L Rettig</name>
</author>
<author><name sortKey="Cudre Mauroux, P" uniqKey="Cudre Mauroux P">P Cudré-Mauroux</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Zhang, Q" uniqKey="Zhang Q">Q Zhang</name>
</author>
<author><name sortKey="Pell, J" uniqKey="Pell J">J Pell</name>
</author>
<author><name sortKey="Canino Koning, R" uniqKey="Canino Koning R">R Canino-Koning</name>
</author>
<author><name sortKey="Howe, Ac" uniqKey="Howe A">AC Howe</name>
</author>
<author><name sortKey="Brown, Ct" uniqKey="Brown C">CT Brown</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Haveliwala, T" uniqKey="Haveliwala T">T Haveliwala</name>
</author>
<author><name sortKey="Gionis, A" uniqKey="Gionis A">A Gionis</name>
</author>
<author><name sortKey="Indyk, P" uniqKey="Indyk P">P Indyk</name>
</author>
</analytic>
</biblStruct>
<biblStruct></biblStruct>
<biblStruct><analytic><author><name sortKey="Cormode, G" uniqKey="Cormode G">G Cormode</name>
</author>
<author><name sortKey="Muthukrishnan, S" uniqKey="Muthukrishnan S">S Muthukrishnan</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Koychev, I" uniqKey="Koychev I">I Koychev</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Gruning, B" uniqKey="Gruning B">B Grüning</name>
</author>
<author><name sortKey="Dale, R" uniqKey="Dale R">R Dale</name>
</author>
<author><name sortKey="Sjodin, A" uniqKey="Sjodin A">A Sjödin</name>
</author>
<author><name sortKey="Chapman, Ba" uniqKey="Chapman B">BA Chapman</name>
</author>
<author><name sortKey="Rowe, J" uniqKey="Rowe J">J Rowe</name>
</author>
<author><name sortKey="Tomkins Tinch, Ch" uniqKey="Tomkins Tinch C">CH Tomkins-Tinch</name>
</author>
</analytic>
</biblStruct>
<biblStruct></biblStruct>
<biblStruct><analytic><author><name sortKey="Bawa, M" uniqKey="Bawa M">M Bawa</name>
</author>
<author><name sortKey="Condie, T" uniqKey="Condie T">T Condie</name>
</author>
<author><name sortKey="Ganesan, P" uniqKey="Ganesan P">P Ganesan</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Pedregosa, F" uniqKey="Pedregosa F">F Pedregosa</name>
</author>
<author><name sortKey="Varoquaux, G" uniqKey="Varoquaux G">G Varoquaux</name>
</author>
<author><name sortKey="Gramfort, A" uniqKey="Gramfort A">A Gramfort</name>
</author>
<author><name sortKey="Michel, V" uniqKey="Michel V">V Michel</name>
</author>
<author><name sortKey="Thirion, B" uniqKey="Thirion B">B Thirion</name>
</author>
<author><name sortKey="Grisel, O" uniqKey="Grisel O">O Grisel</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Sczyrba, A" uniqKey="Sczyrba A">A Sczyrba</name>
</author>
<author><name sortKey="Hofmann, P" uniqKey="Hofmann P">P Hofmann</name>
</author>
<author><name sortKey="Belmann, P" uniqKey="Belmann P">P Belmann</name>
</author>
<author><name sortKey="Koslicki, D" uniqKey="Koslicki D">D Koslicki</name>
</author>
<author><name sortKey="Janssen, S" uniqKey="Janssen S">S Janssen</name>
</author>
<author><name sortKey="Droge, J" uniqKey="Droge J">J Dröge</name>
</author>
</analytic>
</biblStruct>
<biblStruct></biblStruct>
<biblStruct><analytic><author><name sortKey="Coelho, Lp" uniqKey="Coelho L">LP Coelho</name>
</author>
<author><name sortKey="Kultima, Jr" uniqKey="Kultima J">JR Kultima</name>
</author>
<author><name sortKey="Costea, Pi" uniqKey="Costea P">PI Costea</name>
</author>
<author><name sortKey="Fournier, C" uniqKey="Fournier C">C Fournier</name>
</author>
<author><name sortKey="Pan, Y" uniqKey="Pan Y">Y Pan</name>
</author>
<author><name sortKey="Czarnecki Maulden, G" uniqKey="Czarnecki Maulden G">G Czarnecki-Maulden</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Alcon Giner, C" uniqKey="Alcon Giner C">C Alcon-Giner</name>
</author>
<author><name sortKey="Caim, S" uniqKey="Caim S">S Caim</name>
</author>
<author><name sortKey="Mitra, S" uniqKey="Mitra S">S Mitra</name>
</author>
<author><name sortKey="Ketskemety, J" uniqKey="Ketskemety J">J Ketskemety</name>
</author>
<author><name sortKey="Wegmann, U" uniqKey="Wegmann U">U Wegmann</name>
</author>
<author><name sortKey="Wain, J" uniqKey="Wain J">J Wain</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Sim, K" uniqKey="Sim K">K Sim</name>
</author>
<author><name sortKey="Shaw, Ag" uniqKey="Shaw A">AG Shaw</name>
</author>
<author><name sortKey="Randell, P" uniqKey="Randell P">P Randell</name>
</author>
<author><name sortKey="Cox, Mj" uniqKey="Cox M">MJ Cox</name>
</author>
<author><name sortKey="Mcclure, Ze" uniqKey="Mcclure Z">ZE McClure</name>
</author>
<author><name sortKey="Li, M S" uniqKey="Li M">M-S Li</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Shaw, Ag" uniqKey="Shaw A">AG Shaw</name>
</author>
<author><name sortKey="Sim, K" uniqKey="Sim K">K Sim</name>
</author>
<author><name sortKey="Randell, P" uniqKey="Randell P">P Randell</name>
</author>
<author><name sortKey="Cox, Mj" uniqKey="Cox M">MJ Cox</name>
</author>
<author><name sortKey="Mcclure, Ze" uniqKey="Mcclure Z">ZE McClure</name>
</author>
<author><name sortKey="Li, M S" uniqKey="Li M">M-S Li</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Carrieri, Ap" uniqKey="Carrieri A">AP Carrieri</name>
</author>
<author><name sortKey="Rowe, Wpm" uniqKey="Rowe W">WPM Rowe</name>
</author>
<author><name sortKey="Winn, Md" uniqKey="Winn M">MD Winn</name>
</author>
<author><name sortKey="Pyzer Knapp, Eo" uniqKey="Pyzer Knapp E">EO Pyzer-Knapp</name>
</author>
</analytic>
</biblStruct>
</listBibl>
</div1>
</back>
</TEI>
<pmc article-type="research-article"><pmc-dir>properties open_access</pmc-dir>
<front><journal-meta><journal-id journal-id-type="nlm-ta">Microbiome</journal-id>
<journal-id journal-id-type="iso-abbrev">Microbiome</journal-id>
<journal-title-group><journal-title>Microbiome</journal-title>
</journal-title-group>
<issn pub-type="epub">2049-2618</issn>
<publisher><publisher-name>BioMed Central</publisher-name>
<publisher-loc>London</publisher-loc>
</publisher>
</journal-meta>
<article-meta><article-id pub-id-type="pmid">30878035</article-id>
<article-id pub-id-type="pmc">6420756</article-id>
<article-id pub-id-type="publisher-id">653</article-id>
<article-id pub-id-type="doi">10.1186/s40168-019-0653-2</article-id>
<article-categories><subj-group subj-group-type="heading"><subject>Methodology</subject>
</subj-group>
</article-categories>
<title-group><article-title>Streaming histogram sketching for rapid microbiome analytics</article-title>
</title-group>
<contrib-group><contrib contrib-type="author" corresp="yes" equal-contrib="yes"><contrib-id contrib-id-type="orcid">http://orcid.org/0000-0003-0384-4463</contrib-id>
<name><surname>Rowe</surname>
<given-names>Will PM</given-names>
</name>
<address><email>will.rowe@stfc.ac.uk</email>
</address>
<xref ref-type="aff" rid="Aff1">1</xref>
</contrib>
<contrib contrib-type="author" equal-contrib="yes"><name><surname>Carrieri</surname>
<given-names>Anna Paola</given-names>
</name>
<address><email>acarrieri@uk.ibm.com</email>
</address>
<xref ref-type="aff" rid="Aff2">2</xref>
</contrib>
<contrib contrib-type="author"><name><surname>Alcon-Giner</surname>
<given-names>Cristina</given-names>
</name>
<address><email>Cristina.Alcon@quadram.ac.uk</email>
</address>
<xref ref-type="aff" rid="Aff3">3</xref>
</contrib>
<contrib contrib-type="author"><name><surname>Caim</surname>
<given-names>Shabhonam</given-names>
</name>
<address><email>Shabhonam.Caim@quadram.ac.uk</email>
</address>
<xref ref-type="aff" rid="Aff3">3</xref>
</contrib>
<contrib contrib-type="author"><name><surname>Shaw</surname>
<given-names>Alex</given-names>
</name>
<address><email>a.shaw@imperial.ac.uk</email>
</address>
<xref ref-type="aff" rid="Aff4">4</xref>
</contrib>
<contrib contrib-type="author"><name><surname>Sim</surname>
<given-names>Kathleen</given-names>
</name>
<address><email>k.sim@imperial.ac.uk</email>
</address>
<xref ref-type="aff" rid="Aff4">4</xref>
</contrib>
<contrib contrib-type="author"><name><surname>Kroll</surname>
<given-names>J. Simon</given-names>
</name>
<address><email>s.kroll@imperial.ac.uk</email>
</address>
<xref ref-type="aff" rid="Aff4">4</xref>
</contrib>
<contrib contrib-type="author" corresp="yes"><name><surname>Hall</surname>
<given-names>Lindsay J.</given-names>
</name>
<address><email>Lindsay.Hall@quadram.ac.uk</email>
</address>
<xref ref-type="aff" rid="Aff3">3</xref>
</contrib>
<contrib contrib-type="author"><name><surname>Pyzer-Knapp</surname>
<given-names>Edward O.</given-names>
</name>
<address><email>EPyzerK3@uk.ibm.com</email>
</address>
<xref ref-type="aff" rid="Aff2">2</xref>
</contrib>
<contrib contrib-type="author"><name><surname>Winn</surname>
<given-names>Martyn D.</given-names>
</name>
<address><email>martyn.winn@stfc.ac.uk</email>
</address>
<xref ref-type="aff" rid="Aff1">1</xref>
</contrib>
<aff id="Aff1"><label>1</label>
<institution-wrap><institution-id institution-id-type="ISNI">0000 0001 0727 2226</institution-id>
<institution-id institution-id-type="GRID">grid.482271.a</institution-id>
<institution>Scientific Computing Department,</institution>
<institution>STFC Daresbury Laboratory,</institution>
</institution-wrap>
Warrington, UK</aff>
<aff id="Aff2"><label>2</label>
<institution-wrap><institution-id institution-id-type="GRID">grid.14467.30</institution-id>
<institution>IBM Research,</institution>
<institution>The Hartree Centre,</institution>
</institution-wrap>
Warrington, UK</aff>
<aff id="Aff3"><label>3</label>
<institution-wrap><institution-id institution-id-type="GRID">grid.420132.6</institution-id>
<institution>Quadram Institute Bioscience,</institution>
<institution>Norwich Research Park,</institution>
</institution-wrap>
Norwich, UK</aff>
<aff id="Aff4"><label>4</label>
<institution-wrap><institution-id institution-id-type="ISNI">0000 0001 2113 8111</institution-id>
<institution-id institution-id-type="GRID">grid.7445.2</institution-id>
<institution>Department of Medicine, Section of Paediatrics,</institution>
<institution>Imperial College London,</institution>
</institution-wrap>
London, UK</aff>
</contrib-group>
<pub-date pub-type="epub"><day>16</day>
<month>3</month>
<year>2019</year>
</pub-date>
<pub-date pub-type="pmc-release"><day>16</day>
<month>3</month>
<year>2019</year>
</pub-date>
<pub-date pub-type="collection"><year>2019</year>
</pub-date>
<volume>7</volume>
<elocation-id>40</elocation-id>
<history><date date-type="received"><day>25</day>
<month>9</month>
<year>2018</year>
</date>
<date date-type="accepted"><day>1</day>
<month>3</month>
<year>2019</year>
</date>
</history>
<permissions><copyright-statement>© The Author(s). 2019</copyright-statement>
<license license-type="OpenAccess"><license-p><bold>Open Access</bold>
This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (<ext-link ext-link-type="uri" xlink:href="http://creativecommons.org/licenses/by/4.0/">http://creativecommons.org/licenses/by/4.0/</ext-link>
), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made. The Creative Commons Public Domain Dedication waiver (<ext-link ext-link-type="uri" xlink:href="http://creativecommons.org/publicdomain/zero/1.0/">http://creativecommons.org/publicdomain/zero/1.0/</ext-link>
) applies to the data made available in this article, unless otherwise stated.</license-p>
</license>
</permissions>
<abstract id="Abs1"><sec><title>Background</title>
<p id="Par1">The growth in publically available microbiome data in recent years has yielded an invaluable resource for genomic research, allowing for the design of new studies, augmentation of novel datasets and reanalysis of published works. This vast amount of microbiome data, as well as the widespread proliferation of microbiome research and the looming era of clinical metagenomics, means there is an urgent need to develop analytics that can process huge amounts of data in a short amount of time.</p>
<p id="Par2">To address this need, we propose a new method for tyrhe compact representation of microbiome sequencing data using similarity-preserving sketches of streaming k-mer spectra. These sketches allow for dissimilarity estimation, rapid microbiome catalogue searching and classification of microbiome samples in near real time.</p>
</sec>
<sec><title>Results</title>
<p id="Par3">We apply streaming histogram sketching to microbiome samples as a form of dimensionality reduction, creating a compressed ‘histosketch’ that can efficiently represent microbiome k-mer spectra. Using public microbiome datasets, we show that histosketches can be clustered by sample type using the pairwise Jaccard similarity estimation, consequently allowing for rapid microbiome similarity searches via a locality sensitive hashing indexing scheme.</p>
<p id="Par4">Furthermore, we use a ‘real life’ example to show that histosketches can train machine learning classifiers to accurately label microbiome samples. Specifically, using a collection of 108 novel microbiome samples from a cohort of premature neonates, we trained and tested a random forest classifier that could accurately predict whether the neonate had received antibiotic treatment (97% accuracy, 96% precision) and could subsequently be used to classify microbiome data streams in less than 3 s.</p>
</sec>
<sec><title>Conclusions</title>
<p id="Par5">Our method offers a new approach to rapidly process microbiome data streams, allowing samples to be rapidly clustered, indexed and classified. We also provide our implementation, Histosketching Using Little K-mers (HULK), which can histosketch a typical 2 GB microbiome in 50 s on a standard laptop using four cores, with the sketch occupying 3000 bytes of disk space. (<ext-link ext-link-type="uri" xlink:href="https://github.com/will-rowe/hulk">https://github.com/will-rowe/hulk</ext-link>
).</p>
</sec>
</abstract>
<funding-group><award-group><funding-source><institution-wrap><institution-id institution-id-type="FundRef">http://dx.doi.org/10.13039/501100000271</institution-id>
<institution>Science and Technology Facilities Council</institution>
</institution-wrap>
</funding-source>
</award-group>
</funding-group>
<funding-group><award-group><funding-source><institution-wrap><institution-id institution-id-type="FundRef">http://dx.doi.org/10.13039/100004440</institution-id>
<institution>Wellcome Trust</institution>
</institution-wrap>
</funding-source>
<award-id>100/974/C/13/Z</award-id>
<principal-award-recipient><name><surname>Hall</surname>
<given-names>Lindsay J.</given-names>
</name>
</principal-award-recipient>
</award-group>
</funding-group>
<funding-group><award-group><funding-source><institution-wrap><institution-id institution-id-type="FundRef">http://dx.doi.org/10.13039/501100000268</institution-id>
<institution>Biotechnology and Biological Sciences Research Council</institution>
</institution-wrap>
</funding-source>
<award-id>BB/M011216/1</award-id>
<award-id>BB/R012490/1</award-id>
<principal-award-recipient><name><surname>Alcon-Giner</surname>
<given-names>Cristina</given-names>
</name>
<name><surname>Hall</surname>
<given-names>Lindsay J.</given-names>
</name>
</principal-award-recipient>
</award-group>
</funding-group>
<funding-group><award-group><funding-source><institution>Winnicott Foundation</institution>
</funding-source>
<award-id>None</award-id>
</award-group>
</funding-group>
<custom-meta-group><custom-meta><meta-name>issue-copyright-statement</meta-name>
<meta-value>© The Author(s) 2019</meta-value>
</custom-meta>
</custom-meta-group>
</article-meta>
</front>
<body><sec id="Sec1"><title>Background</title>
<p id="Par6">The global corpus of microbiome sequence data is being augmented daily with vast volumes of data, particularly as a result of large-scale sequencing initiatives such as the Human Microbiome Project (HMP) [<xref ref-type="bibr" rid="CR1">1</xref>
], the Earth Microbiome Project [<xref ref-type="bibr" rid="CR2">2</xref>
] and the Global Ocean Survey [<xref ref-type="bibr" rid="CR3">3</xref>
]. Data outputs will continue to increase, particularly as metagenomics within the clinical field is more widely being accepted and adopted [<xref ref-type="bibr" rid="CR4">4</xref>
], and as sequencing costs continue to decline [<xref ref-type="bibr" rid="CR5">5</xref>
].</p>
<p id="Par7">We are now at the point where our ability to analyse microbiome data quickly and effectively is the main bottleneck in our workflows, particularly when it comes to real-time sequencing platforms [<xref ref-type="bibr" rid="CR5">5</xref>
, <xref ref-type="bibr" rid="CR6">6</xref>
]. In addition, we also need to ensure that existing microbiome data remains accessible and usable (including for end users, e.g. clinicians), so that it can be readily incorporated into our new analyses and generate testable hypotheses for validation/confirmation in experimental systems. It is becoming clear that current microbiome analytics are not suitable in this age of ‘big data’, particularly in terms of data retrieval and sample classification [<xref ref-type="bibr" rid="CR7">7</xref>
].</p>
<p id="Par8">Current microbiome analytics can be largely split into referenced-based or de novo approaches [<xref ref-type="bibr" rid="CR8">8</xref>
]. Whereas reference-based analyses (such as taxonomic classification) can often result in sequencing data being excluded and high computational requirements, de novo approaches circumvent these issues. For example, the pairwise comparison of k-mer spectra is a de novo analysis method that has been routinely used in recent years for clustering microbiomes using dissimilarity measures [<xref ref-type="bibr" rid="CR9">9</xref>
, <xref ref-type="bibr" rid="CR10">10</xref>
] (see Table <xref rid="Tab1" ref-type="table">1</xref>
for a summary of technical terms). These measures are used to identify microbiome composition changes in studies that involve longitudinal sampling or multiple isolation sites [<xref ref-type="bibr" rid="CR11">11</xref>
]. However, k-mer spectra can still take considerable time to compute and are relatively large in file size, and new sample comparisons require additional computation. As well as this, machine learning (ML) frameworks will struggle to use these de novo outputs as feature vectors due to their scale. This is a potential barrier to the use of these methods in microbiome analytics as ML can help solve many of the data problems encountered in genomics and holds great potential for microbiome analytics [<xref ref-type="bibr" rid="CR12">12</xref>
].<table-wrap id="Tab1"><label>Table 1</label>
<caption><p>Summary of technical terms</p>
</caption>
<table frame="hsides" rules="groups"><thead><tr><th>Term</th>
<th>Definition</th>
</tr>
</thead>
<tbody><tr><td>Consistent weighted sampling</td>
<td>An efficient method of sub-sampling histogram data that takes into account the frequency of each bin</td>
</tr>
<tr><td>De novo</td>
<td>Analyses based solely on the collected sequence data</td>
</tr>
<tr><td>Dimensionality reduction</td>
<td>Representing the sequence data in a metagenome by a relatively small number of collective quantities</td>
</tr>
<tr><td>Dissimilarity measure</td>
<td>A measure of how dissimilar two metagenomes are, typically used to identify significant changes in microbiome composition</td>
</tr>
<tr><td>Feature vectors</td>
<td>A set of key quantities of a dataset that can be used as input to a machine learning algorithm</td>
</tr>
<tr><td>Histosketch</td>
<td>A small approximate representation of histogram data, such as a k-mer spectrum.</td>
</tr>
<tr><td>Jaccard similarity</td>
<td>A measure of the similarity of two datasets based on the proportion of shared members.</td>
</tr>
<tr><td>K-mer</td>
<td>A short sub-sequence extracted from a read or genome</td>
</tr>
<tr><td>K-mer spectrum</td>
<td>The set of all observed k-mers, together with their abundances in the sequence dataset</td>
</tr>
<tr><td>Locality-sensitive hashing</td>
<td>A method of dimensionality reduction which hashes sequence data in such a way that similar sequences are kept together</td>
</tr>
<tr><td>Reference-based</td>
<td>Making use of existing reference genomes to align and classify new sequencing data</td>
</tr>
</tbody>
</table>
</table-wrap>
</p>
<p id="Par9">The application of other techniques to reduce dimensionality or complexity of genomic data has tried to address some of these issues. By reducing the dimensionality of data, these techniques offer approximate answers to bioinformatic questions (within definable error bounds) but can obtain these answers with much reduced time and memory requirements. These techniques have ranged from distributed string mining of informative k-mers [<xref ref-type="bibr" rid="CR13">13</xref>
] to the recent use of locality-sensitive hashing (LSH) [<xref ref-type="bibr" rid="CR14">14</xref>
–<xref ref-type="bibr" rid="CR18">18</xref>
]. MinHash is one form of LSH that has greatly improved genomic analysis speeds for operations such as sample clustering, database searching and phylogenetic estimation; it works through reducing sequence data to small, representative sketches using a set of minimum k-mer hash values [<xref ref-type="bibr" rid="CR14">14</xref>
]. However, although MinHash-based tools can be used to great effect for certain microbiome analytics (e.g. what genomes are in my microbiome?), there remain limitations to standard MinHash techniques, such as the loss of k-mer frequency information and the impact of relative set size on the Jaccard similarity estimates [<xref ref-type="bibr" rid="CR19">19</xref>
, <xref ref-type="bibr" rid="CR20">20</xref>
]. Although some MinHash genomic implementations address these limitations (e.g. the over-sketching and track-abundance methods of the MinHash tools ‘finch’ and ‘sourmash’), they do not utilise the frequencies of all observed k-mers in generating the sketch for a given sample. With this in mind, we suggest that additional de novo microbiome analysis methods are required in this era of microbiome ‘big data’ in order to perform essential tasks such as rapid similarity, indexing and classification operations. This is particularly pertinent within a clinical metagenomics setting, as accurate and ‘useful’ data is required for downstream analysis and clinical decision making, e.g. antibiotic treatment choices [<xref ref-type="bibr" rid="CR7">7</xref>
]. This paper offers a novel method to augment existing microbiome analysis tools and workflows, with a view to mitigating the above limitations.</p>
<p id="Par10">Here we present a data sketching method for clustering, indexing and classifying microbiome sequencing data. We also describe and demonstrate our software implementation, Histosketching Using Little K-mers (HULK), that is a user-friendly and efficient implementation of the method. Our method reduces microbiome sequence data streams to an updateable ‘histosketch’ of the underlying k-mer spectrum for a sample. We utilise consistent weighted sampling to incorporate k-mer frequency information into the histosketch, allowing the use of weighted and standard Jaccard similarity for histosketch comparisons and sample retrieval [<xref ref-type="bibr" rid="CR21">21</xref>
]. Our method combines the recently proposed histogram sketching algorithm of Yang et al. with count-min sketching of k-mer spectra and our recent implementation of LSH forest indexing for microbiome searching [<xref ref-type="bibr" rid="CR17">17</xref>
, <xref ref-type="bibr" rid="CR22">22</xref>
, <xref ref-type="bibr" rid="CR23">23</xref>
]. We show our method to accurately cluster microbiome samples by sample type and demonstrate the utility of these histosketches to create and search microbiome sequence databases. Finally, we show that histosketches are suitable features for training ML classifiers and can accurately classify microbiome samples according to antibiotic treatment history in at-risk preterm infant populations. We anticipate that our method and accompanying software will work toward addressing the current demand for fast and accurate microbiome comparisons in temporal and spatial studies.</p>
</sec>
<sec id="Sec2"><title>Materials and methods</title>
<p id="Par11">Here we describe our method for the compact representation of microbiome sequencing data using similarity-preserving histosketches of streaming k-mer spectra (Fig. <xref rid="Fig1" ref-type="fig">1</xref>
). We then document our implementation, HULK, and describe several use cases.<fig id="Fig1"><label>Fig. 1</label>
<caption><p>Overview of our method to histosketch microbiome samples from sequence data streams. <bold>a</bold>
During counting, sequence reads are collected from the data stream by <italic>n</italic>
counting processes. Reads are decomposed to canonical k-mers, encoded to uint64 values and used to increment local count-min sketches. Once <italic>X</italic>
reads have been received from the data stream, approximate k-mer counts from the counting processes are transmitted as histogram elements to the single sketching process. <bold>b</bold>
To update the histosketch, the incoming histogram element is hashed and compared against each hash value (<italic>W</italic>
) or the previous histosketch (<italic>S</italic>
), updating <italic>S</italic>
and <italic>W</italic>
if a new minimum is encountered. To hash the incoming vector, uniform scaling is applied and a cumulative frequency estimate is made using a count-min sketch; we then utilise CWS to generate a hash value for the updated histogram bin</p>
</caption>
<graphic xlink:href="40168_2019_653_Fig1_HTML" id="MO1"></graphic>
</fig>
</p>
<sec id="Sec3"><title>Histosketching microbiome data</title>
<p id="Par12">We use the k-mer spectrum (a normalised vector of k-mer frequencies) to represent microbiome diversity, which is a standard analysis method that allows for metagenome dissimilarity analysis [<xref ref-type="bibr" rid="CR9">9</xref>
, <xref ref-type="bibr" rid="CR10">10</xref>
]. However, rather than computing and storing a full k-mer spectrum after reading the sequence data, which is resource intensive (in terms of memory or disk space), we use the recently proposed histosketch data structure to maintain a set of fixed size sketches to approximate the overall k-mer spectrum as it is received from a data stream [<xref ref-type="bibr" rid="CR22">22</xref>
]. The histosketch has two properties making it suitable for this application: (1) it is updateable and (2) it is similarity-preserving. Thus, as new data is received, we can incrementally update the histosketch of the underlying k-mer spectrum and also approximate similarity to other spectra.</p>
<p id="Par13">We view the k-mer spectrum as a histogram, where k-mers from a microbiome sample are hashed uniformly across N bins and the frequency value of a bin corresponds to observed k-mer frequency. In order to incorporate both the bin and frequency (a weighted set) into the histosketch, we employ consistent weighted sampling (CWS) to generate hash values for each histogram element, which ensures that the computational complexity of hashing is independent of bin frequency [<xref ref-type="bibr" rid="CR21">21</xref>
, <xref ref-type="bibr" rid="CR22">22</xref>
].</p>
<sec id="Sec4"><title>Consistent weighted sampling</title>
<p id="Par14">As highlighted in the introduction, a drawback to the efficient set similarity estimations afforded by MinHash sketches is that the input is restricted to binary sets and does not account for weighted sets (e.g. k-mer frequencies). To overcome this, histosketching employs CWS to account for element frequency and approximate the generalised Jaccard similarity between weighted sets, without splitting each weighted element into sub-elements and computing independent hash values (quantization) [<xref ref-type="bibr" rid="CR20">20</xref>
, <xref ref-type="bibr" rid="CR21">21</xref>
, <xref ref-type="bibr" rid="CR24">24</xref>
, <xref ref-type="bibr" rid="CR25">25</xref>
].</p>
<p id="Par15">For a set of k-mer spectrum histogram bins, <italic>W</italic>
, where each bin, <italic>k</italic>
, has a frequency value, <italic>W</italic>
<sub><italic>k</italic>
</sub>
≥ 0, CWS will produce a sample, (<italic>k</italic>
, <italic>a</italic>
<sub><italic>k</italic>
</sub>
): 0 ≤ <italic>a</italic>
<sub><italic>k</italic>
</sub>
≤ <italic>W</italic>
<sub><italic>k</italic>
</sub>
, which is both uniform and consistent. This CWS sample (<italic>k</italic>
, <italic>a</italic>
<sub>k</sub>
) corresponds to the k-mer spectrum histogram bin (<italic>k</italic>
) and its scaled weight (<italic>a</italic>
<sub><italic>k</italic>
</sub>
). The CWS sample is uniformly sampled from <italic>∪</italic>
<sub><italic>k</italic>
</sub>
{<italic>k</italic>
} × [0, <italic>W</italic>
<sub><italic>k</italic>
</sub>
], meaning that the probability of selecting <italic>k</italic>
from <italic>W</italic>
is proportional to the k-mer frequency, <italic>W</italic>
<sub><italic>k</italic>
</sub>
, and <italic>y</italic>
is uniformly distributed on [0, <italic>W</italic>
<sub><italic>k</italic>
</sub>
]. The sample is also consistent as given two weighted sets, <italic>W</italic>
1 and <italic>W</italic>
2, if ∀<italic>k</italic>
, <italic>W</italic>
1<sub><italic>k</italic>
</sub>
≤ <italic>W</italic>
2<sub><italic>k</italic>
</sub>
, a sub-element (<italic>k</italic>
, <italic>a</italic>
<sub><italic>k</italic>
</sub>
) is selected from W1 and satisfies <italic>y</italic>
<sub><italic>k</italic>
</sub>
≤ <italic>W</italic>
2<sub><italic>k</italic>
</sub>
, then (<italic>k</italic>
, <italic>a</italic>
<sub><italic>k</italic>
</sub>
) will also be selected from <italic>W</italic>
2 [<xref ref-type="bibr" rid="CR20">20</xref>
, <xref ref-type="bibr" rid="CR21">21</xref>
].</p>
<p id="Par16">In order to generate a consistent sample for a member of a weighted set, CWS first samples three distributions using all elements from the set. So, for each <italic>k</italic>
in <italic>W</italic>
, CWS samples from <italic>r</italic>
<sub><italic>k</italic>
</sub>
∼ gamma (1, 2), <italic>β</italic>
<sub><italic>k</italic>
</sub>
∼ uniform (0, 1) and <italic>c</italic>
<sub><italic>k</italic>
</sub>
∼ gamma (1, 2). Once these distributions have been sampled, CWS can then generate a consistent sample for any given element from the set. CWS uses the following two equations (Eqs. <xref rid="Equ1" ref-type="">1</xref>
and <xref rid="Equ2" ref-type="">2</xref>
) to output a consistent weight, <italic>a</italic>
<sub><italic>k</italic>
</sub>
.</p>
<p id="Par17"><disp-formula id="Equ1"><label>1</label>
<alternatives><tex-math id="M1">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$$ {y}_k=\exp\;\left(\log\;{W}_k-{r}_k{\beta}_k\right) $$\end{document}</tex-math>
<mml:math id="M2" display="block"><mml:msub><mml:mi>y</mml:mi>
<mml:mi>k</mml:mi>
</mml:msub>
<mml:mo>=</mml:mo>
<mml:mo>exp</mml:mo>
<mml:mspace width="0.12em"></mml:mspace>
<mml:mfenced close=")" open="("><mml:mrow><mml:mo>log</mml:mo>
<mml:mspace width="0.12em"></mml:mspace>
<mml:msub><mml:mi>W</mml:mi>
<mml:mi>k</mml:mi>
</mml:msub>
<mml:mo>−</mml:mo>
<mml:msub><mml:mi>r</mml:mi>
<mml:mi>k</mml:mi>
</mml:msub>
<mml:msub><mml:mi>β</mml:mi>
<mml:mi>k</mml:mi>
</mml:msub>
</mml:mrow>
</mml:mfenced>
</mml:math>
<graphic xlink:href="40168_2019_653_Article_Equ1.gif" position="anchor"></graphic>
</alternatives>
</disp-formula>
</p>
<p id="Par18"><disp-formula id="Equ2"><label>2</label>
<alternatives><tex-math id="M3">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$$ {a}_k=\frac{c_k}{y_k\exp \left({r}_k\right)} $$\end{document}</tex-math>
<mml:math id="M4" display="block"><mml:msub><mml:mi>a</mml:mi>
<mml:mi>k</mml:mi>
</mml:msub>
<mml:mo>=</mml:mo>
<mml:mfrac><mml:msub><mml:mi>c</mml:mi>
<mml:mi>k</mml:mi>
</mml:msub>
<mml:mrow><mml:msub><mml:mi>y</mml:mi>
<mml:mi>k</mml:mi>
</mml:msub>
<mml:mo>exp</mml:mo>
<mml:mfenced close=")" open="("><mml:msub><mml:mi>r</mml:mi>
<mml:mi>k</mml:mi>
</mml:msub>
</mml:mfenced>
</mml:mrow>
</mml:mfrac>
<mml:mspace width="0.12em"></mml:mspace>
</mml:math>
<graphic xlink:href="40168_2019_653_Article_Equ2.gif" position="anchor"></graphic>
</alternatives>
</disp-formula>
</p>
<p id="Par19">Equations <xref rid="Equ1" ref-type="">1</xref>
and <xref rid="Equ2" ref-type="">2</xref>
generate ‘active indices’ and are used to hash an element (<italic>k</italic>
) in proportion to its weight (<italic>W</italic>
<sub><italic>k</italic>
</sub>
). The two active indices allow for the implicit construction of an exponential distribution for each weighted element (in our case, a k-mer spectrum histogram bin and its frequency). In the context of histosketching, hashing a histogram bin is performed by drawing a value from the exponential distribution parameterized by the bin frequency, meaning that a minimum hash value for a histogram bin will be sampled in proportion to the frequency of that bin. Use of the log domain in the active indices avoids most transcendental function computations.</p>
</sec>
<sec id="Sec5"><title>Histosketch creation</title>
<p id="Par20">Equations <xref rid="Equ1" ref-type="">1</xref>
and <xref rid="Equ2" ref-type="">2</xref>
describe the CWS method, which we apply to sample a k-mer spectrum in a way that takes the relative abundance of k-mers into account. To generate a sketch of a k-mer spectrum originating from a biological sample, the k-mer spectrum is sampled <italic>Z</italic>
times, where <italic>Z</italic>
is the size of the sketch.</p>
<p id="Par21">We will denote our underlying k-mer spectrum (a histogram) as <italic>V</italic>
, with cardinality |<italic>V</italic>
| = <italic>X</italic>
(<italic>i</italic>
= 1, …, <italic>X</italic>
). The corresponding histosketch we will denote as <italic>S</italic>
, with cardinality |<italic>S</italic>
| = <italic>Z</italic>
(<italic>j</italic>
= 1, …, <italic>Z</italic>
). To initialise <italic>S</italic>
from <italic>V</italic>
, the first three independent variables are sampled from the CWS distributions: <italic>r</italic>
<sub><italic>i</italic>
</sub>
,<sub><italic>j</italic>
</sub>
∼ gamma (1, 2), <italic>c</italic>
<sub><italic>i</italic>
</sub>
,<sub><italic>j</italic>
</sub>
∼ gamma (1, 2) and <italic>β</italic>
<sub><italic>i</italic>
</sub>
,<sub><italic>j</italic>
</sub>
∼ uniform (0, 1) for <italic>i</italic>
= 1, …, <italic>X</italic>
and <italic>j</italic>
= 1, …, <italic>Z</italic>
. We then use Algorithm 1 of Yang et al. for histosketch creation [<xref ref-type="bibr" rid="CR22">22</xref>
]. The sketch, <italic>S</italic>
, and the corresponding hash values, <italic>A</italic>
, are both kept as the histosketch (<italic>A</italic>
allows for incremental sketch updating).</p>
<graphic position="anchor" xlink:href="40168_2019_653_Figa_HTML" id="MO2"></graphic>
<p id="Par22">To summarise, to create an element <italic>S</italic>
<sub><italic>j</italic>
</sub>
for one histosketch slot, based on underlying histogram <italic>V</italic>
, we select the histogram element <italic>V</italic>
<sub><italic>i</italic>
</sub>
whose hash value is minimal and also keep the corresponding hash value (<italic>A</italic>
<sub><italic>j</italic>
</sub>
).</p>
</sec>
<sec id="Sec6"><title>Histosketch updating</title>
<p id="Par23">To update the histosketch as a new histogram element is received, the previous sketch <italic>S</italic>
and the sketch hash values <italic>A</italic>
are required. In its simplest form, the histosketch incremental update works by hashing and evaluating the incoming element against each slot of the histosketch. The cumulative bin frequency of the incoming element is estimated using a persistent count-min sketch [<xref ref-type="bibr" rid="CR26">26</xref>
]; the frequency estimate is then used to update the hash value for the required histogram bin. If this hash value is now a minimum, the sketch slot and corresponding hash value are updated.</p>
<p id="Par24">In addition to this histosketch update method, we can also utilise the gradual forgetting weights of the original histosketch implementation to adjust for changes in the underlying distribution (concept drift) [<xref ref-type="bibr" rid="CR22">22</xref>
, <xref ref-type="bibr" rid="CR27">27</xref>
]. Prior to the update, uniform scaling is applied to the estimate frequency counts. After this, the histosketh hashes are scaled using a decay weight before evaluating against the incoming element.</p>
</sec>
</sec>
<sec id="Sec7"><title>Our implementation</title>
<p id="Par25">We have implemented our method as an easy to use a program called HULK. HULK is written in Go (version 1.11) and compiles for a variety of operating systems and architectures. It is also packaged for installation with Bioconda and Biocontainers [<xref ref-type="bibr" rid="CR28">28</xref>
, <xref ref-type="bibr" rid="CR29">29</xref>
]. The HULK software uses a UKRI licence, which is free for academic use. HULK utilises a concurrent pipeline pattern that is driven by the flow of data between structs. This pattern facilitates the streaming of data from the standard input (STDIN), as well as from disk, and allows the HULK subcommands to be piped together and operate on data streams:</p>
<p id="Par26"><disp-formula id="Equa"><alternatives><tex-math id="M5">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$$ \mathrm{gunzip}-\mathrm{c}\ \mathrm{reads}.\mathrm{fq}\mid \mathrm{hulk}\ \mathrm{sketch} $$\end{document}</tex-math>
<mml:math id="M6" display="block"><mml:mtext>gunzip</mml:mtext>
<mml:mo>−</mml:mo>
<mml:mi mathvariant="normal">c</mml:mi>
<mml:mspace width="0.25em"></mml:mspace>
<mml:mtext>reads</mml:mtext>
<mml:mo>.</mml:mo>
<mml:mi>fq</mml:mi>
<mml:mspace width="0.25em"></mml:mspace>
<mml:mo>∣</mml:mo>
<mml:mspace width="0.25em"></mml:mspace>
<mml:mtext>hulk sketch</mml:mtext>
</mml:math>
<graphic xlink:href="40168_2019_653_Article_Equa.gif" position="anchor"></graphic>
</alternatives>
</disp-formula>
</p>
<sec id="Sec8"><title>Histosketching</title>
<p id="Par27">The HULK subcommand ‘sketch’ performs histosketching on a FASTQ data stream. Reads are collected from the data stream by one or more independent counting processes (Fig. <xref rid="Fig1" ref-type="fig">1</xref>
: counting), each utilising a separate Go routine for concurrent counting. Each counting process will count reads until an interval is reached (e.g. 1 million reads have been seen) or a signal is sent (e.g. the sample has been classified using a downstream ML classifier, see the “<xref rid="Sec11" ref-type="sec">Random forest classifier</xref>
” section). The counting processes will then send their count data via a Go channel to be histosketched and then wipe their stores before collecting more reads.</p>
<p id="Par28">A read is received by the counting process as a slice of bytes, and the canonical k-mers are encoded to unsigned integers (uint64) using bit shift operations. Once encoded, the k-mer frequency is updated in the local store of the counting process. To ensure the counting processes operate in a fixed amount of memory, we again use the count-min sketch data structure to record frequency estimates for the k-mer spectrum [<xref ref-type="bibr" rid="CR23">23</xref>
, <xref ref-type="bibr" rid="CR26">26</xref>
]. The count-min sketch counters are used as a proxy for the number of bins in the underlying k-mer spectrum. The relative accuracy of the count-min sketch is within a factor of epsilon, with probability delta. The default values of epsilon and delta are 0.0001 and 0.9, respectively, resulting in count-min sketch dimensions of four hashtables, each with 20,000 slots. Using these defaults, the maximum resident set size of the HULK sketching process on one CPU is an average of 1 .5Mb.</p>
<p id="Par29">Once an interval is reached, the counting processes each send their k-mer spectrum data in a randomised order to the single histosketching process; this process follows the incremental histosketch update process described above (Fig. <xref rid="Fig1" ref-type="fig">1</xref>
: sketching).</p>
</sec>
<sec id="Sec9"><title>Distance estimation</title>
<p id="Par30">HULK includes two distance subcommands, ‘distance’ and ‘smash’. Running ‘hulk distance’ will run a pairwise comparison of two histosketches and output the Jaccard, weighted Jaccard, Bray Curtis or Euclidean metrics. Running `hulk smash` will perform a pairwise comparison of two or more histosketches and output a matrix of Jaccard or weighted Jaccard similarities:</p>
<p id="Par31"><disp-formula id="Equb"><alternatives><tex-math id="M7">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$$ \mathrm{hulk}\ \mathrm{smash}--\mathrm{wjsMatrix}-\mathrm{d}./\mathrm{dir}-\mathrm{with}-\mathrm{sketches} $$\end{document}</tex-math>
<mml:math id="M8" display="block"><mml:mtext>hulk smash</mml:mtext>
<mml:mo>−</mml:mo>
<mml:mo>−</mml:mo>
<mml:mtext>wjsMatrix</mml:mtext>
<mml:mo>−</mml:mo>
<mml:mi mathvariant="normal">d</mml:mi>
<mml:mo>.</mml:mo>
<mml:mo>/</mml:mo>
<mml:mi>dir</mml:mi>
<mml:mo>−</mml:mo>
<mml:mtext>with</mml:mtext>
<mml:mo>−</mml:mo>
<mml:mtext>sketches</mml:mtext>
</mml:math>
<graphic xlink:href="40168_2019_653_Article_Equb.gif" position="anchor"></graphic>
</alternatives>
</disp-formula>
</p>
<p id="Par32">The calculation of weighted Jaccard distance utilises the histosketch bin and corresponding hash values; Eq. <xref rid="Equ3" ref-type="">3</xref>
shows the calculation of the weighted Jaccard distance for two histosketches, <italic>S</italic>
and <italic>T</italic>
.</p>
<p id="Par33"><disp-formula id="Equ3"><label>3</label>
<alternatives><tex-math id="M9">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$$ \mathrm{weightedJaccardDistance}\left(S,T\right)=1-\frac{\cap {\sum}_k\min \left({S}_k,{T}_k\right)}{\cup {\sum}_k\max \left({S}_k,{T}_k\right)} $$\end{document}</tex-math>
<mml:math id="M10" display="block"><mml:mtext>weightedJaccardDistance</mml:mtext>
<mml:mfenced close=")" open="(" separators=","><mml:mi>S</mml:mi>
<mml:mi>T</mml:mi>
</mml:mfenced>
<mml:mo>=</mml:mo>
<mml:mn>1</mml:mn>
<mml:mo>−</mml:mo>
<mml:mfrac><mml:mrow><mml:mo>∩</mml:mo>
<mml:msub><mml:mo>∑</mml:mo>
<mml:mi>k</mml:mi>
</mml:msub>
<mml:mo>min</mml:mo>
<mml:mfenced close=")" open="(" separators=","><mml:msub><mml:mi>S</mml:mi>
<mml:mi>k</mml:mi>
</mml:msub>
<mml:msub><mml:mi>T</mml:mi>
<mml:mi>k</mml:mi>
</mml:msub>
</mml:mfenced>
</mml:mrow>
<mml:mrow><mml:mo>∪</mml:mo>
<mml:msub><mml:mo>∑</mml:mo>
<mml:mi>k</mml:mi>
</mml:msub>
<mml:mo>max</mml:mo>
<mml:mfenced close=")" open="(" separators=","><mml:msub><mml:mi>S</mml:mi>
<mml:mi>k</mml:mi>
</mml:msub>
<mml:msub><mml:mi>T</mml:mi>
<mml:mi>k</mml:mi>
</mml:msub>
</mml:mfenced>
</mml:mrow>
</mml:mfrac>
</mml:math>
<graphic xlink:href="40168_2019_653_Article_Equ3.gif" position="anchor"></graphic>
</alternatives>
</disp-formula>
</p>
</sec>
<sec id="Sec10"><title>Indexing</title>
<p id="Par34">HULK utilises the LSH forest self-tuning indexing scheme as employed in our previous work [<xref ref-type="bibr" rid="CR17">17</xref>
]. Briefly, this scheme will take a query and return a subset of nearest-neighbour candidates, based on the number of hash collisions [<xref ref-type="bibr" rid="CR30">30</xref>
]. The two parameters to tune this index are the number of hash functions to encode an item (K), and the number of hash tables to split an item across (L). To tune index prior to adding items, multiple combinations of <italic>K</italic>
and <italic>L</italic>
are evaluated by false positive/negative rate at the given Jaccard similarity threshold. To add a histosketch to the index, we use only the sketch <italic>S</italic>
(i.e. not the hash values <italic>A</italic>
, see the “<xref rid="Sec5" ref-type="sec">Histosketch creation</xref>
” section); the sketch is split into <italic>L</italic>
equally sized chunks of <italic>K</italic>
hashes. The chunks are hashed to a binary string (little-endian ordering) and stored in the corresponding hash table. Prior to searching the index, the hash tables are transferred to a set of arrays and sorted.</p>
<p id="Par35">The HULK index operations are performed using the ‘index’ subcommand. Three modes are available: create, add and search. To create an index, the LSH forest index is initialised using a Jaccard similarity and error rate thresholds, and then each histosketch is split into the appropriate number of chunks and added as described in the above paragraph. The index is written to disk in the unsorted form.</p>
<p id="Par36"><disp-formula id="Equc"><alternatives><tex-math id="M11">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$$ \mathrm{hulk}\ \mathrm{index}-\mathrm{r}\ \mathrm{create}-\mathrm{n}\ \mathrm{a}.\mathrm{index}-\mathrm{j}\ 0.90-\mathrm{d}./\mathrm{ref}-\mathrm{sketches}--\mathrm{r}\mathrm{ecursive} $$\end{document}</tex-math>
<mml:math id="M12" display="block"><mml:mtext>hulk index</mml:mtext>
<mml:mo>−</mml:mo>
<mml:mi mathvariant="normal">r</mml:mi>
<mml:mspace width="0.25em"></mml:mspace>
<mml:mtext>create</mml:mtext>
<mml:mo>−</mml:mo>
<mml:mi mathvariant="normal">n</mml:mi>
<mml:mspace width="0.25em"></mml:mspace>
<mml:mi mathvariant="normal">a</mml:mi>
<mml:mo>.</mml:mo>
<mml:mtext>index</mml:mtext>
<mml:mo>−</mml:mo>
<mml:mi mathvariant="normal">j</mml:mi>
<mml:mspace width="0.25em"></mml:mspace>
<mml:mn>0.90</mml:mn>
<mml:mo>−</mml:mo>
<mml:mi mathvariant="normal">d</mml:mi>
<mml:mo>.</mml:mo>
<mml:mo>/</mml:mo>
<mml:mi>ref</mml:mi>
<mml:mo>−</mml:mo>
<mml:mtext>sketches</mml:mtext>
<mml:mo>−</mml:mo>
<mml:mo>−</mml:mo>
<mml:mtext>recursive</mml:mtext>
</mml:math>
<graphic xlink:href="40168_2019_653_Article_Equc.gif" position="anchor"></graphic>
</alternatives>
</disp-formula>
</p>
<p id="Par37">To add a histosketch to an existing index, the index is loaded and the histosketch is added using the existing index parameters. To search the index, the index is first loaded and the hash tables are transferred to a set of arrays and sorted. The query set of histosketches are then queried in series, and the similar histosketches are returned (by label) that are within the Jaccard similarity threshold that was set during indexing.</p>
<p id="Par38"><disp-formula id="Equd"><alternatives><tex-math id="M13">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$$ \mathrm{hulk}\ \mathrm{index}-\mathrm{r}\ \mathrm{search}-\mathrm{n}\ \mathrm{a}.\mathrm{index}-\mathrm{j}\ 0.90-\mathrm{d}./\mathrm{query}-\mathrm{sketches}--\mathrm{r}\mathrm{ecursive} $$\end{document}</tex-math>
<mml:math id="M14" display="block"><mml:mtext>hulk index</mml:mtext>
<mml:mo>−</mml:mo>
<mml:mi mathvariant="normal">r</mml:mi>
<mml:mspace width="0.25em"></mml:mspace>
<mml:mtext>search</mml:mtext>
<mml:mo>−</mml:mo>
<mml:mi mathvariant="normal">n</mml:mi>
<mml:mspace width="0.25em"></mml:mspace>
<mml:mi mathvariant="normal">a</mml:mi>
<mml:mo>.</mml:mo>
<mml:mtext>index</mml:mtext>
<mml:mo>−</mml:mo>
<mml:mi mathvariant="normal">j</mml:mi>
<mml:mspace width="0.25em"></mml:mspace>
<mml:mn>0.90</mml:mn>
<mml:mo>−</mml:mo>
<mml:mi mathvariant="normal">d</mml:mi>
<mml:mo>.</mml:mo>
<mml:mo>/</mml:mo>
<mml:mtext>query</mml:mtext>
<mml:mo>−</mml:mo>
<mml:mtext>sketches</mml:mtext>
<mml:mo>−</mml:mo>
<mml:mo>−</mml:mo>
<mml:mtext>recursive</mml:mtext>
</mml:math>
<graphic xlink:href="40168_2019_653_Article_Equd.gif" position="anchor"></graphic>
</alternatives>
</disp-formula>
</p>
</sec>
<sec id="Sec11"><title>Random forest classifier</title>
<p id="Par39">We implemented a random forest classifier (RFC) as an example ML classifier to showcase the applicability of our histosketches as features for predicting microbiome sample labels. Our implementation (BANNER) is written in Python (version 3.6) and is distributed with HULK, as well as through Bioconda and Pypi. Source code is available at <ext-link ext-link-type="uri" xlink:href="https://github.com/will-rowe/banner">https://github.com/will-rowe/banner</ext-link>
. It uses the SciKit Learn (version 0.19.2) implementation of the RFC [<xref ref-type="bibr" rid="CR31">31</xref>
]. Again, we use only the sketch values <italic>S</italic>
and discard the hash values <italic>A</italic>
. BANNER trains on 80% of the available data using bootstrapping and 1000 estimators; testing then uses the remaining 20% of the available data and does this with tenfold cross-validation. Once trained, the RFC model is serialised. To classify histosketches with BANNER, the RFC model is first loaded and un-serialised, before collecting histosketches from STDIN, allowing the output of `hulk sketch` to be piped so that histosketches can be classified as they are generated:</p>
<p id="Par40"><disp-formula id="Eque"><alternatives><tex-math id="M15">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$$ \mathrm{hulk}\ \mathrm{sketch}-\mathrm{f}\ \mathrm{sample}.\mathrm{fastq}--\mathrm{stream}-\mathrm{p}\ 8\mid \mathrm{banner}\ \mathrm{predict}-\mathrm{m}\ \mathrm{banner}.\mathrm{rfc} $$\end{document}</tex-math>
<mml:math id="M16" display="block"><mml:mtext>hulk sketch</mml:mtext>
<mml:mo>−</mml:mo>
<mml:mi mathvariant="normal">f</mml:mi>
<mml:mspace width="0.25em"></mml:mspace>
<mml:mtext>sample</mml:mtext>
<mml:mo>.</mml:mo>
<mml:mtext>fastq</mml:mtext>
<mml:mo>−</mml:mo>
<mml:mo>−</mml:mo>
<mml:mtext>stream</mml:mtext>
<mml:mo>−</mml:mo>
<mml:mi mathvariant="normal">p</mml:mi>
<mml:mspace width="0.25em"></mml:mspace>
<mml:mn>8</mml:mn>
<mml:mspace width="0.25em"></mml:mspace>
<mml:mo>∣</mml:mo>
<mml:mspace width="0.25em"></mml:mspace>
<mml:mtext>banner predict</mml:mtext>
<mml:mo>−</mml:mo>
<mml:mi mathvariant="normal">m</mml:mi>
<mml:mspace width="0.25em"></mml:mspace>
<mml:mtext>banner</mml:mtext>
<mml:mo>.</mml:mo>
<mml:mi>rfc</mml:mi>
</mml:math>
<graphic xlink:href="40168_2019_653_Article_Eque.gif" position="anchor"></graphic>
</alternatives>
</disp-formula>
</p>
<p id="Par41">The predict subcommand will only terminate once it makes a prediction above a set probability threshold or the sketching processes finishes.</p>
</sec>
</sec>
<sec id="Sec12"><title>Evaluating performance</title>
<p id="Par42">The full commands and code to evaluate the performance of our implementation can be found in the HULK repository (<ext-link ext-link-type="uri" xlink:href="https://github.com/will-rowe/hulk/tree/master/paper">https://github.com/will-rowe/hulk/tree/master/paper</ext-link>
). HULK version 0.0.2 was used in all experiments (release 0.0.2, commit 97ba8ac).</p>
<p id="Par43">For running the clustering and indexing experiments, the simulated short reads from the Critical Assessment of Metagenome Interpretation (CAMI) project (dataset to benchmark new programs against highly complex and realistic metagenomic datasets) were downloaded in FASTQ format [<xref ref-type="bibr" rid="CR32">32</xref>
]. For each complete read set, HULK sketches (k-mer size = 21, histosketch size = 512), sourmash (version 2.0.0a11) sketches (k-mer size = 21, sketch size = 512, track abundance = true) and Simka (version 1.4.0) k-mer spectra (k-mer size = 21) were created and pairwise Jaccard distances were loaded into Python (version 3.6.5) using Pandas (version 0.23.4) [<xref ref-type="bibr" rid="CR33">33</xref>
] and clustered using Seaborn (version 0.9.0) (clustering method = complete). For running HULK and Simka, both were restricted to 12 CPUs per FASTQ file and run using LSF on a high performance computing cluster (Atos Bull Sequana, Intel Skylake nodes).</p>
<p id="Par44">As an additional clustering experiment, we used a recently published dog microbiome dataset to detect dietary intervention using histosketches on varying levels of sequencing data (ENA: PRJEB20308) [<xref ref-type="bibr" rid="CR34">34</xref>
]. This study reported a significant shift in the taxonomic composition of dog microbiomes when diets were changed from a baseline diet. The full dataset contains 1.9 terabasepairs of sequencing data, of which we sampled 0.005%, 0.05% and 0.5% of each microbiome. We histosketched these samples (k-mer size = 21, histosketch size = 512) and clustered them as above.</p>
<p id="Par45">For performing the RFC analysis, an RFC model was constructed as described in the “<xref rid="Sec10" ref-type="sec">Indexing</xref>
” section, using a clinically relevant dataset: gut microbiome profiles from a cohort of healthy preterm from a single hospital. This is part of a wider neonate clinical study that is longitudinally profiling their gut microbiome and correlating their findings to health outcomes and antibiotic prescription. Faecal samples from preterm infants were collected and their bacterial DNA extracted following the protocols described by Alcon-Giner et al. [<xref ref-type="bibr" rid="CR35">35</xref>
]. Shotgun metagenomic libraries were prepared from 500 ng of genomic DNA which was sheared into fragments of ~ 450 bp. The sheared DNA was purified and concentrated using an SPRI-clean-up kit. Library construction entailed an end repair, A-tailing and adapter ligation steps. Following adapter ligation, samples were amplified and indexed by PCR using established Illumina paired-end protocols. A portion of each library was used to create an equimolar pool, and pooled libraries were subjected to 125 bp paired-end sequencing on a HiSeq 2500 V4. The cohort was labelled according to whether the infants were receiving prophylactic antibiotic treatment or no antibiotics. The histosketches from 108 FASTQ files (BioProject: PRJEB28428) were split into training (80%) and testing (20%) groups. When using the RFC model to classify the incremental sketch updates of blinded samples, HULK was run using sketching intervals of 10,000, 100,000 and 1,000,000 reads using a 4 core laptop (k-mer size = 7, histosketch size = 42, concept drift decay ratio = 0.02).</p>
</sec>
</sec>
<sec id="Sec13"><title>Results</title>
<p id="Par46">The results presented here evaluate our implementation of histosketching for rapid microbiome comparisons, in terms of both the accuracy of the tool and its potential applications. All analyses can be re-run using the analysis workbooks (<ext-link ext-link-type="uri" xlink:href="https://github.com/will-rowe/hulk/tree/master/paper/analysis-notebooks">https://github.com/will-rowe/hulk/tree/master/paper/analysis-notebooks</ext-link>
).</p>
<sec id="Sec14"><title>Clustering microbiome datasets</title>
<p id="Par47">We begin by assessing the speed and ability of HULK to cluster metagenomes based on pairwise similarities, and compare to the performance of two other popular methods. The CAMI metagenome sequence data for 48 microbiome samples were sketched by HULK in 1 min 30 s and by sourmash in 25 min 17 s, and the full k-mer spectra were computed by Simka in 24 min and 1 s. The combination of sketching and a parallel implementation thus makes HULK significantly faster than the other methods tried. Hierarchical clustering identified five distinct groups using both the HULK histosketches (Fig. <xref rid="Fig2" ref-type="fig">2</xref>
a) and the full k-mer spectrum of Simka (Fig. <xref rid="Fig2" ref-type="fig">2</xref>
c); these groups corresponded to the five body sites of the CAMI project (denoted by the coloured bars on the dendrograms). The hierarchical clustering of the sourmash minhash sketches resulted in six groups (Fig. <xref rid="Fig2" ref-type="fig">2</xref>
b). Using the HULK sketches, two samples failed to cluster by body site (skin and airways), whereas three samples failed to cluster for the Simka full k-mer spectra (skin and airways) and 8 samples failed to cluster correctly for the sourmash sketches (skin, airways and oral).<fig id="Fig2"><label>Fig. 2</label>
<caption><p>Hierarchical clustering of CAMI short read microbiome samples [<xref ref-type="bibr" rid="CR32">32</xref>
]. Heatmaps show the pairwise Jaccard similarity between microbiome samples (ranging from 0% (blue) to 100% (red)); colormap ranges are computed using robust quantiles and dendrogram clades are coloured by body site. <bold>a</bold>
HULK histosketches (k-mer size = 21, histosketch size = 512) for 48 microbiome samples were sketched in 1 min 30 s (12 cores per histosketch). <bold>b</bold>
sourmash MinHash sketches (k-mer size = 21, sketch size = 512, track abundance = true) for 48 samples were sketched in 25 min 17 s. <bold>c</bold>
Simka k-mer spectra (k-mer size = 21) for 48 microbiome samples were computed in 24 min 1 s (12 cores per spectrum)</p>
</caption>
<graphic xlink:href="40168_2019_653_Fig2_HTML" id="MO3"></graphic>
</fig>
</p>
<p id="Par48">To show the ability of our method to cluster incomplete data streams in a biological meaningful way, we performed incremental histosketch updating on data streams from a collection of dog microbiome samples. As the data was downloading, we histosketched the data stream (using fastq-dump to stream the download); approximately 0.005%, 0.05% and 0.5% of the reads from each sample (129 samples total) were processed and then clustered based on pairwise Jaccard similarity (Fig. <xref rid="Fig3" ref-type="fig">3</xref>
). At all intervals, we found a clear separation of histosketches between microbiome samples from dogs receiving the baseline diet and those receiving an altered diet (high/low protein). This is in agreement with the findings of the original study, where they reported a significant shift in the taxonomic composition of dog microbiomes when diets were changed [<xref ref-type="bibr" rid="CR34">34</xref>
]. The total microbiome data for the original study was stored in 3096 runs across 129 samples, amounting to 1.9 terabasepairs. Complete download of this dataset from the ENA took over 7 days using fastq-dump with 20 parallel downloads. Sketching the initial 0.005% of the data stream took an average of 4 s per sequencing run (approximately 100 s per sample).<fig id="Fig3"><label>Fig. 3</label>
<caption><p>Hierarchical clustering of dog microbiome samples [<xref ref-type="bibr" rid="CR34">34</xref>
]. <bold>a</bold>
, <bold>b</bold>
and <bold>c</bold>
correspond to clustered histosketches from 0.005%, 0.05% and 0.5% of sample reads, respectively. Heatmaps show the pairwise Jaccard similarity between microbiome samples (ranging from 0% (blue) to 100% (red)); colormap ranges are computed using robust quantiles and dendrogram clades are coloured by diet. The majority of microbiome samples from the dogs on the baseline diet clustered together (green); however, the samples taken after these dogs were put on to an altered diet (pink/blue) and did not show any distinct clustering pattern</p>
</caption>
<graphic xlink:href="40168_2019_653_Fig3_HTML" id="MO4"></graphic>
</fig>
</p>
</sec>
<sec id="Sec15"><title>Indexing microbiome collections</title>
<p id="Par49">We next test the LSH forest self-tuning indexing scheme as applied to HULK histosketches. The histosketches from the CAMI metagenome sequence data were labelled by body site before one sample was randomly removed from each group and used as a search query. The remaining sketches were indexed using HULK in 0.039 s (with a Jaccard similarity threshold of 0.90). Each query histosketch returned a subset of CAMI samples, at least one of which was from the same body site (Fig. <xref rid="Fig4" ref-type="fig">4</xref>
). The oral query returned only oral samples; the gastrointestinal (GI) tract, airways and skin queries returned predominantly samples from their own respective body sites, whilst the urogenital (UG) tract returned one sample from the same body site, plus another from airways. When overlaid on principal components 1 and 2 of a PCA analysis, the search queries are grouped nearest their respective LSH forest search results (Fig. <xref rid="Fig4" ref-type="fig">4</xref>
).<fig id="Fig4"><label>Fig. 4</label>
<caption><p>Principal component analysis of histosketches from CAMI short read microbiomes, with the 48 samples coloured by body site [<xref ref-type="bibr" rid="CR32">32</xref>
]. Circular data points indicate the histosketches used to build the LSH forest index and stars data points indicate histoketches used as search queries. Red rings enclose the returned LSH Forest search results for each search query (Jaccard similarity threshold > 90%)</p>
</caption>
<graphic xlink:href="40168_2019_653_Fig4_HTML" id="MO5"></graphic>
</fig>
</p>
</sec>
<sec id="Sec16"><title>Classifying microbiomes using machine learning</title>
<p id="Par50">Finally, we wanted to determine how the above approaches could be used to profile clinically relevant datasets, providing key data that could be used in a healthcare setting. Thus, we trained a random forest classifier using a microbiome collection that included gut microbiome profiles from a cohort of healthy preterm neonates from the St Mary’s Hospital, NICU, London, and labelled the samples according to whether the infants were receiving prophylactic antibiotic treatment or no antibiotics. The accuracy on the test set during RFC construction was 0.97, with an F1 score of 0.96. When histosketching entire FASTQ files from the blinded microbiome samples from the cohort, histosketches were successfully classified using the previously trained RFC as being from an antibiotic treated neonate (classification probability = 0.99, average runtime = 28.38 s) (Table <xref rid="Tab2" ref-type="table">2</xref>
). Additionally, when streaming reads and performing incremental histosketch updates, classifications could be made using the incrementally updated histosketches in 1.91 s (sampling interval = 10,000 reads, classification probability = 0.82) and go on to achieve classifications with probability ≥ 0.90 after two histosketch updates (average runtime = 2.09 s) (Table <xref rid="Tab2" ref-type="table">2</xref>
). Once classified at a probability ≥ 0.90, the data stream for a sample was terminated and a new sample data stream was then histosketched.<table-wrap id="Tab2"><label>Table 2</label>
<caption><p>Average random forest classification runtimes for predicting antibiotic vs. no-antibiotic treated neonatal microbiomes using read sampling intervals and concept drift (probability threshold = 0.9, <italic>k</italic>
= 7, <italic>s</italic>
= 42, decay ratio = 0.02, <italic>p</italic>
= 8)</p>
</caption>
<table frame="hsides" rules="groups"><thead><tr><th>Sampling interval (no. reads)</th>
<th>Runtime to reach initial classification (seconds)</th>
<th>Initial classification probability</th>
<th>Runtime to reach ≥ 0.9 classification probability (seconds)</th>
<th>Sampling intervals to reach ≥ 0.9 classification probability</th>
</tr>
</thead>
<tbody><tr><td>No interval</td>
<td>28.38</td>
<td>0.99</td>
<td>28.38</td>
<td>na</td>
</tr>
<tr><td>1,000,000</td>
<td>9.16</td>
<td>0.96</td>
<td>9.16</td>
<td>1</td>
</tr>
<tr><td>100,000</td>
<td>2.08</td>
<td>0.87</td>
<td>2.09</td>
<td>2</td>
</tr>
<tr><td>10,000</td>
<td>1.91</td>
<td>0.82</td>
<td>2.17</td>
<td>4</td>
</tr>
</tbody>
</table>
<table-wrap-foot><p><italic>na</italic>
not applicable</p>
</table-wrap-foot>
</table-wrap>
</p>
</sec>
</sec>
<sec id="Sec17"><title>Discussion</title>
<p id="Par51">In this paper, we have presented a new method, as well as several practical examples, for rapid microbiome analytics using streaming histogram sketching. This work has been in direct response to the call for improved microbiome analytics in this era of big data, massive microbiome sequencing initiatives and the realistic prospect of clinical metagenomics [<xref ref-type="bibr" rid="CR4">4</xref>
, <xref ref-type="bibr" rid="CR7">7</xref>
]. We feel that our microbiome sketching method and the applications shown here go toward addressing this challenge.</p>
<p id="Par52">As outlined in the introduction, the dimensionality reduction methods that have only recently been applied to genomics have been a great advance toward the goal of rapid microbiome analytics, facilitating fast similarity queries such as identifying genomes or genes within metagenome samples [<xref ref-type="bibr" rid="CR16">16</xref>
, <xref ref-type="bibr" rid="CR17">17</xref>
]. Our dimensionality reduction method for the comparison, indexing and classification of microbiomes offers a novel and complementary method to these existing ones. In particular, it addresses the main limitations of traditional MinHash for certain microbiome analyses. These being: (1) histogram sketching is not impacted by mismatched set size [<xref ref-type="bibr" rid="CR19">19</xref>
] and (2) histogram sketching accounts for weighted sets (e.g. k-mer frequency).</p>
<p id="Par53">Whilst our method is designed for microbiome comparison studies, it should be noted that it is based upon the assumption that the microbiomes being compared have shared membership, i.e. differences between samples will primarily be in taxa abundance, rather than membership. Consequently, our method (as with other k-mer spectra methods) will perform best with temporal and spatial microbiome samples. Where studies have microbiome samples that do not share substantial levels of similarity in their base constituents (e.g. samples from different environments), other sketching methods would be better suited for microbiome analytics. On a similar note, we want to also state that HULK was not designed for bacterial isolate comparisons/microbiome membership queries (due to the infrequent use of k-mer spectrum comparisons in this area), and direct the reader to other tools that excel in this area (such as microbiome screening offered by Mash/sourmash etc.).</p>
<p id="Par54">In terms of the advantages of HULK over other de novo analysis methods (e.g. k-mer spectra dissimilarity analysis), we have shown here that the computation of histogram sketches from complete metagenomic datasets is 16 times faster than the computation of the full k-mer spectra and 17 times faster than the computation of the MinHash sketch (see the “<xref rid="Sec14" ref-type="sec">Clustering microbiome datasets</xref>
” section and Fig. <xref rid="Fig2" ref-type="fig">2</xref>
). In terms of performing sketching faster than sourmash’s compute function, we should stress that the better performance seen by HULK is due to the ability to parallelise the histosketching process (both tools run in a similar time on a single core). All tools produced a fairly accurate clustering of the microbiome samples, according to the body site from which the microbiomes were designed to originate, with HULK actually producing the most accurate clustering in this sense. We suggest that the incorporation of k-mer frequency information into the sketch generation may account for the better clustering performance of HULK compared to that of sourmash, which differs by using k-mer abundance for weighting the distance calculations and not the sketch generation. As well as faster analysis times, histogram sketching has a much smaller footprint as the entire k-mer spectrum does not need to be kept in memory or written to disk, and the resulting sketches are much smaller in size than the full spectrum. As with other sketching methods, HULK also does not require re-computation of previously sketched samples in order to make new comparisons (provided new samples are sketched using the same parameters).</p>
<p id="Par55">In addition, we showed that histosketching microbiome samples can work on incomplete data streams and allow samples to be clustered by the underlying microbiome composition when using just a small proportion of the total reads (see the “<xref rid="Sec14" ref-type="sec">Clustering microbiome datasets</xref>
” section and Fig. <xref rid="Fig3" ref-type="fig">3</xref>
). Our results suggest that only a small proportion of the total data stream needs to be sampled in order to cluster the samples according to a particular treatment using histosketch similarity. Although we managed to identify the time point when the diet was changed from baseline to an altered diet, we were not able to differentiate between the two altered diets using our sketches from the initial data stream. This may be due to insufficient sampling of the data stream; however, the original study did not report being able to differentiate between the two altered diets either (see Fig. <xref rid="Fig2" ref-type="fig">2</xref>
c, Coelho et al. [<xref ref-type="bibr" rid="CR34">34</xref>
]).</p>
<p id="Par56">In the “<xref rid="Sec15" ref-type="sec">Indexing microbiome collections</xref>
” and “<xref rid="Sec16" ref-type="sec">Classifying microbiomes using machine learning</xref>
” sections, we demonstrated that microbiome histosketches can be efficiently indexed and also used as features in ML classification, which are both typically hard to do using the full k-mer spectra due to their scale and sparsity [<xref ref-type="bibr" rid="CR7">7</xref>
]. In terms of the LSH forest index for microbiome sample retrieval, our results showed that a histosketch from a given body site would predominantly return microbiome samples from the same body site (Fig. <xref rid="Fig4" ref-type="fig">4</xref>
). Only the oral histosketch query returned solely oral samples, which is likely due to the high similarity observed between these datasets (Fig. <xref rid="Fig2" ref-type="fig">2</xref>
). On the whole, these results indicate that histosketches of k-mer spectra can offer an efficient and fast way to index and query collections of microbiome data.</p>
<p id="Par57">Our performance evaluation of HULK using an RFC illustrates how incremental sketching (as highlighted in Fig. <xref rid="Fig3" ref-type="fig">3</xref>
) can be combined with ML in order to classify a microbiome and stop processing a data stream (see the “<xref rid="Sec16" ref-type="sec">Classifying microbiomes using machine learning</xref>
” sections). The RFC experiment showed that histosketches can be generated using part of a data stream more quickly than those generated using the full dataset, at the expense of classification probability. Also, by varying the sampling interval (i.e. number of reads), different classification probabilities are obtained; a histosketch generated at a given sampling interval may need to receive several updates before it meets a probability threshold. As such, there is a balance between sampling interval and the resulting classification probability. Therefore, the use of sampling intervals may be useful for obtaining quick, approximate results, but for greater confidence in microbiome classifications, sampling interval may need to be increased at the expense of runtime.</p>
<p id="Par58">This demonstration of classifying partial data streams is a step forward in dealing with streaming genomics data; the combination of incremental histosketch updates with a ML classifier (and associated classification probabilities) allows for the possibility of terminating data streams in applications such as real-time sequencing [<xref ref-type="bibr" rid="CR14">14</xref>
]. Here, we used this approach to quickly evaluate longitudinal samples from a cohort, identifying whether there is a response to a specific treatment. In this case, we have used this sketching approach to differentiate between those preterm infants that had received antibiotics, versus those that did not. This is important clinically as antibiotic treatment in preterm infants and is associated with significant alterations in the gut microbiota, which may link to increase risk of development serious conditions such as necrotising enterocolitis or sepsis [<xref ref-type="bibr" rid="CR35">35</xref>
–<xref ref-type="bibr" rid="CR37">37</xref>
]. Thus, a rapid and discriminatory microbiome profiling method for this fragile and at-risk patient cohort, or indeed for other clinical microbiome samples, could prove useful for intervention or treatment options. Alternatively, it could be applied to real-time sequencing platforms and inform the sequencer when enough data has been produced. These examples illustrate how this method could be used in the coming era of clinical metagenomics [<xref ref-type="bibr" rid="CR4">4</xref>
]. We are not restricted to using RFC and it would be very useful to evaluate other more sophisticated ML approaches that can utilise histosketches as feature vectors, as well as determining the impact of larger microbiome sample collections on classification accuracy. Indeed, in our recent study evaluating ML for microbiome classification, we showed that histosketches generated from the HMP metagenome collection (~ 670 samples) can be used with a variety of ML classifiers (RVMs, SVMs, RFCs, NBCs), with support-vector machines performing better than RFs in some cases [<xref ref-type="bibr" rid="CR38">38</xref>
]. As well as this, we could refine our ML models further by identifying the more significant elements of the histosketch in terms of their influence over the model training. This in turn could reveal more information relating to the underlying k-mer spectrum of a sample, which may be of use in downstream applications (e.g. feature extraction).</p>
<p id="Par59">Despite the promise shown by our use of histosketching and ML to evaluate and terminate a stream of sequencing data, it should be noted that we currently have no guarantees in our method that the input FASTQ data is randomly ordered, and this in turn could impact the robustness of the resulting sketches. For instance, known biases in the Illumina sequencing platform can result in tiles or edges of the flow cell that produce reads of lower quality, which will impact the histosketch. We have attempted to mitigate some of these sequence quality issues by the inclusion of an optional read quality trimming algorithm in the HULK sketch command.</p>
<p id="Par60">For future work into microbiome analytics, the histogram sketching method presented has potential for further refinement and improvements in order meet the big data challenges that microbiome research presents. Of these, we have already identified that further work into the use of histosketches in ML is definitely needed, particularly with the hope of improving classification accuracy and expanding out from the binary classification task we have shown here. In addition, we would like to further explore the idea of concept drift for gradually forgetting outdated histogram elements [<xref ref-type="bibr" rid="CR22">22</xref>
]. We included concept drift in our ML classification experiment using incrementally updated histosketches and observed increasing classification probability with histosketch updates (see the “<xref rid="Sec16" ref-type="sec">Classifying microbiomes using machine learning</xref>
” sections). We envisage that this could be useful to experiment further in terms of real-time sequencing applications. For instance, histosketching with concept drift may be useful in a clinical setting when, combined with environmental sensors, surface microbiomes could be continually monitored and any changes in microbiome composition reported to then be checked for presence of pathogens.</p>
<p id="Par61">Finally, we have shown that microbiome samples can be histosketched on a laptop with a few cores and a small, fixed amount of memory. In order to fully take advantage of this performance, histosketching needs to move beyond command line interfaces. To this end, we have begun working on a WebAssembly (WASM) port of HULK to enable client side sketching (WASM available Go Version 1.11) so that users can histosketch their own microbiome data and compare just the sketches against online databases, ensuring their microbiome data remains private but enabling quick and easy microbiome analytics.</p>
</sec>
<sec id="Sec18"><title>Conclusions</title>
<p id="Par62">Histosketching generates compact representations of microbiomes from data streams, facilitating sample indexing, similarity-search queries, clustering, and the application of machine learning methods to analyse microbiome samples in the context of the global microbiome corpus.</p>
</sec>
</body>
<back><ack><title>Acknowledgements</title>
<p>We are grateful to Iain Bethune at the Hartree Centre for his feedback and guidance.</p>
<sec id="FPar1"><title>Funding</title>
<p id="Par63">This work was supported in part by the STFC Hartree Centre’s Innovation Return on Research programme, funded by the Department for Business, Energy & Industrial Strategy. This work was funded via a Wellcome Trust Investigator Award to LJH (100/974/C/13/Z), and support of the BBSRC Norwich Research Park Bioscience Doctoral Training Grant (BB/M011216/1, supervisor LJH, student CAG), and Institute Strategic Programme grant for Gut Health and Food Safety, BB/J004529/1, and BBSRC Institute Strategic Programme Gut Microbes and Health BB/R012490/1 (LJH). Work at Imperial College was supported by a Programme Grant from the Winnicott Foundation (JSK).</p>
</sec>
<sec id="FPar2" sec-type="data-availability"><title>Availability of data and materials</title>
<p id="Par64">The source code for our implementation, as well as the code used to run the analyses and plot the manuscript Figures, can be found in the HULK (<ext-link ext-link-type="uri" xlink:href="https://github.com/will-rowe/hulk">github.com/will-rowe/hulk</ext-link>
) and BANNER (<ext-link ext-link-type="uri" xlink:href="https://github.com/will-rowe/hulk">github.com/will-rowe/banner</ext-link>
) repositories (DOIs: 10.5281/zenodo.1406952, 10.5281/zenodo.1406951). The neonatal microbiome data is available from the ENA under BioProject PRJEB28428.</p>
</sec>
</ack>
<notes notes-type="author-contribution"><title>Authors’ contributions</title>
<p>WPMR and APC conceived and executed the study. WPMR coded and tested the implementation. LJH and JSK led on the preterm clinical study; AS, KS and CAG processed and sequenced samples; and SC carried out metagenomics QC, processing and analysis. All authors wrote, read and approved the final manuscript.</p>
</notes>
<notes notes-type="COI-statement"><sec id="FPar3"><title>Ethics approval and consent to participate</title>
<p>The study comprised faecal samples from preterms residing at 2 different Neonatal Intensive Care Units: i) Queen Charlotte’s and Chelsea Hospital (London, England) and ii) St Mary’s Hospital (London, England). Faecal collection for Queen Charlotte’s and Chelsea Hospital and St Mary’s Hospital was approved by West London Research Ethics Committee (REC) under the REC approval reference number 10/H0711/39. In all cases, doctors and nurses recruited infants after parents gave written consent.</p>
</sec>
<sec id="FPar4"><title>Competing interests</title>
<p>The authors declare that they have no competing interests.</p>
</sec>
<sec id="FPar5"><title>Publisher’s Note</title>
<p>Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.</p>
</sec>
</notes>
<ref-list id="Bib1"><title>References</title>
<ref id="CR1"><label>1.</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><collab>Human Microbiome Project Consortium</collab>
</person-group>
<article-title>Structure, function and diversity of the healthy human microbiome</article-title>
<source>Nature.</source>
<year>2012</year>
<volume>486</volume>
<fpage>207</fpage>
<lpage>214</lpage>
<pub-id pub-id-type="doi">10.1038/nature11234</pub-id>
<pub-id pub-id-type="pmid">22699609</pub-id>
</element-citation>
</ref>
<ref id="CR2"><label>2.</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Thompson</surname>
<given-names>LR</given-names>
</name>
<name><surname>Sanders</surname>
<given-names>JG</given-names>
</name>
<name><surname>McDonald</surname>
<given-names>D</given-names>
</name>
<name><surname>Amir</surname>
<given-names>A</given-names>
</name>
<name><surname>Ladau</surname>
<given-names>J</given-names>
</name>
<name><surname>Locey</surname>
<given-names>KJ</given-names>
</name>
<etal></etal>
</person-group>
<article-title>A communal catalogue reveals Earth’s multiscale microbial diversity</article-title>
<source>Nature.</source>
<year>2017</year>
<volume>551</volume>
<fpage>457</fpage>
<lpage>463</lpage>
<pub-id pub-id-type="doi">10.1038/551033a</pub-id>
<pub-id pub-id-type="pmid">29088705</pub-id>
</element-citation>
</ref>
<ref id="CR3"><label>3.</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Rusch</surname>
<given-names>DB</given-names>
</name>
<name><surname>Halpern</surname>
<given-names>AL</given-names>
</name>
<name><surname>Sutton</surname>
<given-names>G</given-names>
</name>
<name><surname>Heidelberg</surname>
<given-names>KB</given-names>
</name>
<name><surname>Williamson</surname>
<given-names>S</given-names>
</name>
<name><surname>Yooseph</surname>
<given-names>S</given-names>
</name>
<etal></etal>
</person-group>
<article-title>The Sorcerer II global ocean sampling expedition: Northwest Atlantic through eastern tropical Pacific</article-title>
<source>PLoS Biol</source>
<year>2007</year>
<volume>5</volume>
<fpage>e77</fpage>
<pub-id pub-id-type="doi">10.1371/journal.pbio.0050077</pub-id>
<pub-id pub-id-type="pmid">17355176</pub-id>
</element-citation>
</ref>
<ref id="CR4"><label>4.</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Mulcahy-O’Grady</surname>
<given-names>H</given-names>
</name>
<name><surname>Workentine</surname>
<given-names>ML</given-names>
</name>
</person-group>
<article-title>The challenge and potential of metagenomics in the clinic</article-title>
<source>Front Immunol</source>
<year>2016</year>
<volume>7</volume>
<fpage>29</fpage>
<pub-id pub-id-type="doi">10.3389/fimmu.2016.00029</pub-id>
<pub-id pub-id-type="pmid">26870044</pub-id>
</element-citation>
</ref>
<ref id="CR5"><label>5.</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Forbes</surname>
<given-names>JD</given-names>
</name>
<name><surname>Knox</surname>
<given-names>NC</given-names>
</name>
<name><surname>Peterson</surname>
<given-names>C-L</given-names>
</name>
<name><surname>Reimer</surname>
<given-names>AR</given-names>
</name>
</person-group>
<article-title>Highlighting clinical metagenomics for enhanced diagnostic decision-making: a step towards wider implementation</article-title>
<source>Comput Struct Biotechnol J</source>
<year>2018</year>
<volume>16</volume>
<fpage>108</fpage>
<lpage>120</lpage>
<pub-id pub-id-type="doi">10.1016/j.csbj.2018.02.006</pub-id>
<pub-id pub-id-type="pmid">30026887</pub-id>
</element-citation>
</ref>
<ref id="CR6"><label>6.</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Greninger</surname>
<given-names>AL</given-names>
</name>
<name><surname>Naccache</surname>
<given-names>SN</given-names>
</name>
<name><surname>Federman</surname>
<given-names>S</given-names>
</name>
<name><surname>Yu</surname>
<given-names>G</given-names>
</name>
<name><surname>Mbala</surname>
<given-names>P</given-names>
</name>
<name><surname>Bres</surname>
<given-names>V</given-names>
</name>
<etal></etal>
</person-group>
<article-title>Rapid metagenomic identification of viral pathogens in clinical samples by real-time nanopore sequencing analysis</article-title>
<source>Genome Med</source>
<year>2015</year>
<volume>7</volume>
<fpage>99</fpage>
<pub-id pub-id-type="doi">10.1186/s13073-015-0220-9</pub-id>
<pub-id pub-id-type="pmid">26416663</pub-id>
</element-citation>
</ref>
<ref id="CR7"><label>7.</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Kakkanatt</surname>
<given-names>C</given-names>
</name>
<name><surname>Benigno</surname>
<given-names>M</given-names>
</name>
<name><surname>Jackson</surname>
<given-names>VM</given-names>
</name>
<name><surname>Huang</surname>
<given-names>PL</given-names>
</name>
<name><surname>Ng</surname>
<given-names>K</given-names>
</name>
</person-group>
<article-title>Curating and integrating user-generated health data from multiple sources to support healthcare analytics</article-title>
<source>IBM J Res Dev</source>
<year>2018</year>
<volume>62</volume>
<issue>1</issue>
<fpage>2</fpage>
<lpage>1</lpage>
<pub-id pub-id-type="doi">10.1147/JRD.2017.2756742</pub-id>
</element-citation>
</ref>
<ref id="CR8"><label>8.</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Morgan</surname>
<given-names>XC</given-names>
</name>
<name><surname>Huttenhower</surname>
<given-names>C</given-names>
</name>
</person-group>
<article-title>Chapter 12: human microbiome analysis</article-title>
<source>PLoS Comput Biol</source>
<year>2012</year>
<volume>8</volume>
<fpage>e1002808</fpage>
<pub-id pub-id-type="doi">10.1371/journal.pcbi.1002808</pub-id>
<pub-id pub-id-type="pmid">23300406</pub-id>
</element-citation>
</ref>
<ref id="CR9"><label>9.</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Dubinkina</surname>
<given-names>VB</given-names>
</name>
<name><surname>Ischenko</surname>
<given-names>DS</given-names>
</name>
<name><surname>Ulyantsev</surname>
<given-names>VI</given-names>
</name>
<name><surname>Tyakht</surname>
<given-names>AV</given-names>
</name>
<name><surname>Alexeev</surname>
<given-names>DG</given-names>
</name>
</person-group>
<article-title>Assessment of k-mer spectrum applicability for metagenomic dissimilarity analysis</article-title>
<source>BMC Bioinformatics</source>
<year>2016</year>
<volume>17</volume>
<fpage>38</fpage>
<pub-id pub-id-type="doi">10.1186/s12859-015-0875-7</pub-id>
<pub-id pub-id-type="pmid">26774270</pub-id>
</element-citation>
</ref>
<ref id="CR10"><label>10.</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Benoit</surname>
<given-names>G</given-names>
</name>
<name><surname>Peterlongo</surname>
<given-names>P</given-names>
</name>
<name><surname>Mariadassou</surname>
<given-names>M</given-names>
</name>
<name><surname>Drezen</surname>
<given-names>E</given-names>
</name>
<name><surname>Schbath</surname>
<given-names>S</given-names>
</name>
<name><surname>Lavenier</surname>
<given-names>D</given-names>
</name>
<etal></etal>
</person-group>
<article-title>Multiple comparative metagenomics using multiset k-mer counting</article-title>
<source>PeerJ Comput Sci PeerJ Inc</source>
<year>2016</year>
<volume>2</volume>
<fpage>e94</fpage>
<pub-id pub-id-type="doi">10.7717/peerj-cs.94</pub-id>
</element-citation>
</ref>
<ref id="CR11"><label>11.</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Anvar</surname>
<given-names>SY</given-names>
</name>
<name><surname>Khachatryan</surname>
<given-names>L</given-names>
</name>
<name><surname>Vermaat</surname>
<given-names>M</given-names>
</name>
<name><surname>van Galen</surname>
<given-names>M</given-names>
</name>
<name><surname>Pulyakhina</surname>
<given-names>I</given-names>
</name>
<name><surname>Ariyurek</surname>
<given-names>Y</given-names>
</name>
<etal></etal>
</person-group>
<article-title>Determining the quality and complexity of next-generation sequencing data without a reference genome</article-title>
<source>Genome Biol</source>
<year>2014</year>
<volume>15</volume>
<fpage>555</fpage>
<pub-id pub-id-type="doi">10.1186/s13059-014-0555-3</pub-id>
<pub-id pub-id-type="pmid">25514851</pub-id>
</element-citation>
</ref>
<ref id="CR12"><label>12.</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Libbrecht</surname>
<given-names>MW</given-names>
</name>
<name><surname>Noble</surname>
<given-names>WS</given-names>
</name>
</person-group>
<article-title>Machine learning applications in genetics and genomics</article-title>
<source>Nat Rev Genet</source>
<year>2015</year>
<volume>16</volume>
<fpage>321</fpage>
<lpage>332</lpage>
<pub-id pub-id-type="doi">10.1038/nrg3920</pub-id>
<pub-id pub-id-type="pmid">25948244</pub-id>
</element-citation>
</ref>
<ref id="CR13"><label>13.</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Seth</surname>
<given-names>S</given-names>
</name>
<name><surname>Välimäki</surname>
<given-names>N</given-names>
</name>
<name><surname>Kaski</surname>
<given-names>S</given-names>
</name>
<name><surname>Honkela</surname>
<given-names>A</given-names>
</name>
</person-group>
<article-title>Exploration and retrieval of whole-metagenome sequencing samples</article-title>
<source>Bioinformatics.</source>
<year>2014</year>
<volume>30</volume>
<fpage>2471</fpage>
<lpage>2479</lpage>
<pub-id pub-id-type="doi">10.1093/bioinformatics/btu340</pub-id>
<pub-id pub-id-type="pmid">24845653</pub-id>
</element-citation>
</ref>
<ref id="CR14"><label>14.</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Ondov</surname>
<given-names>BD</given-names>
</name>
<name><surname>Treangen</surname>
<given-names>TJ</given-names>
</name>
<name><surname>Melsted</surname>
<given-names>P</given-names>
</name>
<name><surname>Mallonee</surname>
<given-names>AB</given-names>
</name>
<name><surname>Bergman</surname>
<given-names>NH</given-names>
</name>
<name><surname>Koren</surname>
<given-names>S</given-names>
</name>
<etal></etal>
</person-group>
<article-title>Mash: fast genome and metagenome distance estimation using MinHash</article-title>
<source>Genome Biol</source>
<year>2016</year>
<volume>17</volume>
<fpage>132</fpage>
<pub-id pub-id-type="doi">10.1186/s13059-016-0997-x</pub-id>
<pub-id pub-id-type="pmid">27323842</pub-id>
</element-citation>
</ref>
<ref id="CR15"><label>15.</label>
<mixed-citation publication-type="other">Luo Y, Yu YW, Zeng J, Berger B, Peng J. Metagenomic binning through low-density hashing. Bioinformatics. 2018. 10.1093/bioinformatics/bty611.</mixed-citation>
</ref>
<ref id="CR16"><label>16.</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Brown</surname>
<given-names>T</given-names>
</name>
<name><surname>Irber</surname>
<given-names>L</given-names>
</name>
</person-group>
<article-title>Sourmash: a library for MinHash sketching of DNA</article-title>
<source>JOSS.</source>
<year>2016</year>
<volume>1</volume>
<fpage>27</fpage>
<pub-id pub-id-type="doi">10.21105/joss.00027</pub-id>
</element-citation>
</ref>
<ref id="CR17"><label>17.</label>
<mixed-citation publication-type="other">Rowe WPM, Winn MD. Indexed variation graphs for efficient and accurate resistome profiling. Bioinformatics. 2018. 10.1093/bioinformatics/bty387.</mixed-citation>
</ref>
<ref id="CR18"><label>18.</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Bovee</surname>
<given-names>R</given-names>
</name>
<name><surname>Greenfield</surname>
<given-names>N</given-names>
</name>
</person-group>
<article-title>Finch: a tool adding dynamic abundance filtering to genomic MinHashing</article-title>
<source>JOSS.</source>
<year>2018</year>
<volume>3</volume>
<fpage>505</fpage>
<pub-id pub-id-type="doi">10.21105/joss.00505</pub-id>
</element-citation>
</ref>
<ref id="CR19"><label>19.</label>
<mixed-citation publication-type="other">Koslicki D, Zabeti H. Improving MinHash via the containment index with applications to metagenomic analysis. bioRxiv. 2017:184150 Available from: <ext-link ext-link-type="uri" xlink:href="https://www.biorxiv.org/content/early/2017/09/04/184150">https://www.biorxiv.org/content/early/2017/09/04/184150</ext-link>
. [cited 2018 Aug 23].</mixed-citation>
</ref>
<ref id="CR20"><label>20.</label>
<element-citation publication-type="book"><person-group person-group-type="author"><name><surname>Wu</surname>
<given-names>W</given-names>
</name>
<name><surname>Li</surname>
<given-names>B</given-names>
</name>
<name><surname>Chen</surname>
<given-names>L</given-names>
</name>
<name><surname>Zhang</surname>
<given-names>C</given-names>
</name>
</person-group>
<article-title>Consistent weighted sampling made more practical</article-title>
<source>Proceedings of the 26th international conference on world wide web. International world wide web conferences steering committee</source>
<year>2017</year>
<fpage>1035</fpage>
<lpage>1043</lpage>
</element-citation>
</ref>
<ref id="CR21"><label>21.</label>
<element-citation publication-type="book"><person-group person-group-type="author"><name><surname>Ioffe</surname>
<given-names>S</given-names>
</name>
</person-group>
<source>Improved consistent sampling, weighted Minhash and L1 sketching</source>
<year>2010</year>
<fpage>246</fpage>
<lpage>255</lpage>
</element-citation>
</ref>
<ref id="CR22"><label>22.</label>
<element-citation publication-type="book"><person-group person-group-type="author"><name><surname>Yang</surname>
<given-names>D</given-names>
</name>
<name><surname>Li</surname>
<given-names>B</given-names>
</name>
<name><surname>Rettig</surname>
<given-names>L</given-names>
</name>
<name><surname>Cudré-Mauroux</surname>
<given-names>P</given-names>
</name>
</person-group>
<source>HistoSketch: fast similarity-preserving sketching of streaming histograms with concept drift</source>
<year>2017</year>
<fpage>545</fpage>
<lpage>554</lpage>
</element-citation>
</ref>
<ref id="CR23"><label>23.</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Zhang</surname>
<given-names>Q</given-names>
</name>
<name><surname>Pell</surname>
<given-names>J</given-names>
</name>
<name><surname>Canino-Koning</surname>
<given-names>R</given-names>
</name>
<name><surname>Howe</surname>
<given-names>AC</given-names>
</name>
<name><surname>Brown</surname>
<given-names>CT</given-names>
</name>
</person-group>
<article-title>These are not the k-mers you are looking for: efficient online k-mer counting using a probabilistic data structure</article-title>
<source>PLoS One</source>
<year>2014</year>
<volume>9</volume>
<fpage>e101271</fpage>
<pub-id pub-id-type="doi">10.1371/journal.pone.0101271</pub-id>
<pub-id pub-id-type="pmid">25062443</pub-id>
</element-citation>
</ref>
<ref id="CR24"><label>24.</label>
<element-citation publication-type="book"><person-group person-group-type="author"><name><surname>Haveliwala</surname>
<given-names>T</given-names>
</name>
<name><surname>Gionis</surname>
<given-names>A</given-names>
</name>
<name><surname>Indyk</surname>
<given-names>P</given-names>
</name>
</person-group>
<source>Scalable techniques for clustering the web (extended abstract)</source>
<year>2000</year>
</element-citation>
</ref>
<ref id="CR25"><label>25.</label>
<mixed-citation publication-type="other">Manasse M, McSherry F, Talwar K. Consistent weighted sampling. Financ Times. 2010; Available from: <ext-link ext-link-type="uri" xlink:href="https://www.microsoft.com/en-us/research/wp-content/uploads/2010/06/ConsistentWeightedSampling2.pdf">https://www.microsoft.com/en-us/research/wp-content/uploads/2010/06/ConsistentWeightedSampling2.pdf</ext-link>
. [cited 23 Aug 2018].</mixed-citation>
</ref>
<ref id="CR26"><label>26.</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Cormode</surname>
<given-names>G</given-names>
</name>
<name><surname>Muthukrishnan</surname>
<given-names>S</given-names>
</name>
</person-group>
<article-title>An improved data stream summary: the count-min sketch and its applications</article-title>
<source>J Algorithm Comput Technol</source>
<year>2005</year>
<volume>55</volume>
<fpage>58</fpage>
<lpage>75</lpage>
<pub-id pub-id-type="doi">10.1016/j.jalgor.2003.12.001</pub-id>
</element-citation>
</ref>
<ref id="CR27"><label>27.</label>
<element-citation publication-type="book"><person-group person-group-type="author"><name><surname>Koychev</surname>
<given-names>I</given-names>
</name>
</person-group>
<article-title>Gradual forgetting for adaptation to concept drift</article-title>
<source>Proceedings of ECAI 2000 workshop current issues in spatio-temporal reasoning</source>
<year>2000</year>
</element-citation>
</ref>
<ref id="CR28"><label>28.</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Grüning</surname>
<given-names>B</given-names>
</name>
<name><surname>Dale</surname>
<given-names>R</given-names>
</name>
<name><surname>Sjödin</surname>
<given-names>A</given-names>
</name>
<name><surname>Chapman</surname>
<given-names>BA</given-names>
</name>
<name><surname>Rowe</surname>
<given-names>J</given-names>
</name>
<name><surname>Tomkins-Tinch</surname>
<given-names>CH</given-names>
</name>
<etal></etal>
</person-group>
<article-title>Bioconda: sustainable and comprehensive software distribution for the life sciences</article-title>
<source>Nat Methods</source>
<year>2018</year>
<volume>15</volume>
<fpage>475</fpage>
<lpage>476</lpage>
<pub-id pub-id-type="doi">10.1038/s41592-018-0046-7</pub-id>
<pub-id pub-id-type="pmid">29967506</pub-id>
</element-citation>
</ref>
<ref id="CR29"><label>29.</label>
<mixed-citation publication-type="other">Grüning B, Sallou O, Moreno P, da Veiga Leprevost F, Ménager H, Søndergaard D, et al. Recommendations for the packaging and containerizing of bioinformatics software. F1000Res. 2018:7 Available from: <ext-link ext-link-type="uri" xlink:href="https://f1000research.com/articles/7-742/v1/pdf">https://f1000research.com/articles/7-742/v1/pdf</ext-link>
. [cited 14 Aug 2018].</mixed-citation>
</ref>
<ref id="CR30"><label>30.</label>
<element-citation publication-type="book"><person-group person-group-type="author"><name><surname>Bawa</surname>
<given-names>M</given-names>
</name>
<name><surname>Condie</surname>
<given-names>T</given-names>
</name>
<name><surname>Ganesan</surname>
<given-names>P</given-names>
</name>
</person-group>
<article-title>LSH forest: self-tuning indexes for similarity search</article-title>
<source>Proceedings of the 14th international conference on world wide web</source>
<year>2005</year>
<publisher-loc>New York</publisher-loc>
<publisher-name>ACM</publisher-name>
<fpage>651</fpage>
<lpage>660</lpage>
</element-citation>
</ref>
<ref id="CR31"><label>31.</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Pedregosa</surname>
<given-names>F</given-names>
</name>
<name><surname>Varoquaux</surname>
<given-names>G</given-names>
</name>
<name><surname>Gramfort</surname>
<given-names>A</given-names>
</name>
<name><surname>Michel</surname>
<given-names>V</given-names>
</name>
<name><surname>Thirion</surname>
<given-names>B</given-names>
</name>
<name><surname>Grisel</surname>
<given-names>O</given-names>
</name>
<etal></etal>
</person-group>
<article-title>Scikit-learn: machine learning in Python</article-title>
<source>J Mach Learn Res</source>
<year>2011</year>
<volume>12</volume>
<fpage>2825</fpage>
<lpage>2830</lpage>
</element-citation>
</ref>
<ref id="CR32"><label>32.</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Sczyrba</surname>
<given-names>A</given-names>
</name>
<name><surname>Hofmann</surname>
<given-names>P</given-names>
</name>
<name><surname>Belmann</surname>
<given-names>P</given-names>
</name>
<name><surname>Koslicki</surname>
<given-names>D</given-names>
</name>
<name><surname>Janssen</surname>
<given-names>S</given-names>
</name>
<name><surname>Dröge</surname>
<given-names>J</given-names>
</name>
<etal></etal>
</person-group>
<article-title>Critical assessment of metagenome interpretation-a benchmark of metagenomics software</article-title>
<source>Nat Methods</source>
<year>2017</year>
<volume>14</volume>
<fpage>1063</fpage>
<lpage>1071</lpage>
<pub-id pub-id-type="doi">10.1038/nmeth.4458</pub-id>
<pub-id pub-id-type="pmid">28967888</pub-id>
</element-citation>
</ref>
<ref id="CR33"><label>33.</label>
<mixed-citation publication-type="other">Mc Kinney W. Pandas: a foundational Python library for data analysis and statistics. 2011. Available from: <ext-link ext-link-type="uri" xlink:href="https://www.dlr.de/sc/Portaldata/15/Resources/dokumente/pyhpc2011/submissions/pyhpc2011_submission_9.pdf">https://www.dlr.de/sc/Portaldata/15/Resources/dokumente/pyhpc2011/submissions/pyhpc2011_submission_9.pdf</ext-link>
</mixed-citation>
</ref>
<ref id="CR34"><label>34.</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Coelho</surname>
<given-names>LP</given-names>
</name>
<name><surname>Kultima</surname>
<given-names>JR</given-names>
</name>
<name><surname>Costea</surname>
<given-names>PI</given-names>
</name>
<name><surname>Fournier</surname>
<given-names>C</given-names>
</name>
<name><surname>Pan</surname>
<given-names>Y</given-names>
</name>
<name><surname>Czarnecki-Maulden</surname>
<given-names>G</given-names>
</name>
<etal></etal>
</person-group>
<article-title>Similarity of the dog and human gut microbiomes in gene content and response to diet</article-title>
<source>Microbiome.</source>
<year>2018</year>
<volume>6</volume>
<fpage>72</fpage>
<pub-id pub-id-type="doi">10.1186/s40168-018-0450-3</pub-id>
<pub-id pub-id-type="pmid">29669589</pub-id>
</element-citation>
</ref>
<ref id="CR35"><label>35.</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Alcon-Giner</surname>
<given-names>C</given-names>
</name>
<name><surname>Caim</surname>
<given-names>S</given-names>
</name>
<name><surname>Mitra</surname>
<given-names>S</given-names>
</name>
<name><surname>Ketskemety</surname>
<given-names>J</given-names>
</name>
<name><surname>Wegmann</surname>
<given-names>U</given-names>
</name>
<name><surname>Wain</surname>
<given-names>J</given-names>
</name>
<etal></etal>
</person-group>
<article-title>Optimisation of 16S rRNA gut microbiota profiling of extremely low birth weight infants</article-title>
<source>BMC Genomics</source>
<year>2017</year>
<volume>18</volume>
<fpage>841</fpage>
<pub-id pub-id-type="doi">10.1186/s12864-017-4229-x</pub-id>
<pub-id pub-id-type="pmid">29096601</pub-id>
</element-citation>
</ref>
<ref id="CR36"><label>36.</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Sim</surname>
<given-names>K</given-names>
</name>
<name><surname>Shaw</surname>
<given-names>AG</given-names>
</name>
<name><surname>Randell</surname>
<given-names>P</given-names>
</name>
<name><surname>Cox</surname>
<given-names>MJ</given-names>
</name>
<name><surname>McClure</surname>
<given-names>ZE</given-names>
</name>
<name><surname>Li</surname>
<given-names>M-S</given-names>
</name>
<etal></etal>
</person-group>
<article-title>Dysbiosis anticipating necrotizing enterocolitis in very premature infants</article-title>
<source>Clin Infect Dis</source>
<year>2015</year>
<volume>60</volume>
<fpage>389</fpage>
<lpage>397</lpage>
<pub-id pub-id-type="doi">10.1093/cid/ciu822</pub-id>
<pub-id pub-id-type="pmid">25344536</pub-id>
</element-citation>
</ref>
<ref id="CR37"><label>37.</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Shaw</surname>
<given-names>AG</given-names>
</name>
<name><surname>Sim</surname>
<given-names>K</given-names>
</name>
<name><surname>Randell</surname>
<given-names>P</given-names>
</name>
<name><surname>Cox</surname>
<given-names>MJ</given-names>
</name>
<name><surname>McClure</surname>
<given-names>ZE</given-names>
</name>
<name><surname>Li</surname>
<given-names>M-S</given-names>
</name>
<etal></etal>
</person-group>
<article-title>Late-onset bloodstream infection and perturbed maturation of the gastrointestinal microbiota in premature infants</article-title>
<source>PLoS One</source>
<year>2015</year>
<volume>10</volume>
<fpage>e0132923</fpage>
<pub-id pub-id-type="doi">10.1371/journal.pone.0132923</pub-id>
<pub-id pub-id-type="pmid">26167683</pub-id>
</element-citation>
</ref>
<ref id="CR38"><label>38.</label>
<element-citation publication-type="book"><person-group person-group-type="author"><name><surname>Carrieri</surname>
<given-names>AP</given-names>
</name>
<name><surname>Rowe</surname>
<given-names>WPM</given-names>
</name>
<name><surname>Winn</surname>
<given-names>MD</given-names>
</name>
<name><surname>Pyzer-Knapp</surname>
<given-names>EO</given-names>
</name>
</person-group>
<source>A fast machine learning workflow for rapid phenotype prediction from whole shotgun metagenomes. Innovative applications of artificial intelligence</source>
<year>2019</year>
</element-citation>
</ref>
</ref-list>
</back>
</pmc>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Sante/explor/MersV1/Data/Pmc/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000398 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Pmc/Corpus/biblio.hfd -nk 000398 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Sante |area= MersV1 |flux= Pmc |étape= Corpus |type= RBID |clé= PMC:6420756 |texte= Streaming histogram sketching for rapid microbiome analytics }}
Pour générer des pages wiki
HfdIndexSelect -h $EXPLOR_AREA/Data/Pmc/Corpus/RBID.i -Sk "pubmed:30878035" \ | HfdSelect -Kh $EXPLOR_AREA/Data/Pmc/Corpus/biblio.hfd \ | NlmPubMed2Wicri -a MersV1
![]() | This area was generated with Dilib version V0.6.33. | ![]() |