In And so it begins ... Compressive Genomics and Predicting the Future: Randomness and Parsimony, we made the case that algorithm development really needed to happen fast in order to face the tsunami of sequencing data we are being hit with. Recently in one of Sunday's Morning Insight entry, we slowly but surely woke up to the realization that we may have to change our vocabulary and ditch l_1 in favor of belief propagation (Approximate Message Passing) so that we could hit better phase transition than the ones given to us by the Donoho-Tanner transition. If you are in this frame of mind, you are ready to read the following paper: which "... is the first step in developing a novel framework for group testing that caters to the unique needs of the emerging field of genotyping through high-throughput sequencing."
Semi-Quantitative Group Testing: a General Paradigm with Applications in Genotyping by Amin Emad, Olgica Milenkovic. The abstract reads:
We propose a novel group testing method, termed semi-quantitative group testing, motivated by a class of problems arising in genome screening experiments. Semi-quantitative group testing (SQGT) is a (possibly) non-binary pooling scheme that may be viewed as a concatenation of an adder channel and an integer-valued quantizer. In its full generality, SQGT can be viewed as a unifying framework for group testing, in the sense that most group testing models are special instances of SQGT. For the new general testing scheme, we define the notion of SQ-disjunct and SQ-separable codes, generalizations of the classic disjunct and separable codes. We describe several combinatorial and probabilistic constructions of such codes. While in most of these constructions, we assume that the number of defectives is much smaller than total number of test subjects, we also consider the case in which there is no restriction on the number of defectives and they can be as large as the total number of subjects. For these codes, we describe a number of decoding algorithms; in particular, we describe belief propagation decoders for sparse SQGT codes. We define the notion of capacity of SQGT and evaluate it for some special choices of parameters using information theoretic methods.
Image Credit: NASA/JPL-Caltech
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.
No comments:
Post a Comment