ThIEF: Finding genome-wide trajectories of epigenetics marks

Anton Polishko, Md Abid Hasan, Weihua Pan, Evelien M. Bunnik, Karine Le Roch, Stefano Lonardi

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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

Original languageEnglish (US)
Title of host publication17th International Workshop on Algorithms in Bioinformatics, WABI 2017
EditorsKnut Reinert, Russell Schwartz
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770507
StatePublished - Aug 1 2017
Event17th International Workshop on Algorithms in Bioinformatics, WABI 2017 - Boston, United States
Duration: Aug 21 2017Aug 23 2017

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


Other17th International Workshop on Algorithms in Bioinformatics, WABI 2017
Country/TerritoryUnited States


  • Epigenetics
  • Genomics
  • Histone Marks
  • Histone Tail Modifications
  • Nucleosomes

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'ThIEF: Finding genome-wide trajectories of epigenetics marks'. Together they form a unique fingerprint.

Cite this