Search PubMed⌕ Search

SEARCH · Search PubMed

Results for “Markov Chain”

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 127 records · Page 7Linked to original sources
PubMed2005

Modeling haplotype block variation using Markov chains.

Models of background variation in genomic regions form the basis of linkage disequilibrium mapping methods. In this work we analyze a background model that groups SNPs into haplotype blocks and represents the dependencies between blocks by a Markov chain. We develop an error measure to compare the performance of this model against the common model that assumes that blocks are independent. By examining data from the International Haplotype Mapping project, we show how the Markov model over haplotype blocks is most accurate when representing blocks in strong linkage disequilibrium. This contrasts with the independent model, which is rendered less accurate by linkage disequilibrium. We provide a theoretical explanation for this surprising property of the Markov model and relate its behavior to allele diversity.

Chromosome Mapping↗
PubMed2007

Reversible jump Markov chain Monte Carlo for deconvolution.

To solve the problem of estimating an unknown input function to a linear time invariant system we propose an adaptive non-parametric method based on reversible jump Markov chain Monte Carlo (RJMCMC). We use piecewise polynomial functions (splines) to represent the input function. The RJMCMC algorithm allows the exploration of a large space of competing models, in our case the collection of splines corresponding to alternative positions of breakpoints, and it is based on the specification of transition probabilities between the models. RJMCMC determines: the number and the position of the breakpoints, and the coefficients determining the shape of the spline, as well as the corresponding posterior distribution of breakpoints, number of breakpoints, coefficients and arbitrary statistics of interest associated with the estimation problem. Simulation studies show that the RJMCMC method can obtain accurate reconstructions of complex input functions, and obtains better results compared with standard non-parametric deconvolution methods. Applications to real data are also reported.

Algorithms↗
PubMed1999

Significance testing of clinical data using virus dynamics models with a Markov chain Monte Carlo method: application to emergence of lamivudine-resistant hepatitis B virus.

Bayesian analysis using a virus dynamics model is demonstrated to facilitate hypothesis testing of patterns in clinical time-series. Our Markov chain Monte Carlo implementation demonstrates that the viraemia time-series observed in two sets of hepatitis B patients on antiviral (lamivudine) therapy, chronic carriers and liver transplant patients, are significantly different, overcoming clinical trial design differences that question the validity of non-parametric tests. We show that lamivudine-resistant mutants grow faster in transplant patients than in chronic carriers, which probably explains the differences in emergence times and failure rates between these two sets of patients. Incorporation of dynamic models into Bayesian parameter analysis is of general applicability in medical statistics.

Antiviral Agents↗
PubMed2004

Parallel Metropolis coupled Markov chain Monte Carlo for Bayesian phylogenetic inference.

MOTIVATION: Bayesian estimation of phylogeny is based on the posterior probability distribution of trees. Currently, the only numerical method that can effectively approximate posterior probabilities of trees is Markov chain Monte Carlo (MCMC). Standard implementations of MCMC can be prone to entrapment in local optima. Metropolis coupled MCMC [(MC)(3)], a variant of MCMC, allows multiple peaks in the landscape of trees to be more readily explored, but at the cost of increased execution time. RESULTS: This paper presents a parallel algorithm for (MC)(3). The proposed parallel algorithm retains the ability to explore multiple peaks in the posterior distribution of trees while maintaining a fast execution time. The algorithm has been implemented using two popular parallel programming models: message passing and shared memory. Performance results indicate nearly linear speed improvement in both programming models for small and large data sets.

Algorithms↗
PubMed2003

Evolution of probability measures by cellular automata on algebraic topological Markov chains.

In this paper we review some recent results on the evolution of probability measures under cellular automata acting on a fullshift. In particular we discuss the crucial role of the attractiveness of maximal measures. We enlarge the context of the results of a previous study of topological Markov chains that are Abelian groups; the shift map is an automorphism of this group. This is carried out by studying the dynamics of Markov measures by a particular additive cellular automata. Many of these topics were within the focus of Francisco Varela's mathematical interests.

Animals↗
PubMed2006

A reversible jump Markov chain Monte Carlo algorithm for bacterial promoter motifs discovery.

Effective probabilistic modeling approaches have been developed to find motifs of biological function in DNA sequences. However, the problem of automated model choice remains largely open and becomes more essential as the number of sequences to be analyzed is constantly increasing. Here we propose a reversible jump Markov chain Monte Carlo algorithm for estimating both parameters and model dimension of a Bayesian hidden semi-Markov model dedicated to bacterial promoter motif discovery. Bacterial promoters are complex motifs composed of two boxes separated by a spacer of variable but constrained length and occurring close to the protein translation start site. The algorithm allows simultaneous estimations of the width of the boxes, of the support size of the spacer length distribution, and of the order of the Markovian model used for the "background" nucleotide composition. The application of this method on three sequence sets points out the good behavior of the algorithm and the biological relevance of the estimated promoter motifs.

Algorithms↗
PubMed2006

Effective p-value computations using Finite Markov Chain Imbedding (FMCI): application to local score and to pattern statistics.

The technique of Finite Markov Chain Imbedding (FMCI) is a classical approach to complex combinatorial problems related to sequences. In order to get efficient algorithms, it is known that such approaches need to be first rewritten using recursive relations. We propose here to give here a general recursive algorithms allowing to compute in a numerically stable manner exact Cumulative Distribution Function (CDF) or complementary CDF (CCDF). These algorithms are then applied in two particular cases: the local score of one sequence and pattern statistics. In both cases, asymptotic developments are derived. For the local score, our new approach allows for the very first time to compute exact p-values for a practical study (finding hydrophobic segments in a protein database) where only approximations were available before. In this study, the asymptotic approximations appear to be completely unreliable for 99.5% of the considered sequences. Concerning the pattern statistics, the new FMCI algorithms dramatically outperform the previous ones as they are more reliable, easier to implement, faster and with lower memory requirements.

Journal Article↗
PubMed2005

Comparison of marker types and map assumptions using Markov chain Monte Carlo-based linkage analysis of COGA data.

We performed multipoint linkage analysis of the electrophysiological trait ECB21 on chromosome 4 in the full pedigrees provided by the Collaborative Study on the Genetics of Alcoholism (COGA). Three Markov chain Monte Carlo (MCMC)-based approaches were applied to the provided and re-estimated genetic maps and to five different marker panels consisting of microsatellite (STRP) and/or SNP markers at various densities. We found evidence of linkage near the GABRB1 STRP using all methods, maps, and marker panels. Difficulties encountered with SNP panels included convergence problems and demanding computations.

Alcoholism↗
PubMed1988

A Markov chain for calculating the durability of marriage.

"The usual Markov model of marriage permits informative experiments on the effect of alterations in the transition rules. It can tell, for example, what difference it would make to the durability of marriage if there was no divorce and the other transitions were as observed. This is in addition to the capacity of the usual model to find the effect of small changes in the transition rates. Canadian data for 1970-1982 permit comparisons over time, and show among other things not only that married men live longer than single, but that the difference is increasing; the increase in the 'marriage bonus' over time also appears for women." (SUMMARY IN FRE)

Americas↗
PubMed2004

Markov-modulated Markov chains and the covarion process of molecular evolution.

The covarion (or site specific rate variation, SSRV) process of biological sequence evolution is a process by which the evolutionary rate of a nucleotide/amino acid/codon position can change in time. In this paper, we introduce time-continuous, space-discrete, Markov-modulated Markov chains as a model for representing SSRV processes, generalizing existing theory to any model of rate change. We propose a fast algorithm for diagonalizing the generator matrix of relevant Markov-modulated Markov processes. This algorithm makes phylogeny likelihood calculation tractable even for a large number of rate classes and a large number of states, so that SSRV models become applicable to amino acid or codon sequence datasets. Using this algorithm, we investigate the accuracy of the discrete approximation to the Gamma distribution of evolutionary rates, widely used in molecular phylogeny. We show that a relatively large number of classes is required to achieve accurate approximation of the exact likelihood when the number of analyzed sequences exceeds 20, both under the SSRV and among site rate variation (ASRV) models.

Algorithms↗
PubMed2003

Markov chain Monte Carlo without likelihoods.

Many stochastic simulation approaches for generating observations from a posterior distribution depend on knowing a likelihood function. However, for many complex probability models, such likelihoods are either impossible or computationally prohibitive to obtain. Here we present a Markov chain Monte Carlo method for generating observations from a posterior distribution without the use of likelihoods. It can also be used in frequentist applications, in particular for maximum-likelihood estimation. The approach is illustrated by an example of ancestral inference in population genetics. A number of open problems are highlighted in the discussion.

Algorithms↗
PubMed2003

Detecting recombination in 4-taxa DNA sequence alignments with Bayesian hidden Markov models and Markov chain Monte Carlo.

This article presents a statistical method for detecting recombination in DNA sequence alignments, which is based on combining two probabilistic graphical models: (1) a taxon graph (phylogenetic tree) representing the relationship between the taxa, and (2) a site graph (hidden Markov model) representing interactions between different sites in the DNA sequence alignments. We adopt a Bayesian approach and sample the parameters of the model from the posterior distribution with Markov chain Monte Carlo, using a Metropolis-Hastings and Gibbs-within-Gibbs scheme. The proposed method is tested on various synthetic and real-world DNA sequence alignments, and we compare its performance with the established detection methods RECPARS, PLATO, and TOPAL, as well as with two alternative parameter estimation schemes.

Base Sequence↗
PubMed2006

Multilocus association mapping using variable-length Markov chains.

I propose a new method for association-based gene mapping that makes powerful use of multilocus data, is computationally efficient, and is straightforward to apply over large genomic regions. The approach is based on the fitting of variable-length Markov chain models, which automatically adapt to the degree of linkage disequilibrium (LD) between markers to create a parsimonious model for the LD structure. Edges of the fitted graph are tested for association with trait status. This approach can be thought of as haplotype testing with sophisticated windowing that accounts for extent of LD to reduce degrees of freedom and number of tests while maximizing information. I present analyses of two published data sets that show that this approach can have better power than single-marker tests or sliding-window haplotypic tests.

Chromosome Mapping↗
PubMed2006

A Markov chain Monte Carlo method for estimating population mixing using Y-chromosome markers: mixing of the Han people in China.

We present a new approach for estimating mixing between populations based on non-recombining markers, specifically Y-chromosome microsatellites. A Markov chain Monte Carlo (MCMC) Bayesian statistical approach is used to calculate the posterior probability distribution of population parameters of interest, including the effective population size and the time to most recent common ancestor (MRCA). To test whether two populations are homogeneously mixed we introduce a "mixing" statistic defined for each coalescent event that weights the contribution of that ancestor's descendants to the two subpopulations, and an associated population "purity" statistic. Using simulated data with low levels of migration between two populations, we demonstrate that our method is more sensitive than other commonly used distance-based methods such as R(ST) and D(SW). To illustrate our method, we analysed mixing between 11 pre-defined Chinese ethnic/regional populations, using 5 microsatellite markers from the non-recombining region of the Y-chromosome (NRY), demonstrating a significant clustering of a subset of subpopulations with a high mutual relative degree of mixing (homogeneous mixing with support >0.99). Our analysis suggests that there is a strong correlation between effective population size and mixing with other subpopulations. Thus, despite considerable mixing between these groups, the purity statistic still identifies significant heterogeneity, suggesting that periods of historical isolation continue to leave a recoverable signal despite modern introgression.

Asian People↗
PubMed1987

The use of Markov chains to detect subtle variation in reproductive cycling.

Certain reproductive parameters in animals are particularly sensitive endpoints in toxicological experiments. Measured changes in one of these endpoints, estrous cycling in the rat, can reflect aberration in the underlying hormonal environment or end organ response. This article proposes the use of Markov chains to measure subtle changes in estrous cycling not readily detectable by standard methods of analysis.

Aging↗
PubMed2003

Dynamical properties of strongly interacting Markov chains.

Spatial interdependences of multiple stochastic units can be suitably quantified by the Kullback-Leibler divergence of the joint probability distribution from the corresponding factorized distribution. In the present paper, a generalized measure for stochastic interaction, which also captures temporal interdependences, is analysed within the setting of Markov chains. The dynamical properties of systems with strongly interacting stochastic units are analytically studied and illustrated by computer simulations. In particular, the emergence of determinism in such systems is demonstrated.

Computer Simulation↗
PubMed2001

Competing risks analysis using Markov chains: impact of cerebrovascular and ischaemic heart disease in cancer mortality.

BACKGROUND: A decrease in cerebrovascular disease (CVD) and ischaemic heart disease (IHD) mortality can produce an increase in mortality from other causes, even cancer. This problem is called the competing risks problem. METHODS: A Markov chain is used to analyse the interrelation between CVD, IHD and cancer mortalities in Spanish women in 1981 and 1994. We compare the results using two models: discarding CVD and IHD mortality (the elimination model) and substituting CVD and IHD 1981 mortality rates in 1994 figures (the constant model). RESULTS: Removing mortality from CVD and IHD increases cancer mortality rates in women aged > or = 70, and the probability of death from cancer rises from 10.7% to 13.3%. In the second model, the use of CVD and IHD 1981 mortality rates in 1994 data yields slightly lower mortality rates and so the impact of CVD and IHD mortality changes in the period 1981 to 1994 is negligible except in elderly women. CONCLUSIONS: Although IHD and CVD mortality have decreased in all age groups of Spanish women from 1981 to 1994, this has not had a great impact on cancer mortality.

Adult↗
PubMed1990

Exact computation of pattern probabilities in random sequences generated by Markov chains.

Observed patterns in macromolecular sequences are often considered as words and compared with their probabilities of occurring in random sequences. Calculation of these probabilities, however, often lacks rigour. We have developed an algorithm for exact computation of such probabilities for stochastic sequences that follow a Markov chain model. The method is applicable to the case that a random sequence contains one out of two given patterns P and Q, or both simultaneously. Another application yields the probability function P(x) that a sequence contains pattern P exactly x times. An application to patterns that include wild-card characters yields probabilities for homonucleotide clusters of a given length. We prove the probability of multiple runs of single nucleotides in the SV40 genome to be in accordance with the dinucleotide composition of the sequence, although it is in conflict with mononucleotide composition.

Algorithms↗