BACKGROUND
epigenetic regulation and methylation-expression associations
epigenetics refers to the study of heritable changes that cannot be explained by changes in the dna sequence  <cit> .
one mechanism of epigenetic regulation involves dna methylation of cg dinucleotides, commonly represented as cpg.
it is known that around 50% of the protein-coding genes are near cpg-rich sequences, known as cpg islands.
patterns of methylation in the cpg islands play an important role in regulating gene expression during both normal cellular development and disease processes.
increased methylation of cpg islands  in tumor suppressor genes have been observed during tumor progression and metastasis as a result of aberrant methylation patterns  <cit> .
at the same time, aberrations leading to decreased methylation of cpg islands  of oncogenes are known to occur  <cit> .
a review of epigenetics in cancer and the role of dna methylation markers can be found in  <cit> .
since hyper and hypomethylation of the genome are considered widespread attributes of tumors, predicting the regulation of gene expression through cpg island methylation at an epigenome level will provide a better understanding of the tumor pathobiology and progression.
to measure genome-wide methylation, we used target amplification by capture and ligation , a high-throughput technique developed by affymetrix inc., which has been used to measure the methylation of  <dig>  cpgs in the promoters of  <dig>  genes for  <dig> samples  <cit> .
in the mtacl approach, regions of the genome to be analyzed  are first captured using du probes.
such probes contain segments of dna complementary to the targets with all the thymidines  substituted by uridines , and two common primers flanking the target sequences.
mtacl has about  <dig>  du probes within the vicinity of transcriptional start sites of  <dig>  genes, with  <dig>  cpgs that are potentially relevant in tumorigenesis.
moreover, the du probes were designed so that they hybridize specifically to target genomic dna digested with restriction enzymes mspi and hpyf3i, along with adaptor oligonucleotides complementary to the common primers of du probes.
all cytosines  of the adaptor oligonucleotides were substituted with 5'-methyl cytosine .
du probes, adaptor oligonucleotides and the target genomic regions were hybridized using the "touchdown annealing" protocol followed by ligation of oligonucleotides to the ends of the target genomic dna.
after ligation, the du probes were removed by digestion using uracil dna-glycosylase, leaving only the target genomic dna ligated to common primers.
later, the target dna was treated with bisulfite followed by amplification using common primers and hybridization to microarray containing 21-mer probes that span across the cpgs in the target dna.
the extent of cpg methylation is measured using relative signal of two probes  for each cpg: one corresponding to the case in which cpg covered by the probe are methylated, and the other one to the sequence in which cpg covered by the probe are unmethylated.
there are at least  <dig> different probe sets that cover the same cpg.
the resulting hybridization signals were translated into methylation values using logistic regression by fitting models of the relative probe signal to percentage methylation for each cpg.
the regression used artificial samples of known cpg methylation  and the quality of fit was assessed with r <dig>
identifying epigenetically regulated genes
this paper discusses how a novel computational protocol can be used to integrate cpg methylation and gene expression data sets to systematically identify epigenetically regulated genes.
our assumption is that the effect of dna methylation on gene expression is local and limited to the promoter region.
a computational protocol on the exploratory analysis of epigenetic regulation using coupled methylation and expression data was proposed by sjahputera et al.
<cit> .
their work investigated differential methylation hybridization and associated gene expression data to build a relational data space for non-hodgkin's lymphoma.
fuzzy set theory is used to identify epigenetically regulated genes from the relational data space.
in this process, methylation-expression associations were transformed into a logarithmic map, which was divided into four discriminative quadrants.
each quadrant represented one out of four gene regulation behaviors .
clustering was applied to sets of associations, and the epigenetic regulation was determined from the cluster's location and quadrant's membership.
a measurement of confidence is then computed from the probabilities involved in the determination of the clusters.
this computational framework suffers from a number of limitations in the context of the high-dimensionality mtacl technology:  processing time of the high-volume relational data may be prohibitive;  fuzzy clustering approaches are iterative and sensitive to the initial conditions, which may lead to unstable solutions;  the division of quadrants is arbitrary and too rigid to incorporate the natural scale of data; and  confidence in the solution is not established in terms of statistical significance .
to overcome the issues described above, we first reduced the dimensionality of the methylation data to alleviate the computational load resulting from the data.
consequently, this enables the efficient correlative analysis and assignment of p-values through permutation analysis that otherwise would be unmanageable in the original space.
to this end, we used the following two-step clustering approach:  grouping along the genome to reveal regions with high concentration of assayed methylation sites, and  clustering of methylation profiles within each region to identify similar methylation patterns.
for the latter, we used spectral clustering, as it offers a number of advantages.
for instance, it is noniterative; it can identify clusters along nonlinear boundaries; and it has been proven to outperform other techniques  <cit> .
its improved performance is attributed to the transformation of data into a higher-dimensional space, which requires less complex problem solving than in the original data space  <cit> .
here, a k-spectral clustering  is employed, and optimal input parameters are determined automatically.
secondly, associations between clustered methylation and gene expression data sets are produced by setting a fixed constraint of  <dig>  base pairs in the vicinity of either 5' or 3' ends to match methylation sites to their genes.
finally, prediction and ranking of epigenetic regulated genes is performed based on logistic regressions of the methylation-expression associations onto an exponential curve.
this logistic approach is flexible enough to incorporate any data scale and distribution, and does not contain rigid and arbitrary definitions that could limit its application.
finally, the significance of the logistic regression is verified by permutation analysis and computing the p-value.
computational protocol
the proposed computational protocol for identifying epigenetically regulated genes consists of three steps :  dimensionality reduction of the methylation profile, which is comprised of two sub-steps:  clustering of methylation profiles on the basis of proximity, and  clustering within methylation sub-regions on the basis of similarity;  association of the clustered methylation data to gene expression data; and  logistic regression and ranking of the methylation-expression associations.
software and data can be downloaded at http://vision.lbl.gov/software.
dimensionality reduction
genome-wide methylation measurements in cpg islands produce a high-volume data that make it computationally unmanageable for association, ranking, and required permutation analyses.
therefore, dimensionality reduction is a necessity and is implemented by us with two steps:  clustering on the basis of proximity of methylation sites within each chromosome along the genome; and  clustering on the basis of similarity among methylation profiles across cell lines.
- clustering on the basis of proximity: in this step, regions of concentration are identified by the proximity of cpg methylation sites along the genome.
in each chromosome, methylation sites adjoining within  <dig>  base pairs are aggregated and form distinct regions from methylation sites adjoined by more than  <dig>  base pairs.
such regions provide a spatial context for methylation sites, grouping and isolating distant chromosomal regions.
this is an important step for subsequent clustering based on the similarity of methylation profiles.
- clustering on the basis of similarity: in this step, methylation profiles are clustered to identify cross-similarities within each region.
prior to the clustering, however, methylation profiles are pre-processed and represented by the largest principal components, which embed 99% of the data underlying variance.
this is a standard approach and well documented in the machine learning literature.
clustering high-dimensional data in their principal component space results in lower computational complexity and lower risk from the curse of dimensionality  <cit> .
the clustering method used here is unsupervised, and based on k-spectral clustering   <cit> , as discussed below.
given a set of methylation profiles  across l cell line principal components, the algorithm starts by computing an affinity matrix a whose diagonal elements aii =  <dig> and off-diagonal elements are
next, the k largest principal components are computed from the matrix
where d is a diagonal matrix whose di,i elements are the sum of a's i-th row.
let x be the n × k matrix that is formed by the k largest principal components of l. k-means clustering  <cit>  is then applied to the normalized matrix y, whose elements are represented by .
finally, the methylation profiles si receive the same clustering assignment proposed for y by k-means, i.e., a profile is assigned to cluster j if and only if row yi is assigned to cluster j.
the above formulation of ksc requires parameter setting for the variables σ and k. σ determines the magnitude of the exponential decay in the computation of the affinity matrix a. its value plays a role on the determination of boundaries between adjacent clusters.
k specifies the number of clusters, which controls the amount of data quantization, but is often difficult to be determined in practice.
a simple yet effective strategy to infer these parameters involves clustering with different combinations of the parameters and estimating the compactness of the inferred clusters.
one way to characterize cluster compactness is to measure the cluster's internal homogeneity over external heterogeneity  <cit> .
this relation can be mathematically defined by the ratio of , where w is the maximum distance between a point within a cluster and its center, and b is the minimum distance between two cluster centers.
in our implementation, we partition the space of k and σ into fixed intervals, perform ksc for each enumerated pair of variables, and select the pair that produces the minimum measure of compactness.
a representative methylation profile for each cluster is then computed by averaging all methylation measurements across cell lines.
we tested this approach on synthetic data with linear and nonlinear boundaries to predict the validity of the results.
figure  <dig> demonstrates the selection of ksc's optimal parameters σ and k for synthetic data equally distributed into three concentric circles.
the compactness measures, produced by each pair of parameters, are then normalized and shown as a heat map.
the minimum value is marked by the blue box.
methylation-expression association
each representative methylation site, averaged over members of the same cluster, is associated with a gene or a set of genes.
the association uses only the methylation site and the gene's probe set base range.
a gene may have multiple probe sets in the expression data, which cover different portions of a chromosome.
these associations are created for representative methylation sites being  within a gene probe set, or  within a  <dig> -base-pair window adjacent to the gene probe set.
the latter accounts for natural uncertainties for locating a potential cpg island along the dna.
logistic regression and assignment of p-value
in order to characterize a negative correlation between the methylation and expression data , we perform logistic regression of the methylation-expression associations.
to this end, we experimented with several functional representations and propose a generic model, with flexible degrees of freedom, corresponding to an exponential curve of the form:
where e and m are respectively the expression and methylation measurements for each cell line, and a, b, and c are the free variables of the logistic model.
evaluation of the logistic regression on synthetic data reveals that expected inverse relationship between expression and methylation can be correctly ranked .
note that r is the correlation coefficient by which the associations are ranked.
it reflects the quality of the logistic regression and, consequently, the method's confidence in an epigenetic regulation.
where ssr = ∑) <dig> and sse = ∑ <dig>  and r =  <dig> indicates a perfect fit to the model.
the corresponding p-value is estimated for each association by computing:
the p-value is computed by comparing the value of r resulting from the curve regression, and the values of rm, m =  <dig>   <dig> ...,m, resulting from m attempts for fitting the same curve after permuting the methylation measurements of each association.
in our implementation, m is set at  <dig> .
RESULTS
data sets
the raw data was composed of  <dig>  cpg methylation measurements containing, among others, the chromosome number, chromosomal sampling site, and the methylation profile across  <dig> cell lines.
we filtered the original array to  <dig>  cpg methylation sites, which contained valid chromosomal annotation data.
with respect to gene expression data, we used publicly available data for a the panel of breast cancer cell lines  <cit> .
each array consists of  <dig>  probe sets containing both luminal and basal subtypes.
forty-five cell lines were found in common between the icbp expression data and the mtacl methylation data, and only data for the common cell lines were used for analysis .
all expression measurements were transformed from the logarithmic scale to decimal units and normalized between 0-100% across the whole data set so the measurements were consistent with methylation.
forty-five cell lines were found in common between the icbp expression and the mtacl methylation data.
the cell lines listed here formed the gene signature used in our analysis.
dimensionality reduction
the first clustering step grouped the  <dig>  methylation sites on the affymetrix array into  <dig>  distinct clusters  across  <dig> chromosomes.
out of these  <dig>  regions, the second clustering step generated  <dig>  clusters, and produced representative methylation patterns by averaging the cluster's respective members.
note that this result represents a reduction of around 90% from the original raw data.
furthermore, 99% of the cell line's principal components' variance was found to be concentrated in  <dig> to  <dig> components, which reveals a high correlation between cell lines.
subsequent associations between the reduced methylation data and the gene expression generated  <dig>  associations.
logistic regression and assignment of p-value
top  <dig> genes predicted as epigenetically regulated according to our logistic model and p-value calculation.
methylation-expression associations for underlined genes are shown in figure  <dig>
we have compared the percentage of selected markers with two cancer-specific gene data sets of   <dig> genes that the cancer genome atlas project  is targeting for sequencing  <cit> , and  genes that were selected using prediction analysis of microarrays  data as described in  <cit> .
the tcga gene set represents genes that are widely expressed in cancer whereas pam gene set represents breast cancer subtypes.
we found that 66% and 22% of our gene list are also in the tcga and the pam data sets, respectively.
this analysis is promising since  the tcga gene list is not specific to breast tissue, and  the pam data set does not incorporate methylation data; thus, by incorporating methylation data, a reduced number of biomarkers can be hypothesized.
epigenetically regulated genes
our protocol has identified  <dig> genes that are epigenetically regulated.
here, we briefly discuss col1a <dig>  top2a, vav <dig>  cdkn2a, and tff <dig> , by comparing them against known literature.
methylation maps for  <dig> genes in relation to the regulated genes are shown in additional file  <dig>
col1a <dig> plays important role in collagen production and tumor development  <cit> , and is hypermethylated and down-regulated in about 40% of the icbp cell lines.
let us assume that hypermethylation and up-regulation accounts for measurements above the 50% threshold.
it is interesting to note that our method has identified epigenetic regulation of col1a <dig> even in the presence of only  <dig> up-regulated cell lines.
these  <dig> lines are not outliers as the computational protocol has generated a hypothesis for further bioinformatics analysis.
epigenetic regulation of col1a <dig> is consistent with the published literature, which suggests that its down-regulation correlates with hypermethylation, and is a frequent event in breast cancer cell lines such as mcf <dig> and hs578t  <cit> .
furthermore, aberrant methylation of col1a <dig> has been identified in medulloblastoma and hepatoma  <cit> , where biallelic methylation of col1a <dig> was observed in 77% of medulloblastomas, in addition to be shown to distinguish histological subtypes of tumors  <cit> .
top2a is an enzyme involved in controlling the topological state of the dna machinery.
approximately 50% of icbp cell lines are hypomethylated and up-regulated top2a.
top2a is  a good prognostic marker in breast cancer and response to therapy  <cit> ,  a prognostic factor for er-positive breast cancer  <cit> , and  is epigenetically regulated for cellular assembly and organization in lymphoblastoid cell lines  <cit> .
tff1's function is not well known to date.
however, it has been widely studied because of its presence in human tumors.
for example, a recent study has identified and validated over-expression of tff <dig> in breast carcinoma  <cit> .
another study has concluded decreased methylation levels in breast tumor cells  <cit> , while a much older study states that tff <dig> expression is regulated by dna methylation in breast cancer  <cit> .
vav <dig> is a nucleotide exchange factor that activates rearrangement of actin filament, and its association shows that only  <dig> cell lines are hypermethylated.
epigenetic regulation of vav <dig> is consistent with a recent report showing that 83% of breast tumors overexpress vav <dig>  <cit> .
cdkn2a is part of the cell cycle machinery and is an important tumor suppressor gene.
our analysis indicates that cdkn2a is hypermethylated and down-regulated in only about 30% of the samples, whereas the majority of the samples are hypomethylated and down-regulated.
this discrepancy can be explained by dna copy number loss or cdkn2a mutation, which is frequently associated with pathophysiology of certain types of cancers, including breast cancer  <cit> .
subnetwork enrichment analysis
although gene-by-gene analysis is a traditional and viable bioinformatics approach, modern analyses can benefit from enrichment strategies.
here, we have applied the predicted  <dig> genes for subnetwork enrichment through pathway studio.
it is noteworthy that   <dig> common regulators with  <dig> or more predicted genes have been identified, and  that these regulators are of the type "pathway".
table  <dig> lists the top  <dig> subnetworks according to their p-value.
a complete spreadsheet of the common regulators and their targets can be found in additional file  <dig>  analysis of these subnetworks suggests that epigenetic regulation of individual genes occurs in a coordinated fashion and through common regulators.
an example is shown in figure  <dig>  where jun/fos complex has been shown to be a common regulator for a number of predicted epigenetic biomarkers.
jun and fos, together with the ap <dig> transcription factor, drive expression of a number of genes necessary for cell cycle progression, including s100a <dig>  s100a <dig> was also predicted by our protocol and has been implicated in breast cancer and its repression in tumor cells is mediated by site-specific methylation  <cit> .
figure  <dig> shows interaction of two common regulators and predicted epigenetic markers.
subnetwork enrichment and the presence of a large number of common regulators further substantiate our methodology.
top  <dig> lowest p-valued pathways identified by subnetwork enrichment analysis of the predicted  <dig> genes through pathway studio .
common regulator, genes involved and respective p-values are shown.
the occurrence of multiple predicted markers within the same pathway suggests that epigenetic regulation of individual genes occurs in a coordinated fashion and through common regulators.
subtype-specific epigenetic regulation
one aspect of data analysis in cancer biology is to identify subtypes within the tumor lines.
our analysis indicates that there is evidence of subtype methylation with respect to the previous classification of basal a, basal b, and luminal lines, where these subtypes were shown to have dna copy number changes similar to those of the respective subtypes found in primary breast tumors  <cit> .
our protocol suggests that the luminal marker gata <dig> and basal marker cd <dig> are  epigenetically regulated and  cell line specific.
for example, figure  <dig> indicates that luminal lines have low expression as a function of methylation for cd <dig> , although the basal lines are epigenetically regulated; and  the opposite holds for gata <dig> .
CONCLUSIONS
in this paper, we proposed a computational pipeline for identifying epigenetically regulated genes for a panel of breast cancer cell lines.
the protocol avoids excessive computational complexity through a step-wise reduction of methylation data for the required expression data associations.
to this end, a twofold clustering approach explored both the proximity of methylation sites and similarities among methylation profiles across cell lines.
k-spectral clustering was presented and used in the latter step.
as a result of data clustering, a number of representative methylation profiles were generated for direct association with candidate genes.
epigenetic regulation was estimated from logistic regressions of the methylation-expression associations and its significance verified through the computed p-value.
the computational pipeline was applied to a panel of  <dig> breast cancer cell lines, and the protocol identified a list of  <dig> genes, including col1a <dig>  top2a, tff <dig>  and vav <dig>  whose key roles in epigenetic regulation are consistent with known literature.
subnetwork enrichment of these markers identified  <dig> common regulators of the type "pathway" with  <dig> or more predicted genes, further suggesting that epigenetic regulation of individual genes occurs in a coordinated fashion and through common regulators.
our current efforts focus on associating methylation data with the therapeutic responses and other biological data derived from the same panel of cell lines.
competing interests
the authors declare that they have no competing interests.
authors' contributions
lal and bp designed and implemented the computational protocol, and drafted the manuscript.
ps and jwg established the biological questions and computational requirements, designed the experiment and provided material to affymetrix.
as contributed to some biological analysis of the results, assisting with suggestions to the manuscript.
sd produced the maps of methylation for the epigenetically regulated genes.
sn, df, vc, mm, yl and mf conducted the experiments resulting in available data from the icbp panel of breast cancer cell lines.
all authors read and approved the final manuscript.
supplementary material
additional file 1
maps of methylation for the epigenetically regulated genes.
each graph shows a map of methylation in relation to the top  <dig> epigenetically regulated genes from table  <dig>  the respective r values are represented by the magnitude of the yellow bars, plotted over the methylation site responsible for the highest ranked association with each gene
click here for file
additional file 2
list of common regulators through subnetwork enrichment.
subnetwork enrichment analysis of the predicted  <dig> genes through pathway studio identified  <dig> common regulators of the type "pathway" with  <dig> or more predicted genes.
common regulator, subnetwork type, total number of neighbors, number of overlapping markers, percentage of overlapping markers, gene set seed, overlapping markers, p-value and rank number are shown.
click here for file
acknowledgements
this work was supported by the director, office of science, office of biological & environmental research, of the u.s. department of energy under contract no.
de-ac02-05ch <dig>  and by the national institutes of health, national cancer institute grants p <dig> ca  <dig>  and the u <dig> ca  <dig>

 epigenetic regulation and methylation-expression associations epigenetics refers to the study of heritable changes that cannot be explained by changes in the dna sequence. one mechanism of epigenetic regulation involves dna methylation of cg dinucleotides, commonly represented as cpg. it is known that around 50% of the protein-coding genes are near cpg-rich sequences, known as cpg islands. patterns of methylation in the cpg islands play an important role in regulating gene expression during both normal cellular development and disease processes. increased methylation of cpg islands in tumor suppressor genes have been observed during tumor progression and metastasis as a result of aberrant methylation patterns. at the same time, aberrations leading to decreased methylation of cpg islands of oncogenes are known to occur. a review of epigenetics in cancer and the role of dna methylation markers can be found in. since hyper and hypomethylation of the genome are considered widespread attributes of tumors, predicting the regulation of gene expression through cpg island methylation at an epigenome level will provide a better understanding of the tumor pathobiology and progression. to measure genome-wide methylation, we used target amplification by capture and ligation, a high-throughput technique developed by affymetrix inc., which has been used to measure the methylation of cpgs in the promoters of genes for samples. in the mtacl approach, regions of the genome to be analyzed are first captured using du probes. such probes contain segments of dna complementary to the targets with all the thymidines substituted by uridines, and two common primers flanking the target sequences. mtacl has about du probes within the vicinity of transcriptional start sites of genes, with cpgs that are potentially relevant in tumorigenesis. moreover, the du probes were designed so that they hybridize specifically to target genomic dna digested with restriction enzymes mspi and hpyf3i, along with adaptor oligonucleotides complementary to the common primers of du probes. all cytosines of the adaptor oligonucleotides were substituted with 5'-methyl cytosine. du probes, adaptor oligonucleotides and the target genomic regions were hybridized using the "touchdown annealing" protocol followed by ligation of oligonucleotides to the ends of the target genomic dna. after ligation, the du probes were removed by digestion using uracil dna-glycosylase, leaving only the target genomic dna ligated to common primers. later, the target dna was treated with bisulfite followed by amplification using common primers and hybridization to microarray containing 21-mer probes that span across the cpgs in the target dna. the extent of cpg methylation is measured using relative signal of two probes for each cpg: one corresponding to the case in which cpg covered by the probe are methylated, and the other one to the sequence in which cpg covered by the probe are unmethylated. there are at least different probe sets that cover the same cpg. the resulting hybridization signals were translated into methylation values using logistic regression by fitting models of the relative probe signal to percentage methylation for each cpg. the regression used artificial samples of known cpg methylation and the quality of fit was assessed with r identifying epigenetically regulated genes this paper discusses how a novel computational protocol can be used to integrate cpg methylation and gene expression data sets to systematically identify epigenetically regulated genes. our assumption is that the effect of dna methylation on gene expression is local and limited to the promoter region. a computational protocol on the exploratory analysis of epigenetic regulation using coupled methylation and expression data was proposed by sjahputera et al.. their work investigated differential methylation hybridization and associated gene expression data to build a relational data space for non-hodgkin's lymphoma. fuzzy set theory is used to identify epigenetically regulated genes from the relational data space. in this process, methylation-expression associations were transformed into a logarithmic map, which was divided into four discriminative quadrants. each quadrant represented one out of four gene regulation behaviors. clustering was applied to sets of associations, and the epigenetic regulation was determined from the cluster's location and quadrant's membership. a measurement of confidence is then computed from the probabilities involved in the determination of the clusters. this computational framework suffers from a number of limitations in the context of the high-dimensionality mtacl technology: processing time of the high-volume relational data may be prohibitive; fuzzy clustering approaches are iterative and sensitive to the initial conditions, which may lead to unstable solutions; the division of quadrants is arbitrary and too rigid to incorporate the natural scale of data; and confidence in the solution is not established in terms of statistical significance. to overcome the issues described above, we first reduced the dimensionality of the methylation data to alleviate the computational load resulting from the data. consequently, this enables the efficient correlative analysis and assignment of p-values through permutation analysis that otherwise would be unmanageable in the original space. to this end, we used the following two-step clustering approach: grouping along the genome to reveal regions with high concentration of assayed methylation sites, and clustering of methylation profiles within each region to identify similar methylation patterns. for the latter, we used spectral clustering, as it offers a number of advantages. for instance, it is noniterative; it can identify clusters along nonlinear boundaries; and it has been proven to outperform other techniques. its improved performance is attributed to the transformation of data into a higher-dimensional space, which requires less complex problem solving than in the original data space. here, a k-spectral clustering is employed, and optimal input parameters are determined automatically. secondly, associations between clustered methylation and gene expression data sets are produced by setting a fixed constraint of base pairs in the vicinity of either 5' or 3' ends to match methylation sites to their genes. finally, prediction and ranking of epigenetic regulated genes is performed based on logistic regressions of the methylation-expression associations onto an exponential curve. this logistic approach is flexible enough to incorporate any data scale and distribution, and does not contain rigid and arbitrary definitions that could limit its application. finally, the significance of the logistic regression is verified by permutation analysis and computing the p-value. computational protocol the proposed computational protocol for identifying epigenetically regulated genes consists of three steps: dimensionality reduction of the methylation profile, which is comprised of two sub-steps: clustering of methylation profiles on the basis of proximity, and clustering within methylation sub-regions on the basis of similarity; association of the clustered methylation data to gene expression data; and logistic regression and ranking of the methylation-expression associations. software and data can be downloaded at http://vision.lbl.gov/software. dimensionality reduction genome-wide methylation measurements in cpg islands produce a high-volume data that make it computationally unmanageable for association, ranking, and required permutation analyses. therefore, dimensionality reduction is a necessity and is implemented by us with two steps: clustering on the basis of proximity of methylation sites within each chromosome along the genome; and clustering on the basis of similarity among methylation profiles across cell lines. - clustering on the basis of proximity: in this step, regions of concentration are identified by the proximity of cpg methylation sites along the genome. in each chromosome, methylation sites adjoining within base pairs are aggregated and form distinct regions from methylation sites adjoined by more than base pairs. such regions provide a spatial context for methylation sites, grouping and isolating distant chromosomal regions. this is an important step for subsequent clustering based on the similarity of methylation profiles. - clustering on the basis of similarity: in this step, methylation profiles are clustered to identify cross-similarities within each region. prior to the clustering, however, methylation profiles are pre-processed and represented by the largest principal components, which embed 99% of the data underlying variance. this is a standard approach and well documented in the machine learning literature. clustering high-dimensional data in their principal component space results in lower computational complexity and lower risk from the curse of dimensionality. the clustering method used here is unsupervised, and based on k-spectral clustering, as discussed below. given a set of methylation profiles across l cell line principal components, the algorithm starts by computing an affinity matrix a whose diagonal elements aii = and off-diagonal elements are next, the k largest principal components are computed from the matrix where d is a diagonal matrix whose di,i elements are the sum of a's i-th row. let x be the n × k matrix that is formed by the k largest principal components of l. k-means clustering is then applied to the normalized matrix y, whose elements are represented by. finally, the methylation profiles si receive the same clustering assignment proposed for y by k-means, i.e., a profile is assigned to cluster j if and only if row yi is assigned to cluster j. the above formulation of ksc requires parameter setting for the variables σ and k. σ determines the magnitude of the exponential decay in the computation of the affinity matrix a. its value plays a role on the determination of boundaries between adjacent clusters. k specifies the number of clusters, which controls the amount of data quantization, but is often difficult to be determined in practice. a simple yet effective strategy to infer these parameters involves clustering with different combinations of the parameters and estimating the compactness of the inferred clusters. one way to characterize cluster compactness is to measure the cluster's internal homogeneity over external heterogeneity. this relation can be mathematically defined by the ratio of, where w is the maximum distance between a point within a cluster and its center, and b is the minimum distance between two cluster centers. in our implementation, we partition the space of k and σ into fixed intervals, perform ksc for each enumerated pair of variables, and select the pair that produces the minimum measure of compactness. a representative methylation profile for each cluster is then computed by averaging all methylation measurements across cell lines. we tested this approach on synthetic data with linear and nonlinear boundaries to predict the validity of the results. figure demonstrates the selection of ksc's optimal parameters σ and k for synthetic data equally distributed into three concentric circles. the compactness measures, produced by each pair of parameters, are then normalized and shown as a heat map. the minimum value is marked by the blue box. methylation-expression association each representative methylation site, averaged over members of the same cluster, is associated with a gene or a set of genes. the association uses only the methylation site and the gene's probe set base range. a gene may have multiple probe sets in the expression data, which cover different portions of a chromosome. these associations are created for representative methylation sites being within a gene probe set, or within a -base-pair window adjacent to the gene probe set. the latter accounts for natural uncertainties for locating a potential cpg island along the dna. logistic regression and assignment of p-value in order to characterize a negative correlation between the methylation and expression data, we perform logistic regression of the methylation-expression associations. to this end, we experimented with several functional representations and propose a generic model, with flexible degrees of freedom, corresponding to an exponential curve of the form: where e and m are respectively the expression and methylation measurements for each cell line, and a, b, and c are the free variables of the logistic model. evaluation of the logistic regression on synthetic data reveals that expected inverse relationship between expression and methylation can be correctly ranked. note that r is the correlation coefficient by which the associations are ranked. it reflects the quality of the logistic regression and, consequently, the method's confidence in an epigenetic regulation. where ssr = ∑) and sse = ∑ and r = indicates a perfect fit to the model. the corresponding p-value is estimated for each association by computing: the p-value is computed by comparing the value of r resulting from the curve regression, and the values of rm, m =...,m, resulting from m attempts for fitting the same curve after permuting the methylation measurements of each association. in our implementation, m is set at.  data sets the raw data was composed of cpg methylation measurements containing, among others, the chromosome number, chromosomal sampling site, and the methylation profile across cell lines. we filtered the original array to cpg methylation sites, which contained valid chromosomal annotation data. with respect to gene expression data, we used publicly available data for a the panel of breast cancer cell lines. each array consists of probe sets containing both luminal and basal subtypes. forty-five cell lines were found in common between the icbp expression data and the mtacl methylation data, and only data for the common cell lines were used for analysis. all expression measurements were transformed from the logarithmic scale to decimal units and normalized between 0-100% across the whole data set so the measurements were consistent with methylation. forty-five cell lines were found in common between the icbp expression and the mtacl methylation data. the cell lines listed here formed the gene signature used in our analysis. dimensionality reduction the first clustering step grouped the methylation sites on the affymetrix array into distinct clusters across chromosomes. out of these regions, the second clustering step generated clusters, and produced representative methylation patterns by averaging the cluster's respective members. note that this result represents a reduction of around 90% from the original raw data. furthermore, 99% of the cell line's principal components' variance was found to be concentrated in to components, which reveals a high correlation between cell lines. subsequent associations between the reduced methylation data and the gene expression generated associations. logistic regression and assignment of p-value top genes predicted as epigenetically regulated according to our logistic model and p-value calculation. methylation-expression associations for underlined genes are shown in figure we have compared the percentage of selected markers with two cancer-specific gene data sets of genes that the cancer genome atlas project is targeting for sequencing, and genes that were selected using prediction analysis of microarrays data as described in. the tcga gene set represents genes that are widely expressed in cancer whereas pam gene set represents breast cancer subtypes. we found that 66% and 22% of our gene list are also in the tcga and the pam data sets, respectively. this analysis is promising since the tcga gene list is not specific to breast tissue, and the pam data set does not incorporate methylation data; thus, by incorporating methylation data, a reduced number of biomarkers can be hypothesized. epigenetically regulated genes our protocol has identified genes that are epigenetically regulated. here, we briefly discuss col1a top2a, vav cdkn2a, and tff, by comparing them against known literature. methylation maps for genes in relation to the regulated genes are shown in additional file col1a plays important role in collagen production and tumor development, and is hypermethylated and down-regulated in about 40% of the icbp cell lines. let us assume that hypermethylation and up-regulation accounts for measurements above the 50% threshold. it is interesting to note that our method has identified epigenetic regulation of col1a even in the presence of only up-regulated cell lines. these lines are not outliers as the computational protocol has generated a hypothesis for further bioinformatics analysis. epigenetic regulation of col1a is consistent with the published literature, which suggests that its down-regulation correlates with hypermethylation, and is a frequent event in breast cancer cell lines such as mcf and hs578t. furthermore, aberrant methylation of col1a has been identified in medulloblastoma and hepatoma, where biallelic methylation of col1a was observed in 77% of medulloblastomas, in addition to be shown to distinguish histological subtypes of tumors. top2a is an enzyme involved in controlling the topological state of the dna machinery. approximately 50% of icbp cell lines are hypomethylated and up-regulated top2a. top2a is a good prognostic marker in breast cancer and response to therapy, a prognostic factor for er-positive breast cancer, and is epigenetically regulated for cellular assembly and organization in lymphoblastoid cell lines. tff1's function is not well known to date. however, it has been widely studied because of its presence in human tumors. for example, a recent study has identified and validated over-expression of tff in breast carcinoma. another study has concluded decreased methylation levels in breast tumor cells, while a much older study states that tff expression is regulated by dna methylation in breast cancer. vav is a nucleotide exchange factor that activates rearrangement of actin filament, and its association shows that only cell lines are hypermethylated. epigenetic regulation of vav is consistent with a recent report showing that 83% of breast tumors overexpress vav. cdkn2a is part of the cell cycle machinery and is an important tumor suppressor gene. our analysis indicates that cdkn2a is hypermethylated and down-regulated in only about 30% of the samples, whereas the majority of the samples are hypomethylated and down-regulated. this discrepancy can be explained by dna copy number loss or cdkn2a mutation, which is frequently associated with pathophysiology of certain types of cancers, including breast cancer. subnetwork enrichment analysis although gene-by-gene analysis is a traditional and viable bioinformatics approach, modern analyses can benefit from enrichment strategies. here, we have applied the predicted genes for subnetwork enrichment through pathway studio. it is noteworthy that common regulators with or more predicted genes have been identified, and that these regulators are of the type "pathway". table lists the top subnetworks according to their p-value. a complete spreadsheet of the common regulators and their targets can be found in additional file analysis of these subnetworks suggests that epigenetic regulation of individual genes occurs in a coordinated fashion and through common regulators. an example is shown in figure where jun/fos complex has been shown to be a common regulator for a number of predicted epigenetic biomarkers. jun and fos, together with the ap transcription factor, drive expression of a number of genes necessary for cell cycle progression, including s100a s100a was also predicted by our protocol and has been implicated in breast cancer and its repression in tumor cells is mediated by site-specific methylation. figure shows interaction of two common regulators and predicted epigenetic markers. subnetwork enrichment and the presence of a large number of common regulators further substantiate our methodology. top lowest p-valued pathways identified by subnetwork enrichment analysis of the predicted genes through pathway studio. common regulator, genes involved and respective p-values are shown. the occurrence of multiple predicted markers within the same pathway suggests that epigenetic regulation of individual genes occurs in a coordinated fashion and through common regulators. subtype-specific epigenetic regulation one aspect of data analysis in cancer biology is to identify subtypes within the tumor lines. our analysis indicates that there is evidence of subtype methylation with respect to the previous classification of basal a, basal b, and luminal lines, where these subtypes were shown to have dna copy number changes similar to those of the respective subtypes found in primary breast tumors. our protocol suggests that the luminal marker gata and basal marker cd are epigenetically regulated and cell line specific. for example, figure indicates that luminal lines have low expression as a function of methylation for cd, although the basal lines are epigenetically regulated; and the opposite holds for gata.  in this paper, we proposed a computational pipeline for identifying epigenetically regulated genes for a panel of breast cancer cell lines. the protocol avoids excessive computational complexity through a step-wise reduction of methylation data for the required expression data associations. to this end, a twofold clustering approach explored both the proximity of methylation sites and similarities among methylation profiles across cell lines. k-spectral clustering was presented and used in the latter step. as a result of data clustering, a number of representative methylation profiles were generated for direct association with candidate genes. epigenetic regulation was estimated from logistic regressions of the methylation-expression associations and its significance verified through the computed p-value. the computational pipeline was applied to a panel of breast cancer cell lines, and the protocol identified a list of genes, including col1a top2a, tff and vav whose key roles in epigenetic regulation are consistent with known literature. subnetwork enrichment of these markers identified common regulators of the type "pathway" with or more predicted genes, further suggesting that epigenetic regulation of individual genes occurs in a coordinated fashion and through common regulators. our current efforts focus on associating methylation data with the therapeutic responses and other biological data derived from the same panel of cell lines. competing interests the authors declare that they have no competing interests. authors' contributions lal and bp designed and implemented the computational protocol, and drafted the manuscript. ps and jwg established the biological questions and computational requirements, designed the experiment and provided material to affymetrix. as contributed to some biological analysis of the results, assisting with suggestions to the manuscript. sd produced the maps of methylation for the epigenetically regulated genes. sn, df, vc, mm, yl and mf conducted the experiments resulting in available data from the icbp panel of breast cancer cell lines. all authors read and approved the final manuscript. supplementary material additional file 1 maps of methylation for the epigenetically regulated genes. each graph shows a map of methylation in relation to the top epigenetically regulated genes from table the respective r values are represented by the magnitude of the yellow bars, plotted over the methylation site responsible for the highest ranked association with each gene click here for file additional file 2 list of common regulators through subnetwork enrichment. subnetwork enrichment analysis of the predicted genes through pathway studio identified common regulators of the type "pathway" with or more predicted genes. common regulator, subnetwork type, total number of neighbors, number of overlapping markers, percentage of overlapping markers, gene set seed, overlapping markers, p-value and rank number are shown. click here for file acknowledgements this work was supported by the director, office of science, office of biological & environmental research, of the u.s. department of energy under contract no. de-ac02-05ch and by the national institutes of health, national cancer institute grants p ca and the u ca 
our protocol has generated a list of predictors including col1a top2a, tff and vav genes whose key roles in epigenetic regulation is documented in the literature. our results indicate that the proposed computational protocol is a viable platform for identifying epigenetically regulated genes. here, we propose a computational pipeline for integrating gene expression and cpg island methylation profles to identify epigenetically regulated genes for a panel of breast cancer cell lines, which is widely used in the integrative cancer biology program. finally, the methylation-expression associations are ranked through a logistic regression, and their significance is quantified through permutation analysis. the pipeline reduces the dimensionality of the methylation data, associates the reduced methylation data with gene expression data, and ranks methylation-expression associations according to their epigenetic regulation. associations between the clustered methylation and the gene expression data sets generate candidate matches within a fxed neighborhood around each gene. methylation of cpg islands within the dna promoter regions is one mechanism that leads to aberrant gene expression in cancer. in particular, the abnormal methylation of cpg islands may silence associated genes. subnetwork enrichment of these genes has identifed common regulators with or more predicted markers. subnetwork enrichment of these predicted markers further suggests that epigenetic regulation of individual genes occurs in a coordinated fashion and through common regulators. dimensionality reduction is performed in two steps: methylation sites are grouped across the genome to identify regions of interest, and methylation profles are clustered within each region. our two-step dimensionality reduction compressed 90% of the original data, reducing methylation sites to clusters. therefore, using high-throughput microarrays to measure cpg island methylation will lead to better understanding of tumor pathobiology and progression, while revealing potentially new biomarkers. logistic regression was used to identify genes from these correspondences that showed a statistically signifcant negative correlation between methylation profles and gene expression in the panel of breast cancer cell lines. methylation-expression associations produced correspondences, which were used to further analyze epigenetic regulation.
 methylation of cpg islands within the dna promoter regions is one mechanism that leads to aberrant gene expression in cancer. in particular, the abnormal methylation of cpg islands may silence associated genes. therefore, using high-throughput microarrays to measure cpg island methylation will lead to better understanding of tumor pathobiology and progression, while revealing potentially new biomarkers. we have examined a recently developed high-throughput technology for measuring genome-wide methylation patterns called mtacl. here, we propose a computational pipeline for integrating gene expression and cpg island methylation profles to identify epigenetically regulated genes for a panel of breast cancer cell lines, which is widely used in the integrative cancer biology program. the pipeline reduces the dimensionality of the methylation data, associates the reduced methylation data with gene expression data, and ranks methylation-expression associations according to their epigenetic regulation. dimensionality reduction is performed in two steps: methylation sites are grouped across the genome to identify regions of interest, and methylation profles are clustered within each region. associations between the clustered methylation and the gene expression data sets generate candidate matches within a fxed neighborhood around each gene. finally, the methylation-expression associations are ranked through a logistic regression, and their significance is quantified through permutation analysis.  our two-step dimensionality reduction compressed 90% of the original data, reducing methylation sites to clusters. methylation-expression associations produced correspondences, which were used to further analyze epigenetic regulation. logistic regression was used to identify genes from these correspondences that showed a statistically signifcant negative correlation between methylation profles and gene expression in the panel of breast cancer cell lines. subnetwork enrichment of these genes has identifed common regulators with or more predicted markers. in addition to identifying epigenetically regulated genes, we show evidence of differentially expressed methylation patterns between the basal and luminal subtypes.  our results indicate that the proposed computational protocol is a viable platform for identifying epigenetically regulated genes. our protocol has generated a list of predictors including col1a top2a, tff and vav genes whose key roles in epigenetic regulation is documented in the literature. subnetwork enrichment of these predicted markers further suggests that epigenetic regulation of individual genes occurs in a coordinated fashion and through common regulators. 