Kracht David, Schober Steffen
Institute of Communications Engineering, Ulm University, Albert-Einstein-Allee 43, Ulm, 89081, Germany.
BMC Bioinformatics. 2015 Feb 18;16:50. doi: 10.1186/s12859-015-0482-7.
Barcode multiplexing is a key strategy for sharing the rising capacity of next-generation sequencing devices: Synthetic DNA tags, called barcodes, are attached to natural DNA fragments within the library preparation procedure. Different libraries, can individually be labeled with barcodes for a joint sequencing procedure. A post-processing step is needed to sort the sequencing data according to their origin, utilizing these DNA labels. The final separation step is called demultiplexing and is mainly determined by the characteristics of the DNA code words used as labels. Currently, we are facing two different strategies for barcoding: One is based on the Hamming distance, the other uses the edit metric to measure distances of code words. The theory of channel coding provides well-known code constructions for Hamming metric. They provide a large number of code words with variable lengths and maximal correction capability regarding substitution errors. However, some sequencing platforms are known to have exceptional high numbers of insertion or deletion errors. Barcodes based on the edit distance can take insertion and deletion errors into account in the decoding process. Unfortunately, there is no explicit code-construction known that gives optimal codes for edit metric.
In the present work we focus on an entirely different perspective to obtain DNA barcodes. We consider a concatenated code construction, producing so-called watermark codes, which were first proposed by Davey and Mackay, to communicate via binary channels with synchronization errors. We adapt and extend the concepts of watermark codes to use them for DNA sequencing. Moreover, we provide an exemplary set of barcodes that are experimentally compatible with common next-generation sequencing platforms. Finally, a realistic simulation scenario is use to evaluate the proposed codes to show that the watermark concept is suitable for DNA sequencing applications.
Our adaption of watermark codes enables the construction of barcodes that are capable of correcting substitutions, insertion and deletion errors. The presented approach has the advantage of not needing any markers or technical sequences to recover the position of the barcode in the sequencing reads, which poses a significant restriction with other approaches.
条形码复用是一种用于共享下一代测序设备不断增长的容量的关键策略：在文库制备过程中，将称为条形码的合成DNA标签附着到天然DNA片段上。不同的文库可以分别用条形码标记，以便进行联合测序。需要一个后处理步骤，利用这些DNA标签根据测序数据的来源对其进行分类。最后的分离步骤称为解复用，主要由用作标签的DNA码字的特性决定。目前，我们面临两种不同的条形码策略：一种基于汉明距离，另一种使用编辑度量来测量码字的距离。信道编码理论为汉明度量提供了著名的码构造。它们提供了大量具有可变长度且对替换错误具有最大纠错能力的码字。然而，已知一些测序平台存在异常高数量的插入或缺失错误。基于编辑距离的条形码可以在解码过程中考虑插入和缺失错误。不幸的是，目前还没有已知的明确码构造能够给出编辑度量的最优码。
在本研究中，我们关注从一个完全不同的角度来获得DNA条形码。我们考虑一种级联码构造，产生所谓的水印码，这是由戴维和麦凯首先提出的，用于通过具有同步错误的二进制信道进行通信。我们对水印码的概念进行了调整和扩展，以将其用于DNA测序。此外，我们提供了一组与常见的下一代测序平台实验兼容的条形码示例。最后，使用一个现实的模拟场景来评估所提出的码，以表明水印概念适用于DNA测序应用。
我们对水印码的改编使得能够构建能够纠正替换、插入和缺失错误的条形码。所提出的方法的优点是不需要任何标记或技术序列来恢复测序读数中条形码的位置，而其他方法存在这一重大限制。
