SEARCH · PubMed Health

Results for “EM algorithm”

Explore indexed PubMed citations for clinical trials, systematic reviews and public health research. Read source abstracts and follow each citation to its original PubMed record.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 37 records · Page 2Linked to original sources

PubMed1995

Maximum-likelihood estimation of molecular haplotype frequencies in a diploid population.

Molecular techniques allow the survey of a large number of linked polymorphic loci in random samples from diploid populations. However, the gametic phase of haplotypes is usually unknown when diploid individuals are heterozygous at more than one locus. To overcome this difficulty, we implement an expectation-maximization (EM) algorithm leading to maximum-likelihood estimates of molecular haplotype frequencies under the assumption of Hardy-Weinberg proportions. The performance of the algorithm is evaluated for simulated data representing both DNA sequences and highly polymorphic loci with different levels of recombination. As expected, the EM algorithm is found to perform best for large samples, regardless of recombination rates among loci. To ensure finding the global maximum likelihood estimate, the EM algorithm should be started from several initial conditions. The present approach appears to be useful for the analysis of nuclear DNA sequences or highly variable loci. Although the algorithm, in principle, can accommodate an arbitrary number of loci, there are practical limitations because the computing time grows exponentially with the number of polymorphic loci. Although the algorithm, in principle, can accommodate an arbitrary number of loci, there are practical limitations because the computing time grows exponentially with the number of polymorphic loci.

Algorithms↗

PubMed1992

Three-dimensional SPECT reconstruction of combined cone beam and parallel beam data.

Single photon emission computed tomography (SPECT) using cone beam (CB) collimation exhibits increased sensitivity compared with acquisition geometries using parallel (P) hole collimation. However, CB collimation has a smaller field-of-view which may result in truncated projections and image artifacts. A primary objective of this work is to investigate maximum likelihood-expectation maximization (ML-EM) methods to reconstruct simultaneously acquired parallel and cone beam (P&CB) SPECT data. Simultaneous P&CB acquisition can be performed with commercially available triple camera systems by using two cone-beam collimators and a single parallel-hole collimator. The loss in overall sensitivity (relative to the use of three CB collimators) is about 15 to 20%. We have developed three methods to combine P&CB data using modified ML-EM algorithms. The first method consists of using both data sets to reconstruct a single intermediate image after each iteration using the ML-EM algorithm. The other two iterative algorithms combine intermediate parallel beam (PB) and CB source estimates to enhance image quality. For these methods, a PB estimate and a CB estimate are obtained for the first iteration. The second method consists of summing the PB and CB estimates for each subsequent iteration to obtain new PB and CB estimates. The third method is similar to the second method, with the exception that the new PB estimate simply is set equal to the PB estimate after each iteration. The combined source estimate is used in each subsequent iteration step of the EM algorithm. These algorithms are evaluated using projection data simulated using a Monte Carlo SPECT model. The P&CB SPECT images demonstrate marked improvement as compared with the CB-only reconstruction, particularly when the projections are truncated.

Algorithms↗

PubMed1989

Probits of mixtures.

The tolerances of individuals (insects, parasites) in a population have a frequency or probability distribution called a tolerance distribution. Many tolerance distributions in bioassay studies can be the result of a rather heterogeneous population of individuals and can often be modelled as a mixture of a number of standard unimodal distributions. A probit analysis can be generalized to the case where the tolerance distribution is a mixture of location and scale parameter distributions. In this article, the existence and determination of the maximum likelihood estimates are investigated. An expectation-maximization (EM) algorithm for probits of mixtures is developed and it is shown that by application of the EM algorithm, the problem of probits of mixtures can be separated into a series of probits of individual component tolerance distributions.

Algorithms↗

PubMed2026

ADAMIXTURE: adaptive first-order optimization for biobank-scale genetic clustering.

MOTIVATION: Estimating genetic clusters from sequencing data is a fundamental task in population and medical genetics, enabling demographic inference and adjustment for population structure in association studies. ADMIXTURE, a widely used model-based clustering method, employs an accelerated Expectation-Maximization (EM) algorithm to infer population parameters; however, its computational demands scale poorly, limiting its usefulness for modern biobank-sized datasets. While recent EM acceleration strategies employing second-order quasi-Newton schemes preserve accuracy, they remain computationally intensive. Conversely, EM-free approaches that prioritize speed often compromise solution quality. RESULTS: We introduce ADAMIXTURE, a novel optimization framework that integrates the EM algorithm with Adaptive Moment Estimation (Adam). Unlike traditional acceleration methods, ADAMIXTURE utilizes first-order gradients with adaptive learning rates derived from raw and squared moments to approximate curvature information, bypassing the computational overhead of Hessian approximations. This approach surpasses the convergence efficiency of second-order methods while maintaining the low computational complexity of first-order updates. Across simulated and large-scale empirical datasets, ADAMIXTURE demonstrates substantial reductions in wall-clock runtime and enhanced scalability compared to state-of-the-art methods, while maintaining comparable or improved inference accuracy. Its GPU implementation runs in under 2 h on half a million samples and variants, a two order of magnitude speedup over current state-of-the-art. AVAILABILITY AND IMPLEMENTATION: Source code is available at: https://github.com/AI-sandbox/ADAMIXTURE.

Clustering Algorithms↗

PubMed2026

Genomic wastewater surveillance of human and animal influenza A viruses in California during the 2024-2025 flu season.

BACKGROUND: Wastewater genomic surveillance provides an opportunity to detect human and animal influenza A virus (IAV). We aimed to implement an IAV genomic surveillance framework agnostic to subtype, which enables recovery of IAV from multiple hosts and estimation of proportions across subtypes. METHODS: We conducted IAV genomic surveillance in wastewater during the 2024-2025 flu season at multiple sites in California and compared these data with available human clinical IAV sequences and test positivity. We applied a custom whole-genome, multi-host IAV probe enrichment panel and adapted our custom expectation-maximization (EM) algorithm to deconvolute IAV mixtures in wastewater and infer subtype relative abundances. Absolute IAV concentrations were quantified using RT-PCR-based assays. H5N1 wastewater and clinical sequences were further characterized by constructing a whole-genome maximum-likelihood phylogenetic tree. Finally, we performed variant analysis to examine amino acid substitutions detected in wastewater. FINDINGS: Our IAV probe enrichment method and EM algorithm successfully enriched all eight segments of three circulating IAV subtypes and accurately estimated subclade relative abundances for mixed IAV samples. Seasonal human H1N1pdm09 and H3N2 were detected throughout the study period from both wastewater and clinical sequencing data, with H1N1 subclades 6B.1A.5a.2a.1 and 6B.1A.5a.2a co-circulating, and H3N2 dominated by subclade 3C.2a1b.2a.2a.3a.1. Wastewater surveillance consistently detected H5N1 clade 2.3.4.4b across three monitored wastewater sites, while clinical H5N1 detections, from anywhere in CA, were sporadic and rare. Whole-genome phylogenetic analysis revealed that wastewater H5N1 sequences clustered with reference sequences associated with dairy cow and avian infections, while all human clinical H5N1 sequences clustered exclusively with reference sequences associated with dairy cow infections. Amino acid substitutions were identified across viral segments, and no mutations associated with mammalian adaptation were observed from wastewater samples. INTERPRETATION: When IAV concentrations were dominated by seasonal human subtypes rather than H5N1, subtype patterns aligned between wastewater and clinical data. While sequencing IAV in wastewater was unable to distinguish if H5N1 detections were due to human or animal infections, it was able to provide clade-level information about H5N1 found in wastewater that could be useful in the future. Wastewater genomic surveillance can complement clinical surveillance, increasing ability to detect all circulating IAV subtypes and enhancing public health preparedness from a One Health perspective.

Journal Article↗

PubMed1995

Transmission maximum-likelihood reconstruction with ordered subsets for cone beam CT.

An iterative algorithm is presented for accelerated reconstruction of cone beam transmission CT data (CBCT). CBCT supplies an attenuation map for SPECT attenuation compensation and anatomical correlation. Iterative algorithms are necessary to reduce truncation artifacts and 3D reconstruction artifacts. An existing transmission maximum-likelihood algorithm (TRML) is accurate but the reconstruction time is too long. The new algorithm is a modified EM algorithm, based on ordered subsets (OSEM). OSEM was evaluated in comparison to TRML using a thorax phantom and a 3D Defrise phantom. A wide range of image measures were evaluated, including spatial resolution, noise, log likelihood, region quantification, truncation artifact removal, and 3D artifact removal. For appropriate subset size, OSEM produced essentially the same image as TRML, but required only one-tenth as many iterations. Thus, adequate images were available in two to four iterations (20-30 min on a SPARC 2 workstation). Further, OSEM still approximately maximizes likelihood: divergence occurs only for very high (and clinically irrelevant) iterations. Ordered subsets are likely to be useful in other geometries (fan and parallel) and for emission CT as well. Therefore, with ordered subsets, high-quality iterative reconstruction is now available in clinically practical reconstructions times.

Algorithms↗

PubMed1990

Counting algorithms for linkage.

The Lander-Green algorithm is algebraically different from the EM algorithm that maximizes likelihood. In our experience the numerical difference is very small. Since computations are no easier or convergence faster for the Lander-Green algorithm, there is no reason to prefer it to EM. As suggested by Green (personal communication), layering is advantageous. Occasional updating of the information weights might also be considered to accelerate mapping.

Algorithms↗

PubMed1989

Efficient computation of lod scores: genotype elimination, genotype redefinition, and hybrid maximum likelihood algorithms.

Calculation of multilocus lod scores presents challenging problems in numerical analysis, combinatories, programming, and genetics. It is possible to accelerate these computations by exploiting the simple pedigree structure of a CEPH-type pedigree consisting of a nuclear family plus all four grandparents. Lathrop et al. (1986) have done this by introducing likelihood factorization and transformation rules and Lander & Green (1987) by the method of 'hidden Markov chains'. The present paper explores an alternative approach based on genotype redefinition in the grandparents and systematic phase elimination in all pedigree members. All three approaches accelerate the computation of a single likelihood. Equally relevant to multilocus mapping are search strategies for finding the maximum likelihood estimates of recombination fractions. Hybrid algorithms that start with the EM algorithm and switch midway to quasi-Newton algorithms show promise. These issues are investigated in the context of a simulated 10 locus example. This same example allows us to illustrate a simple strategy for determining locus order.

Algorithms↗

PubMed1989

Applications of the expectation-maximization algorithm to quantal analysis of postsynaptic potentials.

The expectation-maximization (EM) algorithm is a robust method for maximum likelihood estimation of the parameters of an incompletely sampled distribution. It has been used to resolve the trial-to-trial amplitude fluctuations of postsynaptic potentials, when these are recorded in the presence of noise. Its use has however been limited by the need for different recursion equations for each set of conditions defined by the signal and noise processes. These equations are derived for the following conditions which arise in studies of synaptic transmission: non-gaussian noise process; quantal fluctuation; quantal variability. In addition, a constraint can be incorporated to accommodate simple and compound binomial models of transmitter release. Some advantages of these methods are illustrated by Monte Carlo simulations.

Algorithms↗

PubMed1986

Unbalanced repeated-measures models with structured covariance matrices.

The question of how to analyze unbalanced or incomplete repeated-measures data is a common problem facing analysts. We address this problem through maximum likelihood analysis using a general linear model for expected responses and arbitrary structural models for the within-subject covariances. Models that can be fit include standard univariate and multivariate models with incomplete data, random-effects models, and models with time-series and factor-analytic error structures. We describe Newton-Raphson and Fisher scoring algorithms for computing maximum likelihood estimates, and generalized EM algorithms for computing restricted and unrestricted maximum likelihood estimates. An example fitting several models to a set of growth data is included.

Algorithms↗

PubMed1992

Maximum-penalized-likelihood estimation for independent and Markov-dependent mixture models.

This paper concerns the use and implementation of maximum-penalized-likelihood procedures for choosing the number of mixing components and estimating the parameters in independent and Markov-dependent mixture models. Computation of the estimates is achieved via algorithms for the automatic generation of starting values for the EM algorithm. Computation of the information matrix is also discussed. Poisson mixture models are applied to a sequence of counts of movements by a fetal lamb in utero obtained by ultrasound. The resulting estimates are seen to provide plausible mechanisms for the physiological process.

Algorithms↗

PubMed1995

A fast and stable maximum a posteriori conjugate gradient reconstruction algorithm.

We have derived a maximum a posteriori (MAP) approach for iterative reconstruction based on a weighted least-squares conjugate gradient (WLS-CG) algorithm. The WLS-CG algorithm has been shown to have initial convergence rates up to 10x faster than the maximum-likelihood expectation maximization (ML-EM) algorithm, but WLS-CG suffers from rapidly increasing image noise at higher iteration numbers. In our MAP-CG algorithm, the increasing noise is controlled by a Gibbs smoothing prior, resulting in stable, convergent solutions. Our formulation assumes a Gaussian noise model for the likelihood function. When a linear transformation of the pixel space is performed (the "relaxation" acceleration method), the MAP-CG algorithm obtains a low-noise, stable solution (one that does not change with further iterations) in 10-30 iterations, compared to 100-200 iterations for MAP-EM. Each iteration of MAP-CG requires approximately the same amount of processing time as one iteration of ML-EM or MAP-EM. We show that the use of an initial image estimate obtained from a single iteration of the Chang method helps the algorithm to converge faster when acceleration is not used, but does not help when acceleration is applied. While both the WLS-CG and MAP-CG methods suffer from the potential for obtaining negative pixel values in the iterated image estimates, the use of the Gibbs prior substantially reduces the number of pixels with negative values and restricts them to regions of little or no activity. We use SPECT data from simulated hot-sphere phantoms and from patient studies to demonstrate the advantages of the MAP-CG algorithm. We conclude that the MAP-CG algorithm requires 10%-25% of the processing time of EM techniques, and provides images of comparable or superior quality.

Algorithms↗

PubMedDate not supplied

A maximum likelihood method for region-of-interest evaluation in emission tomography.

A maximum likelihood (ML) estimation method, called the ML-ROI algorithm, is presented for the calculation of region-of-interest (ROI) values from emission tomography scans. The EM algorithm is used to directly estimate ROI values from tomographic projection data given the location, size, and shape of all ROIs. The algorithm requires for the specification of a detailed model of the physical factors contributing to projection measurements including resolution and attenuation. The ML-ROI algorithm also provides an estimate of the variability of the ROI estimator (covariance matrix). The algorithm was tested with simulation and phantom data and compared with ROI estimation strategies using filtered backprojection (FBP) images. The ML-ROI estimates were unbiased, i.e., the partial volume effect was eliminated. Except for regions smaller than the detector resolution, the variability of the ML estimates was comparable to or less than the biased FBP estimators. Computation time for the ML-ROI algorithm was between 5 and 10 s/iteration. An evaluation of the sensitivity of the algorithm to misdefinition of the location and size of the ROIs was also performed.

Humans↗

PubMed1995

High diversity of alpha-globin haplotypes in a Senegalese population, including many previously unreported variants.

RFLP haplotypes at the alpha-globin gene complex have been examined in 190 individuals from the Niokolo Mandenka population of Senegal: haplotypes were assigned unambiguously for 210 chromosomes. The Mandenka share with other African populations a sample size-independent haplotype diversity that is much greater than that in any non-African population: the number of haplotypes observed in the Mandenka is typically twice that seen in the non-African populations sampled to date. Of these haplotypes, 17.3% had not been observed in any previous surveys, and a further 19.1% have previously been reported only in African populations. The haplotype distribution shows clear differences between African and non-African peoples, but this is on the basis of population-specific haplotypes combined with haplotypes common to all. The relationship of the newly reported haplotypes to those previously recorded suggests that several mutation processes, particularly recombination as homologous exchange or gene conversion, have been involved in their production. A computer program based on the expectation-maximization (EM) algorithm was used to obtain maximum-likelihood estimates of haplotype frequencies for the entire data set: good concordance between the unambiguous and EM-derived sets was seen for the overall haplotype frequencies. Some of the low-frequency haplotypes reported by the estimation algorithm differ greatly, in structure, from those haplotypes known to be present in human populations, and they may not represent haplotypes actually present in the sample.

Genetic Variation↗

PubMed1995

Empirical estimation of a distribution function with truncated and doubly interval-censored data and its application to AIDS studies.

In this paper we discuss the non-parametric estimation of a distribution function based on incomplete data for which the measurement origin of a survival time or the date of enrollment in a study is known only to belong to an interval. Also the survival time of interest itself is observed from a truncated distribution and is known only to lie in an interval. To estimate the distribution function, a simple self-consistency algorithm, a generalization of Turnbull's (1976, Journal of the Royal Statistical Association, Series B 38, 290-295) self-consistency algorithm, is proposed. This method is then used to analyze two AIDS cohort studies, for which direct use of the EM algorithm (Dempster, Laird and Rubin, 1976, Journal of the Royal Statistical Association, Series B 39, 1-38), which is computationally complicated, has previously been the usual method of the analysis.

Acquired Immunodeficiency Syndrome↗

PubMed1992

Estimating polygenic models for multivariate data on large pedigrees.

We have developed algorithms for the likelihood estimation of additive genetic models for quantitative traits on large pedigrees. The approach uses the expectation L-maximization (EM) algorithm, but avoids intensive computation. In this paper, we focus on extensions of previous work to the case of multivariate data. We exemplify the approach by analyses of bivariate data on a four-generation, 949-member pedigree of the snail Lymnaea elodes, and on a three-generation pedigree of the guppy Poecilia reticulata containing about 400 individuals.

Algorithms↗

PubMed1989

Stochastic models for heterogeneous DNA sequences.

The composition of naturally occurring DNA sequences is often strikingly heterogeneous. In this paper, the DNA sequence is viewed as a stochastic process with local compositional properties determined by the states of a hidden Markov chain. The model used is a discrete-state, discrete-outcome version of a general model for non-stationary time series proposed by Kitagawa (1987). A smoothing algorithm is described which can be used to reconstruct the hidden process and produce graphic displays of the compositional structure of a sequence. The problem of parameter estimation is approached using likelihood methods and an EM algorithm for approximating the maximum likelihood estimate is derived. The methods are applied to sequences from yeast mitochondrial DNA, human and mouse mitochondrial DNAs, a human X chromosomal fragment and the complete genome of bacteriophage lambda.

Base Sequence↗

PubMed2025

Hierarchical Multi-Label Classification With Gene-Environment Interactions in Disease Modeling.

In biomedical studies, gene-environment (G-E) interactions have been demonstrated to have important implications for analyzing disease outcomes beyond the main G and main E effects. Many approaches have been developed for G-E interaction analysis, yielding important findings. However, hierarchical multi-label classification, which provides insightful information on disease outcomes, remains unexplored in G-E analysis literature. Moreover, unlabeled data are commonly observed in practical settings but omitted by many existing methods of hierarchical multi-label classification. In this study, we consider a semi-supervised scenario and develop a novel approach for the two-layer hierarchical response with G-E interactions. A two-step penalized estimation is then proposed using an efficient expectation-maximization (EM) algorithm. Simulation shows that it has superior performance in classification and feature selection. The analysis of The Cancer Genome Atlas (TCGA) data on lung cancer demonstrates the practical utility of the proposed method. Overall, this study can fill the important knowledge gap in G-E interaction analysis by providing a widely applicable framework for hierarchical multi-label classification of complex disease outcomes.

Humans↗