\chapter{Rearrange Mode}
\label{Rearrange Mode}
%% \MS{New stuff re: non-binary trees.  
%% NBSTs with BGTs
%% Also in Theory: At this time, Notung is not able to rearrange a binary
%% gene tree if the species tree is non-binary.
%% BSTs with NBGTs
%% Also in Theory: Notung’s Rearrange function (\lcsee ) can be applied to a non-binary gene tree when the species tree
%% is binary.
%% The resulting gene tree is binary.
%% Standard algorithm is used to resolve all the polytomies and then
%% rearrange the tree.

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.
%% More
%% precisely, we define a \textbf{Connected Component of Weak Edges
%% (CCW)} to be a maximal set of adjacent edges with weights below the
%% user-defined Edge Weight Threshold.
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 ``\textbf{Highlight weak edges}''
checkbox in \textbf{Rearrange} mode will highlight all weak edges in
yellow, allowing the user to see which edges will be considered for
rearrangement (see~\figlink{fig16}).  This option is only available in
\textbf{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;
\lcseelink{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 (\textit{i.e.} those trees with a
minimal D/L Score).
\begin{figure}[t]
\centering\subfigure[]{
\includegraphics[width=4in]{images/chap8_weak_edges_resize.png}}
\subfigure[]{\includegraphics[width=4in]{images/chap8_rearranged_resize.png}}
\caption{(a) The gene tree from~\figlink{fig10} with weak edges
    highlighted.  (b) After clicking ``Perform Rearrangement,'' the
    rearranged tree appears in the tree panel.  Weak edges are still
    highlighted in yellow.\label{fig16}}
\end{figure}

The \textbf{Rearrangement} function can be applied to a non-binary
gene tree when the species tree is binary (\figlink{fig17}).  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.

%% bv edited to here

\clearpage
\section{Alternate Optimal Hypotheses}
\label{Alternate Optimal Hypotheses}
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 \textbf{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 \texttt{((g1\_mouse, g2\_mouse), (g3\_mouse, g4\_mouse))}, as
well as the subtree \texttt{((((g1\_mouse), g2\_mouse), g3\_mouse),
g4\_mouse)}.
 
If multiple minimum cost trees are found, Notung presents one tree
from each subset (\textit{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.
\textbf{Same Cost Swaps} are node interchanges that result in another
tree with an optimal D/L score.  Clicking the ``\textbf{Examine
same-cost swaps}'' button will highlight all \textbf{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 (\lcseelink{Command Line Options and Batch Processing}).  Note that both the drop down menu and
command line options give distinct optimal event histories,
\textit{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:
\begin{quote}
    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.
\end{quote}

\begin{figure}[t]
\centering \subfigure[]{
\includegraphics[width=4.5in]{images/chap8_weak_edges_nbgt_polytomies_resize.png}}
\subfigure[]{
\includegraphics[width=4.5in]{images/chap8_rearranged_nbgt_resize.png}}
\caption{(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. \label{fig17} }
\end{figure}

\clearpage

\section{Rearrangement Commands}

\textbf{To rearrange the gene tree}:
\begin{enumerate}
   \item Click the \textbf{Rearrange} tab to enter \textbf{Rearrange} mode.
   \item Click ``\textbf{Perform Rearrangement}.''
   \begin{quote}
      A minimum cost rearrangement tree will appear in the tree panel
      as shown in~\figlink{fig16}(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.
   \end{quote}
\end{enumerate}
\textit{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.
  
\textbf{To highlight all weak edges (default: OFF): }
\begin{itemize}
   \item Click the ``\textbf{Highlight weak edges}'' checkbox.
   \begin{quote}
      All weak edges in the tree will be highlighted in yellow.
   \end{quote}
\end{itemize}

\textbf{To view alternate optimal event histories:} 
\begin{quote}
   If more than one optimal event history exists for a rearranged
   tree, the drop down menu ``\textbf{Select an optimal event history'}' will
   be enabled.
\end{quote}
\begin{itemize}
   \item From the drop-down menu, select an alternate event history.
   \begin{quote}
      The tree panel will now show a new tree corresponding to the
      selected alternate history.
   \end{quote}
\end{itemize}
If there is only one optimal history or the tree has not yet been
rearranged, the drop down menu will be grayed out.

\begin{figure}[!h]
\centering
\includegraphics[width=4.5in]{images/chap8_rearranged_same_cost_swaps_before_resize.png}
\caption{Swappable nodes are marked with the enlarged square.  The
   selected node, shown in blue, can be swapped with the node
   highlighted in orange.  \label{fig18}}
\end{figure}

\begin{figure}[!h]
\centering
\includegraphics[width=4.5in]{images/chap8_rearranged_same_cost_swaps_after_resize.png}
\caption{Clicking on first the blue node and then on the orange node
   in \figlink{fig18} results in the alternate optimal tree shown here.
\label{fig19}}
\end{figure}

\clearpage

\textbf{To swap individual nodes:}
\begin{enumerate}
   \item Click the ``\textbf{Examine same cost swaps}'' button in the
         right column on the \textbf{Rearrange} task panel.
   \begin{quote}
      \textit{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.
   \end{quote}
         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~\figlink{fig18}.  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.
   \item Click a node to swap.  The node you selected is highlighted
         with a blue triangle.  Nodes with which it can be swapped are
         now highlighted with red triangles.
   \item Click a second node to complete the swap
         (see~\figlink{fig19}).
\end{enumerate} 

\textit{NOTE}: When a user selects a different alternate event history
from the ``\textbf{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.  \seelink{Opening and Saving Trees} for more
information.

