Weakly-supported edges, as indicated by low edge weights, often imply that the inferred history associated with those edges may not be accurate. Notung can rearrange weakly-supported regions in a gene tree to produce alternate event histories with minimum D/L Score. When these edges or regions are rearranged, the structure of strongly-supported edges or regions stays intact. Any edge that is added as a result of rearrangement will be not be assigned an edge wieght. Since support for edges is determined by edge weight, Notung’s rearrangement function requires that the gene tree include edge weights which assess how well each edge is supported by sequence data. These edge weights can be bootstrap values, probabilities, or branch lengths.
Weak edges are defined as those edges with weights below the Edge Weight Threshold. Selecting the “Highlight weak edges” checkbox in Rearrange mode will highlight all weak edges in yellow, allowing the user to see which edges will be considered for rearrangement (see Figure 7.1). This option is only available in Rearrange mode. The yellow highlighting will disappear when another mode is selected. As a default, the Edge Weight Threshold is 90% of the maximum edge weight. While this is a good starting place for bootstrap values, it may not be appropriate for probabilities or branch lengths. The threshold can be adjusted by the user; see Chapter 3.5 - Parameter Values for information on how to change the Edge Weight Threshold. Notung also considers any edge without an assigned weight to be a weak edge. If Notung’s rearrangement function is applied to a tree with no edge weights, it will consider all edges to be weak, and will find all trees that are optimal when only gene duplication and loss are considered (i.e. those trees with a minimal D/L Score).
Click on image to see larger version
Figure 7.1: (a) The gene tree from Figure 5.1 with weak edges highlighted. (b) After clicking “Perform Rearrangement,” the rearranged tree appears in the tree panel. Weak edges are still highlighted in yellow.
The Rearrangement function can be applied to a non-binary gene tree when the species tree is binary (Figure 7.2). Notung will replace each polytomy with an arbitrary binary resolution, inserting new nodes and edges. These new edges are treated as weak edges. The standard rearrangement algorithm is then applied to the resulting binary tree to determine the rearrangement that results in a minimal D/L Score. Note that it is immaterial how the polytomies are initially resolved, because subsequent rearrangement will result in a minimum cost tree. Rearrangement cannot be performed when the species tree is non-binary.
When rearranging a gene tree, there may be more than one tree that (1) agrees with the original tree at strongly supported edges and (2) has minimal D/L Score. If there are many such trees, considering all of them may be a daunting task. Notung addresses this issue by partitioning the set of all optimal trees into subsets in such a way that any tree in a given subset can be generated from any other tree in the subset by a series of node interchanges.
All trees in any given subset are instances of the same event history. An event history describes a series of events (duplications and losses) and the location in the species tree where they occurred. “A duplication in the common tetrapod ancestor, a loss in the fish lineage and three duplications in mouse” is an example of an event history. To see that more than one tree can have the same event history, note that “three duplications in mouse” corresponds to the subtree ((g1_mouse, g2_mouse), (g3_mouse, g4_mouse)), as well as the subtree ((((g1_mouse), g2_mouse), g3_mouse), g4_mouse).
If multiple minimum cost trees are found, Notung presents one tree from each subset (i.e. one representative of each event history) to the user and provides a point and click interface that allows the user to inspect any other tree in that subset. Initially, Notung arbitrarily selects one event history to present in the tree panel. The other optimal histories may be viewed using the drop-down menu labeled “Select an optimal event history,” which gives a list of up to 50 optimal event histories. The user can perform Same Cost Swaps on a tree to explore the space of all optimal trees corresponding to the current event history. Same Cost Swaps are node interchanges that result in another tree with an optimal D/L score. Clicking the “Examine same-cost swaps” button will highlight all swappable nodes, nodes that can be manually swapped without changing the D/L Score.
If there are more than 50 optimal event histories, they can be generated using the Command Line Interface (see Chapter 12 - Command Line Options and Batch Processing). Note that both the drop down menu and command line options give distinct optimal event histories, but do not generate all optimal gene tree rearrangements. It is only possible to view all trees by performing same cost swaps using the point and click interface in the GUI.
For further details on Notung’s rearrangement algorithm see:
D. Durand, B. V. Halldorsson, B. Vernot. A Hybrid Micro-Macroevolutionary Approach to Gene Tree Reconstruction. Journal of Computational Biology, 13(2): 320-335, 2006.
Click on image to see larger version
Figure 7.2: (a) When rearranging the non-binary gene tree, weak edges are highlighted in yellow. These edges, as well as the polytomies, highlighted in cyan, will be rearranged to produce the binary tree with the minimal D/L Score. (b) After the tree is rearranged, weak edges are highlighted in yellow. Notice that new edges have no edge weight and are considered weak.
To rearrange the gene tree:
A minimum cost rearrangement tree will appear in the tree panel as shown in Figure 7.1(a). Note that weak edges, highlighted in yellow, will not have edge weights. Some or all of these are edges that do not correspond to any bipartition (split) represented in the original tree. The appropriate weights for these edges are not known.
NOTE: If asked to rearrange a tree that has not been reconciled, Notung will reconcile it automatically. In this case, the user is asked to select a species tree for reconciliation.
To highlight all weak edges (default: OFF):
All weak edges in the tree will be highlighted in yellow.
To view alternate optimal event histories:
If more than one optimal event history exists for a rearranged tree, the drop down menu “Select an optimal event history’’ will be enabled.
The tree panel will now show a new tree corresponding to the selected alternate history.
If there is only one optimal history or the tree has not yet been rearranged, the drop down menu will be grayed out.
Click on image to see larger version
Figure 7.3: Swappable nodes are marked with the enlarged square. The selected node, shown in blue, can be swapped with the node highlighted in orange.
Click on image to see larger version
Figure 7.4: Clicking on first the blue node and then on the orange node in Figure 7.3 results in the alternate optimal tree shown here.
To swap individual nodes:
NOTE: If there are no swappable nodes in the tree or if the tree has not yet been rearranged, this button will be grayed out.Swappable nodes are marked with an enlarged blue and cyan square. As you pass the mouse over a swappable node it will be highlighted with a blue triangle. Other nodes that can be interchanged with it with are temporarily highlighted with a light orange triangle, as shown in Figure 7.3. If you have zoomed in, some swappable nodes may be outside the boundaries of the tree panel. Swappable nodes that are not currently visible are indicated by arrows in the tree panel, pointing in the direction of those nodes. These can be seen by scrolling in the direction of the arrow.
NOTE: When a user selects a different alternate event history from the “Select an optimal event history” list, Notung rebuilds the tree from data saved at the time of rearrangement. Any manual swaps made to a previously viewed event history will be lost. Therefore, if you wish to save information after a manual swap, you must save your tree. See Chapter 3.3 - Opening and Saving Trees for more information.