Error and Quality Control Coding for DNA

Abstract — DNA microarrays are one of the most important and widely-used systems for generating genomic data for disease diagnostics and monitoring. The technology supporting DNA microarray production represents a successful combination of ideas from molecular biology, biochemistry, VLSI design and mathematics. Nevertheless, there still exist many issues that have to be resolved in order to ensure very high reliability of microarray operation. Several carefully chosen methods for controlling the quality of microarrays have already made their way into the manufacturing process, but almost no schemes are known that can guarantee proper functionality of arrays in the presence of spot failure and drop-out events occurring after the manufacturing process. Classical error-control coding techniques can be used to ensure increased robustness under spot failure in terms of multiplexing different DNA sequences to multiple spots of the array. Such techniques necessarily lead to changes in the manufacturing process and its underlying quality control techniques. It is the goal of this work to propose an integrated framework for analyzing quality control and error-correction in DNA microarrays generated by photolitographic VLSIPS (Very Large Scale Immobilized Polymer Synthesis) methods. In this context, the issues of base scheduling, mask design and borderlength minimization, construction of quality control arrays and good multiplexing strategies are addressed. The analysis is based on combining and extending results pertaining to the longest common subsequence problem, balanced and superimposed codes. I