title: Levenshtein error-correcting barcodes for multiplexed DNA sequencing.
abstract: BACKGROUND
  High-throughput sequencing technologies are improving in quality, capacity and costs, providing versatile applications in DNA and RNA research. For small genomes or fraction of larger genomes, DNA samples can be mixed and loaded together on the same sequencing track. This so-called multiplexing approach relies on a specific DNA tag or barcode that is attached to the sequencing or amplification primer and hence appears at the beginning of the sequence in every read. After sequencing, each sample read is identified on the basis of the respective barcode sequence.Alterations of DNA barcodes during synthesis, primer ligation, DNA amplification, or sequencing may lead to incorrect sample identification unless the error is revealed and corrected. This can be accomplished by implementing error correcting algorithms and codes. This barcoding strategy increases the total number of correctly identified samples, thus improving overall sequencing efficiency. Two popular sets of error-correcting codes are Hamming codes and Levenshtein codes.
  
  
  RESULTS
  Levenshtein codes operate only on words of known length. Since a DNA sequence with an embedded barcode is essentially one continuous long word, application of the classical Levenshtein algorithm is problematic. In this paper we demonstrate the decreased error correction capability of Levenshtein codes in a DNA context and suggest an adaptation of Levenshtein codes that is proven of efficiently correcting nucleotide errors in DNA sequences. In our adaption we take the DNA context into account and redefine the word length whenever an insertion or deletion is revealed. In simulations we show the superior error correction capability of the new method compared to traditional Levenshtein and Hamming based codes in the presence of multiple errors.
  
  
  CONCLUSIONS
  We present an adaptation of Levenshtein codes to DNA contexts capable of correction of a pre-defined number of insertion, deletion, and substitution mutations. Our improved method is additionally capable of recovering the new length of the corrupted codeword and of correcting on average more random mutations than traditional Levenshtein or Hamming codes.As part of this work we prepared software for the flexible generation of DNA codes based on our new approach. To adapt codes to specific experimental conditions, the user can customize sequence filtering, the number of correctable mutations and barcode length for highest performance.
authors.affiliation: Institute for Medical Informatics and Biometry (IMB), Faculty of Medicine Carl Gustav Carus, Dresden University of Technology, Dresden, Germany. tilo.buschmann@tu-dresden.de.
authors.forename: Tilo
authors.initials: T
authors.lastname: Buschmann
authors.forename: Leonid V
authors.initials: LV
authors.lastname: Bystrykh
mesh_terms: D000465:Algorithms; D004247:DNA / Q000032:analysis / Q000737:chemistry* / Q000235:genetics; D017931:DNA Primers / Q000737:chemistry / Q000235:genetics; D059014:High-Throughput Nucleotide Sequencing / Q000379:methods*; D008957:Models, Genetic; D021141:Nucleic Acid Amplification Techniques / Q000379:methods*; D015203:Reproducibility of Results; D017422:Sequence Analysis, DNA / Q000379:methods*; D012984:Software
chemical_list: D017931:DNA Primers; D004247:DNA
references.citation: BMC Genomics. 2012 Aug 05;13:375
references.pmid: 22863213
references.citation: PLoS One. 2012;7(8):e42543
references.pmid: 22900027
references.citation: BMC Genomics. 2010 Dec 20;11:716
references.pmid: 21171994
references.citation: Methods. 2009 Nov;49(3):227-35
references.pmid: 19481606
references.citation: PLoS One. 2012;7(5):e36852
references.pmid: 22615825
references.citation: BMC Genomics. 2011 May 19;12:245
references.pmid: 21592414
references.citation: Nat Protoc. 2009;4(5):789-98
references.pmid: 19528954
references.citation: Nucleic Acids Res. 2007;35(19):e130
references.pmid: 17932070
references.citation: Nat Methods. 2008 Mar;5(3):247-52
references.pmid: 18297082
references.citation: BMC Genomics. 2011 Feb 11;12:106
references.pmid: 21310087
references.citation: J Comput Biol. 2000;7(3-4):503-19
references.pmid: 11108476
references.citation: Nat Methods. 2012 May 30;9(6):567-74
references.pmid: 22669654
references.citation: Bioessays. 2010 Jun;32(6):524-36
references.pmid: 20486139
references.citation: J Chem Inf Comput Sci. 2003 Nov-Dec;43(6):2014-8
references.pmid: 14632452
references.citation: Nat Methods. 2008 Mar;5(3):235-7
references.pmid: 18264105
references.citation: Genome Res. 2010 Feb;20(2):249-56
references.pmid: 20123915