Compressed Genotyping

Abstract

Significant volumes of knowledge have been accumulated in recent years linking subtle genetic variations to a wide variety of medical disorders from Cystic Fibrosis to mental retardation. Nevertheless, there are still great challenges in applying this knowledge routinely in the clinic, largely due to the relatively tedious and expensive process of DNA sequencing. Since the genetic polymorphisms that underlie these disorders are relatively rare in the human population, the presence or absence of a disease-linked polymorphism can be thought of as a sparse signal. Using methods and ideas from compressed sensing and group testing, we have developed a cost-effective genotyping protocol. In particular, we have adapted our scheme to a recently developed class of high throughput DNA sequencing technologies, and assembled a mathematical framework that has some important distinctions from 'traditional' compressed sensing ideas in order to address different biological and technical constraints.

Submitted to IEEE Transaction on Information Theory - Special Issue on Molecular Biology and Neuroscience

References in corpus (5)

• General Deviants: An Analysis of Perturbations in Compressed Sensing
• Boolean Compressed Sensing and Noisy Group Testing
• Algorithmic linear dimension reduction in the l_1 norm for sparse vectors
• Statistical Mechanics of the Hyper Vertex Cover Problem
• Rare-Allele Detection Using Compressed Se(que)nsing

Cited by in corpus (13)

• Note on Noisy Group Testing: Asymptotic Bounds and Belief Propagation Reconstruction
• The Capacity of Adaptive Group Testing
• Successive Concave Sparsity Approximation for Compressed Sensing
• Strong converses for group testing in the finite blocklength regime
• Semi-Quantitative Group Testing: A Unifying Framework for Group Testing with Applications in Genotyping
• Non-adaptive pooling strategies for detection of rare faulty items
• Distilled Single Cell Genome Sequencing and De Novo Assembly for Sparse Microbial Communities
• Optimal Estimation and Prediction for Dense Signals in High-Dimensional Linear Models
• Mixed Operators in Compressed Sensing
• Code Construction and Decoding Algorithms for Semi-Quantitative Group Testing with Nonuniform Thresholds
• Superimposed Codes and Threshold Group Testing
• Separable Codes for the Symmetric Multiple-Access Channel
• Bacterial Community Reconstruction Using A Single Sequencing Reaction