Identifying the combinatorial effects of histone modifications by association rule mining in yeast

Abstract

Eukaryotic genomes are packaged into chromatin by histone proteins whose chemical modification can profoundly influence gene expression. The histone modifications often act in combinations, which exert different effects on gene expression. Although a number of experimental techniques and data analysis methods have been developed to study histone modifications, it is still very difficult to identify the relationships among histone modifications on a genome-wide scale.We proposed a method to identify the combinatorial effects of histone modifications by association rule mining. The method first identified Functional Modification Transactions (FMTs) and then employed association rule mining algorithm and statistics methods to identify histone modification patterns. We applied the proposed methodology to Pokholok et al's data with eight sets of histone modifications and Kurdistani et al's data with eleven histone acetylation sites. Our method succeeds in revealing two different global views of histone modification landscapes on two datasets and identifying a number of modification patterns some of which are supported by previous studies.We concentrate on combinatorial effects of histone modifications which significantly affect gene expression. Our method succeeds in identifying known interactions among histone modifications and uncovering many previously unknown patterns. After in-depth analysis of possible mechanism by which histone modification patterns can alter transcriptional states, we infer three possible modification pattern reading mechanism ('redundant', 'trivial', 'dominative'). Our results demonstrate several histone modification patterns which show significant correspondence between yeast and human cells.

Keywords: association rule; histone code; yeast.

Figure 1.

The Venn diagram of FMT.

Figure 2.

The global view of histone modification of FMTs for Pokholok et al’s data. Notes: Rows represent transactions, and columns represent sites. To obtain global view of histone modification of FMTs, we used a sliding window of 10 transactions to calculate ratio of over-expressed state of sites. The transactions were sorted according to EC scores. The graph showed the over-expressed states of histone modification.

Figure 3.

The global view of histone modification of FMTs for Kurdistani et al’s data. Note: Same as in Figure 2 except that Kurdistani et al’s data is used.

Figure 4.

Fraction of over-expressed or under-expressed state at sites from extracted 21 rules for Pokholok et al’s data. Notes: Over-expressed state corresponds to ‘X3’ and under-expressed state corresponds to ‘X1’ in the extracted rules, where ‘X’ is the column number.

Figure 5.

Fraction of over-expressed or under-expressed state at sites from extracted 69 rules for Kurdistani et al’s data. Notes: It’s same as in Figure 3. Because of eliminating ‘6X’ (X = 1 or 3) among the extracted rules, there are no value on H3K18 sites (‘6X’ site).