DNA array decoding from nonlinear measurements by belief propagation

We propose a signal recovery method using Belief Propagation (BP) for nonlinear Compressed Sensing (CS) and demonstrate its utility in DNA array decoding. In a CS DNA microarray, the array spots identify DNA sequences that are shared between multiple organisms, thereby reducing the number of spots required. The sparsity in DNA sequence commonality between different organisms translates to conditions that render Belief Propagation (BP) efficient for signal reconstruction. However, an excessively high concentration of target DNA molecules has a nonlinear effect on the measurements - it causes saturation in the measurement intensities at the array spots. We use a modified BP to estimate the target signal coefficients since it is flexible to handle the nonlinearity unlike ℓ₁ decoding or other greedy algorithms and show that the original signal coefficients can be recovered from saturated measurements of their linear combinations.