signature genes are genes that are unique to a certain taxonomic clade , and are common throughout all its major subclades .
the plausible evolutionary explanation for such a phylogenetic distribution is that the gene was invented in the ancestral lineage , and constituted an important innovation that possibly allowed the clade to radiate .
the significance of signature genes in biological research is both functional and taxonomic ( 1 ) .
signature genes contain a wealth of functional signals that are related to clade - specific processes , many of which remain to be described . furthermore , they hold a strong evolutionary signal that can be used to phylogenetically characterize a set of sequences , such as a metagenomics sample .
the recent breakthroughs in nucleotide sequencing ( 2 ) disclose a wealth of environmental niches , each harboring an abundance of undiscovered ( microbial ) life . as the metagenomic sequencing of such niches accelerates ( 35 ) , one of the first challenges lies in the taxonomic characterization of the contributing organisms . traditionally , sequence analyses are the method of choice in taxonomy , and the first approaches to characterize metagenomic data on the basis of sequence have recently been seeing the light ( 69 ) .
signature genes are based on gene content , an intermediate between genotype and phenotype ( 10,11 ) that gives a view on phylogeny that is complementary to sequence - based analyses ( 12 ) .
for example , using a prototype of our new signature gene method ( 13 ) , we showed that the anaerobic ammonium oxidizing bacterium kuenenia stuttgartiensis is closely related to the chlamydiae , a finding that independently supported the traditional phylogenomic analysis based on a superalignment of 49 proteins . in the current article , we introduce signature , an interactive web server that allows a user to identify signature genes in a set of query sequences .
the server first assigns each sequence to one of the orthologous groups from the string 7.0 database ( 14 ) using a sequence similarity search .
the phylogenetic distribution of this orthologous group throughout the tree of life is then assessed to determine if the sequence is a signature gene .
the server produces a list of taxonomic clades that share signature genes with the set of query sequences , a coverage score for each signature in that clade , and an insightful image of the tree of life , in which the clades are color coded based on the number of signature genes present .
this allows the user to quickly see from which part(s ) of the taxonomy the query sequences likely originate . using 1-fold and k - fold cross - validation analyses we confirmed that 93% of all signature genes were re - assigned to their correct clade .
the tool uses mrs ( 15 ) , a fast data retrieval system that also allows for blast searches .
signature currently assigns 2000 unknown protein sequences to orthologous groups in about 10 h , and in 10 s if the sequences occur in the database .
the first is a protein sequence database containing the proteomes of 373 completely sequenced organisms , in which every protein may or may not be assigned to an orthologous group of proteins ( og ) .
the database presently incorporated in signature is string version 7.0 that contains 43 577 cogs , kogs and nogs ( 14 ) .
the second type of information used by signature is a reference tree of life that defines the evolutionary relationships between the species .
, signature provides either the tree of life used in string 7.0 ( consistent with the sequence database ) , or a recently published phylogenomic tree based on a superalignment of 31 universal protein families ( 16 ) .
if the selected tree of life includes bootstrap values , the user can choose to set a bootstrap threshold , so that only the reliable nodes will be considered and the nodes with lower bootstrap value will be collapsed to form a multifurcating branch .
typically , a user will have a set of sequences obtained from an unknown organism or environment and wants to know to which taxonomic clade(s ) the sample belongs .
alternatively , the user will want to know whether a protein sequence has a signature status in any clade , and may thus represent a process particular for that clade . with either of these questions
, the user will go to www.cmbi.ru.nl/signature , enter the amino acid sequences in the input field ( in fasta format ) and click 
go. signature stores the input sequences and the selected options for the blast ( 17 ) search and the og assignment , and then starts by assigning each input sequence to an orthologous group .
if , by md5 checksum and a subsequent sequence identity check , the query sequence is identical to one of the proteins already in the database , it is directly assigned to the corresponding og(s ) .
otherwise , the sequence is assigned according to a cognitor - like rule ( 18 ) if the majority of the top n blast hits belong to the same og ( this option can be adjusted ) .
note that a query sequence will be assigned to multiple ogs if they occur as non - overlapping regions ( the maximum overlap between two regions can be adjusted , see figure 1 ) .
the blast searches can be time - limiting , depending on the number and length of the query sequences .
while running , signature displays an estimate of the duration until the search is finished , based on the running times of searches with a comparable size that were carried out previously .
it is always safe to refresh the page for the most up - to - date results .
signature currently identifies the orthologous groups in 2000 unknown protein sequences within 10 h ( depending on the length of the sequences ) , and in 10 s if the sequences occur in the database ( by checksum ) . as
the sequence similarity searches are the time - limiting step , we are presently extending the tool with a much faster og assignment algorithm , making it feasible to analyse metagenomics scale data sets and dna data sets in six translated frames in a limited time . 

figure 1.assignment of a query sequence to ogs using the default og assignment rule ( 3 of first 5 ) .
disparate regions are first parsed from all the significant blast hits ( max 30 ) if they overlap less than 35 amino acids ( all these parameters can be adjusted ) . then
, each region is assigned to an og : region_1 is not assigned as only two of the first five blast hits belong to the same og , while region_2 is assigned , as at least three of the first five blast hits ( in that region ) belong to og_b .
assignment of a query sequence to ogs using the default og assignment rule ( 3 of first 5 ) .
disparate regions are first parsed from all the significant blast hits ( max 30 ) if they overlap less than 35 amino acids ( all these parameters can be adjusted ) . then
, each region is assigned to an og : region_1 is not assigned as only two of the first five blast hits belong to the same og , while region_2 is assigned , as at least three of the first five blast hits ( in that region ) belong to og_b .
once the query sequences have been automatically assigned to the appropriate ogs , signature permits the user to review these assignments and manually change them if desired .
it is also possible to include additional ogs for the signature search in the second step .
if the user prefers to rely on a personal og assignment tool , the first step may be bypassed by leaving the initial input field empty ( see previous paragraph ) , and entering a list of cogs , kogs or nogs here . upon clicking 
go , signature will assess for each og whether it is a signature for any clade in the selected tree of life .
a signature og for a certain clade is defined as an og that occurs in every daughter lineage of that clade , but nowhere outside it [ figure 2 ( 1 ) ] . to minimize the number of false negatives ,
the basic signature definition does not require a signature og to be present in every species in the clade .
we have developed a nested coverage score that indicates the level of species coverage of a signature og , taking into account potential asymmetrical taxon sampling [ see the figure 2 caption for an example ( 1 ) ]
. using the coverage score cutoff , the user can direct signature to report only high - scoring signature ogs . 

figure 2.definition of signature ogs in a ( partially unresolved ) tree of life . for every species , presence ( 1 ) or absence ( 0 ) of three ogs is indicated . in this example , only og1 is a signature for clade a , as it is present in the daughter lineages a1 , a2 and a3 , but not in clade b. although og2 and og3 are present in more species within clade a , they are not a signature for clade a because og2 is not present in the daughter clade a1 and og3 is present outside of clade a. the coverage score of og1 as a signature for clade a is recursively calculated as the average of the scores in the daughter clades : [ ( 1/1 ) + ( 2/3 ) + ( 1/2)]/3 = 0.72 . definition of signature ogs in a ( partially unresolved ) tree of life . for every species , presence ( 1 ) or absence ( 0 ) of three ogs is indicated . in this example , only og1 is a signature for clade a , as it is present in the daughter lineages a1 , a2 and a3 , but not in clade b. although og2 and og3 are present in more species within clade a , they are not a signature for clade a because og2 is not present in the daughter clade a1 and og3 is present outside of clade a. the coverage score of og1 as a signature for clade a is recursively calculated as the average of the scores in the daughter clades : [ ( 1/1 ) + ( 2/3 ) + ( 1/2)]/3 = 0.72 . the first result of a signature search is a list of all the signature ogs contained in the set of query sequences , along with their coverage score . for each taxonomic clade with signature
ogs , signature calculates a log - likelihood significance that is based on the expected number of signature ogs for that clade ( see  significance score section below ) .
furthermore , signature generates an insightful image of the selected tree of life , where the internal clade branches are color coded based on their number of signature ogs ( shades of green ) , and the species , the terminal leaves in the tree , are color coded based on the cumulative number of signature ogs contained in all the ancestor clades they belong to ( shades of red ) .
thus , the user can easily assess which species are most closely related to the source of the query sequences ( figure 3 ) .
it should be noted that signature can also handle situations where the sequences are derived from several species .
figure 3.image of the tree of life that results from a signature search ( cropped to the archaeal clade ) .
the internal clade branches are color coded based on the number of signature ogs they share with the query ( shades of green ) , the terminal species are color coded based on the sum of the signature ogs of all their parent clades ( shades of red ) .
note that all species in one clade are colored in the same shade of red .
this means that an individual species does not necessarily contain all , or even any , of the signature genes assigned to its parental clades , especially if many signatures were found with a low coverage score .
sequences analysed are the ferroplasma acidarmanus type ii scaffolds obtained from dna sequencing of acid mine drainage [ see text ( 4 ) ] .
image of the tree of life that results from a signature search ( cropped to the archaeal clade ) .
the internal clade branches are color coded based on the number of signature ogs they share with the query ( shades of green ) , the terminal species are color coded based on the sum of the signature ogs of all their parent clades ( shades of red ) .
note that all species in one clade are colored in the same shade of red .
this means that an individual species does not necessarily contain all , or even any , of the signature genes assigned to its parental clades , especially if many signatures were found with a low coverage score .
sequences analysed are the ferroplasma acidarmanus type ii scaffolds obtained from dna sequencing of acid mine drainage [ see text ( 4 ) ] .
typically , a user will have a set of sequences obtained from an unknown organism or environment and wants to know to which taxonomic clade(s ) the sample belongs .
alternatively , the user will want to know whether a protein sequence has a signature status in any clade , and may thus represent a process particular for that clade . with either of these questions
, the user will go to www.cmbi.ru.nl/signature , enter the amino acid sequences in the input field ( in fasta format ) and click 
go. signature stores the input sequences and the selected options for the blast ( 17 ) search and the og assignment , and then starts by assigning each input sequence to an orthologous group .
if , by md5 checksum and a subsequent sequence identity check , the query sequence is identical to one of the proteins already in the database , it is directly assigned to the corresponding og(s ) .
otherwise , the sequence is assigned according to a cognitor - like rule ( 18 ) if the majority of the top n blast hits belong to the same og ( this option can be adjusted ) .
note that a query sequence will be assigned to multiple ogs if they occur as non - overlapping regions ( the maximum overlap between two regions can be adjusted , see figure 1 ) .
the blast searches can be time - limiting , depending on the number and length of the query sequences .
while running , signature displays an estimate of the duration until the search is finished , based on the running times of searches with a comparable size that were carried out previously .
it is always safe to refresh the page for the most up - to - date results .
signature currently identifies the orthologous groups in 2000 unknown protein sequences within 10 h ( depending on the length of the sequences ) , and in 10 s if the sequences occur in the database ( by checksum ) . as
the sequence similarity searches are the time - limiting step , we are presently extending the tool with a much faster og assignment algorithm , making it feasible to analyse metagenomics scale data sets and dna data sets in six translated frames in a limited time . 

figure 1.assignment of a query sequence to ogs using the default og assignment rule ( 3 of first 5 ) .
disparate regions are first parsed from all the significant blast hits ( max 30 ) if they overlap less than 35 amino acids ( all these parameters can be adjusted ) . then
, each region is assigned to an og : region_1 is not assigned as only two of the first five blast hits belong to the same og , while region_2 is assigned , as at least three of the first five blast hits ( in that region ) belong to og_b .
assignment of a query sequence to ogs using the default og assignment rule ( 3 of first 5 ) .
disparate regions are first parsed from all the significant blast hits ( max 30 ) if they overlap less than 35 amino acids ( all these parameters can be adjusted ) . then
, each region is assigned to an og : region_1 is not assigned as only two of the first five blast hits belong to the same og , while region_2 is assigned , as at least three of the first five blast hits ( in that region ) belong to og_b .
once the query sequences have been automatically assigned to the appropriate ogs , signature permits the user to review these assignments and manually change them if desired .
it is also possible to include additional ogs for the signature search in the second step .
if the user prefers to rely on a personal og assignment tool , the first step may be bypassed by leaving the initial input field empty ( see previous paragraph ) , and entering a list of cogs , kogs or nogs here . upon clicking 
go , signature will assess for each og whether it is a signature for any clade in the selected tree of life .
a signature og for a certain clade is defined as an og that occurs in every daughter lineage of that clade , but nowhere outside it [ figure 2 ( 1 ) ] . to minimize the number of false negatives ,
the basic signature definition does not require a signature og to be present in every species in the clade .
we have developed a nested coverage score that indicates the level of species coverage of a signature og , taking into account potential asymmetrical taxon sampling [ see the figure 2 caption for an example ( 1 ) ] . using the coverage score cutoff , the user can direct signature to report only high - scoring signature ogs . 

figure 2.definition of signature ogs in a ( partially unresolved ) tree of life . for every species , presence ( 1 ) or absence ( 0 ) of three ogs is indicated . in this example , only og1 is a signature for clade a , as it is present in the daughter lineages a1 , a2 and a3 , but not in clade b. although og2 and og3 are present in more species within clade a , they are not a signature for clade a because og2 is not present in the daughter clade a1 and og3 is present outside of clade a. the coverage score of og1 as a signature for clade a is recursively calculated as the average of the scores in the daughter clades : [ ( 1/1 ) + ( 2/3 ) + ( 1/2)]/3 = 0.72
. definition of signature ogs in a ( partially unresolved ) tree of life . for every species ,
presence ( 1 ) or absence ( 0 ) of three ogs is indicated . in this example , only og1 is a signature for clade a , as it is present in the daughter lineages a1 , a2 and a3 , but not in clade b. although og2 and og3 are present in more species within clade a , they are not a signature for clade a because og2 is not present in the daughter clade a1 and og3 is present outside of clade a. the coverage score of og1 as a signature for clade a is recursively calculated as the average of the scores in the daughter clades : [ ( 1/1 ) + ( 2/3 ) + ( 1/2)]/3 = 0.72 .
the first result of a signature search is a list of all the signature ogs contained in the set of query sequences , along with their coverage score . for each taxonomic clade with signature
ogs , signature calculates a log - likelihood significance that is based on the expected number of signature ogs for that clade ( see  significance score section below ) .
furthermore , signature generates an insightful image of the selected tree of life , where the internal clade branches are color coded based on their number of signature ogs ( shades of green ) , and the species , the terminal leaves in the tree , are color coded based on the cumulative number of signature ogs contained in all the ancestor clades they belong to ( shades of red ) .
thus , the user can easily assess which species are most closely related to the source of the query sequences ( figure 3 ) .
it should be noted that signature can also handle situations where the sequences are derived from several species .
figure 3.image of the tree of life that results from a signature search ( cropped to the archaeal clade ) .
the internal clade branches are color coded based on the number of signature ogs they share with the query ( shades of green ) , the terminal species are color coded based on the sum of the signature ogs of all their parent clades ( shades of red ) .
note that all species in one clade are colored in the same shade of red .
this means that an individual species does not necessarily contain all , or even any , of the signature genes assigned to its parental clades , especially if many signatures were found with a low coverage score .
sequences analysed are the ferroplasma acidarmanus type ii scaffolds obtained from dna sequencing of acid mine drainage [ see text ( 4 ) ] .
image of the tree of life that results from a signature search ( cropped to the archaeal clade ) .
the internal clade branches are color coded based on the number of signature ogs they share with the query ( shades of green ) , the terminal species are color coded based on the sum of the signature ogs of all their parent clades ( shades of red ) .
note that all species in one clade are colored in the same shade of red .
this means that an individual species does not necessarily contain all , or even any , of the signature genes assigned to its parental clades , especially if many signatures were found with a low coverage score .
sequences analysed are the ferroplasma acidarmanus type ii scaffolds obtained from dna sequencing of acid mine drainage [ see text ( 4 ) ] .
to assess the significance of finding a set of signature genes for a certain clade within a sample , signature provides a significance score for each clade on the output page .
this score is based on the number of expected signature ogs if all ogs were randomly distributed across the genomes . to do this , we composed 1000 randomized sets of genomes , taking care not to place the same og twice in one genome ( 1 ) , and calculated the expected number of signatures for each clade . in these randomizations ,
the number of signature ogs that we find for a clade depends on the number of daughter clades , the genome sizes of the species therein and on the genome sizes of the species outside the clade . to avoid having to compute the expected number of signature ogs by such randomizations at every signature search
we start by calculating the expected the number of ogs present at least once in every daughter lineage , but not in any species outside the clade ( equation 1 ) . 

( 1 ) 
 the product runs over all n daughter lineages d of the clade .
note that n = 2 in a completely resolved phylogeny , n  2 in a tree where nodes with low bootstrap support have been collapsed to a multifurcating branch .
ogsd is the total number of different ogs in all species in daughter d ( union ) , ogsout is the number of different ogs outside the clade , and ogstotal is the number of different ogs in the whole tree .
indeed , there is a good correlation between the analytically predicted e and the number of expected signature genes based on randomization ( figure 4 ) .
as can be observed in the regression equation , the randomized expected value ( x ) increases faster than the analytical e ( y ) , due to other factors such as variations in genome sizes .
thus , taking this correction factor of 0.8146 into account , we can calculate the expected number of signatures from the numbers of ogs present in the daughter lineages as 10 .
this value is based on the total number of different ogs in the whole tree , and can be scaled to the number of query sequences by multiplying it with queries / ogstotal . from this expected number of signature ogs ,
we calculate the observed / expected ratio and present the significance in the signature search output page as the log odds of drawing the observed number of signature ogs ( observed ) from the total set of ogs in the tree , given the number of query sequences ( queries , equation 2 ) . 

( 2 ) 
 figure 4.correlation between analytically calculated e ( equation 1 ) and the expected number of signature ogs based on 1000 randomized sets of genomes .
equation y = 0.8146x + 0.0526 is the formula for the linear regression line plotted in the figure .
( 16 ) tree of life as provided by signature , where clades with bootstrap values < 80% were collapsed ( 1 ) .
the outlier at ( 2.70 ; 7.06 ) are the bacteria , a clade with very low bootstrap support for its earliest branches , leading to 13 daughter lineages and an underestimation of e. for the rest of the clades in this plot , we did not find a correlation between the number of daughter lineages and e ( data not shown ) . 
 
correlation between analytically calculated e ( equation 1 ) and the expected number of signature ogs based on 1000 randomized sets of genomes .
equation y = 0.8146x + 0.0526 is the formula for the linear regression line plotted in the figure .
( 16 ) tree of life as provided by signature , where clades with bootstrap values < 80% were collapsed ( 1 ) .
the outlier at ( 2.70 ; 7.06 ) are the bacteria , a clade with very low bootstrap support for its earliest branches , leading to 13 daughter lineages and an underestimation of e. for the rest of the clades in this plot , we did not find a correlation between the number of daughter lineages and e ( data not shown ) .
we assessed the performance of signature by entering a set of sequences from the first metagenomic sample to be published , obtained from random shotgun sequencing of dna from a natural acidophilic biofilm ( 4 ) . from this sample
this data set contained 1956 sequences with an average length of 267 amino acids . the sequence - similarity search and
og assignment for these proteins took 9 h and 43 min with default parameters , detecting 974 unique ogs ( 1531 total ) in the data set . within 30 s , 196 of these 974 ogs were identified to be a signature for a clade in the default tree of life , highlighting thermoplasmatales as the closest relatives of the species in the metagenomic sample ( figure 3 ) .
signature is a web server that identifies signature ogs within a set of query sequences for any clade in a selected or uploaded tree of life .
a signature og is an orthologous group that is unique for a clade and is retained in all its daughter lineages ( figure 2 ) .
several public databases allow users to download strain- , species- or genus - specific genes , or sets of genes or proteins shared by a chosen set of species ( 1921 ) .
signature is unique in that it identifies the signatures in a set of query sequences , for any clade in an adjustable tree of life and places the query in a taxonomic context .
signature ogs can provide important new functional insights , as they carry out functions that may characterize the clade .
for example , if the sequences in a sample contain many signature genes for the thermoplasmatales and its subclades , then the sample is likely taken from a species in that clade .
based on this idea , signature places the signature ogs it discovers in a taxonomic context and produces an insightful image of the tree of life where the branches and leaves are color coded based on the number of signature genes associated to them ( figure 3 ) .
thus , the user can easily assess from which clade the sample was likely taken . to test the how well the signature method assigns species to the correct clade , we did cross - validation analyses ( signature provides the option of leaving species out of the analysis ) , in which we removed every species from the data set one by one , and identified the signatures among the ogs in the removed genome in a phylogeny that did not contain that genome ( 1 ) .
each of the removed proteins was either a signature og for one of the ancestral nodes of the removed species ( true positive , tp ) , a signature for another node ( false positive , fp ) or not a signature . in that case , the og could have been a signature in the situation where no species were excluded ( false negative , fn ) or not ( true negative , tn ) . using these values ,
we computed sensitivity [ tp/(tp + fn ) ; 77.6% ] , specificity [ tn/(tn + fp ) ; 98.8% ] , precision [ tp/(tp + fp ) ; 93.1% ] and accuracy ( true / all ; 95.6% ) of the method . removing 10% , 20% or 30% of the species ( k - fold cross - validation )
when interpreting the results of signature , it is important to realize the issue of horizontal gene transfers [ hgts ( 22 ) ] . if a signature gene for a certain clade gets transferred to a distantly related organism , it loses its initial signature status , because it will be found outside its taxon in the new situation .
an example of such a case might be og3 in figure 2 , which could have been transferred from a species in clade a to the rightmost species in clade b. in this case , after the hgt , og3 became a signature for the clade ab , as it is present in both its daughter lineages .
a solution for this is provided by the coverage score threshold . whereas og3 would have had a coverage score of [ ( 1/1 ) + ( 3/3 ) + ( 2/2)]/3 = 1.00 in clade a before the hgt event
, it now has a coverage score of  { [ ( 1/1 ) + + ( 3/3 ) + ( 2/2)]/3 } + { [ ( 0/2 ) + ( 1/2 ) ] /2 } 
thus , by using a ( high ) coverage score threshold , which is provided as an option in the signature search input form , the user can filter out signature ogs with a low coverage score that might be the result of hgt . nevertheless , even without using a coverage score threshold ,
we find only 1% false positives and a precision of 93% in the k - fold cross validation analyses ( above ) .
newly sequenced genomes might of course affect which genes are regarded as hgts , potentially leading to the loss or change of signatures .
if hgt would be widespread , genome sequencing could reach a point where all genes have been transferred outside of the taxon for which they were previously a signature . to assess the severity of this problem
, we tested the robustness of the set of signature genes against the addition of new genomes by randomly leaving out 10% , 20% or 30% of the species in the tree , and identifying the overlap between the signature ogs in the original set of species and in the subsampled tree .
this mimics the situation where up to 30% of the species are newly added to the current tree .
new signature genes : 2.0% , 5.1% and 5.9% , respectively [ average of 100 samples ( 1 ) ] . based on the results from these cross - validation experiments
, we do not expect to lose many of the current signature genes in an extended species set , and the taxonomic characterization of a query will be consistent . we will continue to add new genomes to the database as they become available . summarizing , signature is a user - friendly web server that facilitates the identification of signature ogs within a set of query sequences .
many parameters of the underlying method can be adjusted , providing a comprehensive platform for analyses related to clade - specific genes and processes , both in a functional and in a taxonomic context .
 signature genes are genes that are unique to a taxonomic clade and are common within it . 
 they contain a wealth of information about clade - specific processes and hold a strong evolutionary signal that can be used to phylogenetically characterize a set of sequences , such as a metagenomics sample . as signature genes 
 are based on gene content , they provide a means to assess the taxonomic origin of a sequence sample that is complementary to sequence - based analyses . here , we introduce signature ( http://www.cmbi.ru.nl/signature ) , a web server that identifies the signature genes in a set of query sequences , and therewith phylogenetically characterizes it . the server produces a list of taxonomic clades that share signature genes with the set of query sequences , along with an insightful image of the tree of life , in which the clades are color coded based on the number of signature genes present . 
 this allows the user to quickly see from which part(s ) of the taxonomy the query sequences likely originate . 
INTRODUCTION
DATA
A TYPICAL SIGNATURE SEARCH
Assigning query sequences to OGs
Identifying signature OGs in the tree of life
SIGNIFICANCE SCORE
PERFORMANCE
DISCUSSION