\documentclass[fleqn,a4paper]{vch-book}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{makeidx}
    \makeindex
\usepackage{times}
\usepackage{tabularx}
\usepackage{booktabs}
    \setlength{\heavyrulewidth}{0.4pt}
    \setlength{\lightrulewidth}{0.4pt}
    \setlength{\cmidrulewidth}{0.4pt}

% if latex begin
%  \usepackage[dvips]{graphicx}
%  %\usepackage[dvips]{epsfig}
%  \DeclareGraphicsExtensions{.eps,.ps}
% if latex end
% if pdflatex begin
   \usepackage[pdftex]{graphicx}
   %\usepackage[pdftex]{epsfig}
   \usepackage[pdftex,colorlinks=true]{hyperref}
   \DeclareGraphicsExtensions{.pdf}
% if pdflatex end


%    Some definitions useful in producing this sort of documentation:
\chardef\bslash=`\\ % p. 424, TeXbook
%    Normalized (nonbold, nonitalic) tt font, to avoid font
%    substitution warning messages if tt is used inside section
%    headings and other places where odd font combinations might
%    result.
\newcommand{\ntt}{\normalfont\ttfamily}
%    command name
\newcommand{\cn}[1]{{\protect\ntt\bslash#1}}
%    LaTeX package name
\newcommand{\pkg}[1]{{\protect\ntt#1}}
%    File name
\newcommand{\fn}[1]{{\protect\ntt#1}}
%    environment name
\newcommand{\env}[1]{{\protect\ntt#1}}
%    Randbemerkung
\newcommand{\marginlabel}[1]{\mbox{}\marginpar{\raggedleft#1}}
\newcommand{\RB}[1]{\marginpar{\tiny{#1}}}

%    option name
\newcommand{\opt}[1]{{\protect\ntt#1}}
\hfuzz1pc % Don't bother to report overfull boxes if overage is < 1pc
%    Enclose the argument in vert-bar delimiters:
\newcommand{\envert}[1]{\left\lvert#1\right\rvert}
\let\abs=\envert


\newcommand{\bibtex}{\ifx\is@itshape\f@shape{\fontshape{scit}\selectfont
Bib}\else\textsc{Bib}\fi\kern-.1em\TeX}

\newcommand{\Knuth}{Donald E.\ Knuth\index{knuth@{Knuth, Donald E.}}}
\newcommand{\Lamport}{Leslie Lamport\index{lamport@{Lamport, Leslie}}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Own definitions:
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\xxx}{\rule{2em}{1ex}}
\newcommand{\todo}{\rule{2em}{1ex}}
\DeclareMathOperator{\diff}{diff}		% operator (without limits)
\DeclareMathOperator*{\argmax}{argmax}		% operator (with limits)

\newcommand{\mcE}{\mathcal{E}}                  % cal E set
\newcommand{\mcF}{\mathcal{F}}                  % cal F set
\newcommand{\mcL}{\mathcal{L}}                  % cal L set
\newcommand{\mcQ}{\mathcal{Q}}                  % cal Q set
\newcommand{\mcV}{\mathcal{V}}                  % cal V set
\newcommand{\mcS}{\mathcal{S}}                  % cal S set
\newcommand{\mcT}{\mathcal{T}}                  % cal T set
\newcommand{\mbbA}{\mathbb{A}}                  % bf S matr

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\bibliographystyle{plain}
\setcounter{chapter}{3}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\chapter{Phylogeny Reconstruction% 
         \index{Phylogeny Reconstruction}%
         \tocauthor{I. Ebersberger, A. v. Haeseler, H. A. Schmidt}}\label{chap:phylogeny-reconstruction}

\authorafterheading{Ingo Ebersberger$^1$,
                    Arndt von Haeseler$^{2,3,4,5}$,
                    Heiko A. Schmidt$^{2,3,4,5}$}
                    
\affil{$^1$WE Informatik, Universit\"at D\"usseldorf, Germany\\
       $^2$Center for Integrative Bioinformatics Vienna, Austria\\
       $^3$University of Vienna, Austria\\
       $^4$Medical University of Vienna, Austria\\
       $^5$University of Veterinary Medicine Vienna, Austria}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}
\subsection{Tree-thinking in Phylogenetics}
The fundamental axiom in evolutionary biology is the assumption that any two taxa share a
common ancestor at a certain time point in their history. Thus, following the lineages along
which these taxa have evolved backward in time they will eventually coalesce. Considering a
larger set of taxa, subsequent coalescent events result in an ever decreasing number of
predecessors until only two lineages remain. The ancient taxon in which these lineages
eventually merge represents then the most recent ancestor common to all taxa in the
orginal data set. The correspondence to a tree is apparent, and it is therefore of little
surprise that trees play the key role in phylogenetic research. This is already manifested
in the phylogeneticist's vocabulary (figure \ref{TREES}). Contemporary taxa are dubbed
'leaves', leaves are connected via 'external branches' to internal nodes (their common ancestors),
and internal nodes themselves are connected via 'internal branches'. Nodes that give rise to
two descendants are termed 'bifurcation', nodes with a larger number of descendants are
referred to as 'multifurcations'\footnote{Biologists usually judge it as unlikely that three
or more lineages emerged at precisely the same time from a shared ancestor. Thus, we will
concentrate on bifurcating trees.}. Eventually, if the direction of the evolutionary process
is known the ancestor of all leaves in the tree is identified. To stay in the picture, this
node is termed the 'root'. If directional information is not available, the relationships of
the taxa is represented in an 'unrooted tree'. However, in this case the temporal succession of
ancestors remains undetermined.
\begin{figure}
	\fbox{\includegraphics[width=.48\textwidth]{images/tree-notation-rooted}\hfill
		\includegraphics[width=.48\textwidth]{images/tree-notation-unrooted}}
\caption{Phylogenetic relationships among a set of seven taxa represented by a rooted (left) and an unrooted (right) tree.}
\label{TREES}
\end{figure}
\subsubsection{Reconstructing a tree from its leaves}
The reconstruction of the phylogenetic relationships for a set of taxa and their representation
by a tree can be separated into two sub-problems. First, what is the order individual taxa split
from their shared ancestors, i.e., what is the topology of the tree? Second, what is the
evolutionary time that has passed since any two taxa last shared a common ancestor, i.e., how
long are the corresponding branches of the tree? In most cases no hard evidence -- such as a
comprehensive fossil record -- exists to directly reconstruct the evolutionary steps transforming
one ancestral taxon into its descendants. Rather we get hold only of the endpoints of this process
and are more or less ignorant about anything that has happened in the past. Thus, we are facing
the problem to reconstruct the phylogenetic tree just by looking at its leaves.
\subsection{Phylogenetic relationships of taxa and their characters}
Although one is typically interested in the relationships of the taxa, the reconstruction procedure
is usually not based on the taxon as a whole. For practical reasons one vicariously concentrates
on individual characteristics of these taxa, usually either morphological or molecular features.
We will refer to such representative characteristics as 'characters' and to their peculiar
expression in the individual taxa as the 'character state'.

To collect the 'raw data' for phylogenetic analyses, the variety of states for a particular
character in a set of taxa has to be assessed first. Next, the possible transformations of
the character states during evolution has to be reconstructed, which can then be used for
phylogenetic inferences. Irrespective of what type of character has been chosen, two general
approaches can be followed to trace the phylogenetic signal in the data. One can identify those
(evolutionary novel) character states that are shared among a subset of the taxa \cite{hennig1966}.
Such a congruency is interpreted as a result of shared descent. Based on the pattern and
extent of congruent character states the degrees of relationships among the taxa can then be
inferred. Alternatively, the extent of evolutionary change for the particular character between
any pair of taxa can be assessed. From the resulting pairwise evolutionary distances again a
phylogenetic tree can be reconstructed. We will outline both approaches in greater detail below.
Eventually, the evolutionary history of the particular character is extrapolated to the
taxon level.

Inherent to any character based strategy for phylogeny reconstruction is the assumption that
comparisons are performed only between homologous characters, that is characters related by
descent. Although the assignment of homology constitutes one of the major issues in
evolutionary studies \cite{hennig1966,patterson1988,schuh2000} we will take for granted that
this postulation is met.
\subsubsection{The problem of character inconsistencies}\label{sec:character-inconsistency}
With phylogenetic analyses coming of age, tree reconstruction is frequently based on more
than only a single character. This adds the advantage that different characters can complement
each other by adding resolution to different parts of the tree. However, the reverse effect
can occur as well: Trees reconstructed from different characters disagree. Under the assumption
that incompatible groupings of taxa are significantly supported by the respective data, two
alternative explanations are possible. First, the incompatible groupings are based on a
misinterpretation of the data. For example, taxa can share the same character state not due to
a shared ancestry, but rather the particular state arose at least twice independently during
evolution. Phylogeny reconstruction methods that include a modeling of the evolutionary process
(see below) usually account for this problem. However, if such parallel, convergent or back
mutations remain unrecognized -- or are neglected -- an erroneous tree reconstruction is inevitable.
In the second explanation, the evolution of the character states is correctly reconstructed.
Such genuine discrepancies between the inferred trees can have multiple causes. Among the most
frequently stated are processes like the random sorting of ancestral polymorphisms during
successive speciation events, e.g. 
\cite{satta2000}, and horizontal gene transfer \cite{delwiche1996,doolittle1999a,kurland2003}.
If one is suspicious that either of these scenarios could apply, several independently evolving
characters should be analyzed. The most frequently observed tree is then usually the tree
reflecting the evolutionary relationships of the taxa as a whole. Alternatively, if it deems
appropriate to visualize such discrepant phylogenetic signals in the data, a network rather
than a tree can be chosen to represent the phylogeny of the taxa (see below).
\subsubsection{Finding the appropriate character set}
In theory, phylogenetic relationships can be reconstructed from any set of homologous characters
subject to evolutionary change. Depending on the scope of a study and the collection of taxa,
however, certain types of characters might be more suitable than others. Changes in shape, or
morphology in general, are the most conspicuous effect of evolution. It is therefore that the
field of phylogeny reconstruction was dominated for a long time by the analysis of morphological
characters. However, with the expansion of molecular biology the focus has shifted considerably.
Initially, immunological or electrophoretic comparisons of proteins \cite{king1975}, presence
or absence of genomic features such as restriction enzyme recognition sites \cite{ferris1981},
or DNA-DNA hybridization \cite{sheldon1987,felsenstein1987} were used to measure the extent of
character change on the molecular level. During the years the presence and absence or linear
order of regulatory elements and genes (see also chapter 8) and recently, even expression
data have been employed \cite{khaitovich2005} for phylogenetic inference. However, the most
dominant role is taken by the direct comparison of biological sequences.
Sequences change in the course of time, and any two sequences derived from a common
ancestor will eventually diverge. Pattern and extent of divergence between two sequences is
then used to reconstruct their evolutionary history. Initially -- due to experimental
constraints -- the comparison of protein sequences was prevalent. Nowadays, analyses rely almost
entirely on DNA sequences and even those studies comparing amino acid sequences usually derive
these from the corresponding DNA sequences. The advantages of DNA sequence data are apparent.
DNA sequences can be obtained with considerable ease from any taxon and even the comparison of
entire genomes is now far from being an exotic venture. Allowing for some simplifications,
each nucleotide position in the DNA sequence can be regarded as an independently evolving
character and the number of possible states is strictly limited to the four bases, Adenine
(A), Guanine (G), Cytosine (C) and Thymine (T). Eventually, different DNA sequences in a genome
can evolve with different rates. This allows to easily adapt the data set to the evolutionary
time scale for which phylogenetic resolution is required.

%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Modeling DNA sequence evolution}
The substitution of nucleotides in a DNA sequence, i.e., the replacement of one nucleotide by
a different one, is usually considered a random event. As a consequence, an important prerequisite
for the reconstruction of phylogenetic relationships among species is the prior specification of a
{\em model of substitution} which provides a statistical description of this stochastic
process \cite{lio1998}. Once a mathematical model of substitution is assumed, then straightforward
procedures exist to infer genetic relationships from the data.

To count the number of substitutions $X(t)$ that occurred during the time $t$ the so-called
Poisson process is employed: at any point in time an event can take place. That is to say,
per unit of time a substitution occurs with rate $\mu$. Let $P_i(t)$ denote the probability
that exactly $i$ substitutions occurred during the time $t$. Then the number of substitutions
up to time $t$ is Poisson-distributed with parameter $\mu t$:
\begin{equation}
P_i(t)=[(\mu t)^i\exp(-\mu t)]/i!
\end{equation}
On average, $\mu t$ substitutions with variance $\mu t$ are expected. Note that the parameters
$\mu$ (nucleotide substitutions per site per unit time) and $t$ (the time) are confounded. That
is, they cannot be estimated separately but only through their product $\mu t$ (number of
substitutions per site up to time $t$).

The nucleotide substitution process of DNA sequences described by the Poisson process can be
generalized to a so-called Markov process that uses a rate matrix (typically called $Q$ with
elements $Q_{ij}$), which specifies the relative rates of change for each nucleotide. The most
general form of the Q-matrix is shown in figure \ref{QMAT}. Rows follow the order A, C, G and T
so that, for example, the second term of the first row is the instantaneous rate of change from
base A to base C. This rate is given by the frequency of base C ($\pi_C$) times a relative rate
parameter, describing (in this case) how often the substitution A to C occurs during evolution
with respect to all other possible substitutions. Thus, each non-diagonal entry in the matrix
represents the flow from nucleotide $i$ to nucleotide $j$, while the diagonal elements are
chosen to make the sum of each row equal to zero. They represent the total flow that leaves
nucleotide $i$. Accordingly, we can write the total number of substitutions per unit time
(i.e., the total substitution rate $\mu$) as
\begin{equation}
\mu=-\sum_{i=1}^4Q_{ii}\pi_i.
\end{equation}
Models like the one summarized in figure \ref{QMAT} belong to the general class of time-homogenous
time-continuous Markov models. When applied to modeling nucleotide substitutions,
they share the following set of assumptions:
\begin{itemize}
\item{The rate of change from $i$ to $j$ at any nucleotide position in a sequence is independent
of the nucleotide that occupied this position prior to $i$ (Markov property).}
\item{Substitution rates do not change over time (homogeneity).}
\item{The probability for a substitution event in the time interval $[t,\delta t]$ is drawn from
a continuous distribution (time continuity).}
\end{itemize}
Once the evolutionary model -- and thus the Q-matrix -- is specified, it is possible to calculate the
probabilities $P(t)$ of change from one nucleotide to any other during evolutionary time $t$ by
computing the matrix exponential:
\begin{equation}
P(t)=\exp(Qt)
\end{equation}
This equation resembles the equation under the Poisson distribution with the sole difference that
the mean substitution rate $\mu$ in the exponential is replaced by the Q-matrix, specifying the
relative rates for each possible $i\rightarrow j$ substitution according to the evolutionary model
represented by the Q-matrix.\\
\subsubsection{Nucleotide substitution models}

From the instantaneous substitution rate matrix $Q$ various sub-models can be derived. Among these,
the so-called stationary time-reversible models are the ones most commonly used. These models introduce the
constraint that for any two nucleotides $i$ and $j$ the rate of change from $i$ to $j$ is the same
as from $j$ to $i$ (thus, $a=g, b=h, c=j, d=i, e=l, f=l$ in figure \ref{QMAT}). Under these conditions
the $\pi_N$ correspond to the stationary frequencies of the four nucleotides, respectively (i.e., $\pi\cdot Q=0$). 
If all of the remaining eight free parameters of a reversible Q-matrix are specified, the general
time reversible (GTR, \cite{lanave1984}) is derived. At the other extreme it can be assumed that the equilibrium
frequencies of the four nucleotides are 0.25 each, and that any nucleotide has the same rate to be
replaced by any other. These assumptions correspond to a Q-matrix with $\pi_A=\pi_C=\pi_G=\pi_T=1/4$,
and $a=b=c=d=e=f=1$ reflecting the simplest nucleotide substitution model, namely the Jukes and
Cantor (JC69, \cite{jukes1969}) model. An overview of the hierarchy of the most common substitution
models is shown in figure \ref{fig:model-hierarchy}.

%%%%
\begin{figure}
\[ Q = \left( \begin{array}{cccc}
-(a\pi_C+b\pi_G+c\pi_T) & a\pi_C                 &   b\pi_G              &c\pi_T                \\
g\pi_A                  & -(g\pi_A+d\pi_G+e\pi_T)&   d\pi_G              &e\pi_T                \\
h\pi_A                  & i\pi_C                 &-(h\pi_A+i\pi_C+f\pi_T)&f\pi_T                \\
j\pi_A                  & k\pi_C                 &l\pi_G                 &-(j\pi_A+k\pi_C+l\pi_G)\\
\end{array}
\right)
\]
\caption{Instantaneous rate matrix $Q$. Each entry in the matrix represents the instantaneous
substitution rate from nucleotide $i$ to nucleotide $j$ (rows and columns follow the order A, C, G,
T). $a$ to $l$ are rate parameters describing the relative rate one nucleotide is substituted by
any other nucleotide. $\pi_A, \pi_C, \pi_G, \pi_T$ correspond to the nucleotide frequencies.
Diagonal elements are chosen such that each row sums up to zero.}\label{QMAT}
\end{figure}
\begin{figure}
\fbox{\includegraphics[width=.8\textwidth]{images/modelrel-l}}
\caption{A hierarchy of the most commonly used nucleotide substitution models. JC69, model by
Jukes and Cantor (1969) \cite{jukes1969}; F81 Felsenstein (1981) \cite{felsenstein1981}; K2P,
Kimura two-parameter model (1980) \cite{kimura1980}; HKY85, model by Hasegawa, Kishino and Yano
(1985) \cite{hasegawa1985}; TN93, Tamura-Nei model (1993) \cite{tamura1993}; GTR, general time
reversible model \cite{lanave1984}. Many more models are possible and an an extensive overview
is given in \cite{huelsenbeck2004}.}\label{fig:model-hierarchy} 
\end{figure}
%%%%%%%%%%%
\subsection{Modeling rate heterogeneity}
The nucleotide substitution models described so far, implicitly assume that the rate of nucleotide
substitution is the same for any position in the DNA sequence. However, it is well-known that this
is a due oversimplification. For example, substitutions occur at an about 10 times higher frequency
at C and G nucleotides when the C is followed by a G along the sequence \cite{holliday1993}.
Similarly, selective constraints maintaining functional DNA sequences result in varying substitution
rates along a DNA sequence. To account for such site-dependent rate variations, a plausible model
for the distribution of rates over sites is required. Most commonly, a $\Gamma$-distribution with
expectation $1$ and variance $1/\alpha$ is used \cite{gu1995}. By adjusting the shape parameter
$\alpha$, the $\Gamma$-distribution allows varying degrees of rate heterogeneity. For $\alpha > 1$,
the distribution is bell-shaped and models weak rate heterogeneity among sites. For $\alpha < 1$,
the $\Gamma$-distribution takes on a characteristic L-shape, which describes strong rate
heterogeneity, i.e., some sites have very high substitution rates, but most other sites are
practically invariable.
%
\subsection{Codon models}
Heterogeneous substitution rates become a particular issue for DNA that codes for proteins. Amino
acid sites in a protein sequence are expected to be under different selective constraints, depending
on their relevance for the protein function. Accordingly, nucleotide substitutions causing the
encoded amino acid to change (replacement substitutions) will have fixation probabilities that depend
on the selective constraint imposed on the encoded amino acid. In contrast, silent substitutions -- that
is a change in the DNA has no effect on the protein -- are invisible to selective forces acting on the
protein sequence. As a result, the nonsynonymous/synonymous substitution rate ratio ($\omega=d_N/d_S$)
will vary among sites in a DNA sequence, with $\omega=1$ indicating no selection, $\omega<1$ purifying
selection by removing replacement mutations, and $\omega>1$ diversifying positive selection/adaptive
evolution. Codon models have been specifically designed to model the evolution of protein coding DNA
sequences \cite{goldman1994}. An example is shown in figure \ref{CMOD} based on a extension of the
HKY85 model \cite{hasegawa1985} (figure \ref{fig:model-hierarchy}). Note, that in contrast to the
conventional substitution models, codon models consider the replacement of one nucleotide triplet
(codon) by another. Thus, we obtain $4^3-3$ possible character states at a site, the codon, where
the three stop codons are not taken into account. Obviously, the assignment of a distinct $\omega$ to
each codon position would lead to a vast over-parameterization of the model. Therefore, distinct
$\omega$-classes or statistical distributions -- both discrete and continuous -- are used to account
for heterogeneous $\omega$-values among sites \cite{yang1998a, yang2002, massingham2005}.

%%
\begin{figure}
\[ 
   q_{ij} = \left\{ \begin{array}{ll}
	0                       &\mbox{if $i$ and $j$ differ at two or three nt positions,}\\
	\pi_j                   &\mbox{if $i$ and $j$ differ by one synonymous transversion,}\\
	\kappa\pi_j             &\mbox{if $i$ and $j$ differ by one synonymous transition,}\\
	\omega^{(h)}\pi_j       &\mbox{if $i$ and $j$ differ by one non-synonymous transversion}\\
	\omega^{(h)}\kappa\pi_j &\mbox{if $i$ and $j$ differ by one non-synonymous transition.}\\
   \end{array} \right.
\]
\caption{Instantaneous rate that codon $i$ at site $h$ is replaced by codon $j$. $\pi_j$ represents the marginal frequency of codon $j$, $\kappa$ denotes the transition/transversion rate ratio, and $\omega^{(h)}$ the nonsynonymous/synonymous substitution rate ratio at site $h$.}
\label{CMOD}
\end{figure}
%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Tracing the evolutionary signal}
Given a set of homologous DNA sequence whose phylogeny is known, inferences can be made about the
evolutionary forces molding the contemporary DNA sequences from their shared ancestral sequence.
Conversely, with a conception or a model at hand of how DNA sequences evolve one can aim to reconstruct
the phylogenetic tree based on the DNA sequences. In either case, however, a meaningful sequence
alignment is required. Thus, the sequences need to be written such that homologous nucleotides in different
sequences form a column. To account for the insertion and deletion of nucleotides during evolution,
gaps are introduced to achieve this positional homology. We will not dwell on further methodological
details and take it for granted that an alignment is available. Based on this alignment several
criteria exist to find the tree that reflects the evolutionary relationships of the data. We will
explain four principles.
\subsection{The parsimony principle of evolution}
Parsimony methods share as an optimality criterion that among various alternative hypotheses the
one, which requires the minimal number of assumptions should be chosen. In the context of DNA sequence
evolution this results in a model of Maximum Parsimony proposing that contemporary DNA sequences
evolved from their shared ancestor via a minimal number of nucleotide substitutions. Consequently,
trees will be chosen which explain the sequence variability in an alignment with the least number
of substitutions. 
\paragraph{Generalized Parsimony}
To date a vast number of modifications of the initial criterion of maximum parsimony exist
\cite{kluge1969,fitch1971,farris1977,farris1996}. Instead of referring to each and every modification
separately, we would like to give the generalized idea of parsimony \cite{sankoff1975,sankoff1983}
from which the individual modifications can be easily derived. In a mathematical terminology,
one aims to identify those trees in the space of all possible trees which minimize the following
equation:
\begin{equation}
L(\tau)=\sum_{k=1}^B\sum_{j=1}^L\omega_j\times \diff(x_{k'j},x_{k''j})
\end{equation}
where $L(\tau)$ is the length of the tree $\tau$ , $B$ is the total number of branches in the tree,
$L$ is the number of characters analyzed (alignment length), $k'$ and $k''$ are two nodes on branch
$k$ having the character states $x_{k'j}$ and $x_{k''j}$. These can be either the observed character
states present in the data matrix or, in the case of internal nodes, the optimal character state
assignments. Eventually, $\diff(x,y)$ is the cost for the transformation from character state $x$ to
state $y$, and $\omega_{j}$ allows to assign a weight to each character in the tree reconstruction.
The change costs can be summarized in a $m\times m$ matrix $S$, $m$ being the number of different
character states. The entry $S_{ij}$ then represents the increase in tree length associated with a
change from character state $x$ to $y$. Depending on the choice of the cost matrix $S$ and of the
weight parameter $\omega_j$ different extents of prior information about the evolutionary process
can be introduced into the parsimony model. An example for $S$-matrices is shown in figure \ref{COSTMAT}. 
\begin{figure}
\hfill
\textbf{A} =\quad
$\begin{array}{ccccc}
     & A & C  & G & T \\ \hline
  A  & - & 1  & 1 & 1 \\
  C  & 1 & -  & 1 & 1 \\
  G  & 1 & 1  & - & 1 \\
  T  & 1 & 1  & 1 & - \\
\end{array}
$
%\]
%\[
\hfill
\textbf{B} =\quad
$\begin{array}{ccccc}
     & A & C  & G & T \\ \hline
  A  & - & 5  & 1 & 5 \\
  C  & 5 & -  & 5 & 1 \\
  G  & 1 & 5  & - & 5 \\
  T  & 5 & 1  & 5 & - \\
\end{array}
\hfill
$
\caption{Cost matrices for generalized parsimony. In matrix \textbf{A} substitutions between all
four nucleotides invoke the same cost. Matrix \textbf{B} represents a slightly more sophisticated
model. More weight is put on transversions than on transitions.}\label{COSTMAT}
\end{figure}
\paragraph{Multiple/parallel hits}
Parsimony principles rely on the assumption that a group of related taxa share a certain character
by descent. However, this approximates the true evolutionary events only then in a realistic way
when the overall amount of sequence changes is low. Thus, multiple changes of the same character in
the same taxon or parallel independent changes of the same character in different taxa -- both of which
are incompatible with the parsimony principle -- are sufficiently infrequent not to be an issue.
However, when considerably diverged sequences are used for tree reconstruction, or marked
substitution rate heterogeneity among sites exists, multiple/parallel hits can cause severe problems
in both assessing the correct number of character changes along the phylogenetic tree and in
inferring the correct tree topology.
%
\subsection{Distance based methods}
In contrast to parsimony methods with their biologically motivated approach to tree reconstruction,
other methods chose a mathematical access to accomplish this task. Distance based methods
\cite{felsenstein1984} utilize among others the principle of the least squares, which we will concentrate
on. Initially, a distance matrix $D$ is calculated for the data set from all possible pairwise
sequence comparisons. Entry $D_{ij}$ of this matrix represents then the distance between sequence
$i$ and sequence $j$. In a simple approach $D_{ij}$ is computed as the edit distance
(Levenstein distance), that is the minimum number of substitutions required to transform sequence
$i$ into $j$. However, superimposed changes occurring at a single sequence position have no effect
on the edit distance. This requires the use of an appropriate model of sequence evolution to correct
the observed distance for the expected number of 'unseen' changes. Once the distance matrix is
computed, the tree is inferred that minimizes the difference between the evolutionary distances
$d_{ij}$ of any sequence pair $ij$ in the tree and the corresponding entries in $D$. The best tree
($\tau_{LS}$) under this criterion minimizes the following equation:
\begin{equation}
R(\tau) = \sum_{i<j}(d_{ij} - D_{ij})^2\label{EQTLSTREE}
\end{equation}
where $d_{ij}$ is the sum of the branch lengths on the unique path connecting sequences $i$ and
$j$. The branch lengths are the parameters that can be adjusted for any tree to minimize equation
\ref{EQTLSTREE}.
\paragraph{Additive distances}
Under the hypothesis that biological sequences indeed evolve in a tree-like manner, evolutionary
distances have the convenient property of tree additivity. That is, the evolutionary distance
between any two sequences is equal to the total length of the branches connecting the two sequences
in the phylogenetic tree. Under these conditions the four-point metric condition \cite{buneman1971}
is satisfied for any four taxa A, B, C, and D such that
\begin{equation}
d_{AB}+d_{CD}\leq \max(d_{AC}+d_{BD},d_{AD}+d_{BC})\label{eqt:fourpoint}
\end{equation}
In reality, however, the criterion of exact tree additivity is not met although the sequences
evolved tree like. This can occur when the substitution model used for distance correction is
inappropriate. Alternatively, stochastic error in the sampling of phylogenetically informative
positions can result in a deviation from perfect tree additivity, even when the underlying data has
evolved exactly according to the model used for distance correction. Thus, some considerations must
be given to the choice of the substitution model and to the extent of information in the data.
However, it is reassuring that a distance based phylogenetic tree reconstruction allows for a
certain degree of deviation from additivity and still obtains the true evolutionary relationships
\cite{bandelt1986}.
\paragraph{Ultrametric distances}
The concept of additive distances can be extended to the more constrained case of ultrametric
distances. For any set of three taxa A, B, and C this can be summarized in the following three-point
condition:
\begin{equation}
d_{AC}\leq \max(d_{AB}, d_{BC}).
\end{equation}
That is, for any sequence triple two of the three genetic distances are equal and at least as
large as the third distance. From this it can be easily deduced that any two taxa in the tree
are equally distant from their shared ancestral node. As a consequence, by finding that node in
the tree which has the same distance to all terminal taxa, the root of the tree can be identified.
For the inference of ultrametric distances the same limitations apply as mentioned for the inference
of additive distances. Thus, it is frequently more convenient to refer to alternative concepts to
determine the root of a tree (see below).
%
\subsection{The criterion of likelihood}
The third method of tree reconstruction is based on the principle of Maximum Likelihood (ML)
\cite{fisher1912} which was made popular in the field by Felsenstein in 1981 \cite{felsenstein1981}.
The general idea of ML is as simple as it is appealing: For a given model $M$ and the corresponding
parameter vector $\theta$ the probability or likelihood of observing data $D$ can be calculated.
These parameter vectors are chosen that maximize the likelihood of observing the data. For
the specific problem of inferring a phylogenetic tree from biological sequence data, a further
parameter $\tau$ representing the tree topology is introduced such that
\begin{equation}
\tau_{ML} = \argmax\limits_{(\tau, \theta)} P(D|\tau, M, \theta). 
\end{equation}
Note the subtle but far reaching difference to the principle of Maximum Parsimony. The general
concept of sequence evolution inherent to Maximum Parsimony, namely that one sequence is
transformed into another via the least number of changes, is replaced by an explicit model of
sequence evolution, which specifies the rates of changing one nucleotide into another. From this
the most significant advantage of Maximum Likelihood becomes apparent: It allows the incorporation
of any model of biological sequence evolution into the tree reconstruction process. By that, it
opens access to the full use of statistical approaches to compare alternative phylogenetic
hypotheses, as well as to test fit and robustness of individual models of sequence evolution.
A further advantage compared to the previous two approaches is the possibility to make full
use of the sequence information.
\subsection{Calculating the likelihood of a tree}
 We have described above how to calculate the probability of observing a difference at a given
site in two sequences. We now extend this to the question of how to compute the probability of
finding a certain nucleotide pattern ($D_s$) in a column $s$ in a set of $n$ aligned DNA
sequences. This probability depends on the model of DNA sequence evolution and on the tree
relating the $n$ nucleotides in the alignment column: $P(D_s|\tau, M, \theta)$. An efficient
way to compute this probability is described in \cite{felsenstein1981}. Superimposing the
constraints that all positions in an alignment of length $L$ evolve according to the same
evolutionary model but independently from each other, the probability of the alignment given
a tree and a model is
 \begin{equation}
 P(D|\tau, M,\theta) = \prod_{s=1}^LP(D_s|\tau, M, \theta).
 \end{equation}
 To avoid underflow errors during the calculation (probabilities are always $\leq$1) the
likelihood of the data is usually calculated in log-scale, such that
 \begin{equation}
 \log[P(D|\tau, M,\theta)] = \sum_{s=1}^L \log[P(D_s|\tau, M, \theta)].
 \label{MLEQUAT}
 \end{equation}
 This equation allows us to compute the likelihood of an alignment, if we knew the evolutionary
model, the topology of the tree connecting the sequences in the alignment as well as its branch
lengths. In reality, however, we face the reverse situation. Starting from a given alignment,
we aim to infer the underlying phylogenetic tree together with its branch lengths. In order to
do so we regard these parameters as variables. Once we have decided for an evolutionary model
and have specified its parameter values, we can adjust the tree topology and the branch lengths
such that equation \ref{MLEQUAT} is maximized. While straightforward and efficient ways exist to
obtain Maximum Likelihood branch lengths for a specific tree topology, it is both a computationally
as well as intellectually demanding problem to obtain an optimal tree topology. Section \ref{opttree}
deals in detail with this problem.
%
\subsection{Rooting trees / Molecular clock}
So far we have introduced various methods to infer the relationships of sequences (or taxa) to
each other. Unfortunately, most of the methods described above lack an inherent criterion to assign
directionality to the evolutionary process. As a consequence they are unable to identify the
root of a phylogenetic tree. To arrive at a rooted tree, it is required (and possible) to add
supplementary information into the tree reconstruction procedure. 
\paragraph{Outgroup rooting}
Among the various methods to root a tree, it is most intuitive to divide the set of
taxa into two subgroups: a monophyletic ingroup and an outgroup, whose more distant relationship
to any member of the ingroup is either known or at least reasonable to assume. It is then
straightforward to conclude that the node where the outgroup joins the ingroup taxa represents
the root of the tree \cite{smith1994,nixon1993}. Although of tempting simplicity, this approach
requires some considerations. Outgroup taxa should be, despite their clear position outside the
ingroup, as closely related to the ingroup taxa as possible. This will increase the probability
to reliably identify homologous sequence positions using standard alignment procedures. Furthermore,
it minimizes the risk that outgroup taxa are represented by little more than randomized, fully
saturated sequences with respect to the ingroup \cite{wheeler1990,maddison1992a}. In such cases
it would be impossible to extract the phylogenetic signal from the sequence comparisons, and
thus the root placement is meaningless \cite{sanderson2002a}. In addition to these more general
requirements, some additional guidelines exist to root phylogenetic trees by the use of an
outgroup. First, where applicable more than one taxon should be included into the outgroup
\cite{maddison1984}. Furthermore, different outgroup taxa should be used to check whether the
root placement changes with the chosen outgroup \cite{tarrio2001}. Finally, hyper-variable
sites in the sequences should be identified and -- where applicable -- excluded from the analysis
since they tend to blur the phylogenetic signal in distantly related sequences \cite{hendy1989}.
\paragraph{Midpoint rooting and Molecular clock}
As we have seen, the choice of a meaningful outgroup to root a phylogenetic tree can extend to
a considerable problem. This will be the more the case when groups are analyzed whose
phylogenetic relationships are largely unclear. In such cases additional assumptions about
the evolutionary process are imposed that help to root the tree.

Given that per unit of time any lineage accumulates the same amount of sequence changes
(molecular clock) the point in the tree that is equally distant from all terminal taxa will
be assigned as the root (see 'ultrametric condition'). In reality, however, the assumption
of a molecular clock is frequently violated. If this is neglected rooting under the clock
assumption will tend to place the root on that part of the tree that is evolving with a
higher evolutionary rate. 
Midpoint rooting slightly relaxes the constraints imposed by the molecular clock assumption.
It places the root on the midpoint of the path connecting the two most distantly related
taxa in the phylogenetic tree. Compared to the molecular clock scenario this retains only
the postulation that the evolutionary rate has to be the same on the two most divergent
lineages in the data set. However, when this criterion is met midpoint rooting identifies
the localization of the root correctly \cite{swofford1996}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Finding the optimal tree}\label{opttree}
In the previous parts we have outlined the principles to evaluate a phylogenetic tree under
a given evolutionary model. Unfortunately, people are usually only moderately interested in
a statement how likely a particular tree reflects the evolutionary relationships among a
set of taxa. Rather, they require the tree that \textbf{most} likely reflects these
relationships. We can differentiate between two general concepts to search the tree space
comprised by all possible tree topologies for the desired optimal tree: i) exact searches
which guarantee the identification of the optimal tree, and ii) the computationally less
demanding heuristic searches which, however, not necessarily obtain the globally optimal tree.
\subsection{Exact searches}
In the conceptually simplest approach, the exhaustive search, each and every possible bifurcating
tree in the tree space is evaluated under the selected optimality criterion. The identification
of the optimal trees is then straightforward and the computationally challenge limits to an
algorithm that assures a walk through the entire tree space. To accomplish this, one starts
with the (unique) unrooted tree that connects three randomly chosen taxa from the data set.
Subsequently, the remaining taxa are added in a step-wise fashion such that the $i$th taxon
is added separately to each of the $2i-5$ branches of every possible tree for the $i-1$
previous taxa. Obviously, the addition of every taxon increases the number of possible trees
by the number of branches the new taxon can be connected to \cite{felsenstein1978}. Thus,
the total number of unrooted trees for a set of $n$ taxa calculates as:
\begin{equation}
	B(n) = \prod_{k=3}^n (2k -5)  = \frac{(2n-5)!}{2^{n-3}(n-3)!}.
\end{equation}
The limitations of the exhaustive search are perspicuous. Already a compilation of 20 taxa,
a data set that is nowadays easily exceeded, requires the evaluation of over $2 \times 10^{20}$
different trees. Not much imagination is needed to comprehend that this is -- and presumably
will remain -- computationally infeasible.

Branch-and-Bound methods \cite{land1960} provide an alternative approach to find a globally
optimal solution to the problem of tree search, however without the need to evaluate every
possible tree topology. Instead, an exact but guided search in the tree space is performed
omitting those subspaces where the optimal tree cannot be contained in \cite{hendy1982}.
The rationale is simple and has the only prerequisite that the criterion of tree evaluation,
i.e., the objective function $F$, is non-decreasing with the addition of new taxa to a
particular subtree. For the following we assume that we aim to minimize the objective
function $F$. We start with the definition of an upper bound for $F$. This can be obtained
for example by evaluating any arbitrary $n$-taxon tree. Subsequently, using again a three
taxon tree as a primer we recursively reconstruct the possible $n$-taxon trees. However,
as we move on in our reconstruction procedure, i.e., with the addition of more and more taxa
into the trees, we compare $F$ of the resulting subtrees with $F_\mathit{upper}$. As soon as
$F_\mathit{subtree}$ exceeds the predefined upper limit of $F$ we can be certain that our combined
reconstruction/search path leads to a subspace where no tree equally good or better than the
reference tree can be found. Thus, no further reconstruction is required and a new path has
to be followed up. Alternatively, if we end up with a tree including all taxa that is equally
good or better than the reference tree, we will store this as a candidate and update $F_\mathit{upper}$
to the new value. Meanwhile, a number of improvements have been added to increase the efficiency
of Branch-and-Bound methods in the tree search process \cite{hendy1982,swofford1996}. These
refinements are mainly designed to facilitate earlier cut-offs in the tree search. They include
methods to obtain a near optimal tree for an assessment of the initial upper bound, as well as
considerations in the order taxa are added to the subtrees, e.g., to add divergent taxa first,
thereby increasing the length of the initial subtrees.

Despite these improvements exact searches eventually run into computational problems when data
sets become large. For these cases, the considerably faster heuristic methods for tree reconstruction
are required.

\subsection{Heuristic methods}
Summarizing heuristic methods for tree reconstruction with the attribute 'quick and dirty' is
not entirely inappropriate. The jettison of a guaranteed globally optimal solution to the tree
search problem -- therefore 'dirty' -- earns a substantial speed up in computation time. With
contemporary software it is nowadays possible to reconstruct trees from data sets of more
than thousand taxa, e.g., \cite{minh2005a}. Thus, we are nowadays in the pleasant situation
that biological datasets hardly ever reach the computational limits of tree reconstruction
software, provided that one is willing to abandon the guaranteed optimality.
\subsubsection{Hill-climbing and the problem of local optimization}
The problem to find an optimal tree for a set of taxa can be illustrated by the metaphor of a
night time hiker aiming to visit the point with the highest altitude in a hilly area. Due to
the poor visibility, the highest peak cannot be identified a priori. Thus, the hiker remains
with the only option to climb any slope he encounters first until he has reached its top. Up
there he checks his altimeter and is either confident to have reached one of the highest points
in this area and finishes his search, or he invests more effort and climbs another hill. The
analogy to the tree search problem is obvious. Starting off with any tree we modify it in a
stepwise fashion usually accepting only such modifications that lead, according to the chosen
optimality criterion, to an improved tree. At a certain point no further improvement is possible,
and thus we have reached the top of the hill. At this point of the search, however, we have no
means to decide whether we have found the globally optimal tree, or merely a local optimum and
an optimization of a different starting tree would obtain better results. Consequently, these
kinds of tree searches have to cope with three challenges: first, the identification of a
reasonable tree to start the search with, second the implementation of a stepwise hill climbing
algorithm for the tree search, and third the avoidance of local optima.
\paragraph{Identification of the starting tree}
Reasonable starting trees are quickly obtained via so called "greedy" strategies. The
tree reconstruction is is divided into several subproblems which are then sequentially solved
by choosing always that solution that looks best given the current situation.
\begin{figure}
\fbox{\includegraphics[width=.8\textwidth]{images/star-decomp}}
\caption{Star decomposition}
\label{STARDEC}
\end{figure}
In star decomposition methods (figure \ref{STARDEC}), e.g. Saitou and Nei's Neighbor Joining
algorithm \cite{saitou1987}, we begin with an assignment of all taxa in the data set to the
terminal nodes of a star like tree. Subsequently, all trees are evaluated that can be obtained
by joining any two of the terminal taxa into a new group. The tree that scores best under the
chosen optimality criterion forms then the basis for the next step. The iteration of pairwise
joining and tree evaluation continues until the tree is fully resolved, that is an optimal
binary tree is obtained.
\begin{figure}
\fbox{\includegraphics[width=.8\textwidth]{images/stepwise-insertion}}
\caption{Stepwise insertion}
\label{STEPADD}
\end{figure}
Alternatively, we can directly construct a binary tree from scratch by inserting the taxa into
a tree in a stepwise fashion (figure \ref{STEPADD}) \cite{farris1970}. First, a set of three
taxa is used to form a unique binary tree. Next, a fourth taxon is chosen for insertion into
the initial tree. Since the this can be attached on any of the three branches of the initial
tree, we have three possible topologies for the four-species tree. All of these will be evaluated
and the best tree will be stored for insertion of the fifth taxon. The iteration continues until
the tree includes all taxa in the data set.

It is straightforward to see why both star decomposition methods as well as the stepwise insertion
procedure are prone to obtain only locally optimal trees. Any decision concerning the position of
a taxon in the tree is fix for the remaining part of the reconstruction procedure.
\begin{figure}
\fbox{\includegraphics[width=.8\textwidth]{images/tree-rearrangements}}
\caption{Three methods to accomplish branch swapping}
\label{BRANCHSWAPP}
\end{figure}
\paragraph{Optimization procedure and avoidance of local optima}
To increase the flexibility, and by that to escape from local optima, tree-rearrangement methods
exist to override previous decisions. In brief, the initial 'optimal' tree is modified such that
a part of the tree is excised and re-inserted at a different position. The trees resulting from
such 'branch swaps' are evaluated and subjected to one or more acceptance criteria. While a better
tree will be always accepted, trees inferior to the one already obtained can be accepted under
certain conditions \cite{huelsenbeck2001}. This deviation from the strict hill climbing approach
facilitates the transition to better trees that are more than one rearrangement apart from the
currently best tree. Currently, three alternative ways of branch swapping are in use (figure
\ref{BRANCHSWAPP}). Nearest Neighbor Interchange, the least complex approach, takes any internal
branch of the tree and swaps two of the four connected subtrees. By that, a total of $O(n)$
alternative trees can be evaluated.\footnote{Note that only swapping of two subtrees located on the
opposite sides of the internal branch leads to the formation of a new tree!} Subtree pruning
and regrafting ($O(n^2)$) excises a subtree and regrafts it with the cut surface at any branch
on the tree. Tree-bisection and reconnection is the most complex way to swap branches ($O(n^3)$).
The tree is bisected along an internal branch and the resulting subtrees are rejoined at any pair
of branches.

As noted, any of the branch swapping methods is capable to guide the tree reconstruction procedure
out of a local optimum. However, no guarantee is given that it does not simply lead into the next
local optimum, such that the benefit is only limited. Apparently, if the branch swapping is
performed only sufficiently long it becomes likely that sooner or later the global optimum will
be found. However, two problems are associated with this: how shall we recognize the
globally optimal tree, and how long do we have to continue the tree search?
\subsubsection{When (better) trees go extinct}
It is inherent in the heuristic approach that no matter how long we search, we can never be sure
that we have found the globally optimal tree. Thus, we need an idea whether the tree we are looking
at is just good and we can expect to find a better one soon, or whether it is already 'pretty good'
and it will take a fortune to find a better one (although it might exist...). Generally, it is
entirely up to the endurance of the researcher how long he or she allows the program to search.
Either a predefined number of optimization steps or a lower limit by which new trees improve led
to a truncation of the search. Both criteria are arbitrary and a more stalwart basis would be
desirable to decide whether to continue or to end the tree search.

Recently, a method was suggested that is based on the rate of finding better trees during the
search \cite{vinh2004}. Let $F_1, F_2, \ldots , F_j$ denote the values of the objective function
$F$ for the trees found at iteration $1, 2,...,j$. Then the sequence $r(k)$ of record times (i.e.,
iteration number, when a better tree is found) is defined by
\begin{equation}
r(1)=1, \, r(k+1)= \min\{j|F_j > F_{r(k)} \}.
\end{equation}
This sequence is used to estimate the point in time, $r_{\mbox{stop}}$, at which to stop the search,
i.e., when it appears unlikely that a further search will lead to a better tree. Using the theory
detailed in \cite{cooke1980} and \cite{roberts2003}, one can estimate on the fly an upper 95\%
confidence limit $r_{95\%}$ of $r_{\mbox{stop}}$. Once $r_{95\%}$ iterations have been carried out
and a better tree was not detected the program will stop. It can then be concluded that with a
probability of 95\% no better tree will be found during this search. On the other hand, if a better
tree is found before $r_{95\%}$ is hit, the $r_{95\%}$ is re-estimated on the basis of the new record
time added to the sequence $r(k)$.
\subsubsection{Heuristics for large data sets}
The considerable ease with which DNA sequences are nowadays obtained has started a footrace between
size of the data sets available for phylogeny reconstruction and the capacity of tree reconstruction
software. The objectives for further improvement on the computational basis can be quickly summarized.
First, finding in shorter time a better starting tree for subsequent optimization. IQPNNI
\cite{vinh2004} accomplishes this by limiting the number of computation steps to place a new taxon
during tree reconstruction. PhyNav \cite{vinh2005}, on the other hand, reduces the initial tree space
by choosing for each group of closely related taxa one representative. From the resulting representative
leaf set a scaffold is reconstructed, to which subsequently the initially deferred taxa are added
such that an optimal tree is obtained. Second, improving the algorithms for tree optimization. For
example PHYML \cite{guindon2003} has implemented a fast algorithm for Nearest Neighbor Interchange
and RAxML \cite{stamatakis2005} provides an improved version for subtree pruning and regrafting. Third,
the utilization of alternative approaches for tree reconstruction, such as a metapopulation genetic
algorithm \cite{lemmon2002}. And fourth, the dissection of the tree reconstruction problem into a
set of sub-problems that can be solved on several CPUs in parallel. Some of these improvements are
considerably recent developments and it is up to further investigation to determine which combination
will be optimal for tree reconstruction. In a sense an all embracing optimal solution might be
elusive since it is likely that different combinations will perform optimal depending on the
particular data set under consideration. For the same reason it is impossible to provide guidelines
when to use what program best. Different programs will almost inevitably obtain different trees,
and it will always be up to the biologist's ultimate adjudication which of the alternative trees is
the most plausible one. However, one general statement might be justified: with the employment of
parallel computing the biologists can make at least his or her decision sooner. Therefore, the
majority of contemporary tree reconstruction software is available in a parallelized version,
e.g. \cite{stewart2001,olsen1994,stamatakis2005,schmidt2002,schmidt2003a,keane2005,brauer2002,
zhou2004a,wolf2000,zhou2004a,minh2005}
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5
\section{The advent of Phylogenomics}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5

A common problem for the accurate reconstruction of evolutionary relationships among taxa
is the limited amount of phylogenetic signal in the data, which is in addition
frequently blanketed by noise. In view of the ever increasing availability
of DNA sequences provided by the various genome sequencing efforts it seems
trivial to enhance the signal-to-noise-ratio by the simple addition of more data
\cite{hillis1996b}. However, even with the availability of whole genome sequences
alignments remain in many cases limited to the level of individual genes.
Both the rearrangement of genetic information in different taxa and the in part
substantial sequence divergence of non-functional parts of the genome prevent the
generation of meaningful longer sequence alignments. To nonetheless extend the
amount of information, disjoint datasets derived from multiple genomic loci can be recruited
for the analysis. This intersection of phylogenetics and genomics is referred to as phylogenomics.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Multi-locus data sets}\label{sec:consensus}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   \begin{figure}[t!]
      \centering
      \resizebox{\textwidth}{!}{
      %\begin{tabular}{|c|p{.20\textwidth}|c|}\hline
      \begin{tabular}{|c|p{.18\textwidth}|p{.75\textwidth}|}\hline
	   combination & \parbox{.18\textwidth}{method}    & 
					   \parbox{.75\textwidth}{~\\
					   \includegraphics[width=.75\textwidth]%
					   {images/combination-level}\\}\\ 
					   \hline
					   \hline
	   early level & \parbox{.18\textwidth}{\emph{Total Evidence}}   & 
					   \parbox{.75\textwidth}{~\\
					   \includegraphics[width=.75\textwidth]%
					   {images/combination-total}\\}\\
					    \hline
	   late level & \parbox{.18\textwidth}{\emph{Consensus}}       & 
					   \parbox{.75\textwidth}{~\\
					   \includegraphics[width=.75\textwidth]%
					   {images/combination-consensus}\\}\\ 
					    \hline
   \end{tabular}}
   \caption[Levels of Dataset Combination - Complete Data]
           {Level of combination with regard to distance from the underlying 
            datasets. All datasets have the same taxa sets.}
   \label{fig:combination-compl}
   \end{figure}

Having multi-locus datasets derived from the the same set of taxons at hand, two approaches 
have been suggested to combine those datasets for phylogenetics analysis.
In supermatrix approaches \cite{sanderson1998} (also referred to as 
'total evidence' \cite{kluge1989}) data is combined early in the 
analysis by the concatenation of all individual sequence alignments into one large 
superalignment or supermatrix. This alignment can then be used as input 
to essentially any tree reconstruction method to build a tree
(figure ~\ref{fig:combination-compl}).

Another way is to perform a late combination of the data. First, a tree is reconstructed
separately for each dataset. These individual trees are then typically summarized in a so-called consensus 
tree (figure~\ref{fig:combination-compl}). The most abundant methods to compute a consensus
tree are based on the criterion of compatible splits. Splits comprise bipartitions
of the taxon set induced by cutting an
internal edge of a tree.\footnote{Cutting external edges produces only trivial 
splits present in all trees and are, thus, usually discarded.}
In a formal notation they are represented by the symbol '$|$' as in 
figure~\ref{fig:consensus}. 
\label{incompatible}Note, that two splits
$\mathcal{A}|\mathcal{B}$ and $\mathcal{C}|\mathcal{D}$
are considered incompatible if all four possible 
intersection $\mathcal{A} \cap \mathcal{C}$, $\mathcal{A} \cap \mathcal{D}$,
$\mathcal{B} \cap \mathcal{C}$, $\mathcal{B} \cap \mathcal{D}$ are non-empty.
Two trees that contain pairwise incompatible splits are incongruent.

   \begin{figure}[t!]
      \centering
	\fbox{\includegraphics[width=.8\textwidth]{images/consensus-all}}
      \caption[Consensus Methods]
           {Examples for consensus methods to summarize a set of trees
	    with identical taxon sets: strict ($M_{\mathit{strict}}$),
	    semi-strict ($M_{\mathit{semi-strict}}$), and 
	    $50\%$-majority rule consensus ($M_{0.5}$).}
   \label{fig:consensus}
   \end{figure}

The simplest form of the majority consensus $M_{\mbox{majority}}$ \cite{margush1981} collects all
splits in the consensus tree that occur in at least 50\% of the individual trees (figure~\ref{fig:consensus}).
This approach
guarantees that the consensus tree is in fact a tree \cite{semple2003}.
More extreme cases of majority consensus are the strict consensus 
$M_{\mathit{strict}}$ \cite{rohlf1982} that incorporates only  splits 
present in all trees (figure~\ref{fig:consensus}), and the semi-strict 
consensus $M_{\mathit{semi-strict}}$ \cite{bremer1990} that contains all splits 
which are not contradicted by any split from the input trees 
(figure~\ref{fig:consensus}). The latter might only differ from the former 
if multifurcations exist in the input trees. Many further methods exist to arrive at
a consensus tree which we lack the space to go into detail with, e.g., \cite{adams1986, schmidt2003b}. 

The application of consensus methods extends beyond the combination of separate trees from
multi-locus reconstructions. In principle they can be used to summarize 
any set of trees, e.g., derived from Bootstrap analysis 
\cite{felsenstein1985}, sampled from MCMC simulations 
\cite{huelsenbeck2001}, or obtained by randomized input orders 
\cite{strimmer1996} to assess the reliability (or uncertainty)
in the reconstructed trees.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5
\subsection{Combining Incomplete Multi-Locus Datasets: Supertrees et al.}
   \label{sec:supertree-methods}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5

One serious limitation in the use of consensus methods is their restriction to trees of equal size and taxon sets.
This causes a trade-off between the number of taxa and the number
of loci used in the analysis, because the mutual coverage of available 
genes and taxa is far from being satisfactory \cite{driskell2004}.
The problem remains even when completely sequenced genomes are available since taxon
or group-specific genes exist that are not represented in other taxa. Consequently, the question
was raised how to incorporate such incomplete datasets into 
phylogenetic analysis.

Again supermatrix methods (cf. above and figure~\ref{fig:combination-incompl}) 
can be used to combine the datasets early by concatenation. However, subsequently 
applied tree reconstruction methods must be aware of missing data. 
Discarding those as gaps, would leave the user with only completely 
sampled loci or even no data at all.

   \begin{figure}[t!]
      \centering
      \resizebox{\textwidth}{!}{
      %\begin{tabular}{|c|p{.20\textwidth}|c|}\hline
      \begin{tabular}{|c|p{.18\textwidth}|p{.75\textwidth}|}\hline
	   combination & \parbox{.18\textwidth}{method}    & 
					   \parbox{.75\textwidth}{~\\
					   \includegraphics[width=.75\textwidth]%
					   {images/combination-level}\\}\\ 
					   \hline
					   \hline
	   early level & \parbox{.18\textwidth}{\emph{Total Evidence}}   & 
					   \parbox{.75\textwidth}{~\\
					   \includegraphics[width=.75\textwidth]%
					   {images/combination-total-incompl}\\}\\
					    \hline
	   %late level & \parbox{.18\textwidth}{\emph{Consensus}}       & 
	   %				\parbox{.75\textwidth}{~\\
	   %				\includegraphics[width=.75\textwidth]%
	   %				{images/combination-consensus}\\}\\ 
	   %				%\hline
	   late level & \parbox{.18\textwidth}{\emph{MRP}, \emph{MRF}} & 
					   \parbox{.75\textwidth}{~\\
					   \includegraphics[width=.75\textwidth]%
					   {images/combination-mrp}\\}\\ 
					   %\hline
	   late level & \parbox{.18\textwidth}{\sloppy\textsc{ModMinCut}, \textsc{MinCut\\Supertree}} 
                                         & \parbox{.75\textwidth}{~\\
					   \includegraphics[width=.75\textwidth]%
					   {images/combination-mincut}\\}\\ 
					   %\hline
	   late level & \parbox{.18\textwidth}{\sloppy\emph{Quartet-based supertree}} 
	                                 & \parbox{.75\textwidth}{~\\
					   \includegraphics[width=.75\textwidth]%
					   {images/combination-quartet}\\}\\ 
					   \hline
	   medium level & \parbox{.18\textwidth}{\sloppy\emph{SQP}}        
	                                 & \parbox{.75\textwidth}{~\\
					   \includegraphics[width=.75\textwidth]%
					   {images/combination-puzzle}\\}\\ 
					   \hline
      \end{tabular}}
      \caption[Levels of Dataset Combination]
              {Level of combination with regard to distance from the underlying 
               datasets}
      \label{fig:combination-incompl}
   \end{figure}

For a late combination of the data, methods have been proposed to combine separately
reconstructed overlapping (typically rooted) trees of the different loci into one so-called
supertree \cite{gordon1986,bininda2004d}. Supertrees approaches can 
be divided into two classes, agreement supertrees \cite{bininda2004}
and optimization supertrees \cite{wilkinson2004}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5
\subsubsection{Agreement Supertrees}

The \emph{agreement supertrees} \cite{bininda2004} are based on 
common nestings in rooted input trees to build the supertree.
To that end, rooted input trees are decomposed into rooted triplets
(figure~\ref{fig:combination-incompl}). 
Early algorithms like \textsc{Build}/\textsc{OneTree} \cite{aho1981,bryant1995}
would only return a tree if all input trees are congruent, 
that is, no contradictions exist among the overlapping input trees.
This drawback was tried to be overcome \cite{semple2000} introducing 
a minimum-cut step that greedily resolves tree contradictions in the
\textsc{MinCut Supertree} algorithm. This algorithm was 
modified and improved in the \textsc{ModMinCut Supertree} algorithm
\cite{page2002d} by keeping uncontradicted nesting in the input trees.
Further \emph{agreement supertree} methods have been 
suggested recently (\cite{bininda2004,bininda2004b} for overview).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5
\subsubsection{Optimization Supertrees}

To construct the more commonly used optimization supertrees, the set of 
input trees are decomposed into smaller entities used as input to reconstruct
an overall tree optimizing an objective function.
 

\paragraph{Matrix Representation Methods} are the most abundant supertree 
  methods around. Before tree construction, the rooted input trees are encoded 
  into a binary matrix.
  Typically either splits in the trees (Ragan/Baum scheme 
  \cite{ragan1992,baum1992}) or sister groups (Purvis' scheme \cite{purvis1995})
  are coded by zeros, ones, and '?' for missing data 
  (figure~\ref{fig:MRP-schemes}). The obtained \emph{matrix representation}
  is then used as input alignment to reconstruct a supertree
  (figure~\ref{fig:combination-incompl})
  For this purpose, various optimizing algorithms can be applied, such as i) parsimony (MRP \cite{baum1992,ragan1992}),
  ii) distance-based methods (MRD or average consensus method \cite{lapointe1997}), 
  and iii) finding the optimal tree which requires the least changes
  between ones and zeros (flips) to be congruent with the matrix (MRF \cite{chen2003}). 
  Matrix representation with parsimony (MRP) is by far the most used 
  supertree reconstruction to date.

\paragraph{Other supertree methods} decompose the input trees into
  quartet sub-trees to be used as building blocks in the subsequent 
  tree reconstruction \cite{robinson2001,piaggio2004}
  (figure~\ref{fig:combination-incompl}).

Note, that consensus methods could be seen as a special case of the 
supertree approach, because the former is limited to combine trees with 
identical taxa sets while the latter can combine trees with
identical as well as overlapping taxa sets.


\begin{figure}[t]
  \centering
  \includegraphics[width=.5\textwidth]{images/MRP-schemes}
  \caption[MRP Coding Schemes]
          {Coding schemes to encode tree topologies for MRP methods:
           Baum/Ragan and Purvis' scheme}
  \label{fig:MRP-schemes}
\end{figure}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{The Supertrees/Consensus vs. Total Evidence Debate}

Having two alternative approaches at hand for the reconstruction
of trees from patchy data ultimately invokes the debate whether supertree/consensus methods are superior to
the use of a supermatrix
\cite{queiroz1995,miyamoto1995,bininda2002c,bininda2003a,bininda2004a,bininda2004b},
or vice versa \cite{gatesy2002,gatesy2004,eernisse1993,kluge1989,kluge1998}.
Meanwhile a number of critics have been raised
against either approach, as have advantages. 
The predominant critique on the supermatrix approach is the 
issue how to choose an evolutionary model and its parameters 
such that it reflects the various evolutionary constraints imposed on the
different concatenated datasets.
On the other hand, supertree methods are criticized for their heedless
dealings of information provided by the data.
Usually, the underlying sequence data is discarded
prior to combining the input trees. Thus any information not represented by
the tree topology is inevitably lost. Furthermore, supertrees carry the
risk of possible unwanted data duplication and weighting 
\cite{gatesy2002,gatesy2004a}, especially if tree topologies have 
been collected from the literature.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Medium Level Combination}

Based on the above criticisms, a third level of dataset combination
has been proposed recently, which takes an intermediate position between the (late) supertree 
and the (early) supermatrix approaches. It is, hence, referred to as medium 
level combination. The so-called superquartet puzzling algorithm (SQP \cite{schmidt2003b})
combines the data on the level of four taxon trees. These so-called superquartets
are then used as building blocks in the
reconstruction using a voting scheme and a construction algorithm that is aware
of missing data.

SQP allows to apply evolutionary models to be fitted to
each locus separately. Furthermore, it uses the phylogenetic
information in the sequences both to combine the data and in the reconstruction of
the final tree. Thus, SQP tries to combine known advantages of supermatrix
and supertree methods, and is in addition able to use unrooted datasets.

The advent of phylogenomics greatly enhances the need for
further and more sophisticated methods to deal with heterogeneous multiple loci
as data. Thus, a rapid development on this sector is to be expected in the near future.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Phylogenetic Network Methods}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 The tree reconstruction methods presented so far are by the nature of the biological data
only approximate methods. The four-point condition (Equation \ref{eqt:fourpoint}) is almost never
fulfilled. Thus, every reconstructed tree will not entirely reflect the observed data, but
only provide a more or less accurate approximation. Even worse, no matter if the data evolved tree-like or not, tree
reconstruction will always come up with a suggested tree at the end of the day. In practice, biologists try to avoid
methodological artifacts by applying a plethora of different tree-building algorithms. Still,
one may encounter a systematic error, when the methods are subject to the same bias and therefore
hide the true relationship.

Thus a series of algorithms were proposed that should accompany phylogenetic analysis. These methods
will reveal to some extent conflicting alternative groupings in the data, that cannot be illustrated
in a tree \cite{bandelt1992}. Such algorithms are nowadays subsumed under so-called (phylogenetic)
network methods \cite{posada2001f}. Phylogenetic networks should be applied in early
stages of the data analysis. It should be noted that networks provide a visualization of the data and do
not qualify as inference methods. However, if phylogenetic networks exhibit a certain degree of reticulation,
this can indicate substantial departure from tree-likeness. We can envision several biological causes why a
tree is not apropriate for the data at hand. Reassortment \cite{klempa2003} and recombination \cite{posada2002a,paraskevis2005},
e.g., in viruses \cite{fitch1996,salminen1995}
are one example. Horizontal gene transfer \cite{delwiche1996,guindon2001,bergthorsson2003} and genome
hybridization or fusion \cite{zillig1991,doolittle1999a,martin1999} constitute other possibilities.
Sometimes reticulation may be simply due to parallel substitutions in different organisms. In such a situation
the loops in the network indicate the occurrence of reverse or parallel mutations.

One should note, that the basic idea to represent evolutionary processes by networks rather than trees has a
long history. However, only with the advent of computer programs networks became now widely applied in phylogenetic
research. Distance based methods including split decomposition \cite{bandelt1992} or the recently introduced method Neighbor-Net \cite{bryant2004}
as implemented in programs like SplitsTree \cite{huson1998}\RB{ST ist keine Methode - die Methode ist SplitDecomp mit splits-graphs - ebenso T-REX}
and T-REX \cite{makarenkov2001a} as well as character based methods like in
NETWORK \cite{bandelt1999} and Spectronet \cite{huber2002} provide easy to use means that can be readily applied to a phylogenetic analysis.
These package were used to analyze viral data \cite{dopazo1993,salemi2003} (figure \ref{fig:networks})
hybridization events \cite{lockhart2001} and intra-specific data \cite{bandelt1995}.

Furthermore, methods have been suggested to summarize sets (contradictory) trees in more 
detail, taking into account also splits occurring even below the $50\%$ cut-off (cf. $M_50$ consensus).
This way sets of trees with equal taxon sets (cf. \ref{sec:consensus}) can be combined to 
consensus-networks \cite{holland2004}, but also trees with missing taxa into co-called 
super-networks \cite{huson2004b}. 

   \begin{figure}[t!]
      \centering
	\fbox{%
		\includegraphics[width=.32\textwidth]{images/A-J-cons-recombinants-bnj-3rec}\hfill%
		\includegraphics[width=.32\textwidth]{images/A-J-cons-recombinants-sd-3rec}\hfill%
		\includegraphics[width=.32\textwidth]{images/A-J-cons-recombinants-nnet-3rec}%
	}
      \caption[Consensus Methods]
           {Results for a set of HIV dataset from \cite{salemi2003} containing 
	    reference strains (A, B, C, D, F, G, H, J) together with 
            three recombinants (SE7812\_2, UG266, VI1310-1.7). 
            Left: BioNJ tree,
	    middle: Split Decomposition, 
            right: Neighbor-Net.}
   \label{fig:networks}
   \end{figure}

The pros and cons of the different algorithms still need to be evaluated. However, the comparison of different phylogenetic networking
strategies is not easy. From figure \ref{fig:networks} it is apparent that the phylogenetic tree for the HIV data
\cite{salemi2003} does not persist if Splitstree or Neighbor-Net is applied. One readily sees
that Neighbor-Net is more liberal in introducing non-compatible splits. However, which of the two networks reflect the true
(unobservable) history of the data more correctly is at present not clear.
Simulation studies, successfully applied in phylogenetic inference, might be one way to evaluate accuracy and robustness of phylogenetic
network methods. To this end a carefully designed experimental set up is required. An alternative approach is
the introduction of optimality criteria (least square, likelihood) in the network construction process. Unfortunately,
the development of phylogenetic networks in a likelihood framework is still in its infancy \cite{haeseler1993,strimmer2000,strimmer2001}.
Only with such methods, one is able to
decide whether the non-tree like signals are biologically plausible or are merely an artifact of the reconstruction procedure.

In this chapter, we have only touched upon some phylogenetic network methods. Space limitation does not allow a full account of
all existing methods. The pyramidal clustering technique \cite{diday1986} is like Neighbor-Net an agglomerative approach. Statistical
geometry in sequence space \cite{eigen1988} and its descendants \cite{strimmer1997a,nieselt2001} are alternative approaches
to summarize the extent of
tree-likeness in the data without reconstructing phylogenetic networks. 

The field of phylogenetic networks will certainly profit from the data produced in whole genome projects. Because independently
evolving DNA segments of eukaryotic genomes may display different evolutionary histories, the correct history of the taxa, as
carriers of these segments, is probably more adaequate. However, before we can reliably do this, we need to distinguish true loops
in a network from artificial loops generated by too simple assumptions about the evolutioary process.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\bibliography{phylo-chapter}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{thebibliography}{100}

\bibitem{adams1986}
Edward~N. Adams~III.
\newblock N-trees as nestings: Complexity, similarity, and consensus.
\newblock {\em J. Classif.}, 3:299--317, 1986.

\bibitem{aho1981}
Alfred~V. Aho, Yehoshua Sagiv, Thomas~G. Szymanski, and Jeffrey~D. Ullman.
\newblock Inferring a tree from lowest common ancestors with an application to
  the optimization of relational expressions.
\newblock {\em SIAM J. Comput.}, 10:405--421, 1981.

\bibitem{bandelt1986}
H.-J. Bandelt and A.~Dress.
\newblock Reconstructing the shape of a tree from observed dissimilarity data.
\newblock {\em Adv. Appl. Math.}, 7:309--343, 1986.

\bibitem{bandelt1992}
H.-J. Bandelt and A.~W.~M. Dress.
\newblock Split decomposition: A new and useful approach to phylogenetic
  analysis of distance data.
\newblock {\em Mol. Phylogenet. Evol.}, 1:242--252, 1992.

\bibitem{bandelt1999}
Hans-J. Bandelt, Peter Forster, and Arne R{\"o}hl.
\newblock Median-joining networks for inferring intraspecific phylogenies.
\newblock {\em Mol. Biol. Evol.}, 16:37--48, 1999.

\bibitem{bandelt1995}
Hans-J. Bandelt, Peter Forster, Bryan~C. Sykes, and Martin~B. Richards.
\newblock Mitochondrial portraits of human populations using median networks.
\newblock {\em Genetics}, 141:743--753, 1995.

\bibitem{baum1992}
Bernard~R. Baum.
\newblock Combining trees as a way of combining data sets for phylogenetic
  inference, and the desirability of combining gene trees.
\newblock {\em Taxon}, 41:3--10, 1992.

\bibitem{bergthorsson2003}
Ulfar Bergthorsson, Keith~L. Adams, Brendan Thomason, and Jeffrey~D. Palmer.
\newblock Widespread horizontal transfer of mitochondrial genes in flowering
  plants.
\newblock {\em Nature}, 424:197--201, 2003.

\bibitem{bininda2003a}
Olaf R.~P. Bininda-Emonds.
\newblock Supertrees are a necessary not-so-evil: A comment on gatesy et al.
\newblock {\em Syst. Biol.}, 52:724--729, 2003.

\bibitem{bininda2004}
Olaf R.~P. Bininda-Emonds.
\newblock The evolution of supertrees.
\newblock {\em TREE}, 19:315--322, 2004.

\bibitem{bininda2004d}
Olaf R.~P. Bininda-Emonds, editor.
\newblock {\em Phylogenetic Supertrees: Combining Information to Reveal the
  Tree of Life}.
\newblock Kluwer Academic, Dordrecht, 2004.

\bibitem{bininda2004a}
Olaf R.~P. Bininda-Emonds.
\newblock Trees versus characters and the supertree / supermatrix ''paradox''.
\newblock {\em Syst. Biol.}, 53:360--361, 2004.

\bibitem{bininda2002c}
Olaf R.~P. Bininda-Emonds, John~L. Gittleman, and Mike~A. Steel.
\newblock The (super)tree of life: Procedures, problems, and prospects.
\newblock {\em Annu. Rev. Ecol. Syst.}, 33:265--289, 2002.

\bibitem{bininda2004b}
Olaf R.~P. Bininda-Emonds, Kate~E. Jones, Samantha~A. Price, Marcel Cardillo,
  Richard Grenyer, and Andy Purvis.
\newblock Garbage in, garbage out: data issues in supertree construction.
\newblock In Olaf R.~P. Bininda-Emonds, editor, {\em Phylogenetic Supertrees:
  Combining Information to Reveal the Tree of Life}, page in press. Kluwer
  Academic, Dordrecht, The Netherlands, 2004.

\bibitem{brauer2002}
Matthew~J. Brauer, Mark~T. Holder, Laurie~A. Dries, Derrick~J. Zwickl, Paul~O.
  Lewis, and David~M. Hillis.
\newblock Genetic algorithms and parallel processing in maximum-likelihood
  phylogeny inference.
\newblock {\em Mol. Biol. Evol.}, 19:1717--1726, 2002.

\bibitem{bremer1990}
K{\aa}re Bremer.
\newblock Combinable component consensus.
\newblock {\em Cladistics}, 6:369--372, 1990.

\bibitem{bryant2004}
David Bryant and Vincent Moulton.
\newblock Neighbor-net: An agglomerative method for the construction of
  phylogenetic networks.
\newblock {\em Mol. Biol. Evol.}, 21:255--265, 2004.

\bibitem{bryant1995}
David Bryant and Mike Steel.
\newblock Extension operations on sets of leaf-labeled trees.
\newblock {\em Adv. Appl. Math.}, 16:425--453, 1995.

\bibitem{buneman1971}
Peter Buneman.
\newblock The recovery of trees from measurements of dissimilarity.
\newblock In Frank~R. Hodson, David~G. Kendall, and Petre Tautu, editors, {\em
  Mathematics in the Archeological and Historical Sciences}, pages 387--395.
  Edinburgh University Press, Edinburgh, UK, 1971.

\bibitem{chen2003}
Duhong Chen, Lixia Diao, Oliver Eulenstein, David Fern\'{a}ndez-Baca, and
  Michael~J. Sanderson.
\newblock Flipping: A supertree construction method.
\newblock In M.~F. Janowitz, F.-J. Lapointe, F.~R. McMorris, B.~Mirkin, and
  F.~S. Roberts, editors, {\em DIMACS Series in Discrete Mathematics and
  Theoretical Computer Science}, volume~61, pages 135--160. American
  Mathematical Society, Providence, Rhode Island, 2003.

\bibitem{cooke1980}
Peter Cooke.
\newblock Optimal linear estimation of bounds of random variables.
\newblock {\em Biometrika}, 67:257--258, 1980.

\bibitem{queiroz1995}
Alan de~Queiroz, Michael~J. Donoghue, and Junhyong Kim.
\newblock Separate versus combined analysis of phylogenetic evidence.
\newblock {\em Annu. Rev. Ecol. Syst.}, 26:657--681, 1995.

\bibitem{delwiche1996}
Charles~F. Delwiche and Jeffrey~D. Palmer.
\newblock Rampant horizontal transfer and duplication of rubisco genes in
  eubacteria and plastids.
\newblock {\em Mol. Biol. Evol.}, 13:873--882, 1996.

\bibitem{diday1986}
Edwin Diday and Patrice Bertrand.
\newblock An extension of hierarchical clustering: the pyramidal
  representation.
\newblock In Edzard~S. Gelsema and Laveen~N. Kanal, editors, {\em Pattern
  recognition in Practice}, volume~II, pages 411--424. North-Holland,
  Sunderland, Massachusetts, USA, 1986.

\bibitem{doolittle1999a}
W.~Ford Doolittle.
\newblock Phylogenetic classification and the universal tree.
\newblock {\em Science}, 284:2124--2128, 1999.

\bibitem{dopazo1993}
Joaquin Dopazo, Andreas Dress, and Arndt von Haeseler.
\newblock Split decomposition: A technique to analyze viral evolution.
\newblock {\em Proc. Natl. Acad. Sci. USA}, 90:10320--10324, 1993.

\bibitem{driskell2004}
Amy~C. Driskell, C{\'e}cile An{\'e}, J.~Gordon Burleigh, Michelle~M. McMahon,
  Brian~C. O'Meara, and Michael~J. Sanderson.
\newblock Prospects for building the tree of life from large sequence
  databases.
\newblock {\em Science}, 306:1172--1174, 2004.

\bibitem{eernisse1993}
Douglas Eernisse and Arnold~G. Kluge.
\newblock Taxonomic congruence versus total evidence, and amniote phylogeny
  inferred from fossils, molecules, and morphology.
\newblock {\em Mol. Biol. Evol.}, 10:1170--1195, 1993.

\bibitem{eigen1988}
Manfred Eigen, Ruthild Winkler-Oswatitsch, and Andreas Dress.
\newblock Statistical geometry in sequence space: A method of quantitative
  comparative sequence analysis.
\newblock {\em Proc. Natl. Acad. Sci. USA}, 85:5913--5917, 1988.

\bibitem{farris1977}
James~S. Farris.
\newblock Phylogenetic analysis under dollo's law.
\newblock {\em Syst. Zool.}, 26:77--88, 1977.

\bibitem{farris1996}
James~S. Farris.
\newblock Parsimony jackknifing outperforms neighbor-joining.
\newblock {\em Cladistics}, 12:99--124, 1996.

\bibitem{farris1970}
James~S. Farris, Arnold~G. Kluge, and Michael~J. Eckhardt.
\newblock A numerical approach to phylogenetic systematics.
\newblock {\em Syst. Zool.}, 19:172--189, 1970.

\bibitem{felsenstein1978}
Joseph Felsenstein.
\newblock The number of evolutionary trees.
\newblock {\em Syst. Zool.}, 27:27--33, 1978.

\bibitem{felsenstein1981}
Joseph Felsenstein.
\newblock Evolutionary trees from {DNA} sequences: a maximum likelihood
  approach.
\newblock {\em J. Mol. Evol.}, 17:368--376, 1981.

\bibitem{felsenstein1984}
Joseph Felsenstein.
\newblock Distance methods for inferring phylogenies: A justification.
\newblock {\em Evolution}, 38:16--24, 1984.

\bibitem{felsenstein1985}
Joseph Felsenstein.
\newblock Confidence limits on phylogenies: An approach using the bootstrap.
\newblock {\em Evolution}, 39:783--791, 1985.

\bibitem{felsenstein1987}
Joseph Felsenstein.
\newblock Estimation of hominoid phylogeny from a {DNA} hybridization data set.
\newblock {\em J. Mol. Evol.}, 26:123--131, 1987.

\bibitem{ferris1981}
Stephen~D. Ferris, Allan~C. Wilson, and Wesley~M. Brown.
\newblock Evolutionary tree for apes and humans based on cleavage maps of
  mitochondrial {DNA}.
\newblock {\em Proc. Natl. Acad. Sci. USA}, 78:2432--2436, 1981.

\bibitem{fisher1912}
Ronald~A. Fisher.
\newblock On an absolute criterion for fitting frequency curves.
\newblock {\em Messenger in Mathematics}, 41:155--160, 1912.

\bibitem{fitch1971}
Walter~M. Fitch.
\newblock Toward defining the course of evolution: Minimum change for a
  specific tree topology.
\newblock {\em Syst. Zool.}, 20:406--416, 1971.

\bibitem{fitch1996}
Walter~M. Fitch.
\newblock The variety of human virus evolution.
\newblock {\em Mol. Phylogenet. Evol.}, 5:247--258, 1996.

\bibitem{gatesy2004}
John Gatesy, Richard~H. Baker, and Cheryl Hayashi.
\newblock Inconsistencies in arguments for the supertree approach:
  Supermatrices versus supertrees of {Crocodylia}.
\newblock {\em Syst. Biol.}, 53:342--355, 2004.

\bibitem{gatesy2002}
John Gatesy, Conrad Matthee, Rob DeSalle, and Cheryl Hayashi.
\newblock Resolution of a supertree/supermatrix paradox.
\newblock {\em Syst. Biol.}, 51:652--664, 2002.

\bibitem{gatesy2004a}
John Gatesy and Mark~S. Springer.
\newblock A critique of matrix representation with parsimony supertrees.
\newblock In Olaf R.~P. Bininda-Emonds, editor, {\em Phylogenetic Supertrees:
  Combining Information to Reveal the Tree of Life}, pages 369--388. Kluwer
  Academic, Dordrecht, The Netherlands, 2004.

\bibitem{goldman1994}
Nick Goldman and Ziheng Yang.
\newblock A codon--based model of nucleotide substitution for protein--coding
  {DNA} sequences.
\newblock {\em Mol. Biol. Evol.}, 11:725--736, 1994.

\bibitem{gordon1986}
Allan~D. Gordon.
\newblock Consensus supertrees: The synthesis of rooted trees containing
  overlapping sets of labelled leaves.
\newblock {\em J. Classif.}, 3:335--348, 1986.

\bibitem{gu1995}
Xun Gu, Yun-Xin Fu, and Wen-Hsiung Li.
\newblock Maximum likelihood estimation of the heterogeneity of substitution
  rate among nucleotide sites.
\newblock {\em Mol. Biol. Evol.}, 12:546--557, 1995.

\bibitem{guindon2003}
St\'{e}phane Guindon and Olivier Gascuel.
\newblock A simple, fast, and accurate algorithm to estimate large phylogenies
  by maximum likelihood.
\newblock {\em Syst. Biol.}, 52:696--704, 2003.

\bibitem{guindon2001}
St\'{e}phane Guindon and Guy Perri{\`e}re.
\newblock Intragenomic base content variation is a potential source of biases
  when searching for horizontally transferred genes.
\newblock {\em Mol. Biol. Evol.}, 18:1838--1840, 2005.

\bibitem{hasegawa1985}
Masami Hasegawa, Hirohisa Kishino, and Taka-Aki Yano.
\newblock Dating of the human--ape splitting by a molecular clock of
  mitochondrial {DNA}.
\newblock {\em J. Mol. Evol.}, 22:160--174, 1985.

\bibitem{hendy1982}
Michael~D. Hendy and David Penny.
\newblock Branch and bound algorithms to determine minimal evolutionary trees.
\newblock {\em Math. Biosci.}, 60:133--142, 1982.

\bibitem{hendy1989}
Michael~D. Hendy and David Penny.
\newblock A framework for the quantitative study of evolutionary trees.
\newblock {\em Syst. Zool.}, 38:297--309, 1989.

\bibitem{hennig1966}
Willi Hennig.
\newblock {\em Phylogenetic systematics}.
\newblock University of Illinois Press, Urbana, IL, USA, 1966.

\bibitem{hillis1996b}
David~M. Hillis.
\newblock Inferring complex phylogenies.
\newblock {\em Nature}, 383:130--131, 1996.

\bibitem{holland2004}
Barbara~R. Holland, Katharina~T. Huber, Vincent Moulton, and Peter~J. Lockhart.
\newblock Using consensus networks to visualize contradictory evidence for
  species phylogeny.
\newblock {\em Mol. Biol. Evol.}, 21:1459--1461, 2004.

\bibitem{holliday1993}
Robin Holliday and Geoffrey~W. Grigg.
\newblock {DNA} methylation and mutation.
\newblock {\em Mutat. Res.}, 285:61--67, 1993.

\bibitem{huber2002}
Katharina~T. Huber, Michael Langton, David Penny, Vincent Moulton, and Michael
  Hendy.
\newblock Spectronet: a package for computing spectra and median networks.
\newblock {\em Appl. Bioinform.}, 20:159--161, 2002.

\bibitem{huelsenbeck2004}
John~P. Huelsenbeck, Bret Larget, and Michael~E. Alfaro.
\newblock Bayesian phylogenetic model selection using reversible jump {Markov}
  chain {Monte Carlo}.
\newblock {\em Mol. Biol. Evol.}, 21:1123--1133, 2004.

\bibitem{huelsenbeck2001}
John~P. Huelsenbeck and Fredrik Ronquist.
\newblock {MRBAYES}: Bayesian inference of phylogenetic trees.
\newblock {\em Bioinformatics}, 17:754--755, 2001.

\bibitem{huson1998}
Daniel~H. Huson.
\newblock {SplitsTree}: Analyzing and visualizing evolutionary data.
\newblock {\em Bioinformatics}, 14:68--73, 1998.

\bibitem{huson2004b}
Daniel~H. Huson, Tobias Dezulian, Tobias Kl{\"o}pper, and Mike~A. Steel.
\newblock Phylogenetic super-networks from partial trees.
\newblock In {\em Proceedings of the 4th Workshop on Algorithms in
  Bioinformatics (WABI 2004)}, volume 3240 of {\em Lecture Notes in Computer
  Science}, pages 388--399, New York, 2004. Springer.

\bibitem{jukes1969}
Thomas~H. Jukes and Charles~R. Cantor.
\newblock Evolution of protein molecules.
\newblock In H.~N. Munro, editor, {\em Mammalian Protein Metabolism}, volume~3,
  pages 21--123. Academic Press, New York, 1969.

\bibitem{keane2005}
Thomas~M. Keane, Thomas~J. Naughton, Simon A.~A. Travers, James~O. McInerney,
  and Grace~P. McCormack.
\newblock {DPRml}: distributed phylogeny reconstruction by maximum likelihood.
\newblock {\em Bioinformatics}, 21:969--974, 2005.

\bibitem{khaitovich2005}
Philipp Khaitovich, Svante P{\"a}{\"a}bo, and Gunter Weiss.
\newblock Toward a neutral evolutionary model of gene expression.
\newblock {\em Genetics}, 170:929--939, 2005.

\bibitem{kimura1980}
Motoo Kimura.
\newblock A simple method for estimating evolutionary rates of base
  substitutions through comparative studies of nucleotide sequences.
\newblock {\em J. Mol. Evol.}, 16:111--120, 1980.

\bibitem{king1975}
Marie-Claire King and Allan~C. Wilson.
\newblock Evolution at two levels in humans and chimpanzees.
\newblock {\em Science}, 188:107--116, 1975.

\bibitem{klempa2003}
Boris Klempa, Heiko~A. Schmidt, Rainer Ulrich, Stefan Kaluz, Milan Labuda,
  Helga Meisel, Brian Hjelle, and Detlev~H. Kr\"uger.
\newblock Genetic interaction between distinct {Dobrava Hantavirus} subtypes in
  {Apodemus agrarius} and {A. flavicollis} in nature.
\newblock {\em J. Virol.}, 77:804--809, 2003.

\bibitem{kluge1989}
Arnold~G. Kluge.
\newblock A concern for evidence and a phylogenetic hypothesis of relationships
  among {Epicrates} ({Boidae, Serpentes}).
\newblock {\em Syst. Zool.}, 38:7--25, 1989.

\bibitem{kluge1998}
Arnold~G. Kluge.
\newblock Total evidence or taxonomic congruence: Cladistics or consensus
  classification.
\newblock {\em Cladistics}, 14:151--158, 1998.

\bibitem{kluge1969}
Arnold~G. Kluge and James~S. Farris.
\newblock Quantitative phyletics and the evolution of anurans.
\newblock {\em Syst. Zool.}, 18:1--32, 1969.

\bibitem{kurland2003}
Charles~G. Kurland, Bjorn Canback, and Otto~G. Berg.
\newblock Horizontal gene transfer: A critical view.
\newblock {\em Proc. Natl. Acad. Sci. USA}, 100:9658--9662, 2005.

\bibitem{lanave1984}
Cecilia Lanave, Giuliano Preparata, Cecilia Saccone, and Gabriella Serio.
\newblock A new method for calculating evolutionary substitution rates.
\newblock {\em J. Mol. Evol.}, 20:86--93, 1984.

\bibitem{land1960}
Ailsa Land and Alison Doig.
\newblock An automatic method for solving discrete programming problems.
\newblock {\em Econometrica}, 28:497--520, 1960.

\bibitem{lapointe1997}
Fran\c{c}ois-Joseph Lapointe and Guy Cucumel.
\newblock The average consensus procedure: Combining of weighted trees
  containing identical or overlapping sets of taxa.
\newblock {\em Syst. Biol.}, 46:306--312, 1997.

\bibitem{lemmon2002}
Alan~R. Lemmon and Michel~C. Milinkovitch.
\newblock The metapopulation genetic algorithm: An efficient solution for the
  problem of large phylogeny estimation.
\newblock {\em Proc. Natl. Acad. Sci. USA}, 99:10516--10521, 2002.

\bibitem{lio1998}
Pietro Li\`{o} and Nick Goldman.
\newblock Models of molecular evolution and phylogeny.
\newblock {\em Genome Res.}, 8:1233--1244, 1998.

\bibitem{lockhart2001}
Peter~J. Lockhart, Patricia~A. McLenachan, David Havell, David Glenny, Daniel
  Huson, and Uwe Jensen.
\newblock Phylogeny, radiation, and transoceanic dispersal of new zealand
  alpine buttercups: Molecular evidence under split decomposition.
\newblock {\em Ann. Mo. Bot. Gard.}, 88:458--477, 2001.

\bibitem{maddison1992a}
David~R. Maddison, Maryellen Ruvolo, and David~L. Swofford.
\newblock Geographic origins of human mitochondrial {DNA}: phylogenetic
  evidence from control region sequences.
\newblock {\em Syst. Biol.}, 41:111--124, 1992.

\bibitem{maddison1984}
Wayne~P. Maddison, Michael~J. Donoghue, and David~R. Maddison.
\newblock Outgroup analysis and parsimony.
\newblock {\em Syst. Zool.}, 33:83--103, 2005.

\bibitem{makarenkov2001a}
Vladimir Makarenko.
\newblock T-rex: reconstructing and visualizing phylogenetic trees and
  reticulation networks.
\newblock {\em Bioinformatics}, 17:664--668, 2001.

\bibitem{margush1981}
Tim Margush and Fred~R. McMorris.
\newblock Consensus n-trees.
\newblock {\em Bull. Math. Biol.}, 43:239--244, 1981.

\bibitem{martin1999}
William Martin.
\newblock Mosaic bacterial chromosomes: a challenge en route to a tree of
  genomes.
\newblock {\em BioEssays}, 21:99--104, 1999.

\bibitem{massingham2005}
Tim Massingham and Nick Goldman.
\newblock Detecting amino acid sites under positive selection and purifying
  selection.
\newblock {\em Genetics}, 169:1753--1762, 2005.

\bibitem{minh2005}
Bui~Quang Minh, Le~Sy Vinh, Heiko~A. Schmidt, and Arndt von Haeseler.
\newblock {IQPNNI}: Parallelization and improvements.
\newblock In {\em Proceedings of the 1st Young Vietnamese Scientists Meeting
  (YVSM 2005)}, page to be published, Nha Trang, June 2005.

\bibitem{minh2005a}
Bui~Quang Minh, Le~Sy Vinh, Arndt von Haeseler, and Heiko~A. Schmidt.
\newblock {pIQPNNI} -- parallel reconstruction of large maximum likelihood
  phylogenies.
\newblock {\em Bioinformatics}, 21:Advance Access published, 2005.

\bibitem{miyamoto1995}
Michael~M. Miyamoto and Walter~M. Fitch.
\newblock Testing species phylogenies and phylogenetic methods with congruence.
\newblock {\em Syst. Biol.}, 44:64--76, 1995.

\bibitem{nieselt2001}
Kay Nieselt-Struwe and Arndt von Haeseler.
\newblock Quartet-mapping, a generalization of the likelihood-mapping
  procedure.
\newblock {\em Mol. Biol. Evol.}, 18:1204--1219, 2001.

\bibitem{nixon1993}
Kevin~C. Nixon and James~M. Carpenter.
\newblock On outgroups.
\newblock {\em Cladistics}, 9:413--426, 1993.

\bibitem{olsen1994}
Gary~J. Olsen, Hideo Matsuda, Ray Hagstrom, and Ross Overbeek.
\newblock {fastDNAml}: A tool for construction of phylogenetic trees of {DNA}
  sequences using maximum likelihood.
\newblock {\em Comput. Appl. Biosci.}, 10:41--48, 1994.

\bibitem{page2002d}
Roderic D.~M. Page.
\newblock Modified mincut supertrees.
\newblock In {\em Proceedings of the 2nd Workshop on Algorithms in
  Bioinformatics (WABI 2002)}, volume 2452 of {\em Lecture Notes in Computer
  Science}, pages 537--551, New York, 2002. Springer.

\bibitem{paraskevis2005}
Dimitris Paraskevis, Koen Deforche, Philippe Lemey, Gkikas Magiorkinis, Angelos
  Hatzakis, and Anne-Mieke Vandamme.
\newblock {SlidingBayes}: exploring recombination using a sliding window
  approach based on {Bayesian} phylogenetic inference.
\newblock {\em Bioinformatics}, 21:1274--1275, 2005.

\bibitem{patterson1988}
Colin Patterson.
\newblock Homology in classical and molecular biology.
\newblock {\em Mol. Biol. Evol.}, 5:603--625, 1988.

\bibitem{piaggio2004}
Raul Piaggio-Talice, Gordon Burleigh, and Oliver Eulenstein.
\newblock Quartet supertrees.
\newblock In Olaf R.~P. Bininda-Emonds, editor, {\em Phylogenetic Supertrees:
  Combining Information to Reveal the Tree of Life}, pages 173--191. Kluwer
  Academic, Dordrecht, 2004.

\bibitem{posada2001f}
David Posada and Keith~A. Crandall.
\newblock Intraspecific gene genealogies: trees grafting into networks.
\newblock {\em TREE}, 16:37--45, 2001.

\bibitem{posada2002a}
David Posada and Keith~A. Crandall.
\newblock The effect of recombination on the accuracy of phylogeny estimation.
\newblock {\em J. Mol. Evol.}, 54:396--402, 2002.

\bibitem{purvis1995}
Andy Purvis.
\newblock A composite estimate of primate phylogeny.
\newblock {\em Philos. Trans. R. Soc. Lond. Ser. B}, 348:405--421, 1995.

\bibitem{ragan1992}
Mark~A. Ragan.
\newblock Phylogenetic inference based on matrix representation of trees.
\newblock {\em Mol. Phylogenet. Evol.}, 1:53--58, 1992.

\bibitem{roberts2003}
David~L. Roberts and Andrew~R. Solow.
\newblock Flightless birds: When did the dodo become extinct?
\newblock {\em Nature}, 426:245, 2003.

\bibitem{robinson2001}
Marc Robinson-Rechavi and Dan Graur.
\newblock Usage optimization of unevenly sampled data through the combination
  of quartet trees: An eutherian draft phylogeny based on 640 nuclear and
  mitochondrial proteins.
\newblock {\em Isr. J. Zool.}, 47:259--270, 2001.

\bibitem{rohlf1982}
F.~James Rohlf.
\newblock Consensus indices for comparing classifications.
\newblock {\em Math. Biosci.}, 59:131--144, 1982.

\bibitem{saitou1987}
Naruya Saitou and Masatoshi Nei.
\newblock The neighbor--joining method: A new method for reconstructing
  phylogenetic trees.
\newblock {\em Mol. Biol. Evol.}, 4:406--425, 1987.

\bibitem{salemi2003}
Marco Salemi and Anne-Mieke Vandamme, editors.
\newblock {\em The Phylogenetic Handbook: A Practical Approach to {DNA} and
  Protein Phylogeny}.
\newblock Cambridge University Press, Cambridge, UK, 2003.
\newblock to appear.

\bibitem{salminen1995}
Mika~O. Salminen, Jean~K. Carr, Donald~S. Burke, and Francine~E. McCutchan.
\newblock Genotyping of {HIV-1}.
\newblock In {\em Human Retroviruses and AIDS Compendium}, pages III--30 --
  III--34. Los Alamos Natl. Lab., USA, 1995.

\bibitem{sanderson1998}
Michael~J. Sanderson, Andy Purvis, and Chris Henze.
\newblock Phylogenetic supertrees: Assembling the trees of life.
\newblock {\em TREE}, 13:105--109, 1998.

\bibitem{sanderson2002a}
Michael~J. Sanderson and H.~Bradley Shaffer.
\newblock Troubleshooting molecular phylogenetic analyses.
\newblock {\em Annu. Rev. Ecol. Syst.}, 33:49--72, 2002.

\bibitem{sankoff1975}
David Sankoff.
\newblock Minimal mutation trees of sequences.
\newblock {\em SIAM J. Appl. Math.}, 28:35--42, 1975.

\bibitem{sankoff1983}
David Sankoff and Joseph~B. Kruskal, editors.
\newblock {\em Time warps, string edits, and macromolecules}.
\newblock Addison--Wesley Publishing Company, Reading, Massachusetts, 1983.

\bibitem{satta2000}
Yoko Satta, Jan Klein, and Naoyuki Takahata.
\newblock {DNA} archives and our nearest relative: The trichotomy problem
  revisited.
\newblock {\em Mol. Phylogenet. Evol.}, 32:259--275, 2000.

\bibitem{schmidt2003b}
Heiko~A. Schmidt.
\newblock {\em Phylogenetic Trees from Large Datasets}.
\newblock PhD thesis, Universit{\"a}t D{\"u}sseldorf, 2003.

\bibitem{schmidt2003a}
Heiko~A. Schmidt, Ekkehard Petzold, Martin Vingron, and Arndt von Haeseler.
\newblock Molecular phylogenetics: Parallelized parameter estimation and
  quartet puzzling.
\newblock {\em J. Parallel Distrib. Comput.}, 63:719--727, 2003.

\bibitem{schmidt2002}
Heiko~A. Schmidt, Korbinian Strimmer, Martin Vingron, and Arndt von Haeseler.
\newblock {TREE-PUZZLE}: Maximum likelihood phylogenetic analysis using
  quartets and parallel computing.
\newblock {\em Bioinformatics}, 18:502--504, 2002.

\bibitem{schuh2000}
Randall~T. Schuh, editor.
\newblock {\em Biological Systematics: Principles and Applications}.
\newblock Cornell University Press, Ithaca, NY, USA, 2000.

\bibitem{semple2000}
Charles Semple and Mike Steel.
\newblock A supertree method for rooted trees.
\newblock {\em Discr. Appl. Math.}, 105:147--158, 2000.

\bibitem{semple2003}
Charles Semple and Mike Steel.
\newblock {\em Phylogenetics}, volume~24 of {\em Oxford Lecture Series in
  Mathematics and Its Applications}.
\newblock Oxford University Press, Oxford, UK, 2003.

\bibitem{sheldon1987}
Frederick~H. Sheldon.
\newblock Phylogeny of herons estimated from {DNA-DNA} hybridization data.
\newblock {\em Auk}, 104:97--108, 1987.

\bibitem{smith1994}
Andrew~B. Smith.
\newblock Rooting molecular trees: problems and strategies.
\newblock {\em Biol. J. Linn. Soc.}, 51:279--292, 1994.

\bibitem{stamatakis2005}
Alexandros~P. Stamatakis, Thomas Ludwig, and Harald Meier.
\newblock {RAxML-III}: a fast program for maximum likelihood-based inference of
  large phylogenetic trees.
\newblock {\em Bioinformatics}, 21:456--463, 2005.

\bibitem{stewart2001}
Craig~A. Stewart, David Hart, Donald~K. Berry, Gary~J. Olsen, Eric~A. Wernert,
  and William Fischer.
\newblock Parallel implementation and performance of {fastDNAml} - a program
  for maximum likelihood phylogenetic inference.
\newblock In {\em Proceedings of the International Conference on High
  Performance Computing and Communications - SC2001}, pages 191--201, November
  2001.

\bibitem{strimmer2000}
Korbinian Strimmer and Vincent Moulton.
\newblock Likelihood analysis of phylogenetic networks using directed graphical
  models.
\newblock {\em Mol. Biol. Evol.}, 17:875--881, 2000.

\bibitem{strimmer1996}
Korbinian Strimmer and Arndt von Haeseler.
\newblock Quartet puzzling: A quartet maximum--likelihood method for
  reconstructing tree topologies.
\newblock {\em Mol. Biol. Evol.}, 13:964--969, 1996.

\bibitem{strimmer1997a}
Korbinian Strimmer and Arndt von Haeseler.
\newblock Likelihood--mapping: A simple method to visualize phylogenetic
  content of a sequence alignment.
\newblock {\em Proc. Natl. Acad. Sci. USA}, 94:6815--6819, 1997.

\bibitem{strimmer2001}
Korbinian Strimmer, Carsten Wiuf, and Vincent Moulton.
\newblock Recombination analysis using directed graphical models.
\newblock {\em Mol. Biol. Evol.}, 18:97--99, 2001.

\bibitem{swofford1996}
David~L. Swofford, Gary~J. Olsen, Peter~J. Waddell, and David~M. Hillis.
\newblock Phylogeny reconstruction.
\newblock In David~M. Hillis, Craig Moritz, and Barbara~K. Mable, editors, {\em
  Molecular Systematics}, pages 407--514. Sinauer Associates, Sunderland,
  Massachusetts, 2 edition, 1996.

\bibitem{tamura1993}
Koichiro Tamura and Masatoshi Nei.
\newblock Estimation of the number of nucleotide substitutions in the control
  region of mitochondrial {DNA} in humans and chimpanzees.
\newblock {\em Mol. Biol. Evol.}, 10:512--526, 1993.

\bibitem{tarrio2001}
Rosa Tarr{\'i}o, Francisco Rodr{\'i}guez-Trelles, and Francisco~J. Ayala.
\newblock Shared nucleotide composition biases among species and their impact
  on phylogenetic reconstructions of the drosophilidae.
\newblock {\em Mol. Biol. Evol.}, 18:1464--1473, 2001.

\bibitem{vinh2005}
Le~Sy Vinh, Heiko~A. Schmidt, and Arndt von Haeseler.
\newblock {PhyNav}: A novel approach to reconstruct large phylogenies.
\newblock In Claus Weihs and Wolfgang Gaul, editors, {\em Classification - The
  Ubiquitous Challenge}, Studies in Classification, Data Analysis, and
  Knowledge Organization, pages 386--393. Springer, Heidelberg, 2005.

\bibitem{vinh2004}
Le~Sy Vinh and Arndt von Haeseler.
\newblock {IQPNNI}: Moving fast through tree space and stopping in time.
\newblock {\em Mol. Biol. Evol.}, 21:1565--1571, 2004.

\bibitem{haeseler1993}
Arndt von Haeseler and Gary~A. Churchill.
\newblock Network models for sequence evolution.
\newblock {\em J. Mol. Evol.}, 37:77--85, 1993.

\bibitem{wheeler1990}
Ward~C. Wheeler.
\newblock Nucleic acid sequence phylogeny and random outgroups.
\newblock {\em Cladistics}, 6:363--368, 2005.

\bibitem{wilkinson2004}
Mark Wilkinson, Joseph~L. Thorley, Davide Pisani, Fran\c{c}ois-Joseph Lapointe,
  and James~O. McInerney.
\newblock Some desiderata for liberal supertrees.
\newblock In Olaf R.~P. Bininda-Emonds, editor, {\em Phylogenetic Supertrees:
  Combining Information to Reveal the Tree of Life}, pages 227--246. Kluwer
  Academic, Dordrecht, The Netherlands, 2004.

\bibitem{wolf2000}
Marty~J. Wolf, Simon Easteal, Margaret Kahn, Brendan~D. McKay, and Lars~S.
  Jermiin.
\newblock {TrExML}: a maximum-likelihood approach for extensive tree-space
  exploration.
\newblock {\em Bioinformatics}, 16:383--394, 2000.

\bibitem{yang1998a}
Ziheng Yang and Rasmus Nielsen.
\newblock Synonymous and nonsynonymous rate variation in nuclear genes of
  mammals.
\newblock {\em J. Mol. Evol.}, 46:409--418, 1998.

\bibitem{yang2002}
Ziheng Yang and Willie~J. Swanson.
\newblock Codon-substitution models to detect adaptive evolution that account
  for heterogeneous selective pressures among site classes.
\newblock {\em Mol. Biol. Evol.}, 19:49--57, 2002.

\bibitem{zhou2004a}
Bing~Bing Zhou, Michael Till, Albert~Y. Zomaya, and Lars~S. Jermiin.
\newblock Parallel implementation of maximum likelihood methods for
  phylogenetic analysis.
\newblock In {\em Proceedings of the 18th International Parallel and
  Distributed Processing Symposium (IPDPS2004)}, pages 237a 1--6, Los Alamitos,
  USA, 2004. IEEE.

\bibitem{zillig1991}
Wolfgang Zillig.
\newblock Comparative biochemistry of {Archaea} and {Bacteria}.
\newblock {\em Curr. Opin. Genet. Dev.}, 1:544--551, 1991.

\end{thebibliography}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\printindex
%\listoftables
%
%\listoffigures
\end{document}
% \begin{figure}[t!] \caption{debug} \label{fig:debug} \end{figure}
