Ancestral reconstruction

425:, which is the chance of a purine being switched to a pyrimidine, or vice versa. These differences are not captured by maximum parsimony. However, just because some events are more likely than others does not mean that they always happen. We know that throughout evolutionary history there have been times when there was a large gap between what was most likely to happen, and what actually occurred. When this is the case, maximum parsimony may actually be more accurate because it is more willing to make large, unlikely leaps than maximum likelihood is. Maximum likelihood has been shown to be quite reliable in reconstructing character states, but it does not do as good of a job at giving accurate estimations of the stability of proteins. Maximum likelihood always overestimates the stability of proteins, which makes sense since it assumes that the proteins that were made and used were the most stable and optimal. The merits of maximum likelihood have been subject to debate, with some having concluded that maximum likelihood test represents a good medium between accuracy and speed. However, other studies have complained that maximum likelihood takes too much time and computational power to be useful in some scenarios. 3869:, HyPhy, and Mesquite also perform phylogenetic analysis of sequence data, but are designed to be more modular and customizable. HyPhy implements a joint maximum likelihood method of ancestral sequence reconstruction that can be readily adapted to reconstructing a more generalized range of discrete ancestral character states such as geographic locations by specifying a customized model in its batch language. Mesquite provides ancestral state reconstruction methods for both discrete and continuous characters using both maximum parsimony and maximum likelihood methods. It also provides several visualization tools for interpreting the results of ancestral reconstruction. MEGA is a modular system, too, but places greater emphasis on ease-of-use than customization of analyses. As of version 5, MEGA allows the user to reconstruct ancestral states using maximum parsimony, maximum likelihood, and empirical Bayes methods. 2962:. The "genome rearrangement problem", first posed by Watterson and colleagues, asks: given two genomes (permutations) and a set of allowable operations, what is the shortest sequence of operations that will transform one genome into the other? A generalization of this problem applicable to ancestral reconstruction is the "multiple genome rearrangement problem": given a set of genomes and a set of allowable operations, find (i) a binary tree with the given genomes as its leaves, and (ii) an assignment of genomes to the internal nodes of the tree, such that the total number of operations across the whole tree is minimized. This approach is similar to parsimony, except that the tree is inferred along with the ancestral sequences. Unfortunately, even the single genome rearrangement problem is 3008:

never occur; for example, migration between distant locales may never happen directly if air travel between the two places does not exist, so such migrations must pass through intermediate locales first. This means that there could be many parameters in the model which are zero or close to zero. To this end, Lemey and colleagues used a Bayesian procedure to not only estimate the parameters and ancestral states, but also to select which migration parameters are not zero; their work suggests that this procedure does lead to more efficient use of the data. They also explore the use of prior distributions that incorporate geographical structure or hypotheses about migration dynamics, finding that those they considered had little effect on the findings.

2853:(inferences drawn through comparison of related taxa) are often used to identify biological characteristics that do not evolve independently, which can reveal an underlying dependence. For example, the evolution of the shape of a finch's beak may be associated with its foraging behaviour. However, it is not advisable to search for these associations by the direct comparison of measurements or genetic sequences because these observations are not independent because of their descent from common ancestors. For discrete characters, this problem was first addressed in the framework of maximum parsimony by evaluating whether two characters tended to undergo a change on the same branches of the tree. 3065: 348:

an ancestral state reconstruction for this clade reveals that "hummingbird" is the most parsimonious ancestral state for the lower clade (plants D, E, F), that the ancestral states for the nodes in the top clade (plants A, B, C) are equivocal and that both "hummingbird" or "bee" pollinators are equally plausible for the pollination state at the root of the phylogeny. Supposing we have strong evidence from the fossil record that the root state is "hummingbird". Resolution of the root to "hummingbird" would yield the pattern of ancestral state reconstruction depicted by the symbols at the nodes with the state requiring the fewest changes circled.

847:. It is akin to summing over all combinations of ancestral states at all of the other nodes of the tree (including the root node), other than those for which data is available. Marginal reconstruction is finding the state at the current node that maximizes the likelihood integrating over all other states at all nodes, in proportion to their probability. Second, one may instead attempt to find the joint combination of ancestral character states throughout the tree which jointly maximizes the likelihood of the entire dataset. Thus, this approach is referred to as joint reconstruction. Not surprisingly, joint reconstruction is more 385:

technique liable to infer that one change occurred on a very short branch rather than multiple changes occurring on a very long branch, for example. In addition, it is possible that some branches of the tree could be experiencing higher selection and change rates than others, perhaps due to changing environmental factors. Some periods of time may represent more rapid evolution than others, when this happens parsimony becomes inaccurate. This shortcoming is addressed by model-based methods (both maximum likelihood and Bayesian methods) that infer the stochastic process of evolution as it unfolds along each branch of a tree.

352:

inaccurate. Natural selection and evolution do not work towards a goal, they simply select for or against randomly occurring genetic changes. Parsimony methods impose six general assumptions: that the phylogenetic tree you are using is correct, that you have all of the relevant data, in which no mistakes were made in coding, that all branches of the phylogenetic tree are equally likely to change, that the rate of evolution is slow, and that the chance of losing or gaining a characteristic is the same. In reality, assumptions are often violated, leading to several issues:

410:(ML) methods of ancestral state reconstruction treat the character states at internal nodes of the tree as parameters, and attempt to find the parameter values that maximize the probability of the data (the observed character states) given the hypothesis (a model of evolution and a phylogeny relating the observed sequences or taxa). In other words, this method assumes that the ancestral states are those which are statistically most likely, given the observed phenotypes. Some of the earliest ML approaches to ancestral reconstruction were developed in the context of 2925:

synthetic ancestral sequences obtained by maximum likelihood reconstruction have likewise shown that these ancestors are both functional and immunogenic, lending some credibility to these methods. Furthermore, ancestral reconstruction can potentially be used to infer the genetic sequence of the transmitted HIV variants that have gone on to establish the next infection, with the objective of identifying distinguishing characteristics of these variants (as a non-random selection of the transmitted population of viruses) that may be targeted for vaccine design.

4018: 432:. In the simplest of these, all characters undergo independent state transitions (such as nucleotide substitutions) at a constant rate over time. This basic model is frequently extended to allow different rates on each branch of the tree. In reality, mutation rates may also vary over time (due, for example, to environmental changes); this can be modelled by allowing the rate parameters to evolve along the tree, at the expense of having an increased number of parameters. A model defines transition probabilities from states 274:. Maximum parsimony considers all evolutionary events equally likely; maximum likelihood accounts for the differing likelihood of certain classes of event; and Bayeisan inference relates the conditional probability of an event to the likelihood of the tree, as well as the amount of uncertainty that is associated with that tree. Maximum parsimony and maximum likelihood yield a single most probable outcome, whereas Bayesian inference accounts for uncertainties in the data and yields a sample of possible trees. 343:

pollination, red representing "hummingbird" pollination, and black representing "wind" pollination, dual coloured branches are equally parsimonious for the two states coloured). Assignment of "hummingbird" as the root state (because of prior knowledge from the fossil record) leads to the pattern of ancestral states represented by symbols at the nodes of the phylogeny, the state requiring the fewest changes to give rise to the pattern observed at the tips is circled at each node.

2920:

their most recent common ancestor is closer to each of the two viruses than they are to each other. Thus, a vaccine designed for a common ancestor could have a better chance of being effective for a larger proportion of circulating strains. Another team took this idea further by developing a center-of-tree reconstruction method to produce a sequence whose total evolutionary distance to contemporary strains is as small as possible. Strictly speaking, this method was not

1958: 2688:, to model the evolution of traits. Stable processes, roughly speaking, behave as Brownian motions that also incorporate discontinuous jumps. This allows to appropriately model scenarios in which short bursts of fast trait evolution are expected. In this setting, maximum likelihood methods are poorly suited due to a rugged likelihood surface and because the likelihood may be made arbitrarily large, so Bayesian methods are more appropriate. 3977: 339: 1244:

events happened in the order they did, while recognizing the potential for error and uncertainty. Overall, it is the most accurate method for reconstructing ancestral genetic sequences, as well as protein stability. Unlike the other two methods, Bayesian inference yields a distribution of possible trees, allowing for more accurate and easily interpretable estimates of the variance of possible outcomes.

860:. If the rate of evolution for a specific character accelerates on a branch of the phylogeny, then the amount of evolution that has occurred on that branch will be underestimated for a given length of the branch and assuming a constant rate of evolution for that character. In addition to that, it is difficult to distinguish heterotachy from variation among characters in rates of evolution. 883:. In the context of ancestral reconstruction, the objective is to infer the posterior probabilities of ancestral character states at each internal node of a given tree. Moreover, one can integrate these probabilities over the posterior distributions over the parameters of the evolutionary model and the space of all possible trees. This can be expressed as an application of 3076:. Displayed sequences do not correspond to the original paper, but were derived from the notation in the authors' companion paper as follows: A (63A-65B), B (65C-68D), C (69A-70A), D (70B-70D), E (71A-71B), F (71A-73C), G (74A-74C), H (75A-75C), I (76A-76B), J (76C-77B), K (78A-79D), L (80A-81D). Inversions inferred by the authors are highlighted in blue along branches. 292:", refers to the principle of selecting the simplest of competing hypotheses. In the context of ancestral reconstruction, parsimony endeavours to find the distribution of ancestral states within a given tree which minimizes the total number of character state changes that would be necessary to explain the states observed at the tips of the tree. This method of 2899:

lead to the discoveries of new biochemical functions that have been lost in modern proteins. It also allows insights into the biology and ecology of extinct organisms. Although the majority of ancestral reconstructions have dealt with proteins, it has also been used to test evolutionary mechanisms at the level of bacterial genomes and primate gene sequences.

2706:

missing data includes the states of extinct species, the relative rates of evolutionary changes, knowledge of initial character states, and the accuracy of phylogenetic trees. In all cases where ancestral trait reconstruction is used, findings should be justified with an examination of the biological data that supports model based conclusions. Griffith O.W.

1991: 2887:

fast, and scientifically practical. This concept has been applied to identify co-evolving residues in protein sequences using more advanced methods for the reconstruction of phylogenies and ancestral sequences. For example, ancestral reconstruction has been used to identify co-evolving residues in proteins encoded by RNA virus genomes, particularly in HIV.

1355:. Computationally, the empirical Bayes method is akin to the maximum likelihood reconstruction of ancestral states except that, rather than searching for the ML assignment of states based on their respective probability distributions at each internal node, the probability distributions themselves are reported directly. 2778:". Dietary ancestral state reconstruction using maximum parsimony recover 2 major shifts from an insectivorous state: one to granivory, and one to folivory. Maximum-likelihood ancestral state reconstruction recovers broadly similar results, with one significant difference: the common ancestor of the tree finch ( 1087: 693: 444:(in units of evolutionary time). The likelihood of a phylogeny is computed from a nested sum of transition probabilities that corresponds to the hierarchical structure of the proposed tree. At each node, the likelihood of its descendants is summed over all possible ancestral character states at that node: 2442:: in brief, an Ornstein-Uhlenbeck process is a continuous stochastic process that behaves like a Brownian motion, but attracted toward some central value, where the strength of the attraction increases with the distance from that value. This is useful for modelling scenarios where the trait is subject to 330:. In the latter case, it is implied that a character state change has occurred between the ancestor and one of its two immediate descendants. Each such event counts towards the algorithm's cost function, which may be used to discriminate among alternative trees on the basis of maximum parsimony. Next, a 3873:

genomics using ancestral sequence reconstruction. SIMMAP stochastically maps mutations on phylogenies. BayesTraits analyses discrete or continuous characters in a Bayesian framework to evaluate models of evolution, reconstruct ancestral states, and detect correlated evolution between pairs of traits.

2790:) clades are most likely granivorous rather than insectivorous (as judged by parsimony). In this case, this difference between ancestral states returned by maximum parsimony and maximum likelihood likely occurs as a result of the fact that ML estimates consider branch lengths of the phylogenetic tree. 2705:

is widely used to infer the ecological, phenotypic, or biogeographic traits associated with ancestral nodes in a phylogenetic tree. All methods of ancestral trait reconstructions have pitfalls, as they use mathematical models to predict how traits have changed with large amounts of missing data. This

1377:

Put simply, the empirical Bayes approach calculates the probabilities of various ancestral states for a specific tree and model of evolution. By expressing the reconstruction of ancestral states as a set of probabilities, one can directly quantify the uncertainty for assigning any particular state to

1361:

for ancestral reconstruction require the investigator to assume that the evolutionary model parameters and tree are known without error. When the size or complexity of the data makes this an unrealistic assumption, it may be more prudent to adopt the fully hierarchical Bayesian approach and infer the

384:

Parsimony methods implicitly assume that the same amount of evolutionary time has passed along every branch of the tree. Thus, they do not account for variation in branch lengths in the tree, which are often used to quantify the passage of evolutionary or chronological time. This limitation makes the

347:

For example, consider a phylogeny recovered for a genus of plants containing 6 species A - F, where each plant is pollinated by either a "bee", "hummingbird" or "wind". One obvious question is what the pollinators at deeper nodes were in the phylogeny of this genus of plants. Under maximum parsimony,

249:

of the entire sample of taxa. In the context of ancestral reconstruction, a phylogeny is often treated as though it were a known quantity (with Bayesian approaches being an important exception). Because there can be an enormous number of phylogenies that are nearly equally effective at explaining the

90:

are essentially a variation of ancient ones, access to ancient sequences may identify other variations and organisms which could have arisen from those sequences. In addition to genetic sequences, one might attempt to track the changing of one character trait to another, such as fins turning to legs.

3954:

The development and application of computational algorithms for ancestral reconstruction continues to be an active area of research across disciplines. For example, the reconstruction of sequence insertions and deletions (indels) has lagged behind the more straightforward application of substitution

3920:

of binary character evolution). and BiSSE (Binary State Speciation and Extinction) models. Lagrange performs analyses on reconstruction of geographic range evolution on phylogenetic trees. Phylomapper is a statistical framework for estimating historical patterns of gene flow and ancestral geographic

3007:

Treating locations as discrete states (countries, cities, etc.) allows for the application of the discrete-state models described above. However, unlike in a model where the state space for the trait is small, there may be many locations, and transitions between certain pairs of states may rarely or

2995:

Ancestral reconstruction is not limited to biological traits. Spatial location is also a trait, and ancestral reconstruction methods can infer the locations of ancestors of the individuals under consideration. Such techniques were used by Lemey and colleagues to geographically trace the ancestors of

2919:

design efforts, as opposed to sequences isolated from patients in the present day. Because HIV is extremely diverse, a vaccine designed to work on one patient's viral population might not work for a different patient, because the evolutionary distance between these two viruses may be large. However,

2898:

reconstruction allows for the recreation of protein and DNA evolution in the laboratory so that it can be studied directly. With respect to proteins, this allows for the investigation of the evolution of present-day molecular structure and function. Additionally, ancestral protein reconstruction can

855:

ML-based methods of ancestral reconstruction tend to provide greater accuracy than MP methods in the presence of variation in rates of evolution among characters (or across sites in a genome). However, these methods are not yet able to accommodate variation in rates of evolution over time, otherwise

334:

of the tree is performed, proceeding from the root towards the tips. Character states are then assigned to each descendant based on which character states it shares with its parent. Since the root has no parent node, one may be required to select a character state arbitrarily, specifically when more

3964:

of the genetic composition of a rapidly evolving population, such as RNA viruses or tumour cells, in a relatively short amount of time. At the same time, the massive amount of data and platform-specific sequencing error profiles has created new bioinformatic challenges for processing these data for

1977:

associated with different character states; it may also be straightforwardly extended to a more general multiple-discrete-state model. In its most basic form, this model involves six parameters: two speciation rates (one each for lineages in states 0 and 1); similarly, two extinction rates; and two

1255:

One of the first implementations of a Bayesian approach to ancestral sequence reconstruction was developed by Yang and colleagues, where the maximum likelihood estimates of the evolutionary model and tree, respectively, were used to define the prior distributions. Thus, their approach is an example

842:

Rather than compute the overall likelihood for alternative trees, the problem for ancestral reconstruction is to find the combination of character states at each ancestral node with the highest marginal maximum likelihood. Generally speaking, there are two approaches to this problem. First, one can

3085:

from different geographic locations, and observed that one configuration, which they called "standard", was the most common throughout all the studied areas. Remarkably, they also noticed that four different strains could be obtained from the standard sequence by a single inversion, and two others

1424:

Many models have been developed to estimate ancestral states of discrete and continuous characters from extant descendants. Such models assume that the evolution of a trait through time may be modelled as a stochastic process. For discrete-valued traits (such as "pollinator type"), this process is

863:

Since ML (unlike maximum parsimony) requires the investigator to specify a model of evolution, its accuracy may be affected by the use of a grossly incorrect model (model misspecification). Furthermore, ML can only provide a single reconstruction of character states (what is often referred to as a

253:

Ancestral reconstruction can be thought of as the direct result of applying a hypothetical model of evolution to a given phylogeny. When the model contains one or more free parameters, the overall objective is to estimate these parameters on the basis of measured characteristics among the observed

3872:

The Bayesian analysis of genetic sequences may confer greater robustness to model misspecification. MrBayes allows inference of ancestral states at ancestral nodes using the full hierarchical Bayesian approach. The PREQUEL program distributed in the PHAST package performs comparative evolutionary

2924:

reconstruction, as the center-of-tree (COT) sequence does not necessarily represent a sequence that has ever existed in the evolutionary history of the virus. However, Rolland and colleagues did find that, in the case of HIV, the COT virus was functional when synthesized. Similar experiments with

2886:

The reconstruction of ancient proteins and DNA sequences has only recently become a significant scientific endeavour. The developments of extensive genomic sequence databases in conjunction with advances in biotechnology and phylogenetic inference methods have made ancestral reconstruction cheap,

2857:

identified this problem for continuous character evolution and proposed a solution similar to ancestral reconstruction, in which the phylogenetic structure of the data was accommodated statistically by directing the analysis through computation of "independent contrasts" between nodes of the tree

1986:

In the case where the trait instead takes non-discrete values, one must instead turn to a model where the trait evolves as some continuous process. Inference of ancestral states by maximum likelihood (or by Bayesian methods) would proceed as above, but with the likelihoods of transitions in state

1529:

states; when it reaches a given state, it starts an exponential "clock" for each of the other states that it can step to. It then "races" the clocks against each other, and it takes a step towards the state whose clock is the first to ring. In such a model, the parameters are the transition rates

1398:

Ancestral reconstruction can be informed by the observed states in historical samples of known age, such as fossils or archival specimens. Since the accuracy of ancestral reconstruction generally decays with increasing time, the use of such specimens provides data that are closer to the ancestors

1243:

Bayesian inference is the method that many have argued is the most accurate. In general, Bayesian statistical methods allow investigators to combine pre-existing information with new hypothesis. In the case of evolution, it combines the likelihood of the data observed with the likelihood that the

342:

Phylogeny of a hypothetical genus of plants with pollination states of either "bees", "hummingbirds" or "wind" denoted by pictures at the tips. Pollination state nodes in the phylogenetic tree inferred under maximum parsimony are coloured on the branches leading into them (yellow represents "bee"

116:

has taken and when evolutionary events occurred. No matter how well the model approximates the actual evolutionary history, however, one's ability to accurately reconstruct an ancestor deteriorates with increasing evolutionary time between that ancestor and its observed descendants. Additionally,

2837:

of continuous character evolution, which accommodates rare changes of large magnitude. Under a stable model, ancestral mammals retained a low body mass through early diversification, with large increases in body mass coincident with the origin of several Orders of large body massed species (e.g.

397:

When considering a single character state, parsimony will automatically assume that two organisms that share that characteristic will be more closely related than those who do not. For example, just because dogs and apes have fur does not mean that they are more closely related than apes are to

3046:

analysis (DIVA; parsimony), and dispersal-extinction-cladogenesis (DEC; maximum-likelihood). Results indicated that both parsimony methods performed poorly, which was likely due to the fact that parsimony methods do not consider branch lengths. Both maximum-likelihood methods performed better;

3937:

Finally, there are several web-server based applications that allow investigators to use maximum likelihood methods for ancestral reconstruction of different character types without having to install any software. For example, Ancestors is web-server for ancestral genome reconstruction by the

3928:

between species. ANGES compares extant related genomes through ancestral reconstruction of genetic markers. BADGER uses a Bayesian approach to examining the history of gene rearrangement. Count reconstructs the evolution of the size of gene families. EREM analyses the gain and loss of genetic

2870:

at different locations of a protein may evolve non-independently because they have a direct physicochemical interaction, or indirectly by their interactions with a common substrate or through long-range interactions in the protein structure. Conversely, the folded structure of a protein could

1301:

from the posterior likelihood, and prior terms of the formula. Moreover, Yang and colleagues used the empirical distribution of site patterns (i.e., assignments of nucleotides to tips of the tree) in their alignment of observed nucleotide sequences in the denominator in place of exhaustively

196:

Thus, ancestral reconstruction has its roots in several disciplines. Today, computational methods for ancestral reconstruction continue to be extended and applied in a diversity of settings, so that ancestral states are being inferred not only for biological characteristics and the molecular

3054:

Another maximum likelihood method recovers the phylogeographic history of a gene by reconstructing the ancestral locations of the sampled taxa. This method assumes a spatially explicit random walk model of migration to reconstruct ancestral locations given the geographic coordinates of the

351:

Parsimony methods are intuitively appealing and highly efficient, such that they are still used in some cases to seed maximum likelihood optimization algorithms with an initial phylogeny. However, the underlying assumption that evolution attained a certain end result as fast as possible is

175:, one of the precursors of modern phylogenetics. Cladistic methods, which appeared as early as 1901, infer the evolutionary relationships of species on the basis of the distribution of shared characteristics, of which some are inferred to be descended from common ancestors. Furthermore, 3897:' function, including maximum likelihood. Phyrex implements a maximum parsimony-based algorithm to reconstruct ancestral gene expression profiles, in addition to a maximum likelihood method for reconstructing ancestral genetic sequences (by wrapping around the baseml function in PAML). 258:

is an important exception to this paradigm: though it has been shown that there are circumstances under which it is the maximum likelihood estimator, at its core, it is simply based on the heuristic that changes in character state are rare, without attempting to quantify that rarity.

1865: 3955:

models. Bouchard-Côté and Jordan recently described a new model (the Poisson Indel Process) which represents an important advance on the archetypal Thorne-Kishino-Felsenstein model of indel evolution. In addition, the field is being driven forward by rapid advances in the area of

3856:

The majority of these software packages are designed for analyzing genetic sequence data. For example, PAML is a collection of programs for the phylogenetic analysis of DNA and protein sequence alignments by maximum likelihood. Ancestral reconstruction can be performed using the

6631:

Griffith OW, Blackburn DG, Brandley MC, Van Dyke JU, Whittington CM, Thompson MB (September 2015). "Ancestral state reconstructions require biological evidence to test evolutionary hypotheses: A case study examining the evolution of reproductive mode in squamate reptiles".

1614: 1408:); these results were verified by computer simulation. This failure of ancestral reconstruction was attributed to a directional bias in the evolution of plaque size (from large to small plaque diameters) that required the inclusion of "fossilized" samples to address. 2838:

ungulates). By contrast, simulation under a Brownian motion model recovered a less realistic, order of magnitude larger body mass among ancestral mammals, requiring significant reductions in body size prior to the evolution of Orders exhibiting small body size (e.g.

1509:. The typical means of modelling evolution of this trait is via a continuous-time Markov chain, which may be briefly described as follows. Each state has associated to it rates of transition to all of the other states. The trait is modelled as stepping between the 3132:. The following table is not meant to be a comprehensive itemization of all available packages, but provides a representative sample of the extensive variety of packages that implement methods of ancestral reconstruction with different strengths and features. 2911:(HIV) evolve at an extremely rapid rate, orders of magnitude faster than mammals or birds. For these organisms, ancestral reconstruction can be applied on a much shorter time scale; for example, in order to reconstruct the global or regional progenitor of an 170:

relating the observed protein sequences, but also the ancestral protein sequence at the earliest point (root) of this tree. However, the idea of reconstructing ancestors from measurable biological characteristics had already been developing in the field of

1753:; finally, choose the ancestral state which maximizes this. One may also use this substitution model as the basis for a Bayesian inference procedure, which would consider the posterior belief in the state of an ancestral node given some user-chosen prior. 137:

that has already been inferred from the same data. While convenient, this approach has the disadvantage that its results are contingent on the accuracy of a single phylogenetic tree. In contrast, some researchers advocate a more computationally intensive

5842:

Pupko T, Pe'er I, Hasegawa M, Graur D, Friedman N (August 2002). "A branch-and-bound algorithm for the inference of ancestral amino-acid sequences when the replacement rate varies among sites: Application to the evolution of five gene families".

1381:

Whether the hierarchical Bayes method confers a substantial advantage in practice remains controversial, however. Moreover, this fully Bayesian approach is limited to analyzing relatively small numbers of sequences or taxa because the space of

359:

Fitch's method assumes that changes between all character states are equally likely to occur; thus, any change incurs the same cost for a given tree. This assumption is often unrealistic and can limit the accuracy of such methods. For example,

1403:

were propagated to generate an artificial phylogeny. In revisiting these experimental data, Oakley and Cunningham found that maximum parsimony methods were unable to accurately reconstruct the known ancestral state of a continuous character

1411:

Studies of both mammalian carnivores and fishes have demonstrated that without incorporating fossil data, the reconstructed estimates of ancestral body sizes are unrealistically large. Moreover, Graham Slater and colleagues showed using

1378:

an ancestor. On the other hand, the hierarchical Bayes approach averages these probabilities over all possible trees and models of evolution, in proportion to how likely these trees and models are, given the data that has been observed.

892: 450: 2679:

though Brownian motion is appealing and tractable as a model of continuous evolution, it does not permit non-neutrality in its basic form, nor does it provide for any variation in the rate of evolution over time. Instead, one may use a

1862:, regardless of their start and end states. Some transitions may be disallowed by declaring that their rates are simply 0; this may be the case, for example, if certain states cannot be reached from other states in a single transition. 864:"point estimate") — when the likelihood surface is highly non-convex, comprising multiple peaks (local optima), then a single point estimate cannot provide an adequate representation, and a Bayesian approach may be more suitable. 2933:

Rather than inferring the ancestral DNA sequence, one may be interested in the larger-scale molecular structure and content of an ancestral genome. This problem is often approached in a combinatorial framework, by modelling genomes as

3127:

There are many software packages available which can perform ancestral state reconstruction. Generally, these software packages have been developed and maintained through the efforts of scientists in related fields and released under

1399:

being reconstructed and will most likely improve the analysis, especially when rates of character change vary through time. This concept has been validated by an experimental evolutionary study in which replicate populations of

1972:

The binary state speciation and extinction model (BiSSE) is a discrete-space model that does not directly follow the framework of those mentioned above. It allows estimation of ancestral binary character states jointly with

3921:

locations. RASP infers ancestral states using statistical dispersal-vicariance analysis, Lagrange, Bayes-Lagrange, BayArea and BBM methods. VIP infers historical biogeography by examining disjunct geographic distributions.

3102:

have been performed based on the observed analogues in present-day languages. Typically, these analyses are carried out manually using the "comparative method". First, words from different languages with a common etymology

1897:: in this model, the state space is ordered (so that, for example, state 1 is smaller than state 2, which is smaller than state 3), and transitions may only occur between adjacent states. This model contains two parameters 3080:

The first consideration of the multiple genome rearrangement problem, long before its formalization in terms of permutations, was presented by Sturtevant and Dobzhansky in 1936. They examined genomes of several strains of

1868:

Example of a four-state 1-parameter Markov chain model. Note that in this diagram, transitions between states A and D have been disallowed; it is conventional to not draw the arrow rather than to draw it with a rate of

3041:

was used together with information of their geographic ranges to compare four methods of ancestral range reconstruction. The team compared Fitch parsimony, (FP; parsimony) stochastic mapping (SM; maximum likelihood),

1260:

to compute the posterior probabilities of ancestral character states; this method was first implemented in the software package PAML. In terms of the above Bayesian rule formulation, the empirical Bayes method fixes

3905: 3959:

technology, where sequences are generated from millions of nucleic acid templates by extensive parallelization of sequencing reactions in a custom apparatus. These advances have made it possible to generate a

6555:

Cooper, N., G. H. Thomas, C. Venditti, A. Meade, and R. P. Freckleton. 2015. A cautionary note on the use of Ornstein Uhlenbeck models in macroevolutionary studies. Biological Journal of the Linnean Society.

1608: 2762:. These data allow testing of hypotheses concerning the timing and ordering of character state changes through time via ancestral state reconstruction. During the dry season, the diets of the 13 species of 851:

than marginal reconstruction. Nevertheless, efficient algorithms for joint reconstruction have been developed with a time complexity that is generally linear with the number of observed taxa or sequences.

2973:

reconstruction. Chromosome painting is currently the main experimental technique. Recently, researchers have developed computational methods to reconstruct the ancestral karyotype by taking advantage of

1416:

that incorporating fossil data into prior distributions improved both the Bayesian inference of ancestral states and evolutionary model selection, relative to analyses using only contemporaneous data.

7604:"Human immunodeficiency virus type 1 subtype B ancestral envelope protein is functional and elicits neutralizing antibodies in rabbits similar to those elicited by a circulating subtype B envelope" 897: 9639: 1751: 428:

These approaches employ the same probabilistic framework as used to infer the phylogenetic tree. In brief, the evolution of a genetic sequence is modelled by a time-reversible continuous time

7895:

Murphy WJ, Larkin DM, Everts-van der Wind A, Bourque G, Tesler G, Auvil L, et al. (July 2005). "Dynamics of mammalian chromosome evolution inferred from multispecies comparative maps".

6675:

Erkenbrack EM, Ako-Asare K, Miller E, Tekelenburg S, Thompson JR, Romano L (January 2016). "Ancestral state reconstruction by comparative analysis of a GRN kernel operating in echinoderms".

1366:(MCMC) methods to sample ancestral sequences from this joint posterior distribution. A similar approach was also used to reconstruct the evolution of symbiosis with algae in fungal species ( 3061:, this method recovered recent northward expansion, higher per-generation dispersal distance in the recently colonized region, a non-central ancestral location, and directional migration. 2978:. Furthermore, comparative genomics and ancestral genome reconstruction has been applied to identify ancient horizontal gene transfer events at the last common ancestor of a lineage (e.g. 2436:), and the model assumes that the trait evolves freely without a bias toward increase or decrease, and that the rate of change is constant throughout the branches of the phylogenetic tree. 1362:

joint posterior distribution over the ancestral character states, model, and tree. Huelsenbeck and Bollback first proposed a hierarchical Bayes method to ancestral reconstruction by using

2673:

and the process becomes a Brownian motion. Because of this, the models may be nested, and log-likelihood ratio tests discerning which of the two models is appropriate may be carried out.

9629: 6245:

Finarelli JA, Flynn JJ (April 2006). "Ancestral state reconstruction of body size in the Caniformia (Carnivora, Mammalia): the effects of incorporating data from the fossil record".

9624: 3086:

could be related by a second inversion. This allowed them to hypothesize a phylogeny for the sequences, and to infer that the standard sequence was probably also the ancestral one.

2817:, one of the three main subclades of the lineage, have undergone a major evolutionary increase in the proportion of fast-oxidative glycolytic fibers in their iliofibularis muscles. 1670: 311:

that proceeds from the tips toward the root of a tree by visiting descendant (child) nodes before their parents. Initially, we are determining the set of possible character states

2716:, developmental gene expression, and functional divergence of the evolutionary past. For a review of biological and computational techniques of ancestral reconstruction see Chang 368:

in the evolution of nucleic acids. This assumption can be relaxed by assigning differential costs to specific character state changes, resulting in a weighted parsimony algorithm.

250:

data, reducing the subset of phylogenies supported by the data to a single representative, or point estimate, can be a convenient and sometimes necessary simplifying assumption.

237:

of the tree that are progressively connected by branches to their common ancestors, which are represented by the branching points of the tree that are usually referred to as the

6933:

Maddison WP (May 1990). "A Method for Testing the Correlated Evolution of Two Binary Characters: Are Gains or Losses Concentrated on Certain Branches of a Phylogenetic Tree?".

1978:

rates of character change. This model allows for hypothesis testing on the rates of speciation/extinction/character change, at the cost of increasing the number of parameters.

2875:

through residue contacts, was published by Shindyalov and colleagues. Phylogenies relating 67 different protein families were generated by a distance-based clustering method (

3115:, although performed manually. Finally, likely ancestral sounds are hypothesised by manual inspection and various heuristics (such as the fact that most languages have both 1953: 1924: 1160: 2140: 2078: 2045: 2407: 1692: 1610:, which can be estimated using, for example, maximum likelihood methods, where one maximizes over the set of all possible configurations of states of the ancestral nodes. 1238: 1201: 2571: 2434: 2169: 1507: 2107: 6883:

Bonine KE, Gleeson TT, Garland T (December 2005). "Muscle fiber-type variation in lizards (Squamata) and phylogenetic reconstruction of hypothesized ancestral states".

803:

is the set of all possible character states (for example, the nucleotides A, C, G, and T). Thus, the objective of ancestral reconstruction is to find the assignment to

54:, ancestral reconstruction can be used to recover different kinds of ancestral character states of organisms that lived millions of years ago. These states include the 1082:{\displaystyle {\begin{aligned}P(S|D,\theta )&={\frac {P(D|S,\theta )P(S|\theta )}{P(D|\theta )}}\\&\propto P(D|S,\theta )P(S|\theta )P(\theta )\end{aligned}}} 688:{\displaystyle L_{x}=\sum _{S_{x}\in \Omega }P(S_{x})\left(\sum _{S_{y}\in \Omega }P(S_{y}|S_{x},t_{xy})L_{y}\sum _{S_{z}\in \Omega }P(S_{z}|S_{x},t_{xz})L_{z}\right)} 117:

more realistic models of evolution are inevitably more complex and difficult to calculate. Progress in the field of ancestral reconstruction has relied heavily on the

2631: 2591: 1712: 1639: 1353: 1299: 1279: 1117: 801: 1789: 773: 2842:). Thus stable models recover a more realistic picture of mammalian body mass evolution by permitting large transformations to occur on a small subset of branches. 828: 739: 8943:

Arias JS, Szumik CA, Goloboff PA (December 2011). "Spatial analysis of vicariance: a method for using direct geographical information in historical biogeography".

1329: 3942:

regions. FastML is a web-server for probabilistic reconstruction of ancestral sequences by maximum likelihood that uses a gap character model for reconstructing

9123:"EREM: Parameter Estimation and Ancestral Reconstruction by Expectation-Maximization Algorithm for a Probabilistic Model of Genomic Binary Characters Evolution" 3035:

patterns often requires reconstructing ancestral ranges of species on phylogenetic trees. For instance, a well-resolved phylogeny of plant species in the genus

2671: 2651: 2611: 2544: 2524: 2504: 2484: 2464: 2377: 2357: 2337: 2317: 2297: 2277: 2257: 2237: 2217: 2197: 2012: 1893: 1860: 1836: 1814: 1527: 1475: 7019:

Shindyalov IN, Kolchanov NA, Sander C (March 1994). "Can three-dimensional contacts in protein structures be predicted by analysis of correlated mutations?".

3929:

features encoded by binary characters. PARANA performs parsimony based inference of ancestral biological networks that represent gene loss and duplication.

1617:

A general two-state Markov chain representing the rate of jumps from allele a to allele A. The different types of jumps are allowed to have different rates.

843:

assign the most likely character state to each ancestor independently of the reconstruction of all other ancestral states. This approach is referred to as

1374:

for MCMC explores the joint posterior distribution by accepting or rejecting parameter assignments on the basis of the ratio of posterior probabilities.

4365:

Brooks DR (1999). "Phylogenies and the Comparative Method in Animal Behavior, Edited by Emı̀ia P. Martins, Oxford University Press, 1996. X+415 pp".

2915:

that has spanned decades rather than millions of years. A team around Brian Gaschen proposed that such reconstructed strains be used as targets for

2871:

potentially be inferred from the distribution of residue interactions. One of the earliest applications of ancestral reconstruction, to predict the

7216:

Jermann TM, Opitz JG, Stackhouse J, Benner SA (March 1995). "Reconstructing the evolutionary history of the artiodactyl ribonuclease superfamily".

3377: 1839: 7369:"Genome diversification in phylogenetic lineages I and II of Listeria monocytogenes: identification of segments unique to lineage II populations" 1955:: one for the rate of increase of state (e.g. 0 to 1, 1 to 2, etc.), and one for the rate of decrease in state (e.g. from 2 to 1, 1 to 0, etc.). 429: 6202:

Oakley TH, Cunningham CW (April 2000). "Independent contrasts succeed where ancestor reconstruction fails in a known bacteriophage phylogeny".

3866: 1247:

We have given two formulations above to emphasize the two different applications of Bayes' theorem, which we discuss in the following section.

6772:

Chang BS, Ugalde JA, Matz MV (2005). "Applications of ancestral protein reconstruction in understanding protein function: GFP-like proteins".

5880:"Difficulties in testing for covarion-like properties of sequences under the confounding influence of changing proportions of variable sites" 6856:

Maddison WP (1991). "Squared-change parsimony reconstructions of ancestral states for continuous-valued characters on a phylogenetic tree".

8892:

Yu Y, Harris AJ, He X (August 2010). "S-DIVA (Statistical Dispersal-Vicariance Analysis): A tool for inferring biogeographic histories".

5243:

Felsenstein J (1973). "Maximum Likelihood and Minimum-Steps Methods for Estimating Evolutionary Trees from Data on Discrete Characters".

3865:

scripts that wrap the ancestral reconstruction functions of PAML for batch processing and greater ease-of-use. Software packages such as

3047:

however, DEC analyses that additionally allow incorporation of geological priors gave more realistic inferences about range evolution in

8277:"Inversions in the Third Chromosome of Wild Races of Drosophila Pseudoobscura, and Their Use in the Study of the History of the Species" 9634: 8841:

Pagel M (1994). "Detecting Correlated Evolution on Phylogenies: A General Method for the Comparative Analysis of Discrete Characters".

421:, which is a type of point mutation from one purine to another, or from one pyrimidine to another is much more likely to happen than a 7457:

Gaschen B, Taylor J, Yusim K, Foley B, Gao F, Lang D, et al. (June 2002). "Diversity considerations in HIV-1 vaccine selection".

1533: 6159:

Hillis DM, Bull JJ, White ME, Badgett MR, Molineux IJ (January 1992). "Experimental phylogenetics: generation of a known phylogeny".

3912:

provides tools for reconstructing ancestral geographic locations from observed sequences annotated with location data using Bayesian

3111:

biological sequences. Second, correspondences between individual sounds in the cognates are identified, a step similar to biological

183:

articulated the principles of ancestral reconstruction in a phylogenetic context in 1938, when inferring the evolutionary history of

7056:"Covariation of mutations in the V3 loop of human immunodeficiency virus type 1 envelope protein: an information theoretic analysis" 5387:

Li G, Steel M, Zhang L (August 2008). "More taxa are not necessarily better for the reconstruction of ancestral character states".

4968:

Tuffley C, Steel M (May 1997). "Links between maximum likelihood and maximum parsimony under a simple model of site substitution".

2833:

models, Elliot and Mooers showed that the evolutionary process describing mammalian body mass evolution is best characterized by a

82:

of an ancestral population or species (ancestral range reconstruction). This is desirable because it allows us to examine parts of

6280:

Albert JS, Johnson DM, Knouft JH (2009). "Fossils provide better estimates of ancestral body size than do extant taxa in fishes".

5699: 4029: 1163: 7997:"Ancestral genome reconstruction identifies the evolutionary basis for trait acquisition in polyphosphate accumulating bacteria" 4421:

Pupko T, Pe'er I, Shamir R, Graur D (June 2000). "A fast algorithm for joint reconstruction of ancestral amino acid sequences".

7653:"An evaluation of phylogenetic methods for reconstructing transmitted HIV variants using longitudinal clonal HIV sequence data" 3019:

also receiving posterior support. Further, their results support the hypothesis of long-standing presence of African rabies in

9433:

Thorne JL, Kishino H, Felsenstein J (August 1991). "An evolutionary model for maximum likelihood alignment of DNA sequences".

5342:

Mooers AØ, Schluter D (1999). "Reconstructing Ancestor States with Maximum Likelihood: Support for One- and Two-Rate Models".

6574:"Inferring ancestral states without assuming neutrality or gradualism using a stable model of continuous character evolution" 3612: 2879:, UPGMA), and ancestral sequences were reconstructed by parsimony. The authors reported a weak but significant tendency for 5291:

Cunningham CW, Omland KE, Oakley TH (September 1998). "Reconstructing ancestral character states: a critical reappraisal".

3430: 6813:

Hodges WL (November 2004). "Evolution of viviparity in horned lizards (Phrynosoma): testing the cold-climate hypothesis".

2950:(a segment is removed from one part of the permutation and spliced in somewhere else), or gain of genetic content through 108:

to accurately recover ancestral states. These models use the genetic information already obtained through methods such as

8397: 2966:, although it has received much attention in mathematics and computer science (for a review, see Fertin and colleagues). 262:

There are three different classes of method for ancestral reconstruction. In chronological order of discovery, these are

5700:"Computational aspects of maximum likelihood estimation of autoregressive fractionally integrated moving average models" 1717: 9037:

Larget B, Kadane JB, Simon DL (August 2005). "A Bayesian approach to the estimation of ancestral genome arrangements".

7418:"Ancestral sequence reconstruction in primate mitochondrial DNA: compositional bias and effect on functional inference" 3491: 417:

The use of a model of evolution accounts for the fact that not all events are equally likely to happen. For example, a

142:

approach that accounts for uncertainty in tree reconstruction by evaluating ancestral reconstructions over many trees.

8059:"A comparative study in ancestral range reconstruction methods: retracing the uncertain histories of insular lineages" 3818: 7795: 7115:"A phylogenetic method for detecting positive epistasis in gene sequences and its application to RNA virus evolution" 6789: 6529:

Garland Jr T, Dickerman AW, Janis CM, Jones JA (1993). "Phylogenetic analysis of covariance by computer simulation".

4005: 3211: 374:

The upshot of the "minimum evolution" heuristic underlying such methods is that such methods assume that changes are

59: 5608:"The Maximum Likelihood Approach to Reconstructing Ancestral Character States of Discrete Characters on Phylogenies" 2850: 34:) is the extrapolation back in time from measured characteristics of individuals, populations, or species to their 6976:

Göbel U, Sander C, Schneider R, Valencia A (April 1994). "Correlated mutations and residue contacts in proteins".

3893:

also provides methods for ancestral state reconstruction for both discrete and continuous characters through the '

3055:

individuals represented by the tips of the phylogenetic tree. When applied to a phylogenetic tree of chorus frogs

296:

is one of the earliest formalized algorithms for reconstructing ancestral states, as well as one of the simplest.

5200:

Schluter D, Price T, Mooers AØ, Ludwig D (December 1997). "Likelihood of Ancestor States in Adaptive Radiation".

848: 6215: 3916:

sampling methods. Diversitree is an R package providing methods for ancestral state reconstruction under Mk2 (a

2546:

would have a likelihood defined by the transition density of an Ornstein-Uhlenbeck process with two parameters:

86:

corresponding to the distant past, clarifying the evolutionary history of the species in the tree. Since modern

6014:

Huelsenbeck JP, Bollback JP (June 2001). "Empirical and hierarchical Bayesian estimation of ancestral states".

3317: 2997: 3064: 9644: 6059:

Lutzoni F, Pagel M, Reeb V (June 2001). "Major fungal lineages are derived from lichen symbiotic ancestors".

4811:"Maximum likelihood inference of geographic range evolution by dispersal, local extinction, and cladogenesis" 3862: 2766:

may be assorted into three broad diet categories, first those that consume grain-like foods are considered "

326:

of the character states of the ancestor's descendants; if the intersection is the empty set, then it is the

7848:"Are molecular cytogenetics and bioinformatics suggesting diverging models of ancestral mammalian genomes?" 3917: 3099: 1644: 1240:

is the probability of the data for a given model and tree, integrated over all possible ancestral states.

6720:"Cell type phylogenetics informs the evolutionary origin of echinoderm larval skeletogenic cell identity" 5059:

Fitch WM (1971). "Toward Defining the Course of Evolution: Minimum Change for a Specific Tree Topology".

3982: 699: 246: 133:

reconstruction of ancestral sequences). Methods of ancestral reconstruction are often applied to a given

391:

Without a statistical model underlying the method, its estimates do not have well-defined uncertainties.

5542:

Koshi JM, Goldstein RA (February 1996). "Probabilistic reconstruction of ancestral protein sequences".

4204:

Platnick NI, Cameron HD (1977). "Cladistic Methods in Textual, Linguistic, and Phylogenetic Analysis".

4044: 3956: 3881:

Other software packages are more oriented towards the analysis of qualitative and quantitative traits (

3265: 3238: 3183: 2872: 1438: 1383: 8692:"Phylogenetic reconstruction of ancestral character states for gene expression and mRNA splicing data" 7510:"Reconstruction and function of ancestral center-of-tree human immunodeficiency virus type 1 proteins" 5104:"RAxML-VI-HPC: maximum likelihood-based phylogenetic analyses with thousands of taxa and mixed models" 5564: 5021:

Swofford DL, Maddison WP (1987). "Reconstructing ancestral character states under Wagner parsimony".

323: 8366: 8239: 8116: 7159:"An evolutionary-network model reveals stratified interactions in the V3 loop of the HIV-1 envelope" 6431: 6028: 5665: 5160: 4827: 4479: 3480: 3011:

Using this analysis, the team around Lemey found that the most likely hub of diffusion of A-H5N1 is

2809:. Ancestor reconstruction based on squared-change parsimony (equivalent to maximum likelihood under 1929: 1900: 1122: 166:

in 1955, Zuckerkandl and Pauling postulated that such sequences could be used to infer not only the

7846:

Froenicke L, Caldés MG, Graphodatsky A, Müller S, Lyons LA, Robinson TJ, et al. (March 2006).

5356: 4982: 3913: 3890: 3345: 3082: 2959: 2951: 2112: 2050: 2017: 1387: 1363: 299:

Maximum parsimony can be implemented by one of several algorithms. One of the earliest examples is

189: 98:, and cultural characteristics of ancient societies such as oral traditions or marriage practices. 7557:

Kothe DL, Li Y, Decker JM, Bibollet-Ruche F, Zammit KP, Salazar MG, et al. (September 2006).

7114: 5791:

Eyre-Walker A (December 1998). "Problems with parsimony in sequences of biased base composition".

3673: 3392: 2382: 1791:

parameters, overfitting may be an issue. Some common choices that reduce the parameter space are:

1675: 1206: 1169: 3108: 2938:

of genes or homologous regions. Various operations are allowed on these permutations, such as an

2549: 2412: 2145: 1480: 2083: 8361: 8234: 8111: 6426: 6023: 5660: 5559: 5351: 5155: 4977: 4822: 4474: 4033: 3107:) are identified in the contemporary languages under study, analogous to the identification of 1358: 1257: 322:-th ancestor based on the observed character states of its descendants. Each assignment is the 9264:

Ashkenazy H, Penn O, Doron-Faigenboim A, Cohen O, Cannarozzi G, Zomer O, Pupko T (July 2012).

8790:

FitzJohn RG (2012). "Diversitree: comparative phylogenetic analyses of diversification in R".

8169:"A likelihood framework for inferring the evolution of geographic range on phylogenetic trees" 7787: 6366:"Testing the accuracy of methods for reconstructing ancestral states of continuous characters" 5740:

Felsenstein J (1981). "Evolutionary trees from DNA sequences: a maximum likelihood approach".

3716: 1281:

to the empirical estimates of the model and tree obtained from the data, effectively dropping

7995:

Oyserman BO, Moya F, Lawson CE, Garcia AL, Vogt M, Heffernen M, et al. (December 2016).

3129: 3073: 2939: 2883:

pairs of residues to be co-located in the known three-dimensional structure of the proteins.

2616: 2576: 1974: 1697: 1624: 1338: 1284: 1264: 1102: 880: 786: 418: 414:; similar models were also developed for the analogous case of discrete character evolution. 361: 184: 176: 55: 5649:"A simple, fast, and accurate algorithm to estimate large phylogenies by maximum likelihood" 1759: 748: 308: 9573: 9501: 9485: 9442: 9387: 9046: 8901: 8850: 8799: 8288: 8008: 7904: 7466: 7280: 7225: 7170: 7067: 6641: 6585: 6168: 6068: 5800: 5749: 5551: 5300: 4934: 4876: 4723: 4319: 4260: 3990: 3925: 3829: 2975: 2947: 806: 717: 331: 79: 51: 9490:"Reconstructing the dynamics of HIV evolution within hosts from serial deep sequence data" 7344: 7327: 4434: 1305: 8: 8223:"A likelihood framework for estimating phylogeographic history on a continuous landscape" 6467:

Martins EP (1994). "'Estimating the rate of phenotypic evolution from comparative data".

4038:

Jeffrey B Joy; Richard H Liang; Rosemary M McCloskey; T Nguyen; Art Poon (12 July 2016).

3245: 2943: 2834: 2763: 2713: 2685: 1621:

In order to recover the state of a given ancestral node in the phylogeny (call this node

1371: 411: 378:, and thus are inappropriate in cases where change is the norm rather than the exception. 139: 126: 9577: 9505: 9446: 9391: 9050: 8905: 8854: 8803: 8292: 8012: 7908: 7741:

Even S, Goldreich O (1981). "The minimum-length generator sequence problem is NP-hard".

7470: 7284: 7229: 7174: 7071: 6645: 6589: 6172: 6072: 5804: 5753: 5555: 5304: 4938: 4880: 4727: 4323: 4264: 94:

Non-biological applications include the reconstruction of the vocabulary or phonemes of

9596: 9563: 9551: 9524: 9489: 9466: 9410: 9377: 9365: 9341: 9314: 9290: 9265: 9200: 9173: 9149: 9122: 8978: 8925: 8874: 8823: 8767: 8742: 8718: 8691: 8652: 8625: 8601: 8576: 8511: 8486: 8311: 8276: 8198: 8185: 8168: 8029: 7996: 7972: 7947: 7928: 7872: 7847: 7677: 7652: 7628: 7619: 7603: 7534: 7509: 7490: 7303: 7268: 7249: 7193: 7158: 7001: 6950: 6920:

The explanation of organic diversity: the comparative method and adaptations for mating

6838: 6746: 6719: 6700: 6608: 6573: 6484: 6390: 6365: 6346: 6227: 6136: 6111: 6092: 5856: 5824: 5773: 5585: 5519: 5494: 5468: 5422: 5396: 5324: 5268: 5217: 5084: 5003: 4899: 4864: 4746: 4711: 4680: 4655: 4631: 4606: 4538: 4513: 4398: 4342: 4307: 4283: 4248: 4229: 4076: 4039: 4000: 3112: 3056: 2854: 2656: 2636: 2596: 2529: 2509: 2489: 2469: 2449: 2362: 2342: 2322: 2302: 2282: 2262: 2242: 2222: 2202: 2182: 1997: 1878: 1845: 1821: 1799: 1512: 1460: 1446: 1442: 872: 407: 327: 303:, which assigns ancestral character states by parsimony via two traversals of a rooted 271: 267: 130: 105: 7718: 7701: 7508:

Rolland M, Jensen MA, Nickle DC, Yan J, Learn GH, Heath L, et al. (August 2007).

7393: 7368: 6781: 6317:"Integrating fossils with molecular phylogenies improves inference of trait evolution" 5988: 5971: 5947: 5930: 5715: 5312: 4925:

Watterson GA, Ewens WJ, Hall TE, Morgan A (1982). "The chromosome inversion problem".

4378: 4181: 4154: 3777: 3766: 1961:

Graphical representation of an asymmetrical five-state 2-parameter Markov chain model.

1203:

is the prior probability of the ancestral states for a given model and tree. Finally,

9601: 9547: 9529: 9458: 9415: 9346: 9295: 9246: 9205: 9154: 9103: 9082:"Count: evolutionary analysis of phylogenetic profiles with parsimony and likelihood" 9062: 9019: 8970: 8956: 8917: 8866: 8815: 8811: 8772: 8723: 8657: 8606: 8557: 8516: 8449: 8379: 8316: 8254: 8190: 8131: 8080: 8034: 7977: 7920: 7877: 7828: 7791: 7777: 7758: 7754: 7723: 7682: 7633: 7580: 7539: 7482: 7439: 7398: 7384: 7367:

Zhang C, Zhang M, Ju J, Nietfeldt J, Wise J, Terry PM, et al. (September 2003).

7349: 7308: 7241: 7198: 7139: 7095: 7090: 7055: 7036: 6993: 6958: 6900: 6830: 6826: 6795: 6785: 6751: 6692: 6657: 6613: 6515: 6446: 6395: 6338: 6333: 6316: 6297: 6293: 6262: 6231: 6219: 6184: 6141: 6084: 6041: 5993: 5952: 5911: 5860: 5816: 5765: 5719: 5680: 5629: 5577: 5524: 5460: 5414: 5369: 5316: 5260: 5225: 5173: 5128: 5076: 5038: 5034: 5007: 4995: 4950: 4946: 4904: 4842: 4786: 4751: 4685: 4636: 4584: 4579: 4562: 4543: 4494: 4438: 4390: 4382: 4347: 4288: 4221: 4186: 4135: 4081: 4063: 3069: 3037: 2982:

Accumulibacter phosphatis) to identify the evolutionary basis for trait acquisition.

2759: 884: 876: 293: 283: 263: 229:) are related by descent from common ancestors. Observed taxa are represented by the 180: 151: 102: 83: 9470: 9241: 9224: 9098: 9081: 9014: 8997: 8982: 8929: 8878: 8827: 8552: 8535: 8444: 8427: 8202: 7932: 7494: 7005: 6842: 6488: 6350: 5828: 5589: 5123: 5103: 4017: 3352: 2746:(live birth) has evolved multiple times, based on ancestral reconstruction methods. 834:

internal nodes that maximizes the likelihood of the observed data for a given tree.

9591: 9581: 9519: 9509: 9450: 9405: 9395: 9336: 9326: 9285: 9277: 9236: 9195: 9185: 9144: 9134: 9093: 9054: 9009: 8960: 8952: 8909: 8858: 8807: 8762: 8754: 8713: 8703: 8647: 8637: 8596: 8588: 8547: 8506: 8498: 8439: 8371: 8306: 8296: 8244: 8180: 8121: 8070: 8024: 8016: 7967: 7959: 7946:

Ma J, Zhang L, Suh BB, Raney BJ, Burhans RC, Kent WJ, et al. (December 2006).

7912: 7867: 7859: 7820: 7783: 7750: 7713: 7672: 7664: 7623: 7615: 7570: 7529: 7521: 7474: 7429: 7388: 7380: 7339: 7298: 7288: 7253: 7233: 7188: 7178: 7129: 7085: 7075: 7028: 6985: 6942: 6892: 6865: 6822: 6777: 6741: 6731: 6704: 6684: 6649: 6603: 6593: 6538: 6511: 6476: 6436: 6385: 6377: 6328: 6289: 6254: 6211: 6176: 6131: 6123: 6096: 6076: 6033: 5983: 5942: 5901: 5891: 5852: 5808: 5777: 5757: 5711: 5670: 5619: 5569: 5514: 5506: 5472: 5452: 5426: 5406: 5361: 5328: 5308: 5252: 5209: 5165: 5118: 5068: 5030: 4987: 4942: 4894: 4884: 4832: 4778: 4741: 4731: 4675: 4667: 4626: 4618: 4574: 4533: 4525: 4484: 4430: 4402: 4374: 4337: 4327: 4278: 4268: 4213: 4176: 4166: 4125: 4089: 4071: 4053: 3532: 3156: 2955: 289: 255: 163: 159: 95: 87: 63: 5510: 4563:"Chemical Paleogenetics. Molecular "Restoration Studies" of Extinct Forms of Life" 3405: 3325: 3163: 2801:

lizards show remarkable morphological diversity, including in the relative muscle

2720:. For criticism of ancestral reconstruction computation methods see Williams P.D. 9586: 9514: 7183: 4889: 4736: 4332: 4273: 4058: 3961: 2830: 2810: 2802: 2798: 1434: 300: 9172:

Patro R, Sefer E, Malin J, Marçais G, Navlakha S, Kingsford C (September 2012).

9058: 8913: 7575: 7558: 1987:

between adjacent nodes given by some other continuous probability distribution.

1641:) by maximum likelihood, the procedure is: find the maximum likelihood estimate 9370:

Proceedings of the National Academy of Sciences of the United States of America

8281:

Proceedings of the National Academy of Sciences of the United States of America

8150: 7599: 7416:

Krishnan NM, Seligmann H, Stewart CB, De Koning AP, Pollock DD (October 2004).

7273:

Proceedings of the National Academy of Sciences of the United States of America

7060:

Proceedings of the National Academy of Sciences of the United States of America

6037: 4782: 4622: 4024: 3995: 3901: 3552: 3363:

TSV/CSV of species regions. Rows are species and columns are geographic regions

3095: 2767: 2681: 206: 118: 35: 9331: 9266:"FastML: a web server for probabilistic reconstruction of ancestral sequences" 8405: 8249: 8222: 8155:

Computer program and manual available by anonymous FTP from Uppsala University

8126: 8099: 8075: 8058: 7824: 7032: 6869: 6736: 6688: 6634:

Journal of Experimental Zoology. Part B, Molecular and Developmental Evolution

6598: 6542: 6441: 6414: 6258: 5675: 5648: 5410: 4837: 4810: 4671: 4656:"Analyzing protein structure and function using ancestral gene reconstruction" 4489: 4462: 3272: 9618: 9315:"MLGO: phylogeny reconstruction and ancestral inference from gene-order data" 8870: 8819: 8352:

Yang Z (August 2007). "PAML 4: phylogenetic analysis by maximum likelihood".

7762: 7702:"Genome-scale evolution: reconstructing gene orders in the ancestral species" 6301: 6112:"Robustness of ancestral sequence reconstruction to phylogenetic uncertainty" 5723: 5633: 5464: 5373: 5264: 5177: 5080: 5042: 4954: 4588: 4386: 4225: 4139: 4067: 2814: 875:

uses the likelihood of observed data to update the investigator's belief, or

167: 155: 109: 39: 9400: 8758: 8708: 8502: 8375: 8057:

Clark JR, Ree RH, Alfaro ME, King MG, Wagner WL, Roalson EH (October 2008).

7916: 7602:, Rodrigo AG, Nickle DC, Li F, Mahalanabis M, et al. (September 2005). 7478: 7434: 7417: 7293: 7267:

Sadqi M, de Alba E, Pérez-Jiménez R, Sanchez-Ruiz JM, Muñoz V (March 2009).

7134: 7080: 6180: 6127: 5896: 5879: 5624: 5607: 5495:"A new method of inference of ancestral nucleotide and amino acid sequences" 5365: 4130: 4113: 3946:

variation. MLGO is a web-server for maximum likelihood gene order analysis.

3068:

Phylogeny of 7 regional strains of Drosophila pseudoobscura, as inferred by

9605: 9533: 9419: 9350: 9299: 9250: 9209: 9190: 9158: 9107: 9066: 9023: 8974: 8921: 8862: 8776: 8727: 8661: 8642: 8610: 8561: 8520: 8453: 8383: 8320: 8258: 8194: 8135: 8084: 8038: 7981: 7924: 7881: 7832: 7727: 7686: 7637: 7584: 7543: 7486: 7443: 7402: 7353: 7312: 7202: 7143: 6989: 6962: 6904: 6834: 6799: 6755: 6696: 6661: 6617: 6450: 6399: 6381: 6342: 6266: 6223: 6145: 6088: 6045: 5956: 5915: 5864: 5684: 5418: 5320: 5229: 5132: 4908: 4846: 4790: 4755: 4689: 4640: 4547: 4498: 4442: 4394: 4351: 4292: 4190: 4171: 4085: 3700: 3580: 3218: 3032: 3001: 2780: 1441:. Using this model as the basis for statistical inference, one can now use 1426: 1405: 422: 365: 9462: 9139: 8301: 8020: 7245: 7099: 7040: 6997: 6188: 5997: 5820: 5769: 5581: 5528: 4999: 4769:

Ronquist F (September 2004). "Bayesian inference of character evolution".

4093: 9281: 8592: 8398:"Lazarus: a software tool for reconstructing ancestral protein sequences" 7668: 7525: 5972:"PAML: a program package for phylogenetic analysis by maximum likelihood" 3830:

Custom text format for model parameters, tree, observed character values.

3559: 3116: 3020: 2935: 2880: 2826: 2771: 857: 304: 8626:"SIMMAP: stochastic character mapping of discrete traits on phylogenies" 7326:

Chang BS, Jönsson K, Kazmi MA, Donoghue MJ, Sakmar TP (September 2002).

6653: 3587: 2754:

Both phylogenetic and character data are available for the radiation of

2712:

Ancestral reconstruction allows for the study of evolutionary pathways,

1967: 9454: 8965: 7963: 7863: 6954: 5812: 5761: 5573: 5272: 5221: 5088: 4991: 4233: 3043: 3000:

strains sampled from twenty localities in Europe and Asia, and for 101

2867: 2743: 2738: 1430: 1413: 222: 172: 8485:

Tamura K, Stecher G, Peterson D, Filipski A, Kumar S (December 2013).

7894: 7811:

Wienberg J (December 2004). "The evolution of eutherian chromosomes".

6896: 5906: 4529: 3840:

None specified, although site indicates software is freely available.

3662: 2793: 9550:, Trinh A, Sipos B, Brenton JD, Goldman N, Markowetz F (April 2014). 7651:

McCloskey RM, Liang RH, Harrigan PR, Brumme ZL, Poon AF (June 2014).

7266: 7237: 6415:"Estimating a binary character's effect on speciation and extinction" 6080: 3882: 3297: 3016: 3012: 2970: 2829:

species comparing stable models of continuous character evolution to

1957: 218: 134: 122: 113: 75: 43: 8469:"Mesquite: a modular system for evolutionary analysis. Version 2.75" 6946: 6674: 5256: 5213: 5169: 5072: 4712:"Assessing the accuracy of ancestral protein reconstruction methods" 4217: 4155:"Reconstruction of ancestral protein sequences and its applications" 9225:"Ancestors 1.0: a web server for ancestral sequence reconstruction" 6480: 5456: 4114:"The Assumptions and Challenges of Ancestral State Reconstructions" 3727:

Tab-delimited text file of rows for taxa and count data in columns.

3336:

TSV or space delimited table. Rows are species, columns are traits.

2912: 2786: 2775: 2573:, which describes the variance of the driving Brownian motion, and 1400: 1386:

rapidly becomes too vast, making it computationally infeasible for

198: 9568: 9382: 9263: 5401: 4710:

Williams PD, Pollock DD, Blackburne BP, Goldstein RA (June 2006).

4709: 4560: 4463:"Bayesian estimation of ancestral character states on phylogenies" 3507: 1119:

represents both the evolutionary model and the phylogenetic tree.

7845: 7559:"Ancestral and consensus envelope immunogens for HIV-1 subtype C" 7415: 6630: 6502:

Felsenstein J (1988). "Phylogenies and quantitative characters".

3939: 3909: 3455: 3104: 2963: 2916: 2891: 2806: 2733: 1994:

Plots of 200 trajectories of each of: Brownian motion with drift

202: 158:. Motivated by the development of techniques for determining the 67: 47: 8577:"PHAST and RPHAST: phylogenetic analysis with space/time models" 7269:"A designed protein as experimental model of primordial folding" 6109: 5443:

Felsenstein J (1985). "Phylogenies and the Comparative Method".

2653:, the process is less and less constrained by its attraction to 1603:{\displaystyle \mathbf {q} =\{q_{ij}:1\leq i,j\leq k,i\not =j\}} 1162:

is the likelihood of the observed data which can be computed by

338: 74:(e.g., gene order), a measurable characteristic of an organism ( 8536:"MrBayes 3: Bayesian phylogenetic inference under mixed models" 3976: 2839: 1864: 1367: 71: 9640:

Knowledge articles published in peer-reviewed literature (J2W)

6110:

Hanson-Smith V, Kolaczkowski B, Thornton JW (September 2010).

4863:

Lemey P, Rambaut A, Drummond AJ, Suchard MA (September 2009).

3741: 9484:

Poon AF, Swenson LC, Bunnik EM, Edo-Matas D, Schuitemaker H,

8996:

Jones BR, Rajaraman A, Tannier E, Chauve C (September 2012).

8487:"MEGA6: Molecular Evolutionary Genetics Analysis version 6.0" 8484: 8468: 6528: 3943: 2876: 2755: 226: 150:

The concept of ancestral reconstruction is often credited to

7650: 7597: 7328:"Recreating a functional ancestral archosaur visual pigment" 7215: 7113:

Shapiro B, Rambaut A, Pybus OG, Holmes EC (September 2006).

7054:

Korber BT, Farber RM, Wolpert DH, Lapedes AS (August 1993).

6975: 5877: 4308:"Evolutionary history of hunter-gatherer marriage practices" 335:

than one possible state has been reconstructed at the root.

101:

Ancestral reconstruction relies on a sufficiently realistic

9552:"Phylogenetic quantification of intra-tumour heterogeneity" 8995: 8270: 8268: 7776:

Fertin G, Labarre A, Rusu I, Vialette S, Tannier E (2009).

7556: 6216:

10.1554/0014-3820(2000)054[0397:ICSWAR]2.0.CO;2

6103: 5841: 4862: 4607:"Inversions in the Chromosomes of Drosophila Pseudoobscura" 4600: 4598: 4022:

This article was adapted from the following source under a

3637: 2749: 1990: 1613: 9630:

Knowledge articles published in PLOS Computational Biology

9483: 9222: 8097: 7948:"Reconstructing contiguous regions of an ancestral genome" 7053: 6776:. Methods in Enzymology. Vol. 395. pp. 652–670. 6009: 6007: 3191: 8741:

Drummond AJ, Suchard MA, Xie D, Rambaut A (August 2012).

8740: 7775: 7325: 7112: 7018: 5878:

Gruenheit N, Lockhart PJ, Steel M, Martin W (July 2008).

5199: 5146:

Sankoff D (1975). "Minimal Mutation Trees of Sequences".

4561:

Pauling L, Zuckerkandl E, Henriksen T, Lövstad R (1963).

4420: 4306:

Walker RS, Hill KR, Flinn MV, Ellsworth RM (April 2011).

3689: 2908: 2895: 1842:

model. In this model, all transitions have the same rate

1694:; then compute the likelihood of each possible state for 9625:

Knowledge articles published in peer-reviewed literature

9546: 9540: 9432: 8689: 8265: 8167:

Ree RH, Moore BR, Webb CO, Donoghue MJ (November 2005).

7994: 4924: 4595: 4305: 3793: 9357: 9120: 8843:

Proceedings of the Royal Society B: Biological Sciences

8527: 7456: 7012: 6004: 5922: 5286: 5284: 5282: 3908:(Bayesian Evolutionary Analysis by Sampling Trees) and 2969:

The reconstruction of ancestral genomes is also called

2774:" and those that consume vegetation are classified as " 2466:). Under this model, the above-described transition of 775:

is the branch length (evolutionary time) between nodes

254:

taxa (sequences) that descended from common ancestors.

9366:"Evolutionary inference via the Poisson Indel Process" 9223:

Diallo AB, Makarenkov V, Blanchette M (January 2010).

9171: 8743:"Bayesian phylogenetics with BEAUti and the BEAST 1.7" 8091: 7507: 7157:

Poon AF, Lewis FI, Pond SL, Frost SD (November 2007).

6158: 5290: 4705: 4703: 4701: 4699: 4554: 3924:

Genome rearrangements provide valuable information in

2727: 1938: 1909: 217:

Any attempt at ancestral reconstruction begins with a

205:, the geographic location of populations and species ( 9216: 8683: 8173: