{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T08:38:45Z","timestamp":1767861525797,"version":"3.49.0"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"S5","license":[{"start":{"date-parts":[[2013,4,1]],"date-time":"2013-04-01T00:00:00Z","timestamp":1364774400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/2.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2013,4]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>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.<\/jats:p>\n          <jats:p>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 <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"http:\/\/github.com\/uci-cbcl\/tree-hmm\" ext-link-type=\"uri\">http:\/\/github.com\/uci-cbcl\/tree-hmm<\/jats:ext-link>\n          <\/jats:p>","DOI":"10.1186\/1471-2105-14-s5-s4","type":"journal-article","created":{"date-parts":[[2019,12,11]],"date-time":"2019-12-11T02:00:49Z","timestamp":1576029649000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":33,"title":["Discovering and mapping chromatin states using a tree hidden Markov model"],"prefix":"10.1186","volume":"14","author":[{"given":"Jacob","family":"Biesinger","sequence":"first","affiliation":[]},{"given":"Yuanfeng","family":"Wang","sequence":"additional","affiliation":[]},{"given":"Xiaohui","family":"Xie","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2013,4,10]]},"reference":[{"issue":"3","key":"5772_CR1","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1038\/cr.2011.22","volume":"21","author":"A Bannister","year":"2011","unstructured":"Bannister A, Kouzarides T: Regulation of chromatin by histone modifications. Cell research. 2011, 21 (3): 381-395. 10.1038\/cr.2011.22.","journal-title":"Cell research"},{"issue":"6765","key":"5772_CR2","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1038\/47412","volume":"403","author":"BD Strahl","year":"2000","unstructured":"Strahl BD, Allis CD: The language of covalent histone modifications. Nature. 2000, 403 (6765): 41-5. 10.1038\/47412.","journal-title":"Nature"},{"issue":"6","key":"5772_CR3","doi-asserted-by":"publisher","first-page":"771","DOI":"10.1016\/S0092-8674(02)01196-0","volume":"111","author":"SL Schreiber","year":"2002","unstructured":"Schreiber SL, Bernstein BE: Signaling network model of chromatin. Cell. 2002, 111 (6): 771-8. 10.1016\/S0092-8674(02)01196-0.","journal-title":"Cell"},{"issue":"6921","key":"5772_CR4","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1038\/nature01411","volume":"421","author":"G Felsenfeld","year":"2003","unstructured":"Felsenfeld G, Groudine M: Controlling the double helix. Nature. 2003, 421 (6921): 448-453. 10.1038\/nature01411.","journal-title":"Nature"},{"key":"5772_CR5","doi-asserted-by":"crossref","first-page":"396","DOI":"10.1186\/1471-2105-11-396","volume":"11","author":"X Xu","year":"2010","unstructured":"Xu X, Hoang S, Mayo MW, Bekiranov S: Application of machine learning methods to histone methylation ChIP-Seq data reveals H4R3me2 globally represses gene expression. BMC bioinformatics. 2010, 11: 396-","journal-title":"BMC bioinformatics"},{"key":"5772_CR6","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1038\/nature11247","volume":"489","author":"J Khatun","year":"2012","unstructured":"Khatun J: An Integrated Encyclopedia of DNA Elements in the Human Genome. Nature. 2012, 489: 57-74. 10.1038\/nature11247.","journal-title":"Nature"},{"issue":"9","key":"5772_CR7","doi-asserted-by":"publisher","first-page":"R53","DOI":"10.1186\/gb-2012-13-9-r53","volume":"13","author":"X Dong","year":"2012","unstructured":"Dong X, Greven M, Kundaje A, Djebali S, Brown J, Cheng C, Gingeras T, Gerstein M, Guig\u00f3 R, Birney E: Modeling gene expression using chromatin features in various cellular contexts. Genome biology. 2012, 13 (9): R53-10.1186\/gb-2012-13-9-r53.","journal-title":"Genome biology"},{"issue":"4","key":"5772_CR8","doi-asserted-by":"publisher","first-page":"1835","DOI":"10.1016\/j.ajpath.2010.12.045","volume":"178","author":"HX Ju","year":"2011","unstructured":"Ju HX, An B, Okamoto Y, Shinjo K, Kanemitsu Y, Komori K, Hirai T, Shimizu Y, Sano T, Sawaki A, Tajika M, Yamao K, Fujii M, Murakami H, Osada H, Ito H, Takeuchi I, Sekido Y, Kondo Y: Distinct profiles of epigenetic evolution between colorectal cancers with and without metastasis. The American journal of pathology. 2011, 178 (4): 1835-46. 10.1016\/j.ajpath.2010.12.045.","journal-title":"The American journal of pathology"},{"issue":"6","key":"5772_CR9","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1016\/j.smim.2010.07.003","volume":"22","author":"Y Bergman","year":"2010","unstructured":"Bergman Y, Cedar H: Epigenetic control of recombination in the immune system. Seminars in immunology. 2010, 22 (6): 323-9. 10.1016\/j.smim.2010.07.003.","journal-title":"Seminars in immunology"},{"issue":"2","key":"5772_CR10","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1086\/598822","volume":"84","author":"E Jablonka","year":"2009","unstructured":"Jablonka E, Raz G: Transgenerational epigenetic inheritance: prevalence, mechanisms, and implications for the study of heredity and evolution. The Quarterly review of biology. 2009, 84 (2): 131-176. 10.1086\/598822.","journal-title":"The Quarterly review of biology"},{"issue":"10","key":"5772_CR11","doi-asserted-by":"publisher","first-page":"669","DOI":"10.1038\/nrg2641","volume":"10","author":"P Park","year":"2009","unstructured":"Park P: ChIP-seq: advantages and challenges of a maturing technology. Nature Reviews Genetics. 2009, 10 (10): 669-680. 10.1038\/nrg2641.","journal-title":"Nature Reviews Genetics"},{"issue":"11 Suppl","key":"5772_CR12","doi-asserted-by":"publisher","first-page":"S22","DOI":"10.1038\/nmeth.1371","volume":"6","author":"S Pepke","year":"2009","unstructured":"Pepke S, Wold B, Mortazavi A: Computation for ChIP-seq and RNA-seq studies. Nature methods. 2009, 6 (11 Suppl): S22-32.","journal-title":"Nature methods"},{"issue":"3","key":"5772_CR13","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1038\/ng1966","volume":"39","author":"N Heintzman","year":"2007","unstructured":"Heintzman N, Stuart R, Hon G, Fu Y, Ching C, Hawkins R, Barrera L, Van Calcar S, Qu C, Ching K: Distinct and predictive chromatin signatures of transcriptional promoters and enhancers in the human genome. Nature genetics. 2007, 39 (3): 311-318. 10.1038\/ng1966.","journal-title":"Nature genetics"},{"issue":"7235","key":"5772_CR14","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1038\/nature07672","volume":"458","author":"I Mitchell Guttman","year":"2009","unstructured":"Mitchell Guttman I, Garber M, French C, Lin M, Feldser D, Huarte M, Zuk O, Carey B, Cassady J, Cabili M: Chromatin signature reveals over a thousand highly conserved large non-coding RNAs in mammals. Nature. 2009, 458 (7235): 223-227. 10.1038\/nature07672.","journal-title":"Nature"},{"issue":"11","key":"5772_CR15","doi-asserted-by":"publisher","first-page":"e1000566","DOI":"10.1371\/journal.pcbi.1000566","volume":"5","author":"G Hon","year":"2009","unstructured":"Hon G, Wang W, Ren B: Discovery and annotation of functional chromatin signatures in the human genome. PLoS computational biology. 2009, 5 (11): e1000566-10.1371\/journal.pcbi.1000566.","journal-title":"PLoS computational biology"},{"issue":"10","key":"5772_CR16","doi-asserted-by":"publisher","first-page":"4063","DOI":"10.1093\/nar\/gkr016","volume":"39","author":"D Ucar","year":"2011","unstructured":"Ucar D, Hu Q, Tan K: Combinatorial chromatin modification patterns in the human genome revealed by subspace clustering. Nucleic acids research. 2011, 39 (10): 4063-75. 10.1093\/nar\/gkr016.","journal-title":"Nucleic acids research"},{"key":"5772_CR17","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1007\/978-3-642-02008-7_12","volume-title":"Research in Computational Molecular Biology","author":"R Jaschek","year":"2009","unstructured":"Jaschek R, Tanay A: Spatial clustering of multivariate genomic and epigenomic information. Research in Computational Molecular Biology. 2009, Springer, 170-183."},{"issue":"5","key":"5772_CR18","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1038\/nmeth.1937","volume":"9","author":"M Hoffman","year":"2012","unstructured":"Hoffman M, Buske O, Wang J, Weng Z, Bilmes J, Noble W: Unsupervised pattern discovery in human chromatin structure through genomic segmentation. Nature methods. 2012, 9 (5): 473-476. 10.1038\/nmeth.1937.","journal-title":"Nature methods"},{"issue":"20","key":"5772_CR19","doi-asserted-by":"publisher","first-page":"2344","DOI":"10.1093\/bioinformatics\/btn402","volume":"24","author":"H Xu","year":"2008","unstructured":"Xu H, Wei C, Lin F, Sung W: An HMM approach to genome-wide identification of differential histone modification sites from ChIP-seq data. Bioinformatics. 2008, 24 (20): 2344-2349. 10.1093\/bioinformatics\/btn402.","journal-title":"Bioinformatics"},{"issue":"8","key":"5772_CR20","doi-asserted-by":"publisher","first-page":"817","DOI":"10.1038\/nbt.1662","volume":"28","author":"J Ernst","year":"2010","unstructured":"Ernst J, Kellis M: Discovery and characterization of chromatin states for systematic annotation of the human genome. Nature biotechnology. 2010, 28 (8): 817-25. 10.1038\/nbt.1662.","journal-title":"Nature biotechnology"},{"issue":"7345","key":"5772_CR21","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1038\/nature09906","volume":"473","author":"J Ernst","year":"2011","unstructured":"Ernst J, Kheradpour P, Mikkelsen TS, Shoresh N, Ward LD, Epstein CB, Zhang X, Wang L, Issner R, Coyne M, Ku M, Durham T, Kellis M, Bernstein BE: Mapping and analysis of chromatin state dynamics in nine human cell types. Nature. 2011, 473 (7345): 43-9. 10.1038\/nature09906.","journal-title":"Nature"},{"key":"5772_CR22","first-page":"47","volume-title":"Proceedings of the Nineteenth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-03)","author":"J Bilmes","year":"2003","unstructured":"Bilmes J, Bartels C: On Triangulating Dynamic Graphical Models. Proceedings of the Nineteenth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-03). 2003, San Francisco, CA: Morgan Kaufmann, 47-56."},{"key":"5772_CR23","volume-title":"Proceedings of the Nineteenth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-03)","author":"T Dean","year":"1988","unstructured":"Dean T, Kanazawa K: Probabilistic temporal reasoning. Proceedings of the Nineteenth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-03). 1988, AAAI"},{"issue":"1-2","key":"5772_CR24","first-page":"1","volume":"1","author":"M Wainwright","year":"2008","unstructured":"Wainwright M, Jordan M: Graphical models, exponential families, and variational inference. Foundations and Trends\u00ae in Machine Learning. 2008, 1 (1-2): 1-305.","journal-title":"Foundations and Trends\u00ae in Machine Learning"},{"key":"5772_CR25","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511790492","volume-title":"Biological sequence analysis: probabilistic models of proteins and nucleic acids","author":"R Durbin","year":"1998","unstructured":"Durbin R: Biological sequence analysis: probabilistic models of proteins and nucleic acids. 1998, Cambridge Univ Pr"},{"key":"5772_CR26","first-page":"467","volume-title":"Proceedings of the Fifteenth conference on Uncertainty in artificial intelligence","author":"K Murphy","year":"1999","unstructured":"Murphy K, Weiss Y, Jordan M: Loopy belief propagation for approximate inference: An empirical study. Proceedings of the Fifteenth conference on Uncertainty in artificial intelligence. 1999, Morgan Kaufmann Publishers Inc., 467-475."},{"key":"5772_CR27","first-page":"236","volume-title":"Exploring artificial intelligence in the new millennium, Volume 8","author":"J Yedidia","year":"2003","unstructured":"Yedidia J, Freeman W, Weiss Y: Understanding belief propagation and its generalizations. Exploring artificial intelligence in the new millennium, Volume 8. 2003, 236-239."},{"key":"5772_CR28","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511811357","volume-title":"Modeling and reasoning with Bayesian networks, Volume 54","author":"A Darwiche","year":"2009","unstructured":"Darwiche A: Modeling and reasoning with Bayesian networks, Volume 54. 2009, Cambridge University Press"},{"key":"5772_CR29","unstructured":"ENCODE: 2012, [http:\/\/genome.ucsc.edu\/ENCODE\/]"},{"issue":"9","key":"5772_CR30","doi-asserted-by":"publisher","first-page":"1075","DOI":"10.1101\/gr.5319906","volume":"16","author":"M Bibikova","year":"2006","unstructured":"Bibikova M, Chudin E, Wu B, Zhou L, Garcia E, Liu Y, Shin S, Plaia T, Auerbach J, Arking D: Human embryonic stem cells have a unique epigenetic signature. Genome research. 2006, 16 (9): 1075-1083. 10.1101\/gr.5319906.","journal-title":"Genome research"},{"issue":"2","key":"5772_CR31","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/j.cell.2006.02.041","volume":"125","author":"BE Bernstein","year":"2006","unstructured":"Bernstein BE, Mikkelsen TS, Xie X, Kamal M, Huebert DJ, Cuff J, Fry B, Meissner A, Wernig M, Plath K, Jaenisch R, Wagschal A, Feil R, Schreiber SL, Lander ES: A bivalent chromatin structure marks key developmental genes in embryonic stem cells. Cell. 2006, 125 (2): 315-26. 10.1016\/j.cell.2006.02.041.","journal-title":"Cell"},{"issue":"7271","key":"5772_CR32","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1038\/nature08514","volume":"462","author":"R Lister","year":"2009","unstructured":"Lister R, Pelizzola M, Dowen R, Hawkins R, Hon G, Tonti-Filippini J, Nery J, Lee L, Ye Z, Ngo Q: Human DNA methylomes at base resolution show widespread epigenomic differences. Nature. 2009, 462 (7271): 315-322. 10.1038\/nature08514.","journal-title":"Nature"},{"issue":"3","key":"5772_CR33","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1038\/ng.322","volume":"41","author":"P Kolasinska-Zwierz","year":"2009","unstructured":"Kolasinska-Zwierz P, Down T, Latorre I, Liu T, Liu X, Ahringer J: Differential chromatin marking of introns and expressed exons by H3K36me3. Nature genetics. 2009, 41 (3): 376-381. 10.1038\/ng.322.","journal-title":"Nature genetics"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-14-S5-S4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1186\/1471-2105-14-S5-S4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-14-S5-S4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T22:51:42Z","timestamp":1630536702000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-14-S5-S4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,4]]},"references-count":33,"journal-issue":{"issue":"S5","published-print":{"date-parts":[[2013,4]]}},"alternative-id":["5772"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-14-s5-s4","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,4]]},"assertion":[{"value":"10 April 2013","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"S4"}}