Search PubMed⌕ Search

SEARCH · Search PubMed

Results for “EM algorithm”

Search indexed PubMed citations on genomics, clinical trials, systematic reviews and public health. Explore titles, authors and supplied subject terms, then open the PubMed record.

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

At least 235 records · Page 13Linked to original sources
PubMed2003

Mapping quantitative trait loci underlying triploid endosperm traits.

Endosperm, which is derived from two polar nuclei fusing with one sperm, is a triploid tissue in cereals. Endosperm tissue determines the grain quality of cereals. Improving grain quality is one of the important breeding objectives in cereals. However, current statistical methods for mapping quantitative trait loci (QTL) under diploid genetic control have not been effective for dealing with endosperm traits because of the complexity of their triploid inheritance. In this paper, we derive for the first time the conditional probabilities of F(3) endosperm QTL genotypes given different flanking marker genotypes in F(2) plants. Using these probabilities, we develop a multiple linear regression method implemented via the iteratively reweighted least-squares (IRWLS) algorithm and a maximum likelihood method (ML) implemented via the expectation-maximization (EM) algorithm to map QTL underlying endosperm traits. We use the mean value of endosperm traits of F(3) seeds as the dependent variable and the expectations of genotypic indicators for additive and dominance effect of a putative QTL flanked by a pair of markers as independent variables for IRWLS mapping. However, if an endosperm trait is measured quantitatively using a single endosperm sample, the ML mapping method can be used to separate the two dominance effects. Efficiency of the methods is verified through extensive Monte Carlo simulation studies. Results of simulation show that the proposed methods provide accurate estimates of both the QTL effects and locations with very high statistical power. With these methods, we are now ready to map endosperm traits, as we can for regular quantitative trait under diploid control.

Chromosome Mapping↗
PubMed2000

On the convergence of a clustering algorithm for protein-coding regions in microbial genomes.

MOTIVATION: As the number of fully sequenced prokaryotic genomes continues to grow rapidly, computational methods for reliably detecting protein-coding regions become even more important. Audic and Claverie (1998) Proc. Natl Acad. Sci. USA, 95, 10026-10031, have proposed a clustering algorithm for protein-coding regions in microbial genomes. The algorithm is based on three Markov models of order k associated with subsequences extracted from a given genome. The parameters of the three Markov models are recursively updated by the algorithm which, in simulations, always appear to converge to a unique stable partition of the genome. The partition corresponds to three kinds of regions: (1) coding on the direct strand, (2) coding on the complementary strand, (3) non-coding. RESULTS: Here we provide an explanation for the convergence of the algorithm by observing that it is essentially a form of the expectation maximization (EM) algorithm applied to the corresponding mixture model. We also provide a partial justification for the uniqueness of the partition based on identifiability. Other possible variations and improvements are briefly discussed.

Algorithms↗
PubMedDate not supplied

Finding the biologically optimal alignment of multiple sequences.

OBJECTIVE: Deterministic annealing, which is derived from statistical physics, is a method for obtaining the global optimum in parameter space. During the annealing process, starting from high temperatures which are then lowered, deterministic annealing deterministically find the (global) optimum at each temperature. Thus, deterministic annealing is expected to be more computationally efficient than stochastic sampling strategies to obtain the global optimum. We propose to apply the deterministic annealing technique to the problem of efficiently finding the biologically optimal alignment of multiple sequences. METHODS AND MATERIAL: We take a strategy based on probabilistic models for aligning multiple sequences. That is, we train a probabilistic model using given training sequences and obtain their alignment by parsing, i.e. searching for the most likely parse of each sequence and gaps using the trained parameters of the model. In this scenario, we propose a new stochastic model, which is simple enough to be suited to multiple sequence alignment and, unlike existing stochastic models, say a profile hidden Markov model (HMM), allows us to use similarity scores between symbols (or a symbol and a gap). We further present a learning algorithm for our simple model by combining deterministic annealing with an expectation-maximization (EM) algorithm. We emphasize that our approach is time-efficient, even if the training is done through an annealing process. RESULTS: In our experiments, we used actual protein sequences whose three-dimensional (3D) structures are determined and which are all aligned based on their 3D structures. We compared the results obtained by our approach with those by other existing approaches. Experimental results clearly showed that our approach gave the best performance, in terms of the similarity to the structurally determined alignment, among the approaches tested. Experimental results further indicated that our approach was ten times more efficient in terms of actual computation time than a competing method.

Algorithms↗
PubMed2002

Population differences in haplotype structure within a human olfactory receptor gene cluster.

We investigated the population differences in patterns of single nucleotide polymorphisms (SNPs) for a 400 kb olfactory receptor (OR) gene cluster on human chromosome 17p13.3. Samples were drawn from 35 individuals, of four different ethnogeographical origins: Pygmies, Bedouins, Yemenite Jews and Ashkenazi Jews. Of the 74 SNPs identified, two segregated between pseudogenized and intact ORs, while a third involved a change in a highly conserved motif proposed to mediate ligand-induced signal transduction. Linkage disequilibrium (LD) was computed based on phase inference across the cluster using Clark's haplotype subtraction algorithm. We also calculated LD directly from the genotypes using the expectation-maximization (EM) algorithm. Both methods yielded very similar results. Our analyses revealed substantial differences in nucleotide diversity, haplotype distribution and LD patterns among the different human populations. In particular, the two Jewish populations had low haplotype diversity and negligible decay of LD across the entire genomic region. Intriguingly, the three functional SNPs segregated at different frequencies in the different ethnogeographical groups, with the Pygmies having higher frequencies of the intact OR genes. Our data suggests that OR genes may have evolved to create different functional repertoires in distinct human populations.

Chromosomes, Human, Pair 17↗
PubMed2004

Learning mixture models with the regularized latent maximum entropy principle.

This paper presents a new approach to estimating mixture models based on a recent inference principle we have proposed: the latent maximum entropy principle (LME). LME is different from Jaynes' maximum entropy principle, standard maximum likelihood, and maximum aposteriori probability estimation. We demonstrate the LME principle by deriving new algorithms for mixture model estimation, and show how robust new variants of the expectation maximization (EM) algorithm can be developed. We show that a regularized version of LME (RLME), is effective at estimating mixture models. It generally yields better results than plain LME, which in turn is often better than maximum likelihood and maximum a posterior estimation, particularly when inferring latent variable models from small amounts of data.

Algorithms↗
PubMed2001

Stochastic organization of output codes in multiclass learning problems.

The best-known decomposition schemes of multiclass learning problems are one per class coding (OPC) and error-correcting output coding (ECOC). Both methods perform a prior decomposition, that is, before training of the classifier takes place. The impact of output codes on the inferred decision rules can be experienced only after learning. Therefore, we present a novel algorithm for the code design of multiclass learning problems. This algorithm applies a maximum-likelihood objective function in conjunction with the expectation-maximization (EM) algorithm. Minimizing the augmented objective function yields the optimal decomposition of the multiclass learning problem in two-class problems. Experimental results show the potential gain of the optimized output codes over OPC or ECOC methods.

Algorithms↗
PubMed2004

Depth-variant maximum-likelihood restoration for three-dimensional fluorescence microscopy.

We derive an algorithm for maximum-likelihood image estimation on the basis of the expectation-maximization (EM) formalism by using a new approximate model for depth-varying image formation for optical sectioning microscopy. This new strata-based model incorporates spherical aberration that worsens as the microscope is focused deeper under the cover slip and is the result of the refractive-index mismatch between the immersion medium and the mounting medium of the specimen. Images of a specimen with known geometry and refractive index show that the model captures the main features of the image. We analyze the performance of the depth-variant EM algorithm with simulations, which show that the algorithm can compensate for image degradation changing with depth.

Algorithms↗
PubMed1997

[An improved ISRA algorithm for ECT].

Image space reconstruction algorithm (ISRA) is a new kind of method for ECT reconstruction. Unlike the ML-EM algorithm which maximizes likelihood function of Possion distribution, ISRA searches for the minimum non-negative mean square solution. In this paper, an improved ISRA (IISRA) algorithm is proposed. A comparison between the algorithms (ISRA and IISRA) demonstrates that the result of IISRA is closer to the test image than that of ISRA. In addition, the IIRSA inherits some properties of ISRA such as convergence.

Algorithms↗
PubMed1999

Applying the Cox proportional hazards model for analysis of latency data with interval censoring.

The latency time of an infectious disease is defined as the time from infection to disease onset. This paper applies the proportional hazards model to estimate the effect of covariates on latency when the time of disease onset is exact or right-censored but the time of infection is interval-censored. We use a Monte Carlo EM algorithm to estimate parameters of the joint distribution of infection times and latency times. At each EM iteration, exact infection times are multiply imputed from the density determined by the parameters of the infection and latency time distributions. The methodology is tested using a simulation study and is applied to data from a cohort of haemophiliacs with HIV disease.

Algorithms↗
PubMed1997

Grouped-coordinate ascent algorithms for penalized-likelihood transmission image reconstruction.

This paper presents a new class of algorithms for penalized-likelihood reconstruction of attenuation maps from low-count transmission scans. We derive the algorithms by applying to the transmission log-likelihood a version of the convexity technique developed by De Pierro for emission tomography. The new class includes the single-coordinate ascent (SCA) algorithm and Lange's convex algorithm for transmission tomography as special cases. The new grouped-coordinate ascent (GCA) algorithms in the class overcome several limitations associated with previous algorithms. 1) Fewer exponentiations are required than in the transmission maximum likelihood-expectation maximization (ML-EM) algorithm or in the SCA algorithm. 2) The algorithms intrinsically accommodate nonnegativity constraints, unlike many gradient-based methods. 3) The algorithms are easily parallelizable, unlike the SCA algorithm and perhaps line-search algorithms. We show that the GCA algorithms converge faster than the SCA algorithm, even on conventional workstations. An example from a low-count positron emission tomography (PET) transmission scan illustrates the method.

Algorithms↗
PubMed2005

A shared response model for clustered binary data in developmental toxicity studies.

Existing distributions for modeling fetal response data in developmental toxicology such as the beta-binomial distribution have a tendency of inflating the probability of no malformed fetuses, and hence understating the risk of having at least one malformed fetus within a litter. As opposed to a shared probability extra-binomial model, we advocate a shared response model that allows a random number of fetuses within the same litter to share a common response. An explicit formula is given for the probability function and graphical plots suggest that it does not suffer from the problem of assigning too much probability to the event of no malformed fetuses. The EM algorithm can be used to estimate the model parameters. Results of a simulation study show that the EM estimates are nearly unbiased and the associated confidence intervals based on the usual standard error estimates have coverage close to the nominal level. Simulation results also suggest that the shared response model estimates of the marginal malformation probabilities are robust to misspecification of the distributional form, but not so for the estimates of intralitter correlation and the litter-level probability of having at least one malformed fetus. The proposed model is fitted to a set of data from the U.S. National Toxicology Program. For the same dose-response relationship, the fit based on the shared response distribution is superior to that based on the beta-binomial, and comparable to that based on the recently proposed q-power distribution (Kuk, 2004, Applied Statistics53, 369-386). An advantage of the shared response model over the q-power distribution is that it is more interpretable and can be extended more easily to the multivariate case. To illustrate this, a bivariate shared response model is fitted to fetal response data involving visceral and skeletal malformation.

2,4,5-Trichlorophenoxyacetic Acid↗
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↗
PubMed2005

A comparison of algorithms for inference and learning in probabilistic graphical models.

Research into methods for reasoning under uncertainty is currently one of the most exciting areas of artificial intelligence, largely because it has recently become possible to record, store, and process large amounts of data. While impressive achievements have been made in pattern classification problems such as handwritten character recognition, face detection, speaker identification, and prediction of gene function, it is even more exciting that researchers are on the verge of introducing systems that can perform large-scale combinatorial analyses of data, decomposing the data into interacting components. For example, computational methods for automatic scene analysis are now emerging in the computer vision community. These methods decompose an input image into its constituent objects, lighting conditions, motion patterns, etc. Two of the main challenges are finding effective representations and models in specific applications and finding efficient algorithms for inference and learning in these models. In this paper, we advocate the use of graph-based probability models and their associated inference and learning algorithms. We review exact techniques and various approximate, computationally efficient techniques, including iterated conditional modes, the expectation maximization (EM) algorithm, Gibbs sampling, the mean field method, variational techniques, structured variational techniques and the sum-product algorithm ("loopy" belief propagation). We describe how each technique can be applied in a vision model of multiple, occluding objects and contrast the behaviors and performances of the techniques using a unifying cost function, free energy.

Algorithms↗
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↗
PubMed2003

Using the expectation maximization algorithm to estimate coefficient alpha for scales with item-level missing data.

A 2-step approach for obtaining internal consistency reliability estimates with item-level missing data is outlined. In the 1st step, a covariance matrix and mean vector are obtained using the expectation maximization (EM) algorithm. In the 2nd step, reliability analyses are carried out in the usual fashion using the EM covariance matrix as input. A Monte Carlo simulation examined the impact of 6 variables (scale length, response categories, item correlations, sample size, missing data, and missing data technique) on 3 different outcomes: estimation bias, mean errors, and confidence interval coverage. The 2-step approach using EM consistently yielded the most accurate reliability estimates and produced coverage rates close to the advertised 95% rate. An easy method of implementing the procedure is outlined.

Algorithms↗
PubMed2004

Use of runs statistics for pattern recognition in genomic DNA sequences.

In this article, the use of the finite Markov chain imbedding (FMCI) technique to study patterns in DNA under a hidden Markov model (HMM) is introduced. With a vision of studying multiple runs-related statistics simultaneously under an HMM through the FMCI technique, this work establishes an investigation of a bivariate runs statistic under a binary HMM for DNA pattern recognition. An FMCI-based recursive algorithm is derived and implemented for the determination of the exact distribution of this bivariate runs statistic under an independent identically distributed (IID) framework, a Markov chain (MC) framework, and a binary HMM framework. With this algorithm, we have studied the distributions of the bivariate runs statistic under different binary HMM parameter sets; probabilistic profiles of runs are created and shown to be useful for trapping HMM maximum likelihood estimates (MLEs). This MLE-trapping scheme offers good initial estimates to jump-start the expectation-maximization (EM) algorithm in HMM parameter estimation and helps prevent the EM estimates from landing on a local maximum or a saddle point. Applications of the bivariate runs statistic and the probabilistic profiles in conjunction with binary HMMs for pattern recognition in genomic DNA sequences are illustrated via case studies on DNA bendability signals using human DNA data.

Algorithms↗
PubMed2004

Haplotype block partitioning and tag SNP selection using genotype data and their applications to association studies.

Recent studies have revealed that linkage disequilibrium (LD) patterns vary across the human genome with some regions of high LD interspersed by regions of low LD. A small fraction of SNPs (tag SNPs) is sufficient to capture most of the haplotype structure of the human genome. In this paper, we develop a method to partition haplotypes into blocks and to identify tag SNPs based on genotype data by combining a dynamic programming algorithm for haplotype block partitioning and tag SNP selection based on haplotype data with a variation of the expectation maximization (EM) algorithm for haplotype inference. We assess the effects of using either haplotype or genotype data in haplotype block identification and tag SNP selection as a function of several factors, including sample size, density or number of SNPs studied, allele frequencies, fraction of missing data, and genotyping error rate, using extensive simulations. We find that a modest number of haplotype or genotype samples will result in consistent block partitions and tag SNP selection. The power of association studies based on tag SNPs using genotype data is similar to that using haplotype data.

Algorithms↗
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↗