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

Wang J, Dai X, Xiang Q, Deng Y, Feng J, Dai Z, He C - Evol. Bioinform. Online (2010)

Bottom Line: Eukaryotic genomes are packaged into chromatin by histone proteins whose chemical modification can profoundly influence gene expression.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 results demonstrate several histone modification patterns which show significant correspondence between yeast and human cells.

View Article: PubMed Central - PubMed

Affiliation: Department of Electronics and Communications Engineering, School of Information Science and Technology, Sun Yat-Sen University, 135 West Xin'gang Road, Guangzhou, P.R. China.

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.

No MeSH data available.


Related in: MedlinePlus

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.
© Copyright Policy - open-access
Related In: Results  -  Collection


getmorefigures.php?uid=PMC2964047&req=5

f2-ebo-2010-113: 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.

Mentions: Our method first identifies functional histone combinations according to gene expression and then applies association rule mining to candidate transactions. The functional histone modification combinations have two characters (1) significant EC scores (Materials and Methods) (2) no significant TFs in the promoter region or significant TFs which interact with chromatin modifiers. The steps of method can be described as follows: First, we generated 3n transactions each of which corresponds to a histone modification combination or pattern, where n is the number of sites. Second, we identified M transactions which have significant EC scores among all possible transactions. Third, we determined N1 + N2 candidate transactions among M transactions which correspond to FMTs (Identifying Functional Modification Transactions, Fig. 1). Finally, we applied association rule mining technology on the N1 + N2 candidate transactions. Notablely, for the convenience of understanding, a flowchart of this algorithm can be found in Figure S1. When applying aprioir-like algorithm (Christian Borgelt, http://www.borgelt.net/apriori.html), association rules were extracted with absolute minimum support of 5 (which correspond to 0.42% of the whole transactions for Poklok et al’s data, 0.37% for Kurdistani et al’s data), minimum confidence of 80% and minimum lift (improvement) of 110% (Materials and Methods). This method extracted association rules from transactions whose target genes has higher EC score and they are mainly regulated by histone modification. We applied the proposed methodology to two different histone modification data and identified a number of modification combinations some of which are supported by previous studies. And our association rules provide two different global views of histone modification landscapes on two datasets (Figs. 2 and 3). These novel patterns we extracted lay a useful foundation for the additional experiments necessary to gain a fuller understanding of the roles of combinations of histone modifications in gene expression.


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

Wang J, Dai X, Xiang Q, Deng Y, Feng J, Dai Z, He C - Evol. Bioinform. Online (2010)

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.
© Copyright Policy - open-access
Related In: Results  -  Collection

Show All Figures
getmorefigures.php?uid=PMC2964047&req=5

f2-ebo-2010-113: 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.
Mentions: Our method first identifies functional histone combinations according to gene expression and then applies association rule mining to candidate transactions. The functional histone modification combinations have two characters (1) significant EC scores (Materials and Methods) (2) no significant TFs in the promoter region or significant TFs which interact with chromatin modifiers. The steps of method can be described as follows: First, we generated 3n transactions each of which corresponds to a histone modification combination or pattern, where n is the number of sites. Second, we identified M transactions which have significant EC scores among all possible transactions. Third, we determined N1 + N2 candidate transactions among M transactions which correspond to FMTs (Identifying Functional Modification Transactions, Fig. 1). Finally, we applied association rule mining technology on the N1 + N2 candidate transactions. Notablely, for the convenience of understanding, a flowchart of this algorithm can be found in Figure S1. When applying aprioir-like algorithm (Christian Borgelt, http://www.borgelt.net/apriori.html), association rules were extracted with absolute minimum support of 5 (which correspond to 0.42% of the whole transactions for Poklok et al’s data, 0.37% for Kurdistani et al’s data), minimum confidence of 80% and minimum lift (improvement) of 110% (Materials and Methods). This method extracted association rules from transactions whose target genes has higher EC score and they are mainly regulated by histone modification. We applied the proposed methodology to two different histone modification data and identified a number of modification combinations some of which are supported by previous studies. And our association rules provide two different global views of histone modification landscapes on two datasets (Figs. 2 and 3). These novel patterns we extracted lay a useful foundation for the additional experiments necessary to gain a fuller understanding of the roles of combinations of histone modifications in gene expression.

Bottom Line: Eukaryotic genomes are packaged into chromatin by histone proteins whose chemical modification can profoundly influence gene expression.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 results demonstrate several histone modification patterns which show significant correspondence between yeast and human cells.

View Article: PubMed Central - PubMed

Affiliation: Department of Electronics and Communications Engineering, School of Information Science and Technology, Sun Yat-Sen University, 135 West Xin'gang Road, Guangzhou, P.R. China.

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.

No MeSH data available.


Related in: MedlinePlus