ancestral sequence reconstruction ( asr ) methods require as input both a multiple sequence alignment ( msa ) of existing sequences and a corresponding phylogenetic tree ( either provided or computed from the msa ) .
they output a statistical inference of the ancestral sequence at any internal node of the phylogenetic tree .
asr is being used in a steadily increasing number of evolutionary studies [ reviewed in ( 1 ) ] .
resurrection studies , ancestral sequences are synthesized and characterized , thus providing the ability to test evolutionary hypotheses regarding protein evolution . such an approach was successfully applied to study the evolution of the ancestral archosaur visual pigment rhodopsin ( 2 ) and the evolution of the steroid receptor ( 3 ) to name a few .
asr was also applied in various other contexts , including protein engineering ( 4 ) , the study of hiv evolution ( 5 ) and the study of variation in dna turnover due to indels and substitutions among eutherian mammalian lineages ( 6 ) .
there are two main paradigms for asr : maximum parsimony ( mp ) and probabilistic - based reconstruction .
the latter includes maximum likelihood ( ml ) and bayesian reconstructions , both of which were shown to outperform mp [ e.g. ( 7 ) ] .
one advantage of probabilistic - based approaches is that they also provide an estimate of the confidence in each inferred ancestral character , most often expressed as its posterior probability given the data .
while mp reconstruction has a time complexity linear in the number of sequences analyzed , efficient algorithms have also been developed for different types of ml - based reconstructions [ reviewed in ( 8) ] , with a time complexity that is linear with the number of sequence for most algorithms ( 9,10 ) and exponential in the worst case scenario for one variant ( joint reconstruction with among site rate variation ) .
notably , all algorithms can be efficiently used for large data sets in most practical cases ( 11 ) .
most of these tools apply the now standard dynamic programming algorithms to find the most probable sequence at a specific node ( 9,10 ) . however , they differ in various aspects , among which the most important ones are : ( i ) the way gaps in the alignment are treated ; ( ii ) the flexibility with respect to the allowed evolutionary models and the number of optional parameters ; ( iii ) the generation of near - optimal solutions ( i.e. for a given node of the tree , plausible sequences that only marginally differ from the single most likely ancestral sequence ) ; ( iv ) the graphical user interface ( gui ) and the ease of use . here we present the fastml web server , which aims to improve upon existing tools with respect to all these aspects , as detailed below .
fastml is freely available for use at http://fastml.tau.ac.il/ with no requirement of log - in . in asr algorithms ,
gaps are usually treated as unknown characters ( 10,12 ) or as an additional character ( 13 ) .
furthermore , treating gaps as unknown characters results in ancestral sequences that are longer than all present day sequences , which is unrealistic .
one possible way to overcome this limitation is to introduce a heuristic approach that maps indels to a phylogeny so that they maximize some ad hoc scoring function ( 6 ) . the gasp program ( 14 )
however , it uses an unrealistic model in which gaps in adjacent msa columns are assumed to be independent .
furthermore , the probabilities of gaps at internal nodes are not computed based on a continuous time markov model , which is used for reconstructing substitution events .
as described below , in fastml , we developed a different approach in which we first apply an indel - coding methodology that provides for each indel a presence (  1 ) or absence (  0 ) state in the input sequences .
fastml then applies an ml - based reconstruction algorithm for binary data to determine the probability of gap character state in the ancestral sequences . for protein - coding genes , amino acid - based reconstruction rather than codon - based reconstruction
this stems from two main reasons : ( i ) the availability of various empirical amino - acid substitution matrices that were inferred from a large collection of protein sequences ; ( ii ) for more diverged sequences , the synonymous substitutions are often saturated .
however , these models ignore the codon structure of coding sequences , and thus they may be less accurate compared to codon models that explicitly account for the chosen codon at each amino acid site . furthermore , reconstructing ancestral regulatory regions are expected to become more common with the increased availability of fully sequenced genomes .
thus , fastml allows reconstructing ancestral sequences using nucleotide substitution models , amino acid replacement models and codon models .
simulation studies have shown that at each specific position the most likely ancestral state has a high probability to reflect the 
however , this high accuracy reflects an average over all sites , many of which are conserved sites in which accurate reconstruction is trivial . in practice ,
the probability of the  true ancestral sequence to be identical to the reconstructed one across the entire sequence is rather small due to several highly variable sites .
furthermore , it was shown that the most likely reconstructed ancestor might be biased : it tends to favor common amino acids in a particular position over rare variants ( 15 ) . to account for this problem
, most programs not only provide the most likely character at each site , but also give the posterior probabilities of each ancestral character as output .
however , correct usage of these probabilities in studies utilizing ancestral sequences is not obvious . in the fastml web server , we do not only report these site - specific probabilities , but additionally we provide the set of the k most likely ancestral sequences at each node . since ancestral sequences are often used to infer protein variants that are more stable than all current day sequences ( 15 ) , this set provides a list from which protein engineers may choose to synthesize highly stable proteins .
fastml also provides , for each node a list of ancestral proteins sampled from the posterior distribution . in simulations ,
this set was shown to better represent the amino - acid composition and biochemical properties of the  true ancestral sequence compared with the most likely ancestral sequences ( 15 )
. details on the generation of alternative ancestral states are given in the overview section of the web server .
the novice user is provided with a user - friendly interface that requires only an msa as input .
the server further provides a rich graphical output that includes : ( i ) projection of the ancestral sequences onto the phylogeny ; ( ii ) color - scaled projection of the reconstruction probabilities at the internal nodes of the tree ; and ( iii ) a graphical logo of all possible alternative reconstructions .
given an msa and a phylogenetic tree , the ancestral reconstruction process can be divided into two parts : character reconstruction and indel reconstruction . the results of both reconstructions are integrated to provide the most probable ancestral sequences in each node of the phylogeny .
the minimal input of the web server is an msa of nucleotide , protein or codon sequences .
asr depends on a tree , which is computed from the msa using either the neighbor joining algorithm or using the ml tree search procedure as implemented in raxml ( 16 ) .
the first infers for each indel character whether or not a gap is present in the ancestral sequence .
the second algorithm then infers the most likely character states only in the non - gapped positions of the ancestral sequences .
a short description of the methodology is provided below and a more detailed one is available at http://fastml.tau.ac.il/ under the overview section . 

figure 1.a schematic flow chart of the fastml web server . a schematic flow chart of the fastml web server . to account for the dependence of insertions and deletions among sites
, the fastml server first employs the simple indel coding scheme ( 17 ) to code all indels in the data as binary ( presence\absence ) characters , each of which may represent a gap of multiple sites .
the binary data matrix is then provided as input to an ml - based ancestral indel reconstruction algorithm .
the evolutionary model for this indel reconstruction step allows for variable rates of insertions and deletions among indel sites , similar to the model that we have previously developed for phyletic patterns ( 18,19 ) .
the output of this step is the posterior probability for each indel site at each ancestral node of the phylogeny .
most likely character states in the ancestral nodes are reported only in positions that are inferred to be non - gapped with a probability 0.5 .
alternatively , users can select to reconstruct the ancestral indel states based on the mp approach ( 20 ) .
the previously described fastml algorithms are used to infer the most likely ancestral sequences ( 10,11 ) .
briefly , in joint reconstruction , the most likely set of ancestral states at all the internal nodes is inferred , while in marginal reconstruction the most likely sequence at a specific internal node is inferred , averaging over all possible ancestral states at all other nodes .
rate variation among sites is accounted for by assuming that the rate at each site is sampled from a discrete gamma distribution ( 21 ) .
the user is allowed to choose the evolutionary model that best fits the data analyzed . for amino acids ,
the server implements the dayhoff ( 22 ) , jtt ( 23 ) , wag ( 24 ) , lg ( 25 ) , mtrev ( 26 ) and cprev ( 27 ) replacement matrices ; for nucleotides , the jc ( 28 ) and the hky ( 29 ) substitution matrices are implemented . for codon characters ,
the server offers the m5 ( 30 ) , the empirical codon matrix ( 31 ) and the mec ( 32 ) models .
running time depends on the number of sequences and their length , the evolutionary model , the proportion of gaps and the reconstruction algorithm .
additionally , accounting for among site rate variation is significantly more complex for the joint reconstruction compared to the marginal reconstruction ( 11 ) . to aid users with estimating the running time for their data sets , the overview section of the server includes detailed information regarding the average running time on simulated data sets of various sizes , using different evolutionary models .
fastml provides the following outputs : 
 the posterior probability of each character ( or indel ) for each site at each ancestral node;msas augmented with the reconstructed ancestral sequences : one msa according to the joint reconstruction and a second according to the marginal reconstruction;the reconstructed phylogenetic tree;the k most probable ancestral sequences for each ancestral node ( where k is defined by the user);a set of l sequences sampled according to the posterior probabilities for each site and each node ( where l is defined by the user);a graphical visualization of the most probable asr at each node colored according to the posterior probabilities . a graphical logo representing the posterior probabilities of each possible character for each ancestral node is further provided using weblogo ( 33 ) ; anda projection of the ancestral sequences onto the phylogeny .
using jalview ( 34 ) , the user can view the asr at each internal node .
furthermore , the user can download the ancestral sequences of specific nodes or the sequences of an entire subtree . the posterior probability of each character ( or indel ) for each site at each ancestral node ; msas augmented with the reconstructed ancestral sequences : one msa according to the joint reconstruction and a second according to the marginal reconstruction ; the reconstructed phylogenetic tree ; the k most probable ancestral sequences for each ancestral node ( where k is defined by the user ) ; a set of l sequences sampled according to the posterior probabilities for each site and each node ( where l is defined by the user ) ; a graphical visualization of the most probable asr at each node colored according to the posterior probabilities .
a graphical logo representing the posterior probabilities of each possible character for each ancestral node is further provided using weblogo ( 33 ) ; and a projection of the ancestral sequences onto the phylogeny .
using jalview ( 34 ) , the user can view the asr at each internal node .
furthermore , the user can download the ancestral sequences of specific nodes or the sequences of an entire subtree .
fastml provides the following outputs : 
 the posterior probability of each character ( or indel ) for each site at each ancestral node;msas augmented with the reconstructed ancestral sequences : one msa according to the joint reconstruction and a second according to the marginal reconstruction;the reconstructed phylogenetic tree;the k most probable ancestral sequences for each ancestral node ( where k is defined by the user);a set of l sequences sampled according to the posterior probabilities for each site and each node ( where l is defined by the user);a graphical visualization of the most probable asr at each node colored according to the posterior probabilities . a graphical logo representing the posterior probabilities of each possible character for each ancestral node is further provided using weblogo ( 33 ) ; anda projection of the ancestral sequences onto the phylogeny .
using jalview ( 34 ) , the user can view the asr at each internal node .
furthermore , the user can download the ancestral sequences of specific nodes or the sequences of an entire subtree . the posterior probability of each character ( or indel ) for each site at each ancestral node ; msas augmented with the reconstructed ancestral sequences : one msa according to the joint reconstruction and a second according to the marginal reconstruction ; the reconstructed phylogenetic tree ; the k most probable ancestral sequences for each ancestral node ( where k is defined by the user ) ; a set of l sequences sampled according to the posterior probabilities for each site and each node ( where l is defined by the user ) ; a graphical visualization of the most probable asr at each node colored according to the posterior probabilities .
a graphical logo representing the posterior probabilities of each possible character for each ancestral node is further provided using weblogo ( 33 ) ; and a projection of the ancestral sequences onto the phylogeny .
using jalview ( 34 ) , the user can view the asr at each internal node .
furthermore , the user can download the ancestral sequences of specific nodes or the sequences of an entire subtree .
reconstructing the ancestral sequences of hiv-1 is a challenging task due to its fast rate of evolution .
nevertheless , asr was suggested to be of great value to hiv-1 vaccine design that aims to elicit an immune response against a broad spectrum of contemporary viral strains [ e.g. ( 35 ) ] .
specifically , the envelope protein ( env ) exhibits an extraordinary diversity ( up to 35% diversity among different hiv-1 subtypes ) , which is attributed to mutational escape of the virus from the host immune system .
the viral high mutation rate is also responsible for the ability of the virus to acquire resistance to drug treatments and is also a major obstacle toward developing an efficient vaccine . here
we run fastml on a sample of hiv-1 group m sequences from subtypes b and c taken from a previous study ( 36 ) .
our analysis is focused on the marginal reconstruction of the ancestral sequences of subtype c , which is the most prevalent subtype and accounts for nearly half of all infections globally , and subtype b , which is predominant in the western world and accounts for 12% of global infections .
sequences were aligned using mafft ( 37 ) . the alignment , running parameters and the results are provided in the web server s gallery .
several differences were found between clade b and clade c ancestral sequences , including both different character and indel assignments .
interestingly , some sites were reconstructed with high confidence in subtype c and low confidence in subtype b , and vice versa . among these sites
is position 592 in the msa , which corresponds to position 414 of gp120 , a derived protein of env .
fastml inferred that this site in the ancestral of subtype c was threonine with a high posterior probability ( 0.997 ) , while the reconstruction of the ancestor of subtype b is arginine with a much lower posterior probability ( 0.628 only ) .
the difference in the posterior probability between the ancestors of these two clades in this position may be explained by a previous analysis that suggested that the intensity of selection forces on this position is not constant among the various hiv-1 lineages ( 36 ) .
specifically , this position is highly conserved in subtype c but is variable in subtype b , which is directly reflected in the posterior probabilities .
we further used fastml to provide the 100 most likely ancestral sequences of the ancestral of subtype c. at the abovementioned site , threonine is always inferred , which is in agreement with its high posterior probability .
notably , the difference in log - likelihood between the most likely ancestral sequence at this node and the 100th most likely sequence is only 0.141 , indicating that both sequences are almost as likely to reflect the 
graphical representation of the marginal posterior probabilities of the reconstruction of hiv-1 env ancestral sequences of ( a ) subtype b ancestor and ( b ) subtype c ancestor .
a red rectangle highlights the different in the reconstruction of position 592 in the msa , as discussed in the text .
graphical representation of the marginal posterior probabilities of the reconstruction of hiv-1 env ancestral sequences of ( a ) subtype b ancestor and ( b ) subtype c ancestor .
a red rectangle highlights the different in the reconstruction of position 592 in the msa , as discussed in the text .
an israel science foundation [ 878/09 ] ; edmond j. safra bioinformatics center at tel - aviv university ( fellowship to o.p .
 ancestral sequence reconstruction is essential to a variety of evolutionary studies . here , we present the fastml web server , a user - friendly tool for the reconstruction of ancestral sequences . 
 fastml implements various novel features that differentiate it from existing tools : ( i ) fastml uses an indel - coding method , in which each gap , possibly spanning multiples sites , is coded as binary data . 
 fastml then reconstructs ancestral indel states assuming a continuous time markov process . 
 fastml provides the most likely ancestral sequences , integrating both indels and characters ; ( ii ) fastml accounts for uncertainty in ancestral states : it provides not only the posterior probabilities for each character and indel at each sequence position , but also a sample of ancestral sequences from this posterior distribution , and a list of the k - most likely ancestral sequences ; ( iii ) fastml implements a large array of evolutionary models , which makes it generic and applicable for nucleotide , protein and codon sequences ; and ( iv ) a graphical representation of the results is provided , including , for example , a graphical logo of the inferred ancestral sequences . 
 the utility of fastml is demonstrated by reconstructing ancestral sequences of the env protein from various hiv-1 subtypes . 
 fastml is freely available for all academic users and is available online at http://fastml.tau.ac.il/. 
Introduction
MATERIALS AND METHODS
FastML outputs
CASE STUDY
FUNDING