biology textbooks typically use phenotypic characters to describe clades , e.g. milk and hair for mammals . not only do these synapomorphies aid in phylogenetic inference , but they also record key innovations in the history of life , as exemplified by such famous clades as amniota and eutheria ( placental mammals ) .
a convincing molecular synapomorphy can often resolve a phylogeny that can not be unambiguously determined by more continuously varying characters ( 1 ) .
moreover , characteristic proteins ( 2 ) or regulatory sequences ( 3)i.e . sequences restricted to hypothesized clades  may represent landmark evolutionary events , such as the divergence of metazoans ( 2 ) or the origin of the bilaterian body plan ( 4 ) .
characteristic proteins are currently found , with some effort , by local alignment searching each gene in each genome of interest against all other genomes ( 2 ) , or by the use of predefined ortholog collections , such as the cogs database ( 57 ) .
more subtle synapomorphies , such as insertions or deletions are found serendipitously by researchers studying specific genes ( 8,9 ) , or more systematically by manual examination of multiple alignments ( 1013 ) . as more sequence becomes available
, there is a need and opportunity to further automate the search for molecular synapomorphies . in this paper
, we report on a synapomorphy search tool , called conserv , that takes as input two sets of genomes : those for the putative clade , or in - group , and those for an out - group .
the types of molecular synapomorphies we consider are as follows : ( i ) signature genes ubiquitous and unique to the clade , ( ii ) large insertions or deletions ( indels ) present only within the clade and ( iii ) sequence motifs well conserved within the clade but quite different outside the clade . type ( i ) is generally the rarest and type ( iii ) the most common , so these types are roughly ordered from strongest to weakest phylogenetic evidence .
each type includes both strong and weak examples , however , and sequence alone can not distinguish orthologs with novel function or structure , so we somewhat arbitrarily set the boundary between types ( i ) and ( iii ) using blast score thresholds that varied with the probe sequence length .
we do not consider other types of synapomorphies , such as gene fusions ( 14,15 ) or changes in gene order ( 16,17 ) .
they represent rare  possibly even unique  events that can potentially overcome the  ratio problem illustrated in figure 1 : clock - like evolutionary models are inherently limited in their ability to resolve a short internal branch followed by long branches to leaves ( 18 ) .
sequence characteristics with an extremely large number of character states , however , as is the case with signature genes or long indels , can theoretically still retain information ( 19 ) .
first it performs an all - against - all local alignment search , probing each protein - coding gene in each genome against every other genome .
second , it processes the resulting sets of hits to find the orthologous families most conserved over the in - group genomes .
third , it ranks the families by  synaptitude , which measures in - group pairwise similarity scores relative to in - to - out similarity scores .
all three types of molecular synapomorphies , ( i  iii ) above , show up near the top of the ranked list .
evaluation of the significance of the discovered synapomorphies remains a manual ( and poorly understood ) process , but this step can be facilitated by existing bioinformatics tools , such as local alignment search and multiple alignment programs ( 20,21 ) .
we emphasize that conserv is a search tool , and not a complete tool for inferring a phylogenetic tree or network .
conserv 's candidate synapomorphies can be used in conjunction with methods , such as parsimony ( 5,22 ) or dollo parsimony ( 22 ) to reconstruct a tree ; however , because conserved genes and indels that occur in only a single putative clade are rare , conserv is unlikely to find enough synapomorphies to reconstruct a large tree . in this case
, the program can provide confirmatory evidence and help evaluate trees suggested by other means .
notice that phylogeny by synapomorphies and parsimony is quite distinct from phylogeny by gene content ( 24,25 ) , as a single gene with the right distribution pattern may decide a branch , whereas such a gene counts no more heavily than one with a scattered distribution in gene - content methods .
finally , it is worth reiterating that conserv is a relatively simple tool , optimized for speed .
because conserv considers only highly conserved proteins and obvious homology ( at least 25% identity ) , and performs only pairwise alignments , it has no need for sophisticated sequence modeling techniques , such as hidden markov models ( hmms ) ( 25,26 ) .
when run on a putative eukaryotic clade , e.g. ecdysozoa , conserv will return voluminous results that are hard to evaluate , due to the sparse and uneven taxon sampling of eukaryotes .
thus , to demonstrate the utility of conserv , we ran the program over bacterial genomes in genbank ( 27 ) for about 30 choices of in - groups and out - groups , both putative clades and other sets of genomes . in this test , we discovered possible synapomorphies for higher - level clades uniting planctomycetes with chlamydiales and chloroflexi with cyanobacteria , as in figure 1 .
we also discovered strong evidence for placing symbiobacterium in firmicutes , and weaker evidence for placing the endosymbionts buchnera and wigglesworthia in enterobacteria .
the placement of symbiobacterium with firmicutes contradicts the current genbank taxonomy , which places it in actinobacteria , yet the discovered synapomorphies seem incontrovertible .
we also used conserv to explore surprising similarities between two groups that do not together form a clade :  - proteobacteria and spirochaetes .
finally , we used the tool to answer an intriguing peripheral question : what is the most conserved protein ?
given a set of n genomes  n = 30 is typical  and a sequence  window length k , conserv returns a list of families of orthologous protein sequences of the desired length ( k amino acid residues ) .
the number of families in the list can be specified by the user with a typical value being 1000 , but if conserv determines that there are not 1000 sufficiently conserved proteins in the set of genomes ( e.g. if the set of organisms includes reduced genomes or both eubacteria and archaea ) , then conserv will return a shorter list . the list is initially ranked from 
least conserved over the first m genomes in the set , where the user supplies m  n and thus defines the in - group and out - group . in order to find synapomorphies we further process the list as follows : ( i ) we rerank the list by synaptitude ; ( ii ) from each ortholog family
, we remove each sequence of very low pairwise similarity with all the in - group sequences and ( iii ) we use muscle ( 21 ) to compute multiple alignments . step ( ii )
is necessary because , in the case of a genome without a close ortholog , conserv will return a distant homolog or a completely unrelated sequence that could corrupt the multiple alignment . to remove sequences
, we use a log odds threshold that corresponds to about 2025% identity , conserv reports the gene distribution , with presence ( * ) or absence (  ) in each genome , as shown in the example in the supplementary data . it also reports a p - value , the likelihood that this distribution , or a better one , would arise by chance in a random model in which each genome independently chooses the gene with probability equal to its frequency over all n genomes .
for example , if n = 10 and a gene appears in three of the five in - group members and just one of the five out - group members , then the chance that it appears in any given genome is ( 4/10 ) = 0.4 and the chance that it does not appear is 0.6 .
the p - value is the probability that at least three in - group members , and at most one out - group member , contain the gene , or 
 [  ( 53)0.430.62+(54)0.440.61+(55)0.45 ]    [ ( 50)0.65  + ( 51)0.410.64]0.107 .
if the gene distribution indicates a signature gene , or if manual inspection of the multiple alignment shows an indel synapomorphy , we add another step : ( iv ) a blast search [ psi - blast ( 28 ) with default settings ] against all prokaryotic genomes in genbank , possibly followed by another multiple alignment , to check whether we have indeed discovered a synapomorphy of types ( i ) or ( ii ) . rather than find its own orthologs , conserv could , at least in principle , process the orthologs found by blast or an ortholog assembler ( 29 ) , or use predefined ortholog databases such as cogs ( 6,7,30 ) as in ( 5 ) .
conserv is much faster than using blast ; e.g. conserv can find the 1000 most conserved proteins for a window size of 90 in 12 bacterial genomes in 15 min on a sunfire v440 , compared to 7 h for blast - searching each gene in each of the 12 genomes against each other genome .
reciprocal best blast searching may not find the best representative from a set of paralogs ( 31 ) .
similarly , the cogs database draws a line at a certain level of homology , and does not try to separate paralogs even in cases where they can be distinguished fairly reliably , e.g. annotating both clpa and clpb genes as 0542 .
( another , larger , drawback of a predefined database is that it overlooks rare proteins , such as the one annotated simply
conserv attempts to find the best representatives from sets of paralogs by simultaneously minimizing all pairwise distances within each ortholog family .
conserv rarely mixes up paralogs that are separately annotated in genbank . with k = 60
, it sometimes confused peptide chain release factors rf-1 and rf-2 , but with k  90 it correctly separates these two highly homologous proteins . in order to explain how conserv works , we begin by defining a conservation score for a set of orthologous protein sequences .
let pr[i : i+k1 ] denote the subsequence of k amino acid residues starting at residue i in protein pr .
we obtain the alignment score s by aligning pr[i1:i1+k1 ] and ps[i2:i2+k1 ] using the standard dynamic programming algorithm ( 32 ) , scored with the blosum-50 matrix with a gap penalty of 8 .
higher scores represent more similar sequences , but the conservation score is more easily understood if we describe it in terms of a distance function , such as d=1/(1+s ) . then for a highly conserved family of proteins { pr }
, each protein will have a sequence of length k , pr[ir : ir+k1 ] such that all the distances d(pr[ir : ir+k1],ps[is : is+k1 ] ) will be small .
in other words , the set of sequences { pr[ir : ir+k1 ] } will form a tight cluster , whose maximum pairwise distance ( diameter ) is small .
thus a reasonable definition of conservation score over all n organisms is the diameter : 
 cons({pr } ) 
 = mini1,  ,inmax1r , snd(pr[ir : ir+k1],ps[is : is+k1 ] ) , 
 where a smaller score means greater conservation .
,in is a computationally hard problem ; below we describe a heuristic algorithm that works well in practice . in practice , however , the definition of conservation score just given is too brittle .
if an organism t has no homolog of a protein , then the algorithm described below will select a nonhomologous protein pt ( the one with the smallest distance ) and d(pr[ir : ir+k1],pt[it : it+k1 ] ) will be large for all r. thus instead of using the maximum pairwise distance , we use a more robust rank statistic .
we sort the set of distances {  d(pr[ir : ir+k1],ps[is : is+k1])}1r , sn , and select the quartile distance q so that 1/4 of the distances are larger than q and 3/4 are smaller .
if m < n , that is , if we are considering both an in - group and and out - group , we look for minimizing choices of i1,i2, 
,in over all n organisms , and record these choices ( which define the ortholog family ) , but we record the conservation score as max1r , smd(pr[ir : ir+k1],ps[is : is+k1 ] ) . in its internal computations , conserv uses a data structure we call a conservation table .
this is a table with a row for each family of orthologous proteins and a column for each organism .
if there are 1000 rows in the conservation table , conserv 's goal is to fill in the table so that the rows represent the 1000 most conserved proteins over the m genomes of the in - group .
we now explain how conserv arrives at the set of proteins for each row and how it finds approximately minimizing choices of i1,i2,  ,in . as mentioned above , computing the minimizing choices of i1, 
,in is likely to be an inherently hard problem , like most multiple alignment problems , so conserv uses a heuristic algorithm that works well in practice .
the heuristic finds a family of orthologous proteins p ( i.e. builds a row of the conservation table ) at the same time that it computes an approximation of the row 's conservation score . the heuristic first picks two genomes o1 and o2 at random among the first m genomes . for each protein in o1
it finds the most similar protein ( more precisely , the protein with a most similar k - long segment ) in o2 .
then for each row ( nascent orthologous family ) it finds the best k - long homologs in the n  2 other organisms .
this results in a conservation table with a candidate set of rows and a tentative score for each row .
then the whole process is repeated for another random pair of organisms , and the two conservation tables are merged . when merging , if the two tables each have a row with at least two proteins in common , only the row with the better score is retained . to construct the first two columns of the table , we use the standard technique [ used in both blast and fasta ( 33,34 ) ] of building a table of 4mers ( contiguous four - residue sequences ) , only considering potential homologs if they have a 4mer in common .
however , the completed row ( orthologous family ) is not required to have a single 4mer common to all members of that row . along with the  mer table of 4mers
match table , a list of protein pairs sharing common subsequences at least four long .
we start by picking two organisms , o1 and o2 from the in - group of organisms under study .
we place each 4mer from each protein in the two organisms into a mer table of size 20 = 160 000 . each entry in the mer table will have a list of the mer 's occurrences in o1 and a list of its occurrences in o2.build a match table .
for each 4mer in the mer table , look at each pair of occurrences , one from o1 and the other from o2 .
this defines a potential match , that is , an alignment matching the common 4mers .
if the number of elements in the match table is too small or large , change the definition of  extends to a neighborhood ( that is , reduce or enlarge the neighborhood and the number of allowed misses ) until the match table is a reasonable size.compute scores for match table entries . for each item in the match table ( a pair of proteins with a common 4mer ) ,
compute the score of each k - long alignment that extends from the common 4mer .
the score of the item is the maximum of these scores.fill in the first two columns of conservation table .
p in o1 find all entries in the match table that contain a subsequence from p. select the entry ( p , q ) with the highest score . then place p in column 1 , and q in column 2.build a new mer table .
each entry in the just constructed first two columns of the conservation table is a protein together with an k - long sequence with a good alignment .
take each 4mer that occurs in such a sequence and place it into a new mer table .
do this for each protein in columns 1 and 2.fill in the rest of the columns of the conservation table . pick a new column ( organism o ) and iterate through its proteins .
for each protein p in o , examine all 4mers from p. for each one that matches a 4mer in the mer table , constructed in the previous step , compute the score between p and all proteins with that mer from the mer table .
suppose the highest score obtained is s and is with protein q ( from either column 1 or 2 ) . if the entry for the row containing protein q and column k is empty , place p into that slot . if the entry is already occupied , replace it if the score s is higher than the score of the current entry .
finally we sort the resulting table and only retain the rows of sufficiently high degree of conservation.iterate over other starting pairs o1 , o2 . repeat steps ( i  vi ) for a different choice of starting organisms o1 and o2 . merge the resulting conservation tables . whenever there is a row from each table sharing at least two proteins in common , use the row with the highest score . build a table of 4mers .
we start by picking two organisms , o1 and o2 from the in - group of organisms under study .
we place each 4mer from each protein in the two organisms into a mer table of size 20 = 160 000 . each entry in the mer table will have a list of the mer 's occurrences in o1 and a list of its occurrences in o2 .
for each 4mer in the mer table , look at each pair of occurrences , one from o1 and the other from o2 .
this defines a potential match , that is , an alignment matching the common 4mers . check to see if the alignment extends to a neighborhood of the 4mer
if the number of elements in the match table is too small or large , change the definition of  extends to a neighborhood ( that is , reduce or enlarge the neighborhood and the number of allowed misses ) until the match table is a reasonable size .
for each item in the match table ( a pair of proteins with a common 4mer ) , compute the score of each k - long alignment that extends from the common 4mer .
p in o1 find all entries in the match table that contain a subsequence from p. select the entry ( p , q ) with the highest score . then place p in column 1 , and q in column 2 . build a new mer table .
each entry in the just constructed first two columns of the conservation table is a protein together with an k - long sequence with a good alignment .
take each 4mer that occurs in such a sequence and place it into a new mer table .
pick a new column ( organism o ) and iterate through its proteins . for each protein
p in o , examine all 4mers from p. for each one that matches a 4mer in the mer table , constructed in the previous step , compute the score between p and all proteins with that mer from the mer table .
suppose the highest score obtained is s and is with protein q ( from either column 1 or 2 ) . if the entry for the row containing protein q and column k is empty , place p into that slot . if the entry is already occupied , replace it if the score s is higher than the score of the current entry .
finally we sort the resulting table and only retain the rows of sufficiently high degree of conservation .
repeat steps ( i  vi ) for a different choice of starting organisms o1 and o2 .
whenever there is a row from each table sharing at least two proteins in common , use the row with the highest score .
we performed several tests to validate the robustness of conserv 's algorithm for finding and ranking orthologous sequences by conservation level . in one test , we varied the number of iterations in step ( vii ) , i.e. the number of new choices of starting pair , and determined that most subsequences and ranks stabilize after 23 iterations , and all of the top 50 proteins stabilized after at most 10 iterations . in another test , we ran conserv ( with m = n 
 m = n ) on 10 different sets of bacteria .
each set was chosen randomly , but with the constraint that it include one bacterium from each of 19 different phyla represented in genbank at the time .
for each of the top 50 proteins , we computed its relative range , i.e. the difference between the highest and lowest ranks it achieved on the 10 sets , divided by its median rank .
for over half of the proteins , the relative range was less than 0.5 , showing that the list of most conserved proteins is fairly stable over varying taxon samples .
since we are examining only highly similar sequences , we can speed up the computation of the similarity score of two sequences by only filling in the dynamic programming table in a narrow band around the diagonal .
we typically set the band width to be k/60 + 10 for a window size of k ; we empirically found that larger widths did not turn up any more synapomorphies .
our use of mer and match tables means that overall running time is not very dependent on genome sizes ; it depends more heavily on the number of organisms .
it bears repeating that because conserv is intended to find only the most conserved proteins , at least 25% identity over each pair of genomes , it does not need sensitive techniques for detecting remote homology , such as profiles and hmms .
thus conserv is specialized in the opposite direction from most recent bioinformatics tools . rather than being slower but more sophisticated than blast ( 33 )
conserv takes as input a set of n genomes and a sequence  window length k. the program returns ortholog families , with one amino acid sequence of length k from each genome .
conserv uses genome annotations to identify protein - coding genes , but does not use the annotations to identify orthologs .
the use of a fixed window length distinguishes conserv from other alignment search tools , such as blast ( 28,33 ) .
the fixed window enables conserv to make a fair comparison of degree of conservation for genes of different lengths , and more importantly , a search over a range of window lengths can uncover synapomorphies of all three types .
for example , a search with k = 30 will find short motifs and small indels that would make negligible contributions to whole - gene similarity scores . at k = 100
the search can uncover homologous domains , and at k = 300 it can find whole - gene synapomorphies .
we first report on using conserv to find molecular synapomorphies for accepted and hypothesized bacterial clades . for this experiment ,
m genomes form a putative clade , the in - group , and n  m genomes putatively lie outside that clade and form the out - group .
conserv finds sequences that are highly conserved in the in - group and quite different in the out - group .
we calculate the synaptitude of an ortholog family by first computing all ( m2 ) pairwise similarity scores from the putative clade , sorting them , and taking the median .
then we compute all m(n  m ) pairwise distances between orthologous in - group and out - group sequences , and take the three - quartile score ( the ( m2)/4-th largest , where larger scores are less similar ) .
thus for synaptitude to be positive , a typical inside - inside score must exceed a good inside - to - outside score .
all three types of molecular synapomorphies , i.e. ( i ) signature genes , ( ii ) conserved indels and ( iii ) characteristic sequence motifs , should have high synaptitude for some choice of k. we typically ran conserv for k = 30,60,80,100,200,300 . conserv reports the discovered sequences in three groups : those for which the minimum inside similarity score exceeds the maximum in - out score ; those for which the median inside score exceeds the maximum in - out score ; and finally those for which the median inside score exceeds the three - quartile in - out score , i.e. the remaining proteins of positive synaptitude .
a large number of high - synaptitude ortholog families offers some evidence that the hypothesized clade is real , but manual curation is important to further evaluate the evidence and determine synapomorphy type . as usual in phylogenetic inference
a gene could appear to be a strong synapomorphy for a clade relative to a given out - group , but then fail as a synapomorphy relative to a slightly larger out - group . rather than use an enormous out - group and slow down the search , we found it best to use a more modest out - group ( say 20 diverse genomes ) and then doublecheck sequences of high synaptitude by blast searching against all available out - group genomes . the most common situation handled by manual
curation is a gene with an otherwise - good synapomorphy missing from one or more of the clade organisms .
for example , a gene common to all proteobacteria except buchnera would still be a good synapomorphy , because buchnera is a highly reduced genome , safely interior to the clade .
on the other hand , a gene missing from all  - proteobacteria would not be a good synapomorphy for proteobacteria , as  - proteobacteria are the first class of proteobacteria to branch off ( 36,37 ) .
we ran conserv for various choices of in - groups and out - groups , including all eubacterial phyla with more than one sequenced genome in genbank , and a number of hypothesized higher - level clades such as chlamydiales / planctomycetes .
we also ran a number of control experiments with in - groups formed by randomly swapping organisms between an accepted or putative clade and a diverse out - group , in order to test the background level of chance synapomorphies .
control experiments with more than two randomly chosen organisms in the in - group gave no synapomorphies , but two - organism in - groups gave signature genes 15 out of 200 times .
bacteroides seems especially prone to forming pairs , sharing unique genes with treponema ( a hexokinase containing ividaggtnfrsclvrf ) , pirellula ( a glycosyltransferase containing sgwksdilavngfdermqyggqdre ) and helicobacter ( lwqidmihirkgsrydgyfekvaeri ) .
as mentioned above , the sequences returned by conserv were doublechecked by blast searching against all the prokaryotic genomes in genbank . except
as noted , the proteins in table 1 occur only within the named clades  the short probe sequences given do not return any hits outside the clades  and hence are strong molecular synapomorphies .
such signature genes can arise through gene duplication and subsequent rapid evolution , or through horizontal transfer into the ancestral genome from some genome , possibly a bacteriophage genome ( 38 ) , now lost or unsequenced . in either case
perfect signature genes , ubiquitous and conserved within the clade and nonexistent outside the clade . for enterobacteria
the closest such gene is one containing pwyhvvmedddgqpvhtylaeaql , which is missing from buchnera within the clade and has a distant homolog in idiomarina outside the clade .
the rarity of signature genes contrasts with the relatively large number of clade - specific orfan genes ( 85 for enterobacteria ) found by daubin and ochman ( 38 ) .
the difference is that we require a gene to be nearly ubiquitous within the clade , whereas daubin and ochman require only that the gene be confined within the clade and not within one of a small number of subsumed clades , in particular , a gene specific to enterobacteria need not appear in the reduced genomes buchnera and wigglesworthia . for proteobacteria , a large , diverse , and
relatively well - sequenced phylum , we found only a few signature genes , none of them perfect : e.g. ubiquinol - cytochrome c reductase containing psakakaagapvevniskvepgq , phospholipid and glycerol acyltransferase containing wvlkkellripffgwglamtspiaidr , and succinyl - diaminopimelate desuccinylase containing iallitsdeegpavdgt , all of which are missing from a small number of proteobacteria .
we did , however , find a few indel and many motif synapomorphies for proteobacteria .
we found no signature genes or clean indels , and only a few small motifs , for the putative clade marked by * in figure 1 .
the signature genes in table 1 place symbiobacterium with firmicutes , because horizontal transfer would be unlikely to produce such a consistent pattern
. blast searches of key proteins ( 39 ) and maximum - likelihood phylogeny using representative proteins ( 37 ) ( see the supplementary data ) also argue for this placement , but gc - content and 16s rrna initially placed symbiobacterium with actinobacteria ( 40 ) .
figures 24 give example synapomorphies of types ( ii ) and ( iii ) , i.e. indels and motifs .
figure 2 gives several indels in one gene and illustrates the current importance of manual evaluation of evidence .
the qvr insertion in columns 911 and the lr insertion in columns 114115 separate chlamydiales and pirellula [ the only sequenced representative of the enigmatic phylum planctomycetes ( 41 ) ] , an hypothesized clade ( 37 ) , from all the other genomes .
especially important is the separation from leptospira , a spirochaete , as spirochaetes is the most probable sister taxon for chlamydiales ( 36,37,42 ) .
( other sequenced members of spirochaetes do not have close homologs of this gene . ) the qvr insertion , however , is somewhat compromised by the poor conservation of the flanking sequences and the existence of a similarly positioned , but quite different , insertion in chlorobi / bacteroides and geobacter .
the evaluation of flanking sequences could be automated , but this step would not be part of conserv , as it would necessarily take place after multiple alignment .
incidentally , the close similarity of the sequences for chlorobi / bacteroides and geobacter in figure 2 must be a case of horizontal transfer , as most genes clearly place geobacter with -proteobacteria ( represented here by desulfovibrio ) .
examples such as this one caution against using single - gene synapomorphies , no matter how compelling , for prokaryotic phylogenetic inference . because pirellula shares several signature genes with bacteroides , we also searched for synapomorphies supporting a pirellula / bacteroides / chlorobi clade .
the best synapomorphy found was glucosamine-6-phosphate isomerase containing the sequence revqphqiyaagdlsphgthrtcld , present in pirellula , porphyromonas and bacteroides , but missing from chlorobium .
due to the tendency of bacteroides to form pairs , we prefer to place pirellula with chlamydiales .
dehalococcoides ethenogenes ( 43 ) is currently the only fully sequenced representative of the enigmatic phylum chloroflexi .
the position of this phylum has implications for the evolutionary history of photosynthesis ( 11,4446 ) , specifically whether reaction center rc-1 ( in cyanobacteria , chlorobium and heliobacteria ( within firmicutes ) ) , preceded rc-2 ( in cyanobacteria , chloroflexi and proteobacteria ) , or vice versa , or whether both evolved together . using maximum - likelihood phylogeny and a draft genome of chloroflexus aurantiacus from the doe joint genome institute , we previously placed ( 37 ) chloroflexi next to cyanobacteria as the first two phyla to diverge from an hypothesized clade containing chloroflexi , cyanobacteria , deinococcus / thermus and actinobacteria .
the same phylogeny method using the complete dehalococcoides genome places chloroflexi near fusobacterium on a path to firmicutes , but with very poor bootstrap support .
we found no synapomorphies supporting the hypothesized clade containing chloroflexi , cyanobacteria , deinococcus and actinobacteria .
although there are a number of genes ( e.g. polyribonucleotide nucleotidyltransferase ) that are well - conserved over this in - group , some out - group members ( typically members of firmicutes ) also have sequences similar to those of the in - group .
we also found no synapomorphies supporting the hypothesized clade of chloroflexi , fusobacterium and firmicutes .
we did , however , find a few synapomorphies to support a cyanobacteria / chloroflexi clade : a motif sequence ( sidfglcvfcglcvescpt in dehalococcoides ) in nadh dehydrogenase subunit i , and two characteristic indels in imp dehydrogenase , shown in figure 3 .
an in - group of dehalococcoides , chlorobium , bacteroides and pirellula , i.e. a putative clade containing both green sulfur and green nonsulfur bacteria , also gave no synapomorphies , even though such a clade appears in gene trees of photosynthesis genes ( 46 ) .
both searches , however , found several genes that appear in only the in - group genomes and a few out - group members , again generally members of firmicutes , such as clostridium and listeria .
listeria 's sequence in figure 3 shows a related anomaly : it is sufficiently similar to the other sequences that the multiple alignment is probably correct , and not so different from the sequences of the other firmicutes ( lactococcus and streptococcus ) as to constitute a clear case of horizontal transfer , yet it includes the insertion at columns 6065 characteristic of the hypothesized cyanobacteria / chloroflexi clade .
psi - blast searching reveals that this insertion  not so well - conserved  also occurs in two members of bacteroidetes ( bacillus fragilis and porphyromonas gingivalis ) and a spirochaete ( treponema denticola ) .
possible explanations for this pattern include repeated horizontal transfers and/or a tendency for insertion in this sequence .
both our placement of chloroflexi made with synapomorphies , on the path to cyanobacteria , and our weakly supported maximum - likelihood placement of chloroflexi on a path to firmicutes , are consistent with an evolutionary model ( 44,46 ) in which rc-2 ( bacteriochlorophyll ) precedes rc-1 ( chlorophyll ) .
our finding that a number of genes appear only in dehalococcoides , chlorobium and its relatives , and members of firmicutes close to heliobacterium , suggests ancient horizontal transfer into firmicutes as a plausible explanation for the appearance of rc-1 in this early - diverging phylum .
figure 4 studies the position of the endosymbionts buchnera and wigglesworthia with respect to other -proteobacteria , showing the strongest synapomorphy  a motif synapomorphy  for the inclusion of buchnera and wigglesworthia with enterobacteria , as in ( 47,48 ) and the current genbank taxonomy .
an alternative taxonomy ( 36,37 ) that places buchnera / wigglesworthia outside an enterobacteria / pasteurellales clade had less persuasive motif synapomorphies .
neither placement yielded signature gene synapomorphies , but the alternative placement had four genes rather than two with median in - in scores exceeding maximum in - out scores . in this case , even if the alternative placement had found signature genes , we might favor the motif synapomorphies , because buchnera and wigglesworthia are both reduced genomes that could easily have lost signature genes characteristic of the enterobacteria / pasteurellales clade .
due to long branches and reduced genomes , the placement of buchnera and wigglesworthia is not easily made with either distance- or sequence - based phylogenetic methods ( 36,37 ) , and even the fact that these two organisms form a clade is not obvious ( 47 ) .
we also looked at the position of aquifex : does it belong with thermotoga near the base of the bacterial tree ( 36,37,42 ) or did it diverge later , close to proteobacteria ( 13 ) ?
along with many motif synapomorphies , we found two signature - gene synapomorphies for the hypothesized aquifex / thermotoga clade , a protein containing the well - conserved sequence qkrawneyrmllipgfevtnn and another containing khgirditatgvkaititkre .
are these proteins the smoking guns proving that aquifex and thermotoga diverged together , or are they more recent horizontal transfers from one to the other ?
although we found no signature - gene synapomorphies when we tried alternative placements for aquifex , we consider this question still open .
for example , we can give it a set of organisms sharing some biochemical capability , in order to find genes related to that capability .
we have used conserv in this way to study photosynthetic bacteria and endoparasites / endosymbionts ( mycoplasma , buchnera , wigglesworthia ) . such computational experiments have been performed previously using all - against - all blast ; for example , raymond et al . ( 49 ) find genes related to photosynthesis in this way .
conserv is faster than all - against - all blast , and also ranks its output by conservation level or synaptitude so that a user can decide where to cut .
 phylogenetic profiles ( 50 ) cluster predetermined genes by which genomes contain them , thereby discovering possible functional relationships .
conserv enables a reverse search : find sequences ( not necessarily full genes ) with predetermined phylogenetic profiles .
here we report on using conserv to study a false clade not obviously related by a shared capability .
the  - proteobacteria are generally accepted as true proteobacteria , yet molecular phylogeny sometimes places them with spirochaetes ( 37,42 ) .
table 2 gives the annotated proteins with top synaptitude for this ( presumably ) false clade .
the out - group for this experiment included several members of chlamydiales , the likely sister clade of spirochaetes ( 36,42 ) .
evidently , the flagellar proteins of  - proteobacteria resemble those of spirochaetes , although none of the proteins are signature - gene synapomorphies as in table 1 .
it is conceivable that a block of interacting genes were horizontally transferred to an organism ancestral to one of these taxa .
we use conserv to make this quantitative , ranking proteins by degree of conservation over all n input genomes .
we considered both eubacteria and archaea in this experiment . to answer the question for eubacteria ,
we used 28 representative bacteria from 11 phyla ; results vary slightly with other , equivalently diverse , taxon samples .
figure 5 and table 3 summarize the output of conserv over window sizes ranging from about 50 to 500 amino acids . in order to measure the conservation of an orthologous family , we computed all pairwise similarity scores ( blosum-50 with a gap penalty of 8) between orthologous sequences , and took the conservation score to be the score such that one - fourth of the pairs of orthologs score worse ( less similarity ) and three - fourths score better .
the vertical axis represents score per residue and shows that normalized score depends irregularly on window size .
there is a natural way to combine different window sizes and obtain an answer to the question of  what 's the most conserved protein?. for each window size k , with k = 60 , 90 , 120 ,   
then for each protein , we found the k for which it had the highest rank and assigned this best rank to the protein .
achieve the top rank for some choice of k , but because ef - tu is most conserved for both small and large windows , we considered it first among the proteins that achieve rank 1 .
the only ribosomal protein to make the list is s12 , which is physically central to the ribosome and is suspected to interact directly with ef - tu ( personal communication with irina gabashvili ) .
there are four heat shock proteins ( groel , dnak , clpb , clpx ) , but only one metabolic protein ( two subunits of atp synthase f1 ) . for a more systematic study of the connection between function and conservation
, we use the cog functional categories ( 6,7 ) . of the top 20 proteins , 60% are from categories j , k and l , the information storage and processing categories .
this pattern holds up for larger lists . of the top 100 proteins , 56 turn out to be in categories
l ( dna replication , recombination and repair ) and j ( translation , ribosomal structure and biogenesis ) . along with functional category ( 51 ) , conservation level has also been correlated with protein length ( 52 ) , expression level ( 53 ) , essential proteins ( 5456 ) and number of interaction partners ( 53,5759 ) . by rapidly assembling and ranking orthologs by conservation
four genes achieved top rank for some choice of k : cdc48 ( cell division control protein ) , atpa and atpb ( h - transporting atp synthase , subunits a and b ) , and rpob1 ( dna - directed rna polymerase , subunit  ) .
we also ran conserv to find what protein is most conserved over all prokaryotes ( archaea and eubacteria ) .
now three metabolic proteins , ctp synthase , enolase and gmp synthase , which do not even make the top 20 for eubacteria , leap to the top of the list ; this finding is further corroboration of the relative similarity of eubacterial and archaeal metabolic genes compared to transcriptional and translational genes ( 51 ) .
it seems likely that the genes for these most conserved proteins were horizontally transferred sometime after the last common ancestor of archaea and bacteria .
we first report on using conserv to find molecular synapomorphies for accepted and hypothesized bacterial clades . for this experiment ,
m genomes form a putative clade , the in - group , and n  m genomes putatively lie outside that clade and form the out - group .
conserv finds sequences that are highly conserved in the in - group and quite different in the out - group .
we calculate the synaptitude of an ortholog family by first computing all ( m2 ) pairwise similarity scores from the putative clade , sorting them , and taking the median .
then we compute all m(n  m ) pairwise distances between orthologous in - group and out - group sequences , and take the three - quartile score ( the ( m2)/4-th largest , where larger scores are less similar ) .
thus for synaptitude to be positive , a typical inside - inside score must exceed a good inside - to - outside score .
all three types of molecular synapomorphies , i.e. ( i ) signature genes , ( ii ) conserved indels and ( iii ) characteristic sequence motifs , should have high synaptitude for some choice of k. we typically ran conserv for k = 30,60,80,100,200,300 . conserv reports the discovered sequences in three groups : those for which the minimum inside similarity score exceeds the maximum in - out score ; those for which the median inside score exceeds the maximum in - out score ; and finally those for which the median inside score exceeds the three - quartile in - out score , i.e. the remaining proteins of positive synaptitude .
a large number of high - synaptitude ortholog families offers some evidence that the hypothesized clade is real , but manual curation is important to further evaluate the evidence and determine synapomorphy type . as usual in phylogenetic inference
a gene could appear to be a strong synapomorphy for a clade relative to a given out - group , but then fail as a synapomorphy relative to a slightly larger out - group . rather than use an enormous out - group and
slow down the search , we found it best to use a more modest out - group ( say 20 diverse genomes ) and then doublecheck sequences of high synaptitude by blast searching against all available out - group genomes .
the most common situation handled by manual curation is a gene with an otherwise - good synapomorphy missing from one or more of the clade organisms .
for example , a gene common to all proteobacteria except buchnera would still be a good synapomorphy , because buchnera is a highly reduced genome , safely interior to the clade .
on the other hand , a gene missing from all  - proteobacteria would not be a good synapomorphy for proteobacteria , as  - proteobacteria are the first class of proteobacteria to branch off ( 36,37 ) .
we ran conserv for various choices of in - groups and out - groups , including all eubacterial phyla with more than one sequenced genome in genbank , and a number of hypothesized higher - level clades such as chlamydiales / planctomycetes .
we also ran a number of control experiments with in - groups formed by randomly swapping organisms between an accepted or putative clade and a diverse out - group , in order to test the background level of chance synapomorphies .
control experiments with more than two randomly chosen organisms in the in - group gave no synapomorphies , but two - organism in - groups gave signature genes 15 out of 200 times .
bacteroides seems especially prone to forming pairs , sharing unique genes with treponema ( a hexokinase containing ividaggtnfrsclvrf ) , pirellula ( a glycosyltransferase containing sgwksdilavngfdermqyggqdre ) and helicobacter ( lwqidmihirkgsrydgyfekvaeri ) .
as mentioned above , the sequences returned by conserv were doublechecked by blast searching against all the prokaryotic genomes in genbank . except
as noted , the proteins in table 1 occur only within the named clades  the short probe sequences given do not return any hits outside the clades  and hence are strong molecular synapomorphies .
such signature genes can arise through gene duplication and subsequent rapid evolution , or through horizontal transfer into the ancestral genome from some genome , possibly a bacteriophage genome ( 38 ) , now lost or unsequenced . in either case , the signature gene supports the validity of the putative clade .
perfect signature genes , ubiquitous and conserved within the clade and nonexistent outside the clade . for enterobacteria
the closest such gene is one containing pwyhvvmedddgqpvhtylaeaql , which is missing from buchnera within the clade and has a distant homolog in idiomarina outside the clade .
the rarity of signature genes contrasts with the relatively large number of clade - specific orfan genes ( 85 for enterobacteria ) found by daubin and ochman ( 38 ) .
the difference is that we require a gene to be nearly ubiquitous within the clade , whereas daubin and ochman require only that the gene be confined within the clade and not within one of a small number of subsumed clades , in particular , a gene specific to enterobacteria need not appear in the reduced genomes buchnera and wigglesworthia . for proteobacteria , a large , diverse , and
relatively well - sequenced phylum , we found only a few signature genes , none of them perfect : e.g. ubiquinol - cytochrome c reductase containing psakakaagapvevniskvepgq , phospholipid and glycerol acyltransferase containing wvlkkellripffgwglamtspiaidr , and succinyl - diaminopimelate desuccinylase containing iallitsdeegpavdgt , all of which are missing from a small number of proteobacteria .
we did , however , find a few indel and many motif synapomorphies for proteobacteria .
we found no signature genes or clean indels , and only a few small motifs , for the putative clade marked by * in figure 1 .
the signature genes in table 1 place symbiobacterium with firmicutes , because horizontal transfer would be unlikely to produce such a consistent pattern .
blast searches of key proteins ( 39 ) and maximum - likelihood phylogeny using representative proteins ( 37 ) ( see the supplementary data ) also argue for this placement , but gc - content and 16s rrna initially placed symbiobacterium with actinobacteria ( 40 ) .
figures 24 give example synapomorphies of types ( ii ) and ( iii ) , i.e. indels and motifs .
figure 2 gives several indels in one gene and illustrates the current importance of manual evaluation of evidence .
the qvr insertion in columns 911 and the lr insertion in columns 114115 separate chlamydiales and pirellula [ the only sequenced representative of the enigmatic phylum planctomycetes ( 41 ) ] , an hypothesized clade ( 37 ) , from all the other genomes .
especially important is the separation from leptospira , a spirochaete , as spirochaetes is the most probable sister taxon for chlamydiales ( 36,37,42 ) .
( other sequenced members of spirochaetes do not have close homologs of this gene . )
the qvr insertion , however , is somewhat compromised by the poor conservation of the flanking sequences and the existence of a similarly positioned , but quite different , insertion in chlorobi / bacteroides and geobacter
. the evaluation of flanking sequences could be automated , but this step would not be part of conserv , as it would necessarily take place after multiple alignment .
incidentally , the close similarity of the sequences for chlorobi / bacteroides and geobacter in figure 2 must be a case of horizontal transfer , as most genes clearly place geobacter with -proteobacteria ( represented here by desulfovibrio ) .
examples such as this one caution against using single - gene synapomorphies , no matter how compelling , for prokaryotic phylogenetic inference . because pirellula shares several signature genes with bacteroides , we also searched for synapomorphies supporting a pirellula / bacteroides / chlorobi clade .
the best synapomorphy found was glucosamine-6-phosphate isomerase containing the sequence revqphqiyaagdlsphgthrtcld , present in pirellula , porphyromonas and bacteroides , but missing from chlorobium . due to the tendency of bacteroides to form pairs
dehalococcoides ethenogenes ( 43 ) is currently the only fully sequenced representative of the enigmatic phylum chloroflexi .
the position of this phylum has implications for the evolutionary history of photosynthesis ( 11,4446 ) , specifically whether reaction center rc-1 ( in cyanobacteria , chlorobium and heliobacteria ( within firmicutes ) ) , preceded rc-2 ( in cyanobacteria , chloroflexi and proteobacteria ) , or vice versa , or whether both evolved together . using maximum - likelihood phylogeny and a draft genome of chloroflexus aurantiacus from the doe joint genome institute , we previously placed ( 37 ) chloroflexi next to cyanobacteria as the first two phyla to diverge from an hypothesized clade containing chloroflexi , cyanobacteria , deinococcus / thermus and actinobacteria . the same phylogeny method using the complete dehalococcoides genome places chloroflexi near fusobacterium on a path to firmicutes , but with very poor bootstrap support .
we found no synapomorphies supporting the hypothesized clade containing chloroflexi , cyanobacteria , deinococcus and actinobacteria .
although there are a number of genes ( e.g. polyribonucleotide nucleotidyltransferase ) that are well - conserved over this in - group , some out - group members ( typically members of firmicutes ) also have sequences similar to those of the in - group .
we also found no synapomorphies supporting the hypothesized clade of chloroflexi , fusobacterium and firmicutes .
we did , however , find a few synapomorphies to support a cyanobacteria / chloroflexi clade : a motif sequence ( sidfglcvfcglcvescpt in dehalococcoides ) in nadh dehydrogenase subunit i , and two characteristic indels in imp dehydrogenase , shown in figure 3 .
an in - group of dehalococcoides , chlorobium , bacteroides and pirellula , i.e. a putative clade containing both green sulfur and green nonsulfur bacteria , also gave no synapomorphies , even though such a clade appears in gene trees of photosynthesis genes ( 46 ) .
both searches , however , found several genes that appear in only the in - group genomes and a few out - group members , again generally members of firmicutes , such as clostridium and listeria .
listeria 's sequence in figure 3 shows a related anomaly : it is sufficiently similar to the other sequences that the multiple alignment is probably correct , and not so different from the sequences of the other firmicutes ( lactococcus and streptococcus ) as to constitute a clear case of horizontal transfer , yet it includes the insertion at columns 6065 characteristic of the hypothesized cyanobacteria / chloroflexi clade .
psi - blast searching reveals that this insertion  not so well - conserved  also occurs in two members of bacteroidetes ( bacillus fragilis and porphyromonas gingivalis ) and a spirochaete ( treponema denticola ) .
possible explanations for this pattern include repeated horizontal transfers and/or a tendency for insertion in this sequence .
both our placement of chloroflexi made with synapomorphies , on the path to cyanobacteria , and our weakly supported maximum - likelihood placement of chloroflexi on a path to firmicutes , are consistent with an evolutionary model ( 44,46 ) in which rc-2 ( bacteriochlorophyll ) precedes rc-1 ( chlorophyll ) .
our finding that a number of genes appear only in dehalococcoides , chlorobium and its relatives , and members of firmicutes close to heliobacterium , suggests ancient horizontal transfer into firmicutes as a plausible explanation for the appearance of rc-1 in this early - diverging phylum .
figure 4 studies the position of the endosymbionts buchnera and wigglesworthia with respect to other -proteobacteria , showing the strongest synapomorphy  a motif synapomorphy  for the inclusion of buchnera and wigglesworthia with enterobacteria , as in ( 47,48 ) and the current genbank taxonomy .
an alternative taxonomy ( 36,37 ) that places buchnera / wigglesworthia outside an enterobacteria / pasteurellales clade had less persuasive motif synapomorphies .
neither placement yielded signature gene synapomorphies , but the alternative placement had four genes rather than two with median in - in scores exceeding maximum in - out scores . in this case , even if the alternative placement had found signature genes , we might favor the motif synapomorphies , because buchnera and wigglesworthia are both reduced genomes that could easily have lost signature genes characteristic of the enterobacteria / pasteurellales clade .
due to long branches and reduced genomes , the placement of buchnera and wigglesworthia is not easily made with either distance- or sequence - based phylogenetic methods ( 36,37 ) , and even the fact that these two organisms form a clade is not obvious ( 47 ) .
we also looked at the position of aquifex : does it belong with thermotoga near the base of the bacterial tree ( 36,37,42 ) or did it diverge later , close to proteobacteria ( 13 ) ?
along with many motif synapomorphies , we found two signature - gene synapomorphies for the hypothesized aquifex / thermotoga clade , a protein containing the well - conserved sequence qkrawneyrmllipgfevtnn and another containing khgirditatgvkaititkre . are these proteins the smoking guns proving that aquifex and thermotoga diverged together , or are they more recent horizontal transfers from one to the other ?
although we found no signature - gene synapomorphies when we tried alternative placements for aquifex , we consider this question still open .
for example , we can give it a set of organisms sharing some biochemical capability , in order to find genes related to that capability .
we have used conserv in this way to study photosynthetic bacteria and endoparasites / endosymbionts ( mycoplasma , buchnera , wigglesworthia ) .
such computational experiments have been performed previously using all - against - all blast ; for example , raymond et al . ( 49 ) find genes related to photosynthesis in this way .
conserv is faster than all - against - all blast , and also ranks its output by conservation level or synaptitude so that a user can decide where to cut .
 phylogenetic profiles ( 50 ) cluster predetermined genes by which genomes contain them , thereby discovering possible functional relationships .
conserv enables a reverse search : find sequences ( not necessarily full genes ) with predetermined phylogenetic profiles .
here we report on using conserv to study a false clade not obviously related by a shared capability .
the  - proteobacteria are generally accepted as true proteobacteria , yet molecular phylogeny sometimes places them with spirochaetes ( 37,42 ) .
table 2 gives the annotated proteins with top synaptitude for this ( presumably ) false clade .
the out - group for this experiment included several members of chlamydiales , the likely sister clade of spirochaetes ( 36,42 ) .
evidently , the flagellar proteins of  - proteobacteria resemble those of spirochaetes , although none of the proteins are signature - gene synapomorphies as in table 1 .
it is conceivable that a block of interacting genes were horizontally transferred to an organism ancestral to one of these taxa .
biologists frequently describe proteins as  very highly conserved or  one of the most highly conserved proteins . in this section
, we use conserv to make this quantitative , ranking proteins by degree of conservation over all n input genomes .
we considered both eubacteria and archaea in this experiment . to answer the question for eubacteria
, we used 28 representative bacteria from 11 phyla ; results vary slightly with other , equivalently diverse , taxon samples .
figure 5 and table 3 summarize the output of conserv over window sizes ranging from about 50 to 500 amino acids . in order to measure the conservation of an orthologous family , we computed all pairwise similarity scores ( blosum-50 with a gap penalty of 8) between orthologous sequences , and took the conservation score to be the score such that one - fourth of the pairs of orthologs score worse ( less similarity ) and three - fourths score better .
the vertical axis represents score per residue and shows that normalized score depends irregularly on window size .
there is a natural way to combine different window sizes and obtain an answer to the question of  what 's the most conserved protein?. for each window size k , with k = 60 , 90 , 120 ,    ,  510
then for each protein , we found the k for which it had the highest rank and assigned this best rank to the protein .
five different proteins ( ef - tu , ftsh , etc . ) achieve the top rank for some choice of k , but because ef - tu is most conserved for both small and large windows , we considered it first among the proteins that achieve rank 1 .
the only ribosomal protein to make the list is s12 , which is physically central to the ribosome and is suspected to interact directly with ef - tu ( personal communication with irina gabashvili ) .
there are four heat shock proteins ( groel , dnak , clpb , clpx ) , but only one metabolic protein ( two subunits of atp synthase f1 ) . for a more systematic study of the connection between function and conservation
, we use the cog functional categories ( 6,7 ) . of the top 20 proteins , 60% are from categories j , k and l , the information storage and processing categories .
this pattern holds up for larger lists . of the top 100 proteins , 56 turn out to be in categories
l ( dna replication , recombination and repair ) and j ( translation , ribosomal structure and biogenesis ) . along with functional category ( 51 ) , conservation level has also been correlated with protein length ( 52 ) , expression level ( 53 ) , essential proteins ( 5456 ) and number of interaction partners ( 53,5759 ) . by rapidly assembling and ranking orthologs by conservation ,
four genes achieved top rank for some choice of k : cdc48 ( cell division control protein ) , atpa and atpb ( h - transporting atp synthase , subunits a and b ) , and rpob1 ( dna - directed rna polymerase , subunit  ) .
we also ran conserv to find what protein is most conserved over all prokaryotes ( archaea and eubacteria ) .
now three metabolic proteins , ctp synthase , enolase and gmp synthase , which do not even make the top 20 for eubacteria , leap to the top of the list ; this finding is further corroboration of the relative similarity of eubacterial and archaeal metabolic genes compared to transcriptional and translational genes ( 51 ) .
it seems likely that the genes for these most conserved proteins were horizontally transferred sometime after the last common ancestor of archaea and bacteria .
molecular synapomorphies are potentially very valuable phylogenetic characters , because rare discontinuous events  a large insertion or deletion , or the  sudden appearance of a novel , highly conserved gene  are not easily erased by subsequent point mutations .
moreover , molecular synapomorphies are complementary to popular sequence - based methods , such as maximum likelihood , which do not ordinarily take into account non - ubiquitous characters , such as insertions and deletions (  gap columns ' ) and proteins unique to a clade . to date
, however , molecular synapomorphies have been used on an ad hoc basis , with phylogenies inferred from a handful of manually discovered synapomorphies . nevertheless , the prokaryotic phylogenies computed in the 1990s by gupta et al .
( 10,11 ) from hand - picked indels in selected genes show broad agreement with recent phylogenies computed using complete genomes and the latest tools ( 36,37,42 ) .
we do not expect molecular synapomorphies to replace modern tree - building methods , but we can imagine hybrid methods akin to those devised for gene trees ( 60 ) and routine use of synapomorphies to rescore a small number of alternative trees . until now there has been , to our knowledge , no effort or means to automatically gather
hence we believe that conserv , simple as it is , can play a role in phylogenetic inference , as well as in data mining for unexpected nuggets , such as the similarity of the flagellar proteins of  - proteobacteria and spirochaetes .
the sensitivity and specificity of conserv are hard to assess at this point , as we do not have a test set of agreed - upon synapomorphies or a validated mathematical model .
conserv appears to be fairly effective at finding signature - gene and motif synapomorphies , which are easy to recognize from pairwise alignments , but indel synapomorphies remain somewhat problematic .
( 1012 ) from multiple alignments , but missed some of the less obvious ( and more arguable ) one- and two - residue indels .
the great difference in the numbers of signature genes found by our study and that of daubin and ochman reveals that conserv 's sensitivity could be improved by a more flexible definition of synaptitude that allows signature genes to be missing from organisms deemed safely interior to the in - group .
future research should assess the strengths and weaknesses of signature genes , indels , and motifs as phylogenetic characters .
the listeria anomaly in figure 3 highlights the fact that the evolutionary mechanism of insertion and deletion is not well understood . until more is known about this process
, the evidentiary strength of indels will be open to question , and such characters would be better used not as absolute evidence as in the work of gupta et al .
gene order  has been judged relatively weak for deep bacterial phylogeny ( 61 ) , yet valuable for eukaryotic phylogeny based on mitochondrial genomes ( 16,17 ) .
is our classification of synapomorphy types adequate , or would a more detailed and exhaustive classification be useful ? will the discovery of new molecular synapomorphies elucidate epochal events [ e.g. colonization of land ( 36 ) ] in the history of prokaryotic life ?
a short , ancient , internal branch such as the one marked * is not easy to resolve with clock - like sequence evolution , but a rare event such as a signature gene may resolve the clade .
the depicted phylogenetic tree is a consensus of those given in three recent studies ( 36,37,42 ) .
the enigmatic organisms and the placements considered here are shown with wiggly branches , with the solid wiggly lines indicating the placements best supported by our synapomorphy search .
this muscle ( 21 ) alignment of a 125-aa subsequence of succinate dehydrogenase , flavoprotein subunit ( cog1053 ) , provides evidence that pirellula and chlamydiales , the first five rows , form a clade .
the first five rows share overall sequence similarity , along with the qvr insertion in columns 911 and the lr insertion in columns 114115 .
the alignment also uncovers an apparent horizontal transfer from chlorobi / bacteroides to geobacter , evidenced by great sequence similarity and the insertion at columns 114119 .
the top and bottom rows give the consensus sequence of chlamydiales and pirellula . a dot indicates agreement with a consensus residue , and a blank indicates agreement with a consensus gap .
this muscle alignment of a 129-aa subsequence of imp dehydrogenase ( cog0516 ) provides evidence that chloroflexi ( represented by dehalococcoides ) and cyanobacteria , the first eight rows , form a clade .
the first eight rows share overall sequence similarity , along with an insertion in columns 6065 and a deletion in columns 111120 .
the top and bottom rows give the consensus sequence of the first eight rows . in this figure , | indicates a column with complete conservation over all rows , and : indicates nearly complete conservation .
this muscle alignment of a highly conserved 60-aa sequence in atp synthase , subunit c , gives a motif synapomorphy arguing for the inclusion of the endosymbionts buchnera and wigglesworthia with enterobacteria .
the first nine organisms are enterobacteria , the next two ( haemophilus and pasteurella ) are pasteurellales and the last nine are other -proteobacteria , roughly in order of distance from enterobacteria .
the plot shows conservation level , measured by quartile similarity score , as a function of window size for the seven most conserved proteins over a sample of 28 diverse eubacteria , representing 11 phyla .
the similarity score per residue generally decreases , but sometimes increases when a less - conserved stretch is flanked by two well - conserved subsequences . because ef - tu claims top rank at a variety of window lengths , it is the most natural candidate for the most conserved protein over all bacteria .
the sequence given is from one organism in the clade , but is sufficient for blast searching .
none of the signature genes for actinobacteria have orthologs in symbiobacterium , but both of the signature genes for firimicutes do .
this finding is evidence that symbiobacterium belongs with firmicutes . by giving conserv a false clade (  - proteobacteria and spirochaetes ) , we can study what two taxa have in common .
this list of indel and motif synapomorphies tells a consistent  tail. the 20 most conserved eubacterial proteins by quartile similarity score for the diverse set of 28 bacteria from 11 phyla . rank ( rk ) is the protein 's highest rank ; window gives a window size ( or range ) for which the protein achieves its highest rank ; score / res ( s / r ) is the quartile score divided by the window size ; length ( len ) is the number of amino acid residues for a representative bacterium ; cog and class ( cls ) are from ( 7 ) .
class j is translation , ribosomal structure and biogenesis ; k is transcription ; l is replication , recombination and repair ; and o is post - translational modification , protein turnover , and chaperones .
 a synapomorphy is a phylogenetic character that provides evidence of shared descent . 
 ideally a synapomorphy is ubiquitous within the clade of related organisms and nonexistent outside the clade , implying that it arose after divergence from other extant species and before the last common ancestor of the clade . with the recent proliferation of genetic sequence data , 
 molecular synapomorphies have assumed great importance , yet there is no convenient means to search for them over entire genomes . 
 we have developed a new program called conserv , which can rapidly assemble orthologous sequences and rank them by various metrics , such as degree of conservation or divergence from out - group orthologs . 
 we have used conserv to conduct a largescale search for molecular synapomorphies for bacterial clades . 
 the search discovered sequences unique to clades , such as actinobacteria , firmicutes and -proteobacteria , and shed light on several open questions , such as whether symbiobacterium thermophilum belongs with actinobacteria or firmicutes . 
 we conclude that conserv can quickly marshall evidence relevant to evolutionary questions that would be much harder to assemble with other tools . 
INTRODUCTION
MATERIALS AND METHODS
RESULTS
Molecular synapomorphies
What's the most conserved protein?
DISCUSSION
Figures and Tables