Links to Exploration step
Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Better quality score compression through sequence-based quality smoothing</title>
<author><name sortKey="Shibuya, Yoshihiro" sort="Shibuya, Yoshihiro" uniqKey="Shibuya Y" first="Yoshihiro" last="Shibuya">Yoshihiro Shibuya</name>
<affiliation><nlm:aff id="Aff1"><institution-wrap><institution-id institution-id-type="ISNI">0000 0004 1757 3470</institution-id>
<institution-id institution-id-type="GRID">grid.5608.b</institution-id>
<institution>Department of Information Engineering, University of Padova,</institution>
</institution-wrap>
via Gradenigo 6/A, Padova, Italy</nlm:aff>
</affiliation>
<affiliation><nlm:aff id="Aff2"><institution-wrap><institution-id institution-id-type="ISNI">0000 0000 9103 9111</institution-id>
<institution-id institution-id-type="GRID">grid.462940.d</institution-id>
<institution>Laboratoire d’Informatique Gaspard-Monge (LIGM), University Paris-Est Marne-la-Vallée,</institution>
</institution-wrap>
Bâtiment Copernic - 5, bd Descartes, Champs sur Marne, France</nlm:aff>
</affiliation>
</author>
<author><name sortKey="Comin, Matteo" sort="Comin, Matteo" uniqKey="Comin M" first="Matteo" last="Comin">Matteo Comin</name>
<affiliation><nlm:aff id="Aff1"><institution-wrap><institution-id institution-id-type="ISNI">0000 0004 1757 3470</institution-id>
<institution-id institution-id-type="GRID">grid.5608.b</institution-id>
<institution>Department of Information Engineering, University of Padova,</institution>
</institution-wrap>
via Gradenigo 6/A, Padova, Italy</nlm:aff>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">PMC</idno>
<idno type="pmid">31757199</idno>
<idno type="pmc">6873394</idno>
<idno type="url">http://www.ncbi.nlm.nih.gov/pmc/articles/PMC6873394</idno>
<idno type="RBID">PMC:6873394</idno>
<idno type="doi">10.1186/s12859-019-2883-5</idno>
<date when="2019">2019</date>
<idno type="wicri:Area/Pmc/Corpus">000287</idno>
<idno type="wicri:explorRef" wicri:stream="Pmc" wicri:step="Corpus" wicri:corpus="PMC">000287</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en" level="a" type="main">Better quality score compression through sequence-based quality smoothing</title>
<author><name sortKey="Shibuya, Yoshihiro" sort="Shibuya, Yoshihiro" uniqKey="Shibuya Y" first="Yoshihiro" last="Shibuya">Yoshihiro Shibuya</name>
<affiliation><nlm:aff id="Aff1"><institution-wrap><institution-id institution-id-type="ISNI">0000 0004 1757 3470</institution-id>
<institution-id institution-id-type="GRID">grid.5608.b</institution-id>
<institution>Department of Information Engineering, University of Padova,</institution>
</institution-wrap>
via Gradenigo 6/A, Padova, Italy</nlm:aff>
</affiliation>
<affiliation><nlm:aff id="Aff2"><institution-wrap><institution-id institution-id-type="ISNI">0000 0000 9103 9111</institution-id>
<institution-id institution-id-type="GRID">grid.462940.d</institution-id>
<institution>Laboratoire d’Informatique Gaspard-Monge (LIGM), University Paris-Est Marne-la-Vallée,</institution>
</institution-wrap>
Bâtiment Copernic - 5, bd Descartes, Champs sur Marne, France</nlm:aff>
</affiliation>
</author>
<author><name sortKey="Comin, Matteo" sort="Comin, Matteo" uniqKey="Comin M" first="Matteo" last="Comin">Matteo Comin</name>
<affiliation><nlm:aff id="Aff1"><institution-wrap><institution-id institution-id-type="ISNI">0000 0004 1757 3470</institution-id>
<institution-id institution-id-type="GRID">grid.5608.b</institution-id>
<institution>Department of Information Engineering, University of Padova,</institution>
</institution-wrap>
via Gradenigo 6/A, Padova, Italy</nlm:aff>
</affiliation>
</author>
</analytic>
<series><title level="j">BMC Bioinformatics</title>
<idno type="eISSN">1471-2105</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>Motivation</title>
<p>Current NGS techniques are becoming exponentially cheaper. As a result, there is an exponential growth of genomic data unfortunately not followed by an exponential growth of storage, leading to the necessity of compression. Most of the entropy of NGS data lies in the quality values associated to each read. Those values are often more diversified than necessary. Because of that, many tools such as Quartz or GeneCodeq, try to change (smooth) quality scores in order to improve compressibility without altering the important information they carry for downstream analysis like SNP calling.</p>
</sec>
<sec><title>Results</title>
<p>We use the FM-Index, a type of compressed suffix array, to reduce the storage requirements of a dictionary of k-mers and an effective smoothing algorithm to maintain high precision for SNP calling pipelines, while reducing quality scores entropy.</p>
<p>We present YALFF (Yet Another Lossy Fastq Filter), a tool for quality scores compression by smoothing leading to improved compressibility of FASTQ files. The succinct k-mers dictionary allows YALFF to run on consumer computers with only 5.7 GB of available free RAM. YALFF smoothing algorithm can improve genotyping accuracy while using less resources.</p>
</sec>
<sec><title>Availability</title>
<p><ext-link ext-link-type="uri" xlink:href="https://github.com/yhhshb/yalff">https://github.com/yhhshb/yalff</ext-link>
</p>
</sec>
<sec><title>Electronic supplementary material</title>
<p>The online version of this article (10.1186/s12859-019-2883-5) contains supplementary material, which is available to authorized users.</p>
</sec>
</div>
</front>
<back><div1 type="bibliography"><listBibl><biblStruct></biblStruct>
<biblStruct><analytic><author><name sortKey="Ewing, B" uniqKey="Ewing B">B Ewing</name>
</author>
<author><name sortKey="Hillier, L" uniqKey="Hillier L">L Hillier</name>
</author>
<author><name sortKey="Wendl, Mc" uniqKey="Wendl M">MC Wendl</name>
</author>
<author><name sortKey="Green, P" uniqKey="Green P">P Green</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Comin, M" uniqKey="Comin M">M Comin</name>
</author>
<author><name sortKey="Leoni, A" uniqKey="Leoni A">A Leoni</name>
</author>
<author><name sortKey="Schimd, M" uniqKey="Schimd M">M Schimd</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Comin, M" uniqKey="Comin M">M Comin</name>
</author>
<author><name sortKey="Leoni, A" uniqKey="Leoni A">A Leoni</name>
</author>
<author><name sortKey="Schimd, M" uniqKey="Schimd M">M Schimd</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Schimd, M" uniqKey="Schimd M">M Schimd</name>
</author>
<author><name sortKey="Comin, M" uniqKey="Comin M">M Comin</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Malysa, G" uniqKey="Malysa G">G Malysa</name>
</author>
<author><name sortKey="Hernaez, M" uniqKey="Hernaez M">M Hernaez</name>
</author>
<author><name sortKey="Ochoa, I" uniqKey="Ochoa I">I Ochoa</name>
</author>
<author><name sortKey="Rao, M" uniqKey="Rao M">M Rao</name>
</author>
<author><name sortKey="Ganesan, K" uniqKey="Ganesan K">K Ganesan</name>
</author>
<author><name sortKey="Weissman, T" uniqKey="Weissman T">T Weissman</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Roguski, L" uniqKey="Roguski L">L Roguski</name>
</author>
<author><name sortKey="Ochoa, I" uniqKey="Ochoa I">I Ochoa</name>
</author>
<author><name sortKey="Hernaez, M" uniqKey="Hernaez M">M Hernaez</name>
</author>
<author><name sortKey="Deorowicz, S" uniqKey="Deorowicz S">S Deorowicz</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Holley, G" uniqKey="Holley G">G Holley</name>
</author>
<author><name sortKey="Wittler, R" uniqKey="Wittler R">R Wittler</name>
</author>
<author><name sortKey="Stoye, J" uniqKey="Stoye J">J Stoye</name>
</author>
<author><name sortKey="Hach, F" uniqKey="Hach F">F Hach</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Grabowski, S" uniqKey="Grabowski S">S Grabowski</name>
</author>
<author><name sortKey="Deorowicz, S" uniqKey="Deorowicz S">S Deorowicz</name>
</author>
<author><name sortKey="Roguski, L" uniqKey="Roguski L">L Roguski</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Hach, F" uniqKey="Hach F">F Hach</name>
</author>
<author><name sortKey="Numanagi, I" uniqKey="Numanagi I">I Numanagić</name>
</author>
<author><name sortKey="Alkan, C" uniqKey="Alkan C">C Alkan</name>
</author>
<author><name sortKey="Sahinalp, Sc" uniqKey="Sahinalp S">SC Sahinalp</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Greenfield, Dl" uniqKey="Greenfield D">DL Greenfield</name>
</author>
<author><name sortKey="Stegle, O" uniqKey="Stegle O">O Stegle</name>
</author>
<author><name sortKey="Rrustemi, A" uniqKey="Rrustemi A">A Rrustemi</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Yu, Yw" uniqKey="Yu Y">YW Yu</name>
</author>
<author><name sortKey="Yorukoglu, D" uniqKey="Yorukoglu D">D Yorukoglu</name>
</author>
<author><name sortKey="Peng, J" uniqKey="Peng J">J Peng</name>
</author>
<author><name sortKey="Berger, B" uniqKey="Berger B">B Berger</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Bonfield, James K" uniqKey="Bonfield J">James K. Bonfield</name>
</author>
<author><name sortKey="Mahoney, Matthew V" uniqKey="Mahoney M">Matthew V. Mahoney</name>
</author>
</analytic>
</biblStruct>
<biblStruct></biblStruct>
<biblStruct><analytic><author><name sortKey="Canovas, R" uniqKey="Canovas R">R Cánovas</name>
</author>
<author><name sortKey="Moffat, A" uniqKey="Moffat A">A Moffat</name>
</author>
<author><name sortKey="Turpin, A" uniqKey="Turpin A">A Turpin</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Ochoa, I" uniqKey="Ochoa I">I Ochoa</name>
</author>
<author><name sortKey="Asnani, H" uniqKey="Asnani H">H Asnani</name>
</author>
<author><name sortKey="Bharadia, D" uniqKey="Bharadia D">D Bharadia</name>
</author>
<author><name sortKey="Chowdhury, M" uniqKey="Chowdhury M">M Chowdhury</name>
</author>
<author><name sortKey="Weissman, T" uniqKey="Weissman T">T Weissman</name>
</author>
<author><name sortKey="Yona, G" uniqKey="Yona G">G Yona</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Ochoa, I" uniqKey="Ochoa I">I Ochoa</name>
</author>
<author><name sortKey="Hernaez, M" uniqKey="Hernaez M">M Hernaez</name>
</author>
<author><name sortKey="Goldfeder, R" uniqKey="Goldfeder R">R Goldfeder</name>
</author>
<author><name sortKey="Weissman, T" uniqKey="Weissman T">T Weissman</name>
</author>
<author><name sortKey="Ashley, E" uniqKey="Ashley E">E Ashley</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Janin, L" uniqKey="Janin L">L Janin</name>
</author>
<author><name sortKey="Rosone, G" uniqKey="Rosone G">G Rosone</name>
</author>
<author><name sortKey="Cox, Aj" uniqKey="Cox A">AJ Cox</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Benoit, G" uniqKey="Benoit G">G Benoit</name>
</author>
<author><name sortKey="Lemaitre, C" uniqKey="Lemaitre C">C Lemaitre</name>
</author>
<author><name sortKey="Lavenier, D" uniqKey="Lavenier D">D Lavenier</name>
</author>
<author><name sortKey="Drezen, E" uniqKey="Drezen E">E Drezen</name>
</author>
<author><name sortKey="Dayris, T" uniqKey="Dayris T">T Dayris</name>
</author>
<author><name sortKey="Uricaru, R" uniqKey="Uricaru R">R Uricaru</name>
</author>
<author><name sortKey="Rizk, G" uniqKey="Rizk G">G Rizk</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Yu, Yw" uniqKey="Yu Y">YW Yu</name>
</author>
<author><name sortKey="Yorukoglu, D" uniqKey="Yorukoglu D">D Yorukoglu</name>
</author>
<author><name sortKey="Berger, B" uniqKey="Berger B">B Berger</name>
</author>
</analytic>
</biblStruct>
<biblStruct></biblStruct>
<biblStruct><analytic><author><name sortKey="Comin, M" uniqKey="Comin M">M Comin</name>
</author>
<author><name sortKey="Schimd, M" uniqKey="Schimd M">M Schimd</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Comin, M" uniqKey="Comin M">M Comin</name>
</author>
<author><name sortKey="Verzotto, D" uniqKey="Verzotto D">D Verzotto</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Girotto, S" uniqKey="Girotto S">S Girotto</name>
</author>
<author><name sortKey="Comin, M" uniqKey="Comin M">M Comin</name>
</author>
<author><name sortKey="Pizzi, C" uniqKey="Pizzi C">C Pizzi</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Qian, J" uniqKey="Qian J">J Qian</name>
</author>
<author><name sortKey="Marchiori, D" uniqKey="Marchiori D">D Marchiori</name>
</author>
<author><name sortKey="Comin, M" uniqKey="Comin M">M Comin</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Shibuya, Y" uniqKey="Shibuya Y">Y Shibuya</name>
</author>
<author><name sortKey="Comin, M" uniqKey="Comin M">M Comin</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Li, H" uniqKey="Li H">H Li</name>
</author>
<author><name sortKey="Durbin, R" uniqKey="Durbin R">R Durbin</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Li, H" uniqKey="Li H">H Li</name>
</author>
<author><name sortKey="Durbin, R" uniqKey="Durbin R">R Durbin</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Marcais, G" uniqKey="Marcais G">G Marçais</name>
</author>
<author><name sortKey="Kingsford, C" uniqKey="Kingsford C">C Kingsford</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Ferragina, P" uniqKey="Ferragina P">P Ferragina</name>
</author>
<author><name sortKey="Manzini, G" uniqKey="Manzini G">G Manzini</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Ferragina, P" uniqKey="Ferragina P">P Ferragina</name>
</author>
<author><name sortKey="Manzini, G" uniqKey="Manzini G">G Manzini</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Li, H" uniqKey="Li H">H Li</name>
</author>
<author><name sortKey="Durbin, R" uniqKey="Durbin R">R Durbin</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">BMC Bioinformatics</journal-id>
<journal-id journal-id-type="iso-abbrev">BMC Bioinformatics</journal-id>
<journal-title-group><journal-title>BMC Bioinformatics</journal-title>
</journal-title-group>
<issn pub-type="epub">1471-2105</issn>
<publisher><publisher-name>BioMed Central</publisher-name>
<publisher-loc>London</publisher-loc>
</publisher>
</journal-meta>
<article-meta><article-id pub-id-type="pmid">31757199</article-id>
<article-id pub-id-type="pmc">6873394</article-id>
<article-id pub-id-type="publisher-id">2883</article-id>
<article-id pub-id-type="doi">10.1186/s12859-019-2883-5</article-id>
<article-categories><subj-group subj-group-type="heading"><subject>Research</subject>
</subj-group>
</article-categories>
<title-group><article-title>Better quality score compression through sequence-based quality smoothing</article-title>
</title-group>
<contrib-group><contrib contrib-type="author"><name><surname>Shibuya</surname>
<given-names>Yoshihiro</given-names>
</name>
<address><email>yoshihiro.shibuya@studenti.unipd.it</email>
</address>
<xref ref-type="aff" rid="Aff1">1</xref>
<xref ref-type="aff" rid="Aff2">2</xref>
</contrib>
<contrib contrib-type="author" corresp="yes"><name><surname>Comin</surname>
<given-names>Matteo</given-names>
</name>
<address><email>comin@dei.unipd.it</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 0004 1757 3470</institution-id>
<institution-id institution-id-type="GRID">grid.5608.b</institution-id>
<institution>Department of Information Engineering, University of Padova,</institution>
</institution-wrap>
via Gradenigo 6/A, Padova, Italy</aff>
<aff id="Aff2"><label>2</label>
<institution-wrap><institution-id institution-id-type="ISNI">0000 0000 9103 9111</institution-id>
<institution-id institution-id-type="GRID">grid.462940.d</institution-id>
<institution>Laboratoire d’Informatique Gaspard-Monge (LIGM), University Paris-Est Marne-la-Vallée,</institution>
</institution-wrap>
Bâtiment Copernic - 5, bd Descartes, Champs sur Marne, France</aff>
</contrib-group>
<pub-date pub-type="epub"><day>22</day>
<month>11</month>
<year>2019</year>
</pub-date>
<pub-date pub-type="pmc-release"><day>22</day>
<month>11</month>
<year>2019</year>
</pub-date>
<pub-date pub-type="collection"><year>2019</year>
</pub-date>
<volume>20</volume>
<issue>Suppl 9</issue>
<issue-sponsor>Publication of this supplement has not been supported by sponsorship. Information about the source of funding for publication charges can be found in the individual articles. The articles have undergone the journal's standard peer review process for supplements. The Supplement Editors declare that they have no competing interests.</issue-sponsor>
<elocation-id>302</elocation-id>
<history><date date-type="received"><day>30</day>
<month>4</month>
<year>2019</year>
</date>
<date date-type="accepted"><day>7</day>
<month>5</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>Motivation</title>
<p>Current NGS techniques are becoming exponentially cheaper. As a result, there is an exponential growth of genomic data unfortunately not followed by an exponential growth of storage, leading to the necessity of compression. Most of the entropy of NGS data lies in the quality values associated to each read. Those values are often more diversified than necessary. Because of that, many tools such as Quartz or GeneCodeq, try to change (smooth) quality scores in order to improve compressibility without altering the important information they carry for downstream analysis like SNP calling.</p>
</sec>
<sec><title>Results</title>
<p>We use the FM-Index, a type of compressed suffix array, to reduce the storage requirements of a dictionary of k-mers and an effective smoothing algorithm to maintain high precision for SNP calling pipelines, while reducing quality scores entropy.</p>
<p>We present YALFF (Yet Another Lossy Fastq Filter), a tool for quality scores compression by smoothing leading to improved compressibility of FASTQ files. The succinct k-mers dictionary allows YALFF to run on consumer computers with only 5.7 GB of available free RAM. YALFF smoothing algorithm can improve genotyping accuracy while using less resources.</p>
</sec>
<sec><title>Availability</title>
<p><ext-link ext-link-type="uri" xlink:href="https://github.com/yhhshb/yalff">https://github.com/yhhshb/yalff</ext-link>
</p>
</sec>
<sec><title>Electronic supplementary material</title>
<p>The online version of this article (10.1186/s12859-019-2883-5) contains supplementary material, which is available to authorized users.</p>
</sec>
</abstract>
<kwd-group xml:lang="en"><title>Keywords</title>
<kwd>FASTQ compression</kwd>
<kwd>BWT</kwd>
<kwd>FM-Index</kwd>
</kwd-group>
<conference xlink:href="http://bioinformatics.it/"><conf-name>Annual Meeting of the Bioinformatics Italian Society (BITS 2018)</conf-name>
<conf-acronym>BITS 2018</conf-acronym>
<conf-loc>Turin, Italy</conf-loc>
<conf-date>27 - 29 June 2018</conf-date>
</conference>
<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" sec-type="introduction"><title>Introduction</title>
<p>Modern sequencing technologies produce large amount of data compared to the older machines. A single run can produce dozens of gigabytes, but in the near future the amount of data is going to grow in the orders of terabytes [<xref ref-type="bibr" rid="CR1">1</xref>
]. This poses the serious question of how to efficiently store and transmit these huge data sets, especially in anticipation of widespread adoption of personalized medicine and machine learning tasks.</p>
<p>The preferred files in which data are stored by sequencers is the well known FASTQ format. It is a textual file containing, for each read, an identifier, the nucleotide sequence, and a quality string. The quality string has the same length as the nucleotide sequence and each character encodes the probability of error of the corresponding base. The probability is usually encoded using the Phred quality score system [<xref ref-type="bibr" rid="CR2">2</xref>
]. Quality values are often essential for assessing sequence quality, filtering out low-quality reads, mapping reads to a reference genome, assembling genomic sequences, detecting mutations for genotyping, reads clustering [<xref ref-type="bibr" rid="CR3">3</xref>
, <xref ref-type="bibr" rid="CR4">4</xref>
] and comparison [<xref ref-type="bibr" rid="CR5">5</xref>
].</p>
<p>To reduce the memory required by a FASTQ file it is necessary to compress it. The DNA compression is usually as simple as assigning a two bit encoding to each of the four bases. This encoding achieve almost similar results to standard lossless compressors [<xref ref-type="bibr" rid="CR6">6</xref>
]. Moreover, the sequence exposes a high redundancy, especially on large reads collections with high coverage, and a number of methods have been developed to compress it [<xref ref-type="bibr" rid="CR7">7</xref>
–<xref ref-type="bibr" rid="CR10">10</xref>
]. On the other hand, the quality values span a wider range of values, and when compressed they can sum up to about 70% of the total space to encode a FASTQ file [<xref ref-type="bibr" rid="CR11">11</xref>
].</p>
<p>Quality scores are more difficult to compress due to a larger alphabet (63-94 in original form) and intrinsically have a higher entropy [<xref ref-type="bibr" rid="CR12">12</xref>
]. With lossless compression algorithms and entropy encoders reaching their theoretical limits and delivering only moderate compression ratios [<xref ref-type="bibr" rid="CR13">13</xref>
], there is a growing interest to develop lossy compression schemes to improve compressibility further.</p>
<p>To further reduce the file sizes, Illumina proposed a binning method to reduce the number of different quality values from 42 to 8 [<xref ref-type="bibr" rid="CR14">14</xref>
]. With this proposal, Illumina opened the doors for allowing lossy compression of the quality values. Another approach called P-Block [<xref ref-type="bibr" rid="CR15">15</xref>
] involves local quantization so that a representative quality score replaces a contiguous set of quality scores that are within a fixed distance of the representative score. Similarly, the R-Block [<xref ref-type="bibr" rid="CR15">15</xref>
] scheme replaces contiguous quality scores that are within a fixed relative distance of a representative score. Other lossy approaches improve compressibility and preserve higher fidelity by minimising a distortion metric such as mean-squared-error or L1-based errors (Qualcomp and QVZ) [<xref ref-type="bibr" rid="CR6">6</xref>
, <xref ref-type="bibr" rid="CR16">16</xref>
]. The drawback of lossy compression of quality values is that downstream analyses could be affected by the loss incurred with this type of compression. This could be the case for the above methods that process only the string of quality scores, without considering the DNA sequence associated to the read. However, [<xref ref-type="bibr" rid="CR12">12</xref>
, <xref ref-type="bibr" rid="CR17">17</xref>
] and [<xref ref-type="bibr" rid="CR11">11</xref>
] showed that quality values compressed with more advanced methods could achieve not only a better performance in downstream analyses than Illumina-binned quality values, but even better performance than the original quality values in some cases because these methods remove noise from the data.</p>
<p>The most promising methods are those using both sequence and quality information. The first method proposed in this class is [<xref ref-type="bibr" rid="CR18">18</xref>
], where the authors applied the Burrows-Wheeler Transform to the reads collection in order to detect groups of suffixes starting with the same prefix (with size at least k). All quality values in a group are smoothed with the mean value. Leon [<xref ref-type="bibr" rid="CR19">19</xref>
] constructs a reference from the input reads in the form of a bloom filter compressed de-Bruijn graph and then maps each nucleotide sequence as a path in the graph. If a base is covered by a sufficiently large number of k-mers from the reference its quality is set at a fixed high value. Among the most interesting tools, Quartz [<xref ref-type="bibr" rid="CR12">12</xref>
, <xref ref-type="bibr" rid="CR20">20</xref>
], similarly to Leon, relies on an external reference to decide if a given nucleotide is wrong or not. This reference database is implemented as list of k-mers stored explicitly, that requires 24GB when gzipped. Similarly, GeneCodeq [<xref ref-type="bibr" rid="CR11">11</xref>
] also has a list of k-mers as ground truth, but the algorithm involved during smoothing is more complex than Quartz. Each base has its associated error probability recalculated using a Bayesian framework and the smoothing takes place only if the new quality is greater than the old one. Both Quartz [<xref ref-type="bibr" rid="CR12">12</xref>
] and GeneCodeq [<xref ref-type="bibr" rid="CR11">11</xref>
] require a machine with at least 32GB of RAM, because of the size of the reference database.</p>
<p>In this paper we present YALFF (Yet Another Lossy Fastq Filter), a reference-based quality score compressor based on k-mers and the Burrows-Wheeler Transformation (BWT) [<xref ref-type="bibr" rid="CR21">21</xref>
], that is capable to improve compression while introducing low distortion into the processed data. One of the novelties of YALFF is that, thanks to the efficient data structure (BWT), it requires only a small amout of RAM (about 5GB) and it can be run on regular laptop. In the following sections we will present YALFF, and the results of our experiments, discussing the performances of YALFF under different metrics.</p>
</sec>
<sec id="Sec2"><title>Methods</title>
<p>In order to compress quality values it is important, not only to process the quality scores, but also to consider the corresponding sequence of DNA associated in the read. As already demonstrated by a number of studies (see above), the sequence can be used to predict the correctness of a base, without the need of costly alignments of the reads to a reference. Instead, the use of fast alignment-free methods, mostly based on k-mers, has replaced alignment-based methods in a number of different applications of sequence comparison [<xref ref-type="bibr" rid="CR22">22</xref>
–<xref ref-type="bibr" rid="CR25">25</xref>
]. In the context of quality compression, the use of alignment-free methods have attracted the attention for the good genotyping performance [<xref ref-type="bibr" rid="CR11">11</xref>
, <xref ref-type="bibr" rid="CR12">12</xref>
, <xref ref-type="bibr" rid="CR18">18</xref>
, <xref ref-type="bibr" rid="CR19">19</xref>
, <xref ref-type="bibr" rid="CR26">26</xref>
]. These methods are based on the idea that the correctness of a base can be predicted by the context of bases that are next to it. In [<xref ref-type="bibr" rid="CR18">18</xref>
, <xref ref-type="bibr" rid="CR19">19</xref>
] this local sequence context is computed from the input reads, using the BWT [<xref ref-type="bibr" rid="CR18">18</xref>
] or the de-Bruijn graph [<xref ref-type="bibr" rid="CR19">19</xref>
]. Instead, Quartz [<xref ref-type="bibr" rid="CR12">12</xref>
] and GeneCodeq [<xref ref-type="bibr" rid="CR11">11</xref>
] does not need to preprocess the reads, but they are based on an external dictionary of <italic>k</italic>
-mers. In this paper we introduce YALFF that uses a similar approach to Quartz and GeneCodeq, relying on a dictionary of k-mers in order to assess if one base of a read is correct or not. The most distinctive aspect of our approach is the compression of the k-mer list using a succinct data structure which allows us to store the whole dictionary in linear space. This task is achieved by using well-known data structures and algorithms such as the BWT [<xref ref-type="bibr" rid="CR21">21</xref>
] and its implementation found in BWA [<xref ref-type="bibr" rid="CR27">27</xref>
, <xref ref-type="bibr" rid="CR28">28</xref>
]. The main idea is to represent the list of k-mers as a single string so as to eliminate most of the redundancy in a typical k-mer dictionary. Similarly to the other methods, in YALFF the compression of quality values is performed by searching k-mers of the reads into the dictionary. The main difference is that YALFF requires all k-mers covering the base under investigation to be found in the dictionary in order to compress the corresponding quality, whereas for previous algorithms it is enough only one shared k-mer.</p>
<sec id="Sec3"><title>BWT Indexing of k-mers Dictionary</title>
<p>The most common procedure to obtain a reference list of k-mers from a set of sequences is by a k-mer counting procedure. Most k-mer counters keep track of each k-mer using hash tables, which usually require huge amounts of memory even though there exist optimized implementations [<xref ref-type="bibr" rid="CR29">29</xref>
] that allows for reduced memory overhead per key stored and concurrent access. Even if the under-represented k-mers and all the counters are removed from the resulting list, it still requires a huge amount of memory. For example, the 2 bit encoded dictionary for Quartz [<xref ref-type="bibr" rid="CR12">12</xref>
] sums up to 25 GB of space. Similarly, GeneCodeq [<xref ref-type="bibr" rid="CR11">11</xref>
] extracts all k-mers from the human reference genome and store them in a dictionary. Again, the memory requirements of GeneCodeq is of 24GB of RAM. Thus, both these methods are not suited to run on small machines.</p>
<p>The main insights in order to reduce the size of the dictionary is that most of the information carried by a k-mer stored explicitly is redundant. This intuition is easily explained by recalling the k-mer counting procedure itself. All the k-mers counted comes from a set of reference sequences and the counting procedure is only necessary to remove the wrong ones. There is no need to keep the k-mers explicitly stored to answer simple yes/no queries over their set. Given two consecutive k-mers it is possible to reassemble them into a single (k+1)-mer thus reducing the storage requirement by k-1 bases. This reassembly step can be carried out on the k-mers dictionary of Quartz, as well on the k-mers dictionary of GeneCodeq, leading to a linear sequence, or set of sequences, that contains all the input k-mers. However, if we want to use all the k-mers of a given reference genome, there are more efficient data structures to do so.</p>
<p>The problem of indexing a reference genome in minute space, while providing full search capability, has been widely studied and efficient data structure are now available. The data structure chosen for this purpose is the FM-Index [<xref ref-type="bibr" rid="CR30">30</xref>
, <xref ref-type="bibr" rid="CR31">31</xref>
] which is based on the Burrows-Wheeler transform (BWT) of a sequence. The FM-index, and its variants, are now at the basis of many algorithms in the field of sequence analysis. For example, one of the most used tool for reads mapping, BWA [<xref ref-type="bibr" rid="CR32">32</xref>
], is based on the FM-index and it requires as input the FM-index of the reference genome. For this reason, the FM-index of many genomes are available already as they are routinely used by bioinformaticians. Thus, we decided to use the FM-index of the human reference genome. Because a reference genome is also basic resource for every bioinformatician, this method has the collateral advantage of not requiring a separate indexed FASTA for compression instead sharing the same index for reads alignments.</p>
<p>The FM-index will be used to search for k-mers. The procedure to retrieve the position of a k-mer is the enhanced <italic>backward search</italic>
algorithm described in [<xref ref-type="bibr" rid="CR27">27</xref>
], that is also able to account for mismatches. In our case we will search if a k-mer is present in the reference genome with up to one mismatch.</p>
</sec>
<sec id="Sec4"><title>Quality Score Smoothing</title>
<p>The basic idea is that a read is represented by its constituent k-mers. Then, these k-mers can be used to assess if a given base of the read is correct. If a base is predicted to be correct, then we don’t need to store the corresponding quality value, but it can be substituted with a default value indicating a base with high probability to be correct.</p>
<p>The smoothing strategy of YALFF applies this rule as follows: each k-mer of a read is searched in the dictionary and each mismatch makes the corresponding quality score untouchable, that is, it is sufficient to have one non concordant base in one of the k-mers to maintain the corresponding quality value unchanged. If all the k-mers are concordant with the reference for a particular base the associated quality is set to a default value (Fig. <xref rid="Fig1" ref-type="fig">1</xref>
).
<fig id="Fig1"><label>Fig. 1</label>
<caption><p>Example of smoothing performed by YALFF. A mismatch in one of the k-mers is enough to keep the corresponding quality value unchanged</p>
</caption>
<graphic xlink:href="12859_2019_2883_Fig1_HTML" id="MO1"></graphic>
</fig>
</p>
<p>This basic procedure has been modified to include a threshold for the quality scores (Fig. <xref rid="Fig2" ref-type="fig">2</xref>
). All the scores below this threshold are maintained regardless of the outcome of the dictionary search. Such caveat is necessary to enforce YALFF to ignore very low quality k-mers. A very low quality base excludes all the k-mers covering that base as shown in Fig. <xref rid="Fig2" ref-type="fig">2</xref>
where the first five k-mers are skipped because of the single bad quality at position 5. The effect of having very low quality values will imply that all the k-mers containing one or more base with high probability of being incorrect are skipped. This also works as a trimming mechanism as shown in Fig. <xref rid="Fig3" ref-type="fig">3</xref>
where the tail of the read is left untouched.
<fig id="Fig2"><label>Fig. 2</label>
<caption><p>The threshold excludes k-mers 1 to 5 to be skipped by the algorithm</p>
</caption>
<graphic xlink:href="12859_2019_2883_Fig2_HTML" id="MO2"></graphic>
</fig>
<fig id="Fig3"><label>Fig. 3</label>
<caption><p>Example showing the threshold mechanism introduced to trim the low quality bases of a read. In this case only two k-mers are queried</p>
</caption>
<graphic xlink:href="12859_2019_2883_Fig3_HTML" id="MO3"></graphic>
</fig>
</p>
<p>Figure <xref rid="Fig4" ref-type="fig">4</xref>
displays the whole mechanism including both mismatches with the k-mers DB and low quality values. The threshold should be chosen depending on if it is necessary to avoid as much distortion as possible or if compression is considered much more important. As a rule of thumb a higher threshold maintains more quality values unchanged but this leads to an increase in the entropy of the output file. It is advisable to plot an histogram of the distribution of quality values to choose the threshold accordingly. A good value found for this study was a quality value equal to the character ’ (apex) which corresponds to a probability of error of 0.25119.
<fig id="Fig4"><label>Fig. 4</label>
<caption><p>An example of quality smoothing by YALFF including both mismatches with the k-mers DB and low quality values</p>
</caption>
<graphic xlink:href="12859_2019_2883_Fig4_HTML" id="MO4"></graphic>
</fig>
</p>
<p>According to other studies we selected the parameter <italic>k</italic>
=32 [<xref ref-type="bibr" rid="CR11">11</xref>
, <xref ref-type="bibr" rid="CR12">12</xref>
]. The k-mers should be long enough to ensure that the number of all possible k-mers is much larger than the number of unique k-mers in the genome, so as to ensure incidental collisions between unrelated k-mers are rare. Also, k-mer length should ideally be a multiple of four, since a 4bp length DNA sequence can be represented by a single byte. A 32-mer satisfies these constraints [<xref ref-type="bibr" rid="CR11">11</xref>
, <xref ref-type="bibr" rid="CR12">12</xref>
]; it is represented by a single 64-bit integer, with a relatively low probability of containing more than one sequencing error with Illumina sequences, as well as resulting in few k-mer collisions.</p>
</sec>
<sec id="Sec5"><title>Implementation details</title>
<p>YALFF is written in C/C++. The C parts are from BWA. In particular, the source code of the aln utility has been recycled to handle the query operations during smoothing. The FM-indexed version of a dictionary string is obtained through the index command of BWA. This opportunistic choice was made to ensure a widespread adoption of YALFF. Because BWA is the recommended aligner in most applications, it is extremely probable that a user who wants to compress some datasets will already have some sort of indexed reference genome which can be used as a dictionary. The indexing procedure and the data produced can be shared between our software and BWA leading to less time and storage required. In Fig. <xref rid="Fig5" ref-type="fig">5</xref>
is shown an overview of YALFF.
<fig id="Fig5"><label>Fig. 5</label>
<caption><p>An overview of YALFF’s inner structure</p>
</caption>
<graphic xlink:href="12859_2019_2883_Fig5_HTML" id="MO5"></graphic>
</fig>
</p>
<p>Because each read can be processed independently from the others, YALFF can be easily parallelized using more than one thread. The smoothed FASTQ files in output are guaranteed to maintain the order of the records compared to the input. This is particularly useful with paired end reads where the relative position of each read gives the association between them and thus has to be maintained.</p>
<p>In addition to the strictly necessary query parameters such as the k-mer length, the maximum number of mismatches allowed, the trimming threshold and the quality value used as replacement for the concordant bases, YALFF also supports other options. For example, as a speed up, it is possible to replace an entire block of quality values above a certain threshold with the smoothed value without searching the reference, or loading the reference in shared memory. Please refer to <ext-link ext-link-type="uri" xlink:href="https://github.com/yhhshb/yalff">https://github.com/yhhshb/yalff</ext-link>
for a complete description of the available options.</p>
</sec>
</sec>
<sec id="Sec6" sec-type="results"><title>Results</title>
<p>Since YALFF is a compressor where the reconstructed (i.e. decompressed) quality values can be different from the original ones, it is of uttermost importance to assess the effect that these changes in the quality values have on downstream applications. In the scope of this paper, in line with other studies, we choose variant calling as it is crucial for clinical decision making and thus widely used.</p>
<sec id="Sec7"><title>Datasets, pipeline and parameters</title>
<p>The dataset used in this study is a set of real reads (NA12878) from the <italic>1000 Genomes Project</italic>
http://www.<ext-link ext-link-type="uri" xlink:href="https://internationalgenome.org/data-portal/sample/NA12878">internationalgenome.org/data-portal/sample/NA12878</ext-link>
. Only the two paired end archives were used (namely SRR622461_1.filt.fastq.gz and SRR622561_2.filt.fast.gz) for the evaluation, while the third containing unpaired reads were discarded. All tests have been done from scratch using the two paired end reads to evaluate the tools, without using previous results from other papers in order to make the comparison as clear as possible. This dataset has been widely used for benchmarking in other papers, because the list of known SNPs is available and it can retrieved from <ext-link ext-link-type="uri" xlink:href="ftp://ussd-ftp.illumina.com/2017-1.0/hg38">ftp://ussd-ftp.illumina.com/2017-1.0/hg38</ext-link>
.</p>
<p>The reference genome used during alignment, and as a dictionary string for smoothing, is the human genome reference FASTA file hg38.fa downloaded from <ext-link ext-link-type="uri" xlink:href="http://hgdownload.cse.ucsc.edu/goldenpath/hg38/bigZips/">http://hgdownload.cse.ucsc.edu/goldenpath/hg38/bigZips/</ext-link>
. The FM-index of the human genome is computed only once, in about 1h, and then it can be used for multiple runs of quality compression and reads alignment. The genotyping pipeline is implemented as a single bash script which uses bwa mem for alignments, bcftools for SNP calling and vcfeval for evaluation. All scripts can be found at <ext-link ext-link-type="uri" xlink:href="https://github.com/yhhshb/yalff/tree/master/scripts">https://github.com/yhhshb/yalff/tree/master/scripts</ext-link>
.</p>
<p>Although YALFF can be run on a normal laptop, as opposed to Quartz, for all tools all tests were performed on a 14 lame blade cluster DELL PowerEdge M600 where each lame is equipped with two Intel Xeon E5450 at 3.00 GHz, 16GB RAM and two 72GB hard disk in RAID-1 (mirroring).</p>
<p>In this study we compared YALFF with other alignment-free methods, e.g. Quartz and Leon, as well as with other methods that are not based on the sequence like: Illumina 8bin, Pblock, Rblock and QVZ. As reported in [<xref ref-type="bibr" rid="CR11">11</xref>
, <xref ref-type="bibr" rid="CR12">12</xref>
] reference-based methods are the most promising in terms of SNPs detection, in fact only these methods are able to improve the genotyping accuracy w.r.t. to the original reads. The choice to include Leon instead of GeneCodeq is because the latter does not provide an open source license but only non-optimized pre-compiled executables are available. Leon, on the other hand, is completely open-source and its binaries are optimized for most use cases. It also uses a probabilistic de-Brujin graph generated from the reads in input for smoothing instead of a predefined reference, thus widening the scope of the comparison. Leon does not produce a FASTQ file by default and uses its own compressed format instead. The exact commands for each program are reported in the Additional file <xref rid="MOESM1" ref-type="media">1</xref>
.</p>
<p>The result section below shows time measurements for each tool defined as the time to obtain the smoothed FASTQ file from the original.</p>
</sec>
<sec id="Sec8"><title>Genotyping Accuracy</title>
<p>The performance evaluation of the algorithms compares the number of retrieved SNPs from a smoothed file to the ground truth associated with the original dataset. Each set of variants (stored in the output VCF file) is compared against the consensus set of variants. The benchmarking tools output the following values.
<list list-type="bullet"><list-item><p>True Positives (T.P.): All those variants that are both in the consensus set and in the set of called variants.</p>
</list-item>
<list-item><p>False Positives (F.P.): All those variants that are in the called set of variants but not in the consensus set.</p>
</list-item>
<list-item><p>False Negatives (F.N.): All those variants that are in the consensus set but not in the set of called variants.</p>
</list-item>
</list>
</p>
<p>These values are used to compute the following three metrics:
<list list-type="bullet"><list-item><p>Recall: This is the proportion of called variants that are included in the consensus set; that is, <italic>R</italic>
=<italic>T</italic>
.<italic>P</italic>
./(<italic>T</italic>
.<italic>P</italic>
.+<italic>F</italic>
.<italic>N</italic>
.),</p>
</list-item>
<list-item><p>Precision: This is the proportion of consensus variants that are called by the variant calling pipeline; that is, <italic>P</italic>
=<italic>T</italic>
.<italic>P</italic>
./(<italic>T</italic>
.<italic>P</italic>
.+<italic>F</italic>
.<italic>P</italic>
.).</p>
</list-item>
<list-item><p>F-Measure: The harmonic mean of precision and recall; that is, <italic>F</italic>
−<italic>Measure</italic>
=2∗(<italic>P</italic>
∗<italic>R</italic>
)/(<italic>P</italic>
+<italic>R</italic>
)</p>
</list-item>
</list>
</p>
<p>In the first experiments we run all tools and test how the modified quality values influence the detection of SNPs. We use the above metrics to assess the performance with respect to the original unsmoothed FASTQ file.</p>
<p>Table <xref rid="Tab1" ref-type="table">1</xref>
reports the results of these first experiments. The F-measure is a global indicator of the goodness of results, as it captures both precision and recall. If we compare the F-measures of all tools with respect to that of the original unsmoothed fastq, we can observe that the only methods that are able to improve this measure are Quartz and YALFF, whereas all other tools have lower F-measures. The F-measure improvement of Quartz is higher than YALFF and it is mainly due to the higher recall. A possible explanation is the fact that YALFF uses only k-mers from one reference genome, while the k-mers DB of Quartz is built from multiple genomes. Quartz shows the highest recall, that is, more SNPs are found, but at the expenses of the precision, in fact it exhibits the lowest precision and the highest number of false positives. If we consider the precision, the performance of Quartz degrades w.r.t. to the unsmoothed file, while YALFF is closer to it. High values of precision are reported also for Pblock, Rblock and Illumina 8bin, but in these cases the recall decreases. Overall, only Quartz and YALFF are to improve genotyping accuracy in terms of F-measure. However, YALFF produces very few false positive SNPs, as opposed to Quartz. This is a desirable characteristic especially in sensitive application such as health care or cancer analysis. Similar observations can be deduced from the ROC curves in Fig. <xref rid="Fig6" ref-type="fig">6</xref>
. This Figure reports the number of true positives as a function of the false positives, and it includes for completeness the recall rate. More ROC curves can be found in the Additional file <xref rid="MOESM1" ref-type="media">1</xref>
.
<fig id="Fig6"><label>Fig. 6</label>
<caption><p>ROC curves of SNPs calling for various methods</p>
</caption>
<graphic xlink:href="12859_2019_2883_Fig6_HTML" id="MO6"></graphic>
</fig>
<table-wrap id="Tab1"><label>Table 1</label>
<caption><p>Comparison of various metrics T.P., F.P., F.N., Precision, Recall and F-Measure in SNP calling between different tools</p>
</caption>
<table frame="hsides" rules="groups"><thead><tr><th align="left">Smoothing algorithm</th>
<th align="left">T.P.</th>
<th align="left">F.P.</th>
<th align="left">F.N.</th>
<th align="left">Precision</th>
<th align="left">Recall</th>
<th align="left">F-Measure</th>
</tr>
</thead>
<tbody><tr><td align="left">None (original files)</td>
<td align="left">2588159</td>
<td align="left">219803</td>
<td align="left">1493731</td>
<td align="left">0.9217</td>
<td align="left">0.6341</td>
<td align="left">0.7513</td>
</tr>
<tr><td align="left">YALFF</td>
<td align="left">2603620</td>
<td align="left">221368</td>
<td align="left">1478264</td>
<td align="left">0.9216</td>
<td align="left">0.6378</td>
<td align="left">0.7539</td>
</tr>
<tr><td align="left">Quartz</td>
<td align="left">2661218</td>
<td align="left">237820</td>
<td align="left">1420672</td>
<td align="left">0.9180</td>
<td align="left">0.6520</td>
<td align="left">0.7624</td>
</tr>
<tr><td align="left">Leon</td>
<td align="left">2278517</td>
<td align="left">204803</td>
<td align="left">1803366</td>
<td align="left">0.9175</td>
<td align="left">0.5582</td>
<td align="left">0.6941</td>
</tr>
<tr><td align="left">Illumina 8bin</td>
<td align="left">2546518</td>
<td align="left">216128</td>
<td align="left">1535370</td>
<td align="left">0.9218</td>
<td align="left">0.6239</td>
<td align="left">0.7441</td>
</tr>
<tr><td align="left">Pblock p =2</td>
<td align="left">2574111</td>
<td align="left">218405</td>
<td align="left">1507773</td>
<td align="left">0.9218</td>
<td align="left">0.6306</td>
<td align="left">0.7489</td>
</tr>
<tr><td align="left">Pblock p =4</td>
<td align="left">2558612</td>
<td align="left">216995</td>
<td align="left">1523273</td>
<td align="left">0.9218</td>
<td align="left">0.6268</td>
<td align="left">0.7462</td>
</tr>
<tr><td align="left">Rblock t =1.1</td>
<td align="left">2550179</td>
<td align="left">216738</td>
<td align="left">1531706</td>
<td align="left">0.9217</td>
<td align="left">0.6248</td>
<td align="left">0.7447</td>
</tr>
<tr><td align="left">Rblock t =1.15</td>
<td align="left">2526704</td>
<td align="left">215721</td>
<td align="left">1555181</td>
<td align="left">0.9213</td>
<td align="left">0.6190</td>
<td align="left">0.7405</td>
</tr>
<tr><td align="left">QVZ 0.6</td>
<td align="left">2588704</td>
<td align="left">225730</td>
<td align="left">1493180</td>
<td align="left">0.9198</td>
<td align="left">0.6342</td>
<td align="left">0.7507</td>
</tr>
<tr><td align="left">QVZ 0.8</td>
<td align="left">2588773</td>
<td align="left">223210</td>
<td align="left">1493112</td>
<td align="left">0.9206</td>
<td align="left">0.6342</td>
<td align="left">0.7510</td>
</tr>
</tbody>
</table>
</table-wrap>
</p>
</sec>
<sec id="Sec9"><title>Timing and RAM</title>
<p>We also compared the methods in terms of computing resources required for smoothing. The time measurements are the real wall clock times given by the time command on POSIX systems. Because all the tools where given one processor to perform their tasks the real wall clock time and the sum of user and sys times were comparable. All tools were tested on uncompressed FASTQ files because both Quartz and Leon don’t support compressed I/O. It must be noted that YALFF relies on the system pipe mechanism for read/write operations and can be used on compressed archives simply by command concatenation. The I/O operations and throughput handling are left to the pipe mechanism leading to a much more friendly experience.</p>
<p>The fastest tools are those based only on the quality values, like Illumina 8bin, Pblock, Rblock and QVZ. They all require similar computing resources of about few GBs of RAM and 40 to 60 min for the execution. On the other hand, the methods that process also the sequence, like Quartz, YALFF and Leon, are more computationally demanding. Figure <xref rid="Fig7" ref-type="fig">7</xref>
shows a graphical representation of time and memory measures for Quartz, YALFF and Leon. In terms of execution times YALFF is the slowest of the three, with computing times comparable to Quartz, but not as fast as Leon. Leon on the other hand is the fastest, but it is also the least accurate tool with the worst precision and recall. YALFF despite being the slowest it requires less memory, only 5.7 GB of RAM, whereas Leon and Quartz need 6.3 GB and 25.4 GB respectively. Thus YALFF is the only one that can achieve good accuracy on SNPs calling and it can be used on a desktop computer, without relying on expensive hardware.
<fig id="Fig7"><label>Fig. 7</label>
<caption><p>Histogram showing the total execution time in hours and peak RAM usage of the different programs</p>
</caption>
<graphic xlink:href="12859_2019_2883_Fig7_HTML" id="MO7"></graphic>
</fig>
</p>
<p>We tested also the scalability of YALFF. In Fig. <xref rid="Fig8" ref-type="fig">8</xref>
are reported the computing time of YALFF to smooth a single FASTQ file as a function of the number of cores used. To be able to make those scalability measures as reliable as possible each round has the number of cores allocated by a server supervisor so that no additional idle cores are present at each run. Both input and output streams use uncompressed files to make the plot comparable with the others. The optimal number of cores seems to be 3 or 4 but it strongly depends on the secondary storage device used and its characteristics. Using an SSD allows for better throughput and better core utilization. In summary YALFF can be easily parallelized to speed up smoothing.
<fig id="Fig8"><label>Fig. 8</label>
<caption><p>Time taken by YALFF to smooth a FASTQ file as a function of the number of cores</p>
</caption>
<graphic xlink:href="12859_2019_2883_Fig8_HTML" id="MO8"></graphic>
</fig>
</p>
</sec>
<sec id="Sec10"><title>Compression</title>
<p>In this section we evaluate the compression ratios between the original uncompressed files and the compressed ones, while varying the smoothing method. To have a better overview of the compression ratios we used three lossless compressors, two widely used tool as gzip and bzips, and a more advanced one LZMA.</p>
<p>The results are shown in Table <xref rid="Tab2" ref-type="table">2</xref>
. As expected the smoothed files are more compressible that the original FASTQ. Also, LZMA achieves better compression ratios than gzip and bzip on all tests. In terms of compression ratio, the methods based on the sequence are able to achieve better compression. Among the methods based only on the quality values, Rblock appears to be the best one. If we consider all smoothing methods we can observe that YALFF has the best compression ratios, outperforming all other tools, irrespective of the compressor used.
<table-wrap id="Tab2"><label>Table 2</label>
<caption><p>Compression ratio for the different smoothing tools and compressors. The ratio is defined as <inline-formula id="IEq1"><alternatives><tex-math id="M1">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\frac {\text {uncompressed size}}{\text {compressed size}}$\end{document}</tex-math>
<mml:math id="M2"><mml:mfrac><mml:mrow><mml:mtext>uncompressed size</mml:mtext>
</mml:mrow>
<mml:mrow><mml:mtext>compressed size</mml:mtext>
</mml:mrow>
</mml:mfrac>
</mml:math>
<inline-graphic xlink:href="12859_2019_2883_Article_IEq1.gif"></inline-graphic>
</alternatives>
</inline-formula>
where the uncompressed size is 42GB</p>
</caption>
<table frame="hsides" rules="groups"><thead><tr><th align="left">Smoothing algorithm</th>
<th align="left">gzip</th>
<th align="left">bzip2</th>
<th align="left">xz (LZMA)</th>
</tr>
</thead>
<tbody><tr><td align="left">None (original files)</td>
<td align="left">4.617</td>
<td align="left">5.152</td>
<td align="left">5.918</td>
</tr>
<tr><td align="left">YALFF</td>
<td align="left">7.147</td>
<td align="left">7.633</td>
<td align="left">9.186</td>
</tr>
<tr><td align="left">Quartz</td>
<td align="left">6.925</td>
<td align="left">7.349</td>
<td align="left">8.827</td>
</tr>
<tr><td align="left">Leon</td>
<td align="left">7.098</td>
<td align="left">7.551</td>
<td align="left">8.988</td>
</tr>
<tr><td align="left">Illumina 8bin</td>
<td align="left">6.054</td>
<td align="left">6.742</td>
<td align="left">7.819</td>
</tr>
<tr><td align="left">Pblock p =2</td>
<td align="left">5.373</td>
<td align="left">5.966</td>
<td align="left">7.011</td>
</tr>
<tr><td align="left">Pblock p =4</td>
<td align="left">6.052</td>
<td align="left">6.647</td>
<td align="left">7.671</td>
</tr>
<tr><td align="left">Rblock t =1.1</td>
<td align="left">6.285</td>
<td align="left">6.859</td>
<td align="left">7.941</td>
</tr>
<tr><td align="left">Rblock t =1.15</td>
<td align="left">6.675</td>
<td align="left">7.250</td>
<td align="left">8.443</td>
</tr>
<tr><td align="left">QVZ 0.6</td>
<td align="left">4.776</td>
<td align="left">5.533</td>
<td align="left">6.395</td>
</tr>
<tr><td align="left">QVZ 0.8</td>
<td align="left">4.778</td>
<td align="left">5.510</td>
<td align="left">6.366</td>
</tr>
</tbody>
</table>
</table-wrap>
</p>
</sec>
<sec id="Sec11"><title>YALFF parameters</title>
<p>In this section we evaluate the impact of the parameters of YALFF. We recall that YALFF has three parameters: k for the length of k-mers, the lower quality threshold (L.T.) for trimming and the higher quality threshold (H.T.) to speed-up the smoothing. The thresholds L.T. and H.T. are expressed using the Phred quality representation, that for Illumina spans between 0 (poor quality) to 41 (high quality). In the previous experiments we used as default values k =32, L.T. =6 and H.T. =40. In Table <xref rid="Tab3" ref-type="table">3</xref>
we report the performance of YALFF for various parameters.
<table-wrap id="Tab3"><label>Table 3</label>
<caption><p>The impact of the parameters of YALFF for various metrics T.P., F.P., F.N., Precision, Recall, F-Measure, Compression (LZMA) and Time (min.)</p>
</caption>
<table frame="hsides" rules="groups"><thead><tr><th align="left" colspan="3">Parameters</th>
<th align="left"></th>
<th align="left"></th>
<th align="left"></th>
<th align="left"></th>
<th align="left"></th>
<th align="left"></th>
<th align="left"></th>
<th align="left"></th>
</tr>
<tr><th align="left">k</th>
<th align="left">L.T.</th>
<th align="left">H.T.</th>
<th align="left">T.P.</th>
<th align="left">F.P.</th>
<th align="left">F.N.</th>
<th align="left">Prec.</th>
<th align="left">Recall</th>
<th align="left">F-M.</th>
<th align="left">Compr.</th>
<th align="left">Time</th>
</tr>
</thead>
<tbody><tr><td align="left">16</td>
<td align="left">6</td>
<td align="left">40</td>
<td align="left">2659170</td>
<td align="left">276596</td>
<td align="left">1422714</td>
<td align="left">0.9058</td>
<td align="left">0.6515</td>
<td align="left">0.7579</td>
<td align="left">10.107</td>
<td align="left">11850</td>
</tr>
<tr><td align="left">32</td>
<td align="left">6</td>
<td align="left">40</td>
<td align="left">2603620</td>
<td align="left">221368</td>
<td align="left">1478264</td>
<td align="left">0.9216</td>
<td align="left">0.6378</td>
<td align="left">0.7539</td>
<td align="left">9.186</td>
<td align="left">2934</td>
</tr>
<tr><td align="left">48</td>
<td align="left">6</td>
<td align="left">40</td>
<td align="left">2588254</td>
<td align="left">220176</td>
<td align="left">1493631</td>
<td align="left">0.9216</td>
<td align="left">0.6341</td>
<td align="left">0.7513</td>
<td align="left">5.936</td>
<td align="left">509</td>
</tr>
<tr><td align="left">32</td>
<td align="left">0</td>
<td align="left">40</td>
<td align="left">2626957</td>
<td align="left">253747</td>
<td align="left">1454928</td>
<td align="left">0.9119</td>
<td align="left">0.6436</td>
<td align="left">0.7546</td>
<td align="left">9.181</td>
<td align="left">2657</td>
</tr>
<tr><td align="left">32</td>
<td align="left">3</td>
<td align="left">40</td>
<td align="left">2603891</td>
<td align="left">221696</td>
<td align="left">1477993</td>
<td align="left">0.9215</td>
<td align="left">0.6379</td>
<td align="left">0.7539</td>
<td align="left">9.113</td>
<td align="left">2315</td>
</tr>
<tr><td align="left">32</td>
<td align="left">12</td>
<td align="left">40</td>
<td align="left">2601463</td>
<td align="left">219417</td>
<td align="left">1480421</td>
<td align="left">0.9222</td>
<td align="left">0.6373</td>
<td align="left">0.7537</td>
<td align="left">8.813</td>
<td align="left">2239</td>
</tr>
<tr><td align="left">32</td>
<td align="left">3</td>
<td align="left">30</td>
<td align="left">2616530</td>
<td align="left">225716</td>
<td align="left">1465356</td>
<td align="left">0.9206</td>
<td align="left">0.6410</td>
<td align="left">0.7558</td>
<td align="left">9.597</td>
<td align="left">565</td>
</tr>
<tr><td align="left">32</td>
<td align="left">3</td>
<td align="left">35</td>
<td align="left">2612145</td>
<td align="left">223372</td>
<td align="left">1469743</td>
<td align="left">0.9212</td>
<td align="left">0.6399</td>
<td align="left">0.7552</td>
<td align="left">9.429</td>
<td align="left">848</td>
</tr>
<tr><td align="left">32</td>
<td align="left">3</td>
<td align="left">37</td>
<td align="left">2609021</td>
<td align="left">222494</td>
<td align="left">1472866</td>
<td align="left">0.9214</td>
<td align="left">0.6392</td>
<td align="left">0.7548</td>
<td align="left">9.115</td>
<td align="left">1279</td>
</tr>
</tbody>
</table>
</table-wrap>
</p>
<p>The most important parameter is the length of the k-mers. If k is small, e.g. k =16, there is a small improvement in terms of F-measure and compression, however this comes at the expenses of the computing time that increases substantially. On the other hand, if k =48, the running time decreases, but also the compression decreases. We choose k =32 as the best compromise between compression and computing time. The lower threshold (L.T.) is used for trimming low quality values, that are not boosted by YALFF. If this threshold is not applied (L.T. =0) the precision decreases. If higher values are used (L.T. =12) the precision increases, but the compression decreases. We choose L.T. =6 as a trade off between trimming and compression. The higher quality threshold (H.T.) can be used to speed-up the computation by boosting all quality values above H.T. If we use H.T. =30 the computation time decreases considerably, with a small reduction of precision. However, if time is not a constraint and precision is most important, we suggest to use high values of H.T.</p>
</sec>
</sec>
<sec id="Sec12" sec-type="discussion"><title>Discussion</title>
<p>The low compressibility of quality values is one of the main problem of sequencing reads compression. Several lossy smoothing strategies have been proposed, all with the intent to improve compressibility without altering the information carried by quality value for downstream analysis. Here, we propose YALFF, a tool that smooths quality scores based on a dictionary of k-mers from a reference genome. The YALFF smoothing algorithm can achieve low distortion of the processed datasets with a small degradation of precision during SNP calling, but with an overall improvement of F-measure. We developed this program with consumer application of genome sequencing in mind. For example, one of the current hot topic is personalized medicine, which requires huge databases to store as many genomic information as possible and new methods to allow common users to share their genetic code. New compression programs needs to be developed to tackle these problems. Tools with reduced memory consumption, like YALFF, to be executed on commodity computers, will enhance the sharing of sequencing data.</p>
<p>Unfortunately, YALFF is not perfect and it can be further improved. Its main flaw is the time inefficiency compared to e.g. Quartz or Leon. Using a compressed data structure as a dictionary can compromise cache efficiency. The main question which needs to be investigated further is if it is possible to develop a compressed dictionary with good locality properties.</p>
</sec>
<sec id="Sec13" sec-type="conclusion"><title>Conclusions</title>
<p>In this work, we have presented YALFF, a lossy FASTQ smoother which uses a dictionary of k-mers that are compressed with a BWT. YALFF is able to reduce the entropy of quality scores by smoothing leading to improved compressibility of FASTQ files w.r.t. to other popular tools. The succinct dictionary allows YALFF to run on consumer computers with only 5.7 GB of RAM, as opposed to Quartz that requires large amount of memory. The smoothing algorithm of YALFF can improve the genotyping accuracy, in terms of F-measure, when compared with the unsmoothed FASTQ, and it can also reduce the number of false positive, w.r.t. Quartz. In summary YALFF produces smoothed FASTQ that are highly compressible, while maintaining high accuracy on genotyping and using less resources.</p>
</sec>
<sec sec-type="supplementary-material"><title>Additional file</title>
<sec id="Sec14"><p><supplementary-material content-type="local-data" id="MOESM1"><media xlink:href="12859_2019_2883_MOESM1_ESM.pdf"><label>Additional file 1</label>
<caption><p>Supplementary Material. (PDF 303 kb)</p>
</caption>
</media>
</supplementary-material>
</p>
</sec>
</sec>
</body>
<back><glossary><title>Abbreviations</title>
<def-list><def-item><term>BWT</term>
<def><p>Burrows-wheeler transform</p>
</def>
</def-item>
<def-item><term>NGS</term>
<def><p>Next-gen sequencing</p>
</def>
</def-item>
<def-item><term>SNP</term>
<def><p>Single nucleotide polymorphisms</p>
</def>
</def-item>
<def-item><term>YALFF</term>
<def><p>Yet another lossy fastq filter</p>
</def>
</def-item>
</def-list>
</glossary>
<ack><title>Acknowledgements</title>
<p>Not applicable.</p>
<sec id="d29e1681"><title>Funding</title>
<p>Publication of this article did not receive sponsorship.</p>
</sec>
<sec id="d29e1686" sec-type="data-availability"><title>Availability of data and materials</title>
<p>The software is freely available under the MIT license at: <ext-link ext-link-type="uri" xlink:href="https://github.com/yhhshb/yalff">https://github.com/yhhshb/yalff</ext-link>
.</p>
</sec>
<sec id="d29e1696"><title>About this supplement</title>
<p>This article has been published as part of BMC Bioinformatics, Volume 20 Supplement 9, 2019: Italian Society of Bioinformatics (BITS): Annual Meeting 2018. The full contents of the supplement are available at <ext-link ext-link-type="uri" xlink:href="https://bmcbioinformatics.biomedcentral.com/articles/supplements/volume-20-supplement-9">https://bmcbioinformatics.biomedcentral.com/articles/supplements/volume-20-supplement-9</ext-link>
.</p>
</sec>
</ack>
<notes notes-type="author-contribution"><title>Authors’ contributions</title>
<p>All authors contributed to the design of the approach and to the analysis of the results. YS implemented YALFF software and performed the experiments. YS and MC conceived the study and drafted the manuscript. Both authors have read and approved the manuscript for publication.</p>
</notes>
<notes><title>Ethics approval and consent to participate</title>
<p>Not applicable.</p>
</notes>
<notes><title>Consent for publication</title>
<p>Not applicable.</p>
</notes>
<notes notes-type="COI-statement"><title>Competing interests</title>
<p>The authors declare that they have no competing interests.</p>
</notes>
<notes><title>Publisher’s Note</title>
<p>Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.</p>
</notes>
<ref-list id="Bib1"><title>References</title>
<ref id="CR1"><label>1</label>
<mixed-citation publication-type="other">Google Genomics - Store, process, explore and share. <ext-link ext-link-type="uri" xlink:href="https://cloud.google.com/genomics/">https://cloud.google.com/genomics/</ext-link>
.</mixed-citation>
</ref>
<ref id="CR2"><label>2</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Ewing</surname>
<given-names>B</given-names>
</name>
<name><surname>Hillier</surname>
<given-names>L</given-names>
</name>
<name><surname>Wendl</surname>
<given-names>MC</given-names>
</name>
<name><surname>Green</surname>
<given-names>P</given-names>
</name>
</person-group>
<article-title>Base-Calling of Automated Sequencer Traces UsingPhred, I. Accuracy Assessment</article-title>
<source>Genome Res</source>
<year>1998</year>
<volume>8</volume>
<issue>3</issue>
<fpage>175</fpage>
<lpage>85</lpage>
<pub-id pub-id-type="pmid">9521921</pub-id>
</element-citation>
</ref>
<ref id="CR3"><label>3</label>
<element-citation publication-type="book"><person-group person-group-type="author"><name><surname>Comin</surname>
<given-names>M</given-names>
</name>
<name><surname>Leoni</surname>
<given-names>A</given-names>
</name>
<name><surname>Schimd</surname>
<given-names>M</given-names>
</name>
</person-group>
<person-group person-group-type="editor"><name><surname>Brown</surname>
<given-names>D</given-names>
</name>
<name><surname>Morgenstern</surname>
<given-names>B</given-names>
</name>
</person-group>
<article-title>Qcluster: Extending alignment-free measures with quality values for reads clustering</article-title>
<source>Algorithms in Bioinformatics</source>
<year>2014</year>
<publisher-loc>Berlin, Heidelberg</publisher-loc>
<publisher-name>Springer</publisher-name>
</element-citation>
</ref>
<ref id="CR4"><label>4</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Comin</surname>
<given-names>M</given-names>
</name>
<name><surname>Leoni</surname>
<given-names>A</given-names>
</name>
<name><surname>Schimd</surname>
<given-names>M</given-names>
</name>
</person-group>
<article-title>Clustering of reads with alignment-free measures and quality values</article-title>
<source>Algoritm Mol Biol</source>
<year>2015</year>
<volume>10</volume>
<issue>1</issue>
<fpage>1</fpage>
<lpage>10</lpage>
</element-citation>
</ref>
<ref id="CR5"><label>5</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Schimd</surname>
<given-names>M</given-names>
</name>
<name><surname>Comin</surname>
<given-names>M</given-names>
</name>
</person-group>
<article-title>Fast comparison of genomic and meta-genomic reads with alignment-free measures based on quality values</article-title>
<source>BMC Med Genomics</source>
<year>2016</year>
<volume>9</volume>
<issue>1</issue>
<fpage>41</fpage>
<lpage>50</lpage>
<pub-id pub-id-type="pmid">27510222</pub-id>
</element-citation>
</ref>
<ref id="CR6"><label>6</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Malysa</surname>
<given-names>G</given-names>
</name>
<name><surname>Hernaez</surname>
<given-names>M</given-names>
</name>
<name><surname>Ochoa</surname>
<given-names>I</given-names>
</name>
<name><surname>Rao</surname>
<given-names>M</given-names>
</name>
<name><surname>Ganesan</surname>
<given-names>K</given-names>
</name>
<name><surname>Weissman</surname>
<given-names>T</given-names>
</name>
</person-group>
<article-title>QVZ: lossy compression of quality values</article-title>
<source>Bioinformatics (Oxford, England)</source>
<year>2015</year>
<volume>31</volume>
<issue>19</issue>
<fpage>3122</fpage>
<lpage>9</lpage>
</element-citation>
</ref>
<ref id="CR7"><label>7</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Roguski</surname>
<given-names>L</given-names>
</name>
<name><surname>Ochoa</surname>
<given-names>I</given-names>
</name>
<name><surname>Hernaez</surname>
<given-names>M</given-names>
</name>
<name><surname>Deorowicz</surname>
<given-names>S</given-names>
</name>
</person-group>
<article-title>Fastore: a space-saving solution for raw sequencing data</article-title>
<source>Bioinformatics</source>
<year>2018</year>
<volume>34</volume>
<issue>16</issue>
<fpage>2748</fpage>
<lpage>56</lpage>
<pub-id pub-id-type="pmid">29617939</pub-id>
</element-citation>
</ref>
<ref id="CR8"><label>8</label>
<element-citation publication-type="book"><person-group person-group-type="author"><name><surname>Holley</surname>
<given-names>G</given-names>
</name>
<name><surname>Wittler</surname>
<given-names>R</given-names>
</name>
<name><surname>Stoye</surname>
<given-names>J</given-names>
</name>
<name><surname>Hach</surname>
<given-names>F</given-names>
</name>
</person-group>
<person-group person-group-type="editor"><name><surname>Sahinalp</surname>
<given-names>SC</given-names>
</name>
</person-group>
<article-title>Dynamic alignment-free and reference-free read compression</article-title>
<source>Research in Computational Molecular Biology</source>
<year>2017</year>
<publisher-loc>Cham</publisher-loc>
<publisher-name>Springer</publisher-name>
</element-citation>
</ref>
<ref id="CR9"><label>9</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Grabowski</surname>
<given-names>S</given-names>
</name>
<name><surname>Deorowicz</surname>
<given-names>S</given-names>
</name>
<name><surname>Roguski</surname>
<given-names>L</given-names>
</name>
</person-group>
<article-title>Disk-based compression of data from genome sequencing</article-title>
<source>Bioinformatics</source>
<year>2015</year>
<volume>31</volume>
<issue>9</issue>
<fpage>1389</fpage>
<lpage>95</lpage>
<pub-id pub-id-type="pmid">25536966</pub-id>
</element-citation>
</ref>
<ref id="CR10"><label>10</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Hach</surname>
<given-names>F</given-names>
</name>
<name><surname>Numanagić</surname>
<given-names>I</given-names>
</name>
<name><surname>Alkan</surname>
<given-names>C</given-names>
</name>
<name><surname>Sahinalp</surname>
<given-names>SC</given-names>
</name>
</person-group>
<article-title>Scalce: boosting sequence compression algorithms using locally consistent encoding</article-title>
<source>Bioinformatics</source>
<year>2012</year>
<volume>28</volume>
<issue>23</issue>
<fpage>3051</fpage>
<lpage>7</lpage>
<pub-id pub-id-type="pmid">23047557</pub-id>
</element-citation>
</ref>
<ref id="CR11"><label>11</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Greenfield</surname>
<given-names>DL</given-names>
</name>
<name><surname>Stegle</surname>
<given-names>O</given-names>
</name>
<name><surname>Rrustemi</surname>
<given-names>A</given-names>
</name>
</person-group>
<article-title>GeneCodeq: quality score compression and improved genotyping using a Bayesian framework</article-title>
<source>Bioinformatics (Oxford, England)</source>
<year>2016</year>
<volume>32</volume>
<issue>20</issue>
<fpage>3124</fpage>
<lpage>32</lpage>
</element-citation>
</ref>
<ref id="CR12"><label>12</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Yu</surname>
<given-names>YW</given-names>
</name>
<name><surname>Yorukoglu</surname>
<given-names>D</given-names>
</name>
<name><surname>Peng</surname>
<given-names>J</given-names>
</name>
<name><surname>Berger</surname>
<given-names>B</given-names>
</name>
</person-group>
<article-title>Quality score compression improves genotyping accuracy</article-title>
<source>Nat Biotechnol</source>
<year>2015</year>
<volume>33</volume>
<issue>3</issue>
<fpage>240</fpage>
<lpage>3</lpage>
<pub-id pub-id-type="pmid">25748910</pub-id>
</element-citation>
</ref>
<ref id="CR13"><label>13</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Bonfield</surname>
<given-names>James K.</given-names>
</name>
<name><surname>Mahoney</surname>
<given-names>Matthew V.</given-names>
</name>
</person-group>
<article-title>Compression of FASTQ and SAM Format Sequencing Data</article-title>
<source>PLoS ONE</source>
<year>2013</year>
<volume>8</volume>
<issue>3</issue>
<fpage>e59190</fpage>
<pub-id pub-id-type="pmid">23533605</pub-id>
</element-citation>
</ref>
<ref id="CR14"><label>14</label>
<mixed-citation publication-type="other">Quality scores for next-generation sequencing, illumina inc.Technical report. 2011.</mixed-citation>
</ref>
<ref id="CR15"><label>15</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Cánovas</surname>
<given-names>R</given-names>
</name>
<name><surname>Moffat</surname>
<given-names>A</given-names>
</name>
<name><surname>Turpin</surname>
<given-names>A</given-names>
</name>
</person-group>
<article-title>Lossy compression of quality scores in genomic data</article-title>
<source>Bioinformatics</source>
<year>2014</year>
<volume>30</volume>
<issue>15</issue>
<fpage>2130</fpage>
<lpage>6</lpage>
<pub-id pub-id-type="pmid">24728856</pub-id>
</element-citation>
</ref>
<ref id="CR16"><label>16</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Ochoa</surname>
<given-names>I</given-names>
</name>
<name><surname>Asnani</surname>
<given-names>H</given-names>
</name>
<name><surname>Bharadia</surname>
<given-names>D</given-names>
</name>
<name><surname>Chowdhury</surname>
<given-names>M</given-names>
</name>
<name><surname>Weissman</surname>
<given-names>T</given-names>
</name>
<name><surname>Yona</surname>
<given-names>G</given-names>
</name>
</person-group>
<article-title>QualComp: a new lossy compressor for quality scores based on rate distortion theory</article-title>
<source>BMC Bioinformatics</source>
<year>2013</year>
<volume>14</volume>
<fpage>187</fpage>
<pub-id pub-id-type="pmid">23758828</pub-id>
</element-citation>
</ref>
<ref id="CR17"><label>17</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Ochoa</surname>
<given-names>I</given-names>
</name>
<name><surname>Hernaez</surname>
<given-names>M</given-names>
</name>
<name><surname>Goldfeder</surname>
<given-names>R</given-names>
</name>
<name><surname>Weissman</surname>
<given-names>T</given-names>
</name>
<name><surname>Ashley</surname>
<given-names>E</given-names>
</name>
</person-group>
<article-title>Effect of lossy compression of quality scores on variant calling</article-title>
<source>Brief Bioinform</source>
<year>2017</year>
<volume>18</volume>
<issue>2</issue>
<fpage>183</fpage>
<lpage>94</lpage>
<pub-id pub-id-type="pmid">26966283</pub-id>
</element-citation>
</ref>
<ref id="CR18"><label>18</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Janin</surname>
<given-names>L</given-names>
</name>
<name><surname>Rosone</surname>
<given-names>G</given-names>
</name>
<name><surname>Cox</surname>
<given-names>AJ</given-names>
</name>
</person-group>
<article-title>Adaptive reference-free compression of sequence quality scores</article-title>
<source>Bioinformatics</source>
<year>2014</year>
<volume>30</volume>
<issue>1</issue>
<fpage>24</fpage>
<lpage>30</lpage>
<pub-id pub-id-type="pmid">23661694</pub-id>
</element-citation>
</ref>
<ref id="CR19"><label>19</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Benoit</surname>
<given-names>G</given-names>
</name>
<name><surname>Lemaitre</surname>
<given-names>C</given-names>
</name>
<name><surname>Lavenier</surname>
<given-names>D</given-names>
</name>
<name><surname>Drezen</surname>
<given-names>E</given-names>
</name>
<name><surname>Dayris</surname>
<given-names>T</given-names>
</name>
<name><surname>Uricaru</surname>
<given-names>R</given-names>
</name>
<name><surname>Rizk</surname>
<given-names>G</given-names>
</name>
</person-group>
<article-title>Reference-free compression of high throughput sequencing data with a probabilistic de Bruijn graph</article-title>
<source>BMC Bioinformatics</source>
<year>2015</year>
<volume>16</volume>
<fpage>288</fpage>
<pub-id pub-id-type="pmid">26370285</pub-id>
</element-citation>
</ref>
<ref id="CR20"><label>20</label>
<element-citation publication-type="book"><person-group person-group-type="author"><name><surname>Yu</surname>
<given-names>YW</given-names>
</name>
<name><surname>Yorukoglu</surname>
<given-names>D</given-names>
</name>
<name><surname>Berger</surname>
<given-names>B</given-names>
</name>
</person-group>
<person-group person-group-type="editor"><name><surname>Sharan</surname>
<given-names>R</given-names>
</name>
</person-group>
<article-title>Traversing the k-mer landscape of ngs read datasets for quality score sparsification</article-title>
<source>Research in Computational Molecular Biology</source>
<year>2014</year>
<publisher-loc>Cham</publisher-loc>
<publisher-name>Springer</publisher-name>
</element-citation>
</ref>
<ref id="CR21"><label>21</label>
<mixed-citation publication-type="other">Burrows M, Wheeler DJ. A block-sorting lossless data compression algorithm. Technical report. 1994.</mixed-citation>
</ref>
<ref id="CR22"><label>22</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Comin</surname>
<given-names>M</given-names>
</name>
<name><surname>Schimd</surname>
<given-names>M</given-names>
</name>
</person-group>
<article-title>Assembly-free genome comparison based on next-generation sequencing reads and variable length patterns</article-title>
<source>BMC Bioinformatics</source>
<year>2014</year>
<volume>15</volume>
<issue>9</issue>
<fpage>1</fpage>
<lpage>10</lpage>
<pub-id pub-id-type="pmid">24383880</pub-id>
</element-citation>
</ref>
<ref id="CR23"><label>23</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Comin</surname>
<given-names>M</given-names>
</name>
<name><surname>Verzotto</surname>
<given-names>D</given-names>
</name>
</person-group>
<article-title>Beyond fixed-resolution alignment-free measures for mammalian enhancers sequence comparison</article-title>
<source>IEEE/ACM Trans Comput Biol Bioinforma</source>
<year>2014</year>
<volume>11</volume>
<issue>4</issue>
<fpage>628</fpage>
<lpage>37</lpage>
</element-citation>
</ref>
<ref id="CR24"><label>24</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Girotto</surname>
<given-names>S</given-names>
</name>
<name><surname>Comin</surname>
<given-names>M</given-names>
</name>
<name><surname>Pizzi</surname>
<given-names>C</given-names>
</name>
</person-group>
<article-title>Higher recall in metagenomic sequence classification exploiting overlapping reads</article-title>
<source>BMC Genomics</source>
<year>2017</year>
<volume>18</volume>
<issue>10</issue>
<fpage>917</fpage>
<pub-id pub-id-type="pmid">29244002</pub-id>
</element-citation>
</ref>
<ref id="CR25"><label>25</label>
<element-citation publication-type="book"><person-group person-group-type="author"><name><surname>Qian</surname>
<given-names>J</given-names>
</name>
<name><surname>Marchiori</surname>
<given-names>D</given-names>
</name>
<name><surname>Comin</surname>
<given-names>M</given-names>
</name>
</person-group>
<person-group person-group-type="editor"><name><surname>Peixoto</surname>
<given-names>N</given-names>
</name>
<name><surname>Silveira</surname>
<given-names>M</given-names>
</name>
<name><surname>Ali</surname>
<given-names>HH</given-names>
</name>
<name><surname>Maciel</surname>
<given-names>C</given-names>
</name>
<name><surname>van den Broek</surname>
<given-names>EL</given-names>
</name>
</person-group>
<article-title>Fast and sensitive classification of short metagenomic reads with skraken</article-title>
<source>Biomedical Engineering Systems and Technologies</source>
<year>2018</year>
<publisher-loc>Cham</publisher-loc>
<publisher-name>Springer</publisher-name>
</element-citation>
</ref>
<ref id="CR26"><label>26</label>
<element-citation publication-type="book"><person-group person-group-type="author"><name><surname>Shibuya</surname>
<given-names>Y</given-names>
</name>
<name><surname>Comin</surname>
<given-names>M</given-names>
</name>
</person-group>
<article-title>Indexing K-mers in Linear-space for Quality Value Compression</article-title>
<source>Proceedings of the 12th International Joint Conference on Biomedical Engineering Systems and Technologies - Volume 3: BIOINFORMATICS</source>
<year>2019</year>
<publisher-loc>Setúbal</publisher-loc>
<publisher-name>SciTePress</publisher-name>
</element-citation>
</ref>
<ref id="CR27"><label>27</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Li</surname>
<given-names>H</given-names>
</name>
<name><surname>Durbin</surname>
<given-names>R</given-names>
</name>
</person-group>
<article-title>Fast and accurate short read alignment with Burrows-Wheeler transform</article-title>
<source>Bioinformatics (Oxford, England)</source>
<year>2009</year>
<volume>25</volume>
<issue>14</issue>
<fpage>1754</fpage>
<lpage>60</lpage>
</element-citation>
</ref>
<ref id="CR28"><label>28</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Li</surname>
<given-names>H</given-names>
</name>
<name><surname>Durbin</surname>
<given-names>R</given-names>
</name>
</person-group>
<article-title>Fast and accurate long-read alignment with Burrows-Wheeler transform</article-title>
<source>Bioinformatics (Oxford, England)</source>
<year>2010</year>
<volume>26</volume>
<issue>5</issue>
<fpage>589</fpage>
<lpage>95</lpage>
</element-citation>
</ref>
<ref id="CR29"><label>29</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Marçais</surname>
<given-names>G</given-names>
</name>
<name><surname>Kingsford</surname>
<given-names>C</given-names>
</name>
</person-group>
<article-title>A fast, lock-free approach for efficient parallel counting of occurrences of k-mers</article-title>
<source>Bioinformatics</source>
<year>2011</year>
<volume>27</volume>
<issue>6</issue>
<fpage>764</fpage>
<lpage>70</lpage>
<pub-id pub-id-type="pmid">21217122</pub-id>
</element-citation>
</ref>
<ref id="CR30"><label>30</label>
<element-citation publication-type="book"><person-group person-group-type="author"><name><surname>Ferragina</surname>
<given-names>P</given-names>
</name>
<name><surname>Manzini</surname>
<given-names>G</given-names>
</name>
</person-group>
<article-title>Opportunistic Data Structures with Applications</article-title>
<source>Proceedings of the 41st Annual Symposium on Foundations of Computer Science. FOCS ’00</source>
<year>2000</year>
<publisher-loc>Washington</publisher-loc>
<publisher-name>IEEE Computer Society</publisher-name>
</element-citation>
</ref>
<ref id="CR31"><label>31</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Ferragina</surname>
<given-names>P</given-names>
</name>
<name><surname>Manzini</surname>
<given-names>G</given-names>
</name>
</person-group>
<article-title>Indexing Compressed Text</article-title>
<source>J ACM</source>
<year>2005</year>
<volume>52</volume>
<issue>4</issue>
<fpage>552</fpage>
<lpage>81</lpage>
</element-citation>
</ref>
<ref id="CR32"><label>32</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Li</surname>
<given-names>H</given-names>
</name>
<name><surname>Durbin</surname>
<given-names>R</given-names>
</name>
</person-group>
<article-title>Fast and accurate short read alignment with burrows–wheeler transform</article-title>
<source>Bioinformatics</source>
<year>2009</year>
<volume>25</volume>
<issue>14</issue>
<fpage>1754</fpage>
<lpage>60</lpage>
<pub-id pub-id-type="pmid">19451168</pub-id>
</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 0002874 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Pmc/Corpus/biblio.hfd -nk 0002874 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Sante |area= MersV1 |flux= Pmc |étape= Corpus |type= RBID |clé= |texte= }}
![]() | This area was generated with Dilib version V0.6.33. | ![]() |