ThIEF: finding genome-wide trajectories of epigenetics marks. (English) Zbl 1443.92123

Schwartz, Russell (ed.) et al., 17th international workshop on algorithms in bioinformatics, WABI 2017, Boston, MA, USA, August 21–23, 2017. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 88, Article 19, 16 p. (2017).
Summary: We address the problem of comparing multiple genome-wide maps representing nucleosome positions or specific histone marks. These maps can originate from the comparative analysis of ChIP-Seq/MNase-Seq/FAIRE-Seq data for different cell types/tissues or multiple time points. The input to the problem is a set of maps, each of which is a list of genomics locations for nucleosomes or histone marks. The output is an alignment of nucleosomes/histone marks across time points (that we call trajectories), allowing small movements and gaps in some of the maps. We present a tool called ThIEF (tracking of epigenetic features) that can efficiently compute these trajectories. ThIEF comes into two “flavors”: ThIEF:Iterative finds the trajectories progressively using bipartite matching, while ThIEF:LP solves a \(k\)-partite matching problem on a hyper graph using linear programming. ThIEF:LP is guaranteed to find the optimal solution, but it is slower than ThIEF:Iterative. We demonstrate the utility of ThIEF by providing an example of applications on the analysis of temporal nucleosome maps for the human malaria parasite. As a surprisingly remarkable result, we show that the output of ThIEF can be used to produce a supervised classifier that can accurately predict the position of stable nucleosomes (i.e., nucleosomes present in all time points) and unstable nucleosomes (i.e., present in at most half of the time points) from the primary DNA sequence. To the best of our knowledge, this is the first result on the prediction of the dynamics of nucleosomes solely based on their DNA binding preference. Software is available at https://github.com/ucrbioinfo/ThIEF.
For the entire collection see [Zbl 1372.68022].


92D10 Genetics and epigenetics
92-04 Software, source code, etc. for problems pertaining to biology
Full Text: DOI


[1] Schahram Akbarian, Chunyu Liu, et al. The PsychENCODE project. {\it Nature Publishing} {\it Group}, 2015.
[2] Bradley E. Bernstein, John A. Stamatoyannopoulos, Joseph F. Costello, Bing Ren, Aleksan dar Milosavljevic, Alexander Meissner, Manolis Kellis, Marco A. Marra, Arthur L. Beaudet, Joseph R. Ecker, Peggy J. Farnham, Martin Hirst, Eric S. Lander, Tarjei S. Mikkelsen, and James A. Thomson. The NIH roadmap epigenomics mapping consortium. {\it Nat Biotech}, 28(10):1045-1048, 10 2010.
[3] Daniel Blankenberg, Gregory Von Kuster, Nathaniel Coraor, Guruprasad Ananda, Ross Lazarus, Mary Mangan, Anton Nekrutenko, and James Taylor. Galaxy: A web-based genome analysis tool for experimentalists. {\it Current protocols in molecular biology}, pages 19-10, 2010.
[4] Yuk Hei Chan and Lap Chi Lau. On linear and semidefinite programming relaxations for hypergraph matching. {\it Mathematical programming}, 135(1-2):123-148, 2012. · Zbl 1254.90107
[5] Chih-Chung Chang and Chih-Jen Lin. LIBSVM: A library for support vector machines. {\it ACM Trans. Intell. Syst. Technol.}, 2(3):27:1-27:27, May 2011.
[6] Robert C. Edgar. MUSCLE: multiple sequence alignment with high accuracy and high throughput. {\it Nucleic acids research}, 32(5):1792-7, January 2004.
[7] Isaac Elias. Settling the intractability of multiple alignment. {\it Journal of Computational} {\it Biology}, 13(7):1323-1339, 2006.
[8] ENCODE Project Consortium. An integrated encyclopedia of DNA elements in the human genome. {\it Nature}, 2012.
[9] Jason Ernst and Manolis Kellis. ChromHMM: automating chromatin-state discovery and characterization. {\it Nature Methods}, 2012.
[10] Mark B. Gerstein, Zhi John Lu, et al. Integrative analysis of the {\it Caenorhabditis elegans} genome by the modENCODE project. {\it Science}, 2010.
[11] Belinda Giardine, Cathy Riemer, Ross C. Hardison, Richard Burhans, Laura Elnitski, Prachi Shah, Yi Zhang, Daniel Blankenberg, Istvan Albert, James Taylor, Webb C. Miller, W. James Kent, and Anton Nekrutenko. Galaxy: a platform for interactive large-scale genome analysis. {\it Genome research}, 15(10):1451-1455, 2005.
[12] Jeremy Goecks, Anton Nekrutenko, James Taylor, and The Galaxy Team. Galaxy: a com prehensive approach for supporting accessible, reproducible, and transparent computational research in the life sciences. {\it Genome Biol}, 11(8):R86, 2010.
[13] Desmond Higgins and Paul Sharp. CLUSTAL: a package for performing multiple sequence alignment on a microcomputer. {\it Gene}, 73(1):237-244, 1988.
[14] Michael M. Hoffman, Orion J. Buske, Jie Wang, Zhiping Weng, Jeff A. Bilmes, and William Stafford Noble. Unsupervised pattern discovery in human chromatin structure through genomic segmentation. {\it Nature Methods}, 9:473-476, 2012.
[15] Michael M. Hoffman, Jason Ernst, Steven P. Wilder, Anshul Kundaje, Robert S. Harris, Max Libbrecht, Belinda Giardine, Paul M. Ellenbogen, Jeffrey A. Bilmes, Ewan Birney, Ross C. Hardison, Ian Dunham, Manolis Kellis, and William Stafford Noble. Integrative annotation of chromatin elements from ENCODE data. {\it Nucleic Acids Research}, 41(2):827- 841, 2013.
[16] Masato Ishikawa, Tomoyuki Toya, Masaki Hoshida, Katsumi Nitta, Atushi Ogiwara, and Minoru Kanehisa. Multiple sequence alignment by parallel simulated annealing. {\it Comput.} {\it Appl. Biosci.}, 9(3):267-273, 1993.
[17] Roy Jonker and Ton Volgenant. Improving the Hungarian assignment algorithm. {\it Operations} {\it Research Letters}, 5(4):171-175, 1986. · Zbl 0606.90111
[18] W. Just. Computational complexity of multiple sequence alignment with SP-score. {\it Journal} {\it of Computational Biology}, 8(6):615-623, 2001.
[19] :15
[20] :16
[21] :14
[22] Philip Reiner Kensche, Wieteke Anna Maria Hoeijmakers, Christa Geeke Toenhake, Maaike Bras, Lia Chappell, Matthew Berriman, and Richárd Bártfai. The nucleosome landscape of plasmodium falciparum reveals chromatin architecture and dynamics of regulatory se quences. {\it Nucleic Acids Research}, 44(5):2110-2124, 2016.
[23] W. James Kent, Robert Baertsch, Angie Hinrichs, Webb Miller, and David Haussler. Evolu tion’s cauldron: duplication, deletion, and rearrangement in the mouse and human genomes. {\it Proc. Natl. Acad. Sci. U. S. A.}, 100(20):11484-11489, 30 September 2003.
[24] Jin Kim, Sakti Pramanik, and Moon Chung. Multiple sequence alignment using simulated annealing. {\it Comput. Appl. Biosci.}, 10(4):419-426, 1994.
[25] R. D. Kornberg and L. Stryer. Statistical distributions of nucleosomes: nonrandom locations by a stochastic mechanism. {\it Nucleic Acids Research}, 16(14A):6677-6690, 07 1988.
[26] Ekaterina Kotelnikova, Vsevolod Makeev, and Mikhail Gelfand. Evolution of transcription factor DNA binding sites. {\it Gene}, 347(2):255-263, 2005.
[27] Ben Langmead and Steven L. Salzberg. Fast gapped-read alignment with bowtie 2. {\it Nat} {\it Meth}, 9(4):357-359, 04 2012.
[28] M. A. Larkin, G. Blackshields, N. P. Brown, R. Chenna, P. A. McGettigan, H. McWilliam, F. Valentin, I. M. Wallace, A. Wilm, R. Lopez, J. D. Thompson, T. J. Gibson, and D. G. Higgins. Clustal W and Clustal X version 2.0. {\it Bioinformatics}, 23(21):2947-2948, 2007.
[29] Elisa Leimgruber, Queralt Seguin-Estevez, Isabelle Dunand-Sauthier, Natalia Rybtsova, Christoph D. Schmid, Giovanna Ambrosini, Philipp Bucher, and Walter Reith. Nucleosome eviction from MHC class II promoters controls positioning of the transcription start site. {\it Nucleic Acids Res}, 37(8):2514-2528, May 2009.
[30] Hongde Liu, Xueye Duan, Shuangxin Yu, and Xiao Sun. Analysis of nucleosome positioning determined by DNA helix curvature in the human genome. {\it BMC Genomics}, 12:72, Jan 2011.
[31] Saulius Lukauskas, Roberto Visintainer, Guido Sanguinetti, and Gabriele B. Schweikert. DGW: an exploratory data analysis tool for clustering and visualisation of epigenomic marks. {\it BMC Bioinformatics}, 17(16):447, 2016.
[32] Andrew Makhorin. GLPK (GNU linear programming kit), 2008.
[33] Alessandro Mammana and Ho-Ryun Chung. Chromatin segmentation based on a proba bilistic model for read counts explains a large portion of the epigenome. {\it Genome Biology}, 16(1):151, 2015.
[34] Alan Moses, Derek Chiang, Daniel Pollard, Venky Iyer, and Michael Eisen. MONKEY: identifying conserved transcription-factor binding sites in multiple alignments using a bind ing site-specific evolutionary model. {\it Genome biology}, 5(12):R98, 2004.
[35] S. B. Needleman and C. D. Wunsch. A general method applicable to the search for similar ities in the amino acid sequence of two proteins. {\it J Mol Biol}, 48(3):443-453, Mar 1970.
[36] C. Notredame and D. G. Higgins. SAGA: Sequence alignment by genetic algorithm. {\it Nucleic} {\it Acids Res.}, 24(8):1515-1524, 1996.
[37] C. Notredame, E. A. O’Brien, and D. G. Higgins. RAGA: RNA sequence alignment by genetic algorithm. {\it Nucleic acids research}, 25(22):4570-4580, 1997.
[38] Heather E. Peckham, Robert E. Thurman, Yutao Fu, John A. Stamatoyannopoulos, William Stafford Noble, Kevin Struhl, and Zhiping Weng. Nucleosome positioning signals in genomic DNA. {\it Genome Res}, 17(8):1170-1177, Aug 2007.
[39] A. Polishko, E. M. Bunnik, K. G. Le Roch, and S. Lonardi. PuFFIN: A parameter-free method to build nucleosome maps from paired-end reads. {\it BMC Bioinformatics}, 15(Suppl 9):S11, 2014.
[40] Anton Polishko, Nadia Ponts, Karine G Le Roch, and Stefano Lonardi. NORMAL: accurate nucleosome positioning using a modified gaussian mixture model. {\it Bioinformatics (Oxford,} {\it England)}, 28(12):i242-9, June 2012.
[41] Ekaterina Protozanova, Peter Yakovchuk, and Maxim D. Frank-Kamenetskii.Stacked unstacked equilibrium at the nick site of DNA. {\it J Mol Biol}, 342(3):775-785, Sep 2004.
[42] Rainer Pudimat, Ernst-Günter Schukat-Talamazzini, and Rolf Backofen. A multiple-feature framework for modelling and predicting transcription factor binding sites. {\it Bioinformatics}, 21(14):3082-3088, 2005.
[43] Aaron R. Quinlan and Ira M. Hall. BEDTools: a flexible suite of utilities for comparing genomic features. {\it Bioinformatics}, 26(6):841-842, 2010.
[44] S. Roy, J. Ernst, P. V. Kharchenko, and P. Kheradpour. Identification of functional elements and regulatory circuits by Drosophila modENCODE. {\it Science}, 2010.
[45] Rafik A. Salama and Dov J. Stekel.A non-independent energy-based multiple se quence alignment improves prediction of transcription factor binding sites. {\it Bioinformatics}, 29(21):2699-2704, 2013.
[46] Eran Segal, Yvonne Fondufe-Mittendorf, Lingyi Chen, AnnChristine Thastrom, Yair Field, Irene K. Moore, Ji-Ping Z. Wang, and Jonathan Widom. A genomic code for nucleosome positioning. {\it Nature}, 442(7104):772-778, 08 2006.
[47] T. F. Smith and M. S. Waterman. Identification of common molecular subsequences. {\it J Mol} {\it Biol}, 147(1):195-197, Mar 1981.
[48] Julie Thompson, Toby Gibson, and Des Higgins.Multiple sequence alignment using ClustalW and ClustalX. {\it Current protocols in bioinformatics}, Chapter 2, 2002.
[49] Julie Thompson, Desmond Higgins, and Toby Gibson. CLUSTALW: improving the sensitiv ity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice. {\it Nucleic Acids Research}, 22(22):4673-4680, 1994.
[50] Mari-Liis Visnapuu and Eric C Greene. Single-molecule imaging of DNA curtains reveals intrinsic energy landscapes for nucleosome deposition. {\it Nat Struct Mol Biol}, 16(10):1056- 1062, 10 2009.
[51] Jia Wang, Shuai Liu, and Weina Fu. Nucleosome positioning with set of key positions and nucleosome affinity. {\it Open Biomed Eng J}, 8:166-170, 2014.
[52] L. Wang and T. Jiang. On the complexity of multiple sequence alignment. {\it Journal of} {\it Computational Biology}, 1(4):337-348, 1994.
[53] Yong Zhang, Tao Liu, Clifford A. Meyer, Jérôme Eeckhoute, David S. Johnson, Bradley E. Bernstein, Chad Nusbaum, Richard M. Myers, Myles Brown, Wei Li, and X. Shirley Liu. Model-based analysis of ChIP-Seq (MACS). {\it Genome Biology}, 9(9):R137, 2008.
[54] Yong Zhang, Zarmik Moqtaderi, Barbara P. Rattner, Ghia Euskirchen, Michael Snyder, James T. Kadonaga, X. Shirley Liu, and Kevin Struhl. Intrinsic histone-DNA interac tions are not the major determinant of nucleosome positions in vivo. {\it Nat Struct Mol Biol}, 16(8):847-852, Aug 2009.
[55] Xiujuan Zhao, Zhiyong Pei, Jia Liu, Sheng Qin, and Lu Cai. Prediction of nucleosome DNA formation potential and nucleosome positioning using increment of diversity combined with quadratic discriminant analysis. {\it Chromosome Res}, 18(7):777-785, Nov 2010.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.