Multi-scale chromatin state annotation using a hierarchical hidden Markov model.
Ontology highlight
ABSTRACT:
SUBMITTER: Marco E
PROVIDER: S-EPMC5385569 | biostudies-literature | 2017 Apr
REPOSITORIES: biostudies-literature
Publications
Multi-scale chromatin state annotation using a hierarchical hidden Markov model.
Marco Eugenio E Meuleman Wouter W Huang Jialiang J Glass Kimberly K Pinello Luca L Wang Jianrong J Kellis Manolis M Yuan Guo-Cheng GC
Nature communications 20170407
Chromatin-state analysis is widely applied in the studies of development and diseases. However, existing methods operate at a single length scale, and therefore cannot distinguish large domains from isolated elements of the same type. To overcome this limitation, we present a hierarchical hidden Markov model, diHMM, to systematically annotate chromatin states at multiple length scales. We apply diHMM to analyse a public ChIP-seq data set. diHMM not only accurately captures nucleosome-level infor ...[more]
Similar Datasets
Project description:Precise characterization of chromatin states is an important but difficult task for understanding the regulatory role of chromatin. A number of computational methods have been developed with varying levels of success. However, a remaining challenge is to model epigenomic patterns over multi-scales, as each histone mark is distributed with its own characteristic length scale. We developed a tiered hidden Markov model and applied it to analyze a ChIP-seq dataset in human embryonic stem cells. We identified a two-tier structure containing 15 distinct bin-level chromatin states grouped into three domain-level states. Whereas the bin-level states capture the local variation of histone marks, the domain-level states detect large-scale variations. Compared to bin-level states, the domain-level states are more robust and coherent. We also found active regions in intergenic regions that upon closer examination were expressed non-coding RNAs and pseudogenes. These results provide insights into an additional layer of complexity in chromatin organization.
| S-EPMC3676702 | biostudies-literature
Project description:We propose a new computational method for exploring chromatin structural organization based on Markov State Modelling of Hi-C data represented as an interaction network between genomic loci. A Markov process describes the random walk of a traveling probe in the corresponding energy landscape, mimicking the motion of a biomolecule involved in chromatin function. By studying the metastability of the associated Markov State Model upon annealing, the hierarchical structure of individual chromosomes is observed, and corresponding set of structural partitions is identified at each level of hierarchy. Then, the notion of effective interaction between partitions is derived, delineating the overall topology and architecture of chromosomes. Mapping epigenetic data on the graphs of intra-chromosomal effective interactions helps in understanding how chromosome organization facilitates its function. A sketch of whole-genome interactions obtained from the analysis of 539 partitions from all 23 chromosomes, complemented by distributions of gene expression regulators and epigenetic factors, sheds light on the structure-function relationships in chromatin, delineating chromosomal territories, as well as structural partitions analogous to topologically associating domains and active / passive epigenomic compartments. In addition to the overall genome architecture shown by effective interactions, the affinity between partitions of different chromosomes was analyzed as an indicator of the degree of association between partitions in functionally relevant genomic interactions. The overall static picture of whole-genome interactions obtained with the method presented in this work provides a foundation for chromatin structural reconstruction, for the modelling of chromatin dynamics, and for exploring the regulation of genome function. The algorithms used in this study are implemented in a freely available Python package ChromaWalker (https://bitbucket.org/ZhenWahTan/chromawalker).
| S-EPMC6355033 | biostudies-literature
Project description:New biological techniques and technological advances in high-throughput sequencing are paving the way for systematic, comprehensive annotation of many genomes, allowing differences between cell types or between disease/normal tissues to be determined with unprecedented breadth. Epigenetic modifications have been shown to exhibit rich diversity between cell types, correlate tightly with cell-type specific gene expression, and changes in epigenetic modifications have been implicated in several diseases. Previous attempts to understand chromatin state have focused on identifying combinations of epigenetic modification, but in cases of multiple cell types, have not considered the lineage of the cells in question.We present a Bayesian network that uses epigenetic modifications to simultaneously model 1) chromatin mark combinations that give rise to different chromatin states and 2) propensities for transitions between chromatin states through differentiation or disease progression. We apply our model to a recent dataset of histone modifications, covering nine human cell types with nine epigenetic modifications measured for each. Since exact inference in this model is intractable for all the scale of the datasets, we develop several variational approximations and explore their accuracy. Our method exhibits several desirable features including improved accuracy of inferring chromatin states, improved handling of missing data, and linear scaling with dataset size. The source code for our model is available at http:// http://github.com/uci-cbcl/tree-hmm.
| S-EPMC3622631 | biostudies-literature
Project description:BackgroundRoutine surveillance of disease notification data can enable the early detection of localised disease outbreaks. Although hidden Markov models (HMMs) have been recognised as an appropriate method to model disease surveillance data, they have been rarely applied in public health practice. We aimed to develop and evaluate a simple flexible HMM for disease surveillance which is suitable for use with sparse small area count data and requires little baseline data.MethodsA Bayesian HMM was designed to monitor routinely collected notifiable disease data that are aggregated by residential postcode. Semi-synthetic data were used to evaluate the algorithm and compare outbreak detection performance with the established Early Aberration Reporting System (EARS) algorithms and a negative binomial cusum.ResultsAlgorithm performance varied according to the desired false alarm rate for surveillance. At false alarm rates around 0.05, the cusum-based algorithms provided the best overall outbreak detection performance, having similar sensitivity to the HMMs and a shorter average time to detection. At false alarm rates around 0.01, the HMM algorithms provided the best overall outbreak detection performance, having higher sensitivity than the cusum-based Methods and a generally shorter time to detection for larger outbreaks. Overall, the 14-day HMM had a significantly greater area under the receiver operator characteristic curve than the EARS C3 and 7-day negative binomial cusum algorithms.ConclusionOur findings suggest that the HMM provides an effective method for the surveillance of sparse small area notifiable disease data at low false alarm rates. Further investigations are required to evaluation algorithm performance across other diseases and surveillance contexts.
| S-EPMC2735038 | biostudies-literature
Project description:Markov state models can describe ensembles of pathways via kinetic networks but are difficult to create when large free-energy barriers limit unbiased sampling. Chain-of-states simulations allow sampling over large free-energy barriers but are often constructed using a single pathway that is unlikely to thermodynamically average over orthogonal degrees of freedom in complex systems. Here, we combine the advantages of these two approaches in the form of a Markov state model of Markov state models, which we call a Hierarchical Markov state model. In this approach, independent Markov models are constructed in regions of configuration space that are locally well sampled but are separated by large free-energy barriers from other regions. A string method is used to construct an ensemble of pathways connecting the states of these different local Markov models, and the rate through each pathway is then estimated. These rates are then combined with the rate information from the local Markov models in a master equation to predict global rates, fluxes, and populations. By applying this hierarchical approach to tractable systems, a toy potential and dipeptides, we demonstrate that it is more accurate than the conventional single-pathway description. The advantages of this approach are that it (i) is more realistic than the conventional chain-of-states approach, as an ensemble of pathways rather than a single pathway is used to describe processes in high-dimensional systems, and (ii) it resolves the issue of poor sampling in Markov State model building when large free-energy barriers are present. The divide-and-conquer strategy inherent to this approach should make this procedure straightforward to apply to more complex systems.
| S-EPMC7322723 | biostudies-literature
Project description:BackgroundMicroRNAs (miRNAs) are small non-coding single-stranded RNAs (20-23 nts) that are known to act as post-transcriptional and translational regulators of gene expression. Although, they were initially overlooked, their role in many important biological processes, such as development, cell differentiation, and cancer has been established in recent times. In spite of their biological significance, the identification of miRNA genes in newly sequenced organisms is still based, to a large degree, on extensive use of evolutionary conservation, which is not always available.ResultsWe have developed HHMMiR, a novel approach for de novo miRNA hairpin prediction in the absence of evolutionary conservation. Our method implements a Hierarchical Hidden Markov Model (HHMM) that utilizes region-based structural as well as sequence information of miRNA precursors. We first established a template for the structure of a typical miRNA hairpin by summarizing data from publicly available databases. We then used this template to develop the HHMM topology.ConclusionOur algorithm achieved average sensitivity of 84% and specificity of 88%, on 10-fold cross-validation of human miRNA precursor data. We also show that this model, trained on human sequences, works well on hairpins from other vertebrate as well as invertebrate species. Furthermore, the human trained model was able to correctly classify ~97% of plant miRNA precursors. The success of this approach in such a diverse set of species indicates that sequence conservation is not necessary for miRNA prediction. This may lead to efficient prediction of miRNA genes in virtually any organism.
| S-EPMC2648761 | biostudies-literature
Project description:In the genomic era, group association tests are of great interest. Due to the overwhelming number of individual genomic features, the power of testing for association of a single genomic feature at a time is often very small, as are the effect sizes for most features. Many methods have been proposed to test association of a trait with a group of features within a functional unit as a whole, e.g. all SNPs in a gene, yet few of these methods account for the fact that generally a substantial proportion of the features are not associated with the trait. In this paper, we propose to model the association for each feature in the group as a mixture of features with no association and features with non-zero associations to explicitly account for the possibility that a fraction of features may not be associated with the trait while other features in the group are. The feature-level associations are first estimated by generalized linear models; the sequence of these estimated associations is then modeled by a hidden Markov chain. To test for global association, we develop a modified likelihood ratio test based on a log-likelihood function that ignores higher order dependency plus a penalty term. We derive the asymptotic distribution of the likelihood ratio test under the null hypothesis. Furthermore, we obtain the posterior probability of association for each feature, which provides evidence of feature-level association and is useful for potential follow-up studies. In simulations and data application, we show that our proposed method performs well when compared with existing group association tests especially when there are only few features associated with the outcome.
| S-EPMC4834946 | biostudies-literature
Project description:The availability of reliable genetic linkage maps is crucial for functional and evolutionary genomic analyses. Established theory and methods of genetic linkage analysis have made map construction a routine exercise in diploids. However, many evolutionarily, ecologically, and/or agronomically important species are autopolyploids, with autotetraploidy being a typical example. These species undergo much more complicated chromosomal segregation and recombination at meiosis than diploids. In addition, there is evidence of polyploidy-induced and highly dynamic changes in the structure of the genome. These polysomic characteristics indicate the inappropriateness of the theory and methods of linkage analysis in diploids for use in these species and a gap in the theory and methodology of tetraploid map construction. This paper presents a theoretical model and statistical framework for multilocus linkage analysis in autotetraploids for use with dominant and/or codominant DNA molecular markers. The theory and methods incorporate the essential features of allele segregation and recombination under tetrasomic inheritance and the major challenges in statistical modeling and marker data analysis. We validated the method and explored its statistical properties by intensive simulation study and demonstrated its utility by analysis of AFLP and SSR marker data from an outbred autotetraploid potato population.
| S-EPMC2840161 | biostudies-literature
Project description:Diffusion and mobility are essential for cellular functions, as molecules are usually distributed throughout the cell and have to meet to interact and perform their function. This also involves the cytosolic migration of cellular organelles. However, observing such diffusion and interaction dynamics is challenging due to the high spatial and temporal resolution required and the accurate analysis of the diffusional tracks. The latter is especially important when identifying anomalous diffusion events, such as directed motions, which are often rare. Here, we investigate the migration modes of peroxisome organelles in the cytosol of living cells. Peroxisomes predominantly migrate randomly, but occasionally they bind to the cell's microtubular network and perform directed migration, which is difficult to quantify, and so far, accurate analysis of switching between these migration modes is missing. We set out to solve this limitation by experiments and analysis with high statistical accuracy. Specifically, we collect temporal diffusion tracks of thousands of individual peroxisomes in the HEK 293 cell line using two-dimensional spinning disc fluorescence microscopy at a high acquisition rate of 10 frames/s. We use a Hidden Markov Model with two hidden states to (1) automatically identify directed migration segments of the tracks and (2) quantify the migration properties for comparison between states and between different experimental conditions. Comparing different cellular conditions, we show that the knockout of the peroxisomal membrane protein PEX14 leads to a decrease in the directed movement due to a lowered binding probability to the microtubule. However, it does not eradicate binding, highlighting further microtubule-binding mechanisms of peroxisomes than via PEX14. In contrast, structural changes of the microtubular network explain perceived eradication of directed movement by disassembly of microtubules by Nocodazole-treatment.
| S-EPMC10640649 | biostudies-literature
Project description:Epigenomic data from ENCODE can be used to associate specific combinations of chromatin marks with regulatory elements in the human genome. Hidden Markov models and the expectation-maximization (EM) algorithm are often used to analyze epigenomic data. However, the EM algorithm can have overfitting problems in data sets where the chromatin states show high class-imbalance and it is often slow to converge. Here we use spectral learning instead of EM and find that our software Spectacle overcame these problems. Furthermore, Spectacle is able to find enhancer subtypes not found by ChromHMM but strongly enriched in GWAS SNPs. Spectacle is available at https://github.com/jiminsong/Spectacle.
| S-EPMC4355146 | biostudies-literature