September 4, 2009

16:2

WSPC - Proceedings Trim Size: 9.75in x 6.5in

45-Lin1

COMPARATIVE ANALYSIS OF AEROBIC AND ANAEROBIC
PROKARYOTES TO IDENTIFY CORRELATION BETWEENOXYGEN REQUIREMENT AND GENE-GENE FUNCTIONALASSOCIATION PATTERNSYAMING LIN
linyaming@gatech.edu

HONGWEI WU
hongwei.wu@gatech.edu

School of Electrical and Computer Engineering, Georgia Institute of Technology
210 Technology Circle Savannah, Georgia, 31407, USA
Activities of prokaryotes are pivotal in shaping the environment, and are also
greatly inﬂuenced by the environment. With the substantial progress in genome andmetagenome sequencing and the about-to-be-standardized ecological context information, environment-centric comparative genomics will complement species-centric comparative genomics, illuminating how environments have shaped and maintained prokaryotic
diversities. In this paper we report our preliminary studies on the association analysis ofa particular duo of genomic and ecological traits of prokaryotes – gene-gene functional
association patterns vs. oxygen requirement conditions. We ﬁrst establish a stochastic
model to describe gene arrangements on chromosomes, based on which the functional
association between genes are quantiﬁed. The gene-gene functional association measuresare validated using biological process ontology and KEGG pathway annotations. Student’s t-tests are then performed on the aerobic and anaerobic organisms to identify
those gene pairs that exhibit diﬀerent functional association patterns in the two diﬀerent oxygen requirement conditions. As it is diﬃcult to design and conduct biologicalexperiments to validate those genome-environment association relationships that haveresulted from long-term accumulative genome-environment interactions, we ﬁnally conduct computational validations to determine whether the oxygen requirement conditionof an organism is predictable based on gene-gene functional association patterns. The
reported study demonstrates the existence and signiﬁcance of the association relationships between certain gene-gene functional association patterns and oxygen requirement
conditions of prokaryotes, as well as the eﬀectiveness of the adopted methodology forsuch association analysis.
Keywords: oxygen requirement conditions, gene-gene functional association, gene ontology similarity, KEGG pathway annotation

1. Introduction
There are countless ways in which prokaryotes inﬂuence our daily life. On the other
hand, environments have undoubtedly left footprints on prokaryotic morphological, physiological and functional diversities [16]. It is, therefore, very important tostudy genomes in ecological contexts, and such importance has been recognized by
the community. This has led to substantial progresses in multiple enabling ﬁelds.
Environment Ontology (EnvO) and Habitat-Lite [5] have been proposed to stan-September 4, 2009

2

16:2

WSPC - Proceedings Trim Size: 9.75in x 6.5in

45-LinY. Lin & H. Wu

dardize descriptions of the environment, and to be incorporated into the standard
descriptions of genomes [3]. The reduced cost of DNA sequencing and world-wide
sequencing eﬀorts have made available sequences of ∼1,000 complete and ∼2,000
in-progress prokaryotic genomes [12]. With the wealth of genomic/metagenomic sequences and about-to-be-standardized ecological context information, environmentcentric comparative genomics has the potential to complement species-centric comparative genomics in illuminating how environments have shaped and maintainedprokaryotic diversities.
Bohlin et al. analyzed the genome composition of host-associated versus freeliving prokaryotes, and demonstrated that the oligonucleotide usage in non-coding
regions varied more for the former than the latter group of organisms [1]. Paul etal. [13] studied the genomic and proteomic features of halophilic and non-halophilicorganisms. They discovered distinctive molecular-level signatures in halophiles thatare independent of their GC-content or phylogenetic origins. These signatures include, for example, (i) over- and under-representations of certain amino acids, (ii)diﬀerent propensities for the helix and coil structures, and (iii) dinucleotide abundance and synonymous codon usage preference patterns that are not species-speciﬁc
but salt adaptation-speciﬁc. It was also suggested that the amount and source ofhorizontal gene transfer is linked to an organism’s lifestyle. For instance, bacterial
hyperthermophiles seem to have exchanged genes with archaea to a greater extent than other bacteria, whereas transfer of certain classes of eukaryotic genes ismost common in parasitic and symbiotic bacteria [10]. Evidence has shown that the
genome size and gene content in bacteria are associated with their lifestyles. For
example, species with larger genome size are more metabolically versatile, able toexploit a larger number of ecological niches and exhibit larger intra-species diﬀerences; and, host-associated bacteria typically have a smaller genome size and fewer
genes [8, 9]. Comparative analysis on host-associated and free-living bacteria also
indicated that host-associated bacteria in general have fewer rRNA genes, more
split rRNA operons and fewer transcriptional regulators. And, between mutualists
and parasites, the former group has signiﬁcantly more genes that enable nutrient
provisioning, whereas the latter group has more genes of secretion systems [11].
Suen et al. used the distribution of protein domains in various Pfam families toclassify prokaryotes, and compared this classiﬁcation result against the 16S rRNAbased phylogenetic map. The comparison revealed that the prokaryotic organisms
occupying the same ecological niche tend to possess a similar genetic repertoire dueto the evolutionary pressure exerted by the ecological niche [14].
As described above, the association between prokaryotic genomic and ecologicaltraits lies in multiple aspects. The genomic traits can include basic genomic and proteomic features (e.g., genome size, GC-content, preference for various synonymouscodons, and various protein structures), as well as features indicative of evolutionary
traces (e.g., horizontal gene transfer), functional potentialities (e.g., distribution ofgenes in various functional categories), and regulation eﬃciency (e.g., operon structures). And, the ecological traits can include habitat, temperature, pH, salinity,

September 4, 2009

16:2

WSPC - Proceedings Trim Size: 9.75in x 6.5in

45-LinCorrelation between Oxygen Requirement and Gene-Gene Association3

pressure, light intensity, oxygen, nutrient sources, etc. We here focus on a particular duo of genomic and ecological traits – gene-gene functional association patterns
vs. oxygen requirement conditions, to determine whether there exist statistically aswell as biologically signiﬁcant association relationships between these two traits. We
ﬁrst establish a mathematical model to quantify gene-gene functional association,and validate this model using biological process ontology [15] and KEGG pathway annotations [7] (Section 3). We then perform student’s t-tests [6] to identify
those gene pairs that exhibit diﬀerent functional association patterns for aerobic
and anaerobic organisms (Section 4). Finally, to further validate the signiﬁcance of
the identiﬁed association relationships, we examine whether and to what extent theoxygen requirement property of an organism can be predicted based on its genegene functional association properties (Section 5). Conclusions are drawn in Section
6.

2. Aerobic and Anaerobic Prokaryotes
As of March 2009, the NCBI Microbial Genome Project Database [12] contains 841
complete prokaryotic genomes, including 260 aerobes and 147 anaerobes. By aerobic
we mean that the organism can grow in the presence of oxygen and probably uses
oxygen as an electron acceptor; and, by anaerobic we mean that the organism grows
in the absence of oxygen and utilizes alternative electron acceptors.
The ideal strategy to investigate the association between genomes and a particular ecological factor (e.g., oxygen requirement) is to select those organisms whose
diversities in other ecological aspects (e.g., salinity, habitat, and temperature) arecomparable for the diﬀerent ecological conditions being focused on (e.g., aerobic andanaerobic conditions). However, as revealed by Table 1 in supplementary materials,
the distributions of the aerobic and anaerobic organisms in various salinity, habitat
and temperature conditions are slightly diﬀerent. If we selected the aerobic andanaerobic prokaryotes with their other ecological conditions being identical (e.g.,
non-halophilic, host-associated and mesophilic temperature), we would end up witha much smaller number of organisms, which will hinder us from drawing statistically signiﬁcant conclusions. Therefore, we have decided to use all these aerobic andanaerobic prokaryotes for the comparative and association analysis.
In terms of the phylogenetic diversity, as revealed by Table 2 in supplementarymaterials, the majority (∼80%) of the aerobic prokaryotes belong to Proteobacteria, Actinobacteria and Fimicutes with Proteobacteria being the dominant phylum; whereas the majority (∼70%) of the anaerobic prokaryotes belong to Firmicutes, Proteobacteria and Euryarchaeota with these three phyla being approximately
equally populated. To investigate the association between particular genomic features and ecolgocial contexts, we should ideally exclude the impact of factors otherthan ecological contexts (such as phylogenetic origins) on the genomic features. This
could be achieved by focusing on strains belonging to the same taxonomic lineage
but with diﬀerent ecological contexts, such as strains in the Geobacter genus that

September 4, 2009

4

16:2

WSPC - Proceedings Trim Size: 9.75in x 6.5in

45-LinY. Lin & H. Wu

have diﬀerent oxygen requirements and/or habitat types. However, for comparative genomics that involves a wide range of genomes, it is diﬃcult to distinguishwhether phylogenetic origins and ecological contexts are in the same or diﬀerent
roles in shaping the genomic features. Therefore, we have decided to consider all
taxonomic lineages together for the environment-centric comparative and association analysis.
The number of genes in each genomes ranges from 536 to 9,703, and on average∼42.8% of the genes are annotated with KEGG orthologous groups [7]. We here
focus on these KEGG orthology-annotated genes, and consider genes with the same
KEGG orthology annotations as the “same” (orthologous). There are totally 5,436
diﬀerent KEGG orthologous groups, which lead to over 14 million gene pairs to beinvestigated.
3. Quantiﬁcation of Gene-Gene Functional Association
For prokaryotic organisms, the arrangement of genes on chromosomes aﬀects how
eﬃciently genes are transcribed, and consequently reﬂects how diﬀerent parts of thecellular machinery are coordinated in response to environmental changes. The information regarding whether genes are adjacent or how distantly genes are separated
has been demonstrated to be eﬀective for operon prediction [2], functional module
prediction [17], etc. Here we also use the same information to described gene-gene
functional association.
3.1. Stochastic Model for Gene Arrangement
The hypothesis of this stochastic model for gene arrangement is that there exists
no functional association between two genes so that one gene’s presence or positionon the chromosome is independent of that of the other gene. Given any two genes
gi and gj , the evidence in each genome to support this hypothesis can be described
as:
[
]
M
∑
Nm + (2Nm − 1)dij − d2ij
L (gi , gj ) = I(gi , gj , |gi − gj | ≤ dij ) pi pj
N2
m=1
[
(
)2 )]
M (
∑
(1)
Nm
+ I(gi , gj , N A) pi pj 1 −N
m=1+ I(gi , ḡj )pi (1 − pj ) + I(ḡi , gj )(1 − pi )pj + I(ḡi , ḡj )(1 − pi )(1 − pj )where the ﬁve terms on the right hand side account for the scenario that (i) bothgi and gj belong to the same directon (a directon is a continuous stretch of genes
transcribed along the same direction), (ii) gi and gj are present in the genome
but do not belong to the same directon, (iii) gi is present in the genome but gj
is not, (iv) gi is not but gj is present in the genome, and (v) neither gi nor gj ispresent in the genome, respectively. pi denotes the probability of gi being present,
which is estimated as the ratio of the number of organisms containing gi to theSeptember 4, 2009

16:2

WSPC - Proceedings Trim Size: 9.75in x 6.5in

45-LinCorrelation between Oxygen Requirement and Gene-Gene Association5

total number of organisms. dij denotes the number of genes present between gi andgj . N is the total number of genes. All these genes are grouped into M directons
according to their position on the chromosome and transcription direction, with
Nm denoting the number of genes in the m-th directon.And, I() is the indicatorfunction. The so-calculated L (gi , gj ) reﬂects the level of validity of the hypothesis
associated with the stochastic model. The smaller L (gi , gj ) is, the more strongly
is the alternative hypothesis that the two genes are functionally associated being
supported. We therefore use A(gi , gj ) ≡ − log L (gi , gj ) to quantify the functional
association between gi and gj .
3.2. Validation of Gene-Gene Functional Association Measures
We here examine whether the model in Eq. (1) can faithfully capture the functional
association between genes, using biological process ontology and KEGG pathway
annotations.
3.2.1. Validation of the A (gi , gj ) Measures based on Biological Process
Ontology Annotations
The Gene Ontology(GO) describes properties of gene products from three independent perspectives – cellular component, molecular function, and biological process.
In particular, the biological process ontology describes to what biological objectives
gene products contribute and in what series of biological events gene products are
involved. The GO is structured as a directed acyclic graph, wherein (i) each term
is a child of one or more terms, (ii) child terms are instances or components of theparent terms, and (iii) child terms can provide more speciﬁc descriptions than theparent terms [15]. Genes with the same biological process GO annotations can beconsidered as functionally associated to a certain extent. Therefore, our validation
is based on biological process GO annotations.
For each biological process GO term, we deﬁne its depth as the number of terms
in the longest path from it to the root term (GO:0008150, biological process). Fora pair of biological process GO terms, go1 and go2 , we deﬁne their similarity as the
maximum depth of all their common ancestor terms, i.e.,
S GO (go1 , go2 ) = max {depth(go), go ∈ C1 ∩ C2 } ,(2)where Ci denotes the ancestor terms of goi (i = 1, 2), and C1 ∩ C2 denotes thecommon ancestors of go1 and go2 . And, for a pair of genes, g1 and g2 , among all thepairs formed by their biological process GO terms, we take the maximum similarity
as the GO similarity of these two genes, i.e.,{}
S GO (g1 , g2 ) = max S GO (go1 , go2 ), go1 ∈ S1 , go2 ∈ S2
(3)
where Si denotes the biological process GO terms applicable to gi (i = 1, 2).
The above deﬁned GO similarities have been used to derive information forpredicting protein-protein interaction [19] and for validating the functional association measures derived from other resources [17]. We here use them to validate

September 4, 2009

6

16:2

WSPC - Proceedings Trim Size: 9.75in x 6.5in

45-LinY. Lin & H. Wu

the A (gi , gj ) measures. Speciﬁcally, we will verify whether gene pairs that are
indicated as strongly/moderately/weakly functionally associated by the A (gi , gj )measure are also indicated so by the S GO (gi , gj ) measure. We ﬁrst calculate theaverage of the A (gi , gj ) measure across all organisms for each gene pair. Thenbased on the average A (gi , gj ) measures, we form three groups, consisting ofstrongly, moderately, and weakly functionally associated gene pairs, respectively. Bystrongly/moderately/weakly, we mean the 93,118 gene pairs whose average A (gi , gj )measures are among the top/middle/bottom one percent. We then compare the distributions of the S GO (gi , gj ) measure for these three groups of gene pairs, as shownin Fig. 1.

0.35

Strongly AssociatedModerately AssociatedWeakly Associated

Percentage of gene pairs

0.3
0.25
0.2
0.15
0.1
0.05
0

0

1

2

3

4

5 6 7 8GO similarity

9

10 11 12 13

Fig. 1. Distributions of S GO (gi , gj ) for gene pairs that are considered as strongly (cyan), moderately (magenta) and weakly (yellow) functionally associated based on the A (gi , gj ) measures. The
horizontal axis corresponds to the S GO (gi , gj ) measure, ranging from 0 to 13. The bars correspondto the percentages of gene pairs whose S GO (gi , gj ) measures fall within particular ranges.

Kolmogorov-Smirnov tests [6] for pairwise comparisons between these three distributions have indicated that the groups of the S GO (gi , gj ) measure are diﬀerent(with p-value ≤ 1e − 103) for strongly-, moderately-, and weakly- associated genepairs. As shown in Fig. 1, gene pairs with stronger functional association are more
likely than the gene pairs with weaker functional association to be associated withlarger S GO (gi , gj ) measures. Therefore, the A (gi , gj ) and S GO (gi , gj ) measures are
positively correlated; and, the A (gi , gj ) measure is as qualiﬁed as the S GO (gi , gj )measure to quantify the functional association between genes.
3.2.2. Validation of the A (gi , gj ) Measures based on KEGG Pathway
Annotations
The KEGG Pathway database is a collection of manually drawn pathway maps that
represent the knowledge about the molecular interactions and reaction networks [7].

September 4, 2009

16:2

WSPC - Proceedings Trim Size: 9.75in x 6.5in

45-LinCorrelation between Oxygen Requirement and Gene-Gene Association

7

Because genes involved in the same pathway can be considered as functionally associated to a certain extent, we here validate the A (gi , gj ) measures based on the
KEGG Pathway annotations. Speciﬁcally, we will examine whether those gene pairs
with diﬀerent levels of the A (gi , gj ) measure are involved in the same pathway with
diﬀerent levels of likelihood.
Given a group of gene pairs, the likelihood that the two genes of a randomly
drawn pair are involved in the same pathway can be estimated as the ratio of thenumber of gene pairs being involved in the same pathway to the total number ofgene pairs in the group. For the three groups, which contains the strongly, moderately and weakly functionally associated gene pairs, respectively, the ratios are
3.897%, 0.772%, and 0.607%. That is, those gene pairs that are indicated as strongly
functionally associated by the A (gi , gj ) measure are (5∼6 times) more likely to be
involved in the same pathway than those indicated as moderately/weakly associated. Therefore, based on the KEGG pathway annotations, the A (gi , gj ) measures
can capture the functional association between genes.
4. Identiﬁcation of Gene Pairs with Diﬀerent Functional
Association Patterns under the Two Diﬀerent Oxygen
Requirement Conditions
The goal of our study is to identify those gene pairs whose functional association
patterns are statistically as well as biologically linked with the oxygen requirement
conditions of prokaryotes. Each pair of genes are associated with two collectionsof A (gi , gj ) measures that corresponds to the 260 aerobic and 147 anaerobic organisms, respectively. By conducting an unpaired two-sample student’s t-test [6] on
the two collections (See supplementary materials for details of student’s t-test), we
can determine to what extent (measured by the p-value derived from the test) the
functional association between gi and gj exhibit diﬀerent distribution proﬁles forthe two diﬀerent oxygen requirement conditions.
4.1. Student’s t-Test Results
Based on the p-values derived from the t-tests (See supplementary Fig. 1 for p-value
distributions), we have formed two gene pair groups. The ﬁrst group consists of
93,118 gene pairs whose p-values range from 0.9576 to 1 and are among the largest
one percent of all the p-values. The second group consists of 93,118 gene pairs
whose p-values range from 0 to 1e − 18 and are among the smallest one percent of
all the p-values. The ﬁrst group can be interpreted as to contain those gene pairs
whose functional association are invariant to the oxygen requirement condition; andthe second group contains those gene pairs whose functional association measures
exhibit diﬀerent distribution patterns for the two diﬀerent oxygen requirement conditions. Fig. 2 shows the average A (gi , gj ) measure across all aerobic organisms (xaxis) vs. the average A (gi , gj ) measure across all anaerobic organisms (y axis) for
these two group of gene pairs. Note that the ﬁrst group(with large p-values) areSeptember 4, 2009

8

16:2

WSPC - Proceedings Trim Size: 9.75in x 6.5in

45-LinY. Lin & H. Wu

mainly distributed along the y = x line, which is consistent with our interpretationthat gene pairs with large p-values have their functional association relationships
invariant to the oxygen requirement condition. Also note that the second group ofgene pairs (with small p-values) are generally oﬀ the y = x line, with 50,293 pairs
above and 42,879 pairs below the line. Those gene pairs above the y = x line canbe interpreted as to be more strongly functionally associated in the anaerobic condition. Whereas, those gene pairs below the y = x line can be interpreted as to be
more strongly functionally associated in the aerobic condition.

80
Ratio of pathway density

Mean of anaerobic measures5
4
3

Gene pairs with large p values
Gene pairs with small p values

2
1
0
0

2
4
6
Mean of aerobic measures

8

Fig. 2. The average A (gi , gj ) measure acrossaerobic organisms (x-axis) vs. the average
A (gi , gj ) measure across anaerobic organisms(y-axis).

60

40

20

0
0

0.5

1
Threshold

1.5

2

Fig. 3. Likelihood ratio of being involved in
the same KEGG pathway as a function of thethreshold value. The threshold distinguishes
those strongly associated gene pairs in someoxygen requirement condition from the othergene pairs.

4.2. Biological Implications of the Gene Pairs with Large/Small
p-Values
Within the group of gene pairs whose functional association relationships are invariant to the oxygen requirement condition (the ﬁrst group aforementioned), weare more interested in those that are always strongly associated in both aerobic andanaerobic conditions. Similarly, within the group of gene pairs with stronger functional association relationships in one of the oxygen requirement conditions (thesecond group aforementioned), we are more interested in those that are strongly
associated in either aerobic or anaerobic condition. This is because these strongly
associated gene pairs, whether uniformly or conditionally, may reﬂect which part(s)of the cellular machinery are invariantly or conditionally “wired” with respect todiﬀerent oxygen requirement conditions.
To distinguish those gene pairs that are strongly associated in either aerobic
or anaerobic or both conditions, we have utilized the following approach involving
KEGG pathway annotations. Assume t is a threshold value, and those gene pairs

September 4, 2009

16:2

WSPC - Proceedings Trim Size: 9.75in x 6.5in

45-LinCorrelation between Oxygen Requirement and Gene-Gene Association

9

whose average A (gi , gj ) measure across aerobic organisms, or average A (gi , gj ) measure across anaerobic organisms, or both averages is greater than or equal to t areconsidered as strongly associated in some oxygen requirement condition. Intuitively,
the strongly associated gene pairs are more likely than the other pairs to be involvedin the same pathway; hence, we have compared the likelihood of strongly associatedgene pairs being involved in the same pathway against the likelihood of the othergene pairs being involved in the same pathway. Fig. 3 shows this likelihood ratio
as a function of t. Note that this likelihood ratio increases abruptly when t is in
the range of [1.35, 1.45]. We have therefore selected t = 1.45 to screen out thosegene pairs that are strongly associated in either aerobic or anaerobic or both oxygen
requirement conditions.
By applying this threshold value, we have identiﬁed 99 gene pairs with strong
association in the aerobic condition, 28 gene pairs with strong functional association in the anaerobic condition, and 51 gene pairs with strong association inboth aerobic and anaerobic associations. Complete lists are provided in the supplementary material. It is expected that genes involved in energy metabolism(e.g., pyruvate/oxoglutarate oxidoreductases, oxidative phosphorylation, nitrogenmetabolism) are arranged and functionally associated in diﬀerent ways in diﬀerent
oxygen requirement conditions. It is also expected that genes involved in the genetic
information processing (e.g., transcription and translation machinery) are conservedfor organisms of various ecological contexts and genes related to cell motility (e.g.,
ﬂagellar and motor genes) are subject to impacts of other environmental factors
and are therefore invariant to oxygen requirement conditions. However, it is interesting to observe that genes relevant to virulence (e.g., urease, secretion system)
also exhibit diﬀerent functional association patterns for diﬀerent oxygen requirement conditions.

5. Prediction of Oxygen Requirement Conditions Based on certain
Gene-Gene Functional Association Patterns
The signiﬁcance of the association between the gene-gene functional association
patterns and the oxygen requirement condition can be reﬂected statistically by the
p-values obtained through the student’s t-tests. However, because the association
between genomic and ecological traits are the result of long-term accumulative interactions between prokaryotes and the environment, it is diﬃcult to design wet-lab
experiments that can generate relatively long-term observations for further validations. We therefore focus on computational validations, and examine whether and towhat extent the ecological trait (e.g., oxygen requirement condition) of an organism
can be predicted based on the genomic traits (e.g., gene-gene functional association
patterns). The rationale for this computational validation approach lies in that themore predictable the ecological traits are based on the genomic traits, the more signiﬁcantly the ecological and genomic traits are associated. The procedure for thispredication-based computational validation is as follows.

September 4, 2009

10

16:2

WSPC - Proceedings Trim Size: 9.75in x 6.5in

45-LinY. Lin & H. Wu

First, all of the 407 prokaryotic organisms, either aerobic or anaerobic, are randomly partitioned into two sets, where the set consisting of 333 (∼80%) organisms
is used for training, and the other set consisting of 74 (∼20%) organisms is used
for testing. Secondly, using the training set, we estimate for each gene the probability of being present in a genome (pi in Eq. (1)), quantify for each gene pair thefunctional association, and conduct the student’s t-test to identify gene pairs whosefunctional association relationships are either invariant or stronger in one of theoxygen requirement conditions. We are particularly interested in those gene pairs
whose functional association measures follow diﬀerent distribution proﬁles for different oxygen requirement conditions, and are strong in either aerobic or anaerobic
conditions, since the functional association measures of these gene pairs will serveas the features for the predictions. We use t = 1.45 (see Section 4.2) to screen out
those gene pairs whose average functional association measure across all training
aerobic (or anaerobic) organisms is greater than or equal to t = 1.45 and use themas the genomic features of the aerobic (or anaerobic) condition. And ﬁnally, the performance of predicting the ecological trait based on genomic traits will be evaluatedusing organisms in the testing set. For each testing organism, two genomic feature
vectors will be generated that correspond to the aerobic and anaerobic conditions,
respectively. The aerobic feature vector consists of the functional association measures of those signature gene pairs for the aerobic condition, and is compared withthe genomic features of the aerobic condition to determine the Euclidian distance
between the testing organism and training aerobic organisms. Similarly, we candetermine the Euclidian distance between the testing organism and training anaerobic organisms. The oxygen requirement trait of the testing organisms is predicted
as aerobic (or anaerobic) if its distance to the aerobic (or anaerobic) condition issmaller.
The above procedure is repeated for 10 times, so that the eﬀectiveness of theprediction can be evaluated using diﬀerent testing sets. The prediction accuracy
rates for these 10 repeats are summarized in Table 1. Observe that the prediction
accuracy for all the 10 repeats of the random-partitioning-training-and-testing procedure is higher than or equal to 80%, and can even reach ∼90% or higher forsome repeats. Considering that a random guess of an organism’s oxygen requirement condition can only yield a 65% accuracy at most, the prediction results basedon the organism’s gene-gene functional association patterns, which can reach an
80% or even higher accuracy rate, indicate that it is feasible to predict the ecological trait based on the genomic trait. Consequently, the association between certain
gene-gene functional association patterns and the oxygen requirement condition isfar from being random or trivial; rather, such association reﬂects the interactions
between prokaryotic genomes and the environment.

September 4, 2009

16:2

WSPC - Proceedings Trim Size: 9.75in x 6.5in

45-LinCorrelation between Oxygen Requirement and Gene-Gene Association

11

Table 1. Accuracy rate of predicting the oxygen requirement condition of an prokaryotic organism based on its gene-gene functional
association patterns, obtained for 10 repeats of the random-partitioning-training-and-testing procedure.
Experiment
NumberExperiment 1
Experiment 3
Experiment 5
Experiment 7
Experiment 9

Prediction
Accuracy
91.89%
87.84%
87.84%
90.54%
79.73%

Experiment
NumberExperiment 2
Experiment 4
Experiment 6
Experiment 8
Experiment 10

Prediction
Accuracy
81.08%
85.13%
86.49%
86.49%
85.13%

6. Conclusion
In this paper, we have reported our preliminary investigations on the correlation between gene-gene functional association patterns and oxygen requirement conditionsof prokaryotes. We have ﬁrst established a stochastic model to quantify functional
association between genes. The gene-gene functional association measures have thenbeen validated using biological process GO and KEGG pathway annotations. Suchvalidations have revealed that gene pairs indicated as strongly associated by the proposed measure are also more likely to be associated with high GO similarities and be
involved in the same pathway, which means that the stochastic model-based quantiﬁcation can well capture the functional association between genes. We have thenperformed the student’s t-tests on the gene-gene functional association measures of
the aerobic and anaerobic organisms, and have then identiﬁed those gene pairs thatexhibit diﬀerent functional association patterns under diﬀerent oxygen requirement
conditions. We then have conducted computational validations to examine whether
the oxygen requirement trait of an organism can be predicted based on the gene-gene
functional association patterns. The 10 repeats of the random-partitioning-trainingand-testing experiment have shown that an 80% or even higher (∼90%) accuracy
rate can be achieved for such predictions. Compared to the maximum 65% accuracy rate that can be achieved by random guessing, our computational validation
results may indicate the existence and signiﬁcance of the association between certain gene-gene functional association patterns and oxygen requirement conditionsof prokaryotes, as well as the eﬀectiveness of the methodology we have adopted in
exploring the genome-environment association relationships.
Though our preliminary studies have rendered very promising results, there areseveral questions yet to be answered in our future studies. First, how well can theassociation relationships between certain gene-gene functional association patterns
and oxygen requirement conditions that have been identiﬁed through the reported
preliminary study be generalized to other prokaryotic genomes? Our preliminary
studies have been based on the complete prokaryotic genomes, which only accountfor a tiny percentage (< 1%) of the entire microbial world. We will take advantageof the in-progress prokaryotic genomes and metagenomes in our future study togeneralize our comparative and association analysis. Particularly, we will predict

September 4, 2009

12

16:2

WSPC - Proceedings Trim Size: 9.75in x 6.5in

45-LinY. Lin & H. Wu

the oxygen requirement traits of the in-progress genomes and metagenomes using the predictor model built on the complete genomes to determine how accurate
the prediction can be and consequently how well the association relationships canbe generalized. Secondly, how well can the methodology adopted in the reported
preliminary study, including quantiﬁcation of the gene-gene functional association,
statistical test, and predication-based computational validations, be generalized toother environmental factors? We will mainly focus on the phenotypic and ecologicaltraits that are speciﬁed in the NCBI Microbial Genome Project database, including motility, salinity, habitat, temperature, and pathogenicity. We will investigate
whether certain gene-gene functional association patterns are statistically and biologically associated with these phenotypic and ecological traits of prokaryotes.
Finally, is it possible to decouple the impact of phylogenetic diversities and theimpact of environmental diversities on the genomic features of prokaryotes? As wehave observed from Table 2 in supplementary materials, the aerobic prokaryotes aremainly distributed in the Proteobacteria phylum, wherease the anaerobic prokaryotes are mainly distributed in the Firmicutes, Proteobacteria and Euryarchaeota
phyla. We may argue whether the diﬀerence in the phylogenetic distributions also
contributes to the diﬀerence in the gene-gene functional association patterns between the aerobic and anaerobic organisms. Because the environment has undoubtedly been involved in the prokaryotic evolution, it is quite diﬃcult to determine
whether the environmental factors are directly linked with the genomic traits, orindirectly through the phylogenetic traits. Though we do not have answers for thisquestion yet, we will compare those genomic traits that are signatures of certain
phylogenetic origins against those that are signatures of certain ecological contexts.
If the two sets of the signature genomic traits are signiﬁcantly diﬀerent, we may
claim that the phylogenies and environments are in diﬀerent roles in shaping thethe genomic traits of prokaryotes.
Acknowledgements
This research is supported in part by National Science Foundation (NSF/OCE0928196).
References[1] Bohlin, J., Skjerve, E., and Ussery, D.W., Investigations of oligonucleotide usage variance within and between prokaryotes, PLoS Computational Biology, 4(4):e1000057,
2008.
[2] Ermolaeva, M.D., White, O., and Salzberg, S.L., Prediction of operons in microbial
genomes, Nucleic Acids Res., 29(5):1216-1221, 2001.
[3] Field, D., Garrity, G., Gray, T., Morrison, N., The minimum information about agenome sequence (MIGS) speciﬁcation, Nature Biotechnology, 26(5):541–547, 2008.
[4] Fukuchi, S., Yoshimune, K., Wakayama, M., Moriguchi, M., and Nishikawa, K.,
Unique Amino Acid Composition of Protein in Halophilic Bacteria, J. Mol. Bio.,327(2) 347–357, 2003.

September 4, 2009

16:2

WSPC - Proceedings Trim Size: 9.75in x 6.5in

45-LinCorrelation between Oxygen Requirement and Gene-Gene Association

13[5] Hirschman L., Clark C., Cohen K.B., Mardis, S., et al., Habitat-Lite: a GSC casestudy based on free text terms for environmental metadata, OMICS, 12(2):129–136,
2008.
[6] Kanji, G.K., 100 Statistical Tests, Sage Publications Ltd, 2006.
[7] Kanehisa, M., Araki, M., Goto, S., Hattori, M, Hirakawa, M., Itoh, M., Katayama,T., Kawashima, S., Okuda, S., Tokimatsu, T., and Yamanishi, Y., KEGG for linking
genomes to life and the environment, Nucleic Acids Res., 36(Database issue):D480-4,
2008.
[8] Konstantinidis, K.T. and Tiedje, J.M., Trends between gene content and genome sizein prokaryotic species with larger genomes, Proc Natl Acad Sci U S A, 101(9):3160–
3165, 2004.
[9] Konstantinidis, K.T., Ramette, A., and Tiedje, J.M., The bacterial species deﬁnitionin the genomic era, Philos Trans R Soc Lond B Biol Sci, 361(1475):1929–1940, 2006.
[10] Koonin, E.V., Makarova, K.S., and Aravind, L., Horizontal gene transfer in prokaryotes: quantiﬁcation and classiﬁcation, Annual Review Microbiology, 55:709–742, 2001.
[11] Merhej, V., Royer-Carenzi, M., Pontarotti, P., and Raoult, D., Massive comparative
genomic analysis reveals convergent evolution of specialized bacteria, Biology Direct,
4:13, 2009.
[12] NCBI Microbial Genome Project, Available from: http://www.ncbi.nlm.nih.gov/
genomes/lproks.cgi.
[13] Paul, S., Bag, S., Das, S, Harvill, E., and Dutta, C., Molecular signature of hyper saline adaptation: insight from genome and proteome composition of halophilicprokaryotes, Genome Biology, 9(4):R70, 2008[14] Suen, G., Goldman, B., Welch, R., Predicting prokaryotic ecological niches using
genome sequence analysis, PLoS ONE, 2(1):e473, 2007.
[15] The Gene Ontology Consortium, Gene ontology: tool for the uniﬁcation of biology,
Nature Genet., 25(1):25–29, 2000.
[16] Todar, K., Todar’s Online Textbook of Bacteriology, Available from: http://
textbookofbacteriology.net/, 2008.
[17] Wu, H., Mao, F., Su, Z., Olman, V., Xu, Y., Prediction of functional modules based ongene distributions in microbial genomes, Genome Informatics, 16(2):247–259, 2005.
[18] Wu, H., Su, Z., Mao, F., Olman, V., Xu, Y., Prediction of functional modules basedon comparative genome analysis and Gene Ontology application, Nucleic Acids Res.,
33(9):2822–2837, 2005.
[19] Wu, X., Zhu, L., Guo, J., Zhang, D.-Y., Lin, K., Prediction of yeast protein-protein
interaction network: insights from the Gene Ontology and annotations, Nucleic Acids
Res., 34(7):2137–2150, 2006.