FEAST: fast expectation-maximization for microbial source tracking.
Ontology highlight
ABSTRACT:
SUBMITTER: Shenhav L
PROVIDER: S-EPMC8535041 | biostudies-literature | 2019 Jul
REPOSITORIES: biostudies-literature
Publications
FEAST: fast expectation-maximization for microbial source tracking.
Shenhav Liat L Thompson Mike M Joseph Tyler A TA Briscoe Leah L Furman Ori O Bogumil David D Mizrahi Itzhak I Pe'er Itsik I Halperin Eran E
Nature methods 20190610 7
A major challenge of analyzing the compositional structure of microbiome data is identifying its potential origins. Here, we introduce fast expectation-maximization microbial source tracking (FEAST), a ready-to-use scalable framework that can simultaneously estimate the contribution of thousands of potential source environments in a timely manner, thereby helping unravel the origins of complex microbial communities ( https://github.com/cozygene/FEAST ). The information gained from FEAST may prov ...[more]
Similar Datasets
Project description:Elucidating the sources of a microbiome can provide insight into the ecological dynamics responsible for the formation of these communities. Source tracking approaches to date leverage species abundance information; however, single nucleotide variants (SNVs) may be more informative because of their high specificity to certain sources. To overcome the computational burden of utilizing all SNVs for a given sample, we introduce a novel method to identify signature SNVs for source tracking. Signature SNVs used as input into a previously designed source tracking algorithm, FEAST, can more accurately estimate contributions than species and provide novel insights, demonstrated in three case studies.
| S-EPMC10150486 | biostudies-literature
Project description:The current study proposes an alternative feasible Bayesian algorithm for the three-parameter logistic model (3PLM) from a mixture-modeling perspective, namely, the Bayesian Expectation-Maximization-Maximization (Bayesian EMM, or BEMM). As a new maximum likelihood estimation (MLE) alternative to the marginal MLE EM (MMLE/EM) for the 3PLM, the EMM can explore the likelihood function much better, but it might still suffer from the unidentifiability problem indicated by occasional extremely large item parameter estimates. Traditionally, this problem was remedied by the Bayesian approach which led to the Bayes modal estimation (BME) in IRT estimation. The current study attempts to mimic the Bayes modal estimation method and develop the BEMM which, as a combination of the EMM and the Bayesian approach, can bring in the benefits of the two methods. The study also devised a supplemented EM method to estimate the standard errors (SEs). A simulation study and two real data examples indicate that the BEMM can be more robust against the change in the priors than the Bayes modal estimation. The mixture modeling idea and this algorithm can be naturally extended to other IRT with guessing parameters and the four-parameter logistic models (4PLM).
| S-EPMC6555200 | biostudies-literature
Project description:The growing capacity to process and store animal tracks has spurred the development of new methods to segment animal trajectories into elementary units of movement. Key challenges for movement trajectory segmentation are to (i) minimize the need of supervision, (ii) reduce computational costs, (iii) minimize the need of prior assumptions (e.g. simple parametrizations), and (iv) capture biologically meaningful semantics, useful across a broad range of species. We introduce the Expectation-Maximization binary Clustering (EMbC), a general purpose, unsupervised approach to multivariate data clustering. The EMbC is a variant of the Expectation-Maximization Clustering (EMC), a clustering algorithm based on the maximum likelihood estimation of a Gaussian mixture model. This is an iterative algorithm with a closed form step solution and hence a reasonable computational cost. The method looks for a good compromise between statistical soundness and ease and generality of use (by minimizing prior assumptions and favouring the semantic interpretation of the final clustering). Here we focus on the suitability of the EMbC algorithm for behavioural annotation of movement data. We show and discuss the EMbC outputs in both simulated trajectories and empirical movement trajectories including different species and different tracking methodologies. We use synthetic trajectories to assess the performance of EMbC compared to classic EMC and Hidden Markov Models. Empirical trajectories allow us to explore the robustness of the EMbC to data loss and data inaccuracies, and assess the relationship between EMbC output and expert label assignments. Additionally, we suggest a smoothing procedure to account for temporal correlations among labels, and a proper visualization of the output for movement trajectories. Our algorithm is available as an R-package with a set of complementary functions to ease the analysis.
| S-EPMC4803255 | biostudies-literature
Project description:Single Particle Tracking (SPT) is a well known class of tools for studying the dynamics of biological macromolecules moving inside living cells. In this paper, we focus on the problem of localization and parameter estimation given a sequence of segmented images. In the standard paradigm, the location of the emitter inside each frame of a sequence of camera images is estimated using, for example, Gaussian fitting (GF), and these locations are linked to provide an estimate of the trajectory. Trajectories are then analyzed by using Mean Square Displacement (MSD) or Maximum Likelihood Estimation (MLE) techniques to determine motion parameters such as diffusion coefficients. However, the problems of localization and parameter estimation are clearly coupled. Motivated by this, we have created an Expectation Maximization (EM) based framework for simultaneous localization and parameter estimation. We demonstrate this framework through two representative methods, namely, Sequential Monte Carlo combined with Expectation Maximization (SMC-EM) and Unscented Kalman Filter combined with Expectation Maximization (U-EM). Using diffusion in two-dimensions as a prototypical example, we conduct quantitative investigations on localization and parameter estimation performance across a wide range of signal to background ratios and diffusion coefficients and compare our methods to the standard techniques based on GF-MSD/MLE. To demonstrate the flexibility of the EM based framework, we do comparisons using two different camera models, an ideal camera with Poisson distributed shot noise but no readout noise, and a camera with both shot noise and the pixel-dependent readout noise that is common to scientific complementary metal-oxide semiconductor (sCMOS) camera. Our results indicate our EM based methods outperform the standard techniques, especially at low signal levels. While U-EM and SMC-EM have similar accuracy, U-EM is significantly more computationally efficient, though the use of the Unscented Kalman Filter limits U-EM to lower diffusion rates.
| S-EPMC8139521 | biostudies-literature
Project description:MotivationThe Expectation Maximization (EM) algorithm, in the form of the Baum-Welch algorithm (for hidden Markov models) or the Inside-Outside algorithm (for stochastic context-free grammars), is a powerful way to estimate the parameters of stochastic grammars for biological sequence analysis. To use this algorithm for multiple-sequence evolutionary modelling, it would be useful to apply the EM algorithm to estimate not only the probability parameters of the stochastic grammar, but also the instantaneous mutation rates of the underlying evolutionary model (to facilitate the development of stochastic grammars based on phylogenetic trees, also known as Statistical Alignment). Recently, we showed how to do this for the point substitution component of the evolutionary process; here, we extend these results to the indel process.ResultsWe present an algorithm for maximum-likelihood estimation of insertion and deletion rates from multiple sequence alignments, using EM, under the single-residue indel model owing to Thorne, Kishino and Felsenstein (the 'TKF91' model). The algorithm converges extremely rapidly, gives accurate results on simulated data that are an improvement over parsimonious estimates (which are shown to underestimate the true indel rate), and gives plausible results on experimental data (coronavirus envelope domains). Owing to the algorithm's close similarity to the Baum-Welch algorithm for training hidden Markov models, it can be used in an 'unsupervised' fashion to estimate rates for unaligned sequences, or estimate several sets of rates for sequences with heterogenous rates.AvailabilitySoftware implementing the algorithm and the benchmark is available under GPL from http://www.biowiki.org/
| S-EPMC7197704 | biostudies-literature
Project description:Bayesian graphical models are a useful tool for understanding dependence relationships among many variables, particularly in situations with external prior information. In high-dimensional settings, the space of possible graphs becomes enormous, rendering even state-of-the-art Bayesian stochastic search computationally infeasible. We propose a deterministic alternative to estimate Gaussian and Gaussian copula graphical models using an Expectation Conditional Maximization (ECM) algorithm, extending the EM approach from Bayesian variable selection to graphical model estimation. We show that the ECM approach enables fast posterior exploration under a sequence of mixture priors, and can incorporate multiple sources of information.
| S-EPMC7540244 | biostudies-literature
Project description:Modern man-made environments, including urban, agricultural, and industrial environments, have complex ecological interactions among themselves and with the natural surroundings. Microbial source tracking (MST) offers advanced tools to resolve the host source of fecal contamination beyond indicator monitoring. This study was intended to assess karst spring susceptibilities to different fecal sources using MST quantitative PCR (qPCR) assays targeting human, bovine, and swine markers. It involved a dual-time monitoring frame: (i) monthly throughout the calendar year and (ii) daily during a rainfall event. Data integration was taken from both monthly and daily MST profile monitoring and improved identification of spring susceptibility to host fecal contamination; three springs located in close geographic proximity revealed different MST profiles. The Giach spring showed moderate fluctuations of MST marker quantities amid wet and dry samplings, while the Zuf spring had the highest rise of the GenBac3 marker during the wet event, which was mirrored in other markers as well. The revelation of human fecal contamination during the dry season not connected to incidents of raining leachates suggests a continuous and direct exposure to septic systems. Pigpens were identified in the watersheds of Zuf, Shefa, and Giach springs and on the border of the Gaaton spring watershed. Their impact was correlated with partial detection of the Pig-2-Bac marker in Gaaton spring, which was lower than detection levels in all three of the other springs. Ruminant and swine markers were detected intermittently, and their contamination potential during the wet samplings was exposed. These results emphasized the importance of sampling design to utilize the MST approach to delineate subtleties of fecal contamination in the environment.
| S-EPMC4495197 | biostudies-literature
Project description:With the development of computer network bandwidth, packet classification algorithms which are able to deal with large-scale rule sets are in urgent need. Among the existing algorithms, researches on packet classification algorithms based on hierarchical trie have become an important packet classification research branch because of their widely practical use. Although hierarchical trie is beneficial to save large storage space, it has several shortcomings such as the existence of backtracking and empty nodes. This paper proposes a new packet classification algorithm, Hierarchical Trie Algorithm Based on Expectation-Maximization Clustering (HTEMC). Firstly, this paper uses the formalization method to deal with the packet classification problem by means of mapping the rules and data packets into a two-dimensional space. Secondly, this paper uses expectation-maximization algorithm to cluster the rules based on their aggregate characteristics, and thereby diversified clusters are formed. Thirdly, this paper proposes a hierarchical trie based on the results of expectation-maximization clustering. Finally, this paper respectively conducts simulation experiments and real-environment experiments to compare the performances of our algorithm with other typical algorithms, and analyzes the results of the experiments. The hierarchical trie structure in our algorithm not only adopts trie path compression to eliminate backtracking, but also solves the problem of low efficiency of trie updates, which greatly improves the performance of the algorithm.
| S-EPMC5509293 | biostudies-literature
Project description:Genome-wide nucleosome profiles are predominantly characterized using MNase-seq, which involves extensive MNase digestion and size selection to enrich for mononucleosome-sized fragments. Most available MNase-seq analysis packages assume that nucleosomes uniformly protect 147 bp DNA fragments. However, some nucleosomes with atypical histone or chemical compositions protect shorter lengths of DNA. The rigid assumptions imposed by current nucleosome analysis packages potentially prevent investigators from understanding the regulatory roles played by atypical nucleosomes. To enable the characterization of different nucleosome types from MNase-seq data, we introduce the size-based expectation maximization (SEM) nucleosome-calling package. SEM employs a hierarchical Gaussian mixture model to estimate nucleosome positions and subtypes. Nucleosome subtypes are automatically identified based on the distribution of protected DNA fragments. Benchmark analysis indicates that SEM is on par with existing packages in terms of standard nucleosome-calling accuracy metrics, while uniquely providing the ability to characterize nucleosome subtype identities. Applying SEM to a low-dose MNase-H2B-ChIP-seq data set from mouse embryonic stem cells, we identified three nucleosome types: short-fragment nucleosomes, canonical nucleosomes, and di-nucleosomes. Short-fragment nucleosomes can be divided further into two subtypes based on their chromatin accessibility. Short-fragment nucleosomes in accessible regions exhibit high MNase sensitivity and are enriched at transcription start sites (TSSs) and CTCF peaks, similar to previously reported "fragile nucleosomes." These SEM-defined accessible short-fragment nucleosomes are found not just in promoters but also in distal regulatory regions. Additional analyses reveal their colocalization with the chromatin remodelers CHD6, CHD8, and EP400. In summary, SEM provides an effective platform for exploration of nonstandard nucleosome subtypes.
| S-EPMC11529872 | biostudies-literature
Project description:Contamination is a critical issue in high-throughput metagenomic studies, yet progress toward a comprehensive solution has been limited. We present SourceTracker, a Bayesian approach to estimate the proportion of contaminants in a given community that come from possible source environments. We applied SourceTracker to microbial surveys from neonatal intensive care units (NICUs), offices and molecular biology laboratories, and provide a database of known contaminants for future testing.
| S-EPMC3791591 | biostudies-literature