BACKGROUND
the basic unit of eukaryotic chromosomes is the nucleosome, comprised of dna wrapped around a histone octamer complex  <cit> .
nucleosomes can adopt distinct chromatin structures, associated with specific post-translational modifications of histone proteins at their n-terminal tails  <cit> .
such histone modifications can be stably maintained through cell divisions and are strong candidates to serve as marks for epigenetic regulation.
epigenetic modifications either influence the accessibility of cis-regulatory elements in genomic dna or recruit chromatin-binding proteins to regulate gene expression.
the histone code or epigenetic code theory proposes that the combinatorial nature of histone modifications and histone variants represents information that greatly extends the content and display of genetic information alone  <cit> .
as one approach to testing this model, a number of studies have begun to define genome-scale maps of various histone modifications and other chromatin constituents and to relate such maps to cellular phenotypes in organisms from yeast to human  <cit> .
significantly, the encode project reported a high-resolution epigenetic landscape of 1% of the human genome that could be used to accurately predict gene expression in a variety of cell types  <cit>  and increasing amounts of encode whole-genome data are becoming available on genome browsers  <cit> .
while much has been done to explore the nature of the histone code and how it is “read”, little is known about how and where the code is written in the first place  <cit> .
a prevailing hypothesis is that histone- and dna-modifying enzymes, although lacking dna sequence specificity themselves, can be targeted to specific sites by trans-acting co-factors such as transcription factors that bear sequence specificity or even by various classes of rna, including noncoding rnas and small rnas  <cit>  .
histone or dna modifications at these sites would then spread in cis until they encounter barrier or boundary elements defined by patterns of histone replacement or by ctcf binding to form coherently marked epigenetic domains  <cit> .
the fact that epigenetic modifications can encompass large regions of genomic dna and that epigenetic marks display certain plasticity further supports this hypothesis  <cit> .
under this model, the body of epigenetic domains should be largely independent of primary dna sequence .
alternatively, however, it is possible that the genomic sequence could influence different epigenetic domains and that primary dna sequence itself could thus bias their formation and/or maintenance on a genome-wide basis .
this hypothesis can account for chromatin state persistence across cell cycles and even through generations  <cit> .
consistent with the predictions of this model, several recent studies have demonstrated that some epigenetic marks, such as the position of methylated cpg islands  <cit>  or the presence of trimethylated forms of histone h <dig> at lysine  <dig>  or at lysine  <dig>   <cit> , are correlated with particular features of complex genomes.
furthermore, binding of ctcf to cis elements has been shown to form well-positioned nucleosome arrays around them, providing a potential mechanistic link between primary genome sequence and chromatin state  <cit> .
recently, it has been shown that mammalian chromosomes are organized into megabase-size domains stable across cell types and conserved across species, with specific genomic features marking their boundaries  <cit> .
while these findings support the genomic influence model in specific local instances, it remains a question whether the histone code, consisting of many different types of histone modifications and variants, is associated with primary dna sequence genome-wide.
in this study, we have tested this hypothesis for the human genome by investigating correlations of genomic regions associated with a wide range of methylated histones with the underlying dna sequence.
to achieve this, we used high-resolution, genome-wide epigenetic maps and applied a machine learning approach called support vector machine , which can be used successfully to computationally predict other epigenetic states  <cit> .
like other machine learning algorithms, svm has the ability to recognize patterns in a given dataset , and the resulting models can then be tested with previously unseen examples and new predictions can be made accordingly.
thus, an association between genome sequence and epigenetics can be tested by investigating whether or not primary sequence alone is sufficient to predict the genomic location of the histone code.
RESULTS
genomic sequence alone discriminates regions enriched or depleted for most methylated histones in human cd4+ cells
to investigate whether histone marks in general are associated with underlying genomic sequence, we analyzed a dataset containing the profiles of  <dig> different methylated histones from genome-wide chip followed by deep sequencing experiments  in human cd4+ t-cells  <cit> .
we asked whether genomic sequence could distinguish between regions that are enriched or depleted for these histone marks in this cell type.
to select such regions for analysis, we first simulated a null distribution of the tag frequency  for each mark, from which we determined selection criteria that limit the false discovery rate to only 1% at each extreme .
based on these criteria, we identified ± <dig> kb regions that surround either transcription start sites  or non-genic, non-repetitive regions in the genome as significantly “enriched” or “depleted” relative to the null distribution  for each of  <dig> methylated histone states.
overall, tss and non-genetic regions display very different epigenetic profiles .
many tss regions are significantly enriched for h3k4me1- <dig>  h3k9me <dig>  h3k27me <dig>  h4k20me <dig> and h2bk5me <dig>  while many non-genic regions are notably enriched for h3k27me <dig> and h3k9me2- <dig> but depleted for h3k4me <dig> and h4k20me <dig> .
given these differences, we analyzed tss and non-genic regions separately throughout to avoid potential inherent differences between these two types of sequences.
sequence information for each region was captured by the content of all occurring k-mers .
to avoid potential over-fitting problems associated with many machine learning approaches when the number of variables greatly exceeds the number of samples  <cit> , we used a large sample size  for each methylated histone and performed svm classification experiments.
each classification experiment involved training a svm model using  <dig>  regions randomly sampled from the above  <dig>  regions, and testing its prediction performance on the rest.
this classification procedure was reiterated ten times to minimize sampling bias.
if genome sequence has no influence on histone modification placement, svm models should randomly assign sequences to be “enriched” or “depleted” .
however, for all  <dig> histone marks in tss regions and for  <dig> histone marks in non-genic regions, the prediction accuracy of the svm models was significantly greater than 50% , with over 75% accuracy in most cases .
three specific examples, the classifications for a euchromatin mark h3k4me <dig> and two heterochromatin marks, h3k9me <dig> and h3k27me <dig>  are shown in figure 2c.
classification performance of these examples was further visualized using their receiver operating characteristic  curves .
specifically, the area under curve  values from these roc curves are around  <dig> , suggesting the models have very high discrimination power .
in contrast, auc values drop to ~ <dig>  and classification ability is completely lost when models were trained without the correct enrichment/depletion information among the training samples .
thus, these results demonstrate that underlying sequence alone can discriminate, to a substantial degree in most cases, regions enriched or depleted for most methylated histone marks.
sequence predicts the location of methylated histones genome-wide
svm models trained from the above  <dig>  selected sequences for each histone mark also perform consistently on the remaining regions in the genome , indicating that they generalize well on all known tss regions and the non-repetitive portion of the genome.
we next trained a single model for each histone mark , using both tss and non-genic regions, and applied these models to the entire genome, including all repetitive regions, to locate enriched regions for these histone marks.
notwithstanding the fact that ~20% of the regions are not unique  <cit>  and thus were absent from the barski et al.
chip-seq experiments, we observe a striking resemblance between experimentally-determined histone profiles and the predicted ones based solely on sequence, again exemplified by h3k4me <dig>  h3k27me <dig> and h3k9me <dig> on both a gene-poor chromosome  and a gene-rich chromosome .
the predictions for these three marks across all chromosomes are shown in additional file 4: figure s <dig>  zooming in on a 400-kb window on chromosome  <dig> reveals that the predicted locations of these marks agree very well with experimental data on a local scale .
in many cases, the prediction probability even reflects the level of enrichment despite the fact that level information was not used in determining the initial binary svm models .
notably, h3k4me2- and h3k27me3-enriched region density positively correlates with both gene density and gc content, while h3k9me <dig> was just the opposite .
these results further extend the association between sequence and methylated histone marks to a genome-wide scale.
genomic regions occupied by different methylated histones define clusters that distinguish genic and non-genic regions of the genome
it has been shown that different modifications of histones can promote or interfere with one another  <cit> , resulting in co-occupancy of some marks in the same genomic region, while others are mutually exclusive.
alternatively, histone-modifying enzymes may recognize similar or different sequence signals among chromosomal domains.
sequence-based models provide a powerful tool to explore these possible inter-relationships even without complete experimental coverage.
based on the similarity among their occupied sequences, or in other words, the ability to use models trained with one histone type to predict others, we performed cluster analysis on the histone marks for which we had obtained accurate svm models .
by cluster analysis, the  <dig> methylated histones in tss regions fall into three groups .
many mono-methylated histones, as well as h3k4me2- <dig> and h3k79me <dig>  are associated with a similar set of tss regions , consistent with the fact that many such histone modifications are associated with active transcription  <cit> .
notably, these sequences are very different from the two distinct sequence clusters occupied by repressive marks, h3k9me2- <dig> and h3k27me2- <dig>  the two repressive marks can also be readily distinguished from each other based on local sequence, which again is consistent with existing experimental data on a broad scale  <cit> .
interestingly, for non-genic regions, h3k9me <dig> still occupies different sequences from those associated with other histone marks, but h3k27me3-occupied non-genic sequences cannot be distinguished from those occupied by marks of active chromatin .
these results suggest that whatever mechanisms are responsible for placing these marks in the genome are either directly or indirectly dependent on genomic sequence.
further, the data indicate that some of these mechanisms must be different for genic and non-genic regions.
sequence features associated with predictions of methylated histone patterns
while the above analyses all support the existence of predictive genomic characteristics underlying methylated histone patterns in the human genome, they do not by themselves identify the particular sequences involved.
we therefore next explored the specific sequence features supporting each of the above svm classifications to address the nature of the sequence bias.
for each sequence feature, we calculated an f-score, a parameter that considers both within- and between-class variations to estimate their individual discriminating power  <cit> .
a sequence feature with a high f-score has large between-class variation and/or small within-class variation and therefore is more likely to be discriminative.
in general, the f-scores calculated from random sequence datasets are extremely small .
for any given methylated histone dataset, most features have small f-scores and therefore likely contribute little, if at all, to classification.
relatively few sequences have high f-scores ; these likely correspond to the sequence features responsible for accurately predicting the observed histone patterns.
to overcome the dataset dependency nature of f-score calculations, we selected sequence features that consistently have the highest f-scores across multiple, independent subsets of sequences.
the pearson linear correlation coefficients between each feature and whether or not a region is enriched for a particular histone mark were also computed to reveal their degrees of association.
finally, these consistent features were assessed by svm to evaluate their discrimination power as single features .
on the basis of this analysis, highly discriminative sequences in tss regions display three notable features: regions marked by methylated histones that are associated with active transcription  are enriched for cpg-containing sequence features but are depleted for at-rich sequences; h3k27me <dig> regions are enriched in poly-purines and poly-pyrimidines, but are depleted in at-rich features; h3k9me <dig> and h3k9me <dig> regions are enriched for at-rich features but depleted in gc-rich ones .
in contrast, the patterns are much simpler among non-genic regions: gc-richness is associated with all the methylated histones except regions enriched in h3k9me <dig>  in which the association is the opposite .
these features collectively reveal, at least to a first-order, the trends of the genomic bias for methylated histone patterns, based on which epigenetic information can be accurately inferred from primary sequence information.
for h3k27me <dig>  the majority of short sequences that have high f-scores are parts of human alu repetitive elements, sine non-ltr retrotransposons that comprise at least  <dig> % of the human genome .
to systematically investigate the potential contribution to the genomic code of all known repetitive elements, each of which can be viewed as a unique combination of shorter sequences, we performed f-score and svm analysis among a training set including  <dig>  tss regions.
the alu family is the only repetitive element whose content has an unusually high f-score and by itself it predicts ~70% of training samples .
in addition, alu content is negatively correlated with h3k27me <dig> enrichment .
this is consistent with a previous report that h3k27me3-enriched regions in mouse es cells are relatively depleted for transposons  <cit> .
this observation is clearly not just a reflection of the absence of repeat-associated sequences from chip experiments, because other repetitive sequences do not have discriminative power, nor does alu distinguish h3k4me <dig> and h3k9me <dig> in tss regions .
as h3k27me <dig> represents a repressive mechanism for controlling the expression of genes  <cit> , it is likely that alu insertions into vicinities of these genes are selectively eliminated during evolution to ensure gene function in development.
consistently, alu elements have been found to be excluded from tissue-specific genes but enriched in housekeeping genes, a genomic trend apparent both at the level of individual genes and at the level of megabase-sized chromosome bands  <cit> .
it is possible that svm models simply classifies gc/at content, as there is a significant gc bias in the features listed in table s <dig>  to test this hypothesis, we first randomly permuted the base order of selected regions to preserve the base composition but to randomize all higher k-mer  content .
for h3k9me <dig> in tss regions, base composition seems to be the only key factor for accurate prediction, because none of the permutations tested significantly affected the prediction accuracy .
in contrast, prediction on these randomized sequences for h3k4me <dig> and h3k27me <dig> in tss regions was completely lost, with the models classifying all regions to be enriched  or depleted  regardless of the original labels .
to explore further the apparent dependence of h3k4me <dig> and h3k27me <dig> predictions on sequence content, we permuted the tss sequences to preserve both base composition and dinucleotide frequencies, but altering all higher k-mer content .
we observed a significant restoration in prediction rate for h3k4me <dig>  likely due to the restoration of correct cpg content, since prediction was lost in a control experiment when we only permuted the content of cpg-containing sequence features while keep everything else the same .
in contrast, while addition of the correct dinucleotide content partially restored h3k27me <dig> prediction, this appears to be independent of cpg content, since cpg permutation itself has little effect.
these findings suggest that models for h3k27me <dig> recognize cpg-independent, higher-order  sequence features while models for h3k4me <dig> recognize cpg-dependent features and models for h3k9me <dig> depend only on base composition, not appreciably on content.
combined, these results are consistent with the highly predictive features identified based on f-scores and suggest that the observed sequence bias for histone modification exists at multiple levels.
a sequence bias for histone modification is likely a common theme for the human genome
to test whether genomic sequence also influence histone modifications in other tissues and samples, similar svm experiments were carried out with chip-seq data from the encode project  <cit> .
briefly, enriched and depleted tss regions were selected for three histone marks across a number of cell lines used by encode investigators , followed by svm training/predicting the same way as described above.
consistent with the observation made with data from cd4+ cells, svm models based on genomic sequence features are generally able to predict the histone modification status in the same cell line, with an accuracy ranging from 65% to 75% across  <dig> different data sets .
svm models trained with one cell line can also largely predict the histone marks from other cell lines, although often at slightly lower rates .
discussion
our results establish a strong association between the primary dna sequence and an extensive set of histone methylation marks in multiple human cell lines, supporting the hypothesis that at least part of the underlying basis for the histone code is encoded in the genome.
this study also provides an example of how genome organization and sequence might directly impact biological function.
furthermore, the ability of sequence models to make such predictions provides insights into the establishment and maintenance of epigenetic modifications in complex genomes.
it is worth noting that, for several reasons, the prediction accuracy of sequence-based models for the histone code as outlined here is likely an underestimate.
first of all, we have considered only the linear combination of short k-mers in local regions.
future analyses using additional information in the sequence  will be required to further explore the predictive potential of the genomic sequence and to thus further define the genomic code  <cit> .
second, svm models tend to give higher probability to genomic regions that have high levels of a particular epigenetic mark, even without such information being provided in the training sets.
supplying quantitative information to the training sets will likely enable the models to make more accurate predictions.
finally, some “false” predictions may arise from the noise of the experimental approaches, and inclusion of additional datasets may help identify and thus reduce that noise.
a nucleosome code has been described for nucleosome organization and positioning in yeast and c. elegans <cit> .
such a nucleosome code could influence or contribute to our selection of regions in the human genome enriched/depleted for many histone marks in the same way as in yeast  <cit> .
however, nucleosome density appears to be largely invariable except for limited changes in response to signaling or development  <cit> .
therefore, although nucleosome density data that might serve as a control for our analysis are unavailable, our conclusions appear unlikely to be biased by nucleosome placement.
furthermore, most of our analyses are based on several kilobases of sequence containing many nucleosomes, which should effectively reduce the bias even if there is a local nucleosome positioning code in complex genomes.
in addition, by separately analyzing tss and non-genic regions we avoided potential bias from features specifically associated with transcription.
how might primary genomic sequence influence epigenetic modification?
certain types or combinations of sequences could form higher-order signals with specific conformation, which might be used to recruit histone-modifying enzymes and/or to facilitate their spreading in cis to form the initial epigenetic framework.
different sequence composition may target, or have different affinity for, different chromatin remodeling complexes  <cit> .
other sequence-specific events, including transcription and chromatin remodeling factors, could further tailor this framework to create specific and dynamic epigenetic patterns downstream during development, in ways not necessarily dependent on sequence in that later context.
the dataset evaluated here thus provides only a single “snapshot” of epigenetic modification in time, reflecting the combined results of genomic sequence influence and subsequent cell type-specific chromatin remodeling.
notwithstanding the proposed general nature of the genomic bias reported here, the situation is no doubt further complicated at specific loci or in specific regions by various genomic features such as insulators and barriers, replication origins, or centromeres and telomeres.
a prerequisite for the genomic influence hypothesis is that the enzymes responsible for establishing epigenetic marks recognize subtle structural difference of underlying genomic sequence.
consistent with this concept, it has been recently shown that dnmt3a, an enzyme that catalyzes de novo cpg methylation, recognizes cpg periodicity signals encoded in the genome  <cit> .
histone-modifying enzymes could similarly utilize structural information, but not necessarily the same information, because our preliminary results indicate that cpg periodicity is not important for prediction methylated histone marks .
gc- and at-rich sequences have been shown to differ in chromatin conformation as well as histone modifications in yeast  <cit> , which further strengthens the link between sequence and histone modifications.
further explorations of the information encoded in the genome, especially sequence features discovered in this study, and a deeper understanding of the structural hierarchies encoded in the genome, should help to better inform how the genome sequence is interpreted or “read” by epigenetic factors.
conceptually, sequence could be the major driving force influencing the epigenetic framework, which, if true, could help explain the persistence of genome-scale epigenetic modifications and the observed clustering of tissue-specific or generalized functions in complex genomes.
for maintaining “housekeeping” functions across different cell types, for example, it would seem to be much less expensive to use the genomic sequence instead of complicated and error-prone gene regulatory networks.
this hypothesis predicts that the epigenetic framework should be largely invariant in cells from different developmental contexts.
indeed, this prediction is supported by recent genome-scale profiling studies of several histone marks in embryonic stem cells and lineage-committed cells  <cit> .
the specific and dynamic epigenetic patterns that have been demonstrated during development and the cell cycle  <cit>  appear to be at a much smaller and more local scale than the overall framework laid down by sequence features across the genome.
CONCLUSIONS
this study demonstrates a strong association between the primary dna sequence of the human genome and an extensive set of histone methylation marks described in multiple human cell lines and thus supports the hypothesis that at least part of the underlying basis for the histone code is encoded in the genome.
these findings illustrate how genome organization and sequence might establish and maintain epigenetic modifications in complex genomes and thereby directly impact biological function.

 the basic unit of eukaryotic chromosomes is the nucleosome, comprised of dna wrapped around a histone octamer complex. nucleosomes can adopt distinct chromatin structures, associated with specific post-translational modifications of histone proteins at their n-terminal tails. such histone modifications can be stably maintained through cell divisions and are strong candidates to serve as marks for epigenetic regulation. epigenetic modifications either influence the accessibility of cis-regulatory elements in genomic dna or recruit chromatin-binding proteins to regulate gene expression. the histone code or epigenetic code theory proposes that the combinatorial nature of histone modifications and histone variants represents information that greatly extends the content and display of genetic information alone. as one approach to testing this model, a number of studies have begun to define genome-scale maps of various histone modifications and other chromatin constituents and to relate such maps to cellular phenotypes in organisms from yeast to human. significantly, the encode project reported a high-resolution epigenetic landscape of 1% of the human genome that could be used to accurately predict gene expression in a variety of cell types and increasing amounts of encode whole-genome data are becoming available on genome browsers. while much has been done to explore the nature of the histone code and how it is “read”, little is known about how and where the code is written in the first place. a prevailing hypothesis is that histone- and dna-modifying enzymes, although lacking dna sequence specificity themselves, can be targeted to specific sites by trans-acting co-factors such as transcription factors that bear sequence specificity or even by various classes of rna, including noncoding rnas and small rnas. histone or dna modifications at these sites would then spread in cis until they encounter barrier or boundary elements defined by patterns of histone replacement or by ctcf binding to form coherently marked epigenetic domains. the fact that epigenetic modifications can encompass large regions of genomic dna and that epigenetic marks display certain plasticity further supports this hypothesis. under this model, the body of epigenetic domains should be largely independent of primary dna sequence. alternatively, however, it is possible that the genomic sequence could influence different epigenetic domains and that primary dna sequence itself could thus bias their formation and/or maintenance on a genome-wide basis. this hypothesis can account for chromatin state persistence across cell cycles and even through generations. consistent with the predictions of this model, several recent studies have demonstrated that some epigenetic marks, such as the position of methylated cpg islands or the presence of trimethylated forms of histone h at lysine or at lysine, are correlated with particular features of complex genomes. furthermore, binding of ctcf to cis elements has been shown to form well-positioned nucleosome arrays around them, providing a potential mechanistic link between primary genome sequence and chromatin state. recently, it has been shown that mammalian chromosomes are organized into megabase-size domains stable across cell types and conserved across species, with specific genomic features marking their boundaries. while these findings support the genomic influence model in specific local instances, it remains a question whether the histone code, consisting of many different types of histone modifications and variants, is associated with primary dna sequence genome-wide. in this study, we have tested this hypothesis for the human genome by investigating correlations of genomic regions associated with a wide range of methylated histones with the underlying dna sequence. to achieve this, we used high-resolution, genome-wide epigenetic maps and applied a machine learning approach called support vector machine, which can be used successfully to computationally predict other epigenetic states. like other machine learning algorithms, svm has the ability to recognize patterns in a given dataset, and the resulting models can then be tested with previously unseen examples and new predictions can be made accordingly. thus, an association between genome sequence and epigenetics can be tested by investigating whether or not primary sequence alone is sufficient to predict the genomic location of the histone code.  genomic sequence alone discriminates regions enriched or depleted for most methylated histones in human cd4+ cells to investigate whether histone marks in general are associated with underlying genomic sequence, we analyzed a dataset containing the profiles of different methylated histones from genome-wide chip followed by deep sequencing experiments in human cd4+ t-cells. we asked whether genomic sequence could distinguish between regions that are enriched or depleted for these histone marks in this cell type. to select such regions for analysis, we first simulated a null distribution of the tag frequency for each mark, from which we determined selection criteria that limit the false discovery rate to only 1% at each extreme. based on these criteria, we identified ± kb regions that surround either transcription start sites or non-genic, non-repetitive regions in the genome as significantly “enriched” or “depleted” relative to the null distribution for each of methylated histone states. overall, tss and non-genetic regions display very different epigenetic profiles. many tss regions are significantly enriched for h3k4me1- h3k9me h3k27me h4k20me and h2bk5me while many non-genic regions are notably enriched for h3k27me and h3k9me2- but depleted for h3k4me and h4k20me. given these differences, we analyzed tss and non-genic regions separately throughout to avoid potential inherent differences between these two types of sequences. sequence information for each region was captured by the content of all occurring k-mers. to avoid potential over-fitting problems associated with many machine learning approaches when the number of variables greatly exceeds the number of samples, we used a large sample size for each methylated histone and performed svm classification experiments. each classification experiment involved training a svm model using regions randomly sampled from the above regions, and testing its prediction performance on the rest. this classification procedure was reiterated ten times to minimize sampling bias. if genome sequence has no influence on histone modification placement, svm models should randomly assign sequences to be “enriched” or “depleted”. however, for all histone marks in tss regions and for histone marks in non-genic regions, the prediction accuracy of the svm models was significantly greater than 50%, with over 75% accuracy in most cases. three specific examples, the classifications for a euchromatin mark h3k4me and two heterochromatin marks, h3k9me and h3k27me are shown in figure 2c. classification performance of these examples was further visualized using their receiver operating characteristic curves. specifically, the area under curve values from these roc curves are around, suggesting the models have very high discrimination power. in contrast, auc values drop to ~ and classification ability is completely lost when models were trained without the correct enrichment/depletion information among the training samples. thus, these results demonstrate that underlying sequence alone can discriminate, to a substantial degree in most cases, regions enriched or depleted for most methylated histone marks. sequence predicts the location of methylated histones genome-wide svm models trained from the above selected sequences for each histone mark also perform consistently on the remaining regions in the genome, indicating that they generalize well on all known tss regions and the non-repetitive portion of the genome. we next trained a single model for each histone mark, using both tss and non-genic regions, and applied these models to the entire genome, including all repetitive regions, to locate enriched regions for these histone marks. notwithstanding the fact that ~20% of the regions are not unique and thus were absent from the barski et al. chip-seq experiments, we observe a striking resemblance between experimentally-determined histone profiles and the predicted ones based solely on sequence, again exemplified by h3k4me h3k27me and h3k9me on both a gene-poor chromosome and a gene-rich chromosome. the predictions for these three marks across all chromosomes are shown in additional file 4: figure s zooming in on a 400-kb window on chromosome reveals that the predicted locations of these marks agree very well with experimental data on a local scale. in many cases, the prediction probability even reflects the level of enrichment despite the fact that level information was not used in determining the initial binary svm models. notably, h3k4me2- and h3k27me3-enriched region density positively correlates with both gene density and gc content, while h3k9me was just the opposite. these results further extend the association between sequence and methylated histone marks to a genome-wide scale. genomic regions occupied by different methylated histones define clusters that distinguish genic and non-genic regions of the genome it has been shown that different modifications of histones can promote or interfere with one another, resulting in co-occupancy of some marks in the same genomic region, while others are mutually exclusive. alternatively, histone-modifying enzymes may recognize similar or different sequence signals among chromosomal domains. sequence-based models provide a powerful tool to explore these possible inter-relationships even without complete experimental coverage. based on the similarity among their occupied sequences, or in other words, the ability to use models trained with one histone type to predict others, we performed cluster analysis on the histone marks for which we had obtained accurate svm models. by cluster analysis, the methylated histones in tss regions fall into three groups. many mono-methylated histones, as well as h3k4me2- and h3k79me are associated with a similar set of tss regions, consistent with the fact that many such histone modifications are associated with active transcription. notably, these sequences are very different from the two distinct sequence clusters occupied by repressive marks, h3k9me2- and h3k27me2- the two repressive marks can also be readily distinguished from each other based on local sequence, which again is consistent with existing experimental data on a broad scale. interestingly, for non-genic regions, h3k9me still occupies different sequences from those associated with other histone marks, but h3k27me3-occupied non-genic sequences cannot be distinguished from those occupied by marks of active chromatin. these results suggest that whatever mechanisms are responsible for placing these marks in the genome are either directly or indirectly dependent on genomic sequence. further, the data indicate that some of these mechanisms must be different for genic and non-genic regions. sequence features associated with predictions of methylated histone patterns while the above analyses all support the existence of predictive genomic characteristics underlying methylated histone patterns in the human genome, they do not by themselves identify the particular sequences involved. we therefore next explored the specific sequence features supporting each of the above svm classifications to address the nature of the sequence bias. for each sequence feature, we calculated an f-score, a parameter that considers both within- and between-class variations to estimate their individual discriminating power. a sequence feature with a high f-score has large between-class variation and/or small within-class variation and therefore is more likely to be discriminative. in general, the f-scores calculated from random sequence datasets are extremely small. for any given methylated histone dataset, most features have small f-scores and therefore likely contribute little, if at all, to classification. relatively few sequences have high f-scores; these likely correspond to the sequence features responsible for accurately predicting the observed histone patterns. to overcome the dataset dependency nature of f-score calculations, we selected sequence features that consistently have the highest f-scores across multiple, independent subsets of sequences. the pearson linear correlation coefficients between each feature and whether or not a region is enriched for a particular histone mark were also computed to reveal their degrees of association. finally, these consistent features were assessed by svm to evaluate their discrimination power as single features. on the basis of this analysis, highly discriminative sequences in tss regions display three notable features: regions marked by methylated histones that are associated with active transcription are enriched for cpg-containing sequence features but are depleted for at-rich sequences; h3k27me regions are enriched in poly-purines and poly-pyrimidines, but are depleted in at-rich features; h3k9me and h3k9me regions are enriched for at-rich features but depleted in gc-rich ones. in contrast, the patterns are much simpler among non-genic regions: gc-richness is associated with all the methylated histones except regions enriched in h3k9me in which the association is the opposite. these features collectively reveal, at least to a first-order, the trends of the genomic bias for methylated histone patterns, based on which epigenetic information can be accurately inferred from primary sequence information. for h3k27me the majority of short sequences that have high f-scores are parts of human alu repetitive elements, sine non-ltr retrotransposons that comprise at least % of the human genome. to systematically investigate the potential contribution to the genomic code of all known repetitive elements, each of which can be viewed as a unique combination of shorter sequences, we performed f-score and svm analysis among a training set including tss regions. the alu family is the only repetitive element whose content has an unusually high f-score and by itself it predicts ~70% of training samples. in addition, alu content is negatively correlated with h3k27me enrichment. this is consistent with a previous report that h3k27me3-enriched regions in mouse es cells are relatively depleted for transposons. this observation is clearly not just a reflection of the absence of repeat-associated sequences from chip experiments, because other repetitive sequences do not have discriminative power, nor does alu distinguish h3k4me and h3k9me in tss regions. as h3k27me represents a repressive mechanism for controlling the expression of genes, it is likely that alu insertions into vicinities of these genes are selectively eliminated during evolution to ensure gene function in development. consistently, alu elements have been found to be excluded from tissue-specific genes but enriched in housekeeping genes, a genomic trend apparent both at the level of individual genes and at the level of megabase-sized chromosome bands. it is possible that svm models simply classifies gc/at content, as there is a significant gc bias in the features listed in table s to test this hypothesis, we first randomly permuted the base order of selected regions to preserve the base composition but to randomize all higher k-mer content. for h3k9me in tss regions, base composition seems to be the only key factor for accurate prediction, because none of the permutations tested significantly affected the prediction accuracy. in contrast, prediction on these randomized sequences for h3k4me and h3k27me in tss regions was completely lost, with the models classifying all regions to be enriched or depleted regardless of the original labels. to explore further the apparent dependence of h3k4me and h3k27me predictions on sequence content, we permuted the tss sequences to preserve both base composition and dinucleotide frequencies, but altering all higher k-mer content. we observed a significant restoration in prediction rate for h3k4me likely due to the restoration of correct cpg content, since prediction was lost in a control experiment when we only permuted the content of cpg-containing sequence features while keep everything else the same. in contrast, while addition of the correct dinucleotide content partially restored h3k27me prediction, this appears to be independent of cpg content, since cpg permutation itself has little effect. these findings suggest that models for h3k27me recognize cpg-independent, higher-order sequence features while models for h3k4me recognize cpg-dependent features and models for h3k9me depend only on base composition, not appreciably on content. combined, these results are consistent with the highly predictive features identified based on f-scores and suggest that the observed sequence bias for histone modification exists at multiple levels. a sequence bias for histone modification is likely a common theme for the human genome to test whether genomic sequence also influence histone modifications in other tissues and samples, similar svm experiments were carried out with chip-seq data from the encode project. briefly, enriched and depleted tss regions were selected for three histone marks across a number of cell lines used by encode investigators, followed by svm training/predicting the same way as described above. consistent with the observation made with data from cd4+ cells, svm models based on genomic sequence features are generally able to predict the histone modification status in the same cell line, with an accuracy ranging from 65% to 75% across different data sets. svm models trained with one cell line can also largely predict the histone marks from other cell lines, although often at slightly lower rates. discussion our results establish a strong association between the primary dna sequence and an extensive set of histone methylation marks in multiple human cell lines, supporting the hypothesis that at least part of the underlying basis for the histone code is encoded in the genome. this study also provides an example of how genome organization and sequence might directly impact biological function. furthermore, the ability of sequence models to make such predictions provides insights into the establishment and maintenance of epigenetic modifications in complex genomes. it is worth noting that, for several reasons, the prediction accuracy of sequence-based models for the histone code as outlined here is likely an underestimate. first of all, we have considered only the linear combination of short k-mers in local regions. future analyses using additional information in the sequence will be required to further explore the predictive potential of the genomic sequence and to thus further define the genomic code. second, svm models tend to give higher probability to genomic regions that have high levels of a particular epigenetic mark, even without such information being provided in the training sets. supplying quantitative information to the training sets will likely enable the models to make more accurate predictions. finally, some “false” predictions may arise from the noise of the experimental approaches, and inclusion of additional datasets may help identify and thus reduce that noise. a nucleosome code has been described for nucleosome organization and positioning in yeast and c. elegans. such a nucleosome code could influence or contribute to our selection of regions in the human genome enriched/depleted for many histone marks in the same way as in yeast. however, nucleosome density appears to be largely invariable except for limited changes in response to signaling or development. therefore, although nucleosome density data that might serve as a control for our analysis are unavailable, our conclusions appear unlikely to be biased by nucleosome placement. furthermore, most of our analyses are based on several kilobases of sequence containing many nucleosomes, which should effectively reduce the bias even if there is a local nucleosome positioning code in complex genomes. in addition, by separately analyzing tss and non-genic regions we avoided potential bias from features specifically associated with transcription. how might primary genomic sequence influence epigenetic modification? certain types or combinations of sequences could form higher-order signals with specific conformation, which might be used to recruit histone-modifying enzymes and/or to facilitate their spreading in cis to form the initial epigenetic framework. different sequence composition may target, or have different affinity for, different chromatin remodeling complexes. other sequence-specific events, including transcription and chromatin remodeling factors, could further tailor this framework to create specific and dynamic epigenetic patterns downstream during development, in ways not necessarily dependent on sequence in that later context. the dataset evaluated here thus provides only a single “snapshot” of epigenetic modification in time, reflecting the combined results of genomic sequence influence and subsequent cell type-specific chromatin remodeling. notwithstanding the proposed general nature of the genomic bias reported here, the situation is no doubt further complicated at specific loci or in specific regions by various genomic features such as insulators and barriers, replication origins, or centromeres and telomeres. a prerequisite for the genomic influence hypothesis is that the enzymes responsible for establishing epigenetic marks recognize subtle structural difference of underlying genomic sequence. consistent with this concept, it has been recently shown that dnmt3a, an enzyme that catalyzes de novo cpg methylation, recognizes cpg periodicity signals encoded in the genome. histone-modifying enzymes could similarly utilize structural information, but not necessarily the same information, because our preliminary results indicate that cpg periodicity is not important for prediction methylated histone marks. gc- and at-rich sequences have been shown to differ in chromatin conformation as well as histone modifications in yeast, which further strengthens the link between sequence and histone modifications. further explorations of the information encoded in the genome, especially sequence features discovered in this study, and a deeper understanding of the structural hierarchies encoded in the genome, should help to better inform how the genome sequence is interpreted or “read” by epigenetic factors. conceptually, sequence could be the major driving force influencing the epigenetic framework, which, if true, could help explain the persistence of genome-scale epigenetic modifications and the observed clustering of tissue-specific or generalized functions in complex genomes. for maintaining “housekeeping” functions across different cell types, for example, it would seem to be much less expensive to use the genomic sequence instead of complicated and error-prone gene regulatory networks. this hypothesis predicts that the epigenetic framework should be largely invariant in cells from different developmental contexts. indeed, this prediction is supported by recent genome-scale profiling studies of several histone marks in embryonic stem cells and lineage-committed cells. the specific and dynamic epigenetic patterns that have been demonstrated during development and the cell cycle appear to be at a much smaller and more local scale than the overall framework laid down by sequence features across the genome.  this study demonstrates a strong association between the primary dna sequence of the human genome and an extensive set of histone methylation marks described in multiple human cell lines and thus supports the hypothesis that at least part of the underlying basis for the histone code is encoded in the genome. these findings illustrate how genome organization and sequence might establish and maintain epigenetic modifications in complex genomes and thereby directly impact biological function. 
these findings provide evidence of an influence of genomic sequence on patterns of histone modification associated with gene expression and chromatin programming, and they suggest that the mechanisms responsible for global histone modifications may interpret genomic sequence in various ways. combinations of histone variants and modifications, conceptually representing a histone code, have been proposed to play a significant role in gene regulation and developmental processes in complex organisms. to address this systematically in the case of the human genome, we have analyzed primary dna sequences underlying patterns of different methylated histones in human primary t-cells and patterns of three methylated histones across additional human cell lines. while various mechanisms have been implicated in establishing and maintaining epigenetic patterns at specific locations in the genome, they are generally believed to be independent of primary dna sequence on a more global scale. we report strong sequence biases associated with most of these histone marks genome-wide in each cell type. furthermore, the sequence characteristics for such association are distinct for different groups of histone marks.
 combinations of histone variants and modifications, conceptually representing a histone code, have been proposed to play a significant role in gene regulation and developmental processes in complex organisms. while various mechanisms have been implicated in establishing and maintaining epigenetic patterns at specific locations in the genome, they are generally believed to be independent of primary dna sequence on a more global scale.  to address this systematically in the case of the human genome, we have analyzed primary dna sequences underlying patterns of different methylated histones in human primary t-cells and patterns of three methylated histones across additional human cell lines. we report strong sequence biases associated with most of these histone marks genome-wide in each cell type. furthermore, the sequence characteristics for such association are distinct for different groups of histone marks.  these findings provide evidence of an influence of genomic sequence on patterns of histone modification associated with gene expression and chromatin programming, and they suggest that the mechanisms responsible for global histone modifications may interpret genomic sequence in various ways. 