Using the Davey-MacKay code construction for barcodes in DNA sequencing

In this paper we explain how we modify the Davey-MacKay code construction to generate so called DNA barcodes, a kind of label sequences used in the context of DNA sequencing. Davey and Mackay proposed the concept of watermark codes to communicate over binary channels with insertion and deletion errors. Such synchronization errors are likely to occur during DNA sequencing and may lead to serve problems in decoding the DNA barcodes. In order to use the watermark concepts in the DNA context we need adapt and extend the original ideas. We mainly give a quaternary adaptation of the channel model and modifications of the elementary hidden Markov models for decoding. An extended transmission model and a strategy to acquire synchronization for barcodes, that are embedded in an unknown DNA context is also proposed. We show simulation results indicating that watermark inspired barcodes are applicable for DNA sequencing. Apart from other approaches that have been proposed for barcoding in the presence of synchronization errors, we do not depend on greedy search algorithms for code words, but are able to use a code construction and a well-defined decoding procedure.