BACKGROUND
all genomes sequenced so far feature clusters of contiguous repeated genes  that must derive from a common ancestral gene after successive duplication events.
different methods were used to achieve a systematic characterization of tgas in eukaryotic genomes.
all these methods derive from those primarily used to identify any duplicate genes in complete genomes  <cit>  and take into account supplementary data concerning the chromosomal location of the detected duplicate genes.
for the genome of arabidopsis thaliana, the blastp program  <cit>  of sequence similarity search was performed on each chromosome against itself.
then, the blastp results were indexed by their chromosomal physical locations to screen tgas, allowing from  <dig> to  <dig> spacers, i.e.
unrelated genes that separate two tandem duplicated copies  <cit> .
for several genomes of vertebrates, a three-step method was applied  <cit> .
an all-against-all blastp sequence comparison was first carried out on all protein predictions of all studied species with a view to establishing similarities.
on the basis of protein similarity matrices, genes were assigned to families using markov clustering algorithms.
genes were defined as tgas if they belonged to the same family and were either physically adjacent or separated by a maximum number of ten intervening spacer genes.
alternative versions of this method using either blast and smith-waterman algorithms or another clustering method based on the single-linkage criterion were applied to yeast  <cit>  and plant  <cit>  genomes.
here, we developed an original in silico method to identify in a compact genome the complete set of tgas, including those that contain degenerated paralogous copies.
these nonfunctional copies of functional genes are called pseudogenes or gene relics.
the term of pseudogene designates usually a dna segment that shows high similarity to a functional gene, but is inactive due to premature stop codons, indels or the loss of regulatory sequences.
since nonfunctionality of pseudogenes is sometimes difficult to define, zheng and gerstein  <cit>  proposed a classification system of genes and pseudogenes.
a "gene relic" is distinguished from a "pseudogene" by their degree of degeneration.
gene relics have gone through so many mutations of type missense, nonsense or frameshift that do not constitute an open reading frame .
pseudogenes are more similar to an orf.
they are obviously easier to detect than gene relics.
as the distinction is not easy and doesn't affect the results of our method, in this paper, we will use the term "gene relic" to refer to all nonfunctional gene copies present in tgas including pseudogenes.
though tgas have been systematically analyzed in some genomes, the frequency of tgas containing gene relics remains unknown.
identification of these residual duplicated copies is required in order to correctly delimit the tandem repeated unit and retrace the evolutionary history of tgas.
whereas other existing methods used to detect tgas take 0- <dig> spacers into account, our method is aimed at tgas without spacer genes.
in few cases, one spacer is authorized within a tga.
from an evolutionary point of view, the structures without intervening genes between successive paralogs should be the most recent, since they display no chromosomal rearrangement such as insertion of genes.
another distinctive feature of our method, as compared with other methods, is the incorporation of a final step of manual data curation minimizing the number of false positive tgas.
we applied our method of analysis to the complete, assembled genome sequences of nine hemiascomycete yeasts in order to obtain a catalog of tgas covering a large phylum of phylogenetically related species.
this set of data proved useful in retracing genome evolution and notably in determining whether tgas constitute chromosomal rearrangement hotspots for expansion and contraction of gene families.
the detailed sequence analysis of the tga flanking regions could provide better knowledge of the mechanisms at work in the apparition of these particular tandem structures.
furthermore, our tga detection method is a helpful tool for the genome annotation.
in fact, it highlights sequence similarity information between some genes and their neighbors when they are included in a tga and helps to homogenize the annotation of these contiguous gene copies.
RESULTS
algorithm
<dig>  score calculation
the flowchart given in figure  <dig> describes the score calculation process that can be divided into three principal steps.
step <dig> - from each coding sequence  of a complete assembled genome, the corresponding protein sequence was compared with its upstream and downstream chromosomal regions using a tblastn search .
the length of the surrounding dna sequences was three times longer than that of the cds considered .
if the calculated length was below the minimal length  of  <dig> bp, the length retained was equal to lmin.
the bit score was retained for each tblastn sequence alignment.
these initial scores, four per cds considering its two flanking sequences and both dna strands, were called tb  scores.
when several high-scoring segment pairs  were obtained between a given cds protein sequence and one of its flanking region, the total tb score was calculated as the sum of bit scores of all hsps that correspond to the same strand  and do not overlap by more than 20%.
step <dig> - four final scores, called ftb  scores, were calculated for each cds from the tb scores of both strands of its two surrounding sequences .
each tb score was first divided by a tb self-score to express it in percentage.
this tb self-score was the tblastn bit score obtained when the protein sequence of the considered cds was compared with its own genomic sequence.
its calculation also depended on the number and overlapping of hsps generated by the blast program.
the ftb scores were then obtained by subtracting two tb scores expressed as a percentage corresponding to both complementary strands of the same surrounding region.
step <dig> - a filter was necessary to reduce the high background score generated by the small proteins or low sequence complexity proteins.
if tb self-score <  <dig> and  <dig> < ftb score <  <dig>  this filter was applied: filtered ftb score = ftb score - /4).
<dig>  tga extraction
all cdss of a genome were examined, in the ascending order of their chromosomal coordinates, to select the cdss that have at least one ftb score equal to or greater than the threshold value of  <dig> .
to decide if a selected cds  belongs to a tga, its own ftb scores were compared with those of its two adjacent cdss  .
the algorithm of score comparison determines the position of each cds within the tga.
a tga is created when a selected cds occupies the "first position".
as long as the cdss located downstream from this "first cds" occupy a "middle position", the tga is extended.
but as soon as a next cds occupies the "last position", tga elongation comes to an end.
when no directly adjacent cds fits exactly the criteria of a tandem arrayed gene, a "relic" tag was first attributed to the cds at position n. then, the n- <dig> and n+ <dig> cdss were analyzed, permitting the presence of one intervening spacer gene within a tga.
the direct or opposite relative orientation of gene pairs in tgas was determined by comparing their corresponding ftb scores .
<dig>  minisatellite detection
richard and dujon  <cit>  found, in the s. cerevisiae genome,  <dig> protein-coding genes containing consecutive sequence repetitions, called minisatellites, whose repeat unit size ranges from  <dig> bp to  <dig> bp.
these internal tandem repeats can cause problems during tga extraction, since some of them persist outside the coding sequence and can contribute to a ftb score ≥  <dig>  moreover, in some cases, the chromosomal distance between two non-homologous genes containing minisatellites is so small that they can be related to the same tga.
therefore, all cdss involved in a tga were submitted to the equicktandem  and etandem  programs of the emboss package  <cit>  to find tandem repeats in their dna sequences.
equicktandem rapidly identifies potential repeat sizes whereas etandem searches genuine tandem repeats, calculates a consensus for the repeat block and takes gaps into account.
the research of minisatellites and the "relic" tagging in the step of tga extraction are useful when performing the manual curation of tgas .
this enables the researcher to eliminate false positive tgas due to short tandem repeats in gene sequences and to identify the tgas containing gene relics, respectively.
implementation
score calculation, tga extraction and minisatellite detection are the three automated steps of our algorithm and have been implemented in python version  <dig>  http://www.python.org/.
the output file of the first step is a table of the ftb scores calculated for each cds of a given genome.
from this table, another script extracts cdss organized in tandem arrays and then identifies among these cdss those containing minisatellites.
data of this second script can be manually analyzed to eliminate the false positive tgas .
scripts are freely available from the corresponding author who will make recommendations to users and inform them on improvements added to the computational program.
application: identification of tgas in hemiascomycete yeast genomes
databases
we applied our method to nine completely sequenced genomes of hemiascomycete yeasts.
the saccharomyces cerevisiae chromosome sequences and information on annotated genes were downloaded from saccharomyces genome database  http://www.yeastgenome.org/ <cit> .
the eremothecium  gossypii genome sequence and its corresponding annotations were taken from ashbya genome database  http://agd.vital-it.ch/ashbya_gossypii/index.html/ <cit> .
génolevures website http://cbi.labri.fr/genolevures/ <cit>  provided all the data relative to complete genome sequences of the species candida glabrata, debaryomyces hansenii, kluyveromyces lactis, kluyveromyces thermotolerans, saccharomyces kluyveri , yarrowia lipolytica and zygosaccharomyces rouxii.
computation of all tgas in the nine yeast genomes
we define a tga as a structure of contiguous paralogous gene copies, which are either functional or degenerated copies , allowing for the presence of one heterologous gene inserted between the two homologous copies.
in accordance with this definition, we developed an in silico method to detect such tgas in complete eukaryotic genomes.
this method was applied to nine hemiascomycete yeast genomes.
<dig> tgas comprising  <dig> cdss were identified in this set of genomic data, which represents 2% of cdss involved in tgas in relation to the total number of cdss present in these nine genomes .
this proportion is independent of the phylogenetic position of species and is not higher in the post-wgd  species s. cerevisiae and c. glabrata.
interestingly, the d. hansenii genome shows a percentage of cdss in tgas twice higher than the other species.
another remarkable result is the percentage of tgas that include a duplicated gene relic .
on an average 6% of yeast genes contain intron sequences, generally only one intron per gene.
among all cdss that belong to tgas,  <dig> %  have an intron.
in half of the  <dig> tgas concerned, an intron was not present in all the duplicated copies.
the physical distribution of tgas is relatively homogeneous along the different chromosomes of each species .
a first assessment of functional bias for genes in tandem arrays was based on gene ontology  term annotation information  <cit> .
functions such as cellular homeostasis, cell wall organization and biogenesis, conjugation and response to stress, are overrepresented in tgas.
the proportion of genes involved in tgas is very low in the following functional classes: transcription, translation, rna metabolic process and ribosome biogenesis and assembly .
distributions of tga sizes and cds orientations in tgas
tgas were classified according to the number of cdss they contain.
among the nine yeast genomes, the size of tgas ranged from one cds to  <dig> cdss .
tgas belonging to the 1cds-relic class consist of one cds and one gene relic and represents ~10% of the total number of tgas, a proportion equivalent to that of the 3cdss-tga class.
the majority of tgas  comprise two cds copies and the percentage in four copies falls to  <dig> .
large tgas of six and eight cdss  are concentrated in c. glabrata, but the largest one containing  <dig> cdss is in d. hansenii.
the latter , located on the chromosome e of d. hansenii, has been manually reconstructed since it was disrupted  <dig> times by heterologous genes.
in the sequenced strain of s. cerevisiae, s288c, the tga size does not exceed five cdss and the 1cds-relic class of tgas is absent.
nevertheless, three tgas made up of more than one cds plus one relic  are present in this reference strain.
cdss in tgas are principally in a direct orientation  with approximately the same proportion of sense and antisense orientations .
in c. glabrata tgas, the antisense orientation is represented  <dig>  times more than the sense orientation, although the number of cdss on the minus strand  and on the plus strand  is identical.
tgas consisting of two cdss oppositely oriented represent  <dig> % of total tgas.
the low frequency of mixed tgas  is in correlation with the low percentage of tgas containing at least  <dig> cdss  and of which at least two copies have a convergent or divergent orientation, this being the less frequent orientation of a cds pair .
data curation
the originality of our method of tgas detection lies in the possibility to identify tgas containing degenerated gene copies.
from the nine yeast genomes analyzed, two different sets of cdss, possibly close to a gene relic, appeared during the tga extraction step and received a relic tag:   <dig> isolated cdss with at least one ftb score ≥  <dig> and   <dig> cdss, located on one extremity of a tga comprising at least two cds, with two ftb scores ≥  <dig> .
15%  and 22%  of these two respective sets of tagged cdss were first retrieved by an automated curation step to create new tgas.
after this procedure, a manual data curation produced supplementary tgas or some tgas recomposed from 24%  and 48%  of the two respective sets of tagged cdss.
no false positive cds was found among the  <dig> tagged cdss included in a tga, whereas approximately half the isolated cdss  were eliminated.
finally,  <dig> cdss were located near a homologous gene relic:  <dig> constitute the class of tgas that contain just one cds  and  <dig> belong to larger tgas .
a possible source of false positive tgas is the presence of minisatellites in the coding sequences.
among the  <dig> cdss implicated in a tga,  <dig>  have internal tandem repeats .
the manual examination of these suspicious cdss revealed that  <dig> % of the total number of tgas before curation  were false positives.
nevertheless, it was difficult in some cases to decide whether the similarity between contiguous cdss is partially or totally due to minisatellites.
this problem occurred when long stretches of tandem repeats covered a large part of the cdss.
therefore, the percentage of false positives is probably slightly underestimated.
distributions of ftb scores
the degree of gene conservation in a tga can be estimated by comparing blast bit scores between two genes.
ftb scores were calculated from the result of tblastn sequence alignments.
two ftb scores ≥  <dig>  were obtained per gene pairs in a tga.
two additional ftb scores  characterize both chromosomal regions surrounding each tga.
the tga flanking regions can contain cdss, but these coding sequences have no homology with members of the tga .
for each pair of tandem repeated cdss , except those manually recomposed, the ftb score s <dig> was compared with the ftb score s <dig> .
these two scores are mostly equal or equivalent.
in  <dig> % of cases, the difference between both scores is >  <dig> and is due principally  to the size difference between both genes of a tgp.
the comparison between the ftb scores s <dig> and s <dig> shows that in 93% of cases  at least one of these two scores is equal to  <dig> .
few tgas  have one score, s <dig> or s <dig>  greater than  <dig>  they correspond to tgas that start or end with a homologous gene relic.
therefore, they belong to the ncdss-relic class of tgas.
one of the seven tgas in this class is not represented here because it was corrected manually.
evolution of tgas in comparison with the one of the other duplicated genes
distribution of amino acid sequence identities between pairs of homologous proteins was computed to evaluate the divergence between paralogous  and orthologous gene copies .
orthologous proteins show monomodal distributions and average identities comprised between 48-58%.
they represent the most sequence-conserved homologous proteins.
the distribution of tandem paralogs is intermediate between the distribution of other paralogs and the distribution of orthologs.
thus, paralogs in tgas are less divergent than dispersed paralogs.
although the global distributions of these two sets of paralogs are not bimodal, the protein identities do not follow a normal distribution since the paralogs exhibiting high sequence conservation are found more frequently than their poorly conserved counterparts.
this feature is amplified in the case of tandem duplicated genes.
discussion
the sequence homology between tandem duplicated genes favors recombination events, followed by the deletion or deletion-fusion of some copies.
mutational events can also cause the disappearance of genes in tgas but more progressively.
this death of genes is compensated by the maintenance of some other copies and/or the creation of new gene copies to ensure the original gene function  <cit>  .
therefore, a certain number of tgas must conserve the trace of these phantom gene copies called pseudogenes or gene relics depending on their degree of degeneration  <cit> .
all the methods used so far to detect tgas in complete genomes were based on the search of intact gene copies that are homologous by sequence similarity and are organized in tandem repeats  <cit> .
therefore, the proportion of tgas containing degenerated gene copies was still unknown.
we developed a novel computational method to predict all tgas, including the ones with gene relics, in eukaryotic genomes.
this methodological approach is relevant when we know that human and other eukaryotic genomes contain thousands of pseudogenes  <cit> .
in the saccharomyces cerevisiae genome, the pseudogene number was reported by different sources and a compilation of these data, giving  <dig> pseudogenes, was presented by lafontaine et al.
<cit> .
then, the pseudogene frequency in the yeast genome is approximately of one pseudogene/ <dig> cdss .
our method does not perform pairwise blastp comparisons of gene sequences to detect similarities, but compares each coding sequence with the dna sequences of its two surrounding chromosomal regions using the tblastn program.
the detection of sequence similarity between a cds and an adjacent non-coding region reveals the putative presence of a cds-relic tandem repeat.
in order to verify the existence of a relic in such repeats, a manual curation was performed after tga extraction.
our method is efficient for species that have a compact genome such as prokaryotes and unicellular eukaryotes.
its adaptation to multicellular eukaryotic species should take into account the physical characteristics of their genomes.
in fact, the identification of tandem repeated gene copies using tblastn could be difficult with large genomes that feature much longer intergenic regions and coding sequences with frequent and long introns especially if they are subjected to alternative splicing.
moreover, short dna repeats and notably minisatellites are more frequent in complex genomes especially in intergenic sequences .
but, these repeated sequences are mainly located in intergenic regions and will not represent an issue as our method detects minisatellites only within the dna sequence of tandem repeated genes.
despite these limitations, we proceeded with a first evaluation of the proposed method on the chromosome  <dig> of the plant arabidopsis thaliana.
<dig> tgas and  <dig> isolated cdss potentially in tandem with a gene relic were detected by using the same parameters than those used for yeast genomes.
although no manual curation was performed on these data, they agree with the results previously obtained predicting  <dig> tgas  or  <dig> tgas  on the a. thaliana chromosome  <dig>  <cit> .
if confirmed after manual curation , these first results illustrate the interest of the method for the identification of tgas including the "one gene and one gene relic" arrays.
we applied our method to nine annotated complete genomes of hemiascomycete yeasts.
results show that, on an average, 2% of cdss are included in tgas and 11% of these tgas contain a gene relic.
the percentage of tandem arrayed genes in the yeast genomes is lower than the one calculated for other eukaryotic species.
for two plant genomes,  <dig> % and  <dig> % of genes belong to tgas having  <dig> or  <dig> spacer gene and this value rises to  <dig> % if  <dig> spacers are allowed  <cit> .
variation from  <dig> % to  <dig> %  was reported in the case of  <dig> vertebrate species  <cit> .
the total number of tgas had already been estimated for five yeast genomes by another method based on protein families and authorizing 0- <dig> spacers  <cit> .
among these five genomes, only those of s. cerevisiae, c. glabrata, k. lactis and y. lipolytica are exploitable for a comparative analysis of tga data since dujon et al.
<cit>  used another version of the d. hansenii genome.
since  <dig>  this genome was reassembled and its re-annotation showed that the new sequence is quite different compared to the preceding version, notably with regard to the repeated regions .
on the  <dig> genes constituting tandem arrays  in the four yeast species, 47%  were detected by both methods, 28%  were specifically identified by our method and 25%  were found only by the dujon et al.
<cit>  method.
the detailed analysis of the non-common genes highlights the specificities of the two methodological approaches.
some tgas are not found by our method for two main raisons:  more than one spacer gene is present between two tandem duplicated genes , and  the distance between two tandem genes is longer than the average .
concerning the method used by dujon et al.
<cit> , three points explain the absence of a certain number of tgas:  the presence of gene relics in tandem repeats ,  the presence of minisatellites in protein sequences , and  genes of the same tga belonging to different protein families  and  are sometimes associated).
in conclusion, each method has its weaknesses and strengths.
the main advantages of the method we propose are that we have no requirement in terms of protein assignment to families and our ability to detect dead gene copies and minisatellites in tgas.
d. hansenii features the highest proportion  of tandem repeated genes among the nine yeasts analyzed.
the mechanism of tandem gene duplication must be particularly efficient in this cryo- and osmotolerant marine species, probably in response to environmental constraints.
the majority of tgas in yeast genomes  are the size of two cdss and cds orientation is mainly direct .
these characteristics are also observed in other species.
the largest tgas are found in c. glabrata  and in d. hansenii .
strong selective pressure may have intervened to maintain the size of these large tgas, despite the fact that they represent selected targets for chromosomal rearrangements via recombination events.
tgas comprising gene relics were identified in the nine yeast genomes, either as 1cds-relic  or ncdss-relic tgas.
their frequency, equal to  <dig> %, is approximately identical to that of 3cdss-tgas .
this significant figure confirms that an important fraction of tgas have genes that have not evolved in a concerted fashion but comply with the birth-and-death mechanism of evolution.
in fact, tgas are thought to evolve according to two major models  <cit> .
concerted evolution homogenizes the duplicated gene sequences to preserve the gene function and serves to increase gene dosage.
in contrast, in the birth-and-death evolutionary model, sequence divergence within a tga favors the emergence of new functions but also gene inactivation or disappearance.
this second model is consistent with the role of tga formation in rapid adaptation to environmental necessities.
interestingly and similarly, the results of our functional analysis  show that biological processes related to cell-environment relationships  are overrepresented for genes in tgas as compared with other genes.
the step of manual curation was pertinent since it enabled the authors to:  eliminate 49% of false positive cdss displaying a "relic" tag ,  retrieve 25% of tagged cdss to create new tgas or complete pre-existent tgas and  eliminate  <dig> % of false positive tgas containing cdss with internal minisatellites.
applied to genomes having a total number of genes higher than the yeast genomes, our method would probably produce a number of tagged cdss so great that their manual verification would become unachievable.
in this case, a modification of the threshold value of ftb score used to extract tgas could be envisaged to reduce the number of false positive cdss.
for the global analysis of all nine yeast genomes, an increase of this parameter from  <dig> to  <dig> drastically decreased the background noise , without greatly modifying the number of detected tgas .
the length of the sequences flanking a cds, determined as a number of times the length of the cds  and used as a target for the similarity search, is another variable parameter.
but its modification must be limited in a given species since it depends on the size of the coding genes and on overall gene density.
the analysis of the ftb score distribution in tgps was performed to evaluate more precisely the general evolutionary process of tgas.
a bimodal repartition is expected as one part of tgas is supposed to have undergone neofunctionalization or pseudogenization, the other part representing sequence-conserved tgas.
the scatter plot given in the results  does not show a profile characteristic of a bimodal distribution.
this observation could mean that tgas follow a continuous process of degeneration.
on the other hand, we compared protein identity distributions between different sets of homologous gene pairs.
results show that paralogs in tgas have, on an average, amino acid sequences better conserved than dispersed paralogs, but are more divergent than orthologs.
gene conversion is a plausible mechanism for sequence homogenization among many tandem gene repeats and it is reported that its frequency is lower between separated gene copies  <cit> .
another alternative is that tandem duplicate genes supposedly arise from more recent events of gene duplication than dispersed duplicate genes.
the mechanism of tandem gene duplication usually tends to respond more rapidly to environmental stimuli.
it has recently been reported that this mechanism has generated ~80% of the new genes specific to drosophila species  <cit> .
for nascent gene copies shared by multiple drosophila species, 44% and 34% are dispersed and tandem repeated duplicates, respectively.
moreover, zhou et al.
<cit>  have found that tandem duplicate genes have on an average younger ages but lower survivorships as against dispersed genes.
along the same lines, leh-louis et al.
<cit>  observed that the largest tga  in s. cerevisiae ends with a relic and its size varies extensively among different strains of the same species.
CONCLUSIONS
in many comparative genomics studies, large-scale detection of tandem duplicated genes is a necessary step to tackle basic questions about gene duplication, notably the mechanisms of tga formation and evolution.
first, the extension of tgas, such as ribosomal dna gene repeats, is mainly explained by mitotic or meiotic events of unequal sister-chromatid crossover  <cit> .
but there is no convincing mechanism to explain the transition from one original copy to two tandem repeated copies.
second, chimeric or truncated genes are often observed at the edges of segmental duplications  <cit>  and retroposition-mediated single gene duplications  <cit> , although their presence at the borders of tgas is not reported.
gene limits could be recognized by the mechanism of tandem gene duplication.
third, sequence divergence frequently observed between genes sharing the same tandem array suggests that selective pressures are applied to such areas, favoring the emergence of new functions.
tgas would be breeding grounds for new genes.
we will address these interesting questions with a detailed analysis of the tga catalog produced by our computational prediction method from hemiascomycete yeast genomes.
different methods were used to predict in a genome the complete set of tgas.
nevertheless, the novelty and advantage of our method compared with existing methods lies in its detection of additional tgas containing degenerated paralogous gene copies.
identification of these nonfunctional copies of functional genes is a crucial stage to determine the borders of the repeated unit and retrace the evolutionary history of tandem arrayed paralogs.
therefore, the size of tandem repeated units in all yeast genomes analyzed will be correctly determined and chimeric or truncated genes will be searched at the extremities of these units.
we will also identify the possible presence of pertinent sequence elements flanking tgas  in order to define mechanism of tga formation.
finally, multiple sequence alignments will be used to establish phylogenies and calculate nucleotide substitution rates in both silent and non-silent positions in order to date the successive events that have occurred at tandem repeated loci and identify the evolutionary forces .

 all genomes sequenced so far feature clusters of contiguous repeated genes that must derive from a common ancestral gene after successive duplication events. different methods were used to achieve a systematic characterization of tgas in eukaryotic genomes. all these methods derive from those primarily used to identify any duplicate genes in complete genomes and take into account supplementary data concerning the chromosomal location of the detected duplicate genes. for the genome of arabidopsis thaliana, the blastp program of sequence similarity search was performed on each chromosome against itself. then, the blastp results were indexed by their chromosomal physical locations to screen tgas, allowing from to spacers, i.e. unrelated genes that separate two tandem duplicated copies. for several genomes of vertebrates, a three-step method was applied. an all-against-all blastp sequence comparison was first carried out on all protein predictions of all studied species with a view to establishing similarities. on the basis of protein similarity matrices, genes were assigned to families using markov clustering algorithms. genes were defined as tgas if they belonged to the same family and were either physically adjacent or separated by a maximum number of ten intervening spacer genes. alternative versions of this method using either blast and smith-waterman algorithms or another clustering method based on the single-linkage criterion were applied to yeast and plant genomes. here, we developed an original in silico method to identify in a compact genome the complete set of tgas, including those that contain degenerated paralogous copies. these nonfunctional copies of functional genes are called pseudogenes or gene relics. the term of pseudogene designates usually a dna segment that shows high similarity to a functional gene, but is inactive due to premature stop codons, indels or the loss of regulatory sequences. since nonfunctionality of pseudogenes is sometimes difficult to define, zheng and gerstein proposed a classification system of genes and pseudogenes. a "gene relic" is distinguished from a "pseudogene" by their degree of degeneration. gene relics have gone through so many mutations of type missense, nonsense or frameshift that do not constitute an open reading frame. pseudogenes are more similar to an orf. they are obviously easier to detect than gene relics. as the distinction is not easy and doesn't affect the results of our method, in this paper, we will use the term "gene relic" to refer to all nonfunctional gene copies present in tgas including pseudogenes. though tgas have been systematically analyzed in some genomes, the frequency of tgas containing gene relics remains unknown. identification of these residual duplicated copies is required in order to correctly delimit the tandem repeated unit and retrace the evolutionary history of tgas. whereas other existing methods used to detect tgas take 0- spacers into account, our method is aimed at tgas without spacer genes. in few cases, one spacer is authorized within a tga. from an evolutionary point of view, the structures without intervening genes between successive paralogs should be the most recent, since they display no chromosomal rearrangement such as insertion of genes. another distinctive feature of our method, as compared with other methods, is the incorporation of a final step of manual data curation minimizing the number of false positive tgas. we applied our method of analysis to the complete, assembled genome sequences of nine hemiascomycete yeasts in order to obtain a catalog of tgas covering a large phylum of phylogenetically related species. this set of data proved useful in retracing genome evolution and notably in determining whether tgas constitute chromosomal rearrangement hotspots for expansion and contraction of gene families. the detailed sequence analysis of the tga flanking regions could provide better knowledge of the mechanisms at work in the apparition of these particular tandem structures. furthermore, our tga detection method is a helpful tool for the genome annotation. in fact, it highlights sequence similarity information between some genes and their neighbors when they are included in a tga and helps to homogenize the annotation of these contiguous gene copies.  algorithm score calculation the flowchart given in figure describes the score calculation process that can be divided into three principal steps. step - from each coding sequence of a complete assembled genome, the corresponding protein sequence was compared with its upstream and downstream chromosomal regions using a tblastn search. the length of the surrounding dna sequences was three times longer than that of the cds considered. if the calculated length was below the minimal length of bp, the length retained was equal to lmin. the bit score was retained for each tblastn sequence alignment. these initial scores, four per cds considering its two flanking sequences and both dna strands, were called tb scores. when several high-scoring segment pairs were obtained between a given cds protein sequence and one of its flanking region, the total tb score was calculated as the sum of bit scores of all hsps that correspond to the same strand and do not overlap by more than 20%. step - four final scores, called ftb scores, were calculated for each cds from the tb scores of both strands of its two surrounding sequences. each tb score was first divided by a tb self-score to express it in percentage. this tb self-score was the tblastn bit score obtained when the protein sequence of the considered cds was compared with its own genomic sequence. its calculation also depended on the number and overlapping of hsps generated by the blast program. the ftb scores were then obtained by subtracting two tb scores expressed as a percentage corresponding to both complementary strands of the same surrounding region. step - a filter was necessary to reduce the high background score generated by the small proteins or low sequence complexity proteins. if tb self-score < and < ftb score < this filter was applied: filtered ftb score = ftb score - /4). tga extraction all cdss of a genome were examined, in the ascending order of their chromosomal coordinates, to select the cdss that have at least one ftb score equal to or greater than the threshold value of. to decide if a selected cds belongs to a tga, its own ftb scores were compared with those of its two adjacent cdss. the algorithm of score comparison determines the position of each cds within the tga. a tga is created when a selected cds occupies the "first position". as long as the cdss located downstream from this "first cds" occupy a "middle position", the tga is extended. but as soon as a next cds occupies the "last position", tga elongation comes to an end. when no directly adjacent cds fits exactly the criteria of a tandem arrayed gene, a "relic" tag was first attributed to the cds at position n. then, the n- and n+ cdss were analyzed, permitting the presence of one intervening spacer gene within a tga. the direct or opposite relative orientation of gene pairs in tgas was determined by comparing their corresponding ftb scores. minisatellite detection richard and dujon found, in the s. cerevisiae genome, protein-coding genes containing consecutive sequence repetitions, called minisatellites, whose repeat unit size ranges from bp to bp. these internal tandem repeats can cause problems during tga extraction, since some of them persist outside the coding sequence and can contribute to a ftb score ≥ moreover, in some cases, the chromosomal distance between two non-homologous genes containing minisatellites is so small that they can be related to the same tga. therefore, all cdss involved in a tga were submitted to the equicktandem and etandem programs of the emboss package to find tandem repeats in their dna sequences. equicktandem rapidly identifies potential repeat sizes whereas etandem searches genuine tandem repeats, calculates a consensus for the repeat block and takes gaps into account. the research of minisatellites and the "relic" tagging in the step of tga extraction are useful when performing the manual curation of tgas. this enables the researcher to eliminate false positive tgas due to short tandem repeats in gene sequences and to identify the tgas containing gene relics, respectively. implementation score calculation, tga extraction and minisatellite detection are the three automated steps of our algorithm and have been implemented in python version http://www.python.org/. the output file of the first step is a table of the ftb scores calculated for each cds of a given genome. from this table, another script extracts cdss organized in tandem arrays and then identifies among these cdss those containing minisatellites. data of this second script can be manually analyzed to eliminate the false positive tgas. scripts are freely available from the corresponding author who will make recommendations to users and inform them on improvements added to the computational program. application: identification of tgas in hemiascomycete yeast genomes databases we applied our method to nine completely sequenced genomes of hemiascomycete yeasts. the saccharomyces cerevisiae chromosome sequences and information on annotated genes were downloaded from saccharomyces genome database http://www.yeastgenome.org/. the eremothecium gossypii genome sequence and its corresponding annotations were taken from ashbya genome database http://agd.vital-it.ch/ashbya_gossypii/index.html/. génolevures website http://cbi.labri.fr/genolevures/ provided all the data relative to complete genome sequences of the species candida glabrata, debaryomyces hansenii, kluyveromyces lactis, kluyveromyces thermotolerans, saccharomyces kluyveri, yarrowia lipolytica and zygosaccharomyces rouxii. computation of all tgas in the nine yeast genomes we define a tga as a structure of contiguous paralogous gene copies, which are either functional or degenerated copies, allowing for the presence of one heterologous gene inserted between the two homologous copies. in accordance with this definition, we developed an in silico method to detect such tgas in complete eukaryotic genomes. this method was applied to nine hemiascomycete yeast genomes. tgas comprising cdss were identified in this set of genomic data, which represents 2% of cdss involved in tgas in relation to the total number of cdss present in these nine genomes. this proportion is independent of the phylogenetic position of species and is not higher in the post-wgd species s. cerevisiae and c. glabrata. interestingly, the d. hansenii genome shows a percentage of cdss in tgas twice higher than the other species. another remarkable result is the percentage of tgas that include a duplicated gene relic. on an average 6% of yeast genes contain intron sequences, generally only one intron per gene. among all cdss that belong to tgas, % have an intron. in half of the tgas concerned, an intron was not present in all the duplicated copies. the physical distribution of tgas is relatively homogeneous along the different chromosomes of each species. a first assessment of functional bias for genes in tandem arrays was based on gene ontology term annotation information. functions such as cellular homeostasis, cell wall organization and biogenesis, conjugation and response to stress, are overrepresented in tgas. the proportion of genes involved in tgas is very low in the following functional classes: transcription, translation, rna metabolic process and ribosome biogenesis and assembly. distributions of tga sizes and cds orientations in tgas tgas were classified according to the number of cdss they contain. among the nine yeast genomes, the size of tgas ranged from one cds to cdss. tgas belonging to the 1cds-relic class consist of one cds and one gene relic and represents ~10% of the total number of tgas, a proportion equivalent to that of the 3cdss-tga class. the majority of tgas comprise two cds copies and the percentage in four copies falls to. large tgas of six and eight cdss are concentrated in c. glabrata, but the largest one containing cdss is in d. hansenii. the latter, located on the chromosome e of d. hansenii, has been manually reconstructed since it was disrupted times by heterologous genes. in the sequenced strain of s. cerevisiae, s288c, the tga size does not exceed five cdss and the 1cds-relic class of tgas is absent. nevertheless, three tgas made up of more than one cds plus one relic are present in this reference strain. cdss in tgas are principally in a direct orientation with approximately the same proportion of sense and antisense orientations. in c. glabrata tgas, the antisense orientation is represented times more than the sense orientation, although the number of cdss on the minus strand and on the plus strand is identical. tgas consisting of two cdss oppositely oriented represent % of total tgas. the low frequency of mixed tgas is in correlation with the low percentage of tgas containing at least cdss and of which at least two copies have a convergent or divergent orientation, this being the less frequent orientation of a cds pair. data curation the originality of our method of tgas detection lies in the possibility to identify tgas containing degenerated gene copies. from the nine yeast genomes analyzed, two different sets of cdss, possibly close to a gene relic, appeared during the tga extraction step and received a relic tag: isolated cdss with at least one ftb score ≥ and cdss, located on one extremity of a tga comprising at least two cds, with two ftb scores ≥. 15% and 22% of these two respective sets of tagged cdss were first retrieved by an automated curation step to create new tgas. after this procedure, a manual data curation produced supplementary tgas or some tgas recomposed from 24% and 48% of the two respective sets of tagged cdss. no false positive cds was found among the tagged cdss included in a tga, whereas approximately half the isolated cdss were eliminated. finally, cdss were located near a homologous gene relic: constitute the class of tgas that contain just one cds and belong to larger tgas. a possible source of false positive tgas is the presence of minisatellites in the coding sequences. among the cdss implicated in a tga, have internal tandem repeats. the manual examination of these suspicious cdss revealed that % of the total number of tgas before curation were false positives. nevertheless, it was difficult in some cases to decide whether the similarity between contiguous cdss is partially or totally due to minisatellites. this problem occurred when long stretches of tandem repeats covered a large part of the cdss. therefore, the percentage of false positives is probably slightly underestimated. distributions of ftb scores the degree of gene conservation in a tga can be estimated by comparing blast bit scores between two genes. ftb scores were calculated from the result of tblastn sequence alignments. two ftb scores ≥ were obtained per gene pairs in a tga. two additional ftb scores characterize both chromosomal regions surrounding each tga. the tga flanking regions can contain cdss, but these coding sequences have no homology with members of the tga. for each pair of tandem repeated cdss, except those manually recomposed, the ftb score s was compared with the ftb score s. these two scores are mostly equal or equivalent. in % of cases, the difference between both scores is > and is due principally to the size difference between both genes of a tgp. the comparison between the ftb scores s and s shows that in 93% of cases at least one of these two scores is equal to. few tgas have one score, s or s greater than they correspond to tgas that start or end with a homologous gene relic. therefore, they belong to the ncdss-relic class of tgas. one of the seven tgas in this class is not represented here because it was corrected manually. evolution of tgas in comparison with the one of the other duplicated genes distribution of amino acid sequence identities between pairs of homologous proteins was computed to evaluate the divergence between paralogous and orthologous gene copies. orthologous proteins show monomodal distributions and average identities comprised between 48-58%. they represent the most sequence-conserved homologous proteins. the distribution of tandem paralogs is intermediate between the distribution of other paralogs and the distribution of orthologs. thus, paralogs in tgas are less divergent than dispersed paralogs. although the global distributions of these two sets of paralogs are not bimodal, the protein identities do not follow a normal distribution since the paralogs exhibiting high sequence conservation are found more frequently than their poorly conserved counterparts. this feature is amplified in the case of tandem duplicated genes. discussion the sequence homology between tandem duplicated genes favors recombination events, followed by the deletion or deletion-fusion of some copies. mutational events can also cause the disappearance of genes in tgas but more progressively. this death of genes is compensated by the maintenance of some other copies and/or the creation of new gene copies to ensure the original gene function. therefore, a certain number of tgas must conserve the trace of these phantom gene copies called pseudogenes or gene relics depending on their degree of degeneration. all the methods used so far to detect tgas in complete genomes were based on the search of intact gene copies that are homologous by sequence similarity and are organized in tandem repeats. therefore, the proportion of tgas containing degenerated gene copies was still unknown. we developed a novel computational method to predict all tgas, including the ones with gene relics, in eukaryotic genomes. this methodological approach is relevant when we know that human and other eukaryotic genomes contain thousands of pseudogenes. in the saccharomyces cerevisiae genome, the pseudogene number was reported by different sources and a compilation of these data, giving pseudogenes, was presented by lafontaine et al.. then, the pseudogene frequency in the yeast genome is approximately of one pseudogene/ cdss. our method does not perform pairwise blastp comparisons of gene sequences to detect similarities, but compares each coding sequence with the dna sequences of its two surrounding chromosomal regions using the tblastn program. the detection of sequence similarity between a cds and an adjacent non-coding region reveals the putative presence of a cds-relic tandem repeat. in order to verify the existence of a relic in such repeats, a manual curation was performed after tga extraction. our method is efficient for species that have a compact genome such as prokaryotes and unicellular eukaryotes. its adaptation to multicellular eukaryotic species should take into account the physical characteristics of their genomes. in fact, the identification of tandem repeated gene copies using tblastn could be difficult with large genomes that feature much longer intergenic regions and coding sequences with frequent and long introns especially if they are subjected to alternative splicing. moreover, short dna repeats and notably minisatellites are more frequent in complex genomes especially in intergenic sequences. but, these repeated sequences are mainly located in intergenic regions and will not represent an issue as our method detects minisatellites only within the dna sequence of tandem repeated genes. despite these limitations, we proceeded with a first evaluation of the proposed method on the chromosome of the plant arabidopsis thaliana. tgas and isolated cdss potentially in tandem with a gene relic were detected by using the same parameters than those used for yeast genomes. although no manual curation was performed on these data, they agree with the results previously obtained predicting tgas or tgas on the a. thaliana chromosome. if confirmed after manual curation, these first results illustrate the interest of the method for the identification of tgas including the "one gene and one gene relic" arrays. we applied our method to nine annotated complete genomes of hemiascomycete yeasts. results show that, on an average, 2% of cdss are included in tgas and 11% of these tgas contain a gene relic. the percentage of tandem arrayed genes in the yeast genomes is lower than the one calculated for other eukaryotic species. for two plant genomes, % and % of genes belong to tgas having or spacer gene and this value rises to % if spacers are allowed. variation from % to % was reported in the case of vertebrate species. the total number of tgas had already been estimated for five yeast genomes by another method based on protein families and authorizing 0- spacers. among these five genomes, only those of s. cerevisiae, c. glabrata, k. lactis and y. lipolytica are exploitable for a comparative analysis of tga data since dujon et al. used another version of the d. hansenii genome. since this genome was reassembled and its re-annotation showed that the new sequence is quite different compared to the preceding version, notably with regard to the repeated regions. on the genes constituting tandem arrays in the four yeast species, 47% were detected by both methods, 28% were specifically identified by our method and 25% were found only by the dujon et al. method. the detailed analysis of the non-common genes highlights the specificities of the two methodological approaches. some tgas are not found by our method for two main raisons: more than one spacer gene is present between two tandem duplicated genes, and the distance between two tandem genes is longer than the average. concerning the method used by dujon et al., three points explain the absence of a certain number of tgas: the presence of gene relics in tandem repeats, the presence of minisatellites in protein sequences, and genes of the same tga belonging to different protein families and are sometimes associated). in conclusion, each method has its weaknesses and strengths. the main advantages of the method we propose are that we have no requirement in terms of protein assignment to families and our ability to detect dead gene copies and minisatellites in tgas. d. hansenii features the highest proportion of tandem repeated genes among the nine yeasts analyzed. the mechanism of tandem gene duplication must be particularly efficient in this cryo- and osmotolerant marine species, probably in response to environmental constraints. the majority of tgas in yeast genomes are the size of two cdss and cds orientation is mainly direct. these characteristics are also observed in other species. the largest tgas are found in c. glabrata and in d. hansenii. strong selective pressure may have intervened to maintain the size of these large tgas, despite the fact that they represent selected targets for chromosomal rearrangements via recombination events. tgas comprising gene relics were identified in the nine yeast genomes, either as 1cds-relic or ncdss-relic tgas. their frequency, equal to %, is approximately identical to that of 3cdss-tgas. this significant figure confirms that an important fraction of tgas have genes that have not evolved in a concerted fashion but comply with the birth-and-death mechanism of evolution. in fact, tgas are thought to evolve according to two major models. concerted evolution homogenizes the duplicated gene sequences to preserve the gene function and serves to increase gene dosage. in contrast, in the birth-and-death evolutionary model, sequence divergence within a tga favors the emergence of new functions but also gene inactivation or disappearance. this second model is consistent with the role of tga formation in rapid adaptation to environmental necessities. interestingly and similarly, the results of our functional analysis show that biological processes related to cell-environment relationships are overrepresented for genes in tgas as compared with other genes. the step of manual curation was pertinent since it enabled the authors to: eliminate 49% of false positive cdss displaying a "relic" tag, retrieve 25% of tagged cdss to create new tgas or complete pre-existent tgas and eliminate % of false positive tgas containing cdss with internal minisatellites. applied to genomes having a total number of genes higher than the yeast genomes, our method would probably produce a number of tagged cdss so great that their manual verification would become unachievable. in this case, a modification of the threshold value of ftb score used to extract tgas could be envisaged to reduce the number of false positive cdss. for the global analysis of all nine yeast genomes, an increase of this parameter from to drastically decreased the background noise, without greatly modifying the number of detected tgas. the length of the sequences flanking a cds, determined as a number of times the length of the cds and used as a target for the similarity search, is another variable parameter. but its modification must be limited in a given species since it depends on the size of the coding genes and on overall gene density. the analysis of the ftb score distribution in tgps was performed to evaluate more precisely the general evolutionary process of tgas. a bimodal repartition is expected as one part of tgas is supposed to have undergone neofunctionalization or pseudogenization, the other part representing sequence-conserved tgas. the scatter plot given in the results does not show a profile characteristic of a bimodal distribution. this observation could mean that tgas follow a continuous process of degeneration. on the other hand, we compared protein identity distributions between different sets of homologous gene pairs. results show that paralogs in tgas have, on an average, amino acid sequences better conserved than dispersed paralogs, but are more divergent than orthologs. gene conversion is a plausible mechanism for sequence homogenization among many tandem gene repeats and it is reported that its frequency is lower between separated gene copies. another alternative is that tandem duplicate genes supposedly arise from more recent events of gene duplication than dispersed duplicate genes. the mechanism of tandem gene duplication usually tends to respond more rapidly to environmental stimuli. it has recently been reported that this mechanism has generated ~80% of the new genes specific to drosophila species. for nascent gene copies shared by multiple drosophila species, 44% and 34% are dispersed and tandem repeated duplicates, respectively. moreover, zhou et al. have found that tandem duplicate genes have on an average younger ages but lower survivorships as against dispersed genes. along the same lines, leh-louis et al. observed that the largest tga in s. cerevisiae ends with a relic and its size varies extensively among different strains of the same species.  in many comparative genomics studies, large-scale detection of tandem duplicated genes is a necessary step to tackle basic questions about gene duplication, notably the mechanisms of tga formation and evolution. first, the extension of tgas, such as ribosomal dna gene repeats, is mainly explained by mitotic or meiotic events of unequal sister-chromatid crossover. but there is no convincing mechanism to explain the transition from one original copy to two tandem repeated copies. second, chimeric or truncated genes are often observed at the edges of segmental duplications and retroposition-mediated single gene duplications, although their presence at the borders of tgas is not reported. gene limits could be recognized by the mechanism of tandem gene duplication. third, sequence divergence frequently observed between genes sharing the same tandem array suggests that selective pressures are applied to such areas, favoring the emergence of new functions. tgas would be breeding grounds for new genes. we will address these interesting questions with a detailed analysis of the tga catalog produced by our computational prediction method from hemiascomycete yeast genomes. different methods were used to predict in a genome the complete set of tgas. nevertheless, the novelty and advantage of our method compared with existing methods lies in its detection of additional tgas containing degenerated paralogous gene copies. identification of these nonfunctional copies of functional genes is a crucial stage to determine the borders of the repeated unit and retrace the evolutionary history of tandem arrayed paralogs. therefore, the size of tandem repeated units in all yeast genomes analyzed will be correctly determined and chimeric or truncated genes will be searched at the extremities of these units. we will also identify the possible presence of pertinent sequence elements flanking tgas in order to define mechanism of tga formation. finally, multiple sequence alignments will be used to establish phylogenies and calculate nucleotide substitution rates in both silent and non-silent positions in order to date the successive events that have occurred at tandem repeated loci and identify the evolutionary forces. 
the originality of this method lies in the search of protein sequence similarities in the vicinity of each coding sequence, which allows the prediction of tandem duplicated gene copies independently of their functionality. the frequency of tgas with degenerated gene copies means that a significant fraction of tandem duplicated genes follows the birth-and-death model of evolution. the method reported here is a useful computational tool to provide a database of tgas composed of functional or nonfunctional gene copies. this paper describes an efficient in silico method for detecting tandem gene arrays in fully sequenced and compact genomes such as those of prokaryotes or unicellular eukaryotes. notably, a detailed study of the tga catalog will make it possible to tackle the fundamental questions of the origin and evolution of tandem gene clusters. applied to nine hemiascomycete yeast genomes, this method predicts that 2% of the genes are involved in tgas and gene relics are present in 11% of tgas. a comparison of sequence identity distributions between sets of homologous gene pairs shows that the different copies of tandem arrayed paralogs are less divergent than copies of dispersed paralogs in yeast genomes.
 this paper describes an efficient in silico method for detecting tandem gene arrays in fully sequenced and compact genomes such as those of prokaryotes or unicellular eukaryotes. the originality of this method lies in the search of protein sequence similarities in the vicinity of each coding sequence, which allows the prediction of tandem duplicated gene copies independently of their functionality.  applied to nine hemiascomycete yeast genomes, this method predicts that 2% of the genes are involved in tgas and gene relics are present in 11% of tgas. the frequency of tgas with degenerated gene copies means that a significant fraction of tandem duplicated genes follows the birth-and-death model of evolution. a comparison of sequence identity distributions between sets of homologous gene pairs shows that the different copies of tandem arrayed paralogs are less divergent than copies of dispersed paralogs in yeast genomes. it suggests that paralogs included in tandem structures are more recent or more subject to the gene conversion mechanism than other paralogs.  the method reported here is a useful computational tool to provide a database of tgas composed of functional or nonfunctional gene copies. such a database has obvious applications in the fields of structural and comparative genomics. notably, a detailed study of the tga catalog will make it possible to tackle the fundamental questions of the origin and evolution of tandem gene clusters. 