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

Bayesian models and Markov chain Monte Carlo methods for protein motifs with the secondary characteristics.

Statistical methods have been developed for finding local patterns, also called motifs, in multiple protein sequences. The aligned segments may imply functional or structural core regions. However, the existing methods often have difficulties in aligning multiple proteins when sequence residue identities are low (e.g., less than 25%). In this article, we develop a Bayesian model and Markov chain Monte Carlo (MCMC) methods for identifying subtle motifs in protein sequences. Specifically, a motif is defined not only in terms of specific sites characterized by amino acid frequency vectors, but also as a combination of secondary characteristics such as hydrophobicity, polarity, etc. Markov chain Monte Carlo methods are proposed to search for a motif pattern with high posterior probability under the new model. A special MCMC algorithm is developed, involving transitions between state spaces of different dimensions. The proposed methods were supported by a simulated study. It was then tested by two real datasets, including a group of helix-turn-helix proteins, and one set from the CATH Protein Structure Classification Database. Statistical comparisons showed that the new approach worked better than a typical Gibbs sampling approach which is based only on an amino acid model.

Amino Acid Motifs↗
PubMed1999

A Markov chain model to assess the efficacy of screening for non-insulin dependent diabetes mellitus (NIDDM).

BACKGROUND: The high prevalence and severe consequences of non-insulin dependent diabetes mellitus (NIDDM) in Taiwan calls for urgent measures to detect this disease in the asymptomatic phase. However, the efficacy of early detection of NIDDM is highly dependent on its natural history from the disease-free state, through the asymptomatic to the symptomatic phase and death from NIDDM or other causes. METHODS: In order to project the above progression, a five-state illness-and-death Markov chain model was proposed to estimate these transition parameters using data from two rounds of a blood sugar screening programme for NIDDM in Puli, in central Taiwan. RESULTS: Results showed that the annual incidence for asymptomatic NIDDM was 10.67 per 1000 (95% CI: 8.26-13.79) and the average duration between the asymptomatic and symptomatic phases (the sojourn time) was 8 years (95%CI: 5.74-11.29). The 10-year survival rate for asymptomatic NIDDM (79.35%) was better than that for symptomatic NIDDM (69.45%). Prediction of deaths from NIDDM was performed to assess how the efficacy of screening for NIDDM varied by different screening frequencies (annual, biennial, 4-yearly and the control group). Results indicated there is no substantial difference in mortality reduction from NIDDM among the annual, biennial and 4-yearly screening regimens. However, a 4-yearly screening regimen significantly reduced deaths from NIDDM by 40% (95% CI: 26-51%). CONCLUSIONS: A long sojourn time and the substantial reduction in mortality suggest that a 4-yearly screening regime for NIDDM would be most effective and feasible in Taiwan. The proposed five-state Markov chain model can be applied to other similar NIDDM screening projects.

Adolescent↗
PubMed1992

The application of Markov chain analysis to oligonucleotide frequency prediction and physical mapping of Drosophila melanogaster.

Here we compare several methods for predicting oligonucleotide frequencies in 691 kb of Drosophila melanogaster DNA. As in previous work on Escherichia coli and Saccharomyces cerevisiae, a relatively simple equation based on tetranucleotide frequencies can be used in predicting frequencies of higher order oligonucleotides. For example, the mean of observed/expected abundances of 4,096 hexamers was 1.07 with a sample standard deviation of .55. This simple predictor arises by considering each base on the sense strand of D. melanogaster to depend only on the three bases 5' to it (a 3rd order Markov chain) and is more accurate than the random predictor. This equation is useful in predicting restriction enzyme fragment sizes, selecting restriction enzymes that cut preferentially in coding vs noncoding regions, and in selecting probes to fingerprint clones in contig mapping. Once again, this equation well predicts the occurrence of higher order oligonucleotides, supporting our hypothesis that this predictor holds in evolutionarily diverse organisms. When ranked from highest to lowest abundance, the observed frequencies of oligomers of a given length are closely tracked by the predicted abundances of a 3rd order Markov chain. Through use of the dependence of oligomer frequencies on base composition, we report a list of oligomers that will be useful for the completion of a cosmid physical map of D. melanogaster. Presently, the library is such that it will be possible to construct large contigs using only 30 oligonucleotide probes to fingerprint cosmids.

Animals↗
PubMed2002

Identifying transcription factor binding sites through Markov chain optimization.

Even though every cell in an organism contains the same genetic material, each cell does not express the same cohort of genes. Therefore, one of the major problems facing genomic research today is to determine not only which genes are differentially expressed and under what conditions, but also how the expression of those genes is regulated. The first step in determining differential gene expression is the binding of sequence-specific DNA binding proteins (i.e. transcription factors) to regulatory regions of the genes (i.e. promoters and enhancers). An important aspect to understanding how a given transcription factor functions is to know the entire gamut of binding sites and subsequently potential target genes that the factor may bind/regulate. In this study, we have developed a computer algorithm to scan genomic databases for transcription factor binding sites, based on a novel Markov chain optimization method, and used it to scan the human genome for sites that bind to hepatocyte nuclear factor 4 alpha (HNF4alpha). A list of 71 known HNF4alpha binding sites from the literature were used to train our Markov chain model. By looking at the window of 600 nucleotides around the transcription start site of each confirmed gene on the human genome, we identified 849 sites with varying binding potential and experimentally tested 109 of those sites for binding to HNF4alpha. Our results show that the program was very successful in identifying 77 new HNF4alpha binding sites with varying binding affinities (i.e. a 71% success rate). Therefore, this computational method for searching genomic databases for potential transcription factor binding sites is a powerful tool for investigating mechanisms of differential gene regulation.

Algorithms↗
PubMed2005

Markov Chain modeling of pyelonephritis-associated pili expression in uropathogenic Escherichia coli.

Pyelonephritis-associated pili (Pap) expression in uropathogenic Escherichia coli is regulated by a complex phase variation mechanism involving the competition between leucine-responsive regulatory protein (Lrp) and DNA adenine methylase (Dam). Population dynamics of pap gene expression has been studied extensively and the detailed molecular mechanism has been largely elucidated, providing sufficient information for mathematical modeling. Although the Gillespie algorithm is suited for modeling of stochastic systems such as the pap operon, it becomes computationally expensive when detailed molecular steps are explicitly modeled in a population. Here we developed a Markov Chain model to simplify the computation. Our model is analytically derived from the molecular mechanism. The model presented here is able to reproduce results presented using the Gillespie method, but since the regulatory information is incorporated before simulation, our model runs more efficiently and allows investigation of additional regulatory features. The model predictions are consistent with experimental data obtained in this work and in the literature. The results show that pap expression in uropathogenic E. coli is initial-state-dependent, as previously reported. However, without environment stimuli, the pap-expressing fraction in a population will reach an equilibrium level after approximately 50-100 generations. The transient time before reaching equilibrium is determined by PapI stability and Lrp and Dam copy numbers per cell. This work demonstrates that the Markov Chain model captures the essence of the complex molecular mechanism and greatly simplifies the computation.

Algorithms↗
PubMed2002

An example of complex modelling in dentistry using Markov chain Monte Carlo (MCMC) simulation.

BACKGROUND: In the usual regression setting one regression line is computed for a whole data set. In a more complex situation, each person may be observed for example at several points in time and thus a regression line might be calculated for each person. Additional complexities, such as various forms of errors in covariables may make a straightforward statistical evaluation difficult or even impossible. OBJECTIVE AND METHOD: During recent years methods have been developed allowing convenient analysis of problems where the data and the corresponding models show these and many other forms of complexity. The methodology makes use of a Bayesian approach and Markov chain Monte Carlo (MCMC) simulations. The methods allow the construction of increasingly elaborate models by building them up from local sub-models. The essential structure of the models can be represented visually by directed acyclic graphs (DAG). This attractive property allows communication and discussion of the essential structure and the substantial meaning of a complex model without needing algebra. EXAMPLE: After presentation of the statistical methods an example from dentistry is presented in order to demonstrate their application and use. The dataset of the example had a complex structure; each of a set of children was followed up over several years. The number of new fillings in permanent teeth had been recorded at several ages. The dependent variables were markedly different from the normal distribution and could not be transformed to normality. In addition, explanatory variables were assumed to be measured with different forms of error. Illustration of how the corresponding models can be estimated conveniently via MCMC simulation, in particular, 'Gibbs sampling', using the freely available software BUGS is presented. In addition, how the measurement error may influence the estimates of the corresponding coefficients is explored. It is demonstrated that the effect of the independent variable on the dependent variable may be markedly underestimated if the measurement error is not taken into account ('regression dilution bias'). CONCLUSION: Markov chain Monte Carlo methods may be of great value to dentists in allowing analysis of data sets which exhibit a wide range of different forms of complexity.

Bayes Theorem↗
PubMed1999

A study of deleterious gene structure in plants using Markov chain Monte Carlo.

The characteristics of deleterious genes have been of great interest in both theory and practice in genetics. Because of the complex genetic mechanism of these deleterious genes, most current studies try to estimate the overall magnitude of mortality effects on a population, which is characterized classically by the number of lethal equivalents. This number is a combination of several parameters, each of which has a distinct biological effect on genetic mortality. In conservation and breeding programs, it is important to be able to distinguish among different combinations of these parameters that lead to the same number of lethal equivalents, such as a large number of mildly deleterious genes or a few lethal genes, The ability to distinguish such parameter combinations requires more than one generation of mating. We propose a model for survival data from a two-generation mating experiment on the plant species Brassica rapa, and we enable inference with Markov chain Monte Carlo. This computational strategy is effective because a vast amount of missing genotype information must be accounted for. In addition to the lethal equivalents, the two-generation data provide separate information on the average intensity of mortality and the average number of deleterious genes carried by an individual. In our Markov chain Monte Carlo algorithm, we use a vector proposal distribution to overcome inefficiency of a single-site Gibbs sampler. Information about environmental effects is obtained from an outcrossing experiment conducted in parallel with the two-generation mating experiments.

Algorithms↗
PubMed2005

A Markov chain Monte Carlo technique for identification of combinations of allelic variants underlying complex diseases in humans.

In recent years, the number of studies focusing on the genetic basis of common disorders with a complex mode of inheritance, in which multiple genes of small effect are involved, has been steadily increasing. An improved methodology to identify the cumulative contribution of several polymorphous genes would accelerate our understanding of their importance in disease susceptibility and our ability to develop new treatments. A critical bottleneck is the inability of standard statistical approaches, developed for relatively modest predictor sets, to achieve power in the face of the enormous growth in our knowledge of genomics. The inability is due to the combinatorial complexity arising in searches for multiple interacting genes. Similar "curse of dimensionality" problems have arisen in other fields, and Bayesian statistical approaches coupled to Markov chain Monte Carlo (MCMC) techniques have led to significant improvements in understanding. We present here an algorithm, APSampler, for the exploration of potential combinations of allelic variations positively or negatively associated with a disease or with a phenotype. The algorithm relies on the rank comparison of phenotype for individuals with and without specific patterns (i.e., combinations of allelic variants) isolated in genetic backgrounds matched for the remaining significant patterns. It constructs a Markov chain to sample only potentially significant variants, minimizing the potential of large data sets to overwhelm the search. We tested APSampler on a simulated data set and on a case-control MS (multiple sclerosis) study for ethnic Russians. For the simulated data, the algorithm identified all the phenotype-associated allele combinations coded into the data and, for the MS data, it replicated the previously known findings.

Algorithms↗
PubMed2004

Bayesian phylogenetic model selection using reversible jump Markov chain Monte Carlo.

A common problem in molecular phylogenetics is choosing a model of DNA substitution that does a good job of explaining the DNA sequence alignment without introducing superfluous parameters. A number of methods have been used to choose among a small set of candidate substitution models, such as the likelihood ratio test, the Akaike Information Criterion (AIC), the Bayesian Information Criterion (BIC), and Bayes factors. Current implementations of any of these criteria suffer from the limitation that only a small set of models are examined, or that the test does not allow easy comparison of non-nested models. In this article, we expand the pool of candidate substitution models to include all possible time-reversible models. This set includes seven models that have already been described. We show how Bayes factors can be calculated for these models using reversible jump Markov chain Monte Carlo, and apply the method to 16 DNA sequence alignments. For each data set, we compare the model with the best Bayes factor to the best models chosen using AIC and BIC. We find that the best model under any of these criteria is not necessarily the most complicated one; models with an intermediate number of substitution types typically do best. Moreover, almost all of the models that are chosen as best do not constrain a transition rate to be the same as a transversion rate, suggesting that it is the transition/transversion rate bias that plays the largest role in determining which models are selected. Importantly, the reversible jump Markov chain Monte Carlo algorithm described here allows estimation of phylogeny (and other phylogenetic model parameters) to be performed while accounting for uncertainty in the model of DNA substitution.

Algorithms↗
PubMedDate not supplied

Markov chain analysis finds a significant influence of neighboring bases on the occurrence of a base in eucaryotic nuclear DNA sequences both protein-coding and noncoding.

Sixty-four eucaryotic nuclear DNA sequences, half of them coding and half noncoding, have been examined as expressions of first-, second-, or third-order Markov chains. Standard statistical tests found that most of the sequences required at least second-order Markov chains for their representation, and some required chains of third order. For all 64 sequences the observed one-step second-order transition count matrices were effective in predicting the two-step transition count matrices, and 56 of 64 were effective in predicting the three-step transition count matrices. The departure from random expectation of the observed first- and second-order transition count matrices meant that a considerable sample of eucaryotic nuclear DNA sequences, both protein coding and noncoding, have significant local structure over subsequences of three to five contiguous bases, and that this structure occurs throughout the total length of the sequence. These results suggested that present DNA sequences may have arisen from the duplication, concatenation, and gradual modification of very early short sequences.

Animals↗
PubMed1996

Coupled Markov chain model: characterization of membrane channel currents with multiple conductance sublevels as partially coupled elementary pores.

A parameterized Markov chain model is developed to represent the characteristics of channel currents that either are the superposition of many single channels or show multiple conductance sublevels. The simplified model takes the form of a set of binary chains that are interdependent according to a simple lumped coupling parameter. When varied, this parameter realizes a range of behaviors from tight coupling to complete independence. Other model parameters describe the intrinsic characteristics of the binary chains. An identification procedure for the model parameters is developed based on hidden Markov modeling ideas but incorporating a novel parameter estimation. The usefulness of the model in analyzing certain types of data is demonstrated with examples of real channel currents.

Animals↗
PubMed2004

A unified Markov chain Monte Carlo framework for mapping multiple quantitative trait loci.

In this article, a unified Markov chain Monte Carlo (MCMC) framework is proposed to identify multiple quantitative trait loci (QTL) for complex traits in experimental designs, based on a composite space representation of the problem that has fixed dimension. The proposed unified approach includes the existing Bayesian QTL mapping methods using reversible jump MCMC algorithm as special cases. We also show that a variety of Bayesian variable selection methods using Gibbs sampling can be applied to the composite model space for mapping multiple QTL. The unified framework not only results in some new algorithms, but also gives useful insight into some of the important factors governing the performance of Gibbs sampling and reversible jump for mapping multiple QTL. Finally, we develop strategies to improve the performance of MCMC algorithms.

Chromosome Mapping↗
PubMed1987

Absorbent Markov chains as a model for the study of the evolution of proteins.

The formalism of absorbent Markov chains, previously developed by Kemeny & Snell (1960) is used as a model for the study of the evolution of proteins. Within the limits of statistical analysis used, the amino acid substitution frequencies of McLachlan (1972) are explained by the numerical values derived from the model used. In addition, the amino acid composition of proteins is partially explained and the relative mutability of amino acids receives a new interpretation in the light of the above mentioned stochastic model. The results show that some basic aspect of protein evolution can be predicted by a stochastic model and therefore a significant component of protein evolution is driven by a random element.

Amino Acid Sequence↗
PubMedDate not supplied

Estimation of markov chain transition probabilities and rates from fully and partially observed data: uncertainty propagation, evidence synthesis, and model calibration.

Markov transition models are frequently used to model disease progression. The authors show how the solution to Kolmogorov's forward equations can be exploited to map between transition rates and probabilities from probability data in multistate models. They provide a uniform, Bayesian treatment of estimation and propagation of uncertainty of transition rates and probabilities when 1) observations are available on all transitions and exact time at risk in each state (fully observed data) and 2) observations are on initial state and final state after a fixed interval of time but not on the sequence of transitions (partially observed data). The authors show how underlying transition rates can be recovered from partially observed data using Markov chain Monte Carlo methods in WinBUGS, and they suggest diagnostics to investigate inconsistencies between evidence from different starting states. An illustrative example for a 3-state model is given, which shows how the methods extend to more complex Markov models using the software WBDiff to compute solutions. Finally, the authors illustrate how to statistically combine data from multiple sources, including partially observed data at several follow-up times and also how to calibrate a Markov model to be consistent with data from one specific study.

Calibration↗
PubMed2004

Markov chain modeling of initiation and demand: the case of the U.S. cocaine epidemic.

Everingham and Rydell's Markov chain model of cocaine demand is modified and updated in light of recent data. Key insights continue to hold, e.g., that the proportion of cocaine demand stemming from heavy vs. light users changed dramatically over the 1980s. New insights emerge, e.g., pertaining to the average duration of a career of heavy use (about 12 years) and the negative relationship between levels of heavy use and epidemic "infectivity" or the number of new initiates per current user per year. This illustrates how simple modeling can yield insights directly relevant to managing complex drug control policy questions.

Cocaine-Related Disorders↗
PubMed2003

Integrals for continuous-time Markov chains.

This paper presents a method of evaluating the expected value of a path integral for a general Markov chain on a countable state space. We illustrate the method with reference to several models, including birth-death processes and the birth, death and catastrophe process.

Birth Rate↗
PubMed1997

Bayesian phylogenetic inference using DNA sequences: a Markov Chain Monte Carlo Method.

An improved Bayesian method is presented for estimating phylogenetic trees using DNA sequence data. The birth-death process with species sampling is used to specify the prior distribution of phylogenies and ancestral speciation times, and the posterior probabilities of phylogenies are used to estimate the maximum posterior probability (MAP) tree. Monte Carlo integration is used to integrate over the ancestral speciation times for particular trees. A Markov Chain Monte Carlo method is used to generate the set of trees with the highest posterior probabilities. Methods are described for an empirical Bayesian analysis, in which estimates of the speciation and extinction rates are used in calculating the posterior probabilities, and a hierarchical Bayesian analysis, in which these parameters are removed from the model by an additional integration. The Markov Chain Monte Carlo method avoids the requirement of our earlier method for calculating MAP trees to sum over all possible topologies (which limited the number of taxa in an analysis to about five). The methods are applied to analyze DNA sequences for nine species of primates, and the MAP tree, which is identical to a maximum-likelihood estimate of topology, has a probability of approximately 95%.

Algorithms↗
PubMed2000

Confidence bands for comparison of transition probabilities in a Markov chain model.

We consider graphs, confidence procedures and tests that can be used to compare transition probabilities in a Markov chain model with intensities specified by a Cox proportional hazard model. Under assumptions of this model, the regression coefficients provide information about the relative risks of covariates in one-step transitions, however, they cannot in general be used to to assess whether or not the covariates have a beneficial or detrimental effect on the endpoint events. To alleviate this problem, we consider graphical tests based on confidence procedures for a generalized Q-Q plot and for the difference between transition probabilities. The procedures are illustrated using data of the International Bone Marrow Transplant Registry.

Bone Marrow Transplantation↗