BACKGROUND
importance of housekeeping genes
housekeeping  genes are defined as genes constitutively expressed in all tissues to maintain essential cellular functions.
conversely, tissue specific  genes, are defined as genes only or mainly expressed in a specific tissue or organ, and hence responsible for specific functions and development  <cit> .
gene expression profiling is a key to characterizing normal and diseased biological states.
many disciplines need to discriminate between housekeeping and tissue specific genes.
in microbiology, housekeeping genes are known to play a role in enhancing virulence of pathogens and they are studied to find potential drug targets  <cit> , while slowly diverging housekeeping genes are used in evolutionary studies to discriminate subspecies  <cit> .
in medicine they are studied to discover if genetic diseases linked to housekeeping genes are more likely to affect multiple organs.
in biology and physiology housekeeping genes are the key to determine the set of basic functions necessary for cellular life or an organ function  <cit> .
additionally, many quantitative techniques used for diagnosis and research use housekeeping gene expression as a baseline to normalize numerical values and to detect differential expression.
housekeeping genes like glyceraldehyde-3-phosphate dehydrogenase , beta-actin, or beta-tubulin are used as standards in assay techniques like microarrays, rt-pcr, northern blotting  and western blotting .
direct assay of expression across tissues
until now, lists of housekeeping genes have been constructed by testing gene expression in different tissues, with the most recent attempts involving microarrays  <cit> .
unfortunately, microarray techniques suffer from certain limitations.
some are intrinsic to the technique, for example, the mrna extraction by hybridization of the polya tail on a polyt column causes a loss of mrna material that remains attached to the column, a detail particularly important for mrna expressed at extremely low levels.
another problem is the conversion from mrna to cdna where the reverse transcription process introduces a bias toward certain sequences.
other limitations might decrease over time, but are still relevant factors today.
cost, for example, is still an important limitation, and has a crucial impact on replicates.
another limit in commercial microarrays is that not all new genomes or gene sequences are immediately available.
in addition, the dna probes responsible for the specificity of hybridization with a unique gene are sometimes difficult to create.
for example, if the probe is too near to the end of the gene sequence, any splicing event will make the probe useless for recognizing different variants of the same gene.
kothapalli found that most probes were, unfortunately, chosen from the gene end in commercial platforms, and so less useful for distinguishing differentially expressed splicing versions  <cit> .
additionally, the sensitivity of the technique still limits the possibility of reproducing results: comparisons have found a maximum correlation of 70% between genes recognized as expressed by different commercial platforms like affymetrix ®genechips and amersham ™codelink  <cit> .
tan reports an even more modest correlation  <cit> .
other limitations are becoming evident over time, due to the constantly evolving history of genome sequencing: some published lists of housekeeping genes contain only the gene identifiers valid at the time the experiments were performed, but not the original sequence of the probe.
and in general, quoting brazma: "gene expression data are meaningful only in the context of a detailed description of the conditions under which they where generated"  <cit> .
to overcome these limitations we describe in this article an alternative system based on genes physical characteristics, that will help in identify housekeeping and tissue specific genes without having to test them in a wet lab against all known tissues.
physical characteristics of housekeeping genes
recent articles have demonstrated that tissue specific and housekeeping genes show distinctive physical characteristics of gene length and chromatin compactness.
to date, these features have been analysed individually, while in this work we will exploit their additive power in an integrated learning procedure.
gene length
eisenberg has shown that housekeeping genes tend to be significantly more compact and shorter than tissue specific genes  <cit> .
the average length for introns, exons, 3' utr  and 5' utr is shorter for housekeeping genes than for tissue specific genes.
moreover, housekeeping genes tend to have less exons.
the theory that underlies these data is that cells are thrifty: "the transcription process is both slow and costly; it takes  <dig> milliseconds and two atp molecules approximately to transcribe a nucleotide.
this might be expected to provide selective pressure to make genes as short as functionally possible.
the more copies of a gene required for the organism, the stronger this pressure should be"  <cit> .
additional evidence from castillo-davis showed that genes with a large number of expressed sequence tags  in public libraries have a significantly shorter average intron length than those with fewer ests   <cit> .
chromatin compactness
the dna in the nucleus of eukarya is packed in loops and folded over histones to form units called nucleosomes.
the dna structure in the region upstream of a gene is implicated in gene expression regulation, making it more or less easy for transcription factors to attach to or near the promoter and initiate transcription.
ganapathi analyzed the 5' and 3' flanking regions of housekeeping and tissue specific genes for various attributes of chromatin organization  <cit> .
the study showed that putative scaffold/matrix attachment regions  are more abundant upstream of tissue specific genes as compared to housekeeping genes.
s/mar attach themselves to the nuclear matrix and hence help the formation of chromatin loops.
genes less frequently expressed  appear to have less accessible and more compact dna in their promoter region, and so more s/mar sequences.
conversely, some repeats found to be more abundant upstream of housekeeping genes, like poly and n, destabilize the formation of nucleosomes and, leaving the dna less packaged, are implicated in maintaining constitutive gene expression  <cit> .
the naive bayes classifier
to identify an object, in this case a gene, as belonging to a particular class – e.g.
housekeeping vs. tissue specific – using computational techniques belongs to the broad field of classification.
for the classification to be successful, each class must show some distinct properties or characteristics.
none of the characteristics described in the above sections allows by itself a direct classification of a given gene as housekeeping or not.
this work, however, tests if multiple features can be combined to create a powerful classifier.
the algorithm of choice is the naive  bayes classifier that finds its origins in the bayesian theory of probability.
the main advantage of bayesian classifiers is that they are probabilistic models, robust to real data noise and missing values.
the naive bayes classifier assumes independence of the attributes used in classification but it has been tested on several artificial and real data sets, showing good performances even when strong attribute dependences are present.
in addition, the naive bayes classifier can outperform other powerful classifiers when the sample size is small.
using the words of domingos and pazzani: "in summary,  the bayesian classifier has much broader applicability than previously thought.
since it also has advantages in terms of simplicity, learning speed, classification speed, storage space and incrementality its use should perhaps be considered more often."
<cit> .
this work classifies housekeeping and tissue specific genes on the basis of physical characteristics only, without directly assaying expression in different tissues.
it exploits features already available in databases, like exon length and measures of chromatin compactness and combines them into a naive bayes classifier to obtain new lists of housekeeping and tissue specific genes in human, mouse and fruit fly.
RESULTS
classifier evaluation
attributes
a set of attributes was collected and the corresponding attribute values were fed to the classifier for each transcript of all human, mouse and fruit fly genes.
not all attributes, however, are fit for use in a classifier.
first, some attributes are clearly not independent and do not provide any additional advantage when evaluated together.
for example the number of exons and the number of introns for each transcript: the number of introns – or intervening sequences between exons – is by definition the number of exons minus one.
second, some attributes are not selective enough between the two classes of interest, like the presence of poly of  <dig> or more bp .
the attributes remaining after this analysis were, for each transcript:  <dig>  cdna length ,  <dig>  coding sequence  length ,  <dig>  number of exons,  <dig>  presence of s/mar in the 5' region,  <dig>  presence of s/mar in the 3' region,  <dig>  presence of poly  in the 5' region,  <dig>  presence of 2– <dig> in the 5' region,  <dig>  percent of go terms for the gene that match with the housekeeping go terms list,  <dig>  percent of go terms for the gene that match with the tissue specific go terms list.
short gene length for housekeeping genes
the work of eisenberg highlighted the compactness and short length of human housekeeping genes  <cit> .
we confirmed these results also for the mouse and fruit fly homologs of human housekeeping and tissue specific genes.
figure  <dig> shows the frequency distribution, normalized to one, of the different cdna lengths found in housekeeping , tissue specific  and the full gene set, for each of the three species.
the housekeeping distribution appears to be shifted to the left of the diagram, reflecting shorter transcripts, while the tissue specific distribution is more dispersed toward the right, reflecting longer exons and introns.
similar patterns of results were found for cds length and number of exons as summarized in table  <dig>
chromatin compactness upstream housekeeping genes
s/mar are expected to be less present upstream of human housekeeping genes  <cit> , as less packed chromatin eases gene expression.
this was confirmed in our analysis  also for mouse, while in fruit fly s/mar sequences seems to be more present upstream of housekeeping genes.
poly sequences, on the contrary, should be more likely present upstream of human housekeeping genes, as they keep the dna unpackaged and enhance gene expression.
this too was confirmed for mouse, while the regions upstream fruit fly genes seems to have almost no poly sequences.
a pattern similar to that of poly sequences is expected for the nucleosomes destabilizing sequence 2– <dig>  with increased presence upstream of housekeeping genes to enhance transcription and decreased presence upstream of tissue specific genes  <cit> .
this pattern was confirmed for human and mouse  while in fruit fly the opposite seems true.
this could be caused by a real biological difference in the structure of housekeeping genes in fruit fly compared to human, or it could be an artefact of the homology conversion from human to fruit fly.
in this sense, a fruit fly homologous gene might be similar in function to the human gene, but not share the same pattern of expression, and hence have different chromatin structure.
an important aspect of the classifier is that it is independent of the biological interpretation of data.
in theory, for the use in the classifier, it doesn't matter what the pattern of difference is, as long as it helps in discriminating between the two classes, but in practice, these new data would deserve further biological analysis, as the role of 2– <dig> sequences has been extensively studied in yeast and human only.
gene ontology term matching
the gene ontology  terms  <cit>  linked to each gene were compared to the go terms specific for the housekeeping or the tissue specific set of genes.
a go term was defined as being specific for housekeeping genes when the term appears exclusively in association with one or more housekeeping genes .
the analogous choice was made when generating a list of go terms specific for tissue specific genes.
table  <dig> lists the go terms that appears more frequently in each set.
a measure of similarity was generated comparing the go terms of each gene with the list of go terms specific for housekeeping  genes .
training and evaluation
for the classification of housekeeping genes, only genes classified as housekeeping in all three microarray sets  were accepted in the training set, and only tissue specific genes present in at least two of the tissue specific lists from table  <dig> were used .
a zero rule classifier that simply chooses the majority class  as classification for all instances was trained and used as a performance baseline .
for the actual classification two different naive bayes algorithms were tested, a classic version and the aode  version  <cit>  that should reduce the error due to non-independent attributes.
since the performance of two algorithms was very similar , from now on we will only comment on the classic naive bayes results .
after data filtering, each classifier was trained and cross-validated for 10-times with a 10-fold random sampling.
the ten resulting values for each performance parameter  were averaged to obtain the final figures, and receiver operating characteristic  curves, plotting tp rates vs. fp rates, were analyzed.
as expected, the naive bayes classifier shows a definite progression in performance when data discretisation is used, either supervised or un-supervised with frequency binning, as shown in figure  <dig> for human data.
in addition, the performance level is not particularly affected by the threshold of homology chosen.
to convert the training set from human to mouse  thresholds of identity of 40% or 50% have been tested with no significant difference in performance .
comparing performance across human, mouse and fruit fly
for all species, the classifier performance improves when comparing the zerorule classifier baseline with the naive bayes classifier .
in particular, the classification performance over housekeeping genes improves dramatically compared with the 0% precision, recall and f measure of the zerorule classifier .
the success rates for the three species are summarized in table  <dig>  in addition, the receiver operating characteristic  curves in figure  <dig> compare the maximum performance obtained by the classifiers on human, mouse and fruit fly transcripts.
roc curves represent the classification data in a ranked order of probability, showing how many true positives  one can obtain taking, for example, the highest 10% of the ranking list, and how many false positives one would also unknowingly collect in the meantime.
put simply, the closer the curve is to the upper left corner, the better the classification is, while the more the curve relaxes to the right and toward the centre of the diagram, the worse the performance .
the curves in figure  <dig> show a decrease in performance for mouse data and, in particular, for fruit fly data when compared to performance on human data.
the overall performance was examined further and it seemed unrelated to the identity thresholds, but very sensitive to the data consolidation used.
the sensitivity to data consolidation is further analysed in figure 4: this diagram shows the decrease in performance that appears in both mouse and fruit fly when all tissue specific genes are used to generate the training set instead of using only genes present in at least two different published sources.
in general, considering both algorithms  and both filters  the best success rate that the system could achieve for human is  <dig> % , for mouse is  <dig> %  and for fruit fly is  <dig> %  .
comparison with other classifiers
the naive bayes classifier performs better than the baseline on all performance indicators, and was also compared with other well known classifiers.
the naive bayes classifier is among the best classifiers and learning methods when the success rate is used as main indicator.
interestingly, two of the closest contending algorithms are also derived from the naive bayes algorithm   <cit> .
the naive bayes algorithm is also extremely fast compared to the others tested: there is no significant wait time for a 10-times 10-fold cross-evaluation of ≈  <dig> transcripts training set, and it takes only a couple of seconds to obtain the classification of a  <dig> instances test set .
genes and transcripts
in this work, we use transcripts as minimal genetic units for classification, instead of genes.
this decision is justified by the biological existence, especially for mammalians, of multiple transcripts for each gene, each with a potentially different tissue expression pattern.
in fact, in this study  <dig> human  genes having two or more different transcripts had their transcripts classified with different housekeeping probabilities.
and  <dig> human  genes had at least one transcript classified as housekeeping and at least another transcript classified as tissue specific.
the different classification of transcripts of the same gene reflects the ability of the classifier to identify different biological ways of regulating gene expression: by gene length or by chromatin compactness.
if a gene contains several transcripts with different patterns of expression, the evolutionary pressure on the chromatin compactness around the gene may be conflicting.
the preference for having open chromatin around a housekeeping gene may be some how offset by the pressure for having compact chromatin around a tissue specific transcript.
however, there will still be pressure on gene length to keep transcripts often expressed shorter.
similarly, in the classifier, the set of different transcripts for a gene will have all the values for the chromatin attributes in common, as the 3' and 5' regions are the same for all transcripts in a gene.
but the classifier can use the other attributes  to drive the final classification.
predicted housekeeping transcripts
in the evaluation phase the classifier was trained on nine tenths of the known data while the remaining tenth was withhold for calculating the classifier performance.
in the second phase each classifier was trained with all available known data for each species.
in the third phase each of the classifiers was run on all available transcript data for all genes  to obtain predictions .
the classifier trained on human data was applied to all  <dig> human transcripts , the mouse classifier was applied to all  <dig> mouse transcripts , and the drosophila classifier was applied to the  <dig> drosophila transcripts .
excluding the genes already known to be housekeeping or tissue specific, the three classifiers extracted new lists of housekeeping and tissue specific genes for each of the three species.
the probabilistic classifications uses "housekeeping" and "tissue specific" as the two ends of the spectrum considered.
the probability of being housekeeping and being tissue specific add up to one, for example: if the housekeeping probability is  <dig>  %, then the tissue specific probability is  <dig> %.
the actual classification decision will depend on the threshold used.
if we use 90% as minimum threshold, all genes with a housekeeping probability above 90%  will be considered housekeeping.
accordingly, all transcripts with tissue specific probability above 90%  will be considered tissue specific.
the number of transcripts with housekeeping probability above 90% and above 50%  can be found in table  <dig>  the lists of new housekeeping transcripts found in all three species show a high presence of proteins from housekeeping families, like ribosomal proteins: the related go terms appear  <dig> times in the human housekeeping list,  <dig> times only in the tissue specific predicted set.
the classifier also correctly classified as housekeeping mrnas commonly used as standardization controls like: beta-actin , beta-2-microglobulin , non-pou domain containing nuclear rna-binding protein , and the ribosomal proteins rps <dig>  rpl <dig>  rpl <dig> and rps <dig>
predicted tissue specific genes
the number of transcripts with predicted tissue specific probability above 90%  and tissue specific probability above 50%  are also shown in table  <dig>  the new predicted tissue specific genes have an extremely varied set of functions, rich in tissue specific structures like brain receptors, muscle fibre components, and also protein variants known to be involved in disease and tumorigenesis.
for example, in human,  <dig> transcripts have brain specific description .
some functions are almost completely absent in the housekeeping set, but present in the tissue specific set like:  <dig> synaptic transmission transcripts ,  <dig> spermatogenesis transcripts   <dig> olfactory receptors transcripts ,  <dig> cytokines ,  <dig> platelet transcripts ,  <dig> gaba transporters and receptors ,  <dig> dystrophy involved transcripts .
the tissue specific set is also particularly enriched in functions like signal transduction  or receptor activity .
many other tissue specific functions are represented, like the 5-aminolevulinate synthase erythroid-specific, or involved in disease, like the abnormal spindle-like microcephaly-associated protein.
other differences between the sets are less quantitatively evident, but not less interesting.
for example, among the predicted housekeeping transcripts we find  <dig> general and mitochondrial elongation factors.
in the tissue specific set too we find  <dig> elongation factors, but not mitochondrial ones, and  <dig> are testis specific factors, while  <dig> are negative elongation factors, involved in diseases that subvert the common housekeeping of cell growth, like breast cancer and wolf-hirschhorn syndrome, a multiple malformation syndrome characterized by mental and developmental defects.
patterns of expression across tissues
the pattern of expression across different tissues of the new housekeeping and tissue specific genes can be used to check and confirm the classifier predictions.
the unigene site offers text reports containing the number of est  found for each unigene cluster  in  <dig> basic tissues.
the number of est registered in the database is considered a measure of the level of gene expression in each particular tissue.
figure  <dig> shows the known and the predicted housekeeping genes, plotted against the number of tissues in which they are expressed.
most of the new predicted human housekeeping genes are expressed in more than  <dig> tissues out of  <dig>  as would be expected for potential housekeeping genes.
the area between the line representing predicted housekeeping genes  and the line representing the known transcripts  visually represents the number of new housekeeping transcripts extracted for human .
since the original lists of housekeeping genes were mainly extracted at a time when affymetrix microarrays contained only  <dig> human genes , it would be expected that the classifier would find a number of new housekeeping genes.
discussion
the three species investigated  were chosen to generate a certain evolutionary fan, and to test the range of applicability of the method.
all theories regarding gene length and chromatin compactness have been verified only in human , but not in fruit fly.
however, eukaryotic genes are known to share similar structures and patterns, which have been used in the past to automate gene discovery.
the approach used here is to perform computational experiments, without prior expectations regarding the patterns of mouse or fruit fly data.
the results obtained are clearly not random, and the classification performance is good.
therefore, these computational studies broadly confirm that the characteristics of human housekeeping genes can be identified in other species.
but the differences between species that we observe also suggest further investigation into characteristic features of such genes for species more distantly related to human, and into the method of determining homologs would indeed be worthwhile.
in particular, one of the main challenges for the training phase was the conversion of the housekeeping and tissue specific genes identifiers: up to 25% of the unigene gene identifiers published in past works on housekeeping genes were retired from the unigene database in the last four years.
10% of the unigene identifiers have been retired without having a new identifier assigned, and so part of the potential housekeeping training set was lost.
the identifiers conversion between the ncbi accession numbers  and the european embl identifiers caused a loss of around 15% of the genes.
in addition, the available tissue specific lists agreed on just  <dig> transcripts out of  <dig> human transcripts from  <cit> ,  <dig> from  <cit>  and  <dig> from  <cit> , .
however, to create a strong training set and to preserve high performance we still tried to merge the available list to obtain only the data on which different authors and different experimental techniques agreed.
another constraint was the ratio between housekeeping and tissue specific genes: from microarray estimates in homo sapiens housekeeping genes represent about 5– <dig> % of the total  <cit> , but there is no evidence that the human estimate applies also to the other species.
CONCLUSIONS
to-date, studies of housekeeping genes have typically concentrated on human genes only, and the housekeeping genes are normally taken from a small number of already published lists.
the labelling of genes with housekeeping or tissue specific status is not common, even in highly curated databases.
in this work, we propose an automated solution that is based on the integration of existing datasets.
as noted above, integration is not straightforward, but is achievable.
the main achievement of this work is to have proved that it is possible to discover if a gene is housekeeping using simple features of that gene sequence and its surroundings.
this is made possible by the integration of different attributes operated by the naive bayes engine, since the attributes already discovered in literature  were not powerful enough, taken alone, for deciding if a gene was housekeeping or not.
this opens up the possibility of automatically assigning the housekeeping/tissue specific status to all genes  for which we have a sequence.
our method proposes not only a housekeeping label, but a certainty value, that gives a measure of trust in the prediction.
this classification method is applicable to genes of any eukaryotic species, exploiting information that is already available in publicly accessible databases, and it can generate a functional description even for sequenced but otherwise unknown genes.
considering this strength of the method here evaluated, future work might include the analysis of less well known genomes.
at the same time, in the future the structure of the classifier might be enriched, for example, the gene ontology structure might be further exploited to compare also go terms that are in a parent or child relation with the go terms of each gene.
as the risk of overfitting is always present with attributes that are partially learnt from the training set, the go attributes could be further elaborated, for example: using housekeeping and tissue specific lists of go terms verified by expert curators, or by learning the go lists from other sources.
thanks to the flexible structure of the naive bayes classifier additional attributes can be easily added, either attributes already studied  or newly discovered ones.

 importance of housekeeping genes housekeeping genes are defined as genes constitutively expressed in all tissues to maintain essential cellular functions. conversely, tissue specific genes, are defined as genes only or mainly expressed in a specific tissue or organ, and hence responsible for specific functions and development. gene expression profiling is a key to characterizing normal and diseased biological states. many disciplines need to discriminate between housekeeping and tissue specific genes. in microbiology, housekeeping genes are known to play a role in enhancing virulence of pathogens and they are studied to find potential drug targets, while slowly diverging housekeeping genes are used in evolutionary studies to discriminate subspecies. in medicine they are studied to discover if genetic diseases linked to housekeeping genes are more likely to affect multiple organs. in biology and physiology housekeeping genes are the key to determine the set of basic functions necessary for cellular life or an organ function. additionally, many quantitative techniques used for diagnosis and research use housekeeping gene expression as a baseline to normalize numerical values and to detect differential expression. housekeeping genes like glyceraldehyde-3-phosphate dehydrogenase, beta-actin, or beta-tubulin are used as standards in assay techniques like microarrays, rt-pcr, northern blotting and western blotting. direct assay of expression across tissues until now, lists of housekeeping genes have been constructed by testing gene expression in different tissues, with the most recent attempts involving microarrays. unfortunately, microarray techniques suffer from certain limitations. some are intrinsic to the technique, for example, the mrna extraction by hybridization of the polya tail on a polyt column causes a loss of mrna material that remains attached to the column, a detail particularly important for mrna expressed at extremely low levels. another problem is the conversion from mrna to cdna where the reverse transcription process introduces a bias toward certain sequences. other limitations might decrease over time, but are still relevant factors today. cost, for example, is still an important limitation, and has a crucial impact on replicates. another limit in commercial microarrays is that not all new genomes or gene sequences are immediately available. in addition, the dna probes responsible for the specificity of hybridization with a unique gene are sometimes difficult to create. for example, if the probe is too near to the end of the gene sequence, any splicing event will make the probe useless for recognizing different variants of the same gene. kothapalli found that most probes were, unfortunately, chosen from the gene end in commercial platforms, and so less useful for distinguishing differentially expressed splicing versions. additionally, the sensitivity of the technique still limits the possibility of reproducing results: comparisons have found a maximum correlation of 70% between genes recognized as expressed by different commercial platforms like affymetrix ®genechips and amersham ™codelink. tan reports an even more modest correlation. other limitations are becoming evident over time, due to the constantly evolving history of genome sequencing: some published lists of housekeeping genes contain only the gene identifiers valid at the time the experiments were performed, but not the original sequence of the probe. and in general, quoting brazma: "gene expression data are meaningful only in the context of a detailed description of the conditions under which they where generated". to overcome these limitations we describe in this article an alternative system based on genes physical characteristics, that will help in identify housekeeping and tissue specific genes without having to test them in a wet lab against all known tissues. physical characteristics of housekeeping genes recent articles have demonstrated that tissue specific and housekeeping genes show distinctive physical characteristics of gene length and chromatin compactness. to date, these features have been analysed individually, while in this work we will exploit their additive power in an integrated learning procedure. gene length eisenberg has shown that housekeeping genes tend to be significantly more compact and shorter than tissue specific genes. the average length for introns, exons, 3' utr and 5' utr is shorter for housekeeping genes than for tissue specific genes. moreover, housekeeping genes tend to have less exons. the theory that underlies these data is that cells are thrifty: "the transcription process is both slow and costly; it takes milliseconds and two atp molecules approximately to transcribe a nucleotide. this might be expected to provide selective pressure to make genes as short as functionally possible. the more copies of a gene required for the organism, the stronger this pressure should be". additional evidence from castillo-davis showed that genes with a large number of expressed sequence tags in public libraries have a significantly shorter average intron length than those with fewer ests. chromatin compactness the dna in the nucleus of eukarya is packed in loops and folded over histones to form units called nucleosomes. the dna structure in the region upstream of a gene is implicated in gene expression regulation, making it more or less easy for transcription factors to attach to or near the promoter and initiate transcription. ganapathi analyzed the 5' and 3' flanking regions of housekeeping and tissue specific genes for various attributes of chromatin organization. the study showed that putative scaffold/matrix attachment regions are more abundant upstream of tissue specific genes as compared to housekeeping genes. s/mar attach themselves to the nuclear matrix and hence help the formation of chromatin loops. genes less frequently expressed appear to have less accessible and more compact dna in their promoter region, and so more s/mar sequences. conversely, some repeats found to be more abundant upstream of housekeeping genes, like poly and n, destabilize the formation of nucleosomes and, leaving the dna less packaged, are implicated in maintaining constitutive gene expression. the naive bayes classifier to identify an object, in this case a gene, as belonging to a particular class – e.g. housekeeping vs. tissue specific – using computational techniques belongs to the broad field of classification. for the classification to be successful, each class must show some distinct properties or characteristics. none of the characteristics described in the above sections allows by itself a direct classification of a given gene as housekeeping or not. this work, however, tests if multiple features can be combined to create a powerful classifier. the algorithm of choice is the naive bayes classifier that finds its origins in the bayesian theory of probability. the main advantage of bayesian classifiers is that they are probabilistic models, robust to real data noise and missing values. the naive bayes classifier assumes independence of the attributes used in classification but it has been tested on several artificial and real data sets, showing good performances even when strong attribute dependences are present. in addition, the naive bayes classifier can outperform other powerful classifiers when the sample size is small. using the words of domingos and pazzani: "in summary, the bayesian classifier has much broader applicability than previously thought. since it also has advantages in terms of simplicity, learning speed, classification speed, storage space and incrementality its use should perhaps be considered more often.". this work classifies housekeeping and tissue specific genes on the basis of physical characteristics only, without directly assaying expression in different tissues. it exploits features already available in databases, like exon length and measures of chromatin compactness and combines them into a naive bayes classifier to obtain new lists of housekeeping and tissue specific genes in human, mouse and fruit fly.  classifier evaluation attributes a set of attributes was collected and the corresponding attribute values were fed to the classifier for each transcript of all human, mouse and fruit fly genes. not all attributes, however, are fit for use in a classifier. first, some attributes are clearly not independent and do not provide any additional advantage when evaluated together. for example the number of exons and the number of introns for each transcript: the number of introns – or intervening sequences between exons – is by definition the number of exons minus one. second, some attributes are not selective enough between the two classes of interest, like the presence of poly of or more bp. the attributes remaining after this analysis were, for each transcript: cdna length, coding sequence length, number of exons, presence of s/mar in the 5' region, presence of s/mar in the 3' region, presence of poly in the 5' region, presence of 2– in the 5' region, percent of go terms for the gene that match with the housekeeping go terms list, percent of go terms for the gene that match with the tissue specific go terms list. short gene length for housekeeping genes the work of eisenberg highlighted the compactness and short length of human housekeeping genes. we confirmed these results also for the mouse and fruit fly homologs of human housekeeping and tissue specific genes. figure shows the frequency distribution, normalized to one, of the different cdna lengths found in housekeeping, tissue specific and the full gene set, for each of the three species. the housekeeping distribution appears to be shifted to the left of the diagram, reflecting shorter transcripts, while the tissue specific distribution is more dispersed toward the right, reflecting longer exons and introns. similar patterns of results were found for cds length and number of exons as summarized in table chromatin compactness upstream housekeeping genes s/mar are expected to be less present upstream of human housekeeping genes, as less packed chromatin eases gene expression. this was confirmed in our analysis also for mouse, while in fruit fly s/mar sequences seems to be more present upstream of housekeeping genes. poly sequences, on the contrary, should be more likely present upstream of human housekeeping genes, as they keep the dna unpackaged and enhance gene expression. this too was confirmed for mouse, while the regions upstream fruit fly genes seems to have almost no poly sequences. a pattern similar to that of poly sequences is expected for the nucleosomes destabilizing sequence 2– with increased presence upstream of housekeeping genes to enhance transcription and decreased presence upstream of tissue specific genes. this pattern was confirmed for human and mouse while in fruit fly the opposite seems true. this could be caused by a real biological difference in the structure of housekeeping genes in fruit fly compared to human, or it could be an artefact of the homology conversion from human to fruit fly. in this sense, a fruit fly homologous gene might be similar in function to the human gene, but not share the same pattern of expression, and hence have different chromatin structure. an important aspect of the classifier is that it is independent of the biological interpretation of data. in theory, for the use in the classifier, it doesn't matter what the pattern of difference is, as long as it helps in discriminating between the two classes, but in practice, these new data would deserve further biological analysis, as the role of 2– sequences has been extensively studied in yeast and human only. gene ontology term matching the gene ontology terms linked to each gene were compared to the go terms specific for the housekeeping or the tissue specific set of genes. a go term was defined as being specific for housekeeping genes when the term appears exclusively in association with one or more housekeeping genes. the analogous choice was made when generating a list of go terms specific for tissue specific genes. table lists the go terms that appears more frequently in each set. a measure of similarity was generated comparing the go terms of each gene with the list of go terms specific for housekeeping genes. training and evaluation for the classification of housekeeping genes, only genes classified as housekeeping in all three microarray sets were accepted in the training set, and only tissue specific genes present in at least two of the tissue specific lists from table were used. a zero rule classifier that simply chooses the majority class as classification for all instances was trained and used as a performance baseline. for the actual classification two different naive bayes algorithms were tested, a classic version and the aode version that should reduce the error due to non-independent attributes. since the performance of two algorithms was very similar, from now on we will only comment on the classic naive bayes results. after data filtering, each classifier was trained and cross-validated for 10-times with a 10-fold random sampling. the ten resulting values for each performance parameter were averaged to obtain the final figures, and receiver operating characteristic curves, plotting tp rates vs. fp rates, were analyzed. as expected, the naive bayes classifier shows a definite progression in performance when data discretisation is used, either supervised or un-supervised with frequency binning, as shown in figure for human data. in addition, the performance level is not particularly affected by the threshold of homology chosen. to convert the training set from human to mouse thresholds of identity of 40% or 50% have been tested with no significant difference in performance. comparing performance across human, mouse and fruit fly for all species, the classifier performance improves when comparing the zerorule classifier baseline with the naive bayes classifier. in particular, the classification performance over housekeeping genes improves dramatically compared with the 0% precision, recall and f measure of the zerorule classifier. the success rates for the three species are summarized in table in addition, the receiver operating characteristic curves in figure compare the maximum performance obtained by the classifiers on human, mouse and fruit fly transcripts. roc curves represent the classification data in a ranked order of probability, showing how many true positives one can obtain taking, for example, the highest 10% of the ranking list, and how many false positives one would also unknowingly collect in the meantime. put simply, the closer the curve is to the upper left corner, the better the classification is, while the more the curve relaxes to the right and toward the centre of the diagram, the worse the performance. the curves in figure show a decrease in performance for mouse data and, in particular, for fruit fly data when compared to performance on human data. the overall performance was examined further and it seemed unrelated to the identity thresholds, but very sensitive to the data consolidation used. the sensitivity to data consolidation is further analysed in figure 4: this diagram shows the decrease in performance that appears in both mouse and fruit fly when all tissue specific genes are used to generate the training set instead of using only genes present in at least two different published sources. in general, considering both algorithms and both filters the best success rate that the system could achieve for human is %, for mouse is % and for fruit fly is %. comparison with other classifiers the naive bayes classifier performs better than the baseline on all performance indicators, and was also compared with other well known classifiers. the naive bayes classifier is among the best classifiers and learning methods when the success rate is used as main indicator. interestingly, two of the closest contending algorithms are also derived from the naive bayes algorithm. the naive bayes algorithm is also extremely fast compared to the others tested: there is no significant wait time for a 10-times 10-fold cross-evaluation of ≈ transcripts training set, and it takes only a couple of seconds to obtain the classification of a instances test set. genes and transcripts in this work, we use transcripts as minimal genetic units for classification, instead of genes. this decision is justified by the biological existence, especially for mammalians, of multiple transcripts for each gene, each with a potentially different tissue expression pattern. in fact, in this study human genes having two or more different transcripts had their transcripts classified with different housekeeping probabilities. and human genes had at least one transcript classified as housekeeping and at least another transcript classified as tissue specific. the different classification of transcripts of the same gene reflects the ability of the classifier to identify different biological ways of regulating gene expression: by gene length or by chromatin compactness. if a gene contains several transcripts with different patterns of expression, the evolutionary pressure on the chromatin compactness around the gene may be conflicting. the preference for having open chromatin around a housekeeping gene may be some how offset by the pressure for having compact chromatin around a tissue specific transcript. however, there will still be pressure on gene length to keep transcripts often expressed shorter. similarly, in the classifier, the set of different transcripts for a gene will have all the values for the chromatin attributes in common, as the 3' and 5' regions are the same for all transcripts in a gene. but the classifier can use the other attributes to drive the final classification. predicted housekeeping transcripts in the evaluation phase the classifier was trained on nine tenths of the known data while the remaining tenth was withhold for calculating the classifier performance. in the second phase each classifier was trained with all available known data for each species. in the third phase each of the classifiers was run on all available transcript data for all genes to obtain predictions. the classifier trained on human data was applied to all human transcripts, the mouse classifier was applied to all mouse transcripts, and the drosophila classifier was applied to the drosophila transcripts. excluding the genes already known to be housekeeping or tissue specific, the three classifiers extracted new lists of housekeeping and tissue specific genes for each of the three species. the probabilistic classifications uses "housekeeping" and "tissue specific" as the two ends of the spectrum considered. the probability of being housekeeping and being tissue specific add up to one, for example: if the housekeeping probability is %, then the tissue specific probability is %. the actual classification decision will depend on the threshold used. if we use 90% as minimum threshold, all genes with a housekeeping probability above 90% will be considered housekeeping. accordingly, all transcripts with tissue specific probability above 90% will be considered tissue specific. the number of transcripts with housekeeping probability above 90% and above 50% can be found in table the lists of new housekeeping transcripts found in all three species show a high presence of proteins from housekeeping families, like ribosomal proteins: the related go terms appear times in the human housekeeping list, times only in the tissue specific predicted set. the classifier also correctly classified as housekeeping mrnas commonly used as standardization controls like: beta-actin, beta-2-microglobulin, non-pou domain containing nuclear rna-binding protein, and the ribosomal proteins rps rpl rpl and rps predicted tissue specific genes the number of transcripts with predicted tissue specific probability above 90% and tissue specific probability above 50% are also shown in table the new predicted tissue specific genes have an extremely varied set of functions, rich in tissue specific structures like brain receptors, muscle fibre components, and also protein variants known to be involved in disease and tumorigenesis. for example, in human, transcripts have brain specific description. some functions are almost completely absent in the housekeeping set, but present in the tissue specific set like: synaptic transmission transcripts, spermatogenesis transcripts olfactory receptors transcripts, cytokines, platelet transcripts, gaba transporters and receptors, dystrophy involved transcripts. the tissue specific set is also particularly enriched in functions like signal transduction or receptor activity. many other tissue specific functions are represented, like the 5-aminolevulinate synthase erythroid-specific, or involved in disease, like the abnormal spindle-like microcephaly-associated protein. other differences between the sets are less quantitatively evident, but not less interesting. for example, among the predicted housekeeping transcripts we find general and mitochondrial elongation factors. in the tissue specific set too we find elongation factors, but not mitochondrial ones, and are testis specific factors, while are negative elongation factors, involved in diseases that subvert the common housekeeping of cell growth, like breast cancer and wolf-hirschhorn syndrome, a multiple malformation syndrome characterized by mental and developmental defects. patterns of expression across tissues the pattern of expression across different tissues of the new housekeeping and tissue specific genes can be used to check and confirm the classifier predictions. the unigene site offers text reports containing the number of est found for each unigene cluster in basic tissues. the number of est registered in the database is considered a measure of the level of gene expression in each particular tissue. figure shows the known and the predicted housekeeping genes, plotted against the number of tissues in which they are expressed. most of the new predicted human housekeeping genes are expressed in more than tissues out of as would be expected for potential housekeeping genes. the area between the line representing predicted housekeeping genes and the line representing the known transcripts visually represents the number of new housekeeping transcripts extracted for human. since the original lists of housekeeping genes were mainly extracted at a time when affymetrix microarrays contained only human genes, it would be expected that the classifier would find a number of new housekeeping genes. discussion the three species investigated were chosen to generate a certain evolutionary fan, and to test the range of applicability of the method. all theories regarding gene length and chromatin compactness have been verified only in human, but not in fruit fly. however, eukaryotic genes are known to share similar structures and patterns, which have been used in the past to automate gene discovery. the approach used here is to perform computational experiments, without prior expectations regarding the patterns of mouse or fruit fly data. the results obtained are clearly not random, and the classification performance is good. therefore, these computational studies broadly confirm that the characteristics of human housekeeping genes can be identified in other species. but the differences between species that we observe also suggest further investigation into characteristic features of such genes for species more distantly related to human, and into the method of determining homologs would indeed be worthwhile. in particular, one of the main challenges for the training phase was the conversion of the housekeeping and tissue specific genes identifiers: up to 25% of the unigene gene identifiers published in past works on housekeeping genes were retired from the unigene database in the last four years. 10% of the unigene identifiers have been retired without having a new identifier assigned, and so part of the potential housekeeping training set was lost. the identifiers conversion between the ncbi accession numbers and the european embl identifiers caused a loss of around 15% of the genes. in addition, the available tissue specific lists agreed on just transcripts out of human transcripts from, from and from,. however, to create a strong training set and to preserve high performance we still tried to merge the available list to obtain only the data on which different authors and different experimental techniques agreed. another constraint was the ratio between housekeeping and tissue specific genes: from microarray estimates in homo sapiens housekeeping genes represent about 5– % of the total, but there is no evidence that the human estimate applies also to the other species.  to-date, studies of housekeeping genes have typically concentrated on human genes only, and the housekeeping genes are normally taken from a small number of already published lists. the labelling of genes with housekeeping or tissue specific status is not common, even in highly curated databases. in this work, we propose an automated solution that is based on the integration of existing datasets. as noted above, integration is not straightforward, but is achievable. the main achievement of this work is to have proved that it is possible to discover if a gene is housekeeping using simple features of that gene sequence and its surroundings. this is made possible by the integration of different attributes operated by the naive bayes engine, since the attributes already discovered in literature were not powerful enough, taken alone, for deciding if a gene was housekeeping or not. this opens up the possibility of automatically assigning the housekeeping/tissue specific status to all genes for which we have a sequence. our method proposes not only a housekeeping label, but a certainty value, that gives a measure of trust in the prediction. this classification method is applicable to genes of any eukaryotic species, exploiting information that is already available in publicly accessible databases, and it can generate a functional description even for sequenced but otherwise unknown genes. considering this strength of the method here evaluated, future work might include the analysis of less well known genomes. at the same time, in the future the structure of the classifier might be enriched, for example, the gene ontology structure might be further exploited to compare also go terms that are in a parent or child relation with the go terms of each gene. as the risk of overfitting is always present with attributes that are partially learnt from the training set, the go attributes could be further elaborated, for example: using housekeeping and tissue specific lists of go terms verified by expert curators, or by learning the go lists from other sources. thanks to the flexible structure of the naive bayes classifier additional attributes can be easily added, either attributes already studied or newly discovered ones. 
traditionally, housekeeping and tissue specific genes have been classified using direct assay of mrna presence across different tissues, but these experiments are costly and the results not easy to compare and reproduce. in this work, a naive bayes classifier based only on physical and functional characteristics of genes already available in databases, like exon length and measures of chromatin compactness, has achieved a 97% success rate in classification of human housekeeping genes. overall, the classifier shows promise, and in the future additional attributes might be included to improve its discriminating power. the newly obtained lists of housekeeping and tissue specific genes adhere to the expected functions and tissue expression patterns for the two classes.
 traditionally, housekeeping and tissue specific genes have been classified using direct assay of mrna presence across different tissues, but these experiments are costly and the results not easy to compare and reproduce.  in this work, a naive bayes classifier based only on physical and functional characteristics of genes already available in databases, like exon length and measures of chromatin compactness, has achieved a 97% success rate in classification of human housekeeping genes.  the newly obtained lists of housekeeping and tissue specific genes adhere to the expected functions and tissue expression patterns for the two classes. overall, the classifier shows promise, and in the future additional attributes might be included to improve its discriminating power. 