GRASP

GRASP outputs

Phylogenetic tree

The results page shows an interactive version of the phylogenetic tree that was provided for reconstruction. By default, labels of extant sequences are displayed and the user is given the option to also display or hide labels and branch lengths (see (2) in Figure 2). It is possible to search for nodes given search pattern (see (3) in Figure 2). If extant labels follow a standard format, it is possible to download taxonomic information from NCBI and UniProt by the press of a button (see (2) in Figure 2).

GRASP will number ancestors (i.e. phylogenetic branch points) internally from the root (N0, N1, ...) using the principle of 'depth first'. N0 is always going to be the root of the tree. You can see an ancestor label by hovering over the node, or in a pop-up box by clicking it. If available, taxonomic information will be collated and summaries for ancestor nodes are shown when clicked at (more information below).

It is possible to upload annotations for extant labels (see (1) in Figure 2) that can subsequently be searched for (more information below).

It is possible to search for sequence motifs in the ancestor sequences (see (3) in Figure 2); the syntax is described below.

For big trees you may want to reduce the number of nodes shown. Use the buttons at (4) to adjust how many nodes are collapsed and the size of text labels.

Each node is coloured by evolutionary distance according to the legend on the left hand side (see (6) in Figure 2). One node will always appear pink and be noted in the header above the tree. This is the node that is having its reconstruction displayed in the graph below the phylogenetic tree and is known as the primary node. By default, N0 (the root node) is the primary node, will appear pink and be listed in the header.

By hovering over nodes in the phylogenetic tree, the name will be revealed. By right clicking an ancestral node in the tree you will bring up a number of operations which can be performed on the ancestor. Note that some operations may take time to complete. (Unless previously run for the specified ancestor, marginal reconstruction will usually take as long as the initial reconstruction.)

Annotation: User-provided labels

GRASP can assign tabulated series of values to both extants and ancestors by their labels (see (1) in Figure 2). For example, a user can use this to assign functional annotation indexed by a column header, say 'Substrate', to a certain protein, say 'N123' or 'P12345'. This would be uploaded in the form of a tab-separated values (TSV), e.g.

        ID          Name         Substrate    Activity
        N123        Fav_ancestor Luciferase   High(100)
        P12345      My-enzyme    Luciferase   Moderate(10)
        P54321      No-enzyme    None         None(0)
                            

Upload this content (paste or type into the input window), and use the same popup menu to enter which column you want to search in, say 'Substrate', and the term that needs to be matched for a node to be highlighted, say 'Luciferase'.

Tree vis options: Taxonomy

GRASP can automatically retrieve taxonomic information from the NCBI and UniProt databases by clicking on the Annotate taxonomy button, and append this information to the extant nodes of the phylogenetic tree. (The first time this is done, information needs to be downloaded so please be patient.) Clicking on an ancestor node will display a summary and histograms for each taxonomic rank, with numbers of extants that fall under each label.

For example, in Figure 4, we used the example data set 'Foley et al. DHAD (1612)', clicked annotate taxonomy, and clicked on ancestor 'N1087', which has about 400 extants.

In order to annotate taxonomy from the NCBI and UniProt databases, GRASP expects the sequence IDs in your FASTA file to be in either the NCBI or UniProt ID format -

>PRD21445.1 Cyp2u1 [Nephila clavipes]

or

>tr|A0A2P6K539|A0A2P6K539_NEPCL Cyp2u1 OS=Nephila clavipes OX=6915 GN=NCL1_51699 PE=4 SV=1

By default, GRASP will expect the ID to be separated by a whitespace from any additional information.

However, it will accept IDs which are completely stripped of additional information -

>PRD21445.1

or

>tr|A0A2P6K539|A0A2P6K539_NEPCL

Or IDs that have all whitespace removed (in order to force annotations to appear on phylogenetic trees) if the additional information is separated from the ID by a pipe symbol (|) -

>PRD21445.1|Cyp2u1_Nephila_clavipes

or

>tr|A0A2P6K539|A0A2P6K539_NEPCL|Cyp2u1_OS=Nephila_clavipes

Note that this means that headers where additional information is not separated by either a whitespace or a pipe symbol will not be able to have their taxonomy annotated - i.e. the following will not work -

>PRD21445.1_Cyp2u1_Nephila_clavipes

or

>tr|A0A2P6K539|A0A2P6K539_NEPCL_Cyp2u1_OS=Nephila_clavipes

All of the existing constraints about sequence names matching between alignment and phylogenetic tree must still be adhered to.

Tree search options: Sequence motif

You are able to search for ancestors with specified sequence motifs in saved joint reconstructions; note that searching is done only in preferred sequences, and not in optional paths (see more below).

Example search patterns:

• %A%: Highlight sequences with an A in any position, you can also use just an A however the % signs are recommended.
• %A-*M%: Highlight sequences with an A followed by any number of gaps and then an M .
• %AM(P|R)%: Highlight sequences with an A followed by an M , followed by either a P or an R .
• %A_M%: Highlight sequences with an A followed by any other character (e.g. a gap, K , P etc) followed by an M .

Syntax guide:

• _ : Wildcard character.
• | : denotes one of the two options.
• *: repetition of preceding amino acid 0 or more times.
• {n}: repetition of the preceding amino acid n times.
• {m, n}: repetition of the preceding amino acid more than m times and less than n times.

Note 1: Since the gap patterns from the original alignment are preserved, unless you specify gaps or use (-*) between your search elements, only those sequences without gaps between the search terms will be highlighted.

Note 2: The searching looks for a match anywhere in the sequence, this means that even though two sequences are highlighted, they might not have the motif in the same position! So it is recommended you confirm your findings by downloading the joint reconstructions and checking the alignment.

Partial-order graph

GRASP uses partial-order graphs to represent ancestors. They are suited to this task as (a) sequence homology amongst members in a protein family (and by extension their ancestors) may not always map unambiguously to a single, linear ordering, and (b) unresolved insertions and deletions can be identified as alternative paths through the graph.

We suggest that you read a partial-order graph from left-to-right, node-by-node, forming a putative biological sequence (N- to C-terminus) by following a single path. While GRASP attempts to resolve the history of insertions and deletions, at a single node, you may be presented with multiple in- and out-going edges, each of which joins potential ancestral sequences together.

Nodes in a partial-order graph

A node represents the character state at a position in a sequence. The position is not defined in an absolute sense, rather in a relative sense when there is evidence of an order. For practical reasons, there is still a positional index to assist navigation in GRASP.

The node displays either a single character state or a distribution over possible character states. The states of ancestral nodes are inferred by maximum likelihood.

Edges in a partial-order graph and preferred paths

An edge represents a valid path to create a full-length sequence. Once homologous sections have been determined by alignment, the joint set of extant sequences express the space of possible paths that can be taken. Of them, by enumerating them at each node, GRASP infers the maximally parsimonious edges, i.e. the edge or edges that imply the least number of changes across the whole evolutionary history. We call this process bi-directional edge-parsimony (BDEP). The term "bi-directional" here refers to the separation of in- and out-going edges of a node, and therefore an edge can be maximally parsimonious, for one or both nodes it joins. You can find a more detailed explanation here.

GRASP identifies edges for which there is qualified support, and makes distinctions that are important to interpret sequences that you assemble through them:

• Solid edges are fully supported by bi-directional edge-parsimony; these links are strong candidates for how an ancestor can be assembled. They are not exclusive; multiple paths connecting different parts of a full-length sequence may be present. Nor are they guaranteed to identify even a single full-length sequence.

• A dotted edge is maximally parsimonious when only one of the nodes it joins is considered (which one is not shown). These edges are weaker candidates but are kept to allow full-length ancestors to be formulated in the absence of the stronger option above.

GRASP also uses the number of extant sequences on which the inference is based. This can be used to separate edges further:

• The darker the edge, the more extant sequences (of the set in the subtree under the ancestor) travel through the same edge.

• GRASP provides the option of displaying one preferred path through a sequence. If this option is turned on, thick/bold edges represent a single, preferred traversal of the graph, giving preference to (a) bi-directional edge-parsimony support (edge is drawn dark) and (b) greater number of extant sequences following (in the subtree under the ancestor).

Graph visualisation - joint reconstruction

After running reconstruction, you will be able to see a navigation bar (see (1) in Figure 5), a multiple sequence alignment graph (see (2) in Figure 5) and the primary ancestor graph(see (3) in Figure 5) underneath the phylogenetic tree.

GRASP allows you to 'add' ancestors to be visualised along side the primary ancestor. Each added ancestor becomes the current ancestor graph.

Navigation bar

The navigation bar has a blue box (see (4) in Figure 5) which can be expanded, or collapsed and moved across the window to view different sections of the graphs. The region of the graph that you are viewing is within the blue box. Relative to the primary ancestor that is being viewed (see Phylogenetic tree) you will see grey boxes and red circles across the navigation bar.

Grey boxes represent insertions and deletions in the ancestor that cannot be resolved definitively; they indicate the presence of two or more edges in the ancestor at the corresponding position.

Red circles represent definitive absence of content in the current ancestor, relative to the input sequence alignment graph.

If you add multiple ancestor POGs shown together, grey boxes are determined from the union of ancestors, but red circles apply only to the current ancestor.

Input sequences

The multiple sequence alignment is represented here as a partial-order graph that contains paths to regenerate all sequences uploaded by the user. Each node in the graph is depicted as a pie chart representing the distribution of amino acids at that position across all extant sequences. The most probable amino acid is shown using its one-letter code. When you hover your mouse over each node, a bar chart will display, showing the distribution in more detail, as seen in Figure 6.

The edges in the multiple sequence alignment graph represent the insertion and deletions of all extant sequences.

Primary ancestor

This graph displays the partial-order graph of the primary ancestor. More technical information of joint reconstruction is provided below.

Edges in reconstructions are inferred by edge-parsimony. One or more ancestral sequences can be formed by following one path. We recommend that solid edges are given preference, but all presented edges have some support.

The joint reconstruction 'stack'

When the 'Add joint reconstruction' option is selected for a node in the phylogenetic tree, its reconstructed sequence will be added below the primary ancestor (boxed with a blue shade that indicates the evolutionary distance of the phylogenetic node it is taken from to the root). We refer to this as the 'stack' and you can keep adding joint reconstructions to it; this allows for comparisons between ancestral states at different phylogenetic branch points.

Graph options

Graphs can be saved as PNG images using the 'Save graphs' button (see (5) in Figure 5). The amino acid colour scheme is, by default, set to Clustal.

Graph visualisation - marginal reconstruction

A marginal reconstruction can be performed on any ancestor selected in the phylogenetic tree on the results page. A marginal reconstruction will look similar to Figure 8.

The reconstruction of the primary node will be composed of pie charts similar to the input sequence alignment graph. Each pie chart depicts the distribution of amino acids at each position in the reconstructed ancestor. More technical information about marginal reconstruction is provided here.

Mutants

Once a marginal reconstruction has been performed, it is possible to identify targets for mutational analysis. This is based on the idea that the reconstruction represents just one possible ancestor, and that others can be explored around it by mutating positions that are inferred to be in an ambivalent state.

The user can select the level of complexity of the mutant library. The base case "0" means that all nodes map to the single, most probable amino acid. You will note by setting it to "0" all nodes become single-state. By increasing the level, alternative amino acids are added to positions that are more ambivalent; at higher levels of complexity, some positions are assigned two or more mutational targets. An arrow appears close to the location of the identified nodes alongside the navigation bar. You will note that the ambivalent nodes are shown with more character states. More technical information is provided below.

Downloading results

You can download results generated by GRASP, through the download section. The download section is expanded by clicking the "Download Results" drop down button located below the graph visualisation area (see (1) in Figure 9).

Note that sequences are based on a single, preferred path in each, more information-rich ancestor partial-order graph. We recommend that you still consult with the partial-order graph to corroborate what the evidence for the ancestor sequence is.

To download results, click the appropriate button.

The tree (2) (in Figure 9) is the tree the user provided but with internal/ancestral nodes labelled (N0, N1..etc.).

A marginal reconstruction (3) (in Figure 9) is available as either TSV file (tabulated for the probability of each character, in each position) and FASTA file (with the most probable character in each position). Note that only the single, primary ancestor is downloaded.

A joint reconstruction (4) (in Figure 9) is available as a FASTA file (with nominated ancestors, or the full set of ancestors).

Technical information

What is the difference between joint and marginal reconstruction?

GRASP employs exact probabilistic inference; it distinguishes between two types of reconstructions:

Joint - GRASP infers the most probable combination of all ancestral states. The assignment of all ancestral states (across the whole phylogenetic tree) optimises a single objective (the joint state with the greatest likelihood). This will tell you which are the most probable ancestors, given the extant sequences and their phylogenetic relationships. The inference is valid for the whole tree, and it is practical to compare ancestors with one another as they represent snapshots from the same evolutionary history.

Marginal - GRASP infers the probability distribution of each residue for a single, nominated ancestor. This inference will present you with the probability of amino acids at each position in the nominated ancestor, given extant sequences and their phylogenetic relationships. The inference "marginalises" all other ancestors, which means that (a) each ancestor needs to be inferred separately, and (b) resulting distributions are not directly comparable. Multiple marginal reconstructions (for different ancestors) are based on the same input data, but their mutual consistency is not enforced; they allow for different versions of evolutionary histories along the same branches.

The most probable character state in each character distribution resulting from a marginal reconstruction is commonly identical to that from a joint reconstruction; so, in practise, it may not matter much which inference type you use.

Once GRASP performs a joint reconstruction it will determine and keep all ancestral states in memory; this process can take some time to complete. "Adding" nodes on the results page will not require additional inference of ancestral states, so the delay you experience is minor. Marginal reconstruction needs to be performed for each node; inference is separate so there will be longer delays each time even after you have moved to the results page. (That said, we now have implemented caching of these states, so if you have "added" them before, the delay is minor.)

What is bi-directional edge-parsimony?

Edges represent optional paths through which sequences can be composed; ultimately, the collective of extant sequences when aligned determines the set of all possible paths; that set is the source from which we draw the path or paths for any ancestor. We are interested in identifying which edges that are best supported for an ancestor, given their phylogenetic relationships. For this we use the basic principle of maximum parsimony, where only the most parsimonious edges are kept for each individual ancestor.

Maximum parsimony is applied to edges of a node; for each node, we separately process edges labelled by the nodes preceding it, and edges labelled by the nodes following it. An edge can therefore be supported in one direction but not the other. Uni-directional support is sufficient for GRASP to display an edge and maintain any paths to the nodes concerned; bi-directional support should be seen as a much stronger endorsement though. We run maximum parsimony to identify all edges that achieve the best score (the same score can be shared by multiple edge selections). This means that in many cases multiple paths through an ancestor cannot be ruled out.

How is a single, preferred ancestor sequence determined from a graph?

Not uncommonly, multiple indel histories are equally parsimonious, implying that several ancestor candidate sequences can be identified by traversing an ancestor POG; however, in some applications it is necessary to nominate a single sequence. To determine a 'preferred' path through an ancestor POG, we determine the proportion of extant sequences in the subtree under the ancestor that follow each edge. We use this proportion to express preference between multiple edges.

GRASP uses the A* algorithm to determine the selection of edges in a POG that jointly minimise the cost, travelling from the N- to the C-terminus. GRASP imposes an absolute preference for bi-directionally parsimonious edges; a uni-directional is only chosen in the absence of bi-directional edges to complete the traversal. The exception is the edge to the first node, and the edge from the last node, where bi-directionality is disregarded.

How are mutant libraries determined?

A marginal reconstruction allows the user to identify the positions that should be mutated with priority, to explore the space of probable ancestors.

Initially, the complexity of the mutant library is "0", suggesting for each position, only the most probable amino acid. At "1", a single mutation is allowed, at the position that best improves the summed Kullback-Leibler divergence between the mutant distributions and the corresponding marginal distributions, across all sequence positions. For each increase in the level, another mutation is identified where an alternative amino acid is suggested. Note that additional mutations could occur at a position that has been mutated previously or in a different position. Either way, the potential library will increase in complexity, i.e. increase the number of theoretically possible mutants.

References

Reference to GRASP and example data sets

Foley G, et al. Identifying and engineering ancient variants of enzymes using Graphical Representation of Ancestral Sequence Predictions (GRASP). bioRxiv 2019. DOI:10.1101/2019.12.30.891457

More example data sets

1. Afriat-Jurnou L, Jackson CJ and Tawfik DS. Reconstructing a Missing Link in the Evolution of a Recently Diverged Phosphotriesterase by Active-Site Loop Remodeling. Biochemistry 2012, 51, 6047-6055. DOI:10.1021/bi300694t
2. Hudson WH, Kossmann BR, de Vera IM, Chuo SW, Weikum ER, Eick GN, Thornton JW, Ivanov IN, Kojetin DJ, and Ortlund EA. Distal substitutions drive divergent DNA specificity among paralogous transcription factors through subdivision of conformational space. Proc Natl Acad Sci USA, 113(2): 326-331. DOI:10.1073/pnas.1518960113