DNA array decoding from nonlinear measurements by belief propagation

Mona A. Sheikh, Shriram Sarvotham, Olgica Milenkovic, Richard G. Baraniuk

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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 ℓ1 decoding or other greedy algorithms and show that the original signal coefficients can be recovered from saturated measurements of their linear combinations.

Original languageEnglish (US)
Title of host publication2007 IEEE/SP 14th Workshop on Statistical Signal Processing, SSP 2007, Proceedings
Number of pages5
StatePublished - 2007
Externally publishedYes
Event2007 IEEE/SP 14th WorkShoP on Statistical Signal Processing, SSP 2007 - Madison, WI, United States
Duration: Aug 26 2007Aug 29 2007

Publication series

NameIEEE Workshop on Statistical Signal Processing Proceedings


Other2007 IEEE/SP 14th WorkShoP on Statistical Signal Processing, SSP 2007
Country/TerritoryUnited States
CityMadison, WI


  • Belief propagation
  • Compressed sensing
  • DNA microarray
  • Saturated measurements

ASJC Scopus subject areas

  • Signal Processing


Dive into the research topics of 'DNA array decoding from nonlinear measurements by belief propagation'. Together they form a unique fingerprint.

Cite this