phylogenetic footprinting is a comparative genomics approach to the computational prediction of transcription factor binding sites [ for a review see ( 1 ) ] . under the premise that functional regions of a dna sequence tend to evolve at a lower rate than non - functional regions , highly conserved regions found in a set of homologous promoter sequences
while several phylogenetic footprinting methods have been developed for identifying putative binding sites for transcription factors with known position weight matrices [ e.g. rvista ( 2 ) and consite ( 3 ) ] , our focus here is on de novo methods , where no prior knowledge about the transcription factors involved is assumed .
the first group , called alignment - based methods , contains the most published variations [ see , among others , phylovista ( 4 ) and phastcons ( 5 ) ] .
these methods start by computing a multiple sequence alignment of the set of orthologous sequences considered . the alignment is then scanned to identify conserved regions .
methods from the second group , called motif - based methods , do not assume that the orthologous sequences can be reliably aligned , but instead directly attempt to identify sets of subsequences that exhibit a high degree of conservation [ see , e.g. footprinter2 ( 6,7 ) ] .
here , we introduce footprinter3 , a new web - based program that unifies the two approaches , taking advantage of the strengths of both methods . for both types of methods to clearly differentiate between binding sites and their non - functional surroundings , the set of sequences to be considered should cover a sufficiently large total amount of divergence for non - functional regions to have accumulated significantly more mutations than functional regions .
this can be achieved either through a large set of relatively closely related species , or through a smaller set of more highly diverged species . however , highly diverged sequences are difficult to align .
in fact , even if the set of orthologous sequences considered contains a few short , highly conserved substrings , alignment programs will often fail to align them correctly , because of the high noise of the surrounding poorly conserved sequences . in practice , this means , for example , that to identify transcription factor binding sites in a human sequence , one may want to compare it to other mammalian sequences , but comparing it to other more distantly related vertebrate species is likely to fail because of incorrect ( or unavailable ) alignment . in particular , the evolutionary distance between the mammalian genomes and the recently sequenced chicken genome is too large to be able to reliably align most non - coding regions ( 8) .
motif - based approaches have been developed precisely to address this problem , and they do not suffer from the presence of highly diverged sequences , as long as these sequences still contain the short conserved regions likely to correspond to binding sites .
this is due to the fact that since each motif is identified independently and outside of its context , it is possible that a set of conserved substrings identified may not be orthologous ( i.e. they are not derived from a common ancestor ) , and that their apparent similarity is simply due to chance . in this paper , we introduce footprinter3 , a web server for the detection of short , conserved regions likely to be transcription factor binding sites in a set of partially aligned sequences . partially aligned sequences consist of a set of ordered local alignments , each involving regions from a subset ( or all ) of input sequences .
not all nucleotides of all sequences need to belong to an alignment block , and regions that can not be reliably aligned are simply left unaligned .
these alignment blocks are then used as a guide for the detection of conserved substrings using a modification of the footprinter motif - finding algorithm ( 7 ) .
the motifs reported can be located both in aligned and unaligned regions and their position is guaranteed to be compatible ( in a sense to be defined below ) with the set of local alignment blocks .
this results in a motif prediction algorithm that retains the strengths of both approaches while correcting for their weaknesses . in completely alignable sequences ,
our approach is similar to existing sliding - window approaches , while in completely unalignable sequences , it is equivalent to the footprinter2 motif - discovery algorithm ( 7 ) . in between , it uses the local alignments to reduce the likelihood of finding sets of substrings that are not true orthologs , thereby increasing the specificity of the predictions .
for both types of methods to clearly differentiate between binding sites and their non - functional surroundings , the set of sequences to be considered should cover a sufficiently large total amount of divergence for non - functional regions to have accumulated significantly more mutations than functional regions .
this can be achieved either through a large set of relatively closely related species , or through a smaller set of more highly diverged species . however , highly diverged sequences are difficult to align .
in fact , even if the set of orthologous sequences considered contains a few short , highly conserved substrings , alignment programs will often fail to align them correctly , because of the high noise of the surrounding poorly conserved sequences . in practice , this means , for example , that to identify transcription factor binding sites in a human sequence , one may want to compare it to other mammalian sequences , but comparing it to other more distantly related vertebrate species is likely to fail because of incorrect ( or unavailable ) alignment .
in particular , the evolutionary distance between the mammalian genomes and the recently sequenced chicken genome is too large to be able to reliably align most non - coding regions ( 8) .
motif - based approaches have been developed precisely to address this problem , and they do not suffer from the presence of highly diverged sequences , as long as these sequences still contain the short conserved regions likely to correspond to binding sites .
this is due to the fact that since each motif is identified independently and outside of its context , it is possible that a set of conserved substrings identified may not be orthologous ( i.e. they are not derived from a common ancestor ) , and that their apparent similarity is simply due to chance .
in this paper , we introduce footprinter3 , a web server for the detection of short , conserved regions likely to be transcription factor binding sites in a set of partially aligned sequences .
partially aligned sequences consist of a set of ordered local alignments , each involving regions from a subset ( or all ) of input sequences .
not all nucleotides of all sequences need to belong to an alignment block , and regions that can not be reliably aligned are simply left unaligned .
these alignment blocks are then used as a guide for the detection of conserved substrings using a modification of the footprinter motif - finding algorithm ( 7 ) .
the motifs reported can be located both in aligned and unaligned regions and their position is guaranteed to be compatible ( in a sense to be defined below ) with the set of local alignment blocks .
this results in a motif prediction algorithm that retains the strengths of both approaches while correcting for their weaknesses . in completely alignable sequences ,
our approach is similar to existing sliding - window approaches , while in completely unalignable sequences , it is equivalent to the footprinter2 motif - discovery algorithm ( 7 ) . in between , it uses the local alignments to reduce the likelihood of finding sets of substrings that are not true orthologs , thereby increasing the specificity of the predictions .
the footprinter3 web server allows researchers to identify , in a set of orthologous genomic sequences , short conserved regions that are likely to be regulatory elements .
the user provides as input a set of unaligned orthologous nucleotide sequences , in fasta format .
typical inputs would contain from 3 to 20 orthologous ( or paralogous ) promoter regions of 1 kb each .
for example , the results in figure 1 were obtained by using the 1 kb promoter regions of the fos gene , an important leucine - zipper transcription factor involved in apoptosis , in human , mouse , dog , chicken , frog , tetraodon , fugu and zebrafish .
this allows the server to automatically establish the phylogenetic relationships between the input sequences , using previously published phylogenetic trees ( e.g. tree of life project ) . in cases where the sequences come from organisms absent from our phylogenetic database , or
if the sequences contain paralogs , the user is asked to provide a phylogenetic tree in newick format .
the first step performed by footprinter3 is to use the tba multiple alignment program ( 9 ) to identify local multiple alignment blocks .
an alignment block consists of two or more regions of the input sequences that share significant sequence similarity , typically over at least 50 nt .
alignment blocks can be considered as regions that are very likely to be orthologous . in the graphical output produced by footprinter3
regions from different species belonging to the same alignment block are shown with the same color .
for example , in figure 1 , the light - green block aligns 130 bp regions from the frog , chicken , human , dog and mouse , while other blocks are common to chicken and mammals ( e.g. the blue  gray block ) , common only to mammals ( e.g. the purple block ) or only to puffer fishes tetraodon and fugu ( aqua block ) .
note that no alignment is found between the fish sequences and the tetrapods sequences , nor is any alignment found in zebrafish .
besides the graphical view described here , the tba output file is also reported to the user .
the second step of footprinter3 is to search for conserved motifs [ sets of short ( 612 bp ) , highly conserved regions ] among the input sequences .
footprinter evaluates motif conservation using the parsimony score , defined as the minimal number of substitutions that need to have occurred during the evolution of the motif .
a motif is consistent with a set of alignment blocks if the substrings it contains could form a new alignment block that would not violate the partial order relation defined by the existing blocks [ see ( 9 ) ] .
for example , in figure 1 , a motif that would consist of a substring from the 5 end of the human sequence and one from the 3 end of the frog sequence would not be consistent with the alignment blocks , because in human it would be located to the left of the light - green alignment block , while , in frog , it would be located to the right of that same block .
when a motif contains a substring inside an alignment block , then only substrings aligned to it in other species are eligible , unless they come from a species that does not contribute to the alignment block .
for example , the green motif is located in an alignment block within mammals but is in an unaligned region in chicken .
a formal definition of consistency is rather technical and is available in ( 10 ) ( ) .
the motifs identified by footprinter3 are reported both graphically and in text format . in the graphical output , each motif is reported as a set of colored bars whose heights depend on the significance of the observed conservation . in figure 1 ,
the red motif consists of a substring of each of the input sequences ( with two candidates from zebrafish ) .
this motif is compatible with the alignment because ( i ) all its tetrapod instances are aligned within the light - green block , ( ii ) the fugu and tetraodon instances are aligned within the aqua block , and ( iii ) the set of substrings is consistent with all the other alignment blocks .
other motifs are found in only a subset of the species ( e.g. cyan motif in all three fish , dark green motif in chicken and mammals , etc . ) .
compared to the output obtained using the same parameters but without the alignment constraints ( supplementary figure s1 ) , the output of figure 1 has much higher specificity and improved readability .
in general , we observe using the alignment constraints improve the specificity by about 3050% , without a significant reduction in sensitivity .
a discussion of other options inherited from the previous versions of footprinter is available in ( 6 ) .
the most important of these is the ability of footprinter to find motifs that are only present in a subset of the sequences considered . in that mode
, footprinter will report a motif if the parsimony score of the substrings chosen is significantly low , given the divergence of the species in which it occurs [ see ( 7 ) for more details ] .
this allows the identification of binding sites that may have been lost or turned over in certain lineages .
a complete online help explains each input parameter and helps the user to choose appropriate parameter values and to interpret the results .
output of the footprinter3 web server when run on a set of vertebrate promoter regions of the fos gene .
each orthologous sequence extends 1 kb upstream of the start codon ( in most species , the 5-untranslated region 5-utr extends over 150 bp ) .
alignment blocks are shown in thin colored lines , while the motifs found appear as colored bars .
arrows indicate the position of experimentally verified transcription factor binding sites from transfac . below the graphical output
are part of the set of sequences used as input , with the motifs highlighted in the same color as in the graphical display .
the list of all motifs found , with the position of each of their substrings and the score statistics are shown on the right , again with a consistent color scheme .
the parameters used for the run were : motif size : 8 bp ; number of mutations allowed : 2 ; maximum number of mutations per branch : 1 ; use tba alignment : 
yes ; allow regulatory element losses :  yes ; spanned tree significance level : 
significant ; motif loss cost : 1 ; the running time of the query was less than 2 min .
the set of input sequences and the output files are available as example from the web server .
 footprinter3 is a web server for predicting transcription factor binding sites by using phylogenetic footprinting . until now 
 , phylogenetic footprinting approaches have been based either on multiple alignment analysis ( e.g. phylovista , phastcons ) , or on motif - discovery algorithms ( e.g. footprinter2 ) . 
 footprinter3 integrates these two approaches , making use of local multiple sequence alignment blocks when those are available and reliable , but also allowing finding motifs in unalignable regions . 
 the result is a set of predictions that joins the advantages of alignment - based methods ( good specificity ) to those of motif - based methods ( good sensitivity , even in the presence of highly diverged species ) . 
 footprinter3 is thus a tool of choice to exploit the wealth of vertebrate genomes being sequenced , as it allows taking full advantage of the sequences of highly diverged species ( e.g. chicken , zebrafish ) , as well as those of more closely related species ( e.g. mammals ) . 
 the footprinter3 web server is available at : . 
INTRODUCTION
Alignment-based versus motif-based phylogenetic footprinting
A unified approach
THE FOOTPRINTER3 WEB SERVER
SUPPLEMENTARY DATA
Supplementary Material
Figures and Tables