Links to Exploration step
Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Indel-correcting DNA barcodes for high-throughput sequencing</title>
<author><name sortKey="Hawkins, John A" sort="Hawkins, John A" uniqKey="Hawkins J" first="John A." last="Hawkins">John A. Hawkins</name>
<affiliation><nlm:aff id="aff1">Institute for Computational Engineering and Sciences,<institution>The University of Texas at Austin</institution>
, Austin,<addr-line>TX</addr-line>
78712;</nlm:aff>
</affiliation>
<affiliation><nlm:aff id="aff2">Department of Molecular Biosciences,<institution>The University of Texas at Austin</institution>
, Austin,<addr-line>TX</addr-line>
78712;</nlm:aff>
</affiliation>
<affiliation><nlm:aff id="aff3">Institute for Cellular and Molecular Biology,<institution>The University of Texas at Austin</institution>
, Austin,<addr-line>TX</addr-line>
78712;</nlm:aff>
</affiliation>
</author>
<author><name sortKey="Jones, Stephen K" sort="Jones, Stephen K" uniqKey="Jones S" first="Stephen K." last="Jones">Stephen K. Jones</name>
<affiliation><nlm:aff id="aff2">Department of Molecular Biosciences,<institution>The University of Texas at Austin</institution>
, Austin,<addr-line>TX</addr-line>
78712;</nlm:aff>
</affiliation>
<affiliation><nlm:aff id="aff3">Institute for Cellular and Molecular Biology,<institution>The University of Texas at Austin</institution>
, Austin,<addr-line>TX</addr-line>
78712;</nlm:aff>
</affiliation>
</author>
<author><name sortKey="Finkelstein, Ilya J" sort="Finkelstein, Ilya J" uniqKey="Finkelstein I" first="Ilya J." last="Finkelstein">Ilya J. Finkelstein</name>
<affiliation><nlm:aff id="aff2">Department of Molecular Biosciences,<institution>The University of Texas at Austin</institution>
, Austin,<addr-line>TX</addr-line>
78712;</nlm:aff>
</affiliation>
<affiliation><nlm:aff id="aff3">Institute for Cellular and Molecular Biology,<institution>The University of Texas at Austin</institution>
, Austin,<addr-line>TX</addr-line>
78712;</nlm:aff>
</affiliation>
<affiliation><nlm:aff id="aff4">Center for Systems and Synthetic Biology,<institution>The University of Texas at Austin</institution>
, Austin,<addr-line>TX</addr-line>
78712;</nlm:aff>
</affiliation>
</author>
<author><name sortKey="Press, William H" sort="Press, William H" uniqKey="Press W" first="William H." last="Press">William H. Press</name>
<affiliation><nlm:aff id="aff1">Institute for Computational Engineering and Sciences,<institution>The University of Texas at Austin</institution>
, Austin,<addr-line>TX</addr-line>
78712;</nlm:aff>
</affiliation>
<affiliation><nlm:aff id="aff3">Institute for Cellular and Molecular Biology,<institution>The University of Texas at Austin</institution>
, Austin,<addr-line>TX</addr-line>
78712;</nlm:aff>
</affiliation>
<affiliation><nlm:aff id="aff5">Department of Integrative Biology,<institution>The University of Texas at Austin</institution>
, Austin,<addr-line>TX</addr-line>
78712</nlm:aff>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">PMC</idno>
<idno type="pmid">29925596</idno>
<idno type="pmc">6142223</idno>
<idno type="url">http://www.ncbi.nlm.nih.gov/pmc/articles/PMC6142223</idno>
<idno type="RBID">PMC:6142223</idno>
<idno type="doi">10.1073/pnas.1802640115</idno>
<date when="2018">2018</date>
<idno type="wicri:Area/Pmc/Corpus">001128</idno>
<idno type="wicri:explorRef" wicri:stream="Pmc" wicri:step="Corpus" wicri:corpus="PMC">001128</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en" level="a" type="main">Indel-correcting DNA barcodes for high-throughput sequencing</title>
<author><name sortKey="Hawkins, John A" sort="Hawkins, John A" uniqKey="Hawkins J" first="John A." last="Hawkins">John A. Hawkins</name>
<affiliation><nlm:aff id="aff1">Institute for Computational Engineering and Sciences,<institution>The University of Texas at Austin</institution>
, Austin,<addr-line>TX</addr-line>
78712;</nlm:aff>
</affiliation>
<affiliation><nlm:aff id="aff2">Department of Molecular Biosciences,<institution>The University of Texas at Austin</institution>
, Austin,<addr-line>TX</addr-line>
78712;</nlm:aff>
</affiliation>
<affiliation><nlm:aff id="aff3">Institute for Cellular and Molecular Biology,<institution>The University of Texas at Austin</institution>
, Austin,<addr-line>TX</addr-line>
78712;</nlm:aff>
</affiliation>
</author>
<author><name sortKey="Jones, Stephen K" sort="Jones, Stephen K" uniqKey="Jones S" first="Stephen K." last="Jones">Stephen K. Jones</name>
<affiliation><nlm:aff id="aff2">Department of Molecular Biosciences,<institution>The University of Texas at Austin</institution>
, Austin,<addr-line>TX</addr-line>
78712;</nlm:aff>
</affiliation>
<affiliation><nlm:aff id="aff3">Institute for Cellular and Molecular Biology,<institution>The University of Texas at Austin</institution>
, Austin,<addr-line>TX</addr-line>
78712;</nlm:aff>
</affiliation>
</author>
<author><name sortKey="Finkelstein, Ilya J" sort="Finkelstein, Ilya J" uniqKey="Finkelstein I" first="Ilya J." last="Finkelstein">Ilya J. Finkelstein</name>
<affiliation><nlm:aff id="aff2">Department of Molecular Biosciences,<institution>The University of Texas at Austin</institution>
, Austin,<addr-line>TX</addr-line>
78712;</nlm:aff>
</affiliation>
<affiliation><nlm:aff id="aff3">Institute for Cellular and Molecular Biology,<institution>The University of Texas at Austin</institution>
, Austin,<addr-line>TX</addr-line>
78712;</nlm:aff>
</affiliation>
<affiliation><nlm:aff id="aff4">Center for Systems and Synthetic Biology,<institution>The University of Texas at Austin</institution>
, Austin,<addr-line>TX</addr-line>
78712;</nlm:aff>
</affiliation>
</author>
<author><name sortKey="Press, William H" sort="Press, William H" uniqKey="Press W" first="William H." last="Press">William H. Press</name>
<affiliation><nlm:aff id="aff1">Institute for Computational Engineering and Sciences,<institution>The University of Texas at Austin</institution>
, Austin,<addr-line>TX</addr-line>
78712;</nlm:aff>
</affiliation>
<affiliation><nlm:aff id="aff3">Institute for Cellular and Molecular Biology,<institution>The University of Texas at Austin</institution>
, Austin,<addr-line>TX</addr-line>
78712;</nlm:aff>
</affiliation>
<affiliation><nlm:aff id="aff5">Department of Integrative Biology,<institution>The University of Texas at Austin</institution>
, Austin,<addr-line>TX</addr-line>
78712</nlm:aff>
</affiliation>
</author>
</analytic>
<series><title level="j">Proceedings of the National Academy of Sciences of the United States of America</title>
<idno type="ISSN">0027-8424</idno>
<idno type="eISSN">1091-6490</idno>
<imprint><date when="2018">2018</date>
</imprint>
</series>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass></textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en"><title>Significance</title>
<p>Modern high-throughput biological assays study pooled populations of individual members by labeling each member with a unique DNA sequence called a “barcode.” DNA barcodes are frequently corrupted by DNA synthesis and sequencing errors, leading to significant data loss and incorrect data interpretation. Here, we describe an error correction strategy to improve the efficiency and statistical power of DNA barcodes. Our strategy accurately handles insertions and deletions (indels) in DNA barcodes, the most common type of error encountered during DNA synthesis and sequencing, resulting in order-of-magnitude increases in accuracy, efficiency, and signal-to-noise ratio. The accompanying software package makes deployment of these barcodes straightforward for the broader experimental scientist community.</p>
</div>
</front>
<back><div1 type="bibliography"><listBibl><biblStruct><analytic><author><name sortKey="Klein, Am" uniqKey="Klein A">AM Klein</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Macosko, Ez" uniqKey="Macosko E">EZ Macosko</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Zheng, Gxy" uniqKey="Zheng G">GXY Zheng</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Kitzman, Jo" uniqKey="Kitzman J">JO Kitzman</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Haque, A" uniqKey="Haque A">A Haque</name>
</author>
<author><name sortKey="Engel, J" uniqKey="Engel J">J Engel</name>
</author>
<author><name sortKey="Teichmann, Sa" uniqKey="Teichmann S">SA Teichmann</name>
</author>
<author><name sortKey="Lonnberg, T" uniqKey="Lonnberg T">T Lönnberg</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Zilionis, R" uniqKey="Zilionis R">R Zilionis</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Spies, N" uniqKey="Spies N">N Spies</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Eroshenko, N" uniqKey="Eroshenko N">N Eroshenko</name>
</author>
<author><name sortKey="Kosuri, S" uniqKey="Kosuri S">S Kosuri</name>
</author>
<author><name sortKey="Marblestone, Ah" uniqKey="Marblestone A">AH Marblestone</name>
</author>
<author><name sortKey="Conway, N" uniqKey="Conway N">N Conway</name>
</author>
<author><name sortKey="Church, Gm" uniqKey="Church G">GM Church</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Plesa, C" uniqKey="Plesa C">C Plesa</name>
</author>
<author><name sortKey="Sidore, Am" uniqKey="Sidore A">AM Sidore</name>
</author>
<author><name sortKey="Lubock, Nb" uniqKey="Lubock N">NB Lubock</name>
</author>
<author><name sortKey="Zhang, D" uniqKey="Zhang D">D Zhang</name>
</author>
<author><name sortKey="Kosuri, S" uniqKey="Kosuri S">S Kosuri</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Fan, R" uniqKey="Fan R">R Fan</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Ma, C" uniqKey="Ma C">C Ma</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Zimmermann, G" uniqKey="Zimmermann G">G Zimmermann</name>
</author>
<author><name sortKey="Neri, D" uniqKey="Neri D">D Neri</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Melkko, S" uniqKey="Melkko S">S Melkko</name>
</author>
<author><name sortKey="Scheuermann, J" uniqKey="Scheuermann J">J Scheuermann</name>
</author>
<author><name sortKey="Dumelin, Ce" uniqKey="Dumelin C">CE Dumelin</name>
</author>
<author><name sortKey="Neri, D" uniqKey="Neri D">D Neri</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Kosuri, S" uniqKey="Kosuri S">S Kosuri</name>
</author>
<author><name sortKey="Church, Gm" uniqKey="Church G">GM Church</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Petrone, J" uniqKey="Petrone J">J Petrone</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Litovchick, A" uniqKey="Litovchick A">A Litovchick</name>
</author>
</analytic>
</biblStruct>
<biblStruct></biblStruct>
<biblStruct><analytic><author><name sortKey="Peterson, Ww" uniqKey="Peterson W">WW Peterson</name>
</author>
<author><name sortKey="Weldon, Ej" uniqKey="Weldon E">EJ Weldon</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Macwilliams, Fj" uniqKey="Macwilliams F">FJ MacWilliams</name>
</author>
<author><name sortKey="Sloane, Nja" uniqKey="Sloane N">NJA Sloane</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Lyons, E" uniqKey="Lyons E">E Lyons</name>
</author>
<author><name sortKey="Sheridan, P" uniqKey="Sheridan P">P Sheridan</name>
</author>
<author><name sortKey="Tremmel, G" uniqKey="Tremmel G">G Tremmel</name>
</author>
<author><name sortKey="Miyano, S" uniqKey="Miyano S">S Miyano</name>
</author>
<author><name sortKey="Sugano, S" uniqKey="Sugano S">S Sugano</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Erlich, Y" uniqKey="Erlich Y">Y Erlich</name>
</author>
<author><name sortKey="Zielinski, D" uniqKey="Zielinski D">D Zielinski</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Levenshtein, Vi" uniqKey="Levenshtein V">VI Levenshtein</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Costea, Pi" uniqKey="Costea P">PI Costea</name>
</author>
<author><name sortKey="Lundeberg, J" uniqKey="Lundeberg J">J Lundeberg</name>
</author>
<author><name sortKey="Akan, P" uniqKey="Akan P">P Akan</name>
</author>
<author><name sortKey="Tag, Gd" uniqKey="Tag G">GD Tag</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Houghten, Sk" uniqKey="Houghten S">SK Houghten</name>
</author>
<author><name sortKey="Ashlock, D" uniqKey="Ashlock D">D Ashlock</name>
</author>
<author><name sortKey="Lenarz, J" uniqKey="Lenarz J">J Lenarz</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Quail, Ma" uniqKey="Quail M">MA Quail</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Hamming, Rw" uniqKey="Hamming R">RW Hamming</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Buschmann, T" uniqKey="Buschmann T">T Buschmann</name>
</author>
<author><name sortKey="Bystrykh, Lv" uniqKey="Bystrykh L">LV Bystrykh</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Lee, Df" uniqKey="Lee D">DF Lee</name>
</author>
<author><name sortKey="Lu, J" uniqKey="Lu J">J Lu</name>
</author>
<author><name sortKey="Chang, S" uniqKey="Chang S">S Chang</name>
</author>
<author><name sortKey="Loparo, Jj" uniqKey="Loparo J">JJ Loparo</name>
</author>
<author><name sortKey="Xie, Xs" uniqKey="Xie X">XS Xie</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Markham, Nr" uniqKey="Markham N">NR Markham</name>
</author>
<author><name sortKey="Zuker, M" uniqKey="Zuker M">M Zuker</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Van Zanten, Aj" uniqKey="Van Zanten A">AJ van Zanten</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">Proc Natl Acad Sci U S A</journal-id>
<journal-id journal-id-type="iso-abbrev">Proc. Natl. Acad. Sci. U.S.A</journal-id>
<journal-id journal-id-type="hwp">pnas</journal-id>
<journal-id journal-id-type="pmc">pnas</journal-id>
<journal-id journal-id-type="publisher-id">PNAS</journal-id>
<journal-title-group><journal-title>Proceedings of the National Academy of Sciences of the United States of America</journal-title>
</journal-title-group>
<issn pub-type="ppub">0027-8424</issn>
<issn pub-type="epub">1091-6490</issn>
<publisher><publisher-name>National Academy of Sciences</publisher-name>
</publisher>
</journal-meta>
<article-meta><article-id pub-id-type="pmid">29925596</article-id>
<article-id pub-id-type="pmc">6142223</article-id>
<article-id pub-id-type="publisher-id">201802640</article-id>
<article-id pub-id-type="doi">10.1073/pnas.1802640115</article-id>
<article-categories><subj-group subj-group-type="heading"><subject>PNAS Plus</subject>
</subj-group>
<subj-group subj-group-type="heading"><subject>Biological Sciences</subject>
<subj-group><subject>Cell Biology</subject>
</subj-group>
</subj-group>
<subj-group subj-group-type="heading"><subject>Physical Sciences</subject>
<subj-group><subject>Biophysics and Computational Biology</subject>
</subj-group>
</subj-group>
<series-title>PNAS Plus</series-title>
</article-categories>
<title-group><article-title>Indel-correcting DNA barcodes for high-throughput sequencing</article-title>
</title-group>
<contrib-group><contrib contrib-type="author"><name><surname>Hawkins</surname>
<given-names>John A.</given-names>
</name>
<xref ref-type="aff" rid="aff1"><sup>a</sup>
</xref>
<xref ref-type="aff" rid="aff2"><sup>b</sup>
</xref>
<xref ref-type="aff" rid="aff3"><sup>c</sup>
</xref>
</contrib>
<contrib contrib-type="author"><name><surname>Jones</surname>
<given-names>Stephen K.</given-names>
<suffix>Jr.</suffix>
</name>
<xref ref-type="aff" rid="aff2"><sup>b</sup>
</xref>
<xref ref-type="aff" rid="aff3"><sup>c</sup>
</xref>
</contrib>
<contrib contrib-type="author"><contrib-id contrib-id-type="orcid" authenticated="false">http://orcid.org/0000-0002-9371-2431</contrib-id>
<name><surname>Finkelstein</surname>
<given-names>Ilya J.</given-names>
</name>
<xref ref-type="aff" rid="aff2"><sup>b</sup>
</xref>
<xref ref-type="aff" rid="aff3"><sup>c</sup>
</xref>
<xref ref-type="aff" rid="aff4"><sup>d</sup>
</xref>
<xref ref-type="corresp" rid="cor1"><sup>1</sup>
</xref>
</contrib>
<contrib contrib-type="author"><name><surname>Press</surname>
<given-names>William H.</given-names>
</name>
<xref ref-type="aff" rid="aff1"><sup>a</sup>
</xref>
<xref ref-type="aff" rid="aff3"><sup>c</sup>
</xref>
<xref ref-type="aff" rid="aff5"><sup>e</sup>
</xref>
<xref ref-type="corresp" rid="cor1"><sup>1</sup>
</xref>
</contrib>
<aff id="aff1"><sup>a</sup>
Institute for Computational Engineering and Sciences,<institution>The University of Texas at Austin</institution>
, Austin,<addr-line>TX</addr-line>
78712;</aff>
<aff id="aff2"><sup>b</sup>
Department of Molecular Biosciences,<institution>The University of Texas at Austin</institution>
, Austin,<addr-line>TX</addr-line>
78712;</aff>
<aff id="aff3"><sup>c</sup>
Institute for Cellular and Molecular Biology,<institution>The University of Texas at Austin</institution>
, Austin,<addr-line>TX</addr-line>
78712;</aff>
<aff id="aff4"><sup>d</sup>
Center for Systems and Synthetic Biology,<institution>The University of Texas at Austin</institution>
, Austin,<addr-line>TX</addr-line>
78712;</aff>
<aff id="aff5"><sup>e</sup>
Department of Integrative Biology,<institution>The University of Texas at Austin</institution>
, Austin,<addr-line>TX</addr-line>
78712</aff>
</contrib-group>
<author-notes><corresp id="cor1"><sup>1</sup>
To whom correspondence may be addressed. Email: <email>ifinkelstein@cm.utexas.edu</email>
or <email>wpress@cs.utexas.edu</email>
.</corresp>
<fn fn-type="edited-by"><p>Contributed by William H. Press, May 25, 2018 (sent for review February 13, 2018; reviewed by Curtis G. Callan Jr., Olga G. Troyanskaya, and Jonathan S. Weissman)</p>
</fn>
<fn fn-type="con"><p>Author contributions: J.A.H., I.J.F., and W.H.P. designed research; J.A.H. and S.K.J. performed research; J.A.H. analyzed data; and J.A.H., S.K.J., I.J.F., and W.H.P. wrote the paper.</p>
</fn>
<fn fn-type="con"><p>Reviewers: C.G.C., Princeton University; O.G.T., Princeton University; and J.S.W., University of California, San Francisco.</p>
</fn>
</author-notes>
<pub-date pub-type="ppub"><day>3</day>
<month>7</month>
<year>2018</year>
</pub-date>
<pub-date pub-type="epub"><day>20</day>
<month>6</month>
<year>2018</year>
</pub-date>
<pub-date pub-type="pmc-release"><day>20</day>
<month>6</month>
<year>2018</year>
</pub-date>
<pmc-comment> PMC Release delay is 0 months and 0 days and was based on the . </pmc-comment>
<volume>115</volume>
<issue>27</issue>
<fpage>E6217</fpage>
<lpage>E6226</lpage>
<permissions><copyright-statement>Copyright © 2018 the Author(s). Published by PNAS.</copyright-statement>
<copyright-year>2018</copyright-year>
<license license-type="open-access" xlink:href="https://creativecommons.org/licenses/by-nc-nd/4.0/"><ali:license_ref specific-use="vor"></ali:license_ref>
<license-p>This open access article is distributed under <ext-link ext-link-type="uri" xlink:href="https://creativecommons.org/licenses/by-nc-nd/4.0/">Creative Commons Attribution-NonCommercial-NoDerivatives License 4.0 (CC BY-NC-ND)</ext-link>
.</license-p>
</license>
</permissions>
<self-uri xlink:title="pdf" xlink:href="pnas.201802640.pdf"></self-uri>
<abstract abstract-type="executive-summary"><title>Significance</title>
<p>Modern high-throughput biological assays study pooled populations of individual members by labeling each member with a unique DNA sequence called a “barcode.” DNA barcodes are frequently corrupted by DNA synthesis and sequencing errors, leading to significant data loss and incorrect data interpretation. Here, we describe an error correction strategy to improve the efficiency and statistical power of DNA barcodes. Our strategy accurately handles insertions and deletions (indels) in DNA barcodes, the most common type of error encountered during DNA synthesis and sequencing, resulting in order-of-magnitude increases in accuracy, efficiency, and signal-to-noise ratio. The accompanying software package makes deployment of these barcodes straightforward for the broader experimental scientist community.</p>
</abstract>
<abstract><p>Many large-scale, high-throughput experiments use DNA barcodes, short DNA sequences prepended to DNA libraries, for identification of individuals in pooled biomolecule populations. However, DNA synthesis and sequencing errors confound the correct interpretation of observed barcodes and can lead to significant data loss or spurious results. Widely used error-correcting codes borrowed from computer science (e.g., Hamming, Levenshtein codes) do not properly account for insertions and deletions (indels) in DNA barcodes, even though deletions are the most common type of synthesis error. Here, we present and experimentally validate filled/truncated right end edit (FREE) barcodes, which correct substitution, insertion, and deletion errors, even when these errors alter the barcode length. FREE barcodes are designed with experimental considerations in mind, including balanced guanine-cytosine (GC) content, minimal homopolymer runs, and reduced internal hairpin propensity. We generate and include lists of barcodes with different lengths and error correction levels that may be useful in diverse high-throughput applications, including >10<sup>6</sup>
single-error–correcting 16-mers that strike a balance between decoding accuracy, barcode length, and library size. Moreover, concatenating two or more FREE codes into a single barcode increases the available barcode space combinatorially, generating lists with >10<sup>15</sup>
error-correcting barcodes. The included software for creating barcode libraries and decoding sequenced barcodes is efficient and designed to be user-friendly for the general biology community.</p>
</abstract>
<kwd-group><kwd>DNA barcodes</kwd>
<kwd>error-correcting codes</kwd>
<kwd>information storage</kwd>
<kwd>massively parallel synthesis</kwd>
</kwd-group>
<funding-group><award-group id="gs1"><funding-source id="sp1">Welch Foundation<named-content content-type="funder-id">100000928</named-content>
</funding-source>
<award-id rid="sp1">F-1808</award-id>
<principal-award-recipient>Ilya J Finkelstein</principal-award-recipient>
</award-group>
<award-group id="gs2"><funding-source id="sp2">HHS | National Institutes of Health (NIH)<named-content content-type="funder-id">100000002</named-content>
</funding-source>
<award-id rid="sp2">GM120554 and GM124141</award-id>
<principal-award-recipient>Stephen K Jones</principal-award-recipient>
<principal-award-recipient>Ilya J Finkelstein</principal-award-recipient>
</award-group>
<award-group id="gs3"><funding-source id="sp3">HHS | National Institutes of Health (NIH)<named-content content-type="funder-id">100000002</named-content>
</funding-source>
<award-id rid="sp3">AG053051</award-id>
<principal-award-recipient>Stephen K Jones</principal-award-recipient>
<principal-award-recipient>Ilya J Finkelstein</principal-award-recipient>
</award-group>
</funding-group>
<counts><page-count count="10"></page-count>
</counts>
</article-meta>
</front>
<body><p content-type="flushleft">Many modern large-scale biology experiments use high-throughput DNA sequencing to study the behavior of individual biomolecules in pooled populations. These experiments encode the identity of individual members via DNA barcodes: short and unique DNA sequences that are coupled to each member in the population (<xref ref-type="fig" rid="fig01">Fig. 1<italic>A</italic>
</xref>
). DNA barcode-based identification is central to such diverse applications as single-cell genome and RNA sequencing (<xref rid="r1" ref-type="bibr">1</xref>
<xref rid="r2" ref-type="bibr"></xref>
<xref rid="r3" ref-type="bibr"></xref>
<xref rid="r4" ref-type="bibr"></xref>
<xref rid="r5" ref-type="bibr"></xref>
<xref rid="r6" ref-type="bibr"></xref>
–<xref rid="r7" ref-type="bibr">7</xref>
), gene synthesis (<xref rid="r8" ref-type="bibr">8</xref>
, <xref rid="r9" ref-type="bibr">9</xref>
), high-throughput antibody screens (<xref rid="r10" ref-type="bibr">10</xref>
, <xref rid="r11" ref-type="bibr">11</xref>
), and drug discovery (<xref rid="r12" ref-type="bibr">12</xref>
, <xref rid="r13" ref-type="bibr">13</xref>
). Such experiments have been enabled by recent breakthroughs in massively parallel, pooled DNA synthesis (<xref rid="r14" ref-type="bibr">14</xref>
, <xref rid="r15" ref-type="bibr">15</xref>
). For example, a recent study used DNA barcodes to discover small-molecule inhibitors of enzymes by screening ∼10<sup>8</sup>
small molecules. Each small molecule was attached to a unique set of three DNA barcodes. The highest affinity ligands were enriched via multiple rounds of selection and then identified via high-throughput sequencing of the attached barcodes (<xref rid="r16" ref-type="bibr">16</xref>
). The rapid growth of such methodologies in all areas of biomedicine requires the development of large pools (>10<sup>6</sup>
members) of unique DNA barcodes to identify individual members (e.g., cells, proteins, drugs) in heterogeneous ensembles.</p>
<fig id="fig01" fig-type="featured" orientation="portrait" position="float"><label>Fig. 1.</label>
<caption><p>Applications and error correction strategies of DNA barcodes. (<italic>A</italic>
) Illustrative examples of high-throughput sequencing assays that require large lists of error-correcting DNA barcodes. Barcodes are used to identify individual cells or molecules in pooled libraries (<xref rid="r1" ref-type="bibr">1</xref>
, <xref rid="r10" ref-type="bibr">10</xref>
, <xref rid="r13" ref-type="bibr">13</xref>
). (<italic>B</italic>
) Current strategies to correct synthesis and sequencing errors in DNA barcodes are confounded by indels. Hamming distance can only handle substitutions. Levenshtein distance is confounded by the fact that barcodes are prepended to other sequences of interest. Indels thus produce phantom Levenshtein distance errors when bases from the remaining DNA molecule shift into or out of the barcode window. (<italic>C</italic>
) Examples of FREE divergence (this work), given the actual edit history. Levenshtein (Lev) and Hamming distances are also shown for comparison. A substitution and insertion are correctly attributed as two edits by FREE divergence (first column). FREE divergence is a symmetrical function [i.e., <italic>FreeDiv(E, O)</italic>
= <italic>FreeDiv(O, E)</italic>
] (first and second columns). Different actual edit paths can result in the same observed sequence (second and third columns). Indels can have zero cost, particularly near the end of the barcode, where they can occasionally be undone by fill or truncation (fourth column). Edits past the barcode end can matter since the fill/truncation step happens only upon observation (fifth column). del., deletion; div., divergence; ins., insertion; sub., substitution; trunc., truncation.</p>
</caption>
<graphic id="gra1" xlink:href="pnas.1802640115fig01"></graphic>
</fig>
<p>Every assay with DNA barcodes is subject to errors introduced during DNA synthesis and sequencing. These errors decrease experimental power and accuracy by confounding the identity of individual biomolecules in the population. The most common DNA synthesis error is a single-base deletion (<xref ref-type="sec" rid="s1"><italic>Results</italic>
</xref>
). This is particularly challenging to decode because it causes a frameshift in all downstream sequencing. Substitutions and insertion errors are also common during massively parallel pooled oligonucleotide synthesis (<xref ref-type="sec" rid="s1"><italic>Results</italic>
</xref>
). Our own experimental results are consistent with manufacturer-advertised error rates of up to one per 200 nucleotides (nt) (<xref rid="r17" ref-type="bibr">17</xref>
). For 20-base pair (bp)-long barcodes with no error correction, this translates to a best-case scenario of 10% data lost or, worse, incorrectly interpreted. Next-generation sequencing also has error rates between 10<sup>−3</sup>
and 10<sup>−4</sup>
. This alone represents errors in ∼1% of our example 20-bp barcodes, which can be limiting for detection of rare events. These errors can be overcome through the use of error-correcting DNA barcodes: DNA sequences that can correctly identify the underlying individuals in a pooled experiment even in the presence of sequencing and synthesis errors.</p>
<p>Error-correcting barcodes must efficiently detect and correct all DNA sequencing and synthesis errors. Many current DNA barcode strategies repurpose error-correcting codes developed for computers (<xref rid="r18" ref-type="bibr">18</xref>
, <xref rid="r19" ref-type="bibr">19</xref>
), such as Hamming or Reed–Solomon codes, to DNA applications (<xref rid="r20" ref-type="bibr">20</xref>
, <xref rid="r21" ref-type="bibr">21</xref>
). Hamming distance (i.e., the number of substitutions between two sequences of equal length) is possibly the most used due to its simplicity. However, nearly all well-studied error-correcting codes developed in computer science, including the widely used Hamming codes, were not designed to handle insertions and deletions (indels), which are the most common errors in DNA synthesis. Such codes are generally used only to detect errors without correcting them, but even a single error (e.g., deletion) has the possibility of converting one barcode into another. Levenshtein codes, also known as edit codes, can theoretically account for all three types of common error (substitutions, insertions, and deletions), but only when the corrupted length of each barcode after errors is known (<xref rid="r22" ref-type="bibr">22</xref>
, <xref rid="r23" ref-type="bibr">23</xref>
). This is a critical limitation in real-world DNA barcode applications because errors can change the barcode length unpredictably, which leads to erroneous decoding of Levenshtein-based barcodes in the context of a longer read (<xref ref-type="fig" rid="fig01">Fig. 1<italic>B</italic>
</xref>
). As a workaround, Levenshtein codes can be used at twice the level of error correction as desired for a given application, for example, using a two-error–correcting code when a one-error–correcting code is desired, but this is inefficient and significantly decreases the number of valid barcodes for a given oligonucleotide length. In sum, existing DNA barcode strategies are unable to efficiently detect and decode real-world errors encountered during DNA synthesis and sequencing.</p>
<p>Here, we develop and experimentally validate error-correcting filled/truncated right end edit (FREE) barcodes. FREE barcodes can correct substitutions, insertions, and deletions even when the edited length of the barcode is unknown. These barcodes are designed with experimental considerations in mind, including balanced guanine-cytosine (GC) content, minimal homopolymer runs, and no self-complementarity of more than two bases to reduce internal hairpin propensity. We generate and include lists of barcodes with different lengths and error correction levels that may be broadly useful in diverse high-throughput applications. For each barcode set, we calculate hairpin melting temperatures that can be used to select subsets of barcodes to match experimental conditions. Our largest barcode list includes >10<sup>6</sup>
unique error-correcting barcodes usable in a single experiment. Moreover, appending two or more barcodes together combinatorially increases the total barcode set, producing >10<sup>9</sup>
–10<sup>12</sup>
unique error-correcting DNA barcodes. The included software for creating new barcode libraries and decoding/error-correcting observed barcodes is fast and efficient, decoding >120,000 barcodes per second with a single processor and is designed to be user-friendly for a broad biologist community.</p>
<sec sec-type="results" id="s1"><title>Results</title>
<sec id="s2"><title>Overview of FREE Divergence Codes.</title>
<p>After DNA synthesis and sequencing, a barcode of length <italic>n</italic>
can be altered, and is not guaranteed to end after exactly <italic>n</italic>
bases. Our goal is to design barcodes that can be unambiguously identified from the first <italic>n</italic>
bases of the sequenced read. To begin, we define a filled/truncated right-end <italic>m</italic>
-edit, hereafter written “FRE <italic>m</italic>
-edit,” of a DNA sequence of length <italic>n</italic>
to be the result of any <italic>m</italic>
-edits [substitutions (<italic>sub</italic>
), insertions (<italic>ins</italic>
), or deletions (<italic>del</italic>
)], followed by truncating or filling with any random bases on the right (as from the unknown downstream read) as necessary to return to original length <italic>n</italic>
(<xref ref-type="fig" rid="fig01">Fig. 1<italic>B</italic>
</xref>
). For any two DNA sequences <italic>X</italic>
and <italic>Y</italic>
of the same length, we define the FREE divergence between <italic>X</italic>
and <italic>Y</italic>
, written <italic>FreeDiv(X, Y)</italic>
, to be the minimum <italic>m</italic>
such that <italic>Y</italic>
is a FRE <italic>m</italic>
-edit of <italic>X</italic>
.</p>
<p><xref ref-type="fig" rid="fig01">Fig. 1<italic>C</italic>
</xref>
shows a typical example of how FREE divergence captures the actual number of barcode edits in the context of a longer read. An insertion has caused the final “T” to move out of the barcode window, but FREE divergence correctly accounts for its loss. FREE divergence is a symmetrical function [i.e., <italic>FreeDiv(X, Y) = FreeDiv(Y, X)</italic>
] (<xref ref-type="fig" rid="fig01">Fig. 1<italic>C</italic>
</xref>
). This is because reversing the edits and reversing the right-end fill or truncation step moves one from <italic>Y</italic>
back to <italic>X</italic>
in the same minimum number of steps (<ext-link ext-link-type="uri" xlink:href="http://www.pnas.org/lookup/suppl/doi:10.1073/pnas.1802640115/-/DCSupplemental" xlink:show="new"><italic>SI Appendix</italic>
</ext-link>
). FREE divergence is defined as the minimum number of steps between the expected and observed barcodes, but it is possible to accomplish the same transformation with more edits, for example, via the identity del + ins <italic>= sub</italic>
(<xref ref-type="fig" rid="fig01">Fig. 1<italic>C</italic>
</xref>
). Also, indels near the end of the sequence can result in a FREE divergence of zero if the inserted or filled bases match the truncated or deleted bases, respectively. While <xref ref-type="fig" rid="fig01">Fig. 1<italic>C</italic>
</xref>
shows this for deletions, inserting “GC” instead of deleting it results in the same sequenced barcode. Finally, we note that FREE divergence is not a metric, a mathematically precise term for distance, because edits outside the barcode window can lead to violation of the triangle inequality (<xref ref-type="fig" rid="fig01">Fig. 1<italic>C</italic>
</xref>
and <ext-link ext-link-type="uri" xlink:href="http://www.pnas.org/lookup/suppl/doi:10.1073/pnas.1802640115/-/DCSupplemental" xlink:show="new"><italic>SI Appendix</italic>
</ext-link>
). This requires us to use specialized code generation techniques that do not rely on the properties of a metric, and also underlies usage of the term “divergence” rather than “distance” throughout this work.</p>
<p>With FREE divergence defined, building an error-correcting barcode list is conceptually equivalent to packing spheres in the space of possible barcodes (<xref ref-type="fig" rid="fig02">Fig. 2<italic>A</italic>
</xref>
). We set a barcode length <italic>n</italic>
and call any DNA sequence of length <italic>n</italic>
a word. For any word <italic>B</italic>
, we call the set of all words <italic>W</italic>
such that <italic>FreeDiv(B, W)</italic>
≤ <italic>m</italic>
, the <italic>m</italic>
-error decode sphere of <italic>B</italic>
, written as <italic>DecodeSphere</italic>
<sub><italic>m</italic>
</sub>
<italic>(B)</italic>
, or just <italic>DecodeSphere(B)</italic>
if <italic>m</italic>
is clear from context. Any observed DNA sequence within <italic>DecodeSphere(B)</italic>
will, by definition, decode to (error-correct to) the center word <italic>B</italic>
(<xref ref-type="fig" rid="fig02">Fig. 2<italic>A</italic>
</xref>
). Then, an <italic>m</italic>
-error–correcting FREE code is simply any set of barcodes such that the <italic>m</italic>
-error decode spheres of all barcodes are disjoint (i.e., no two decode spheres overlap). Any corrupted barcode with up to <italic>m</italic>
errors is thus in the decode sphere of exactly one barcode and can be decoded (error-corrected) uniquely (<xref ref-type="fig" rid="fig02">Fig. 2<italic>A</italic>
</xref>
). Requiring disjoint decode spheres places a limit on the relationship between allowed <italic>m</italic>
, the number of correctable errors, and <italic>n</italic>
, the barcode length: To fit more than one nonoverlapping decode sphere in the space requires that 2 <italic>m</italic>
+ 1 ≤ <italic>n</italic>
(<ext-link ext-link-type="uri" xlink:href="http://www.pnas.org/lookup/suppl/doi:10.1073/pnas.1802640115/-/DCSupplemental" xlink:show="new"><italic>SI Appendix</italic>
</ext-link>
).</p>
<fig id="fig02" fig-type="figure" orientation="portrait" position="float"><label>Fig. 2.</label>
<caption><p>FREE barcode generation and decoding. (<italic>A</italic>
) Error-correcting barcode generation is a sphere-packing problem. Around each accepted barcode <italic>B</italic>
(e.g., “CTCA”), we reserve <italic>DecodeSphere</italic>
<sub><italic>m</italic>
</sub>
<italic>(B)</italic>
, the set of all sequences within FREE divergence <italic>m</italic>
of <italic>B</italic>
; that is, the set of all sequences with any combination of up to <italic>m</italic>
errors from <italic>B</italic>
, followed by fill or truncation as necessary. (<italic>Right</italic>
) Any set of disjoint decode spheres is a valid FREE code. (<italic>B</italic>
) Number of single- and double-error correction barcodes generated for a range of barcode lengths. (<italic>C</italic>
) Accompanying software decodes more than 120,000 barcodes per second for all barcode lengths considered here. (<italic>D</italic>
) Comparison of FREE barcode counts against pruned Hamming codes and Levenshtein codes. Hamming codes were pruned to remove members that did not decode FREE divergence errors, while Levenshtein codes were produced at double the error correction levels for the same purpose. FREE codes produce more barcodes than either of the other methods for all barcode lengths.</p>
</caption>
<graphic id="gra2" xlink:href="pnas.1802640115fig02"></graphic>
</fig>
</sec>
<sec id="s3"><title>Efficient FREE Barcode Generation and Decoding.</title>
<p>A software library accompanying this paper efficiently generates FREE barcodes with a given total length and error correction level. The generation algorithm is conceptually very simple: Iterate through the space of <italic>n</italic>
-mers alphabetically, find the decode sphere for each candidate barcode, and reserve barcodes whose decode spheres do not overlap the decode spheres of any previously reserved barcodes (<xref ref-type="fig" rid="fig02">Fig. 2<italic>A</italic>
</xref>
). This set of reserved barcodes, by definition, forms a valid FREE code. Additional algorithmic details make the process faster and more memory-efficient (<xref ref-type="sec" rid="s8"><italic>Methods</italic>
</xref>
). Adding valid code words in alphabetical order is a heuristic method previously observed to efficiently pack spheres (<xref rid="r24" ref-type="bibr">24</xref>
). Experimental synthesis and sequencing limitations are also incorporated during barcode selection. Candidate barcodes must have the following: (<italic>i</italic>
) balanced GC content (40–60%), (<italic>ii</italic>
) no homopolymer triples (e.g., AAA), (<italic>iii</italic>
) no GGC [a known Illumina-based error motif (<xref rid="r25" ref-type="bibr">25</xref>
)], and (<italic>iv</italic>
) no self-complementarity of greater than two bases to reduce hairpin propensity. All of our software is available in the GitHub repository accompanying this paper (<ext-link ext-link-type="uri" xlink:href="http://github.com/finkelsteinlab/freebarcodes" xlink:show="new">github.com/finkelsteinlab/freebarcodes</ext-link>
).</p>
<p>The number of available error-correcting barcodes for a DNA sequence of length <italic>n</italic>
will depend on the experimentally required degree of error correction (<xref ref-type="fig" rid="fig02">Fig. 2<italic>B</italic>
</xref>
). We generated libraries of single-error–correcting codes up to a 16-nt length, containing >1,600,000 barcodes. In addition, we generated more robust, double-error–correcting codes up to a 17-nt length with >23,000 unique members (<ext-link ext-link-type="uri" xlink:href="http://www.pnas.org/lookup/suppl/doi:10.1073/pnas.1802640115/-/DCSupplemental" xlink:show="new"><italic>SI Appendix</italic>
, Table S1</ext-link>
). Barcodes correcting <italic>m</italic>
errors require a length of at least 2<italic>m</italic>
+ 1 bp because, otherwise, all decode spheres overlap all other decode spheres (<ext-link ext-link-type="uri" xlink:href="http://www.pnas.org/lookup/suppl/doi:10.1073/pnas.1802640115/-/DCSupplemental" xlink:show="new"><italic>SI Appendix</italic>
</ext-link>
). Thus, the one-error–correcting and two-error–correcting barcode libraries have minimum lengths of 3 bp and 5 bp, respectively. All single-error–correcting and double-error–correcting barcode libraries shown in <xref ref-type="fig" rid="fig02">Fig. 2<italic>B</italic>
</xref>
are included as supporting information (<ext-link ext-link-type="uri" xlink:href="http://www.pnas.org/lookup/suppl/doi:10.1073/pnas.1802640115/-/DCSupplemental" xlink:show="new">Dataset S1</ext-link>
) and are available in the GitHub repository (<ext-link ext-link-type="uri" xlink:href="http://github.com/finkelsteinlab/freebarcodes" xlink:show="new">github.com/finkelsteinlab/freebarcodes</ext-link>
). The barcode decoding software runs in time proportional to the length of the barcodes but constant with respect to the number of barcodes in the library. Hence, one-error–correcting and two-error–correcting codes decode at the same speed for a given barcode length even though the one-error libraries contain many more barcodes (<xref ref-type="fig" rid="fig02">Fig. 2<italic>C</italic>
</xref>
). Even the slowest decodes considered here, the 17-mer double-error correction barcodes, decode at >120,000 barcodes per second on a desktop computer using a single processor.</p>
</sec>
<sec id="s4"><title>Comparison with Current Error-Correcting DNA Barcode Strategies.</title>
<p>Current state-of-the art error-correcting DNA barcoding applications often use Hamming or Levenshtein error correction strategies (<xref rid="r20" ref-type="bibr">20</xref>
, <xref rid="r23" ref-type="bibr">23</xref>
). Hamming codes only correct substitutions, and are thus insufficient for any DNA barcode applications with indels (<xref rid="r26" ref-type="bibr">26</xref>
). However, they are linear codes, meaning the code words form a well-structured lattice in barcode space. We tested an alternative hypothesis that pruning these well-packed Hamming decode spheres to subsets with disjoint <italic>FreeDiv</italic>
decode spheres could result in a more efficient packing (more barcodes for a given barcode length) than our alphabetical generation strategy. This was not, in fact, the case: FREE codes have about a factor of two more barcodes for a given length than our best pruning of Hamming codes (<xref ref-type="fig" rid="fig02">Fig. 2<italic>D</italic>
</xref>
).</p>
<p>Levenshtein codes can be used directly (i.e., without pruning) because they account for indels, but they must be used at a twofold higher error correction for DNA barcode applications (<xref ref-type="fig" rid="fig01">Fig. 1<italic>B</italic>
</xref>
). We generated such overcorrected Levenshtein barcode sets in a manner similar to the FREE code generation strategy. This strategy produced even fewer barcodes than the pruned Hamming code sets (<xref ref-type="sec" rid="s8"><italic>Methods</italic>
</xref>
and <xref ref-type="fig" rid="fig02">Fig. 2<italic>D</italic>
</xref>
). Sequence-Levenshtein codes attempted to solve the problems inherent in using Levenshtein codes for DNA applications, but an error in the derivation of these codes (<xref rid="r27" ref-type="bibr">27</xref>
) often causes the decode spheres to overlap, resulting in wrong barcode decodings (<ext-link ext-link-type="uri" xlink:href="http://www.pnas.org/lookup/suppl/doi:10.1073/pnas.1802640115/-/DCSupplemental" xlink:show="new"><italic>SI Appendix</italic>
</ext-link>
). In sum, FREE codes offer a substantially larger number of usable barcodes for a given barcode length when taking into consideration real-world errors such as the deletions, insertions, and substitutions that are encountered during DNA sequencing and synthesis.</p>
</sec>
<sec id="s5"><title>Error Correction in Real and Simulated Data.</title>
<p>We validated FREE barcodes generated in this study by both numerical simulation and experiment. Pooled oligonucleotide synthesis was used to produce a library of >8,000 oligos with double-error–correcting barcodes at both ends (<xref ref-type="fig" rid="fig03">Fig. 3<italic>A</italic>
</xref>
). The barcodes were arranged such that each left barcode should only ever be observed on the same oligo with one specific right barcode sequence, and similarly for right barcodes. Hence, we were able to measure the rate of incorrectly decoding barcodes from observing unexpected left-right barcode pairs (<xref ref-type="sec" rid="s8"><italic>Methods</italic>
</xref>
). We sequenced 1.4 million copies of this library on an Illumina MiSeq instrument for an average coverage of 159-fold using the standard Illumina workflow.</p>
<fig id="fig03" fig-type="figure" orientation="portrait" position="float"><label>Fig. 3.</label>
<caption><p>Experimental measurement of synthesis and sequencing error rates. (<italic>A</italic>
) Schematic of the DNA constructs used for barcode validation experiments. Each member in the synthetic library had a unique pair of left and right barcodes (green) drawn from a list of >8,000 17-nt FREE codes with double-error correction. By using the primer regions (brown) to distinguish the left and right ends from one another, we could determine whether the barcodes were correctly decoded (matching) or incorrectly decoded (mismatching). (<italic>B</italic>
) Synthesis error rates measured in this experiment, by intended reference base and error type: substitution (Sub), deletion (Del), and insertion (Ins). (<italic>C</italic>
) Measured sequencing substitution error rates by reference base. Indels from Illumina sequencing are extremely rare and are omitted for clarity.</p>
</caption>
<graphic id="gra3" xlink:href="pnas.1802640115fig03"></graphic>
</fig>
<p>Full-length, paired-end Illumina sequencing was used to measure the background synthesis and sequencing error rates (<xref ref-type="fig" rid="fig03">Fig. 3 <italic>B</italic>
and <italic>C</italic>
</xref>
). Using full-length, paired-end reads permitted discrimination between synthesis and sequencing errors (<xref ref-type="sec" rid="s8"><italic>Methods</italic>
</xref>
). Substitution, insertion, and deletion error rates from library amplification using Q5 polymerase have previously been reported to occur at rates less than 10<sup>−5</sup>
, and thus are a negligible fraction of the measured synthesis errors (<xref rid="r28" ref-type="bibr">28</xref>
). Measured errors were dominated by single-base synthesis deletions, which occurred at rates of ∼1 in 200 bp and ∼1 in 100 bp in the left and right barcode regions, respectively (<xref ref-type="fig" rid="fig03">Fig. 3<italic>B</italic>
</xref>
and <ext-link ext-link-type="uri" xlink:href="http://www.pnas.org/lookup/suppl/doi:10.1073/pnas.1802640115/-/DCSupplemental" xlink:show="new"><italic>SI Appendix</italic>
, Fig. S7</ext-link>
). The twofold difference in synthesis error rates between the two sides is consistent with the synthesis error rates reported by the manufacturer (<xref rid="r17" ref-type="bibr">17</xref>
). Sequencing error rates are between 10<sup>−4</sup>
and 10<sup>−3</sup>
, as advertised by Illumina (<xref ref-type="fig" rid="fig03">Fig. 3<italic>C</italic>
</xref>
). In sum, experimental error rates are dominated by deletion errors. As Hamming codes are not designed to error-correct deletions in barcodes, they will perform very poorly in DNA-based experiments.</p>
<p>We compared the experimentally determined error rates with simulations of the overall decoding error rate (i.e., the probability of incorrectly demultiplexing a barcode). Simulations were used to analyze the decode error rate for several error-correcting codes as a function of the per-base error rate, <italic>p</italic>
<sub><italic>err</italic>
</sub>
(<xref ref-type="fig" rid="fig04">Fig. 4</xref>
). Simulations were performed in two different ways. First, we used a binomial model, which assumes independent and identically distributed errors at each base, to calculate the probability of observing more than one or two errors given per-base <italic>p</italic>
<sub><italic>err</italic>
</sub>
. Second, we directly simulated the errors directly using our decoding software: For a given per-base <italic>p</italic>
<sub><italic>err</italic>
</sub>
, we randomly select barcodes and add errors with probability <italic>p</italic>
<sub><italic>err</italic>
</sub>
. For simplicity, insertion, deletion, and substitution error rates were modeled as <italic>p</italic>
<sub><italic>err</italic>
</sub>
/3 with no correlation between individual errors within a given barcode. The corrupted barcodes are then decoded using our software, and the fraction of incorrectly decoded barcodes is used as a measure of the decode error rate.</p>
<fig id="fig04" fig-type="figure" orientation="portrait" position="float"><label>Fig. 4.</label>
<caption><p>Decoding corrupted barcodes from simulated errors. Modeled and simulated decoding error rates given the per-base error rate for length 8 (<italic>A</italic>
) and length 16 (<italic>B</italic>
) barcodes. Barcode sets are labeled according to length and number of errors corrected; for example, the 16-2 code is length 16 and corrects up to two errors. Solid lines show the error rate approximations using a binomial model. Circles and triangles show direct simulation error rates for single- and double-error–correcting codes, respectively. Substitution, insertion, and deletion errors each have a simulated error rate <italic>P(error per base)</italic>
/3 for simplicity.</p>
</caption>
<graphic id="gra4" xlink:href="pnas.1802640115fig04"></graphic>
</fig>
<p>At experimentally determined per-base error rates, <italic>p</italic>
<sub><italic>err</italic>
</sub>
, each increase in error correction level results in at least an order of magnitude improvement in the decoding error rate (<xref ref-type="fig" rid="fig04">Fig. 4</xref>
). For example, our experimental data showed an overall per-base <italic>p</italic>
<sub><italic>err</italic>
</sub>
of ∼10<sup>−2</sup>
(<xref ref-type="fig" rid="fig03">Fig. 3 <italic>B</italic>
and <italic>C</italic>
</xref>
). At this per-base error rate, the approximate uncorrected decode error rate (solid line) is 8% for length 8 barcodes and 15% for length 16 barcodes. Without error correction, a best-case scenario would be that these errors could be successfully filtered out, representing a significant loss of data. In other scenarios, these data might be erroneously counted. Error correction improves the decoding error rate significantly. For length 8 barcodes, the approximate decode error rate is 8% with zero-error correction, 0.3% with single-error correction, and 0.005% with double-error correction. For length 16 barcodes, the approximate decode error rate is 15% with zero-error correction, 1% with single-error correction, and 0.05% with double-error correction. A more comprehensive comparison of the various barcode lists is given in <ext-link ext-link-type="uri" xlink:href="http://www.pnas.org/lookup/suppl/doi:10.1073/pnas.1802640115/-/DCSupplemental" xlink:show="new"><italic>SI Appendix</italic>
, Figs. S3–S5</ext-link>
. The simulated results are consistently better than the binomial approximation because indels near the right end occasionally add the correct base and because insertions occasionally push other errors out of the barcode window (<ext-link ext-link-type="uri" xlink:href="http://www.pnas.org/lookup/suppl/doi:10.1073/pnas.1802640115/-/DCSupplemental" xlink:show="new"><italic>SI Appendix</italic>
, Fig. S2</ext-link>
).</p>
<p>We validated FREE barcodes by measuring the decoding error rates for the experimental dataset described earlier (<xref ref-type="fig" rid="fig05">Fig. 5</xref>
). For double-error correction, we used mismatches in barcode pairs to identify erroneously decoded barcodes (<xref ref-type="sec" rid="s8"><italic>Methods</italic>
</xref>
). After corrections, we observe error rates of 0.29% and 0.46% for left and right barcodes respectively. We counted the zero- and one-error correction rates shown in <xref ref-type="fig" rid="fig05">Fig. 5</xref>
by also counting the number of errors observed in each correctly decoded barcode. That is, zero-error correction decode error rates were calculated as the number of erroneously decoded barcodes plus the number of correctly decoded barcodes with one or two errors; one-error correction errors were counted similarly. On the other hand, the theoretical model was calculated using the synthesis and sequencing error rates found in <xref ref-type="fig" rid="fig03">Fig. 3</xref>
to calculate the decode error probability of each barcode depending on its base composition, and then combined for an overall error rate (<ext-link ext-link-type="uri" xlink:href="http://www.pnas.org/lookup/suppl/doi:10.1073/pnas.1802640115/-/DCSupplemental" xlink:show="new"><italic>SI Appendix</italic>
</ext-link>
).</p>
<fig id="fig05" fig-type="figure" orientation="portrait" position="float"><label>Fig. 5.</label>
<caption><p>Decoding corrupted barcodes from experimental data. Observed decoding error rates compared with theoretical rates from the synthesis and sequencing error rates.</p>
</caption>
<graphic id="gra5" xlink:href="pnas.1802640115fig05"></graphic>
</fig>
<p>The experimentally observed decoding error rates follow the same trend as the simulated errors: Decode error rates decrease by approximately an order of magnitude with each additional error correction level. We also observed that experimental error rates are higher than the theoretical error rate. This is explained by two observations. First, the theoretical model assumes independent errors at each position along the barcode. This assumption is not observed in the experimental data (<ext-link ext-link-type="uri" xlink:href="http://www.pnas.org/lookup/suppl/doi:10.1073/pnas.1802640115/-/DCSupplemental" xlink:show="new"><italic>SI Appendix</italic>
, Fig. S7</ext-link>
). Second, the starting position of each barcode may not be defined exactly because the primer region can have errors. We are careful to identify the start of each barcode as precisely as possible (<ext-link ext-link-type="uri" xlink:href="http://www.pnas.org/lookup/suppl/doi:10.1073/pnas.1802640115/-/DCSupplemental" xlink:show="new"><italic>SI Appendix</italic>
</ext-link>
), but any errors in starting position appear as spurious insertions or deletions during decoding. Nonetheless, even though per-base errors are not independent, the overall order-of-magnitude decrease in decode errors per error correction level is recapitulated in the experimental dataset.</p>
</sec>
<sec id="s6"><title>Combinatorially Large Barcode Lists via Concatenation.</title>
<p>State-of-the-art high-throughput sequencing applications already require >10<sup>6</sup>
unique barcodes (<xref rid="r16" ref-type="bibr">16</xref>
). We anticipate that improvements in high-density pooled oligo synthesis, along with the continuing reduction in sequencing costs, will continue to push the need for even larger error-correcting barcode sets. Below, we demonstrate that arbitrarily large barcode lists (>10<sup>15</sup>
unique members shown here) can be constructed from FREE barcodes by concatenating multiple FREE barcodes in a row.</p>
<p>As a demonstration, we concatenated two or three barcodes from the same starting list of subbarcodes (<xref ref-type="fig" rid="fig06">Fig. 6</xref>
). For the rest of this section, we will refer to the original barcodes as “subbarcodes,” while “barcode” will refer to the full-length, concatenated barcode. Due to the possibility of indels, the starting positions of the second and third subbarcodes are only known approximately, and that approximation worsens as more subbarcodes are added (<xref ref-type="fig" rid="fig06">Fig. 6<italic>A</italic>
</xref>
). Decoding the subbarcodes sequentially from left to right is a strategy to account for this ambiguity. The left-most subbarcode is decoded first, and the decoded subbarcode is then used to find the starting position of the next subbarcode. The error correction level of each FREE subbarcode remains the same, such that three concatenated double-error correction subbarcodes can each correct up to two errors for a maximum total of six corrected errors if the errors are evenly distributed, two per subbarcode. Overall concatenated barcode decoding error rates are given by the probability of any decoding error in any subbarcode or barcode. Concatenated barcode error rates are thus slightly higher than for the individual subbarcodes (<xref ref-type="fig" rid="fig06">Fig. 6<italic>B</italic>
</xref>
). The increased error rate of concatenated barcodes is due, in part, to errors in determining barcode boundaries, but direct simulation of decoding errors shows that this effect is relatively small (<xref ref-type="fig" rid="fig06">Fig. 6<italic>B</italic>
</xref>
). The decoding process is performed automatically using the software accompanying this paper.</p>
<fig id="fig06" fig-type="figure" orientation="portrait" position="float"><label>Fig. 6.</label>
<caption><p>Combinatorial barcode libraries via concatenation of FREE barcodes. (<italic>A</italic>
) Concatenated barcodes can be decoded sequentially in a left-to-right order, even when the end position of each edited subbarcode is not initially known. The decoded first FREE subbarcode can be used to find the starting position of the next subbarcode, and similarly for subsequent subbarcodes. (<italic>B</italic>
) Concatenated barcode decoding error rates. Concatenated barcode labels use the following format: a 3 × (16-1) barcode consists of three concatenated subbarcodes, each of which is 16 bp long and can correct up to one error. Lines indicate a binomial model. Points indicate direct simulation. (<italic>C</italic>
and <italic>D</italic>
) Concatenating multiple barcodes combinatorially increases the numbers of effective FREE barcodes. Concatenated barcodes can correct the same number of errors per subbarcode. When the errors are distributed evenly among the subbarcodes, concatenated barcodes can correct a higher total number of errors than the individual subbarcodes. (<italic>C</italic>
) Concatenated single-error–correcting barcodes. (<italic>D</italic>
) Concatenated double-error–correcting barcodes. Dashed lines indicate projected quantities calculated by sampling. Dotted lines indicate log-linear projections.</p>
</caption>
<graphic id="gra6" xlink:href="pnas.1802640115fig06"></graphic>
</fig>
<p>Concatenating FREE barcodes results in combinatorially large barcode sets that will be sufficient for even the most demanding high-throughput sequencing applications (<xref ref-type="fig" rid="fig06">Fig. 6</xref>
). The concatenated barcodes were pruned to remain compatible with experimental constraints by removing DNA sequences that had triplet repeats of a single base or excess self-complementarity (defined as any self-complementarity of any three or more bases). Even with these filters, we generated full lists of up to 10<sup>10</sup>
barcodes with concatenation of three single-error–correcting codes (<xref ref-type="fig" rid="fig06">Fig. 6</xref>
). Beyond that, where possible, the projected total barcode count was estimated via subsampling. When even that was limited by available hard drive space, the projected total was estimated via log-linear fit, which went above 10<sup>15</sup>
barcodes for 3 × (16-bp single-error) barcodes. Due to their size, we do not include these concatenated barcode sets explicitly with this paper. They can be generated on demand using the included software package and single barcode lists. In sum, concatenating FREE codes produces a rapid and efficient strategy for further increasing the size of error-correcting barcode lists for pooled high-throughput sequencing experiments.</p>
<p>Concatenated barcodes can also be used to significantly decrease error rates. The simplest such strategy is to consider <italic>r</italic>
concatenated repeats of each subbarcode as a complete barcode: For example, instead of using barcodes AAC and GGT, using repeated, concatenated barcodes AACAAC and GGTGGT. Any barcodes with mismatching decoded subbarcodes (AACGGT or GGTAAC in the previous example) are then filtered out. The decoding error probability is then the probability that all <italic>r</italic>
subbarcodes are not only wrong but are all erroneously decoded as the same wrong subbarcode. If <italic>p</italic>
is the probability of a subbarcode decoding error, then the full-length decoding error is <italic>qp</italic>
<sup><italic>r</italic>
</sup>
, where <italic>q</italic>
is the probability of <italic>r</italic>
wrong decodes all being the same wrong subbarcode (<ext-link ext-link-type="uri" xlink:href="http://www.pnas.org/lookup/suppl/doi:10.1073/pnas.1802640115/-/DCSupplemental" xlink:show="new"><italic>SI Appendix</italic>
, Fig. S8</ext-link>
). Meanwhile, the probability of filtering is approximately only <italic>rp</italic>
(<ext-link ext-link-type="uri" xlink:href="http://www.pnas.org/lookup/suppl/doi:10.1073/pnas.1802640115/-/DCSupplemental" xlink:show="new"><italic>SI Appendix</italic>
</ext-link>
). For example, two-error–correcting length 10 barcodes have an estimated decoding error probability, <italic>p</italic>
, of 10<sup>−4</sup>
at our observed per-base error rate of 10<sup>−2</sup>
. Using two or three repeats brings the decoding error probability down to an estimated 10<sup>−12</sup>
or 10<sup>−19</sup>
while only filtering out reads with a probability of <inline-formula><mml:math id="i1"><mml:mrow><mml:mn>2</mml:mn>
<mml:mo>×</mml:mo>
<mml:msup><mml:mrow><mml:mn>10</mml:mn>
</mml:mrow>
<mml:mrow><mml:mo>−</mml:mo>
<mml:mn>4</mml:mn>
</mml:mrow>
</mml:msup>
</mml:mrow>
</mml:math>
</inline-formula>
or <inline-formula><mml:math id="i2"><mml:mrow><mml:mn>3</mml:mn>
<mml:mo>×</mml:mo>
<mml:msup><mml:mrow><mml:mn>10</mml:mn>
</mml:mrow>
<mml:mrow><mml:mo>−</mml:mo>
<mml:mn>4</mml:mn>
</mml:mrow>
</mml:msup>
</mml:mrow>
</mml:math>
</inline-formula>
, respectively (<ext-link ext-link-type="uri" xlink:href="http://www.pnas.org/lookup/suppl/doi:10.1073/pnas.1802640115/-/DCSupplemental" xlink:show="new"><italic>SI Appendix</italic>
, Fig. S8</ext-link>
). Hence, concatenated FREE barcodes can be used for experiments requiring extremely low decoding error rates.</p>
</sec>
</sec>
<sec sec-type="discussion" id="s7"><title>Discussion</title>
<p content-type="flushleft">Here, we described the design and experimental validation of FREE error-correcting DNA barcodes capable of correcting substitution, insertion, and deletion errors, even when the corrupted length of the barcode is unknown. We generated lists of FREE divergence error-correcting barcodes and provided software on GitHub for user-friendly generation and decoding of these DNA barcodes for real-world applications.</p>
<p>Most high-throughput DNA sequencing applications require PCR-based amplification or reverse transcription (in the case of RNA) of the input nucleic acid libraries. The polymerase and reverse transcriptase enzymes used during library preparation perform best on libraries that avoid stable secondary structures and self-complimentary regions. To improve the utility of our codes for such demanding applications, we used UNAFold (<xref rid="r29" ref-type="bibr">29</xref>
) to calculate the melting temperature of hairpins for the FREE barcodes included with this paper (<ext-link ext-link-type="uri" xlink:href="http://www.pnas.org/lookup/suppl/doi:10.1073/pnas.1802640115/-/DCSupplemental" xlink:show="new">Dataset S1</ext-link>
). This information will allow users to prune out barcode sequences with a propensity to form stable hairpins in their specific experimental conditions (<ext-link ext-link-type="uri" xlink:href="http://www.pnas.org/lookup/suppl/doi:10.1073/pnas.1802640115/-/DCSupplemental" xlink:show="new"><italic>SI Appendix</italic>
, Fig. S9</ext-link>
). Such experimental considerations will further increase the utility of FREE codes for demanding high-throughput sequencing applications.</p>
<p>In validating the FREE barcodes, we measured the types and frequency of errors that are introduced during massively parallel oligo synthesis and Illumina-based high-throughput sequencing. We observed that deletions during synthesis were the most frequent sources of error (∼1 per 100 nt), followed by substitutions and insertions (∼1 per 1,000 nt). These experimentally measured error frequencies were used to simulate and experimentally measure the decoding quality of FREE codes. Even though the observed decoding error rates do not follow a model that assumes independent errors at each base, we still obtain exponential improvement of the final decoding error rate with codes that correct for increasing numbers of errors. Importantly, the error-correcting decode software runs fast enough to handle the massive datasets involved in modern high-throughput sequencing applications, decoding hundreds of thousands of barcodes per second on a single processor for all barcode lists considered.</p>
<p>In this paper we have focused on codes that fix a specified number of errors because such barcodes are platform-independent, and hence widely applicable. However, one can also use the FREE barcode method to produce barcodes with a desired total decode error probability instead of a maximum number of correctable errors. For example, if the rates of substitutions, deletions, and insertions for a given synthesis and sequencing pipeline are known, a user could choose to generate barcodes that have, say, a 10<sup>−6</sup>
probability of decode error. Instead of creating decode spheres by iterating over all barcodes with up to a chosen number of errors, one would iterate over the most likely erroneous barcodes until the total probability of the barcodes contained in the sphere is at least 1–10<sup>−6</sup>
. All other steps of the generation and decoding process would remain exactly the same. This strategy would be more efficient (i.e., produce more barcodes per barcode length) for a given desired decode error rate. The tradeoff is that this barcode set would be tied to a specific DNA synthesis and sequencing pipeline. As such, popular synthesis and sequencing pipelines may warrant their own dedicated barcodes in the future.</p>
<p>Furthermore, while we have focused exclusively on FREE codes prepended to the start of sequenced DNA reads, the current work applies equally to their natural mirrored counterpart, filled/truncated left end edit codes. This would be required for applications where the barcode appears at the end of each sequenced read rather than the beginning. In fact, the same codes can be used by simply taking the reverse complement of FREE codes before synthesis and again before decoding. Hence, FREE barcodes can be used equally well on the 5′ or 3′ end of pooled samples, as long as the orientation is chosen appropriately.</p>
<p>FREE barcodes are a powerful tool to correct DNA barcode errors, reducing measurement errors in modern high-throughput experiments. We anticipate that the use of FREE barcodes will improve these assays in three key ways: (<italic>i</italic>
) helping avoid spurious results, (<italic>ii</italic>
) decreasing the amount of discarded data, and (<italic>iii</italic>
) increasing experimental signal-to-noise ratios. Decreasing spurious results and decreasing discarded data are important for any experiment involving DNA barcodes, but we are most excited by the new possibilities available with increased signal-to-noise ratios. The power to decrease error rates from 15 to 0.05%, as in <xref ref-type="fig" rid="fig04">Fig. 4<italic>B</italic>
</xref>
, could open the door for entirely new assay designs. We anticipate that FREE barcodes will be broadly useful for the ever-growing set of pooled high-throughput sequencing experiments in cell and molecular biology, protein engineering, and drug discovery.</p>
</sec>
<sec sec-type="methods" id="s8"><title>Methods</title>
<sec id="s9"><title>Definitions and Numerical Representation of DNA.</title>
<p>For any barcode system, the word length, <italic>n,</italic>
is given. Any DNA sequence of length <italic>n</italic>
is a word, and any word observed in the data is an observed word.</p>
<p>We represent strings of DNA as base 4 numbers, where A, C, G, and T correspond to 0, 1, 2, and 3, respectively. Thus, for example,<disp-formula id="uneq1"><mml:math id="me1"><mml:mrow><mml:mtext>AAGCT</mml:mtext>
<mml:mo>=</mml:mo>
<mml:msub><mml:mrow><mml:mo>(</mml:mo>
<mml:mn>00213</mml:mn>
<mml:mo>)</mml:mo>
</mml:mrow>
<mml:mrow><mml:mtext>base</mml:mtext>
<mml:mn>4</mml:mn>
</mml:mrow>
</mml:msub>
<mml:mo>=</mml:mo>
<mml:mn>39</mml:mn>
<mml:mo> </mml:mo>
<mml:mtext>length</mml:mtext>
<mml:mo> </mml:mo>
<mml:mn>5</mml:mn>
<mml:mo>.</mml:mo>
</mml:mrow>
</mml:math>
</disp-formula>
</p>
<p content-type="flushleft">Here, 39 is the word number and 5 is the word length. Note that the word length is required to uniquely convert numbers to DNA to account for leading A’s. For example, the word number from the example above, 39, with word length 3 is simply GCT. For word length <italic>n</italic>
, the largest valid word number is 4<sup><italic>n</italic>
</sup>
− 1.</p>
<p>For an <italic>m</italic>
-error–correcting code, we define a decode sphere around a barcode <italic>B</italic>
to be the set of all words with <italic>FreeDiv</italic>
less than or equal to <italic>m,</italic>
and we define an encode sphere to be the set of all words of <italic>FreeDiv</italic>
less than or equal to 2<italic>m</italic>
. We write these as <italic>DecodeSphere(B)</italic>
and <italic>EncodeSphere(B)</italic>
.</p>
</sec>
<sec id="s10"><title>Barcode Generation.</title>
<p>FREE barcode sets are generated with a modified lexicographic code generation method. Lexicographic code generation consists of marching through all words lexicographically, alphabetically in this case, and adding new words to the list of barcodes whenever they are sufficiently far from all previous barcodes (<xref rid="r30" ref-type="bibr">30</xref>
). For Hamming codes, lexicographic codes are linear (<xref rid="r30" ref-type="bibr">30</xref>
), and, more generally, lexicographic code generation has been shown to have relatively good sphere-packing efficiency (<xref rid="r24" ref-type="bibr">24</xref>
). The first FREE modification to the procedure is to enforce the following sequencing and synthesis properties: (<italic>i</italic>
) balanced GC content (40–60%), (<italic>ii</italic>
) no homopolymer triples (e.g., TTT), (<italic>iii</italic>
) no triplet self-complementarity, and (<italic>iv</italic>
) no GGC [Illumina error motif (<xref rid="r25" ref-type="bibr">25</xref>
)].</p>
<p>For speed, we iterate over these potential barcodes via recursive base addition: Given a barcode prefix <italic>P</italic>
, we add the next base only if it does not violate any of the above. We thereby skip large recursive subtrees in which all words violate one of the above conditions.</p>
<p>For an <italic>m-</italic>
error–correcting code, the only requirement is that the decode spheres of all barcodes are disjoint. Because FREE divergence is not a metric, standard metric-based code generation methods cannot be used. Instead, we accomplish this directly with a sphere iterator (<ext-link ext-link-type="uri" xlink:href="http://www.pnas.org/lookup/suppl/doi:10.1073/pnas.1802640115/-/DCSupplemental" xlink:show="new"><italic>SI Appendix</italic>
</ext-link>
). For every accepted barcode <italic>B</italic>
, we iterate over <italic>DecodeSphere(B)</italic>
and reserve all words therein as mapping to <italic>B</italic>
. For any potential new barcode <italic>P</italic>
, we first verify that no words in <italic>DecodeSphere(P)</italic>
are reserved before accepting it as a new barcode.</p>
<p>This algorithm would be very slow because most decode sphere tests would run into reserved words and fail to add new barcodes. One further observation makes this process tractable. Given a barcode <italic>B</italic>
and a proposed new barcode <italic>W,</italic>
if <italic>FreeDiv(B, W)</italic>
≤ <italic>2m</italic>
, that is, if <italic>W</italic>
is in <italic>EncodeSphere(B)</italic>
, then <italic>DecodeSphere(W)</italic>
and <italic>DecodeSphere(B)</italic>
overlap and <italic>W</italic>
is not a valid new barcode (<ext-link ext-link-type="uri" xlink:href="http://www.pnas.org/lookup/suppl/doi:10.1073/pnas.1802640115/-/DCSupplemental" xlink:show="new"><italic>SI Appendix</italic>
</ext-link>
). This implies the following algorithm: Generate the code by lexicographically iterating over words while looking for new barcodes to add to the code. For each accepted new barcode <italic>B</italic>
, we color any uncolored words in <italic>EncodeSphere(B)</italic>
black, and we then color all words in <italic>DecodeSphere(B)</italic>
red. Restricting encode sphere coloring to previously uncolored words avoids overwriting the decode spheres of all previous barcodes. All black- and red-colored words are guaranteed to not be valid barcodes, so addition of new barcodes is restricted to uncolored words. For an uncolored proposed new barcode <italic>W</italic>
, <italic>DecodeSphere(W)</italic>
is checked for red words. If no red words are found, <italic>W</italic>
is added as a new barcode.</p>
<p>The coloring of barcodes, decode spheres, and encode spheres is accomplished by having an array of 4<sup><italic>n</italic>
</sup>
integers valued 0, 1, or 2: 0 for uncolored, 1 for black, and 2 for red. The location of each integer in memory itself represents the word, via the numerical representation of DNA given above. This is both memory- and speed-efficient. Memory efficiency is important, as it is a limiting resource for this method. The memory required for barcode generation is 4<sup><italic>k</italic>
</sup>
bytes, which was up to 16 Gb of random access memory (RAM) for this paper.</p>
</sec>
<sec id="s11"><title>Barcode Decoding.</title>
<p>The decoding process builds the code book and looks up decoded words directly. We do this in a memory-efficient fashion as follows. For each barcode in a list, the barcode index is defined as the index of that barcode within the list of barcodes. We again reserve a space of 4<sup><italic>k</italic>
</sup>
integers to represent the code space. For each barcode <italic>B</italic>
, we store the barcode index of <italic>B</italic>
at every word of <italic>DecodeSphere(B)</italic>
. We store barcode indices rather than barcode numbers because barcode indices require fewer bits per word. The memory required for barcode decoding is <inline-formula><mml:math id="i4"><mml:mrow><mml:mrow><mml:mo>(</mml:mo>
<mml:mn>1</mml:mn>
<mml:mo>,</mml:mo>
<mml:mn>2</mml:mn>
<mml:mo>,</mml:mo>
<mml:mtext>or</mml:mtext>
<mml:mo> </mml:mo>
<mml:mn>4</mml:mn>
<mml:mo>)</mml:mo>
</mml:mrow>
<mml:mo>×</mml:mo>
<mml:msup><mml:mn>4</mml:mn>
<mml:mi>n</mml:mi>
</mml:msup>
</mml:mrow>
</mml:math>
</inline-formula>
bytes, requiring one, two, or four bytes to store each barcode index. For this paper, the maximum memory used for barcode decoding was 32 Gb of RAM.</p>
</sec>
<sec id="s12"><title>Barcode Pruning.</title>
<p>Specific barcode lists from literature or elsewhere may sometimes be required for a given experiment, but require pruning to find a subset with error correction. We accomplish barcode pruning via the same strategy as barcode generation, but only considering the input set of barcodes as potential new barcodes. This pruning method was also used to prune the linear Hamming codes.</p>
</sec>
<sec id="s13"><title>Simulation of Errors.</title>
<p>To test the error-correcting capacity of FREE barcodes, we wrote error-simulating code, which adds a given number of substitutions, insertions, deletions, or all three randomly distributed. We used this to verify the correctness of each of the FREE <italic>m-</italic>
error–correcting codes by randomly selecting barcodes, adding <italic>m</italic>
errors, and verifying that the decoded word matches the expected word. We used the same code for generating <xref ref-type="fig" rid="fig04">Fig. 4</xref>
by randomly choosing the number of errors from a binomial distribution with probability of error <italic>p</italic>
<sub><italic>err</italic>
</sub>
.</p>
</sec>
<sec id="s14"><title>Levenshtein Barcodes.</title>
<p>Levenshtein barcodes were generated lexicographically using the standard technique of code generation with a metric. Briefly, for desired barcode length <italic>n</italic>
and number of correctable errors <italic>e,</italic>
we walk through the space of <italic>n</italic>
-mers lexicographically adding any new word if it (<italic>i</italic>
) satisfies the same sequencing and synthesis properties as above and (<italic>ii</italic>
) has a Levenshtein distance at least 2<italic>e</italic>
+ 1 from any previously accepted barcode.</p>
</sec>
<sec id="s15"><title>Pruned Linear Hamming Barcodes.</title>
<p>We generated Hamming barcode lists using linearity in base 4 (<ext-link ext-link-type="uri" xlink:href="http://www.pnas.org/lookup/suppl/doi:10.1073/pnas.1802640115/-/DCSupplemental" xlink:show="new"><italic>SI Appendix</italic>
</ext-link>
). Briefly, a Hamming code of length <italic>n</italic>
with <italic>k</italic>
< <italic>n</italic>
“message bits” can be generated by all linear combinations of <italic>k</italic>
basis vectors of length <italic>n</italic>
, which are chosen to enforce the error correction properties required. These codes were then filtered according to the FREE sequencing and synthesis property requirements and pruned as described above to form valid FREE codes.</p>
</sec>
<sec id="s16"><title>Experimental Synthesis, Sequencing, and Decoding Error Rates.</title>
<p>Oligonucleotide pools were designed as in <xref ref-type="fig" rid="fig03">Fig. 3<italic>A</italic>
</xref>
, with primers and barcodes on each end and a spacer in the middle (116-bp total length). To test the FREE method, 8,634 barcodes of length 17 and double-error correction were used in 8,634 unique pairs. Oligos were synthesized (CustomArray, Inc.), and the oligo pool was amplified for 20 cycles with Q5 polymerase (New England Biolabs) and sequenced on an Illumina MiSeq machine with 2 × 150-bp paired-end reads. Reads are available on the Sequence Read Archive under accession number SRP145011. Maximum likelihood sequences were inferred using both reads.</p>
<p>The left and right primer sequences were used to determine both the read orientation and the starting position of each barcode (<ext-link ext-link-type="uri" xlink:href="http://www.pnas.org/lookup/suppl/doi:10.1073/pnas.1802640115/-/DCSupplemental" xlink:show="new"><italic>SI Appendix</italic>
</ext-link>
). Each barcode was then decoded using the FREE decoding software. Matching barcodes identified correctly decoded barcodes, while mismatching barcodes indicated an error. The FREE method was powerful enough to reveal a surprising and unrelated source of error: the creation of oligo chimeras, sequences with the left part of one oligo and the right part of another, which we then also accounted for (<ext-link ext-link-type="uri" xlink:href="http://www.pnas.org/lookup/suppl/doi:10.1073/pnas.1802640115/-/DCSupplemental" xlink:show="new"><italic>SI Appendix</italic>
</ext-link>
).</p>
<p>Once each oligo had been identified from its barcodes, the observed sequence was aligned with the reference sequence. At each base where the two reads agreed with each other but not with the reference sequence, we counted a synthesis error; at each base where the reads disagreed and one read matched the reference sequence, we counted a sequencing error; and at each base where the reads disagreed and neither matched the reference sequence, we counted a synthesis error and a sequencing error.</p>
<p>Observed synthesis and sequencing error rates for each reference base were used to find theoretical decoding error rates for each barcode, given its base composition. These were then used to estimate the overall expected error rate (<ext-link ext-link-type="uri" xlink:href="http://www.pnas.org/lookup/suppl/doi:10.1073/pnas.1802640115/-/DCSupplemental" xlink:show="new"><italic>SI Appendix</italic>
</ext-link>
).</p>
</sec>
</sec>
<sec sec-type="supplementary-material"><title>Supplementary Material</title>
<supplementary-material content-type="local-data"><label>Supplementary File</label>
<media xlink:href="pnas.1802640115.sapp.pdf"></media>
</supplementary-material>
<supplementary-material content-type="local-data"><label>Supplementary File</label>
<media xlink:href="pnas.1802640115.sd01.csv"></media>
</supplementary-material>
</sec>
</body>
<back><ack><p>We thank James Rybarski, Andrea Hawkins-Daarud, Jeffrey Hussmann, Prakash Mohan, Alexander Boulgakov, and Kevin Drew for useful feedback throughout the project. This work was supported by a College of Natural Sciences Catalyst Award, the Welch Foundation (Grant F-1808 to I.J.F.), and the NIH (Grants R01 GM120554 and R01 GM124141 to I.J.F., Grant F32 AG053051 to S.K.J.).</p>
</ack>
<fn-group><fn fn-type="COI-statement"><p>The authors declare no conflict of interest.</p>
</fn>
<fn fn-type="other"><p>Data deposition: DNA barcode lists are provided as <ext-link ext-link-type="uri" xlink:href="http://www.pnas.org/lookup/suppl/doi:10.1073/pnas.1802640115/-/DCSupplemental" xlink:show="new">Dataset S1</ext-link>
. Raw sequenced reads have been deposited in the Sequence Read Archive (SRA), <ext-link ext-link-type="uri" xlink:href="http://www.ncbi.nlm.nih.gov/sra" xlink:show="new">http://www.ncbi.nlm.nih.gov/sra</ext-link>
(accession no. <ext-link ext-link-type="uri" xlink:href="http://www.ncbi.nlm.nih.gov/sra/SRP145011" xlink:show="new">SRP145011</ext-link>
). The software library has been deposited in the GitHub repository (<ext-link ext-link-type="uri" xlink:href="https://github.com/finkelsteinlab/freebarcodes" xlink:show="new">https://github.com/finkelsteinlab/freebarcodes</ext-link>
).</p>
</fn>
<fn fn-type="supplementary-material"><p>This article contains supporting information online at <ext-link ext-link-type="uri" xlink:href="http://www.pnas.org/lookup/suppl/doi:10.1073/pnas.1802640115/-/DCSupplemental" xlink:show="new">www.pnas.org/lookup/suppl/doi:10.1073/pnas.1802640115/-/DCSupplemental</ext-link>
.</p>
</fn>
</fn-group>
<ref-list><ref id="r1"><label>1</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name name-style="western"><surname>Klein</surname>
<given-names>AM</given-names>
</name>
<etal></etal>
</person-group>
<year>2015</year>
<article-title>Droplet barcoding for single-cell transcriptomics applied to embryonic stem cells</article-title>
<source>Cell</source>
<volume>161</volume>
<fpage>1187</fpage>
<lpage>1201</lpage>
<pub-id pub-id-type="pmid">26000487</pub-id>
</element-citation>
</ref>
<ref id="r2"><label>2</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name name-style="western"><surname>Macosko</surname>
<given-names>EZ</given-names>
</name>
<etal></etal>
</person-group>
<year>2015</year>
<article-title>Highly parallel genome-wide expression profiling of individual cells using nanoliter droplets</article-title>
<source>Cell</source>
<volume>161</volume>
<fpage>1202</fpage>
<lpage>1214</lpage>
<pub-id pub-id-type="pmid">26000488</pub-id>
</element-citation>
</ref>
<ref id="r3"><label>3</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name name-style="western"><surname>Zheng</surname>
<given-names>GXY</given-names>
</name>
<etal></etal>
</person-group>
<year>2016</year>
<article-title>Haplotyping germline and cancer genomes with high-throughput linked-read sequencing</article-title>
<source>Nat Biotechnol</source>
<volume>34</volume>
<fpage>303</fpage>
<lpage>311</lpage>
<pub-id pub-id-type="pmid">26829319</pub-id>
</element-citation>
</ref>
<ref id="r4"><label>4</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name name-style="western"><surname>Kitzman</surname>
<given-names>JO</given-names>
</name>
</person-group>
<year>2016</year>
<article-title>Haplotypes drop by drop</article-title>
<source>Nat Biotechnol</source>
<volume>34</volume>
<fpage>296</fpage>
<lpage>298</lpage>
<pub-id pub-id-type="pmid">26963554</pub-id>
</element-citation>
</ref>
<ref id="r5"><label>5</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name name-style="western"><surname>Haque</surname>
<given-names>A</given-names>
</name>
<name name-style="western"><surname>Engel</surname>
<given-names>J</given-names>
</name>
<name name-style="western"><surname>Teichmann</surname>
<given-names>SA</given-names>
</name>
<name name-style="western"><surname>Lönnberg</surname>
<given-names>T</given-names>
</name>
</person-group>
<year>2017</year>
<article-title>A practical guide to single-cell RNA-sequencing for biomedical research and clinical applications</article-title>
<source>Genome Med</source>
<volume>9</volume>
<fpage>75</fpage>
<pub-id pub-id-type="pmid">28821273</pub-id>
</element-citation>
</ref>
<ref id="r6"><label>6</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name name-style="western"><surname>Zilionis</surname>
<given-names>R</given-names>
</name>
<etal></etal>
</person-group>
<year>2017</year>
<article-title>Single-cell barcoding and sequencing using droplet microfluidics</article-title>
<source>Nat Protoc</source>
<volume>12</volume>
<fpage>44</fpage>
<lpage>73</lpage>
<pub-id pub-id-type="pmid">27929523</pub-id>
</element-citation>
</ref>
<ref id="r7"><label>7</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name name-style="western"><surname>Spies</surname>
<given-names>N</given-names>
</name>
<etal></etal>
</person-group>
<year>2017</year>
<article-title>Genome-wide reconstruction of complex structural variants using read clouds</article-title>
<source>Nat Methods</source>
<volume>14</volume>
<fpage>915</fpage>
<lpage>920</lpage>
<pub-id pub-id-type="pmid">28714986</pub-id>
</element-citation>
</ref>
<ref id="r8"><label>8</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name name-style="western"><surname>Eroshenko</surname>
<given-names>N</given-names>
</name>
<name name-style="western"><surname>Kosuri</surname>
<given-names>S</given-names>
</name>
<name name-style="western"><surname>Marblestone</surname>
<given-names>AH</given-names>
</name>
<name name-style="western"><surname>Conway</surname>
<given-names>N</given-names>
</name>
<name name-style="western"><surname>Church</surname>
<given-names>GM</given-names>
</name>
</person-group>
<year>2012</year>
<article-title>Gene assembly from chip-synthesized oligonucleotides</article-title>
<source>Curr Protoc Chem Biol</source>
<volume>2012</volume>
<fpage>ch110190</fpage>
<pub-id pub-id-type="pmid">25077042</pub-id>
</element-citation>
</ref>
<ref id="r9"><label>9</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name name-style="western"><surname>Plesa</surname>
<given-names>C</given-names>
</name>
<name name-style="western"><surname>Sidore</surname>
<given-names>AM</given-names>
</name>
<name name-style="western"><surname>Lubock</surname>
<given-names>NB</given-names>
</name>
<name name-style="western"><surname>Zhang</surname>
<given-names>D</given-names>
</name>
<name name-style="western"><surname>Kosuri</surname>
<given-names>S</given-names>
</name>
</person-group>
<year>2018</year>
<article-title>Multiplexed gene synthesis in emulsions for exploring protein functional landscapes</article-title>
<source>Science</source>
<volume>359</volume>
<fpage>343</fpage>
<lpage>347</lpage>
<pub-id pub-id-type="pmid">29301959</pub-id>
</element-citation>
</ref>
<ref id="r10"><label>10</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name name-style="western"><surname>Fan</surname>
<given-names>R</given-names>
</name>
<etal></etal>
</person-group>
<year>2008</year>
<article-title>Integrated barcode chips for rapid, multiplexed analysis of proteins in microliter quantities of blood</article-title>
<source>Nat Biotechnol</source>
<volume>26</volume>
<fpage>1373</fpage>
<lpage>1378</lpage>
<pub-id pub-id-type="pmid">19029914</pub-id>
</element-citation>
</ref>
<ref id="r11"><label>11</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name name-style="western"><surname>Ma</surname>
<given-names>C</given-names>
</name>
<etal></etal>
</person-group>
<year>2011</year>
<article-title>A clinical microchip for evaluation of single immune cells reveals high functional heterogeneity in phenotypically similar T cells</article-title>
<source>Nat Med</source>
<volume>17</volume>
<fpage>738</fpage>
<lpage>743</lpage>
<pub-id pub-id-type="pmid">21602800</pub-id>
</element-citation>
</ref>
<ref id="r12"><label>12</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name name-style="western"><surname>Zimmermann</surname>
<given-names>G</given-names>
</name>
<name name-style="western"><surname>Neri</surname>
<given-names>D</given-names>
</name>
</person-group>
<year>2016</year>
<article-title>DNA-encoded chemical libraries: Foundations and applications in lead discovery</article-title>
<source>Drug Discov Today</source>
<volume>21</volume>
<fpage>1828</fpage>
<lpage>1834</lpage>
<pub-id pub-id-type="pmid">27477486</pub-id>
</element-citation>
</ref>
<ref id="r13"><label>13</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name name-style="western"><surname>Melkko</surname>
<given-names>S</given-names>
</name>
<name name-style="western"><surname>Scheuermann</surname>
<given-names>J</given-names>
</name>
<name name-style="western"><surname>Dumelin</surname>
<given-names>CE</given-names>
</name>
<name name-style="western"><surname>Neri</surname>
<given-names>D</given-names>
</name>
</person-group>
<year>2004</year>
<article-title>Encoded self-assembling chemical libraries</article-title>
<source>Nat Biotechnol</source>
<volume>22</volume>
<fpage>568</fpage>
<lpage>574</lpage>
<pub-id pub-id-type="pmid">15097996</pub-id>
</element-citation>
</ref>
<ref id="r14"><label>14</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name name-style="western"><surname>Kosuri</surname>
<given-names>S</given-names>
</name>
<name name-style="western"><surname>Church</surname>
<given-names>GM</given-names>
</name>
</person-group>
<year>2014</year>
<article-title>Large-scale de novo DNA synthesis: Technologies and applications</article-title>
<source>Nat Methods</source>
<volume>11</volume>
<fpage>499</fpage>
<lpage>507</lpage>
<pub-id pub-id-type="pmid">24781323</pub-id>
</element-citation>
</ref>
<ref id="r15"><label>15</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name name-style="western"><surname>Petrone</surname>
<given-names>J</given-names>
</name>
</person-group>
<year>2016</year>
<article-title>DNA writers attract investors</article-title>
<source>Nat Biotechnol</source>
<volume>34</volume>
<fpage>363</fpage>
<lpage>364</lpage>
<pub-id pub-id-type="pmid">27054977</pub-id>
</element-citation>
</ref>
<ref id="r16"><label>16</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name name-style="western"><surname>Litovchick</surname>
<given-names>A</given-names>
</name>
<etal></etal>
</person-group>
<year>2015</year>
<article-title>Encoded library synthesis using chemical ligation and the discovery of sEH inhibitors from a 334-million member library</article-title>
<source>Sci Rep</source>
<volume>5</volume>
<fpage>10916</fpage>
<pub-id pub-id-type="pmid">26061191</pub-id>
</element-citation>
</ref>
<ref id="r17"><label>17</label>
<element-citation publication-type="web"><person-group person-group-type="author"><collab>CustomArray, Inc.</collab>
</person-group>
<year>2018</year>
<comment>About Us. Available at <ext-link ext-link-type="uri" xlink:href="http://www.customarrayinc.com/aboutus_main.htm" xlink:show="new">www.customarrayinc.com/aboutus_main.htm</ext-link>
. Accessed January 8, 2018</comment>
</element-citation>
</ref>
<ref id="r18"><label>18</label>
<element-citation publication-type="book"><person-group person-group-type="author"><name name-style="western"><surname>Peterson</surname>
<given-names>WW</given-names>
</name>
<name name-style="western"><surname>Weldon</surname>
<given-names>EJ</given-names>
</name>
</person-group>
<year>1972</year>
<source>Error-Correcting Codes</source>
<publisher-name>MIT Press</publisher-name>
<publisher-loc>Cambridge, MA</publisher-loc>
</element-citation>
</ref>
<ref id="r19"><label>19</label>
<element-citation publication-type="book"><person-group person-group-type="author"><name name-style="western"><surname>MacWilliams</surname>
<given-names>FJ</given-names>
</name>
<name name-style="western"><surname>Sloane</surname>
<given-names>NJA</given-names>
</name>
</person-group>
<year>1977</year>
<source>The Theory of Error-Correcting Codes</source>
<publisher-name>Elsevier</publisher-name>
<publisher-loc>New York</publisher-loc>
</element-citation>
</ref>
<ref id="r20"><label>20</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name name-style="western"><surname>Lyons</surname>
<given-names>E</given-names>
</name>
<name name-style="western"><surname>Sheridan</surname>
<given-names>P</given-names>
</name>
<name name-style="western"><surname>Tremmel</surname>
<given-names>G</given-names>
</name>
<name name-style="western"><surname>Miyano</surname>
<given-names>S</given-names>
</name>
<name name-style="western"><surname>Sugano</surname>
<given-names>S</given-names>
</name>
</person-group>
<year>2017</year>
<article-title>Large-scale DNA barcode library generation for biomolecule identification in high-throughput screens</article-title>
<source>Sci Rep</source>
<volume>7</volume>
<fpage>13899</fpage>
<pub-id pub-id-type="pmid">29066821</pub-id>
</element-citation>
</ref>
<ref id="r21"><label>21</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name name-style="western"><surname>Erlich</surname>
<given-names>Y</given-names>
</name>
<name name-style="western"><surname>Zielinski</surname>
<given-names>D</given-names>
</name>
</person-group>
<year>2017</year>
<article-title>DNA Fountain enables a robust and efficient storage architecture</article-title>
<source>Science</source>
<volume>355</volume>
<fpage>950</fpage>
<lpage>954</lpage>
<pub-id pub-id-type="pmid">28254941</pub-id>
</element-citation>
</ref>
<ref id="r22"><label>22</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name name-style="western"><surname>Levenshtein</surname>
<given-names>VI</given-names>
</name>
</person-group>
<year>1966</year>
<article-title>Binary codes capable of correcting deletions, insertions, and reversals</article-title>
<source>Sov Phys Dokl</source>
<volume>10</volume>
<fpage>707</fpage>
<lpage>710</lpage>
</element-citation>
</ref>
<ref id="r23"><label>23</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name name-style="western"><surname>Costea</surname>
<given-names>PI</given-names>
</name>
<name name-style="western"><surname>Lundeberg</surname>
<given-names>J</given-names>
</name>
<name name-style="western"><surname>Akan</surname>
<given-names>P</given-names>
</name>
<name name-style="western"><surname>Tag</surname>
<given-names>GD</given-names>
</name>
</person-group>
<year>2013</year>
<article-title>TagGD: Fast and accurate software for DNA tag generation and demultiplexing</article-title>
<source>PLoS One</source>
<volume>8</volume>
<fpage>e57521</fpage>
<pub-id pub-id-type="pmid">23469199</pub-id>
</element-citation>
</ref>
<ref id="r24"><label>24</label>
<element-citation publication-type="book"><person-group person-group-type="author"><name name-style="western"><surname>Houghten</surname>
<given-names>SK</given-names>
</name>
<name name-style="western"><surname>Ashlock</surname>
<given-names>D</given-names>
</name>
<name name-style="western"><surname>Lenarz</surname>
<given-names>J</given-names>
</name>
</person-group>
<year>2006</year>
<article-title>Construction of optimal edit metric codes</article-title>
<source>2006 IEEE Information Theory Workshop–ITW ’06 Chengdu</source>
<publisher-name>IEEE Press</publisher-name>
<publisher-loc>Piscataway, NJ</publisher-loc>
<fpage>259</fpage>
<lpage>263</lpage>
</element-citation>
</ref>
<ref id="r25"><label>25</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name name-style="western"><surname>Quail</surname>
<given-names>MA</given-names>
</name>
<etal></etal>
</person-group>
<year>2012</year>
<article-title>A tale of three next generation sequencing platforms: Comparison of ion torrent, Pacific biosciences and Illumina MiSeq sequencers</article-title>
<source>BMC Genomics</source>
<volume>13</volume>
<fpage>341</fpage>
<pub-id pub-id-type="pmid">22827831</pub-id>
</element-citation>
</ref>
<ref id="r26"><label>26</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name name-style="western"><surname>Hamming</surname>
<given-names>RW</given-names>
</name>
</person-group>
<year>1950</year>
<article-title>Error detecting and error correcting codes</article-title>
<source>Bell Labs Tech J</source>
<volume>29</volume>
<fpage>147</fpage>
<lpage>160</lpage>
</element-citation>
</ref>
<ref id="r27"><label>27</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name name-style="western"><surname>Buschmann</surname>
<given-names>T</given-names>
</name>
<name name-style="western"><surname>Bystrykh</surname>
<given-names>LV</given-names>
</name>
</person-group>
<year>2013</year>
<article-title>Levenshtein error-correcting barcodes for multiplexed DNA sequencing</article-title>
<source>BMC Bioinformatics</source>
<volume>14</volume>
<fpage>272</fpage>
<pub-id pub-id-type="pmid">24021088</pub-id>
</element-citation>
</ref>
<ref id="r28"><label>28</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name name-style="western"><surname>Lee</surname>
<given-names>DF</given-names>
</name>
<name name-style="western"><surname>Lu</surname>
<given-names>J</given-names>
</name>
<name name-style="western"><surname>Chang</surname>
<given-names>S</given-names>
</name>
<name name-style="western"><surname>Loparo</surname>
<given-names>JJ</given-names>
</name>
<name name-style="western"><surname>Xie</surname>
<given-names>XS</given-names>
</name>
</person-group>
<year>2016</year>
<article-title>Mapping DNA polymerase errors by single-molecule sequencing</article-title>
<source>Nucleic Acids Res</source>
<volume>44</volume>
<fpage>e118</fpage>
<pub-id pub-id-type="pmid">27185891</pub-id>
</element-citation>
</ref>
<ref id="r29"><label>29</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name name-style="western"><surname>Markham</surname>
<given-names>NR</given-names>
</name>
<name name-style="western"><surname>Zuker</surname>
<given-names>M</given-names>
</name>
</person-group>
<year>2008</year>
<article-title>UNAFold: Software for nucleic acid folding and hybridization</article-title>
<source>Methods Mol Biol</source>
<volume>453</volume>
<fpage>3</fpage>
<lpage>31</lpage>
<pub-id pub-id-type="pmid">18712296</pub-id>
</element-citation>
</ref>
<ref id="r30"><label>30</label>
<element-citation publication-type="journal"><person-group person-group-type="author"><name name-style="western"><surname>van Zanten</surname>
<given-names>AJ</given-names>
</name>
</person-group>
<year>1997</year>
<article-title>Lexicographic order and linearity</article-title>
<source>Des Codes Cryptogr</source>
<volume>10</volume>
<fpage>85</fpage>
<lpage>97</lpage>
</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 0011288 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Pmc/Corpus/biblio.hfd -nk 0011288 | 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. | ![]() |