\documentclass[12pt,pdftex]{book} \usepackage{amsmath} % need for subequations \usepackage[pdftex]{color,graphicx} % need for figures \usepackage{verbatim} % useful for program listings \usepackage{subfigure} % use for side-by-side figures \usepackage[hang,scriptsize,bf]{caption} \usepackage{cite} \usepackage{tabularx} \usepackage{longtable} \usepackage[pdftex,colorlinks]{hyperref} % use for hypertext links, including those to external documents and URLs % above is the preamble \newcommand{\chaplink}[1]{\hyperref[#1]{Chapter \ref{#1}}} \newcommand{\apendixlink}[1]{\hyperref[#1]{Appendix \ref{#1}}} \newcommand{\seelink}[1]{See \hyperref[#1]{chapter \ref{#1} - #1} on page \pageref{#1}} \newcommand{\lcseelink}[1]{see \hyperref[#1]{chapter \ref{#1} - #1} on page \pageref{#1}} \newcommand{\seeappendixlink}[1]{See \hyperref[#1]{Appendix \ref{#1} - #1} on page \pageref{#1}} \newcommand{\lcseeappendixlink}[1]{see \hyperref[#1]{Appendix \ref{#1} - #1} on page \pageref{#1}} \newenvironment{listWee}[1]{\textbf{#1}\begin{enumerate}}{\end{enumerate}} \newenvironment{listWei}[1]{\textbf{#1}\begin{itemize}}{\end{itemize}} \newcommand{\figlink}[1]{\hyperref[#1]{figure \ref{#1}}} \newcommand{\tablink}[1]{\hyperref[#1]{table \ref{#1}}} \setlength{\parskip}{14pt} \setlength{\parindent}{0pt} \pagestyle{headings} \begin{document} \chapter{Introduction to Notung} \label{Introduction to Notung} Notung offers a unified framework for incorporating information about duplication and loss into phylogenetic tasks. Notung can : \begin{itemize} \item reconcile a gene tree with a species tree; \item identify gene duplications and estimate upper and lower bounds on the time of duplication; \item root an unrooted gene tree by minimizing gene duplications and losses; \item rearrange rooted trees that have weakly-supported edges to minimize duplications and losses; \item resolve non-binary nodes in a non-binary gene tree. \end{itemize} \setlength{\parskip}{14pt} Notung differs from other reconciliation software in that it is the first and only software to reconcile and root non-binary gene trees with binary species trees and binary gene trees with non-binary species trees in addition to traditional analysis with binary gene trees and binary species trees. Another novel feature is Notung's ability to rearrange and resolve non-binary gene trees. Notung provides a graphical interface for tree manipulation and visualization and offers a command line option that can be used for automated analysis of a large number of trees. Notung utilizes novel, efficient algorithms[1, 2, 3] for reconstructing the history of gene duplications and losses, for rooting gene trees based on duplication/loss parsimony and for the rearrangement of weakly supported areas of gene trees. More information about Notung can be found at: \begin{center} http://www.cs.cmu.edu/$\sim$durand/Notung \end{center} More information about other Durand Lab projects can be found at: \begin{center} http://www.cs.cmu.edu/$\sim$durand/Lab \end{center} Notung can be used to address a broad range of applications. It can assist scientists who wish to bring gene duplication models to bear on gene tree construction; evolutionary biologists studying the history of a gene family; and experimental biologists interested in incorporating evolutionary insights into questions of function and structure. The graphical user interface was partially constructed using the tree visualization library provided by FORESTER (version 1.92) [4]. \textbf{How to cite Notung}: 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. B. Vernot, M. Stolzer, A. Goldman, D. Durand. Reconciliation with Non-Binary Species Trees. In Computational Systems Bioinformatics: CSB2007 Conference Proceedings, Imperial College Press, 2007: 441-452. \chapter{Using This Manual} \label{Using This Manual} This manual provides a detailed description of Notung, and gives step-by-step instructions for Notung's tasks and visualization features. It assumes familiarity with basic concepts of phylogeny reconstruction. For more information on these subjects, refer to basic textbooks, such as [5, 6]. A \hyperref[Glossary]{Glossary} is provided on page \pageref{Glossary}. Additional sources are provided in the \hyperref[Bibliography]{Bibliography} on page \pageref{Bibliography}. \hyperref[Worked Examples]{Worked Examples} are provided on page \pageref{Worked Examples}. The manual is organized into numbered chapters by topic. Each chapter begins with paragraphs describing the topic, followed by a list of step-by-step commands for operations associated with the topic. Figures showing the Notung graphical interface have been included to illustrate program displays and command results. A brief discussion regarding the relevant evolutionary theories regarding non- binary species and gene trees will be provided in \chaplink{Non-Binary Trees}. A basic introduction to the Notung GUI is provided in \chaplink{Getting Started}. Notung's five task modes are described in \chaplink{Reconciliation Mode} - \chaplink{Annotations}. \chaplink{Changing the Appearance of the Tree Panel} describes options for changing the appearance of the tree. Detailed information regarding batch processing of trees using the command line is located in \chaplink{Command Line Options and Batch Processing}. More detailed information about input/output and tree file formats are given in the \apendixlink{File Formats}. \chapter{Downloading and Running Notung} \label{Downloading and Running Notung} The Notung package can be downloaded from the Notung website in the file Notung-2.5.zip. When the file is unzipped, it will create a folder called \textit{Notung-2.5} that includes: this manual; a folder of sample trees; a folder of a sample batch run; and the Notung program file, Notung-2.5.jar. Notung is supported on Windows 2000 and Windows XP, Mac OS X 10.3 and above, and Linux. To run Notung, Java must be installed on your computer. Notung has been tested under Java 1.4.2, but should work for newer versions of Java. \textbf{To download Notung-2.5}: \begin{center} Go to http://www.cs.cmu.edu/$\sim$durand/Notung/download.html \end{center} \textbf{To unzip Notung-2.5.zip}: \emph{On Windows}: \begin{itemize} \item If you are running Windows XP or newer, double click on Notung-2.5.zip. \item If you are running Windows 2000 or earlier, use WinZip to open Notung-2.5.zip and extract its contents. If you do not have WinZip, go to http://www.winzip.com and download the WinZip application. \end{itemize} \emph{On Mac OS X}: \begin{itemize} \item Double click on Notung-2.5.zip. \end{itemize} \emph{On Linux}: \begin{itemize} \item Run the command: \begin{verbatim} unzip Notung-2.5.zip \end{verbatim} \end{itemize} \textbf{If you do not know if you have Java}: \begin{itemize} \item Go to http://www.java.com/en/download/help/testvm.jsp, or, in a terminal or command window, type \begin{verbatim} java -version \end{verbatim} Notung requires at least Java 1.4. \end{itemize} \textbf{To get Java (if you do not have it)}: \begin{itemize} \item For Windows and Linux, go to: http://java.sun.com/webapps/getjava/BrowserRedirect \item For Mac OS X use the Software Update application to install or update Java. \end{itemize} \textbf{To run Notung}: \emph{Using the graphical user interface on Windows or Mac OS X}: \begin{itemize} \item Unzip the downloaded file. \item Double-click on the file Notung-2.5.jar. \end{itemize} \textbf{Using the graphical user interface on Linux}: \begin{itemize} \item Unzip the downloaded file and move into the Notung directory. \item Enter in the command line: \begin{verbatim} java -jar Notung-2.5.jar \end{verbatim} \end{itemize} In addition, Notung can perform many of its operations from the command line without launching the graphical user interface. \seelink{Command Line Options and Batch Processing} for more information. \chapter{Non-Binary Trees} \label{Non-Binary Trees} A \textbf{non-binary}, or \textbf{multifurcating}, tree is a tree where at least one node has more than two children. Such nodes are referred to as \textbf{polytomies}. A non-binary tree may also be referred to as an unresolved tree, because a polytomy represents a degree of uncertainty regarding the topology of the tree. Since Notung displays trees as rectangular cladograms, polytomies are represented as vertical edges with more than two children. See, for example, the polytomy in \figlink{fig1}. \setlength{\textfloatsep}{15mm} \begin{figure}[!h] \centering \includegraphics[scale=0.75]{images/image004.jpg} \caption{Notung displays trees as cladograms. Polytomies are vertical edges with more than two children. The only polytomy in this tree is indicated by the arrow.\label{fig1}} \end{figure} Notung can fit a binary gene tree to a non-binary species tree or a non-binary gene tree to a binary species tree, but currently cannot compare a non-binary gene tree with a non-binary species tree. The specific functions that Notung can perform on each combination of inputs are given in ~\tablink{tab1} . \begin{table}[!hbp] \begin{tabular}{c|c||c|c|c|c} \hline \textbf{Gene Tree} & \textbf{Species Tree} & \textbf{Reconcile} & \textbf{Root} & \textbf{Rearrange} & \textbf{Resolve}\\ \hline Binary & Binary & yes & yes & yes & N/A\\ \hline Non-Binary & Binary & yes & yes & yes & yes\\ \hline Binary & Non-Binary & yes & yes & no & N/A\\ \hline \end{tabular} \caption{Notung's main functions on binary and non-binary trees.\label{tab1}} \end{table} \subsection*{Non-binary Species Trees} Many sources of species trees, such as the \href{http://www.ncbi.nlm.nih.gov/}{NCBI Taxonomy Database} , permit polytomies in a species tree. In fact, non-binary species trees may be common - 64\% of branch points in the NCBI Taxonomy Database \cite{Copley02} have three or more children. Since a species tree represents the evolution of a population of organisms, a polytomy may represent either the simultaneous divergence of all descendants (a \textbf{hard polytomy} ), or the uncertainty in reconstructing the true binary branching pattern (a \textbf{soft polytomy} ). Simultaneous divergences of three or more lineages can occur due to the isolation of subpopulations within a widespread species by sudden meteorological or geological events, or rapid expansion of the population into open territory, resulting in reproductive isolation. Soft polytomies often occur if a sequence of binary divisions follow each other in close succession and the time between events is insufficient to accumulate informative variation. \subsection*{Non-binary Gene Trees} In contrast to species trees, a gene tree traces the evolution of a sequence, rather than a population. Divergence occurs through gene duplication or cell division. Since the product of either of these events is exactly two descendant sequences, the true branching pattern in a gene tree is always binary. If the true binary branching process cannot be resolved, some phylogeny reconstruction programs will output non-binary gene trees in which a polytomy represents uncertainty. Such uncertainty often arises if binary divisions occur too rapidly to accumulate informative variation or if the data set is noisy. \section{Reconciliation} \label{Reconciliation} In addition to traditional reconciliation of binary gene trees with binary species trees, Notung can reconcile binary gene trees with non-binary species trees, as well as non-binary gene trees with binary species. \subsection{Binary Gene Tree and Non-binary Species Tree} Reconciling a binary gene tree with a non-binary species tree results in a binary gene tree with duplications and losses added. The reconciled tree is always binary because the true branching pattern of a gene tree is always binary. Since a species tree represents the evolution of a population of organisms, gene trees with different binary branching processes can be consistent with a species polytomy. If multiple alleles are present in a population when lineages diverge, a different allele may fix in each lineage. The resulting gene tree will be binary and will reflect the order in which new alleles arose in the ancestral population. This process is called \textbf{incomplete lineage sorting}. When the time of separation of the lineages in the gene tree predates the time of speciation, the divergence is referred to as a \textbf{deep coalescence event}. Deep coalescence can also occur if two or more binary speciation events occur in rapid succession. If the time between subsequent speciations is shorter than the fixation time, more than one allele will still be present at the time of the second speciation. Each population may randomly fix a different allele so that the branching pattern of t! he gene tree is not congruent to the branching pattern of the species tree. \begin{figure}[!h] \centering \includegraphics[scale=0.75]{images/image006.jpg} \caption{Different gene families evolving in the same species polytomy may have different binary topologies. In this example, the possible binary gene trees could result in genes from B and C most closely related (left tree), genes from A and B most closely related (center tree), or genes from A and C most closely related (right tree). \label{fig2}} \end{figure} For these reasons, incongruence between binary gene and non-binary species trees can indicate either deep coalescence or duplication. This is fundamentally different from the case where both trees are binary and disagreement always implies a duplication. To account for this, Notung uses a novel reconciliation algorithm \cite{Patthy03} for non-binary species trees that distinguishes between cases in which disagreement can only be explained by a duplication (\textbf{required duplications}) and cases in which it is not possible to determine whether the disagreement is due to deep coalescence or duplication (\textbf{conditional duplications}). Notung reports required duplications and conditional duplications separately. Inferring loss events is also fundamentally different when the species tree is non-binary. When both trees are binary, an inferred loss is always unambiguously assigned to a specific edge in the gene tree. However, when a loss is associated with a polytomy in the species tree, it is, in general, only possible to identify a set of candidate edges. The inferred loss must have occurred on one of these edges, but it is not possible to determine which one. In Figure 3d, for example, a gene loss in species A could be placed on any of the three colored edges indicated. To resolve this ambiguity, Notung assigns each loss to a specific edge within the set, in such a way as to minimize the total number of losses. Two novel algorithms for inferring losses, based on different minimization criteria, have been implemented in Notung. \begin{figure}[!h] \centering \includegraphics[scale=0.75]{images/image008.jpg} \caption{Losses associated with a polytomy in the species tree are ambiguous. In the subtree of the gene tree (d), a gene is lost in species A. This loss can be placed on three possible edges. Placing a loss on the green edge implies that A diverged first and was then lost (a); the blue edge implies that A was lost after C, which diverged first (b); the red edge implies that A was lost after B, which diverged first (c). The tree in e shows the result of placing the loss as high as possible. \label{fig3}} \end{figure} The first algorithm is based on the observation that losses in sibling species of a polytomy can be explained by a single loss in their common ancestor. Under this scenario, the total number of losses can be reduced by combining losses that share a parent. The combined polytomy loss algorithm considers all possible loss assignments and selects the assignment that minimizes the total number of \textbf{combined losses}. This algorithm is exponential in the size of the largest polytomy in the pruned species tree. It is only implemented in the command line interface of Notung. Base on performance tests, in which we reconciled 1173 binary gene trees from TreeFam 3.0\cite{Bashton02} with non-binary species trees on a 3.2ghz Opti-Plex GX620 computer, users should be prepared for extended running times if the species tree has a polytomy with more than 12 children. The second algorithm minimizes the total number of uncombined losses. These are referred to as \textbf{explicit losses}. Once the losses have been identified, they are then combined wherever possible. This algorithm runs in polynomial time. It is implemented in both the graphical user interface and the command line interface. In many, if not most, cases, minimizing explicit losses, and then combining them where possible will produce the same results as the combined losses algorithm. For algorithms and details on reconciliation with non-binary species trees, see: B. Vernot, M. Stolzer, A. Goldman, D. Durand. Reconciliation with Non-Binary Species Trees. In \textit{Computational Systems Bioinformatics: CSB2007 Conference Proceedings}, Imperial College Press, 2007: 441-452 \chapter{Getting Started} \label{Getting Started} Notung is a tool for comparing gene and species trees. Notung takes tree files as input and allows users to refine and manipulate them. The modified trees can be saved as output. The following subsections introduce basic input and output in Notung, general tree statistics, the graphical user interface, and the parameter values used in Notung's tree refinement tasks. \section{Gene and Species Trees} \label{Gene and Species Trees} To perform its functions, Notung requires a gene tree and a species tree. The species tree must contain all the species from which genes in the gene tree were sampled. The species tree may contain additional species as well - these will be ignored. A correspondence between the leaves of the species and gene trees is determined by the leaf labels in the gene tree. The label must include a substring that specifies the species from which the gene was sampled, as well as be consistent with the labels used in the species tree. Labels may be provided in Newick, NHX, or Notung format. \seeappendixlink{File Formats} for further information. Notung can operate on a non-binary gene tree or a non-binary species tree. However, its functions cannot run when both the gene tree and corresponding species tree are non-binary. \seelink{Non-Binary Trees} for more information. For a complete summary of functions that Notung can perform, see \tablink{tab1} on page \pageref{tab1}. \subsection*{Species Trees} The species tree must be rooted, with leaf nodes labeled with species names. The internal nodes may be given taxonomic labels (e.g., "\textit{tetrapodia}"). If the internal nodes are not labeled, Notung will assign alphanumeric labels (such as\textit{ n1, n2, etc}.). If the species tree has edge weights or branch lengths, this information will be ignored. The tasks that Notung performs are based on the assumption that the user has selected a species tree that is a reliable representation of the true species relationships. Using Notung with an incorrect species tree will give incorrect results. \subsection*{Gene Trees} In order to perform reconciliation and rearrangement, Notung requires a rooted gene tree. If the gene tree is not rooted, it can be rooted using Notung. \seelink{Rooting Mode} for more information. The gene tree must have leaf nodes labeled to specify the gene sequence as well as the species from which the gene was sampled. \seeappendixlink{Specifying the Species Associated with Each Gene} for more information. The internal nodes may be labeled. If the internal nodes are not labeled, Notung will assign alphanumeric labels (e.g. \textit{n5, n6, etc}.). In Rearrangement mode, Notung requires that the tree have edge weights. These are used to identify edges that are weakly supported and may be rearranged. These weights may be bootstrap values, posterior probabilities, edge lengths, or any other weighting scheme selected by the user. Several different fields in the Newick and NHX formats may be used to store edge weights. \seeappendixlink{File Formats} for details of these formats and how to indicate to Notung which field is being used for edge weights in a particular input tree. If the gene tree is binary and unrooted, it might have one trifurcation (a node with three children) at the top of the tree. This node can be resolved by rooting the tree in Notung. \seelink{Rooting Mode} for more information. If the gene tree is non-binary, it too can be rooted, reconciled, rearranged, and resolved with Notung, so long as the species tree is binary. \section{The Graphical User Interface} \label{The Graphical User Interface} Notung's graphical interface facilitates tree visualization and manipulation, enabling the user to inspect duplicated nodes and lost leaves in a tree, and annotate gene subfamilies for visual differentiation or presentation. The graphical user interface (GUI) is available on all platforms. Notung can also be run from the command line without opening the GUI. \seelink{Command Line Options and Batch Processing} for a description of the command line interface. When Notung is first launched, the program window will be blank. \figlink{fig4} and \figlink{fig5} show Notung's graphical interface once a gene tree and species tree have been opened. Notung's graphical user interface has the following components: \textbf{Tree panel}: The tree that is currently selected appears in the tree panel. Both gene and species trees are rendered here with the root at left and leaf nodes at right. Nodes are denoted by small blue squares in the tree. Edge weights and leaf node names appear in the tree by default (\seelink{Display Options} for instructions on how to modify the labeling of the tree). The size of the tree and tree labels can be modified using the Fonts and Zoom menus (\seelink{Display Options}). Notung fits the whole tree in the tree panel by default. \begin{figure}[!h] \centering \textbf{Program Window} \includegraphics[scale=0.75]{images/image014.jpg} \caption{ Notung's graphical user interface displaying a gene tree. The different panels are highlighted in red (tree panel), blue (task panel), and yellow (parameters panel). \label{fig4}} \includegraphics[scale=0.75]{images/image016.jpg} \caption{ Notung's graphical user interface displaying a species tree. Only the tree panel (red) and the task panel (blue) are available. \label{fig5}} \end{figure} Although multiple trees can be open in Notung at once, Notung operates on only one tree at a time. To facilitate working with many trees, Notung marks each open tree with a tab at the top of the tree panel. Clicking on a tab selects the corresponding tree. Tabs are labeled with the file name and special icons to identify them as a gene or species tree - a DNA helix for gene trees, and a cartoon of the evolution of humankind for species trees (see \figlink{fig6}). \begin{figure}[!h] \centering \includegraphics[scale=0.75]{images/image014.jpg} \caption{ Tree tabs for a gene tree (left) and a species tree (right) \label{fig6}} \end{figure} \textbf{Task panel}: Operations on the gene tree are performed in the task panel (see \figlink{fig4}). Tabs at the top of the task panel correspond to the various tasks that Notung can perform. Clicking on a tab puts Notung in the corresponding task mode, revealing the buttons that control tasks specific to that mode. If the gene tree is selected, six modes are available: History, Reconciliation, Rooting, Rearrange, Resolve, and Annotations. Only the History and Annotation modes can be used when a species tree is selected. \textbf{Parameter values}: When a gene tree is selected, boxes displaying the Edge Weight Threshold and Duplication, Conditional Duplication, and Loss Costs appear in the bottom-right corner of the program window. These values can be changed using the Edit Values button directly below them. Note that when a species tree is selected, the program window will not display the parameter values. \section{Opening and Saving Trees} \label{Opening and Saving Trees} Notung reads and saves tree files in Newick, NHX, and Notung file format. NHX and Notung file formats are extensions of Newick; \seeappendixlink{File Formats} for details. Notung can also save the image in the tree panel as a Portable Network Graphic (PNG) file. \textbf{To open trees}: \begin{enumerate} \item Click "File $\rightarrow$ Open Gene Tree" or "File $\rightarrow$ Open Species Tree." \item In the Open dialog box, select a tree file and click "\textbf{Open}." \begin{quote} \textit{NOTE:} Notung cannot distinguish gene trees from species trees automatically. If a gene tree is opened as a species tree, or a species tree is opened as a gene tree, reconciliation will produce incorrect results. \end{quote} \end{enumerate} \textbf{To reload a tree}: \begin{enumerate} \item Click "File $\rightarrow$ Reload from File." \item In the Open dialog box, select a tree file and click "\textbf{Open}." \end{enumerate} \textbf{To save trees}: \begin{enumerate} \item Click "File $\rightarrow$ Save As." \item In the drop-down menu, select one of the following formats: \begin{itemize} \item Notung File Format (*.ntg) \item Newick File Format (*.nh) \item NHX File Format (*.nhx) \end{itemize} \item Click "\textbf{Save}." \begin{quote} \textit{NOTE:} The default format for saving trees is the Notung File Format. \end{quote} \end{enumerate} \textbf{To save an image of a tree as a PNG file}: \begin{itemize} \item Click "File $\rightarrow$ Save Current View as PNG." \begin{quote} \textit{NOTE:} The PNG file saves only the image currently visible in the tree panel. If you have zoomed in on a tree, the PNG will save only the section in view. \end{quote} \end{itemize} \textbf{To print an image of a tree}: \begin{enumerate} \item Click "File $\rightarrow$ Print Current View." \item The print dialogue box will appear. Change the settings as necessary and click "\textbf{OK}." \begin{quote} \textit{NOTE:} For most printers the default page layout will be portrait; however, the landscape layout is usually preferred for printing trees from Notung. \end{quote} \item A red rectangle will appear in the tree panel. Only the structure inside this rectangle will be printed. Select one of the available buttons: \item To proceed with the printing, click "\textbf{Print}." \item If you wish to change the printer's settings or the size of the tree, click "\textbf{Cancel}." The red rectangle will disappear and the appearance of the tree can be manipulated. \begin{quote} \textit{NOTE:} It may be necessary to change both the printer's settings (i.e. page layout, margins, etc.) and the appearance of the tree so that the desired print area fits within the red rectangle. \seelink{Zoom} for more information on zooming in and out of the tree. \end{quote} \end{enumerate} \textbf{To close trees}: \begin{enumerate} \item Select the tree to close. \item Click "File $\rightarrow$ Close." \end{enumerate} \subsection{General Tree Statistics} \label{General Tree Statistics} Notung compiles information on tree characteristics, such as height, number of leaves, number of nodes, etc. Notung reports this information in the general tree statistics box under the "Info" menu. The properties examined depend on whether the given tree is a gene tree or a species tree, and whether the gene tree has been reconciled or not. The following information is reported for species trees and \textit{unreconciled} gene trees: \begin{description} \item[\textit{Total nodes} :] the total number of nodes \item[\textit{Leaf nodes} :] the total number of leaves \item[\textit{Internal nodes} :] the total number of internal nodes (Total nodes minus Leaf nodes) \item[\textit{Polytomies} :] the total number of polytomies in the tree. This number will be zero if the tree is binary. \item[\textit{Size of largest polytomy} :] the number of children of the largest polytomy in the tree. This number will be zero if the tree is binary. \item[\textit{Height} :] the maximum path length from a leaf node to the root \end{description} \begin{figure}[!h] \centering \includegraphics[scale=0.75]{images/image020.jpg} \caption{ General tree statistics for the species tree shown in Figure 1 \label{fig7}} \end{figure} If the gene tree \textit{has} been reconciled, more information is available regarding the tree. Notung will report the statistics given above under the heading, \textit{Tree Without Losses}. The following statistics, based on the gene tree with losses included, are listed under the heading of \textit{Tree With Losses}: \begin{description} \item[\textit{Total nodes} :] the number of internal and leaf nodes \item[\textit{Leaf nodes }:] the total number of leaves (the number of original leaves plus the number of losses) \item[\textit{Internal nodes} :] the total number of internal nodes. This includes any internal nodes that were added to "attach" a loss as a leaf node. \item[\textit{Size of largest polytomy} :] the number of children of the largest polytomy in the tree. This number will be zero if the tree is binary. It will also equal its counterpart for the unreconciled tree if the largest polytomy does not have any losses associated with it. \item[\textit{Height} :] the maximum path length from any leaf node (including loss nodes) to the root \end{description} \begin{figure}[!h] \centering \includegraphics[scale=0.75]{images/image020.jpg} \caption{ General tree statistics for a reconciled gene tree. \label{fig8}} \end{figure} In addition, the following statistics regarding the reconciliation of the tree will be under the heading \textit{Reconciliation Information}: \begin{description} \item[\textit{Duplications} :] the total number of duplications in the reconciled gene tree \item[\textit{Conditional Duplications} :] the number of conditional duplications in the reconciled gene tree. This number will be zero if there are no conditional duplications. \item[\textit{Losses} :] the total number of losses in the reconciled gene tree. \end{description} If the gene tree has been reconciled, the species tree that was used will be reported, as well as the tree statistics for the \textit{pruned species tree}. \textbf{To get general statistics for the tree shown}: \begin{enumerate} \item Click "Info $\rightarrow$ General Tree Statistics." \begin{quote} A window will appear containing information on the tree's characteristics, as described above. \\ \\ \textit{NOTE:} Information on duplication bounds and losses can also be gathered through the Info Menu with Duplication Bounds and Loss Counts. For more information on duplication bounds, \seelink{Duplication Bounds and Loss Information}. \end{quote} \end{enumerate} \subsection{Parameter Values} \label{Parameter Values} The parameter values used in Notung - the Edge Weight Threshold, Duplication Cost, Conditional Duplication Cost, and Loss Cost - can be specified by the user. These values influence the results produced by Notung's tree rearrangement tasks. Notung uses a Duplication/Loss Score to score reconciled trees and evaluate alternate roots. The \textbf{D/L Score} is defined to be: \begin{math} c_{L}~L + c_{ D }~D + c_{ C }~C \end{math} where L is the number of losses, D is the number of duplications and C is the number of conditional duplications implied by the current reconciliation. The loss cost, $c_{L}$, duplication cost, $c_{D}$, and conditional duplication cost, $c_{C}$ reflect the relative importance of losses, duplications, and conditional duplications in scoring the tree. The user can specify these costs. The default values are 1.0 for losses, 1.5 for duplications, and no cost for conditional duplications. Notung displays the reconciled tree's D/L Score, along with the number of losses, duplications, and conditional duplications in the bottom-left corner of the program window (see \figlink{fig9}). \begin{figure}[!h] \centering \includegraphics[scale=0.75]{images/image027.jpg} \caption{ If the gene tree has been reconciled, the D/L Score (the number of duplications, conditional duplications, losses) and the species tree used to reconcile it appear at the bottom of the program window. \label{fig9}} \end{figure} The Edge Weight Threshold is a parameter used to define the set of strong edges in the gene tree. In Rearrange mode, edges weighted below the Edge Weight Threshold are considered weak and may be rearranged (for more information about rearrangement, \seelink{Rearrange Mode}). Since edges with no weight specified are assigned an edge weight of zero, these edges will also be considered weak. The default threshold is 90\% of the highest edge weight in the gene tree file. If no edge weights are found, the threshold is set to one. The user may change this cutoff if a different threshold is desired for the current data set. \textbf{To adjust the parameter values}: \begin{enumerate} \item Click the "\textbf{Edit Values}" button. A dialog box appears. \item Enter the appropriate values in the text field, and then click "\textbf{Apply Changes.}" \begin{quote} \textit{NOTE:} This will change the value settings only for the gene tree that is currently selected. Also, each history state saves the parameter values used at that state; when moving through the history, parameter values may change depending on the state and tree viewed. For more information on history states, \seelink{History}. \end{quote} \end{enumerate} \chapter*{Task Modes} \label{Task Modes} The following sections describe the tasks that can be performed using Notung's task panel. The gene tree refinement tasks - \textbf{Reconciliation, Rooting, Rearrangement,} and \textbf{Resolve} - are described first, followed by \textbf{History} and \textbf{Annotations}. Note that the History and Annotations modes can be used when either a gene or a species trees is selected, while Reconciliation, Rooting, Rearrangement, and Resolve can only be performed on a gene tree. \chapter{Reconciliation Mode} \label{Reconciliation Mode} In Reconciliation mode, Notung compares a gene tree with a species tree to infer gene duplications and losses. Notung will display a reconciled tree in the tree panel with inferred duplication events marked and loss nodes present. The D/L Score of the reconciled tree will be displayed in the lower left corner of the screen (see \figlink{fig10}). Notung requires that gene and species trees have compatible labels, so that for each gene, the species from which it originated can be identified. An error message will appear if one or more gene labels cannot be matched to a label in the species tree. See \seeappendixlink{Specifying the Species Associated with Each Gene} for further information on gene labels. All species represented in the gene tree must be present in the species tree, but the species tree may include additional species. During reconciliation, Notung automatically identifies the species in the species tree that are not present in the gene tree, and generates a pruned species tree with those species removed. This tree is not shown or saved unless the user does so explicitly. This tree can be viewed using the "Show Pruned Species Tree" button. During reconciliation, Notung determines lower and upper bounds on the time of each duplication and conditional duplication, where bounds are represented in terms of internal nodes in the species tree; \textit{i.e.}, in terms of ancestral species. The upper bound on the time of duplication is the most recent species in which the duplication was not present. The lower bound is the oldest species in which the duplication must have been present. This information, along with statistics on losses, can be viewed in a new window by using the "Show Duplication Bounds" button. Duplications and bounds in this window are identified by internal node names. For losses, each node in the species tree is listed, followed by the number of losses associated with that taxon. To display internal node names in the tree panel, "Display Internal Node Names" and "Display Internal Node Species Names" must be turned on in the Display Options menu (see \seelink{Display Options}). \begin{figure}[!h] \centering \includegraphics[scale=0.75]{images/image033.jpg} \caption{ The reconciled gene tree appears in the tree panel. \label{fig10}} \end{figure} \section*{Alternate Optimal Hypotheses} When reconciling a non-binary gene tree with a binary species tree, Notung first resolves all polytomies in the gene tree to obtain binary nodes that minimize the D/L Score and then reconciles the resulting binary tree(s) with the species tree. Since there may be more than one binary resolution of the polytomy that has minimal D/L Score, there may be multiple reconciliations (see \figlink{fig11}). Notung addresses this issue by allowing the user to select the different histories that result in a minimum D/L Score for the polytomy. Each individual tree shows a different number of duplications and losses that could result in the same minimal D/L Score. 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. If there are more than 50 optimal event histories, they can be generated! using the Command Line Interface (\seelink{Command Line Options and Batch Processing}. \begin{figure}[!h] \centering \includegraphics[scale=0.75]{images/image033.jpg} \caption{ Reconciliation of a non-binary gene tree with a binary species tree. More than one duplication may be inferred at polytomies in the gene tree. In addition, it is possible to have more than one optimal event history, as seen in the lower left-hand corner. \label{fig11}} \end{figure} \textbf{To reconcile a gene tree with a species trees}: \begin{enumerate} \item Click the \textbf{Reconciliation} tab to enter Reconciliation mode. \item Click the "\textbf{Reconcile/Rereconcile}" button. A dialog box appears. \item In the dialog box, select the species tree for reconciliation in the drop-down menu. \item Check that Notung correctly identified the species naming convention used in the gene tree. The available settings are: \begin{itemize} \item Prefix of the gene label i.e., (SPECIESGENE) \item Postfix (underscore required) of the gene label i.e., (GENE\_SPECIES) \item NHX: species label is stored in the NHX comment field in the gene tree file. ( \textit{i.e.}, GENENAME[\&\&NHX:S=SPECIES] ) \\ \\ \begin{quote} If the convention selected by Notung is not the naming convention used in the gene tree, change it by selecting the appropriate radio button. \\ \\ \seeappendixlink{Specifying the Species Associated with Each Gene} for details about species tag specifications. \\ \\ \textit{NOTE:} The Prefix and Postfix formats require species names to be embedded in the gene names. NHX Species Tag format embeds the species information in a Newick comment field. The information will not appear on the screen when this format is used, unless the "Display Leaf Node Species Names" option in the \textbf{Display Options} menu is selected (\seelink{Display Options}). \end{quote} \end{itemize} \item In the dialog box, click "\textbf{Reconcile}." \end{enumerate} The reconciled tree appears in the tree panel (see \figlink{fig10}). Loss nodes appear in light gray type and state in which species the loss occurred. When reconciling a gene tree with a non-binary species tree, it is possible to have multiple, individual losses associated with children of a polytomy combined as one loss. When multiple polytomy losses are combined, the default display will state in which children of the polytomy the losses occurred as well as the corresponding species polytomy in the species tree (see \figlink{fig12}). Duplications appear in the tree as small red squares with red D's, while conditional duplications are small pink squares with pink cD's. Since more than one duplication may be associated with a polytomy in a gene tree, the number of duplications associated with that node will also be shown with the red D (see \figlink{fig11}). \seelink{Display Options} for more information on changing the appearance of loss nodes and duplications. \begin{figure}[!h] \centering \includegraphics[scale=0.75]{images/image029.jpg} \caption{ When reconciling a binary gene tree with a non-binary species tree, both conditional and required duplications are inferred. Conditional duplications are marked by pink cD's, while required duplications are indicated with red D's. \label{fig12}} \end{figure} A message at the bottom of the program window reminds you which species tree was used in reconciliation (e.g., "Reconciled with: "; see \figlink{fig12}). \textbf{To hide loss nodes/duplications}: \\ The duplication marks or loss nodes can be hidden to avoid a cluttered image. \begin{itemize} \item Click the appropriate checkbox in the Reconciliation task panel. \begin{description} \item[$\surd$ Display Loss Nodes (default: ON)] When the "Display loss nodes" box is checked, the implied lost nodes appear in the tree. To make the lost genes disappear, uncheck the box. \\ NOTE: If you are zoomed in when you uncheck "Display loss nodes," Notung will reset the image so that the whole tree fits in the tree panel. \item[$\surd$ Display Duplications (default: ON)] When the "Display duplications" box is checked, duplications are indicated on internal nodes by red D's. To make the duplication marks disappear, uncheck the box. \item[$\surd$ Display Conditional Duplications (default: ON)] When the "Display conditional duplications" box is checked, conditional duplications are indicated on internal nodes by pink cD's. To make the conditional duplication marks disappear, uncheck the box. \end{description} \end{itemize} These options will be grayed out if no reconciliation has been performed. The "Display Conditional Duplications" option will also be grayed out if the gene tree was reconciled with a binary species tree. \textbf{To view alternate optimal event histories}: \begin{enumerate} \item If more than one optimal event history exists for a rearranged tree, the drop down menu "Select an optimal event history" will be enabled. \item From the drop-down menu, select an alternate event history. \\ \\ The tree panel will now show a new tree corresponding to the selected alternate history. \end{enumerate} If there is only one optimal history or if the tree has not been reconciled, the drop down menu will be grayed out. \textbf{To undo the reconciliation}: \begin{itemize} \item Click the "\textbf{unreconcile}" button. The previous reconciliation will be undone. This option will be grayed out if the gene tree was not reconciled. \end{itemize} \textbf{To display a pruned species tree}: \begin{enumerate} \item Click the "\textbf{Show pruned species tree}" button. A dialog box appears. \item Enter a title in the text field and click "\textbf{OK}." \end{enumerate} This option will be grayed out if the gene tree was not reconciled. \textbf{To show time bounds and information on losses}: \begin{itemize} \item Click the "\textbf{Show Duplication bounds}" button. A new window will appear. \begin{quote} The D/L Score of the reconciled tree appears at the top of the window. Duplication bounds are described in the three columns below the cost. The left column gives the internal node in the gene tree where the duplication occurred. The center column and right column give lower and upper bounds on the time of duplication, expressed as node names in the pruned species tree. The total number of duplications appears below this table. Conditional duplication bounds are described in the three columns below duplication bounds. The left column gives the internal node in the gene tree where the conditional duplication occurred. The center and right columns provide the lower and upper bounds, respectively, in which the event (duplication or deep coalescence) may have occurred. The total number of condition duplications is listed below this table. Information on losses will appear in two columns below (conditional) duplication bounds. The left column lists all the nodes in the ! species tree. The right column gives the number of losses that appeared in that species. A combined polytomy loss is assigned to the corresponding polytomy, rather than the individual species in which the losses occurred. To display internal node names in the tree panel, "Display Internal Node Names" and "Display Internal Node Species Names" must be turned on in the Display Options menu (\seelink{Display Options}) for both the gene and species tree. \end{quote} \end{itemize} This option will be grayed out if the gene tree was not reconciled. \textbf{To not display the species names in polytomy losses}: \begin{enumerate} \item Go to the Display Options menu. \item Click in the box next to "Use Species Names in Polytomy Losses." \begin{quote} This causes polytomy losses to be display as the number of children of the polytomy lost over the size of the polytomy with the name of the polytomy in which losses occurred. \end{quote} \end{enumerate} \begin{figure}[!h] \centering \includegraphics[scale=0.75]{images/image035.jpg} \caption{ The gene tree from Figure 4b without species names shown in the polytomy losses. \label{fig13}} \end{figure} \chapter{Rooting Mode} \label{Rooting Mode} In Rooting mode, the D/L Score can be used to infer the root of a gene tree. Notung's Rooting Analysis calculates a root score for each edge in the tree, corresponding to the D/L Score of the tree if rooted on that edge. When the Rooting Analysis is complete, Notung highlights edges with low cost root scores. Edges with the minimum score are highlighted in red (\figlink{fig15}). Notung also highlights those edges with scores near the minimum. Edges with scores that are greater than the minimum by at most 5 percent of the difference between the maximum and minimum score are highlighted in pink. If rooting on a polytomy produces the minimum or near-minimum score, the node will be circled and the vertical edge representing that polytomy will be highlighted in the appropriate color (\figlink{fig14}). If highlighted edges are small, they are circled in the appropriate color to help the user find them. Use the Zoom feature (\seelink{Zoom}) to zoom in on these edges. \begin{figure}[!h]s \centering \includegraphics[scale=0.75]{images/image037.jpg} \caption{ Rooting analysis for a non-binary gene tree. The optimal root locations are colored in red. If an edge represented by the polytomy can be selected as an optimal root, the polytomy will be circled and colored in red. \label{fig14}} \end{figure} The Rooting Analysis computes root scores, but does not change the tree. To reroot the tree, click on any edge or polytomy in the tree panel. Notung will root the tree on that edge/polytomy, and recalculate the reconciliation. The D/L Score of the new, rooted tree is displayed in the bottom-left corner of the screen. Rooting mode can also be used to root a tree manually by clicking on any edge at any time, even if the Rooting Analysis has not been performed. \textit{NOTE}: If the tree has not been reconciled before running a Rooting Analysis, Notung will reconcile it automatically. You will be asked to select a species tree for reconciliation (\seelink{Reconciliation Mode}). \textbf{To find optimal root edges}: \begin{enumerate} \item Click the \textbf{Rooting} tab to enter Rooting mode. \item Click "\textbf{Run Rooting Analysis}." \end{enumerate} \begin{figure}[!h] \centering \includegraphics[scale=0.75]{images/image039.jpg} \caption{ (Top.) The gene tree from Figure 11 after completing the Rooting Analysis. (Bottom.) After selecting an edge/polytomy in Rooting mode, Notung reconfigures the tree with that edge/polytomy as the root. \label{fig15}} \end{figure} \textbf{To show/hide Rooting Analysis results}: \\ The following options take effect after clicking "Run Rooting Analysis." \begin{itemize} \item Click the appropriate checkbox in the \textbf{Rooting} task panel. \begin{description} \item[$\surd$ Color good roots (default: ON)] When the "color good roots" box is checked, the low-scoring root edges in the tree are colored (red for the minimum score, pink for scores within 5 percent of the minimum). To remove the highlighting, uncheck the box. \item[$\surd$ Highlight polytomies (default: OFF)] When the "highlight polytomies" box is checked, vertical edges representing polytomies in the gene tree, if any exist, are highlighted and circled in cyan. \item[$\surd$ Circle small edges (default: ON)] When the "circle small edges" box is checked, circles appear around small highlighted edges in the tree, if any exist, making it easier to locate them in large trees. To remove the circles, uncheck the box. \item[$\surd$ Write root score (default: OFF)] When the "write root score" box is checked, the associated D/L Score appears next to each edge and polytomy in the tree. Rooting scores are shown in pink to distinguish them from edge weights, which are given in green. \end{description} \end{itemize} \textbf{To reroot the tree}: \begin{itemize} \item Click on any edge or polytomy of the tree in the tree panel. \end{itemize} \chapter{Rearrange Mode} \label{Rearrange Mode} Notung can rearrange weakly-supported areas of a gene tree to produce alternate event histories with minimum D/L Score. In Notung, a weakly-supported area is a \textbf{Connected Component of Weak Edges (CCW)}, defined to be a maximal set of adjacent edges with weights below the user-defined Edge Weight Threshold. When weakly-supported areas are rearranged, the structure of strongly-supported areas - with edges above the Edge Weight Threshold - stays intact. Selecting the "Highlight weak edges" checkbox will highlight in yellow all weak edges in the tree, allowing the user to see which edges will be considered for rearrangement (\figlink{fig16}). This option is only available in rearrange mode. Notung's rearrangement function requires that the gene tree include edge weights that assess how well each edge is supported by sequence data. Notung considers any edge without a weight to be a weak edge. If Notung's rearrangement function is applied to a tree with no edge weights present, it will consider all edges to be weak, and find all trees that are optimal when only gene duplication and loss are considered (\textit{i.e.} those trees with a minimal Duplication/Loss Score). \section*{Alternate Optimal Hypotheses} 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. Only \textbf{same cost swaps}, interchanges that result in another tree with optimal D/L Score, are considered. All trees in any given subset share the same event history. An event is a duplication or loss. An \textbf{event history} describes a series of events 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 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. When an event history is selected, one tree from the corresponding subset is displayed. The user can perform Same Cost Swaps on that tree to explore the space of all optimal trees corresponding to the current event history. Clicking the "Examine same-cost swaps" button will highlight all \textbf{swappable nodes}, nodes that can be manually swapped without changing the D/L Score. Notung provides visual cues in the tree panel to show where swappable nodes appear in the tree. If there are more than 50 optimal event histories, they can be generated using the Command Line Interface (\seelink{Command Line Options and Batch Processing}). Note that the drop down menu and command line options give distinct optimal event histories, \textbf{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. \textbf{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}[!h] \centering \includegraphics[scale=0.75]{images/image043.jpg} \includegraphics[scale=0.75]{images/image045.jpg} \caption{ (Top.) The gene tree from Figure 11 with weak edges highlighted. (Bottom.) After clicking "Perform Rearrangement," the rearranged tree appears in the tree panel. Weak edges are still highlighted yellow. \label{fig16}} \end{figure} \textbf{To rearrange the gene tree}: \begin{enumerate} \item Click the \textbf{Rearrange} tab to enter 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}(bottom). Note that not all edges in the rearranged tree will have edge weights. 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 "Highlight weak edges" checkbox. \begin{quote} All weak edges in the tree will be highlighted. \end{quote} \end{itemize} \begin{figure}[!h] \centering \includegraphics[scale=0.75]{images/image047.jpg} \includegraphics[scale=0.75]{images/image049.jpg} \caption{ (Top.) 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 tree with the minimal D/L Score. (Bottom.) After the tree is rearranged, weak edges are highlighted in yellow. Notice that any edges that were not present in the original tree have no edge weight and are considered weak. \label{fig17}} \end{figure} \textbf{To view alternate optimal event histories:} \begin{enumerate} \item If more than one optimal event history exists for a rearranged tree, the drop down menu "Select an optimal event history" will be enabled. \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{enumerate} If there is only one optimal history or the tree has not yet been rearranged, the drop down menu will be grayed out. \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, other nodes that can be interchanged with it with are temporarily highlighted with a light orange triangle, as shown in \figlink{fig18}. Swappable nodes that are not currently visible in the tree panel (for instance, if you have zoomed in), are indicated by arrows in the tree panel pointing in the direction of those nodes. \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 (\figlink{fig18}). \item Click a second node to complete the swap (\figlink{fig19}). \end{enumerate} \textit{NOTE}: When a different alternate event history is selected in 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 \textbf{Opening and Saving Trees} on page 16 for more information. \begin{figure}[!h] \centering \includegraphics[scale=0.75]{images/image051.jpg} \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[scale=0.75]{images/image053.jpg} \caption{Clicking on first the blue node and then on the orange node in Figure 19 results in the alternate optimal tree shown here. \label{fig19}} \end{figure} \chapter{Resolve Mode} \label{Resolve Mode} Notung can be used to resolve polytomies in a non-binary gene tree by comparing it with the species tree. The resulting binary tree(s) will have minimal D/L Score. Selecting the "Highlight Polytomies" checkbox will highlight in cyan all vertical edges representing a polytomy in the tree, allowing the user to see which nodes will be resolved. Selecting the "Highlight New Edges" checkbox after resolving will highlight in cyan all those edges in the gene tree that were previously represented by the polytomy (\figlink{fig20}). This option is only available in resolve mode. \section*{Alternate Optimal Hypotheses} There may be more than one tree that (1) has minimal D/L Score and (2) can be represented by the polytomy. 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 share the same event history. An event is a duplication or loss. An event history describes a series of events 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\_mo! use), g4\_mouse). Note that all the trees with the same event history have the same D/L Score. If multiple minimum cost trees are found, Notung presents one representative tree from 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 by interchanging pairs of nodes. We refer to this operation as \textbf{same cost swaps}, because they always result in another tree with the same D/L Score. 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. When an event history is selected, one tree from the corresponding subset is displayed. The user can perform Same Cost Swaps on that tree to explore the space of all optimal trees corresponding to the current event history. Clicking the "Examine same-cost swaps" button will highlight all \textbf{swappable nodes}, nodes that can be manually swapped wit! hout changing the D/L Score. Notung provides visual cues in the tree panel to show where swappable nodes appear in the tree.