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 325 records · Page 18Linked to original sources
PubMed2001

A Bayesian method for finding regulatory segments in DNA.

A goal of the human genome project is to determine the entire sequence of DNA (3 x 10(9) base pairs) found in chromosomes. The massive amounts of data produced by this project require interpretation. A Bayesian model is developed for locating regulatory regions in a DNA sequence. Regulatory regions are areas of DNA to which specific proteins bind and control whether or not a gene is transcribed to produce templates for protein synthesis. Each human cell contains the same DNA sequence. Thus the particular function of different cells is determined by the genes that are transcribed in that cell. A Hidden Markov chain is used to model whether a small interval of the DNA is in a regulatory region or not. This can be regarded as a changepoint problem where the changepoints are the start of a regulatory or nonregulatory region. The data consists of protein-binding elements, which are short subsequences, or "words," in the DNA sequence. Although these words can occur anywhere in the sequence, a larger number are expected in regulatory regions. Therefore, regulatory regions are detected by locating clusters of words. For a particular DNA sequence, the model automatically selects those words that best predict regions of interest. Markov chain Monte Carlo methods are used to explore the posterior distribution of the Hidden Markov chain. The model is tested by means of simulations, and applied to several DNA sequences.

Bayes Theorem↗
PubMed2000

Ante-dependence modeling in a longitudinal study of periodontal disease: the effect of age, gender, and smoking status.

BACKGROUND: It is generally accepted that periodontal disease progresses by a series of bursts that are interspersed by periods of stability or even gain of attachment. In order to analyze longitudinal data on a patient's disease experience, it is necessary to use models which accommodate serial dependence. Ante-dependence between the results of a series of periodontal examinations over time can be modeled using a Markov chain. This model describes temporal changes in patients' levels of disease in terms of transition probabilities, which allow for both regression and progression of the disease. The aim of the present study was to demonstrate the use of a Markov chain model to analyze data from a longitudinal study investigating the progression of periodontal disease in an adult population. METHODS: The study population consisted of 504 volunteers; however, only 456 were included in the analysis because the remaining 48 subjects did not give consecutive data. Subjects were examined at baseline, 6 months, and 1, 2, and 3 years. Probing depths (PD) were recorded using an automated probe. Disease was defined as four or more sites with PD > or = 4 mm. Markov chain modeling was used to determine the effect of age, gender, and smoking on the natural progression and regression (healing) of periodontal disease. RESULTS: Smoking and increasing age had no effect on the progression of disease in this population, but did have a significant effect (P values < or = 0.05) in reducing the regression of disease; i.e., their effect on disease appears to be inhibition of the natural healing process. Gender had no significant effects. CONCLUSIONS: These results demonstrate how ante-dependence modeling of longitudinal data can reveal effects that may not be immediately apparent from the data, with smoking and increasing age being seen to inhibit the healing process rather than promote disease progression.

Adolescent↗
PubMedDate not supplied

Irreducibility and efficiency of ESIP to sample marker genotypes in large pedigrees with loops.

Markov chain Monte Carlo (MCMC) methods have been proposed to overcome computational problems in linkage and segregation analyses. This approach involves sampling genotypes at the marker and trait loci. Among MCMC methods, scalar-Gibbs is the easiest to implement, and it is used in genetics. However, the Markov chain that corresponds to scalar-Gibbs may not be irreducible when the marker locus has more than two alleles, and even when the chain is irreducible, mixing has been observed to be slow. Joint sampling of genotypes has been proposed as a strategy to overcome these problems. An algorithm that combines the Elston-Stewart algorithm and iterative peeling (ESIP sampler) to sample genotypes jointly from the entire pedigree is used in this study. Here, it is shown that the ESIP sampler yields an irreducible Markov chain, regardless of the number of alleles at a locus. Further, results obtained by ESIP sampler are compared with other methods in the literature. Of the methods that are guaranteed to be irreducible, ESIP was the most efficient.

Algorithms↗
PubMed1998

Calculating the exact probability of language-like patterns in biomolecular sequences.

We present algorithms for the exact computation of the probability that a random string of a certain length matches a given regular expression. These algorithms can be used to determine statistical significance in a variety of pattern searches such as motif searches and gene-finding. This work improves upon work of Kleffe and Langebacker (Kleffe & Langbecker 1990) and of Sewell and Durbin (Sewell & Durbin 1995) in several ways. First, in many cases of interest, the algorithms presented here are faster. In addition, the type of pattern considered here strictly includes those of both previous works but also allows, for instance, arbitrary length gaps. Also, the type of probability model which can be used is more general than that of Sewell and Durbin, allowing for Markov chains. The problem solved in this work is in fact in the class of NP-hard problems which are believed to be intractable. However, the problem is fixed-parameter tractable, meaning that it is tractable for small patterns. The is problem is also computationally feasible for many patterns which occur in practice. As a sample application, we consider calculating the statistical significance of most of the PROSITE patterns as in Sewell and Durbin. Whereas their method was only fast enough to exactly compute the probabilities for sequences of length 13 larger than the pattern length, we calculate these probabilities for sequences of up to length 2000. In addition, we calculate most of these probabilities using a first order Markov chain. Most of the PROSITE patterns have high significance at length 2000 under both the i.i.d. and Markov chain models. For further applications, we demonstrate the calculation of the probability of a PROSITE pattern occurring on either strand of a random DNA sequence of up to 500 kilo-bases and the probability of a simple gene model occurring in a random sequence of up to 1 megabase.

Algorithms↗
PubMedDate not supplied

Markov modeling of contaminant concentrations in indoor air.

Most models for contaminant dispersion in indoor air are deterministic and do not account for the probabilistic nature of the pollutant concentration at a given room position and time. Such variability can be important when estimating concentrations involving small numbers of contaminant particles. This article describes the use of probabilistic models termed Markov chains to account for a portion of this variability. The deterministic and Markov models are related in that the former provide the expected concentration values. To explain this relationship, a single-zone (well-mixed room) scenario is described as a Markov chain. Subsequently, a two-zone room is cast as a Markov model, and the latter is applied to assessing a health care worker's risk of tuberculosis infection. Airborne particles carrying Mycobacterium tuberculosis bacilli are usually present in small numbers in a room occupied by an infectious tuberculosis patient. For a given scenario, the Markov model permits estimates of variability in exposure intensity and the resulting variability in infection risk.

Air Microbiology↗
PubMed2005

Why do complications of gastrointestinal disease and procedures come as serial rather than singular events?

BACKGROUND: It often appears as if complications arising from gastrointestinal disease and interventional procedures come in 'series' and 'cluster' in individual patients. AIM: The aim of this study was to analyse the clustering of complications in terms of stochastic modelling and Markov chains. METHODS: A patient with gastrointestinal disease is simulated to move along either a 'bad track' associated with multiple consecutive complications or a 'good track' free of complications, the transitions within each track and between the two tracks being governed by probability values. RESULTS: Because the occurrence of a single complication increases the risk of further complications, subjects who encounter their first complication are more likely to experience a second, third or even more complications, before they leave the 'bad track' and their personal chain of cascading complications becomes discontinued. The model of a Markov chain explains why the overall number of complications in the total population of patients with digestive disease remains low even if individual patients are expected to encounter more than a single complication. CONCLUSIONS: Published complication rates for gastrointestinal procedures underestimate the true risk to the patient, because they do not consider the added vulnerability to cascading complications after the first event.

Cluster Analysis↗
PubMedDate not supplied

Probabilistic and statistical properties of words: an overview.

In the following, an overview is given on statistical and probabilistic properties of words, as occurring in the analysis of biological sequences. Counts of occurrence, counts of clumps, and renewal counts are distinguished, and exact distributions as well as normal approximations, Poisson process approximations, and compound Poisson approximations are derived. Here, a sequence is modelled as a stationary ergodic Markov chain; a test for determining the appropriate order of the Markov chain is described. The convergence results take the error made by estimating the Markovian transition probabilities into account. The main tools involved are moment generating functions, martingales, Stein's method, and the Chen-Stein method. Similar results are given for occurrences of multiple patterns, and, as an example, the problem of unique recoverability of a sequence from SBH chip data is discussed. Special emphasis lies on disentangling the complicated dependence structure between word occurrences, due to self-overlap as well as due to overlap between words. The results can be used to derive approximate, and conservative, confidence intervals for tests.

Base Sequence↗
PubMed1992

Survival of small populations under demographic stochasticity.

We estimate the mean time to extinction of small populations in an environment with constant carrying capacity but under stochastic demography. In particular, we investigate the interaction of stochastic variation in fecundity and sex ratio under several different schemes of density dependent population growth regimes. The methods used include Markov chain theory, Monte Carlo simulations, and numerical simulations based on Markov chain theory. We find a strongly enhanced extinction risk if stochasticity in sex ratio and fluctuating population size act simultaneously as compared to the case where each mechanism acts alone. The distribution of extinction times deviates slightly from a geometric one, in particular for short extinction times. We also find that whether maximization of intrinsic growth rate decreases the risk of extinction or not depends strongly on the population regulation mechanism. If the population growth regime reduces populations above the carrying capacity to a size below the carrying capacity for large r (overshooting) then the extinction risk increases if the growth rate deviates from an optimal r-value.

Animals↗
PubMed2005

A computer program to estimate the parameters of covariate dependent higher order Markov model.

This paper presents a computer program developed in S-plus to estimate the parameters of covariate dependent higher order Markov Chain and related tests. The program can be applied for two states Markov Chain with any order and any number of covariates depending on the PC capabilities. The program provides the maximum likelihood estimates of the parameters, together with their estimated standard error, t-value and significance level. It also produces the test results for likelihood ratio and model chi-square. To illustrate the program we have used a longitudinal data set on maternal morbidity of rural women in Bangladesh. The occurrences of haemorrhage, convulsion, or fits at different follow-ups were used as outcome variable. Economic status, wanted pregnancy, ages at marriage, and education of women were used as covariates.

Algorithms↗
PubMed1999

Probability description of ligand-receptor interactions. Evaluation of reliability of events with small and supersmall doses. I. Kinetics of ligand-receptor interactions.

We have developed mathematical methods for describing ligand-receptor interactions (LRI) using Markov chains. Under some conditions, the mean value of ligand-receptor complexes obtained using Markov chains coincides with that obtained from the law of mass action. Using the calculated ratio of standard deviation to mean number of ligand-receptor complexes, we show that with small concentrations of ligand-receptor complexes LRI must be described using probability methods. Using data from the literature, we show that LRI description using the mass-action law under these conditions can cause significant errors in interpretation of experimental data.

Binding Sites↗
PubMed2004

Assessment of possible impact of a health promotion program in Korea from health risk trends in a longitudinally observed cohort.

BACKGROUND: Longitudinally observed cohort data can be utilized to assess the potential for health promotion and healthcare planning by comparing the estimated risk factor trends of non-intervened with that of intervened. The paper seeks (1) to estimate a natural transition (patterns of movement between states) of health risk state from a Korean cohort data using a Markov model, (2) to derive an effective and necessary health promotion strategy for the population, and (3) to project a possible impact of an intervention program on health status. METHODS: The observed transition of health risk states in a Korean employee cohort was utilized to estimate the natural flow of aggregated health risk states from eight health risk measures using Markov chain models. In addition, a reinforced transition was simulated, given that a health promotion program was implemented for the cohort, to project a possible impact on improvement of health status. An intervened risk transition was obtained based on age, gender, and baseline risk state, adjusted to match with the Korean cohort, from a simulated random sample of a US employee population, where a health intervention was in place. RESULTS: The estimated natural flow (non-intervened), following Markov chain order 2, showed a decrease in low risk state by 3.1 percentage points in the Korean population while the simulated reinforced transition (intervened) projected an increase in low risk state by 7.5 percentage points. Estimated transitions of risk states demonstrated the necessity of not only the risk reduction but also low risk maintenance. CONCLUSIONS: The frame work of Markov chain efficiently estimated the trend, and captured the tendency in the natural flow. Given only a minimally intense health promotion program, potential risk reduction and low risk maintenance was projected.

Journal Article↗
PubMed2004

Analysis and synthesis of textured motion: particles and waves.

Natural scenes contain a wide range of textured motion phenomena which are characterized by the movement of a large amount of particle and wave elements, such as falling snow, wavy water, and dancing grass. In this paper, we present a generative model for representing these motion patterns and study a Markov chain Monte Carlo algorithm for inferring the generative representation from observed video sequences. Our generative model consists of three components. The first is a photometric model which represents an image as a linear superposition of image bases selected from a generic and overcomplete dictionary. The dictionary contains Gabor and LoG bases for point/particle elements and Fourier bases for wave elements. These bases compete to explain the input images and transfer them to a token (base) representation with an O(10(2))-fold dimension reduction. The second component is a geometric model which groups spatially adjacent tokens (bases) and their motion trajectories into a number of moving elements--called "motons." A moton is a deformable template in time-space representing a moving element, such as a falling snowflake or a flying bird. The third component is a dynamic model which characterizes the motion of particles, waves, and their interactions. For example, the motion of particle objects floating in a river, such as leaves and balls, should be coupled with the motion of waves. The trajectories of these moving elements are represented by coupled Markov chains. The dynamic model also includes probabilistic representations for the birth/death (source/sink) of the motons. We adopt a stochastic gradient algorithm for learning and inference. Given an input video sequence, the algorithm iterates two steps: 1) computing the motons and their trajectories by a number of reversible Markov chain jumps, and 2) learning the parameters that govern the geometric deformations and motion dynamics. Novel video sequences are synthesized from the learned models and, by editing the model parameters, we demonstrate the controllability of the generative model.

Algorithms↗
PubMed1993

A stochastic model for genetic linkage equilibrium.

Linkage equilibrium is an independence condition among the alleles at a set of gene loci. Equilibrium or disequilibrium only makes sense relative to some reference population of a species. If the loci all occur on the same chromosome, then linkage equilibrium holds provided a random representative of that chromosome from the reference population displays independent alleles at the various loci of the set. Classical deterministic population genetics theory shows that linkage equilibrium is approached asymptotically after many generations of random mating in a reference population of infinite size. The current paper considers a Markov chain model for the establishment of linkage equilibrium in a population of finite size. The states of this Markov chain correspond to counts of chromosomes of various types. Because the chain is reversible, the equilibrium distribution can be explicitly computed. Partial characterization of the geometric rate of convergence of the chain to equilibrium is possible using a strong stationary stopping time.

Alleles↗
PubMed2006

Inferring complex DNA substitution processes on phylogenies using uniformization and data augmentation.

A new method is developed for calculating sequence substitution probabilities using Markov chain Monte Carlo (MCMC) methods. The basic strategy is to use uniformization to transform the original continuous time Markov process into a Poisson substitution process and a discrete Markov chain of state transitions. An efficient MCMC algorithm for evaluating substitution probabilities by this approach using a continuous gamma distribution to model site-specific rates is outlined. The method is applied to the problem of inferring branch lengths and site-specific rates from nucleotide sequences under a general time-reversible (GTR) model and a computer program BYPASSR is developed. Simulations are used to examine the performance of the new program relative to an existing program BASEML that uses a discrete approximation for the gamma distributed prior on site-specific rates. It is found that BASEML and BYPASSR are in close agreement when inferring branch lengths, regardless of the number of rate categories used, but that BASEML tends to underestimate high site-specific substitution rates, and to overestimate intermediate rates, when fewer than 50 rate categories are used. Rate estimates obtained using BASEML agree more closely with those of BYPASSR as the number of rate categories increases. Analyses of the posterior distributions of site-specific rates from BYPASSR suggest that a large number of taxa are needed to obtain precise estimates of site-specific rates, especially when rates are very high or very low. The method is applied to analyze 45 sequences of the alpha 2B adrenergic receptor gene (A2AB) from a sample of eutherian taxa. In general, the pattern expected for regions under negative selection is observed with third codon positions having the highest inferred rates, followed by first codon positions and with second codon positions having the lowest inferred rates. Several sites show exceptionally high substitution rates at second codon positions that may represent the effects of positive selection.

Algorithms↗
PubMed1993

Using three-color chromosome painting to test chromosome aberration models.

Ionizing radiation induces DNA double-strand breaks (DSB), which interact pairwise to produce chromosome aberrations. There have long been two main competing theories of such pairwise DSB-DSB interactions. The "classical" theory asserts that an unrepaired DSB makes two ends that separate within the cell nucleus, with each end subsequently able to join any similar (nontelomeric) end. The "exchange" theory asserts that at a DSB the chromatin does not separate completely; rather the DSB ends remain associated until repair, or an illegitimate recombination involving another DSB, occurs. The DSB-DSB interaction mechanism was tested by using three-color fluorescence in situ hybridization to paint chromosomes and observe "three-color triplets": three broken and misrejoined chromosomes having cyclically permuted colors. We observed 18 "three-color triplets" in 2000 cells after 2.25 Gy of gamma-irradiation. On the exchange model in its standard form such three-color triplets cannot occur, so this model is inconsistent with the observations. On the classical model, formalized as a discrete time Markov chain embedded at the transitions of a continuous time Markov chain, the frequency of occurrence of three-color triplets can be computed by Monte Carlo simulations. The number of three-color triplets predicted mathematically by the classical model was found to be slightly larger than the observed number. Thus our data, together with our computer simulations, exclude the standard form of the exchange model but are compatible with the classical model. The results are also compatible with other, more complicated models.

Chromosome Aberrations↗
PubMed1990

Use of hidden Markov models for electrocardiographic signal analysis.

Hidden Markov modelling (HMM) is a powerful stochastic modelling technique that has been successfully applied to automatic speech recognition problems. We are currently investigating the application of HMM to electrocardiographic signal analysis with the goal of improving ambulatory ECG analysis. The HMM approach specifies a Markov chain to model a "hidden" sequence that in this case is the underlying state of the heart. Each state of the Markov chain has an associated output function that describes the statistical characteristics of measurement samples generated during that state. Given a measurement sequence and HMM parameter estimates, the most likely underlying state sequence can be determined and used to infer beat classification. Advantages of this approach include resistance to noise, ability to model low-amplitude waveforms such as the P wave, and availability of an algorithm for automatically estimating model parameters from training data. We have applied the HMM approach to QRS complex detection and to arrhythmia analysis with encouraging results.

Algorithms↗
PubMed2001

On the dispersion index of a Markovian molecular clock.

The number of nucleotide substitutions accumulated in a gene or in a lineage is an important random variable in the study of molecular evolution. Of particular interest is the ratio of the variance to the mean of that random variable, often known as the dispersion index. Because nucleotide substitution is most commonly modeled by a continuous-time four-state Markov chain, this paper provides a systematic method of computing the dispersion indices exhibited by a continuous-time four-state Markov chain. Using this method along with computer algebra and Monte Carlo simulation, this paper offers partially proven conjectures that were supported by thorough computer experiments. It is believed that the Tamura model, the equal-input model and the Takahata-Kimura model always exhibit dispersion indices less than 2. It is also believed that a general four-state model can be chosen to exhibit a dispersion index of any desired magnitude, although the chance of a randomly chosen such model exhibiting a dispersion index greater than 2 is as small as about 2%. Relevance of these findings to the neutral theory is discussed.

Computer Simulation↗
PubMed2002

A Fuzzy Markov approach for assessing groundwater pollution potential for landfill siting.

This study presents a Fuzzy Markov groundwater pollution potential assessment approach to facilitate landfill siting analysis. Landfill siting is constrained by various regulations and is complicated by the uncertainty of groundwater related factors. The conventional static rating method cannot properly depict the potential impact of pollution on a groundwater table because the groundwater table level fluctuates. A Markov chain model is a dynamic model that can be viewed as a hybrid of probability and matrix models. The probability matrix of the Markov chain model is determined based on the groundwater table elevation time series. The probability reflects the likelihood of the groundwater table changing between levels. A fuzzy set method is applied to estimate the degree of pollution potential, and a case study demonstrates the applicability of the proposed approach. The short- and long-term pollution potential information provided by the proposed approach is expected to enhance landfill siting decisions.

Forecasting↗