BACKGROUND
we previously developed gominer  <cit>  and high-throughput gominer  <cit> , applications that organize lists of "interesting" genes  for biological interpretation in the context of the gene ontology  <cit> .
gominer and related tools typically generate a list of significant functional categories.
in addition to lists and tables, high-throughput gominer also provides a valuable graphical output termed a "clustered image map" .
the "integrative" and "individual" cims can depict the relationship between categories and either multiple experiments or genes, respectively.
when designing an algorithm for a program like gominer, a number of implementation decisions must be made.
one such decision is how to handle genes mapping to a category that is a child of the category under consideration.
the particular algorithm adopted by gominer "rolls up" genes mapping to a child category; that is, genes mapping to a child category are  assigned to the parent of that child category.
although that approach provides robust protection against variability in curation techniques, it can result in redundancy between parent and child categories.
even in the absence of "rolling up," redundancy can be an important issue.
that is, two non-parent/child categories may include identical or nearly-identical sets of genes.
overall, the redundancy can easily inflate by a factor of about three the number of categories that are considered statistically significant, create an illusion of an overly long list of significant categories, and obscure the relevant biological interpretation.
one way of addressing redundancy is exemplified by go slims  <cit> : "go slims are cut-down versions of the go ontologies containing a subset of the terms in the whole go.
they give a broad overview of the ontology content without the detail of the specific fine grained terms.
go slims are particularly useful for giving a summary of the results of go annotation of a genome, microarray, or cdna collection when broad classification of gene product function is required."
however, in the context of gominer analysis, the go slims approach has several drawbacks:
• it cannot deal with redundancy that might not result from "rolling up"
• it is rather inflexible, as it is pre-computed and cannot adapt to the characteristics of a particular data set
• it "throws out the baby with the bathwater:" a simplified view might be a useful first approximation, but the molecular biologist also needs to be able to "drill down" to see the full details
we propose here a solution that overcomes these limitations of go slims.
full details are given in the methods section.
briefly, our approach, redundancyminer, de-replicates the  redundant go categories: the user selects a desired redundancy threshold, and a new reduced clustered imaged map  is created.
that cim represents those categories that were not affected by the processing, as well as composite categories that represent groups of merged categories.
an additional new type of cim is also created, which we term a "meta cim."
the meta cim conveniently visualizes the pattern of grouping within the merged categories.
thus, an overview is afforded by the reduced cim, and the details by the meta cim.
furthermore, the redundancy computation can be based on either  all genes that map to a category or  just the genes that exhibited altered expression levels in the current experiment.
the latter approach  will provide a meta cim that reflects redundancy and interaction between categories that is specific to the conditions of the study.
this pattern may be significantly different from the static reference behavior obtained by approach , and it may suggest the underlying systems biology.
the meta cim does not simply discard redundancy, as might be the case for go slims; rather, it processes the patterns of redundancy and extracts information from them.
ignoring the existence of redundancy, as go slims does, is an oversimplification that may throw away valuable information.
a number of other earlier papers address related issues.
several of those papers address approaches to studying gene enrichment, but not specifically the redundancy problem.
for example, pehkonen  <cit>  developed a method that clusters genes to groups with homogenous functionalities.
the method uses nonnegative matrix factorization  to create several clustering results with varying numbers of clusters.
the clustering results are combined into a simple graphical presentation showing the functional groups over-represented in the analyzed gene list.
prufer  <cit>  developed "func," a package for detecting significant associations between gene sets and ontological annotations.
xu  <cit>  developed "ceago," enriching clustered go terms based on semantic similarity.
hermann  <cit>  developed "simct," which draws a simplified representation of biological terms present in the set of objects
several papers address approaches to address the redundancy problem within the context of studying gene enrichment, and are therefore potentially more germane.
for example, alexa  <cit>  proposed a method "topw" to eliminate local dependencies between go terms; lu  <cit>  developed "gengo," a generative probabilistic model which identifies a small subset of categories that, together, explain the selected gene set; and grossmann  <cit>  developed the "ontologizer" that uses the parent child union  to reduce the dependencies between the individual term's measurements, and recomputes the p-value for a specific category by taking into account the immediately more general terms .
that procedure can often lead to the removal of false positives, since some of the more specific categories are eliminated if their parent category is determined to be significant.
the more recent global "mgsa" method of bauer  <cit>  outperformed the local methods of alexa, lu, and grossmann.
finally, richards  <cit>  recently developed a novel global approach to assess the functional coherence of gene sets by taking into account both the enrichment of go terms and their relationships among terms.
in summary, the two most promising of the previously published methods for addressing redundancy are those of bauer and richards.
however, unlike redundancyminer, neither of those methods takes advantage of the redundancy patterns to infer subtle nuanced themes among groups of go categories.
redundancyminer's meta cim is shown here to be of great potential value in such analyses.
implementation
overview
a typical sequence of steps would be:
• prepare a list of "changed" or "interesting" genes
○ i.e., over-expressed genes in a microarray experiment
• prepare a list of "total" genes
○ i.e., all genes appearing on the microarray
• run high-throughput gominer  on the two gene lists
○ generate a mapping of "changed" genes to statistically significant go categories
• run redundancyminer on the cim representing the gene to category mapping
○ generate a reduced-redundancy cim
○ generate a meta cim that captures the nuances of the redundancy
the first  <dig> steps are preparatory to running redundancyminer; they are not an integral part of redundancyminer itself.
high-throughput gominer
gominer  <cit>  is a tool for biological interpretation of 'omic' data, including data from gene expression microarrays and state of the art sequencing technologies.
it leverages the gene ontology  to identify "biological processes," "molecular functions," and "cellular components" represented in a list of genes.
high-throughput gominer   <cit> , which was used for many of the analyses reported here, is an enhancement of gominer that efficiently performs the computationally-challenging task of automated batch processing of an arbitrary number of such gene lists.
in addition to generating results for each individual input gene list, htgm also generates integrative results that relate the entire set of input files.
in particular, htgm generates an integrative cim that shows the fdr of the significant go categories versus the experiments.
a go category is enriched if the number of changed genes that htgm assigned to it is statistically significantly greater than the number expected by chance.
a category is considered significant if its fisher's exact p-value and its false discovery rate  are both less than or equal to a user-selected threshold .
see  <cit>  for detailed discussions of gominer and htgm, including calculations of statistical significance.
the parameters used in all of the htgm analyses are listed in additional file  <dig>
clustered image maps
clustered image maps , first introduced for omic studies in the mid-1990's by members of our group  <cit> , were produced here with the genesis program  <cit> .
in general, a cim is a visual representation of a two-dimensional table of numerical values, in which hierarchical clustering has been performed along one or both axes.
the numerical values are mapped to a pseudo-color scale.
we often use cims to represent the mapping of genes to go categories.
one axis represents genes and the other axis represents go categories.
the numerical values in the table are 0's  and 1's , designating the absence  or presence  of the gene in the category.
we selected the euclidean distance metric and average linkage for hierarchal clustering.
to facilitate visualization, we implemented a recently-added optional feature of gominer to remove very large generic categories from all cims.
overview of redundancyminer computation stream
there are three salient features of our practical solution to the redundancy problem:
definition of a similarity metric to capture the degree of relatedness of go categories
generation of a set of non-redundant groups of go categories clustered by clique decomposition, as implemented by the multiclust algorithm
visualization of cims of the non-redundant groups
we will describe our approach to those three features, and demonstrate their effectiveness in the context of analysis of gene expression microarray data.
definition of a similarity metric
the similarity metric is the fisher's exact p-value.
for each pair of significant categories, we compute the fisher's exact p-value corresponding to the null hypothesis that the sets of genes mapping to the two categories are statistically independent.
the  <dig> ×  <dig> contingency table for the one-tail fisher's exact test is given in table  <dig>  our java implementation of the fisher's exact test is based on javascript by Øyvind langsrud  <cit> .
in first category
not in first category
row sums
in second category
not in second category
column sums
{ai} and {bi} are the sets of genes mapping to the first and second categories, respectively.
prime indicates the complement of a set.
{ai} ∪ {ai}' represents the set of genes mapping to the root go category.
as suggested by wang  <cit> , bias in the annotation of go can result in bias in subsequent analyses that use go.
wang observed a correlation between a protein's annotation length  and the semantic similarity scores.
such a bias is not expected to affect the redundancyminer similarity metric, since
• the bias studied by wang arises from the fact that a heavily-studied protein will be mapped to a relatively large number of go categories, since relatively more is known about the functions of that protein.
thus, when that protein is represented as a vector of associated go categories, that vector will be overly long.
however, we are here proposing redundancyminer as a method to compare vectors of go categories, not vectors of proteins.
biases in the number of studies for a given protein will not differentially bias the length  in a go category vector.
• the metric that we use is based upon fisher's exact p-value.
thus, if two go category vectors are both highly populated with 1's, a high degree of overlap will not produce an artifactually significant  score, since the computation of the p-value is explicitly based upon the probability of the observed degree of overlap relative to the proportion of 1's in the two vectors being compared.
the relevant  <dig> ×  <dig> contingency table, which explicitly takes the proportion of 1's into account, is shown in table  <dig>
generation of a set of de-replicated groups by redundancyminer's multiclust algorithm
we first compute a similarity matrix composed of fisher's exact p-values.
next we select a desired p-value threshold.
this selection is based on an estimate of "nominal number of merged pairs" .
we then apply the selected p-value threshold to the elements of the matrix to generate an undirected graph g whose vertices are go categories.
two vertices are connected if the similarity between the two vertices is larger than the given threshold.
the goal of this process is to find a clique decomposition of g and then consider each clique as a de-replicated functional group  <cit> .
the clique decomposition is equivalent to the identification of a set of maximal cliques that cover all vertices in g. the procedure is summarized here in pseudo-code:
variables:
• reference - list of n significant categories
• similarity - n × n matrix of pairwise similarity values
• cluster - list of current set of clusters
• change - an indication that there is a change in cluster
change = true
while {
change = false
for each c in cluster
for each ref in reference but not in c
if the similarity between ref and every vertex in c is larger than the given threshold
change = true
update c to include ref
endif
endfor
endfor
cluster = list of current set of unique clusters
endwhile
the condition "if the similarity between ref and every vertex in c is larger than the given threshold" corresponds to "complete linkage clustering," so the result is independent of the order of computing the elements of cluster c.
visualization of cims of the de-replicated groups
after deriving the new groups, each of which corresponds to a clique obtained in the previous step, the value displayed in the modified cim depends on the type of input cim, as shown in table  <dig>
input type
output values
categories versus genes
experiments versus genes
to summarize, the input is a  cim, and the output is a de-replicated cim with the original redundant categories merged into a group whose name is the concatenation of names of the member categories.
it is possible  for any of the original categories to appear in multiple merged groups.
running redundancyminer
overview
redundancyminer consists of a set of perl modules  and a java gui.
the java gui is intended to provide optimal convenience for the molecular biologist, whereas the perl modules allow the developer to integrate redundancyminer's functionalities into a custom high-throughput data processing stream.
the gui can be invoked either by double-clicking the icon, or by entering "java -jar redundancyminer.jar" in a terminal window.
the latter method is preferred, since it provides a trace of the execution.
the archived java and perl modules are available as additional file  <dig> and the most recent version can be downloaded from the supplementary materials web page.
the various types of htgm output files that may be used as input to redundancyminer are tabulated in additional file  <dig>
modes
• default mode: the goal is to generate a consistent set of collapsed cims for an entire htgm output directory based on a common meta cim pattern derived from the integrative cim
○ the user selects the htgm output directory
○ redundancyminer generates a meta cim only for the htgm integrative cim, but not for each htgm individual cim
○ the collapsing pattern for the integrative cim is used for collapsing each htgm individual cim
○ the resulting reduced cims are stored in the same directory as the corresponding htgm cim
• custom mode: compared to the default mode, the user has more control over the threshold and the choice of the file to define the categories/genes structure
○ the user selects one specific cim to process
○ the user selects a threshold for collapsing
○ the user selects a file type  to define the categories/genes structure
○ the output  is directed to a special temp directory
user's manual
a user's manual is provided in the form of a powerpoint presentation  and a .pdf file .
a simplified version of the htgm result directory that is exemplified in the user's manual is available as additional file  <dig>
experimental studies
retinal development
full details are provided in  <cit> .
briefly, to better understand gene regulatory patterns in congenital defects of ocular development, we laser capture-microdissected tissue samples from embryonic mouse retina at the site of optic fissure closure at  <dig> time points .
the affymetrix moe  <dig>  <dig>  microarray was used to analyze gene expression levels.
to identify associated gene regulation patterns in  <dig> genes whose expression levels varied between 4-fold and 26-fold, we applied laplacian eigenmaps  to the temporal microarray data.
k-means clustering of the temporal expression profiles generated  <dig> coherent gene groups.
we used gominer to facilitate identification of further gene regulatory associations in human ocular development, and to determine the biological themes that are represented by the genes in each cluster.
we chose the largest cluster , containing  <dig> genes , for redundancyminer analysis.
kinetochore genes
the list of  <dig> kinetochore genes  was manually compiled by expert literature curation by one of us .
the gominer results are available as additional file  <dig>
RESULTS
to highlight the characteristics and value of the redundancyminer approach, we next present analyses of two different types of data sets:
• the gene expression profile obtained by laser-capture microdissection  of serial cryosections of the retina at the site of final optic fissure closure in the mouse embryos at specific embryonic stages  <cit> .
• a conceptual data set obtained by examining a list of genes deemed to be "kinetochore" genes
retinal development
each row of the original cim  represents a statistically significant go category, and each column represents an input gene that was mapped to at least one of these categories.
that cim is quite complex, containing  <dig> categories, many of which are redundant  with respect to one another.
to remove that complexity from the original cim and transfer the information to the meta cim, we ran redundancyminer at a level of stringency corresponding to a nominal number of merged pairs =  <dig>  the reduced cim  was significantly less complex, containing only  <dig> categories .
although the experience is inherently subjective, it seems clear that the reduced cim is more readily amenable to visual interpretation.
the smaller number of categories and the reduction of redundancy make it easier to discern the major biological themes that are relevant to retinal development, e.g., biological adhesion, cell projection organization, eye morphogenesis, and axon regeneration.
the clustering performed by redundancyminer is more complex than traditional clustering, since a category may appear in more than a single cluster.
for instance, regulation of phosphorus metabolic process appears twice in the reduced cim , in redundancyminer clusters  <dig> and  <dig>  the subtle reason for this dichotomy is revealed by the meta cim .
cluster  <dig> reflects the sub-theme positive regulation of protein kinase activity, whereas cluster  <dig> reflects a related, but slightly different, sub-theme, positive regulation of protein amino acid phosphorylation.
all instances of this type of relationship can easily be found by examination of the meta cim.
consider the row corresponding to a particular category of interest.
if there is more than a single red element in that row, then that category is involved in multiple redundancyminer clusters.
for example, axonogenesis is a member of clusters  <dig> and  <dig>  cluster  <dig> reflects regulation of neuron differentation, whereas cluster  <dig> reflects central nervous system development.
just as genes may map to multiple categories in go, the next higher level of organization involves the mapping of categories to different category clusters that represent subtly different functionalities.
note that in the go slims approach, the simplification is performed prior to the experiment, and so the pattern of redundancy reduction and information persistence is not dynamically optimized for the experiment at hand.
furthermore, go slims would entirely miss the richness of detail that is available in the meta cim.
kinetochore genes
as was the case for retinal development, the original cim  is again quite complex, containing  <dig> categories.
to reduce the complexity in the original cim and transfer the information to the meta cim, we compared the effect of running redundancyminer at two levels of stringency.
the more stringent level  yields a reduced cim  containing  <dig> categories , and a meta cim containing  <dig> clusters .
the more permissive level  yielded a reduced cim  containing  <dig> categories , and a meta cim containing  <dig> clusters .
the two different compression ratios demonstrate the fine control that the user has in partitioning the complexity and information between the cim and the meta cim.
for instance, the more complex meta cim  contains an instance of categories  that are involved in three different clusters .
those clusters represent rna localization, intracellular transport, and nuclear transport, respectively.
as the stringency level is reduced, there is often an increase in the multiplicity of clusters containing a common category.
the user can choose to explore the meta cims generated at several different stringency levels, to find the optimal visualization of the relationship of the most interest.
CONCLUSIONS
we have presented the redundancyminer analysis of retinal development and kinetochore genes.
in both cases, redundancyminer facilitates the visual interpretation of the primary cim image.
in the original cim images, there is a high degree of complexity arising from detailed, but relatively redundant, information.
the visual complexity is significantly reduced by shifting the information in the redundant categories to the meta cim.
in contrast to the original cim, the display of the redundancy pattern in the meta cim provides valuable insight into the fine structure of the biological correlate of the gene expression pattern.
availability and requirements
the most recent versions of the redundancyminer program package and user's manual can be downloaded from http://discover.nci.nih.gov/rm/supplementarymaterials.html.
additional file  <dig> provides information for developers about the relationships of the rm and htgm files.
redundancyminer was developed using perl  and java .
in order to execute redundancyminer, perl  and java virtual machine  need to be installed and accessible to the operating system.
authors' contributions
brz developed the project, and wrote the manuscript.
hl devised and implemented the clustering algorithm, produced the java and perl code, and constructed the powerpoint user manual.
abk and jnw were involved in initial discussions about potential approaches to address the redundancy issue.
me, vnr, and rfb performed the clustering analysis of the retinal data sets.
jdb and bpb generated retinal data.
vll and wr curated and maintained the kinetochore data set.
yp provided overall scientific guidance for all of the work that was performed.
all authors read and approved the final manuscript.
supplementary material
additional file 1
parameters used in htgm analyses.
table of parameters used in htgm analyses.
click here for file
additional file 2
perl modules.
table of perl modules and their function.
click here for file
additional file 3
redundancyminer program package download.
the code for running redundancyminer on your own computer.
click here for file
additional file 4
types of htgm gene-category association files used by redundancyminer.
table of types and descriptions of htgm files used by redundancyminer.
click here for file
additional file 5
powerpoint user's manual.
powerpoint version of the redundancyminer user's manual.
click here for file
additional file 6
pdf format of powerpoint user's manual.
.pdf version of the redundancyminer user's manual.
click here for file
additional file 7
simplified version of the htgm result directory that is exemplified in the user's manual.
htgm result directory to be used in conjunction with the examples given in the redundancyminer user's manual.
click here for file
additional file 8
retinal development htgm download.
compressed package of the results of running htgm on the retinal development genes list.
click here for file
additional file 9
kinetochore genes.
table listing kinetochore genes.
click here for file
additional file 10
kinetochore genes htgm download.
compressed package of the results of running htgm on the kinetochore genes list.
click here for file
additional file 11
original genes versus categories cim for an interesting retinal development time-series cluster.
.png image of original genes versus categories cim for an interesting retinal development time-series cluster.
click here for file
additional file 12
reduced cim of retinal development genes versus categories.
.png image of reduced cim of retinal development genes versus categories.
click here for file
additional file 13
meta cim of retinal development categories versus meta cim group.
.png image of meta cim of retinal development categories versus meta cim group.
click here for file
additional file 14
original kinetochore genes versus categories cim.
.png image of original kinetochore genes versus categories cim.
click here for file
additional file 15
reduced cim of kinetochore genes versus categories.
.png image of reduced cim of kinetochore genes versus categories.
click here for file
additional file 16
meta cim of kinetochore categories versus meta cim group.
.png image of meta cim of kinetochore categories versus meta cim group.
click here for file
additional file 17
reduced cim of kinetochore genes versus categories.
.png image of reduced cim of kinetochore genes versus categories.
click here for file
additional file 18
meta cim of kinetochore genes versus categories.
.png image of meta cim of kinetochore genes versus categories.
click here for file
additional file 19
information for developers.
table of the relationship of rm and htgm files.
click here for file
acknowledgements
this research was supported in part by the intramural research program of the nih, national cancer institute, center for cancer research.
the work by jnw was supported in part by a generous gift from the chapman foundation.
hf is supported by the nih grant r01lm009959a <dig>

 we previously developed gominer and high-throughput gominer, applications that organize lists of "interesting" genes for biological interpretation in the context of the gene ontology. gominer and related tools typically generate a list of significant functional categories. in addition to lists and tables, high-throughput gominer also provides a valuable graphical output termed a "clustered image map". the "integrative" and "individual" cims can depict the relationship between categories and either multiple experiments or genes, respectively. when designing an algorithm for a program like gominer, a number of implementation decisions must be made. one such decision is how to handle genes mapping to a category that is a child of the category under consideration. the particular algorithm adopted by gominer "rolls up" genes mapping to a child category; that is, genes mapping to a child category are assigned to the parent of that child category. although that approach provides robust protection against variability in curation techniques, it can result in redundancy between parent and child categories. even in the absence of "rolling up," redundancy can be an important issue. that is, two non-parent/child categories may include identical or nearly-identical sets of genes. overall, the redundancy can easily inflate by a factor of about three the number of categories that are considered statistically significant, create an illusion of an overly long list of significant categories, and obscure the relevant biological interpretation. one way of addressing redundancy is exemplified by go slims: "go slims are cut-down versions of the go ontologies containing a subset of the terms in the whole go. they give a broad overview of the ontology content without the detail of the specific fine grained terms. go slims are particularly useful for giving a summary of the results of go annotation of a genome, microarray, or cdna collection when broad classification of gene product function is required." however, in the context of gominer analysis, the go slims approach has several drawbacks: • it cannot deal with redundancy that might not result from "rolling up" • it is rather inflexible, as it is pre-computed and cannot adapt to the characteristics of a particular data set • it "throws out the baby with the bathwater:" a simplified view might be a useful first approximation, but the molecular biologist also needs to be able to "drill down" to see the full details we propose here a solution that overcomes these limitations of go slims. full details are given in the methods section. briefly, our approach, redundancyminer, de-replicates the redundant go categories: the user selects a desired redundancy threshold, and a new reduced clustered imaged map is created. that cim represents those categories that were not affected by the processing, as well as composite categories that represent groups of merged categories. an additional new type of cim is also created, which we term a "meta cim." the meta cim conveniently visualizes the pattern of grouping within the merged categories. thus, an overview is afforded by the reduced cim, and the details by the meta cim. furthermore, the redundancy computation can be based on either all genes that map to a category or just the genes that exhibited altered expression levels in the current experiment. the latter approach will provide a meta cim that reflects redundancy and interaction between categories that is specific to the conditions of the study. this pattern may be significantly different from the static reference behavior obtained by approach, and it may suggest the underlying systems biology. the meta cim does not simply discard redundancy, as might be the case for go slims; rather, it processes the patterns of redundancy and extracts information from them. ignoring the existence of redundancy, as go slims does, is an oversimplification that may throw away valuable information. a number of other earlier papers address related issues. several of those papers address approaches to studying gene enrichment, but not specifically the redundancy problem. for example, pehkonen developed a method that clusters genes to groups with homogenous functionalities. the method uses nonnegative matrix factorization to create several clustering results with varying numbers of clusters. the clustering results are combined into a simple graphical presentation showing the functional groups over-represented in the analyzed gene list. prufer developed "func," a package for detecting significant associations between gene sets and ontological annotations. xu developed "ceago," enriching clustered go terms based on semantic similarity. hermann developed "simct," which draws a simplified representation of biological terms present in the set of objects several papers address approaches to address the redundancy problem within the context of studying gene enrichment, and are therefore potentially more germane. for example, alexa proposed a method "topw" to eliminate local dependencies between go terms; lu developed "gengo," a generative probabilistic model which identifies a small subset of categories that, together, explain the selected gene set; and grossmann developed the "ontologizer" that uses the parent child union to reduce the dependencies between the individual term's measurements, and recomputes the p-value for a specific category by taking into account the immediately more general terms. that procedure can often lead to the removal of false positives, since some of the more specific categories are eliminated if their parent category is determined to be significant. the more recent global "mgsa" method of bauer outperformed the local methods of alexa, lu, and grossmann. finally, richards recently developed a novel global approach to assess the functional coherence of gene sets by taking into account both the enrichment of go terms and their relationships among terms. in summary, the two most promising of the previously published methods for addressing redundancy are those of bauer and richards. however, unlike redundancyminer, neither of those methods takes advantage of the redundancy patterns to infer subtle nuanced themes among groups of go categories. redundancyminer's meta cim is shown here to be of great potential value in such analyses. implementation overview a typical sequence of steps would be: • prepare a list of "changed" or "interesting" genes ○ i.e., over-expressed genes in a microarray experiment • prepare a list of "total" genes ○ i.e., all genes appearing on the microarray • run high-throughput gominer on the two gene lists ○ generate a mapping of "changed" genes to statistically significant go categories • run redundancyminer on the cim representing the gene to category mapping ○ generate a reduced-redundancy cim ○ generate a meta cim that captures the nuances of the redundancy the first steps are preparatory to running redundancyminer; they are not an integral part of redundancyminer itself. high-throughput gominer gominer is a tool for biological interpretation of'omic' data, including data from gene expression microarrays and state of the art sequencing technologies. it leverages the gene ontology to identify "biological processes," "molecular functions," and "cellular components" represented in a list of genes. high-throughput gominer, which was used for many of the analyses reported here, is an enhancement of gominer that efficiently performs the computationally-challenging task of automated batch processing of an arbitrary number of such gene lists. in addition to generating results for each individual input gene list, htgm also generates integrative results that relate the entire set of input files. in particular, htgm generates an integrative cim that shows the fdr of the significant go categories versus the experiments. a go category is enriched if the number of changed genes that htgm assigned to it is statistically significantly greater than the number expected by chance. a category is considered significant if its fisher's exact p-value and its false discovery rate are both less than or equal to a user-selected threshold. see for detailed discussions of gominer and htgm, including calculations of statistical significance. the parameters used in all of the htgm analyses are listed in additional file clustered image maps clustered image maps, first introduced for omic studies in the mid-1990's by members of our group, were produced here with the genesis program. in general, a cim is a visual representation of a two-dimensional table of numerical values, in which hierarchical clustering has been performed along one or both axes. the numerical values are mapped to a pseudo-color scale. we often use cims to represent the mapping of genes to go categories. one axis represents genes and the other axis represents go categories. the numerical values in the table are 0's and 1's, designating the absence or presence of the gene in the category. we selected the euclidean distance metric and average linkage for hierarchal clustering. to facilitate visualization, we implemented a recently-added optional feature of gominer to remove very large generic categories from all cims. overview of redundancyminer computation stream there are three salient features of our practical solution to the redundancy problem: definition of a similarity metric to capture the degree of relatedness of go categories generation of a set of non-redundant groups of go categories clustered by clique decomposition, as implemented by the multiclust algorithm visualization of cims of the non-redundant groups we will describe our approach to those three features, and demonstrate their effectiveness in the context of analysis of gene expression microarray data. definition of a similarity metric the similarity metric is the fisher's exact p-value. for each pair of significant categories, we compute the fisher's exact p-value corresponding to the null hypothesis that the sets of genes mapping to the two categories are statistically independent. the × contingency table for the one-tail fisher's exact test is given in table our java implementation of the fisher's exact test is based on javascript by Øyvind langsrud. in first category not in first category row sums in second category not in second category column sums {ai} and {bi} are the sets of genes mapping to the first and second categories, respectively. prime indicates the complement of a set. {ai} ∪ {ai}' represents the set of genes mapping to the root go category. as suggested by wang, bias in the annotation of go can result in bias in subsequent analyses that use go. wang observed a correlation between a protein's annotation length and the semantic similarity scores. such a bias is not expected to affect the redundancyminer similarity metric, since • the bias studied by wang arises from the fact that a heavily-studied protein will be mapped to a relatively large number of go categories, since relatively more is known about the functions of that protein. thus, when that protein is represented as a vector of associated go categories, that vector will be overly long. however, we are here proposing redundancyminer as a method to compare vectors of go categories, not vectors of proteins. biases in the number of studies for a given protein will not differentially bias the length in a go category vector. • the metric that we use is based upon fisher's exact p-value. thus, if two go category vectors are both highly populated with 1's, a high degree of overlap will not produce an artifactually significant score, since the computation of the p-value is explicitly based upon the probability of the observed degree of overlap relative to the proportion of 1's in the two vectors being compared. the relevant × contingency table, which explicitly takes the proportion of 1's into account, is shown in table generation of a set of de-replicated groups by redundancyminer's multiclust algorithm we first compute a similarity matrix composed of fisher's exact p-values. next we select a desired p-value threshold. this selection is based on an estimate of "nominal number of merged pairs". we then apply the selected p-value threshold to the elements of the matrix to generate an undirected graph g whose vertices are go categories. two vertices are connected if the similarity between the two vertices is larger than the given threshold. the goal of this process is to find a clique decomposition of g and then consider each clique as a de-replicated functional group. the clique decomposition is equivalent to the identification of a set of maximal cliques that cover all vertices in g. the procedure is summarized here in pseudo-code: variables: • reference - list of n significant categories • similarity - n × n matrix of pairwise similarity values • cluster - list of current set of clusters • change - an indication that there is a change in cluster change = true while {       change = false       for each c in cluster          for each ref in reference but not in c             if the similarity between ref and every vertex in c is larger than the given threshold                   change = true                   update c to include ref             endif          endfor       endfor    cluster = list of current set of unique clusters endwhile the condition "if the similarity between ref and every vertex in c is larger than the given threshold" corresponds to "complete linkage clustering," so the result is independent of the order of computing the elements of cluster c. visualization of cims of the de-replicated groups after deriving the new groups, each of which corresponds to a clique obtained in the previous step, the value displayed in the modified cim depends on the type of input cim, as shown in table input type output values categories versus genes experiments versus genes to summarize, the input is a cim, and the output is a de-replicated cim with the original redundant categories merged into a group whose name is the concatenation of names of the member categories. it is possible for any of the original categories to appear in multiple merged groups. running redundancyminer overview redundancyminer consists of a set of perl modules and a java gui. the java gui is intended to provide optimal convenience for the molecular biologist, whereas the perl modules allow the developer to integrate redundancyminer's functionalities into a custom high-throughput data processing stream. the gui can be invoked either by double-clicking the icon, or by entering "java -jar redundancyminer.jar" in a terminal window. the latter method is preferred, since it provides a trace of the execution. the archived java and perl modules are available as additional file and the most recent version can be downloaded from the supplementary materials web page. the various types of htgm output files that may be used as input to redundancyminer are tabulated in additional file modes • default mode: the goal is to generate a consistent set of collapsed cims for an entire htgm output directory based on a common meta cim pattern derived from the integrative cim ○ the user selects the htgm output directory ○ redundancyminer generates a meta cim only for the htgm integrative cim, but not for each htgm individual cim ○ the collapsing pattern for the integrative cim is used for collapsing each htgm individual cim ○ the resulting reduced cims are stored in the same directory as the corresponding htgm cim • custom mode: compared to the default mode, the user has more control over the threshold and the choice of the file to define the categories/genes structure ○ the user selects one specific cim to process ○ the user selects a threshold for collapsing ○ the user selects a file type to define the categories/genes structure ○ the output is directed to a special temp directory user's manual a user's manual is provided in the form of a powerpoint presentation and a.pdf file. a simplified version of the htgm result directory that is exemplified in the user's manual is available as additional file experimental studies retinal development full details are provided in. briefly, to better understand gene regulatory patterns in congenital defects of ocular development, we laser capture-microdissected tissue samples from embryonic mouse retina at the site of optic fissure closure at time points. the affymetrix moe microarray was used to analyze gene expression levels. to identify associated gene regulation patterns in genes whose expression levels varied between 4-fold and 26-fold, we applied laplacian eigenmaps to the temporal microarray data. k-means clustering of the temporal expression profiles generated coherent gene groups. we used gominer to facilitate identification of further gene regulatory associations in human ocular development, and to determine the biological themes that are represented by the genes in each cluster. we chose the largest cluster, containing genes, for redundancyminer analysis. kinetochore genes the list of kinetochore genes was manually compiled by expert literature curation by one of us. the gominer results are available as additional file  to highlight the characteristics and value of the redundancyminer approach, we next present analyses of two different types of data sets: • the gene expression profile obtained by laser-capture microdissection of serial cryosections of the retina at the site of final optic fissure closure in the mouse embryos at specific embryonic stages. • a conceptual data set obtained by examining a list of genes deemed to be "kinetochore" genes retinal development each row of the original cim represents a statistically significant go category, and each column represents an input gene that was mapped to at least one of these categories. that cim is quite complex, containing categories, many of which are redundant with respect to one another. to remove that complexity from the original cim and transfer the information to the meta cim, we ran redundancyminer at a level of stringency corresponding to a nominal number of merged pairs = the reduced cim was significantly less complex, containing only categories. although the experience is inherently subjective, it seems clear that the reduced cim is more readily amenable to visual interpretation. the smaller number of categories and the reduction of redundancy make it easier to discern the major biological themes that are relevant to retinal development, e.g., biological adhesion, cell projection organization, eye morphogenesis, and axon regeneration. the clustering performed by redundancyminer is more complex than traditional clustering, since a category may appear in more than a single cluster. for instance, regulation of phosphorus metabolic process appears twice in the reduced cim, in redundancyminer clusters and the subtle reason for this dichotomy is revealed by the meta cim. cluster reflects the sub-theme positive regulation of protein kinase activity, whereas cluster reflects a related, but slightly different, sub-theme, positive regulation of protein amino acid phosphorylation. all instances of this type of relationship can easily be found by examination of the meta cim. consider the row corresponding to a particular category of interest. if there is more than a single red element in that row, then that category is involved in multiple redundancyminer clusters. for example, axonogenesis is a member of clusters and cluster reflects regulation of neuron differentation, whereas cluster reflects central nervous system development. just as genes may map to multiple categories in go, the next higher level of organization involves the mapping of categories to different category clusters that represent subtly different functionalities. note that in the go slims approach, the simplification is performed prior to the experiment, and so the pattern of redundancy reduction and information persistence is not dynamically optimized for the experiment at hand. furthermore, go slims would entirely miss the richness of detail that is available in the meta cim. kinetochore genes as was the case for retinal development, the original cim is again quite complex, containing categories. to reduce the complexity in the original cim and transfer the information to the meta cim, we compared the effect of running redundancyminer at two levels of stringency. the more stringent level yields a reduced cim containing categories, and a meta cim containing clusters. the more permissive level yielded a reduced cim containing categories, and a meta cim containing clusters. the two different compression ratios demonstrate the fine control that the user has in partitioning the complexity and information between the cim and the meta cim. for instance, the more complex meta cim contains an instance of categories that are involved in three different clusters. those clusters represent rna localization, intracellular transport, and nuclear transport, respectively. as the stringency level is reduced, there is often an increase in the multiplicity of clusters containing a common category. the user can choose to explore the meta cims generated at several different stringency levels, to find the optimal visualization of the relationship of the most interest.  we have presented the redundancyminer analysis of retinal development and kinetochore genes. in both cases, redundancyminer facilitates the visual interpretation of the primary cim image. in the original cim images, there is a high degree of complexity arising from detailed, but relatively redundant, information. the visual complexity is significantly reduced by shifting the information in the redundant categories to the meta cim. in contrast to the original cim, the display of the redundancy pattern in the meta cim provides valuable insight into the fine structure of the biological correlate of the gene expression pattern. availability and requirements the most recent versions of the redundancyminer program package and user's manual can be downloaded from http://discover.nci.nih.gov/rm/supplementarymaterials.html. additional file provides information for developers about the relationships of the rm and htgm files. redundancyminer was developed using perl and java. in order to execute redundancyminer, perl and java virtual machine need to be installed and accessible to the operating system. authors' contributions brz developed the project, and wrote the manuscript. hl devised and implemented the clustering algorithm, produced the java and perl code, and constructed the powerpoint user manual. abk and jnw were involved in initial discussions about potential approaches to address the redundancy issue. me, vnr, and rfb performed the clustering analysis of the retinal data sets. jdb and bpb generated retinal data. vll and wr curated and maintained the kinetochore data set. yp provided overall scientific guidance for all of the work that was performed. all authors read and approved the final manuscript. supplementary material additional file 1 parameters used in htgm analyses. table of parameters used in htgm analyses. click here for file additional file 2 perl modules. table of perl modules and their function. click here for file additional file 3 redundancyminer program package download. the code for running redundancyminer on your own computer. click here for file additional file 4 types of htgm gene-category association files used by redundancyminer. table of types and descriptions of htgm files used by redundancyminer. click here for file additional file 5 powerpoint user's manual. powerpoint version of the redundancyminer user's manual. click here for file additional file 6 pdf format of powerpoint user's manual..pdf version of the redundancyminer user's manual. click here for file additional file 7 simplified version of the htgm result directory that is exemplified in the user's manual. htgm result directory to be used in conjunction with the examples given in the redundancyminer user's manual. click here for file additional file 8 retinal development htgm download. compressed package of the results of running htgm on the retinal development genes list. click here for file additional file 9 kinetochore genes. table listing kinetochore genes. click here for file additional file 10 kinetochore genes htgm download. compressed package of the results of running htgm on the kinetochore genes list. click here for file additional file 11 original genes versus categories cim for an interesting retinal development time-series cluster..png image of original genes versus categories cim for an interesting retinal development time-series cluster. click here for file additional file 12 reduced cim of retinal development genes versus categories..png image of reduced cim of retinal development genes versus categories. click here for file additional file 13 meta cim of retinal development categories versus meta cim group..png image of meta cim of retinal development categories versus meta cim group. click here for file additional file 14 original kinetochore genes versus categories cim..png image of original kinetochore genes versus categories cim. click here for file additional file 15 reduced cim of kinetochore genes versus categories..png image of reduced cim of kinetochore genes versus categories. click here for file additional file 16 meta cim of kinetochore categories versus meta cim group..png image of meta cim of kinetochore categories versus meta cim group. click here for file additional file 17 reduced cim of kinetochore genes versus categories..png image of reduced cim of kinetochore genes versus categories. click here for file additional file 18 meta cim of kinetochore genes versus categories..png image of meta cim of kinetochore genes versus categories. click here for file additional file 19 information for developers. table of the relationship of rm and htgm files. click here for file acknowledgements this research was supported in part by the intramural research program of the nih, national cancer institute, center for cancer research. the work by jnw was supported in part by a generous gift from the chapman foundation. hf is supported by the nih grant r01lm009959a 
the main algorithm of redundancyminer, multiclust, performs a novel form of cluster analysis in which a go category might belong to several category clusters. tools such as gominer can leverage go to perform ontological analysis of microarray and proteomics studies, typically generating a list of significant functional categories. for illustration, we have applied it to the clarification of the results arising from two current studies: assessment of the gene expression profiles obtained by laser capture microdissection of serial cryosections of the retina at the site of final optic fissure closure in the mouse embryos at specific embryonic stages, and analysis of a conceptual data set obtained by examining a list of genes deemed to be "kinetochore" genes. each category cluster follows a "complete linkage" paradigm. the redundancy might typically inflate the report of significant categories by a factor of three-fold, create an illusion of an overly long list of significant categories, and obscure the relevant biological interpretation.
 the gene ontology consortium organizes genes into hierarchical categories based on biological process, molecular function and subcellular localization. tools such as gominer can leverage go to perform ontological analysis of microarray and proteomics studies, typically generating a list of significant functional categories. two or more of the categories are often redundant, in the sense that identical or nearly-identical sets of genes map to the categories. the redundancy might typically inflate the report of significant categories by a factor of three-fold, create an illusion of an overly long list of significant categories, and obscure the relevant biological interpretation.  we now introduce a new resource, redundancyminer, that de-replicates the redundant and nearly-redundant go categories that had been determined by first running gominer. the main algorithm of redundancyminer, multiclust, performs a novel form of cluster analysis in which a go category might belong to several category clusters. each category cluster follows a "complete linkage" paradigm. the metric is a similarity measure that captures the overlap in gene mapping between pairs of categories.  redundancyminer effectively eliminated redundancies from a set of go categories. for illustration, we have applied it to the clarification of the results arising from two current studies: assessment of the gene expression profiles obtained by laser capture microdissection of serial cryosections of the retina at the site of final optic fissure closure in the mouse embryos at specific embryonic stages, and analysis of a conceptual data set obtained by examining a list of genes deemed to be "kinetochore" genes. 