Associations Between Inverted Repeats and the Structural Evolution of Bacterial Genomes

Corresponding author: Eduardo P. C. Rocha, Université Pierre et Marie Curie, 12 Rue Cuvier, 75005 Paris, France., erocha{at}pasteur.fr (E-mail)

Communicating editor: M. A. F. NOOR

	ABSTRACT

TOP ABSTRACT METHODS AND DATA MODELS OF GENOME REARRANGEMENT RESULTS AND DISCUSSION CONCLUSION LITERATURE CITED

The stability of the structure of bacterial genomes is challenged by recombination events. Since major rearrangements (i.e., inversions) are thought to frequently operate by homologous recombination between inverted repeats, we analyzed the presence and distribution of such repeats in bacterial genomes and their relation to the conservation of chromosomal structure. First, we show that there is a strong under-representation of inverted repeats, relative to direct repeats, in most chromosomes, especially among the ones regarded as most stable. Second, we show that the avoidance of repeats is frequently associated with the stability of the genomes. Closely related genomes reported to differ in terms of stability are also found to differ in the number of inverted repeats. Third, when using replication strand bias as a proxy for genome stability, we find a significant negative correlation between this strand bias and the abundance of inverted repeats. Fourth, when measuring the recombining potential of inverted repeats and their eventual impact on different features of the chromosomal structure, we observe a tendency of repeats to be located in the chromosome in such a way that rearrangements produce a smaller strand switch and smaller asymmetries than expected by chance. Finally, we discuss the limitations of our analysis and the influence of factors such as the nature of repeats, e.g., transposases, or the differences in the recombination machinery among bacteria. These results shed light on the challenges imposed on the genome structure by the presence of inverted repeats.

THE advances of the last decade on genome sequencing and pulsed field gel electrophoresis provide a puzzling image concerning the organization and stability of bacterial genomes. On one hand, many features of genome organization have been found or further unraveled, such as the impact of replication in imposing compositional strand biases (LOBRY 1996 ) and constraining gene distribution (MCLEAN et al. 1998 ). Coding sequences cover 90% of most bacterial genomes and transcriptional regulation can be very complex, suggesting selection for structural stability. On the other hand, the genome structure is extremely fluid. Operons are not well conserved between distant species (ITOH et al. 1999 ) and gene content varies at a very high rate in some bacterial lineages (CASJENS 1998 ), partly because of frequent horizontal transfers (OCHMAN et al. 2000 ). Distinctive features of the organization of bacterial genomes, notably in relation to replication, have different importance in different species (ROCHA and DANCHIN 2001 ). Among groups such as Firmicutes, one observes very different compositional bias, as well as different gene positional biases (ROCHA 2002 ). Thus, the understanding of the trade-offs between genome stability and the requirements of genotypic diversity is becoming a major issue in the study of genome evolution.

Intrachromosomal homologous recombination can lead to deletions, duplications, translocations (for direct repeats), and inversions (for inverted repeats; SMITH 1988 ; ROTH et al. 1996 ; ROMERO and PALACIOS 1997 ). All these events change the genome composition, but most of them do not induce very important shifts in its structure. Indeed, large deletions are counterselected, large insertions are rare, and large tandem duplications are not observed in currently sequenced bacterial genomes, probably because they are too unstable. Therefore, inversions have been regarded as one of the main motors of chromosome structural change (LIU and SANDERSON 1996 ; ROTH et al. 1996 ; HUGHES 2000 ). Pairwise comparisons among completely sequenced genomes show that the first large chromosome rearrangements are caused by inversions (EISEN et al. 2000 ; TILLIER and COLLINS 2000A ; ZIVANOVIC et al. 2002 ). Currently, the sole exception to this rule is provided by the comparison of Mycoplasma pneumoniae and M. genitalium, which reveals several translocations and no inversion (HIMMELREICH et al. 1997 ). However, inverted repeats capable of mediating chromosomal inversions are strongly underrepresented in these genomes, being present up to 60 times less frequently than direct repeats (ROCHA and BLANCHARD 2002 ).

It is difficult to define genome stability without experimental support or a large number of very close genomes. Thus, we use replication compositional bias as a proxy of genome stability. DNA replication is asymmetric; one strand is replicated continuously (leading strand) whereas the other is replicated in discrete steps through the use of Okasaki fragments (lagging strand; MARIANS 1992 ). Since the origins of replication in bacteria, when they are known, seem to be unique, the asymmetry in replication creates a durable asymmetry in the structure of the chromosome (FRANK and LOBRY 1999 ). This leads to different nucleotide compositions in each replicating strand, which seem to result from an essentially neutral mutational bias (FRANK and LOBRY 1999 ; TILLIER and COLLINS 2000B ; ROCHA and DANCHIN 2001 ). Thus, the intensity of the bias is shaped by the strength of the mutational mechanism and by the rates of genome rearrangement. Assuming that the strength of the mechanism has small variations between genomes, strand bias should be highly correlated to the stability of the chromosome.

Chromosomal inversions seem to be rare in nature but very frequent in the laboratory (LOUARN et al. 1985 ; ROTH et al. 1996 ). This suggests the existence of selection pressure for maintaining chromosomal structure. As a result of this, the large inversions observed in bacterial genomes are symmetrical in relation to the origin of replication (EISEN et al. 2000 ; TILLIER and COLLINS 2000A ). It is then important to understand how chromosomes face recombination events and especially inversions. Here, we tackle this question by accounting for the distribution of repeats capable of producing rearrangements (inverted repeats). We also take into consideration the effects of such potential rearrangements on different elements of the chromosomal structure, in particular chromosome asymmetry and replication strand bias.

	METHODS AND DATA

TOP ABSTRACT METHODS AND DATA MODELS OF GENOME REARRANGEMENT RESULTS AND DISCUSSION CONCLUSION LITERATURE CITED

Data:
Data on the complete bacterial genomes were taken from Entrez Genomes (http://www.ncbi.nlm.nih.gov), and the annotations were taken from the GenBank files. Except when noted otherwise, we used only one strain for each species to avoid any bias in favor of species represented several times in GenBank. This resulted in a data set of 63 chromosomes, representing 58 bacterial genomes.

Identification of large strict repeats:
To compute the threshold minimal length of large repeats, we used a statistic of extremes that takes into account the nucleotide composition and the length of the genome (KARLIN and OST 1985 ). Among bacteria, the minimal length for which the probability of finding one exact repeat in the genome is <1 is in the range 21–26 nucleotides (nt) (P < 0.001; ROCHA et al. 1999A ). The search for such large, strictly identical repeats was done using Reputer (KURTZ and SCHLEIERMACHER 1999 ).

Deriving large nonstrict repeats:
To investigate the influence of genome structure on repeats, we identified nonstrict repeats from strict repeats using an extension process previously described (ACHAZ et al. 2000 , ACHAZ et al. 2002 ). The method identifies nonstrict repeats by extending both sides of strict repeats when they share significant similarity in sequence. This is based on a local alignment procedure (SMITH and WATERMAN 1981 ). Nucleotide frequencies differ widely between bacterial species and identity matrix scores produce artificially longer repeats in highly biased genomes. To avoid this effect, we used an empirical scoring matrix for each chromosome, which takes into account the frequencies of nucleotides (ACHAZ et al. 2002 ). After comparing different methods to build such a matrix, we used the one providing closer average lengths for repeats detected in random genomes with different nucleotide compositions (from very low to very high values of G + C content). This scoring matrix is the following:

where p_i is the frequency of the nucleotide i in the genome. This matrix provides scores of matches ranging from 20 to 41 and scores of mismatches ranging from -41 to -20. The score of match_N/i is either 7 or 8, depending on the genome bias.

Strand compositional bias:
Linear discriminant analyses followed by skew analyses were used to identify genomes with significant strand bias, as in ROCHA and DANCHIN 2001 . Once origin and terminus were identified, compositional strand bias was quantified in terms of GC skews. These are defined as the average difference in GC skews between the genes in the leading and the lagging strand. GC = (G_lead - C_lead)/(G_lead + C_lead) - (G_lag - C_lag)/(G_lag + C_lag), where X_i is the nucleotide frequency of the nucleotide X (i.e., G or C) in the genes of strand i (i.e., lead or lag). This normalizes the replication biases in terms of the genome average bias in nucleotide composition.

	MODELS OF GENOME REARRANGEMENT

TOP ABSTRACT METHODS AND DATA MODELS OF GENOME REARRANGEMENT RESULTS AND DISCUSSION CONCLUSION LITERATURE CITED

Before proceeding, we must model the potential outcome of recombination between repeats. We consider a random model where each copy of a repeat can recombine with another copy of the repeat in a random way. We further suppose that couples of repeats of identical size recombine at identical frequency. Yet, two factors are taken into account. First, since one expects larger repeats to recombine more often than smaller ones (in a linear fashion according to SHEN and HUANG 1986 ; VULIC et al. 1997 ), we weight each repeat by its length when computing indices of potential rearrangement. Second, we incorporate the fact that recombination always proceeds between two copies of a repeat. A repeat present in two copies recombines only in a single way between the two copies. However, a repeat with three copies (e.g., A, B, and C) can recombine in three different ways (A with B, A with C, and B with C), each resulting in different outcomes. Thus, because recombination takes place between pairs of repeats we count the latter repeat as three couples of repeats. Therefore, counting pairs of potentially recombining repeats is equivalent to counting couples of repeats.

Assumptions:
To accomplish this analysis we had to proceed to several assumptions:

1. We implicitly assume that homologous recombination may proceed with all statistically significant large repeats. Such minimal length varies from 21 to 26 nt depending on genome size and composition. In fact, it corresponds to the minimal length requirements for the start of homologous recombination by the RecBCD system in Escherichia coli and its functional homolog AddAB in Bacillus subtilis, the only bacterial species for which such studies have been conducted (SHEN and HUANG 1986 ; ROBERTS and COHAN 1993 ).

2. We analyze the distribution of repeats as they occur in the published genomes. Thus, we do not take into account the changes of that distribution if rearrangements do occur. Naturally, more refined models should be developed in the future to tackle this question. Such models should take into account the results of rearrangements on the relative positioning of the other repeats (even though that is a very hard computational problem), and the rate of repeat creation and loss.

3. Given the lack of experimental comparative studies of recombination mechanisms and frequencies in most bacteria, we implicitly assume that the frequency of intrachromosomal recombination is the same in different genomes. All bacteria here analyzed, except Buchnera (SHIGENOBU et al. 2000 ), have RecA, the major protein in homologous recombination pathways. However, the different elements of the homologous recombination pathways vary significantly between genomes (EISEN and HANAWALT 1999 ).

4. We consider that all repeats are involved in the dynamics of the chromosome in the same way. Since self-replicating repeated elements, such as IS, have special dynamics, we analyze their influence separately. We discuss the impact of violations to these assumptions in the interpretation of the results.

Measures of global rearrangement:
The inversion produced by a recombination event between two occurrences of a repeat implicates the inversion of the region between the repeats—the spacer. This element contains less than half of the chromosome, by definition. A simple way of analyzing the potential for genome rearrangement is simply to divide the total number of pairs of inverted repeats by the length of the genome, thereby computing a density of pairs of repeats. However, the analysis of direct repeats has shown that the average spacer length is different between genomes (ROCHA et al. 1999A ). Also, the frequency of recombination between copies of a repeat is expected to be proportional to the repeat's length. Therefore, a more precise measure for the average rearrangement length potentially induced by the inverted repeats in a genome is given by

where R_L is the potential rearrangement length associated with the repeats in the genome; Lr_i, the length of the repeat i; Lsp_i, its spacer length; G_L, the genome length; and Lr_T, the sum of the repeats' lengths.

Inversions and replication structure:
Compositional strand bias and chromosomal symmetry are differently affected by recombination between inverted repeats (Fig 1). By definition, copies of inverted repeats occur in different DNA strands. However, they can be in the same type of replicating strand (i.e., both copies in the same chirochore—either leading or lagging strand) or in the same replichore (same replicating half of the chromosome). If they are in the same replichore (I_R), then an inversion will produce a shift of the spacer from one replicating strand to the other, so that the sequence of the spacer that was on the leading strand switches to the lagging strand and vice versa. However, because in this case the spacer does not include the origin or the terminus of replication, the symmetry of the chromosome (i.e., the opposite placement of origin and terminus of replication) will not be affected. Naturally, close occurrences will induce small changes, whereas distant occurrences induce large changes. One can then define a measure of average strand switch (SS) potentially induced by all I_R repeats in a genome as

View larger version (28K): [in this window] [in a new window] [Download PPT slide]   Figure 1. Examples of intrachromosomal recombination between inverted repeats. Solid and shaded semicircles represent different replicating strands. (A) Repeats in the same chirochore (IC) and symmetrical around the origin of replication. The inversion through recombination between 1 and 2 results in RL = Lsp12/GL, AS 0, SS = 0. (B) Repeats in the same chirochore (IC) and asymmetrical around the origin of replication. The inversion through recombination between 1 and 3 results in RL = Lsp13/GL, AS = 2 x |P13, POri|/GL, SS = 0. (C) Repeats in the same replichore (IR). The inversion through recombination between 4 and 5 results in RL = Lsp45/GL, AS = 0, SS = RL. Lspij is the shortest distance between i and j in the circle (i.e., the length of the spacer), GL is the length of the genome, Pij is the geometric center of the spacer between the copies i and j, POri is the position of the origin of replication.

Conversely, the spacer of a repeat with occurrences in the same chirochore (I_C) encompasses the origin or the terminus of replication. In this case, an inversion will not change the leading/lagging character of the spacer, but may induce changes in the relative positions of the origin and terminus of replication. The average asymmetry switch (AS) induced by the inversion will be proportional to the distance of the position of the center of the spacer (P_i) to the closer origin/terminus of replication (P_ori/ter):

Expected values:
We determined the expected values of R_L, SS, and AS under a model where pairs of copies of repeats engage into recombination randomly. The null model corresponds to a random placement of repeats in the chromosomes. Thus, approximate values for the expectations of R_L, SS, and AS can be easily determined by simulation. Here, we detail the derivation of the exact expressions. Under the model of random placement of repeats in the chromosome, the distance between two copies of a repeat is distributed uniformly in the interval ]0, G_L/2]. Therefore, the expected value of R_L is ¹/₄ (1/G_L x G_L/4).

For the determination of the expected values of SS and AS we assume, as previously, uniform distribution for the distance between copies. For simplicity, but this does not affect generality, we assume that all repeats have the same length. Under these conditions, we call SSi the strand switch associated with a repeat and allow it to take one of two values: either the length of the spacer (both copies in the same replichore) or 0 (both copies in the same chirochore). Given the symmetry of the system, the value SSi = 0 has a probability 0.5. Thus, one has to determine only the expression for the probability density function of SSi when repeats are in the same replichore (which sums to 0.5). This results in a function that depends linearly on the spacer length (see Fig 2) and is constrained by two conditions: (i) the cumulated probability is 0.5 and (ii) the function evaluates to zero at G_L/2. Thus, the probability density function is given by

which results in a function

whose expected value is given by

View larger version (18K): [in this window] [in a new window] [Download PPT slide]   Figure 2. Diagram depicting the rationale of the method to determine the probability density function associated with SS. Let us suppose the above replichore. A repeat will be counted only if both copies occur in the same replichore. Let us fixate the first copy of the repeat. If this copy is at position 1 (repeat 1), then the other copy has a uniform probability of occurrence in the replichore except at position 1; i.e., it has a uniform probability density in 1 (which has a length of GL/2 - 1). Now suppose the repeat whose first occurrence is at position 2. The second occurrence of this repeat has a uniform probability of occurrence in 2 (which has a length of GL/2 - 2). A similar reasoning applies to all repeats whose first copy is at positions 3 to GL/2 - 1. For these repeats, the second copy is distributed with a uniform probability of occurrence in 3 to GL/2-1. A copy at GL/2 cannot have a second occurrence in the replichore. Thus, the distribution of the length of the spacer () is a linear function of the length of the replichore (i.e., it is a linear function of GL/2).

Since SS is the sum of each partial SSi, divided by the genome length, its expected value is ¹/₁₂. Excluding from the analysis the repeats in the same chirochore, for which SS = 0, the expected value becomes ¹/₆. A similar reasoning applies to the determination of the expected value of AS.

	RESULTS AND DISCUSSION

TOP ABSTRACT METHODS AND DATA MODELS OF GENOME REARRANGEMENT RESULTS AND DISCUSSION CONCLUSION LITERATURE CITED

Relative distribution of inverted repeats in bacterial genomes:
Absolute numbers of repeats: The distribution of direct and inverted repeats in bacterial genomes has recently been analyzed in the context of horizontal transfer (ROCHA et al. 1999A ) and of repeat generation (ACHAZ et al. 2002 ). These works have shown that bacterial genomes contain a considerable amount of large repeats. Furthermore, the abundance of such repeats is highly variable among species. In our data set, one finds a maximum of 66,860 pairs of inverted repeats in Neisseria meningitidis and no inverted repeats in Chlamydia trachomatis (Table 1). Interestingly, both bacteria are human pathogens and seem to have a functional RecBCD system. However, C. trachomatis is an obligatory and intracellular parasite, whereas Neisseria is neither. A low level of repeats is typical of obligatory intracellular bacteria (see below). On the other hand, Neisseria is a very extreme case of repeat abundance, mostly for effects of antigenic variation (SAUNDERS et al. 2000 ). For clarity it is removed from most graphs where the number of repeats is taken explicitly into account. The average length of the repeats in the different genomes is nearly always well above the lower threshold of statistical significance. Indeed, the average length of strict repeats in the genomes is 207 nucleotides.

Inverted repeats are underrepresented compared to direct ones: One would expect to find more direct than inverted repeats if selection acts toward minimizing inversions. On one hand, inverted repeats may induce inversions. On the other hand, if repeats originate mainly from close direct repeats (ACHAZ et al. 2002 ), inversions are required to create inverted repeats from direct repeats. In any case, our analysis indicates that inverted repeats are usually underrepresented compared to direct repeats: the ratio of inverted/direct repeats is almost always <1 (Fig 3). This still holds if one excludes close direct repeats, which are thought to be the result of an active process of duplication (ACHAZ et al. 2002 ). The strongest underrepresentation of inverted repeats tends to occur when the total number of repeats is smaller. This suggests that when repeats are avoided (e.g., by structural reasons), inverted repeats are even more strongly avoided, possibly because of their major role in chromosomal inversions. Genomes saturated with repeats, e.g., Neisseria, show no difference between inverted and direct repeats, possibly because selection for a direct positioning vs. the inverted becomes inefficient at such a high level of repeat density (or possibly because their recombination apparatus is less sensitive to repeats).

View larger version (20K): [in this window] [in a new window] [Download PPT slide]   Figure 3. Distribution of the ratio of inverted (NI) over direct (ND) repeats in the function of the total number of repeats and corresponding histogram.

Rearrangement length: Although relative avoidance of inverted repeats may suggest counterselection of sequences capable of producing inversions, many different causes can underlie such avoidance. In particular, if the magnitude of the rearrangements' counterselection were simply proportional to their length, one would expect a selection for close repeats that could induce small rearrangements. However, the average observed/expected (O/E) R_L is 0.963, which is not significantly different from 1 (P > 0.4, signed-rank test; Fig 4). One is then inclined to think that although selective pressure against rearrangements may cause the avoidance of inverted repeats, relative to direct ones, there is no systematic tendency toward the minimization of the length of the potential rearrangement.

View larger version (38K): [in this window] [in a new window] [Download PPT slide]   Figure 4. Observed/expected median rearrangement length of repeats in the bacterial genomes. The arrow indicates the median (0.96), which is not significantly different from 1 (P > 0.4, signed-rank test).

Support for the hypothesis that inverted repeats challenge the chromosomal stability:
Analyses of close genomes: The genomes presenting the lowest values of observed/expected rearrangement length are the ones containing fewer repeats, notably Chlamydia, some Mycoplasma, Rickettsia, and Buchnera. These are also the genomes with smaller inverted/direct ratios. Interestingly, recent works have shown that many obligatory intracellular bacterial genomes keep a remarkable synteny (SUYAMA and BORK 2001 ; WOLF et al. 2001 ). In light of their small populations one would expect less efficient purifying selection and therefore larger differences in gene order. The observations that such genomes contain a reduced recombination potential, especially when it involves inversions, may thus explain their stability. Recently, a second genome of Buchnera has been published (TAMAS et al. 2002 ), which indicates that for 50 million years these genomes remained strictly colinear, showing no inversion. This is not surprising since these genomes have both <10 large inverted repeats in their genomes and a deficient homologous recombination machinery. However, the other small stable genomes presenting few repeats do code for both RecA and RecBCD or RecF-like systems.

Closely related bacteria with very different repeat abundance show increased levels of synteny loss. For example, the strains KIM and CO92 of Yersinia pestis are very closely related (average 99.9% of protein similarity) but show a considerable amount of rearrangement in their genomes (DENG et al. 2002 ). The closely related Salmonella enterica typhi and typhimurium (mean protein similarity of 98.6%) show only two large rearrangements. This can be put into relation with their different numbers of repeats: 5000 in Y. pestis, many of them insertion sequences, and <1000 in S. enterica typhimurium (for genomes of similar lengths). The correlation between abundance of repeats and genome stability seems to be valid also in Archaea. A recent comparative study of three Pyrococcus (Pyrococcus abyssi, P. horikoshii, and P. furiosus) has indicated that P. furiosus is much more subject to genome rearrangements (ZIVANOVIC et al. 2002 ). The close comparison between these genomes seemed to implicate repeats in these rearrangements. Indeed, the comparison of the number of pairs of inverted repeats in these genomes (of nearly identical genome length) is in good agreement with these observations: 503 for P. horikoshii, 711 for P. abyssi, and 2004 for P. furiosus.

The case of Rickettsia conorii: One major exception to this trend concerns the comparison of Rickettsia conorii with R. prowazekii. R. conorii is 14% larger than R. prowazekii, but the genomes are colinear, thus supposedly stable, even though R. conorii contains 1180 inverted repeats that have been proposed to replicate in a selfish manner (OGATA et al. 2000 ) for only 6 inverted repeats in R. prowazekii. A closer analysis of the former genome indicates that its repeats are all small, since 70% of repeats have between 25 and 30 bp, and only 2 repeats are >85 bp. Since the genome does not contain a homolog of the RecBCD system, homologous recombination is expected to follow the RecF pathway (SHEN and HUANG 1986 ). The RecF pathway is thought to be involved in restarting replication after replication fork disassociation, and the importance of its role in homologous recombination has been disputed (COURCELLE et al. 2001 ; AMUNDSEN and SMITH 2003 ). For this pathway, the minimal length of strict homology required to start homologous recombination in E. coli is much larger than that required for the RecBCD pathway. It might be as large as 90 bp, whereas it is 20–30 bp for the RecBCD pathway (SHEN and HUANG 1986 ). It is thus quite possible that these repeats are not targeted by homologous recombination in Rickettsia, because of the peculiarities of its recombination machinery. This would explain the stability of these genomes in spite of the large number of small repeats.

Support to use replication composition bias as a proxy of genome stability: We have previously suggested a link between the number of repeats in a genome and the replication compositional strand bias (ROCHA et al. 1999B ). Compositional replication strand bias seems to result from a fast asymmetric mutational bias causing inverted genes to adapt fast to the new strand (TILLIER and COLLINS 2000B ). The magnitude of strand bias can vary either by the intensity of the mutational bias or by processes counteracting its establishment, such as genome rearrangements. In this sense, important levels of strand bias can be established only if the genomes are stable. Among the 63 chromosomes, 44 exhibit a significant replication bias. Genomes with significant strand bias have a median of 394 repeats/genome, whereas the remaining genomes have a median of 708 repeats/genome (even though the former genomes are 23% larger). Moreover, genomes with significant strand bias show a negative correlation ( = -0.30, P < 0.05, Spearman's rank test) between the number of inverted repeats and the intensity of the bias (measured as GC skew). These results suggest that the chromosomal stability is highly challenged by inverted repeats. As a consequence, in very stable chromosomes, the number of inverted repeats might tend to be minimized.

How do inverted repeats challenge the chromosomal stability?
To tackle this question, we divided inverted repeats into two categories: repeats in the same chirochore (further labeled as I_C) and repeats in the same replichore (I_R; see MODELS OF GENOME REARRANGEMENT and Fig 1). We also developed simple measures of the impact of these repeats on AS and SS. AS measures the consequences of potential rearrangements between I_C. SS measures the consequences of potential rearrangements between I_R. Therefore the ratio of observed/expected of these indices indicates the association between the positioning of repeats and the instabilities they might induce on genomes.

Differences between I_C and I_R suggest selection for chromosomal stability: Repeats are causes of change in chromosomal structure, but the distribution and maintenance of repeats is also constrained by the characteristics of that structure. In genomes containing strong compositional strand biases, the mutation pattern is similar for both copies of I_C, but different for both copies of I_R (ROCHA and DANCHIN 2001 ). Thus, faster divergence between copies of I_R repeats, relative to I_C, could lead to differences in number and length between I_C and I_R (Table 2). If this is so, we should expect higher similarity between copies of I_C than between copies of I_R. Naturally this hypothesis cannot be tested with the data on strict repeats, which are identical (by definition). Therefore, we extended by dynamic programming the exact repeats into larger nonstrict repeats by searching for significant similarity at the edge of the strict repeats (as described in METHODS AND DATA). The comparison of nonstrict repeats confirms that I_C are more numerous and longer than I_R (Table 2). However, the average identity percentage does not differ between I_C and I_R repeats. This suggests that the different abundance of each type of repeats is not due to larger rates of divergence among I_R repeats. The avoidance of I_R could then be a consequence of negative selection on the distribution of repeats. Such selection pressure may have different origins. First, inversions change the relative distance of the genes to the origin of replication. This is expected to be counterselected in genomes selecting for highly expressed genes near the origin of replication. Second, genes on the leading strand will be transferred to the lagging strand and vice versa. This is also expected to be counterselected for highly expressed genes and for genomes containing two dedicated DNA polymerases (ROCHA 2002 ). Finally, it has been proposed that higher levels of substitutions in inverted genes may lead to gene loss (MACKIEWICZ et al. 2001 ).

Chromosomes tend to keep their symmetry: Using the positions of the origins and termini of replication, one can determine the relative lengths of the two replichores. We analyzed the 48 genomes for which the origin and the terminus can be reliably predicted. In these genomes the length of the two replichores never differed by >20%. Further, the ratio of the lengths of the smallest over the largest replichores of each genome shows a median of 0.95 (data not shown). Such similarity between replichore lengths is in good agreement with the existence of a selective pressure against inversions increasing the asymmetry of the chromosome. A similar selection pressure has been observed in horizontal transfer between strains of E. coli and Salmonella, since genomic variation tends to occur in equal amounts on both replichores, thus keeping chromosomal symmetry (BERGTHORSSON and OCHMAN 1998 ). Further, inversions between the rRNA operons of E. coli that strongly change the symmetry of the chromosome have been found to be severely detrimental (HILL and GRAY 1988 ). This is also in good agreement with data indicating preference for symmetrical rearrangements around the origin and terminus of replication (EISEN et al. 2000 ; TILLIER and COLLINS 2000A ). It has been proposed that such inversions could result from illegitimate recombination between the two newly replicated chromosomes at the moment of replication (TILLIER and COLLINS 2000A ), but there is still no experimental evidence of such a mechanism. The analyses of AS indicate O/E ratios systematically smaller than one (average AS = 0.86, P < 0.001, signed-rank test; Fig 5). This indicates that potential rearrangements caused by homologous recombination between I_C tend to be symmetrical and that such I_C repeats may be less negatively selected.

View larger version (18K): [in this window] [in a new window] [Download PPT slide]   Figure 5. (A) Observed/expected values for the asymmetry switch. The solid arrow indicates the median value (0.86). (B) Observed/expected values for the strand switch. The solid arrow indicates the median of the genomes with significant compositional strand bias (0.80), whereas the shaded arrow indicates the median for the other genomes (1.08).

Strand switch and replication compositional bias: An inversion between two I_R switches the strands of the spacer and thus switches the compositional biases in each strand. The comparison of genomes with and without significant compositional strand biases shows a different median observed/expected SS (respectively, 0.80 and 1.08, P < 0.01, Wilcoxon test). Genomes lacking strand compositional bias have a median observed/expected SS not significantly different from 1 (median 1.08, not significant), whereas the others show a ratio systematically smaller than one (median 0.80, P < 0.001, signed-rank test). Further, among these genomes there is a significant negative correlation between the potential of repeats to induce strand switch and their genome GC skew (-0.553, P < 0.001, Spearman ; Fig 6). Although the correlation is highly significant, the analysis of its residuals shows a considerable dispersion and two outliers, Streptococcus pneumoniae and N. meningitidis (P < 0.01). This is an indication that other factors affect strand bias and/or that some of our basic assumptions are oversimplified (e.g., the assumption of similar recombination mechanisms and frequencies in different bacteria).

View larger version (15K): [in this window] [in a new window] [Download PPT slide]   Figure 6. Strand switch (SS x NI) vs. the strand composition bias (GC skew). Spearman's rank correlation is -0.553 (P < 0.001). The cross corresponds to the genome of S. pneumoniae (excluded as an outlier, along with N. meningitidis; see text).

General picture: Both AS and SS indicate observed/expected ratios systematically smaller than 1 (Fig 5), and the differences between AS and SS are not statistically significant. One should note that avoiding simultaneously AS and SS can be done it two different ways. First, it can be done if the occurrences of repeats are close. However, the analysis of R_L for all inverted repeats and the relative abundance of I_R and I_C indicates that is not the case. Second, it can be done by selecting the placement of the two copies of repeats in the same chirochore and in a symmetrical way around the origin or the terminus of replication (see Fig 1). Our results point toward the latter hypothesis.

The special role of transposases: Among the simplifications we have made at the beginning of this work, we assumed that repeats induced rearrangements through homologous recombination. This is an oversimplification for some types of sequences and especially when transposases are concerned. We have thus tried to further analyze the impact of these elements in the induction of genome rearrangements. We have identified 40 bacterial genomes containing genes coding for putative transposases, using the annotation files. As expected, these genomes contain a much larger density of repeats (4.5 times larger, P < 0.002, Wilcoxon test). Further, the density of repeats correlates well with the number of transposases ( = +0.45, P < 0.005, Spearman rank test) with two clear outliers (S. solfataricus and S. pneumoniae). However, only 19% of the repeats directly concern sequences coding for transposases. Part of the difference may be explained by the difficulty in identifying unknown families of transposases or by the existence of insertion sequence (IS) remnants that no longer contain intact transposases. Only in three genomes (Bacillus halodurans, Synechocystis C125, and Y. pestis) do transposase-coding sequences include >55% of the genome's inverted repeats (respectively, 76%, 74%, and 72%).

Genomes lacking IS have smaller ratios of inverted/direct repeats (median 0.22) than genomes containing IS (median 0.69, P < 0.01), although both values are significantly <1 (P < 0.01). There is also a positive and similar effect of transposases on the O/E values for AS and SS, which tend to get closer to 1, with the existence and with the number of transposases in the genome (P < 0.01). Thus, the presence of transposases in shuffling the genome seems to exceed the one of simple repeats targeted by homologous recombination. It is likely that their self-replicative behavior further shuffles the chromosome.

	CONCLUSION

TOP ABSTRACT METHODS AND DATA MODELS OF GENOME REARRANGEMENT RESULTS AND DISCUSSION CONCLUSION LITERATURE CITED

The availability of complete genomes of close species, or strains within a species, has brought to light the importance of genome rearrangements in fashioning the bacterial genome (HUGHES 1999 ). Almost without exception, the first major rearrangements observed in recently divergent bacterial strains or species concern inversions that are symmetrical around the origin and terminus of replication. Here, we have tried to understand the relation between such analyses and the potential for intrachromosomal rearrangements mediated by the long repeats present in bacterial chromosomes. Selective processes are probably at the basis of the different abundance and characteristics of inverted repeats. These repeats have important consequences for genome stability, as we have seen, but they can also be under positive selection for antigenic variation or gene dosage effects. This seems to be a particular case of the trade-off between the necessity of generating genotypic diversity and the problems that are derived from that need.

To be able to compare different genomes we were forced to make several simplifying assumptions. Some, e.g., the role of transposases, could be tackled in this work, but most will have to be tested as more experimental works on homologous recombination in other bacteria become available. In particular, it is of outmost importance to determine the relative levels of homologous recombination between repeats in different genomes as well as the minimal lengths required for homologous recombination. The results of this work suggest that these requirements are likely to be different, since some genomes, such as Neisseria, contain an astonishingly high level of repeats. The genome of S. pneumoniae shows particularly striking features, since it contains very high numbers of repeats for its size and large numbers of transposases (46 genes), but exhibits strong GC skews and 80% of the genes in the leading strand. Such a well-ordered genome structure contrasts with the quantity of elements capable of disrupting it. It remains an open question if this is due to differences in the recombination machinery or to other processes.

Most of the results we have presented are compatible with the hypothesis that repeats challenge the structure of bacterial chromosomes. We found low values of AS and SS, a frequent association of repeat density with differential stability of close genomes, and a systematic underrepresentation of inverted repeats relative to direct ones. However, one would have also expected to find O/E R_L values significantly <1, which was not the case. However, considering only I_R, O/E R_L are <1, resulting in O/E SS < 1 (the underrepresentation of I_R as compared to I_C leads to that apparent randomness). On the other hand, the lack of a global bias in R_L shows that mechanisms creating repeats at short distances are not biasing our results. O/E R_L values close to 1 could result if the other elements contributing to the selection of a stable chromosomal structure are not sensitive to the length of the rearrangement. For example, selection of operon structures should be equally effective on small and on large rearrangements, since in both cases only the two operons at the breakpoints of rearrangements are disrupted (and this if repeats are inside different operons). Considering that many large repeats in bacteria are inside coding sequences (ROCHA et al. 1999A ), selection for minimization of operon disruption would be effective only through the avoidance of inverted repeats relative to direct ones (as observed). Thus, the distribution of repeats in genomes would be constrained by the structure of the chromosome in terms of replication, which is dependent on the length and the type of rearrangement, and of some other factors, which are possibly independent of the length of the inverted segments (i.e., the rearrangement length). The relation between the distribution of repeats in bacterial chromosomes and other genomic features is still a largely unexplored field. For example, several works have suggested that nonpermissive intervals of rearrangement exist in E. coli (SEGALL et al. 1988 ; GUIJO et al. 2001 ) and that some regions of the chromosome are particularly prone to recombination events (LOUARN et al. 1991 ). Further work will be required to tackle these questions.

	FOOTNOTES

¹ Present address: Wakeley Lab, BioLabs, Harvard University, 16 Divinity Ave., Cambridge, MA 02138.
² Present address: Equipe Hélix, INRIA Rhône-Alpes, Zirst, 655 Avenue de l'Europe, Montbonnot, 38334 Saint Ismier Cedex, France.

	ACKNOWLEDGMENTS

We are very grateful to Isabelle Gonçalves for carefully reading the manuscript. Guillaume Achaz was funded by "La Société de Secours des Amis des Sciences." Eric Coissac and Pierre Netter are at the Université Pierre et Marie Curie and Eduardo Rocha at the Centre National de la Recherche Scientifique. This work was partially funded by the Association pour la Recherche sur le Cancer, contract 4672.

Manuscript received December 17, 2002; Accepted for publication April 14, 2003.

	LITERATURE CITED

TOP ABSTRACT METHODS AND DATA MODELS OF GENOME REARRANGEMENT RESULTS AND DISCUSSION CONCLUSION LITERATURE CITED

ACHAZ, G., E. COISSAC, A. VIARI, and P. NETTER, 2000  Analysis of intrachromosomal duplications in yeast Saccharomyces cerevisiae: a possible model for their origin. Mol. Biol. Evol. 17:1268-1275.[Abstract/Free Full Text]

ACHAZ, G., E. P. C. ROCHA, P. NETTER, and E. COISSAC, 2002  Origin and fate of repeats in bacteria. Nucleic Acids Res. 30:2987-2994.[Abstract/Free Full Text]

AMUNDSEN, S. K. and G. R. SMITH, 2003  Interchangeable parts of the Escherichia coli recombination machinery. Cell 112:741-744.[Medline]

BERGTHORSSON, U. and H. OCHMAN, 1998  Distribution of chromosome length variation in natural isolates of Escherichia coli.. Mol. Biol. Evol. 15:6-16.[Abstract]

CASJENS, S., 1998  The diverse and dynamic structure of bacterial genomes. Annu. Rev. Genet. 32:339-377.[Medline]

COURCELLE, J., A. K. GANESAN, and P. C. HANAWALT, 2001  Therefore, what are recombination proteins there for? Bioessays 23:463-470.[Medline]

DENG, W., V. BURLAND, G. PLUNKETT, III, A. BOUTIN, and G. F. MAYHEW et al., 2002  Genome sequence of Yersinia pestis KIM. J. Bacteriol. 184:4601-4611.[Abstract/Free Full Text]

EISEN, J. A. and P. C. HANAWALT, 1999  A phylogenomic study of DNA repair genes, proteins, and processes. Mutat. Res. 435:171-213.[Medline]

EISEN, J. A., J. F. HEIDELBERG, O. WHITE and S. L. SALZBERG, 2000 Evidence for symmetric chromosomal inversions around the replication origin in bacteria. Genome Biol. 1: 11.1–11.9.

FRANK, A. C. and J. R. LOBRY, 1999  Asymmetric patterns: a review of possible underlying mutational or selective mechanisms. Gene 238:65-77.[Medline]

GUIJO, M. I., J. PATTE, M. DEL MAR CAMPOS, J. M. LOUARN, and J. E. REBOLLO, 2001  Localized remodeling of the Escherichia coli chromosome: the patchwork of segments refractory and tolerant to inversion near the replication terminus. Genetics 157:1413-1423.[Abstract/Free Full Text]

HILL, C. W. and J. A. GRAY, 1988  Effects of chromosomal inversion on cell fitness in Escherichia coli K-12. Genetics 119:771-778.[Abstract/Free Full Text]

HIMMELREICH, R., H. PLAGENS, H. HILBERT, B. REINER, and R. HERRMANN, 1997  Comparative analysis of the genomes of the bacteria Mycoplasma pneumoniae and Mycoplasma genitalium.. Nucleic Acids Res. 25:701-712.[Abstract/Free Full Text]

HUGHES, D., 1999 Impact of homologous recombination on genome organization and stability, pp. 109–128 in Organization of the Prokaryotic Genome, edited by R. L. CHARLEBOIS. ASM Press, Washington, DC.

HUGHES, D., 2000  Co-evolution of the tuf genes links gene conversion with the generation of chromosomal inversions. J. Mol. Biol. 297:355-364.[Medline]

ITOH, T., K. TAKEMOTO, H. MORI, and T. GOJOBORI, 1999  Evolutionary instability of operon structures disclosed by sequence comparisons of complete microbial genomes. Mol. Biol. Evol. 16:332-346.[Abstract]

KARLIN, S., and F. OST, 1985 Maximal segmental match length among random sequences from a finite alphabet, pp. 225–243 in Proceedings of the Berkeley Conference in Honor of Jerzy Neyman and Jack Kiefer, edited by L. M. L. CAM and R. A. OLSHEN. Wadsworth, New York.

KURTZ, S. and C. SCHLEIERMACHER, 1999  REPuter: fast computation of maximal repeats in complete genomes. BioInformatics 15:426-427.[Abstract/Free Full Text]

LIU, S. L. and K. E. SANDERSON, 1996  Highly plastic chromosomal organization in Salmonella typhi.. Proc. Natl. Acad. Sci. USA 93:10303-10308.[Abstract/Free Full Text]

LOBRY, J. R., 1996  Asymmetric substitution patterns in the two DNA strands of bacteria. Mol. Biol. Evol. 13:660-665.[Abstract]

LOUARN, J. M., J. P. BOUCHE, F. LEGENDRE, J. LOUARN, and J. PATTE, 1985  Characterization and properties of very large inversions of the E. coli chromosome along the origin-to-terminus axis. Mol. Gen. Genet. 201:467-476.[Medline]

LOUARN, J.-M., J. LOUARN, V. FRANÇOIS, and J. PATTE, 1991  Analysis and possible role of hyperrecombination in the termination region of the E. coli chromosome. J. Bacteriol. 173:5097-5104.[Abstract/Free Full Text]

MACKIEWICZ, P., D. MACKIEWICZ, A. GIERLIK, M. KOWALCZUK, and A. NOWICKA et al., 2001  The differential killing of genes by inversions in prokaryotic genomes. J. Mol. Evol. 53:615-621.[Medline]

MARIANS, K. J., 1992  Prokaryotic DNA replication. Annu. Rev. Biochem. 61:673-719.[Medline]

MCLEAN, M. J., K. H. WOLFE, and K. M. DEVINE, 1998  Base composition skews, replication orientation and gene orientation in 12 prokaryote genomes. J. Mol. Evol. 47:691-696.[Medline]

OCHMAN, H., J. G. LAWRENCE, and E. A. GROISMAN, 2000  Lateral gene transfer and the nature of bacterial innovation. Nature 405:299-304.[Medline]

OGATA, H., S. AUDIC, V. BARBE, F. ARTIGUENAVE, and P. E. FOURNIER et al., 2000  Selfish DNA in protein-coding genes of Rickettsia.. Science 290:347-350.[Abstract/Free Full Text]

ROBERTS, M. S. and F. M. COHAN, 1993  The effect of DNA sequence divergence on sexual isolation in Bacillus. Genetics 134:401-408.[Abstract]

ROCHA, E. P. C., 2002  Is there a role for replication fork asymmetry in the distribution of genes in bacterial genomes? Trends Microbiol. 10:393-396.[Medline]

ROCHA, E. P. C. and A. BLANCHARD, 2002  Genomic repeats, genome plasticity and the dynamics of Mycoplasma evolution. Nucleic Acids Res. 30:2031-2042.[Abstract/Free Full Text]

ROCHA, E. P. C. and A. DANCHIN, 2001  Ongoing evolution of strand composition in bacterial genomes. Mol. Biol. Evol. 18:1789-1799.[Abstract/Free Full Text]

ROCHA, E. P. C., A. DANCHIN, and A. VIARI, 1999a  Analysis of long repeats in bacterial genomes reveals alternative evolutionary mechanisms in Bacillus subtilis and other competent prokaryotes. Mol. Biol. Evol. 16:1219-1230.[Abstract]

ROCHA, E. P. C., A. DANCHIN, and A. VIARI, 1999b  Functional and evolutionary roles of long repeats in prokaryotes. Res. Microbiol. 150:725-733.[Medline]

ROMERO, D. and R. PALACIOS, 1997  Gene amplification and genomic plasticity in prokaryotes. Annu. Rev. Genet. 31:91-111.[Medline]

ROTH, J. R., N. BENSON, T. GALITSKI, K. HAACK, J. G. LAWRENCE et al., 1996 Rearrangements of the bacterial chromosome: formation and applications, pp. 2256–2276 in Escherichia coli and Salmonella: Cellular and Molecular Biology, edited by R. C. H. NEINHARDT, J. L. INGRAHAM, E. C. C. LIN, K. BROOKS LOW, B. MAGASANIK et al. ASM Press, Washington, DC.

SAUNDERS, N. J., A. C. JEFFRIES, J. F. PEDEN, D. W. HOOD, and H. TETTELIN et al., 2000  Repeat-associated phase variable genes in the complete genome sequence of Neisseria meningitidis strain MC58. Mol. Microbiol. 37:207-215.[Medline]

SEGALL, A., M. J. MAHAN, and J. R. ROTH, 1988  Rearrangement of the bacterial chromosome: forbidden inversions. Science 241:1314-1318.[Abstract/Free Full Text]

SHEN, P. and H. V. HUANG, 1986  Homologous recombination in Escherichia coli: dependence on substrate length and homology. Genetics 112:441-457.[Abstract/Free Full Text]

SHIGENOBU, S., H. WATANABE, M. HATTORI, Y. SAKAKI, and H. ISHIKAWA, 2000  Genome sequence of the endocellular bacterial symbiont of aphids Buchnera sp. APS. Nature 407:81-86.

SMITH, G. R., 1988  Homologous recombination in procaryotes. Microbiol. Rev. 52:1-28.[Free Full Text]

SMITH, T. F. and M. S. WATERMAN, 1981  Comparison of bio-sequences. Adv. Appl. Math. 2:482-489.

SUYAMA, M. and P. BORK, 2001  Evolution of prokaryotic gene order: genome rearrangements in closely related species. Trends Genet. 17:10-13.[Medline]

TAMAS, I., L. KLASSON, B. CANBACK, A. K. NASLUND, and A. S. ERIKSSON et al., 2002  50 million years of genomic stasis in endosymbiotic bacteria. Science 296:2376-2379.[Abstract/Free Full Text]

TILLIER, E. R. and R. A. COLLINS, 2000a  Genome rearrangement by replication-directed translocation. Nat. Genet. 26:195-197.[Medline]

TILLIER, E. R. and R. A. COLLINS, 2000b  Replication orientation affects the rate and direction of bacterial gene evolution. J. Mol. Evol. 51:459-463.[Medline]

VULIC, M., F. DIONISIO, F. TADDEI, and M. RADMAN, 1997  Molecular keys to speciation: DNA polymorphism and the control of genetic exchange in enterobacteria. Proc. Natl. Acad. Sci. USA 94:9763-9767.[Abstract/Free Full Text]

WOLF, Y. I., I. B. ROGOZIN, A. S. KONDRASHOV, and E. V. KOONIN, 2001  Genome alignment, evolution of prokaryotic genome organization, and prediction of gene function using genomic context. Genome Res. 11:356-372.[Abstract/Free Full Text]

ZIVANOVIC, Y., P. LOPEZ, H. PHILIPPE, and P. FORTERRE, 2002  Pyrococcus genome comparison evidences chromosome shuffling-driven evolution. Nucleic Acids Res. 30:1902-1910.[Abstract/Free Full Text]

This article has been cited by other articles:

				H.-L. Lee, R. K. Jansen, T. W. Chumley, and K.-J. Kim Gene Relocations within Chloroplast Genomes of Jasminum and Menodora (Oleaceae) Are Due to Multiple, Overlapping Inversions Mol. Biol. Evol., May 1, 2007; 24(5): 1161 - 1180. [Abstract] [Full Text] [PDF]

				G. Achaz, F. Boyer, E. P. C. Rocha, A. Viari, and E. Coissac Repseek, a tool to retrieve approximate repeats from large DNA sequences Bioinformatics, January 1, 2007; 23(1): 119 - 121. [Abstract] [Full Text] [PDF]

				X. Bai, J. Zhang, A. Ewing, S. A. Miller, A. Jancso Radek, D. V. Shevchenko, K. Tsukerman, T. Walunas, A. Lapidus, J. W. Campbell, et al. Living with genome instability: the adaptation of phytoplasmas to diverse environments of their insect and plant hosts. J. Bacteriol., May 1, 2006; 188(10): 3682 - 3696. [Abstract] [Full Text] [PDF]

				A. J. Rattray A method for cloning and sequencing long palindromic DNA junctions Nucleic Acids Res., November 8, 2004; 32(19): e155 - e155. [Abstract] [Full Text] [PDF]

				E. P. C. Rocha The replication-related organization of bacterial genomes Microbiology, June 1, 2004; 150(6): 1609 - 1627. [Abstract] [Full Text] [PDF]

This Article Abstract