Search

BackgroundMost of our knowledge about the remarkable microbial diversity on Earth comes from sequencing the 16S rRNA gene. The use of next-generation sequencing methods has increased sample number and sequencing depth, but the read length of the most widely used sequencing platforms today is quite short, requiring the researcher to choose a subset of the gene to sequence (typically 16-33% of the total length). Thus, many bacteria may share the same amplified region, and the resolution of profiling is inherently limited. Platforms that offer ultra-long read lengths, whole genome shotgun sequencing approaches, and computational frameworks formerly suggested by us and by others all allow different ways to circumvent this problem yet suffer various shortcomings. There is a need for a simple and low-cost 16S rRNA gene-based profiling approach that harnesses the short read length to provide a much larger coverage of the gene to allow for high resolution, even in harsh conditions of low bacterial biomass and fragmented DNA.ResultsThis manuscript suggests Short MUltiple Regions Framework (SMURF), a method to combine sequencing results from different PCR-amplified regions to provide one coherent profiling. The de facto amplicon length is the total length of all amplified regions, thus providing much higher resolution compared to current techniques. Computationally, the method solves a convex optimization problem that allows extremely fast reconstruction and requires only moderate memory. We demonstrate the increase in resolution by in silico simulations and by profiling two mock mixtures and real-world biological samples. Reanalyzing a mock mixture from the Human Microbiome Project achieved about twofold improvement in resolution when combing two independent regions. Using a custom set of six primer pairs spanning about 1200 bp (80%) of the 16S rRNA gene, we were able to achieve ~ 100-fold improvement in resolution compared to a single region, over a mock mixture of common human gut bacterial isolates. Finally, the profiling of a Drosophila melanogaster microbiome using the set of six primer pairs provided a ~ 100-fold increase in resolution and thus enabling efficient downstream analysis.ConclusionsSMURF enables the identification of near full-length 16S rRNA gene sequences in microbial communities, having resolution superior compared to current techniques. It may be applied to standard sample preparation protocols with very little modifications. SMURF also paves the way to high-resolution profiling of low-biomass and fragmented DNA, e.g., in the case of formalin-fixed and paraffin-embedded samples, fossil-derived DNA, or DNA exposed to other degrading conditions. The approach is not restricted to combining amplicons of the 16S rRNA gene and may be applied to any set of amplicons, e.g., in multilocus sequence typing (MLST).

The emergence of massively parallel sequencing technology has revolutionized microbial profiling, allowing the unprecedented comparison of microbial diversity across time and space in a wide range of host-associated and environmental ecosystems. Although the high-throughput nature of such methods enables the detection of low-frequency bacteria, these advances come at the cost of sequencing read length, limiting the phylogenetic resolution possible by current methods. Here, we present a generic approach for integrating short reads from large genomic regions, thus enabling phylogenetic resolution far exceeding current methods. The approach is based on a mapping to a statistical model that is later solved as a constrained optimization problem. We demonstrate the utility of this method by analyzing human saliva and Drosophila samples, using Illumina single-end sequencing of a 750 bp amplicon of the 16S rRNA gene. Phylogenetic resolution is significantly extended while reducing the number of falsely detected bacteria, as compared with standard single-region Roche 454 Pyrosequencing. Our approach can be seamlessly applied to simultaneous sequencing of multiple genes providing a higher resolution view of the composition and activity of complex microbial communities.

Discrete-input two-dimensional (2-D) Gaussian channels with memory represent an important class of systems, which appears extensively in communications and storage. In spite of their widespread use, the workings of 2-D channels are still very much unknown. In this work, we try to explore their properties from the perspective of estimation theory and information theory. At the heart of our approach is a mapping of a 2-D channel to an undirected graphical model, and inferring its a posteriori probabilities (APPs) using generalized belief propagation (GBP). The derived probabilities are shown to be practically accurate, thus enabling optimal maximum a posteriori (MAP) estimation of the transmitted symbols. Also, the Shannon-the-oretic information rates are deduced either via the vector-wise Shannon-McMillan-Breiman (SMB) theorem, or via the recently derived symbol-wise Guo-Shamai-Verdu (GSV) theorem. Our approach is also 'described from the perspective of statistical mechanics, as the graphical model and inference algorithm have their analogues in physics. Our experimental study, based on common channel settings taken from cellular networks and magnetic recording devices, demonstrates that under nontrivial memory conditions, the performance of this fully tractable GBP estimator is almost identical to the performance of the optimal MAP estimator. It also enables a practically accurate simulation-based estimate of the information rate. Rationalization of this excellent performance of GBP in the 2-D Gaussian channel setting is addressed. Index Terms--Cluster variation method, generalized belief propagation (GBP), Guo-Shamal-Verdu (GSV) theorem, information rate, intersymbol interference (ISI), magnetic recording channels, maximum a posteriori (MAP) estimation, multiple-access (MA) channels, Shannon-McMillan-Breiman (SMB) theorem, two-dimensional (2-D) channels.