\documentclass[fleqn,a4paper]{vch-book}
% ($Id: phylo-chapter.tex,v 1.66 2005/12/09 12:28:42 hschmidt Exp $)
\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{WileyVCH}
\bibliographystyle{molcellbiol}
%\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}
\RB{Please change the title of the first subsection and expand its content.

One should start with a few lines on the importance of reconstructing phylogenies and what wealth of information comes from the phylogenies. Phylogenies are the basis for comparative genomics (reference to Chapter 38, they provide major information for protein structure prediction (Chapter 11),analyzing protein function (Chapter 33), analyzing the evolution of pathogens (Chapter 42), etc. (reference to other chapters in the book).

Phylogenies have to be accurate because.....

In this context one can discuss the role of the tree model of evolution and make a forward pointer to the latter sections of the chapter that go beyond the tree model.

Before you then become tree-like and formal in the following sections, please complete this basic biological discussion.}

\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}
\subsection{Reconstructing a tree from its leaves}
\RB{New section  number here. First a few introductory remarks on trees, maybe moved from the section above. Then become formal.\textbf{done so. Moved things (ingo)}}
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
original dataset. The correspondence to a tree is apparent, and it is therefore of little
surprise that trees play the key role in phylogenetic research. 
The dominant role of trees in the area of phylogeny reconstruction 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. 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 of reconstructing 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.
Such a congruency is interpreted as a result of shared descent \cite{hennig1966}. 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
(Section~\ref{sec:phylosignal}).
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-tl} we will take for granted that
this postulation is met.
\subsubsection{The problem of character inconsistencies}\label{sec:character-inconsistency}
Due to the ever increasing amount of phylogenetic informative data, tree reconstruction is nowadays
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 supported significantly 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
(cf. sections \ref{subsec:distance} and \ref{subsec:likelihood}) 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 various causes. Among the most frequently
stated are processes like the random sorting of
ancestral polymorphisms during subsequent speciation events, e.g., \cite{satta2000}, and horizontal gene transfer 
\cite{delwiche1996,doolittle1999a,kurland2003} (Figure \ref{fig:incongruent-trees})\xxx\RB{\textbf{figure added. Read caption carefully (ingo)}}.
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 seems
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 (cf. Section~\ref{sec:networks}).
\begin{figure}\centering
	\fbox{\includegraphics[width=.48\textwidth]{images/incongruent-tree}}
\caption{Trees reconstructed from individual characters can differ. a) The
phylogenetic history of the character (bold line) follows that of the species. b) The random sorting
of ancestral polymorphisms at subsequent speciation events can result in phylogenies that are
incongruent to the species tree. The probability for a polymorphism to survive decreases exponentially
with time. Thus, incongruent trees due to ancestral polymorphisms are an
issue only for species whose speciation events occurred in close temporal succession. c) Horizontal gene transfer, that is the
lateral transfer of individual genes or DNA sequences between species comprises a further possibility
to explain why individual characters can own their distinct evolutionary history.}
\label{fig:incongruent-trees}
\end{figure}
\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 effects of evolution. Therefore, the
field of phylogeny reconstruction was dominated by the analysis of morphological
characters for a long time. However, with the expansion of molecular biology the focus has shifted considerably.
Initially, immunological and electrophoretic analysis of structural and electrical properties of
\RB{what features of the proteins are compared here? \textbf{added 'immunological and electrophoretic analysis of structural and electrical properties of proteins' (ingo)}}
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. As time proceeded, the presence and absence or linear
order of regulatory elements and genes (see also chapter 8) and recently, even expression
data \cite{khaitovich2005} have been employed for phylogenetic inference. However, the most
dominant role is still 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 
\RB{Why eventually? \textbf{Because this is a time dependent process and many sequences found in different species
have not yet diverged (ingo)!}}
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 has now become feasible. 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 for easy adaption of the dataset to the evolutionary
time scale for which phylogenetic resolution is required.

%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Modeling DNA sequence evolution}\label{sec:modeling}
\RB{Please formulate this paragraph more carefully. Motivate explicitly, why you are using a Poisson process. \textbf{I tried to motivate it. }}
\RB{Is this a time point or a time interval. Do you really want to count several substitutions at the
same time instant? \textbf{Time is not a time point, to my opinion. However, I tried to use intervals where applicable (ingo)}}
\RB{up to time t? From time 0 to time t?}
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 DNA sequence evolution \cite{lio1998}. Processes in which
independent events occur randomly in time, such as the decay of radioactive material, have been successfully
described by the so-called Poisson process, a simple, one-parameter
probability model. Making some basic assumptions concerning the independence of individual
substitutions and the uniformity of the substitution process in time, it is straightforward 
to apply the Poisson process for counting the number of substitutions $X(t)$ that occurred in a DNA
sequence during a time interval $[0,t]$. Let $\mu$ be the rate with which a nucleotide substitution occurs per unit
of time. Furthermore, let $P_i(t)$ denote the probability that exactly $i$ substitutions occurred in the time interval $[0,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)\RB{Is confounded a technical term? \textbf{I removed it (ingo)}} 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}
Compared to the probability functions based on the Poisson process,
\RB{under? of? It does not look that way if one inspects eq 4.1. \textbf{rephrased. ok? (ingo)}}
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 model \RB{noun missing. \textbf{'model' added (ingo)}}
(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-Cantor model (JC69, \cite{jukes1969}). 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 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 an 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 continuous probability distribution, the $\Gamma$-distribution 
\RB{Explain what this is. \textbf{added a sub-clause}} 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 (Figure~\ref{fig:gamma}). For $\alpha > 1$, 
\RB{Can you provide a figure? \textbf{done so. (ingo)}}
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.
\begin{figure}
	\fbox{\includegraphics[width=.48\textwidth]{images/gamma-pdf}}
\caption{Probability density functions of the $\Gamma$-distribution for different values of the shape parameter $\alpha$.}
\label{fig:gamma}
\end{figure}

%
\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 sequence has no effect on the encoded protein -- are invisible to selective forces acting on the
protein sequence. As a result, the ratio of nonsynonymous and synonymous substitution rates ($\omega=d_N/d_S$)
will vary among sites in a DNA sequence, with $\omega=1$ indicating no selection, $\omega<1$ representing 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} (cf. 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 substitution rate ratio $\omega$ to
each codon position would lead to a vast over-parameterization of the model. Therefore, either a set of predefined $\omega$-values 
\RB{I do not know what you mean by this. \textbf{I tried to clarify that (ingo)}}
or statistical distributions -- both discrete and continuous -- are used to account
for varying $\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}\label{sec:phylosignal}
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 aligned 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. Chapter 3 deals in detail with methods of constructing sequence alignments. 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 for finding the tree that reflects best the evolutionary relationships of the data. We will
explain four principles for tree generation.
\subsection{The parsimony principle of evolution}
\RB{An illustrative example comparing the four methods would be of great help.}
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 (Figure~\ref{fig:parsimony}). Usually only a fraction of the differences in a sequence alignment are phylogenetically informative. For instance, position 8 in the alignment in Figure~\ref{fig:parsimony} supports a tree grouping sequences $W$ and $X$, and $Y$ and $Z$, respectively. In contrast, sequence positions 1 and 3 are informative with respect to the tree topology, since two substitutions are required independent from what tree topology is chosen. Thus, phylogenetic inference based on maximum parsimony requires initially the identification of the phylogenetic informative positions. The tree that is supported by the largest number of  informative sites is then the maximum parsimony tree. Note however, that no unique solution is guaranteed since more than one most parsimonious tree might exist.
%%
\begin{figure}
	\fbox{\includegraphics[width=.48\textwidth]{images/parsimony_example}}
\caption{Maximum parsimony tree reconstruction from an alignment of four DNA sequences. For the alignment columns labeled with a '*' all three possible unrooted tree topologies are shown, respectively. Labels at the leafs denote the taxon and the represented nucleotide. Nucleotides at the inner nodes represent one of several possible alternative reconstructions. Nucleotide substitution events are represented by a black dot in the tree. The only phylogenetic informative site in the alignment is position 8 since tree 1 requires only a single substitution compared to trees 2 and 3 both of which require 2 substitutions.}
\label{fig:parsimony}
\end{figure}

\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 present the generalized idea of parsimony \cite{sankoff1975,sankoff1983-tl}
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 called the length of the tree $\tau$, 
\RB{It would be more illiustrative to define this in terms of sequences and sequence positions. \textbf{done so (ingo)}}
$B$ is the total number of branches in the tree,
$L$ is the number of nucleotide positions analyzed (alignment length), $k'$ and $k''$ are the two nodes connected by branch
\RB{you mean the two endpoints of the branch? \textbf{changed to 'nodes connected by branch k' (ingo)}}
$k$ displaying the nucleotides $x_{k'j}$ and $x_{k''j}$. These can be either the observed nucleotides present in the alignment or, in the case of internal nodes, the optimal nucleotide
assignments. Finally, $\diff(x,y)$ is the cost of the transformation from nucleotide $x$ to
state $y$, and $\omega_{j}$ allows for assigning a weight to each nucleotide position 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 sequences share a certain nucleotide
by descent. However, this approximates the true evolutionary events in a realistic way
only if the overall amount of sequence changes is low. Thus, multiple changes of the same nucleotide position in
the same taxon or parallel independent changes of the same nucleotide position 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}\label{subsec:distance}
\RB{\textbf{I have rephrased the entire subsection (ingo)}}
In contrast to parsimony methods with their biologically motivated approach to tree reconstruction,
distance-based methods choose a mathematical route to accomplish this task \cite{felsenstein1984}. A phylogenetic tree is reconstructed for a set of taxa from their pairwise evolutionary distances. To this end, a distance matrix $D$ is calculated for the dataset from all possible pairwise
sequence comparisons first. Entry $D_{ij}$ of this matrix represents 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 for correcting
the observed distance for the expected number of 'unseen' changes (cf. Section~\ref{sec:modeling}). Once the distance matrix is computed, various methods exist for constructing a phylogenetic tree from it.
The basic principle, however, is the same for all methods: Guided by the pairwise evolutionary distances of their DNA sequences, the taxa are grouped in a step-wise fashion, such that each step reduces the number of taxa by 1. Subsequent to each grouping, the pairwise distances are recalculated for the reduced taxon set. This procedure is repeated until a fully resolved tree is obtained. The most fundamental problem of distance-based tree reconstruction is to decide which pair of taxa should be joined first and it is here where the individual methods differ.

\paragraph{UPGMA}
The \textbf{U}nweighted \textbf{p}air \textbf{G}roup \textbf{M}ethod using \textbf{A}rithmetic means groups those two taxa first whose evolutionary distance is the shortest among all pairs of taxa. Consider a taxon set $A$, $B$, $C$, and $D$ with the evolutionary distances shown in Figure~\ref(fig:upgma-tree)a. It is easy to see that the first two taxa to be joined are $A$ and $B$. Subsequently, $A$ and $B$ are treated as a single compound taxon $AB$ and the pairwise distances to the two remaining taxa $C$ and $D$ are computed. $d_{(AB)C}$ is calculated as the arithmetic mean of the individual distances $d_{AC}$ and $d_{BC}$, thus $d_{(AB)C}=(7+8)/2=7.5$ in our example. Likewise, $d_{(AB)D}$ is $(12+14)/2=13$.  From this it is obvious that $AB$ and $C$ are the next taxa to group. Thus we obtain $((AB)C)$ and $D$ as the two remaining taxa with $d_{((AB)C)D}=(12+14+11)/3=12.3$. Joining $D$ to $((AB)C)$ results then in the full tree $(((AB)C)D)$ (Figure~\ref{fig:upgma-tree}b). We have now determined the branching order of the tree connecting the four taxa. In order to obtain the corresponding branch lengths, UPGMA utilizes the concept of a molecular clock  and places the node connecting two taxa $A$ and $B$ at $d_{AB}/2$. This requires that the evolutionary distances between the individual taxa are \textit{ultrametric}, i.e., they have to fulfill 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 are equally distant from their shared ancestor. For our example, this results in the branch lengths shown in Figure~\ref{fig:upgma-tree}b. Note that the assumption of the molecular clock results in a rooted tree.
%%
\begin{figure}
	\fbox{\includegraphics[width=.48\textwidth]{images/distance-tree}}
\caption{Reconstruction of a phylogenetic tree with the UPGMA method. From the matrix of pair-wise sequence distances (a) the phylogenetic tree shown in (b) is reconstructed. Numbers in (b) represent the branch lengths inferred under the assumption of a molecular clock.}
\label{fig:upgma-tree}
\end{figure}
%%

Unfortunately,  the criterion of ultrametric distances is frequently not met by the data due to individual lineages evolving with different rates. Under such circumstances UPGMA may give an erroneous tree topology.  To arrive at a correct tree topology nevertheless, the \textit{transformed distance method} can be used to make corrections for unequal rates of evolution among the lineages under study\xxx\RB{\textbf{cite klotz et al. pnas 1979}}. One taxon in the dataset is identified as outgroup (cf. Section~\ref{subsec:rooting}), e.g., taxon $D$ in Figure~\ref{tab:distance}. 
\RB{label tab:distance missing - is that fig:upgma-tree??? (Heiko)}
The distance $d_{ij}$ between any two of the remaining taxa is transformed by the following equation:
\begin{equation}
d'_{ij} = [(d_{ij}-d_{iD}-d{jD}) / 2] +\bar{d}_D
\end{equation}
where $i,j\in\{A,B,D\}$ and $\bar{d}_D=(d_{AD} + d_{BD}+d_{CD})/3$. 
The such modified distance matrix can then be used to infer the tree topology using UPGMA.

\paragraph{Neighbors-Relation Methods}
In contrast to the UPGMA method and its derivatives, the concept of phylogeny reconstruction from a distance matrix based on the the identification of \textit{neighbors} does not require the assumption of a molecular clock. Two taxa are called neighbors in an unrooted tree if they are connected through a single internal node. For instance the taxa $A$ and $B$ in Figure~\ref{fig:quartet-tree}  are neighbors, while the taxa $A$ and $C$ or $B$ and $D$ are not. Under the assumption that the evolutionary distances between a set of taxa are \textit{tree-additive} -- that is, the evolutionary distance between any two taxa is equal to the total length of the branches connecting the two sequences
in the phylogenetic tree -- the four-point metric condition \cite{zaretskii1965,buneman1971}\RB{\textbf{zaretskii1965 added - first name missing in BibTeX entry}}
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}
Conversely, if the phylogenetic relationships for a set of four taxa is not known, equation \ref{eqt:fourpoint} can be used to identify the respective neighbors from a set of four taxa. Once the two pairs of neighbors are determined, so is the topology of the tree. To reconstruct a tree from a set of more than four taxa, the topology of all possible quartets is determined first and the neighbors in each quartet are assigned a score of 1\cite{sattath1977}\RB{\textbf{cite sattath and tversky, Additive similarity trees Psychometrika 42:319-345 (ingo) - done}}. The taxon pair with the highest score is joined first. The distance matrix is then recomputed as described for the UPGMA method, and the procedure is repeated to select the second pair of neighbors. This cycle is continued until only three (compound) taxa remain, for which only a single unrooted tree topology exists.
%%
\begin{figure}
	\fbox{\includegraphics[width=.48\textwidth]{images/quartet}}
\caption{An unrooted quartet-tree.}
\label{fig:quartet-tree}
\end{figure}
%%
\paragraph{Neighbor-Joining Method} The most widely used method based on the neighbors-relation concept is the neighbor-joining method by Saitou and Nei \cite{saitou1987}. Instead of using the scoring approach described above, the neighbor-joining method sequentially identify those taxa as neighbors whose joining minimizes the total length of the resulting tree, that is the sum of the lengths of all branches (minimum-evolution criterion)\cite{cavalli1967a}\RB{\textbf{cite cavalli-sforza and edwards 1967} - which one? Evolution or Am. J. Hum. Genet.? I added the former (Heiko)}. To this end, the set of $N$ taxa are arranged in a star-like tree first. Subsequently, any two taxa $1$, $2$ are tentatively joined as neighbors and the length of the resulting tree is estimated from the pairwise distances $d_{ij}$ as:
\begin{equation}
S_{12}=\frac{1}{2(N-2)}\sum^{N}_{k=3}(d_{1k}+d_{2k})+\frac{1}{2}d_{12}+\frac{1}{N-2}\sum_{3\leq i \leq j \leq N}d_{ij}\label{eqt:treelength}
\end{equation}
This is repeated for all possible pairs of taxa and those two are joined as neighbors that minimize equation \ref{eqt:treelength}. The cycle of calculating a new distance matrix and identifying the next neighbors to join is continued until the initially star-like tree is fully resolved (cf. Section~\ref{STARDEC}).

\paragraph{Estimation of branch lengths}
So far we have mainly focused on the question how a tree topology is reconstructed by the use of a pair-wise distance matrix. Next, we will outline two principles that are used to estimate the branch length of the inferred tree. The method proposed by Fitch and Margoliash\cite{fitch1967}\RB{\textbf{cite Fitch and Margoliash 1967} - done} is exemplified best by the use of an unrooted tree-taxon tree (Figure~\ref{fig:triplet-tree}). The distance between any two taxa in the tree is the sum of the branches along the unique path connecting the two taxa. Thus, $d_{AB}=x+y$, $d_{AC}=x+z$, and $d_{BC}=y+z$. From this, the following equations can be derived for calculating the branch lengths from the pair-wise distances:
\begin{equation}
\begin{aligned}
x=(d_{AB}+d_{AC}-d_{BC}) / 2\\
y=(d_{AB} + d_{BC} - d_{AC})/2\\
z=(d_{AC}+d_{BC}-d_{AB})/2
\end{aligned}
\end{equation}
Note that this can result in the estimation of negative branch lengths. Since there is no biological representation of negative branch lengths, such estimates should be set to a value of 0.
Extending this procedure to a $N$-taxon set is straightforward: $N-2$ taxa are grouped in a single compound taxon, and thus the problem is reduced to the three-taxon case. The distance of a taxon $i$ to the compound taxon $C$ is calculated as
\begin{equation}
d_{iC}=\frac{1}{N-2}\sum^{N-2}_{j=1}d_{ij}
\end{equation} 
%%
\begin{figure}
	\fbox{\includegraphics[width=.48\textwidth]{images/triplet}}
\caption{Unrooted tree connecting three taxa. $x$, $y$, $z$ represent the branch lengths.}
\label{fig:triplet-tree}
\end{figure}
%%
As an alternative to the Fitch-Margoliash method, branch lengths can be estimated such that the discrepancy between the evolutionary distances $d_{ij}$ of any taxon pair $ij$ in the tree and the corresponding entries in the distance matrix $D$ is minimized. The \textit{least-squares method} provides such a measure for the goodness of fit of the tree and its branch lengths to the data. 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 along the unique path connecting sequences $i$ and
$j$. Once the tree topology is known, the branch lengths can be adjusted such that equation \ref{EQTLSTREE} is minimized.
%
\subsection{The criterion of likelihood}\label{subsec: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.
Those 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 for the incorporation
of any model of biological sequence evolution into the tree reconstruction process. In this way, 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}
\RB{Here is the point where you can bring in Bayesian methods. \textbf{below ML we have added a Section~about bayes (heiko)}}
 We have described in Section~\ref{sec:modeling} 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 ($A_s$) in a column $s$ in a set of $n$ aligned DNA
sequences, e.g., the pattern $CCTC$ at position 1 of the alignment shown in Figure~\ref{fig:parsimony}. This probability depends on the model of DNA sequence evolution and on the tree
relating the $n$ nucleotides in the alignment column: $P(A_s|\tau, M, \theta)$. \RB{Are your presenting this now?  What parts of it are you presenting? \textbf{I moved the Felsenstein-citation and the efficient algorithm down to the position where we talk about efficient ways to obtain ML branch lengths when the tree is known (ingo)}}
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 then
 \begin{equation}
 P(A|\tau, M,\theta) = \prod_{s=1}^LP(A_s|\tau, M, \theta).
 \end{equation}
 %To avoid underflow errors during the calculation (probabilities are always $\leq$1) the
 To avoid numerical problems caused by underflows and rounding errors during the calculation the
\RB{I do not understand the relevance of the text in parens - \xxx my suggestion - Heiko}
likelihood of the data is usually calculated in log-scale, such that
 \begin{equation}
 \log[P(A|\tau, M,\theta)] = \sum_{s=1}^L \log[P(A_s|\tau, M, \theta)].
 \label{MLEQUAT}
 \end{equation}
 This equation facilitates a computation of the likelihood of an alignment, if we know 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, e.g., \cite{felsenstein1981}. 
, it is both a computationally
\RB{TL: Here is where the efficiency of the approach comes in, right?  You are not really commenting concretely on this. Why is it efficient?  How did Felsenstein do it? - (Heiko: F81 introduced the peeling alg. to avoid multiple computations of the same parts!) \textbf{Ich denke, dass ein Ausweiten dieses Themas wirklich zu weit fuehrt. (ingo)} - stimmt! Ich wollte nur TLs Frage beantworten, falls das doch rein sollte ;-)}
as well as intellectually demanding problem to obtain an optimal tree topology. Section \ref{opttree}
deals in detail with this problem.
%
\subsection{Bayesian statistics in phylogenetic analysis}\label{subsec:bayes}
%
%The likelihood approach addresses the quality of a tree by the 
%question, what is the probability $P(D|\tau,M,\theta)$ of the analyzed 
%alignment $D$ given that the assumed evolutionary hypothesis (consisting 
%of the tree $\tau$, model $M$, and parameters $\theta$) is correct, 
%which is identical to the likelihood of the hypothesis given the data. 
%Bayesian analysis on the other hand tries to assess the probability 
%$P(\tau,M,\theta|D)$ that the evolutionary hypothesis $\tau,M,\theta$ 
%the tree is correct given the data $D$ \cite[p. 106]{ewens2001} 
%applying Bayes' Theorem
%\begin{equation}\label{eq:bayes}
%   P(\tau,M,\theta|D) = \frac{P(D|\tau,M,\theta) P(\tau,M,\theta)}{P(D)}
\RB{\textbf{New!! Arndt, please read carefully (ingo)}}
The likelihood approach outlined so far determines the quality of a tree by calculating the
probability of observing the alignment $A$ given the tree  $\tau$, the model of sequence evolution $M$, and the parameter vector $\theta$, see equation \ref{MLEQUAT}. If we consider a particular combination of $\tau$, $M$, and $\theta$ as an \textit{evolutionary hypothesis}, $H_i$, we have inferred so far $P(D|H_i)$. However, it might be interesting to address the reverse question: what is the probability that the evolutionary hypothesis $H_i$ is correct given the data $D$ \cite[p. 106]{ewens2001}, i.e., $P(H_i|D)$? 
Applying Bayes' theorem, we can calculate this posterior probability as:
\begin{equation}
P(H_i|D) = \frac{P(D|H_i)P(H_i)}{P(D)}\label{bayestheorem}
\end{equation}
Rewriting the equation for the problem of tree reconstruction we obtain
\begin{equation}
   P(\tau,M,\theta|A) = \frac{P(A|\tau,M,\theta) P(\tau,M,\theta)}{P(A)}\label{eqt:bayes}
\end{equation}
where $P(\tau, M, \theta)$ is the probability for choosing a certain tree topology, evolutionary model, and parameter vector and represents the prior belief how likely this particular $H_i$ is, and $P(A)$ is the total probability to observe the alignment $A$.

Equation \ref{eqt:bayes} can now be applied in two ways for making phylogenetic inferences from a set of DNA sequences. If one is only interested in identifying the tree that is best supported by the data, a simple optimization of equation \ref{eqt:bayes} is sufficient. For this purpose no posterior probabilities are required, and thus $P(D)$ can be neglected as it is constant for any $H_i$. Alternatively, the posterior probability for every possible realizations of $\tau$, $M$, and $\theta$ can be calculated. This identifies not only the $H_i$ that is supported best by the data, but allows also to assess how much better the support is compared to the alternative hypotheses \cite{sinsheimer1996}.\RB{textbf{add citation} - done}. However, it is easy to see that this is feasible for only a very limited number of sequences. Even if we keep $M$ and $\theta$ fix for all $H_i$, and allowing only the tree topology to vary, a set of 20 taxa would already require the evaluation of more than $10^20$ alternative hypotheses (cf. Section~\ref{opttree}). Thus, typically Markov Chain Monte Carlo (MCMC) simulations are used for inferring the posterior probabilities \cite{mau1999}.\RB{textbf{add citation} - added}

Imagine that the individual $H_i$ comprise points in a landscape and $P(H_i|D)$ corresponds to their respective (unknown) altitude. An MCMC simulation is now little more than a walk through this landscape by that visiting the individual points. This walk however is not random but guided in a way that higher points are visited more often than lower ones. Thus, when the walk is finished an altitude profile of the landscape can be generated by using the information of how often a particular point was visited. In practice, MCMC simulations work the following way: Starting from any $H_i$ the transition to a new hypothesis ($H_j$), e.g., a new tree topology, is proposed with a probability $q(H_i, H_j)$. This proposal is then subjected to an evaluation, accepting it with the probability
\begin{equation}
\min(1, \frac{P(D|H_j)P(H_j)q(H_i, H_j)}{P(D|H_i)P(H_i)q(H_j, H_i)})
\end{equation}
otherwise remaining at $H_i$. Thus, if $H_j$ is supported better by the data than $H_i$ the transition is always accepted. In the reverse case, it is still accepted with a probability that depends on how much worse the support of $H_j$ compared to $H_i$. The latter option is required to escape from local optima (cf. Section~\ref{opttree}). If the transition is accepted $H_j$ will be sampled and the chain moves on. Given now that the chain can run for a sufficiently long time, the numbers with which a particular $H_i$ has been sampled is a reflection of its posterior probability. However, in most cases it is impracticable to run the chain long enough. To reduce the bias of the Monte Carlo estimates resulting from the incomplete sampling \xxx cite[Besag and Green, 1993 J Royal Stat. Soc. Series B 55: 25-37].\xxx\RB{\textbf{add citation}}, initial sample points are generally discarded. This \textit{burn-in} procedure has the effect that the chain samples only near-optimal hypotheses.\RB{\textbf{maybe add a sentence about the grouping of hypotheses prior to analysis, but I think that goes too far.}}

%An additional advantage of Eq.~/ref{eq:bayes} is, that one can include prior
%knowledge about the occurrence of the evolutionary hypotheses via
%the prior probability $P(\tau,M,\theta)$. However, if one has no prior
%knowledge about it, it leaves the researcher with the serious problem 
%how the prior should be chosen.

Today, usually more than one Markov Chain is used whose 'temperatures' differ \cite{geyer1991a,huelsenbeck2001}.
\RB{\textbf{give reference} - done} So called 'hot' chains have a high acceptance probability of inferior transition proposals. To stay in the above picture, they are used for a more global exploration of the landscape since their affinity to areas of high altitude is low. In contrast, 'cold' chains with their low acceptance probability of inferior transition probosals \xxx are used for a thorough exploration of local areas in the landscape. \RB{transition proposals or probabilities??? (Heiko)}
Hypothesis sampling is done only from the cold chain. However, from time to time, the temperatures of the chains are switched such that the hot chain is turned into a cold chain and vice versa. 
%
\subsection{Rooting trees / molecular clock}\label{subsec:rooting}
So far we have introduced various methods of inferring the relationships between sequences (or taxa). Unfortunately, most of the methods described above lack an inherent criterion for assigning
directionality to the evolutionary process. As a consequence they are unable to identify the
root of a phylogenetic tree. To obtain a rooted tree, it is required (and possible) to add
supplementary information into the tree reconstruction procedure. 
%%%%
\begin{figure}
	\fbox{\includegraphics[width=.48\textwidth]{images/rooting}}
\caption{Two alternative principles for rooting phylogenetic trees. a) outgroup rooting. The set of taxa $A-E$ is divided into an ingroup (shaded in grey) and the outgroup, taxon $E$. The node that joins the outgroup to the ingroup represents the root of the ingroup-subtree. The root of the entire tree, that is the common ancestor of all taxa, must be located somewhere on the outgroup-branch. However its exact position remains unknown. b) distance-based rooting. $t-z$ denote the lengths of the individual branches in the tree. The root of the entire tree is identified as the midpoint of the path connecting the two taxa with the largest evolutionary distance.}
\label{fig:rooting}
\end{figure}
%%%
\paragraph{Outgroup rooting}
\RB{In general, this is section a bit intransparent. Can you help the reader with a Figure~or 2? \textbf{figure added(ingo)}}
Among the various methods for rooting a tree, it is most intuitive to divide the set of
taxa into two subgroups: a monophyletic 
\RB{What is this? \textbf{explained}}
ingroup -- a group of taxa that shares a common ancestor to the exclusion of all other taxa in the dataset -- and an outgroup, whose more distant relationship
to any member of the ingroup is either known or at least reasonable to assume (Figure~\ref{fig:rooting}a). It is then
straightforward to conclude that the node that joins the outgroup to the ingroup taxa represents
the root of the ingroup-subtree \cite{smith1994,nixon1993}. Though simple, this approach
requires some considerations. Despite their clear position outside the
ingroup, outgroup taxa should be as closely related to the ingroup taxa as possible. This will increase the probability
of reliably identifying 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 for rooting 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 for rooting a phylogenetic tree can become
a considerable problem. This is especially relevant when groups are analyzed whose
phylogenetic relationships are largely unclear. In such cases additional assumptions about
the evolutionary process are imposed that help rooting 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 can
be assigned as the root (cf. Section~\ref{subsec:distance} 'UPGMA'). In reality, however, the assumption
of a molecular clock is frequently violated. If this is neglected rooting under the clock
assumption tends to place the root in a part of the tree that is evolving with a
high 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 (Figure~\ref{fig:rooting}b). Compared to the molecular clock scenario this retains only
the postulation that the evolutionary rate has to be the same along the two most divergent
lineages in the dataset. When this criterion is met midpoint rooting identifies
the localization of the root correctly \cite{swofford1996}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Finding the optimal tree}\label{opttree}
So far we have outlined the principles to construct a phylogenetic tree from a set of aligned sequences. 
\RB{The first senetence covers all of Section 3. This sentence only applies to ML. \textbf{rephrased the first sentences}}
However, it still is unclear how to find the tree that reflects the
relationships between the taxa best. We can differentiate between two general concepts of searching the tree space
comprised by all possible tree topologies for the desired optimal tree: i) \textit{exhaustive searches},
which guarantee the identification of the optimal tree, and ii) the computationally less
demanding \textit{heuristic searches} which, however, not necessarily obtain the globally optimal tree.
\subsection{Exhaustive search methods}
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 computational challenge is limited to exploring all of tree space. To accomplish this, one starts
with the (unique) unrooted tree that connects three randomly chosen taxa from the dataset.
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 to which the new taxon can be connected \cite{felsenstein1978}. Thus,
the total number of unrooted trees for a set of $n$ taxa is:
\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 evident. Already a compilation of 20 taxa,
a dataset that is nowadays easily exceeded, requires the evaluation of over $2 \times 10^{20}$
different trees. This is -- and presumably will remain -- computationally infeasible.

Branch-and-Bound methods \cite{land1960} provide an alternative approach to finding a globally
optimal solution to the problem of tree search, however without the need of evaluating every
possible tree topology. Instead, a guided search in the tree space is performed
omitting those subspaces that cannot contain an optimal tree \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 when new taxa are added 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 by evaluating any arbitrary $n$-taxon tree. Subsequently, using a three-taxon tree as a primer we recursively reconstruct the possible $n$-taxon trees. However,
as we move along 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 which contains no tree equally good or better than the
reference tree. 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 beats the reference tree, we store the new tree as candidate and update $F_\mathit{upper}$
to the new value. A number of improvements have been added to this basic scheme, to increase the efficiency
of Branch-and-Bound methods in the tree search process \cite{hendy1982,swofford1996}. These
refinements are mainly designed as to further reduce the exploration of tree space. They include
methods for obtaining a near-optimal tree for an assessment of the initial upper bound, as well as
schemes for generating a suitable order in which the taxa are added to the subtrees. For instance, by adding divergent taxa first, the length of the initial subtrees is increased, allowing for a quicker identification of subtrees that exceed the the upper bound for the tree length.
\RB{Why is this preferable? \textbf{added one sentence (ingo)}}

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 search methods}
Heuristic methods for tree reconstruction earn a substantial speed-up in computation time by the jettison of a guaranteed globally optimal solution to the tree search problem
\RB{This is a bit too colloquial. \textbf{rephrased it (ingo)}}
With contemporary software it is possible to reconstruct trees from datasets of more
than thousand taxa, e.g., \cite{minh2005a}. Thus, nowadays
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 again be illustrated by the metaphor of exploring a landscape. A hiker aims 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. This kind of search strategy is called local search.

Applying this approach to the tree search problem, we start off with any tree and modify it in a
stepwise fashion usually accepting only such modifications that result in an improved tree according to the chosen objective function. 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 of deciding 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, tree searches based on a local search 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 getting stuck in local optima that are highly suboptimal in terms of cost.\xxx \RB{\textbf{check last phrase (ingo)}}
\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 the 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
\RB{This algorithm deserves a more exposed role in the chapter. \textbf{done (ingo)}}
algorithm \cite{saitou1987} (cf. Section~\ref{subsec:distance}), we begin with an assignment of all taxa in the dataset 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 the basis for the next step. The iteration of pairwise
joining and tree evaluation continues until the tree is fully resolved.
\RB{Optimal in what respect? We have a greedy heuristic here. \textbf{I have removed the sub-clause 'that is, an optimal binary tree is obtained' (ingo)}}
\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 taxon 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 dataset.

It is straightforward to see why both star decomposition methods as well as the stepwise insertion
procedure are prone to obtaining only locally optimal trees. Any decision concerning the position of
a taxon in the tree is fixed for the remaining part of the reconstruction procedure.
\begin{figure}
\fbox{\includegraphics[width=.8\textwidth]{images/tree-rearrangements}}
\caption{Three methods that accomplish branch swapping}

\label{BRANCHSWAPP}
\end{figure}
\paragraph{Optimization procedure and avoidance of local optima}
In order to escape from local optima, tree-rearrangement methods
exist that can override previous decisions concerning the placement of taxa in the tree. 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 is 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 require more than one rearrangement of the
\RB{What do you mean by 'more than one rearrangement apart'.  \textbf{slightly rephrased (ingo)}}
currently best tree. Currently, three alternative ways of branch swapping are in use (figure
\ref{BRANCHSWAPP}). Nearest Neighbor Interchange, the simplest approach, takes any internal
branch of the tree and swaps two of the four connected subtrees. In this way, 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 of swapping 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 of guiding the tree reconstruction procedure
out of a local optimum. However, no guarantee is given that this does not simply lead into the next
local optimum, such that the benefit is only limited. Apparently, if the branch swapping is
continued for a sufficient amount of time it becomes likely that sooner or later the global optimum will
be found. However, how shall we recognize the
globally optimal tree once we found it? And for how long should we continue the tree search?
\subsubsection{Modeling tree quality}
\RB{Please choose a less colloquial title. \textbf{done, but check! (ingo)}}
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 a concept of tree quality, as we are continuing the search. In most cases it is essentially up to the user how long the search is continued. Either a predefined number of optimization steps or a lower limit by which new trees have to improve can be used as stopping criteria. However, both criteria are arbitrary and a well-founded basis for deciding when to end the search would be desirable. 
\RB{This is significantly too colloquial. \textbf{reformulated (ingo)}}
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.,
number of iteration at which 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 based on the probability of yet finding 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 has not been 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 datasets}
The considerable ease with which DNA sequences are obtained nowadays results in ever-increasing datasets available for phylogeny reconstruction. As a consequence there is a continuing demand for increasing the capacity of tree reconstruction software.
\RB{Please be less colloquial. Besides, I do not understand what you want to say. \textbf{rephrased. (ingo)}}
The objectives for further improvements on the computational basis are quickly summarized.
i) finding in shorter time a better starting tree for subsequent optimization. 
\RB{This sentence is missing a verb. \textbf{turned into a list. (ingo)}}
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. ii) improving the algorithms for tree optimization. 
For instance, 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. iii) the utilization of alternative approaches for tree reconstruction, such as a metapopulation genetic  algorithm \cite{lemmon2002}. iv) 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
recent developments and it is not clear yet 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 optimally on different data sets. For the same reason it is impossible to provide guidelines
for when to use what program. Different programs will almost inevitably obtain different trees,
and it will always be up to the biologist's ultimate judgement which of the alternative trees is
the most plausible one. However, this general statement might be justified:
parallel computing supports a timely decision by the biologist. Therefore, many
\RB{I find this argument baroque. Is it not just that parallel codes are there because all this takes a lot of cycles? \textbf{I don't think that this is an argument. It is just a statement (ingo)}}
contemporary programs for tree reconstruction are available in a parallelized version,
e.g.  fastDNAml-based programs \cite{olsen1994,stewart2001,stamatakis2005},
TREE-PUZZLE \cite{schmidt2002},
GAML \cite{brauer2002},
MrBAYES \cite{altekar2004},
advanced stepwise addition \cite{zhou2004a}, and
IQPNNI \cite{minh2005}.
\RB{This list is a bit long for a subject that you do not even discuss. \textbf{removed some and slightly rephrased (ingo)}}
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%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, in addition, is
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 limited to the level of individual genes, in many cases.
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 extend the
amount of information, nonetheless, disjoint datasets derived from multiple genomic loci can be combined for the analysis. This intersection of phylogenetics and genomics is referred to as phylogenomics.

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

   \begin{figure}[t!]
      \centering
      \resizebox{\textwidth}{!}{
 %     \begin{tabular}{|c|p{.20\textwidth}|c|}\hline
      \begin{tabular}{|p{.14\textwidth}|p{.18\textwidth}|p{.75\textwidth}|}\hline
	   \parbox{.14\textwidth}{\centering\bf Combination level} & \parbox{.18\textwidth}{\centering\bf Combination method}    & 
					   \parbox{.75\textwidth}{~\\
					   %\includegraphics[width=.75\textwidth]%
					  % {images/combination-level}
					   \\}\\ 
					   \hline
					  % \hline
	   \parbox{.14\textwidth}{\centering early} & \parbox{.18\textwidth}{\emph{Supermatrix /
	   Total evidence}}   & 
					   \parbox{.75\textwidth}{~\\
					   \includegraphics[width=.75\textwidth]%
					   {images/combination-total_ingo}\\}\\
					    \hline
	   \parbox{.14\textwidth}{\centering late} & \parbox{.18\textwidth}{\emph{Consensus tree}}       & 
					   \parbox{.75\textwidth}{~\\
					   \includegraphics[width=.75\textwidth]%
					   {images/combination-consensus_ingo}\\}\\ 
					    \hline
   \end{tabular}}
   \caption[Levels of dataset combination - complete data]
           {Two alternative methods to reconstruct a single phylogenetic tree from a set of disjoint alignments. In the \textit{early level combination}, the individual alignments represented by the patterned boxes are concatenated first to form a single superalignment. Standard phylogeny reconstruction programs can then be applied to reconstruct a tree from the superalignment. In the \textit{late level combination} a phylogenetic tree is reconstructed first for each alignment separately. The such reconstructed individual trees are later combined into a single \textit{consensus tree}.}
   \label{fig:combination-compl}
   \end{figure}
Two approaches have been suggested for combining multi-locus datasets from the same set of taxa 
for phylogenetics analysis.
In supermatrix approaches \cite{sanderson1998} (also referred to as 
'total evidence' \cite{kluge1989}) all individual sequence alignments are concatenated to form one large 
\textit{superalignment}. The tree reconstruction is then based on this superalignment using standard methods. In this approach, the phylogenetic information present in the individual alignments is combined early in the phylogenetic analysis. Hence we refer to them as an \textit{early level combination} method (Figure~~\ref{fig:combination-compl} 'early'). Alternatively, the information present in the individual alignments can be combined late in the phylogenetic analysis. Trees are reconstructed first for each alignment separately. These individual trees are then combined at a later step to form a so-called \textit{consensus tree} (Figure~\ref{fig:combination-compl} 'late'). However, in contrast to the concatenation of individual alignments, which is simple text-editing, the combination of trees requires some further considerations.

The most frequently used methods for computing a consensus from a compilation of trees is based on the principle of identifying the set of \textit{compatible splits} among these trees. To this end, splits comprise bipartitions of the taxon set that are induced by cutting a tree at any internal edge. In formal notation splits are represented by the symbol '$|$' (Figure~\ref{fig:split}).\footnote{Of course splits are induced also by cutting at an external edge. However, since this creates only trivial 
splits present in all trees they usually discarded.}  Thus, we can induce for any $\mathcal{N}$-taxon \RB{\textbf{muss das nicht '$|\mathcal{N}|$-taxon' hei\ss{}en, analog zu 4-taxon tree (Heiko)}}tree ($|\mathcal{N}|\ge4$) a split $\mathcal{A}|\mathcal{B}$, such that $\mathcal{A} \cup \mathcal{B} = \mathcal{N}$ and $\mathcal{A} \cap \mathcal{B} = \emptyset$.
%%
\begin{figure}
      \centering
	\fbox{\includegraphics[width=.28\textwidth]{images/split}}
      \caption{Two non-trivial splits can be derived from this tree. Cutting at the edge $y$ induces the split $AB|CDE$. Cutting at edge $z$ moves taxon $C$ from the right-hand side of the split to the left-hand side and results in $ABC|DE$.}
   \label{fig:split}
\end{figure}
%%
Lets consider now a second split $\mathcal{C}|\mathcal{D}$ of the same taxon-set $\mathcal{N}$, e.g., by cutting at edge $z$ instead of $y$ in Figure~\ref{fig:split}. As a consequence, a subtree (in this case taxon $C$) moves from one side of the split to the other. Since an exchange in the other direction cannot occur, one of the intersections of the four taxon-subsets that are defined by the two splits has to stay empty. More formally, two splits $\mathcal{A}|\mathcal{B}$ and $\mathcal{C}|\mathcal{D}$ are said to be compatible if one of the four possible intersections $\mathcal{A} \cap \mathcal{C}$, $\mathcal{A} \cap \mathcal{D}$,
$\mathcal{B} \cap \mathcal{C}$, $\mathcal{B} \cap \mathcal{D}$ is empty. It is easy to see that splits derived from a tree are always pairwise compatible. Conversely, splits derived from two trees that are pairwise incompatible indicate that the two trees 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 arriving at a consensus from a set of trees is collecting all splits that occur in at least 
50\% of the individual trees and using these splits to reconstruct the consensus tree (figure~\ref{fig:consensus}).
This majority consensus approach $M_{\mathit{majority}}$ \cite{margush1981}
guarantees that, in fact, the consensus tree is a tree \cite{semple2003}.
More restrictive 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 for generating a 
consensus tree, e.g., \cite{adams1986, bryant2001a, schmidt2003b}.\RB{bryant2001a added - bibtex entry to be completed} 

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 Jackknife \cite{miller1974} or Bootstrap analysis 
\cite{felsenstein1985,efron1979}, 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 and other methods}
   \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.
\RB{This section needs careful revision. I did not understand much of it.}
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 in the public sequence
databases is far from being satisfactory \cite{driskell2004}.
This problem of incompleteness remains even for completely sequenced genomes 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 for combining 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
      \begin{tabular}{|p{.14\textwidth}|p{.18\textwidth}|p{.75\textwidth}|}\hline
	   \parbox{.14\textwidth}{\centering\bf combination level} & \parbox{.18\textwidth}{\centering\bf combination method}    & 
					   \parbox{.75\textwidth}{~\\
					   \includegraphics[width=.75\textwidth]%
					   {images/combination-level-medium}\\}\\ 
					   \hline
					   \hline
	   \parbox{.14\textwidth}{\centering early} & \parbox{.18\textwidth}{\emph{Total evidence / supermatrix approaches}}   & 
					   \parbox{.75\textwidth}{~\\
					   \includegraphics[width=.75\textwidth]%
					   {images/combination-total-incompl}\\}\\
					    \hline
	   %late & \parbox{.18\textwidth}{\emph{Consensus}}       & 
	   %				\parbox{.75\textwidth}{~\\
	   %				\includegraphics[width=.75\textwidth]%
	   %				{images/combination-consensus}\\}\\ 
	   %				%\hline
	   \parbox{.14\textwidth}{\centering late} & \parbox{.18\textwidth}{\sloppy\textsc{ModMinCut}, \textsc{MinCut\\Supertree}} 
                                         & \parbox{.75\textwidth}{~\\
					   \includegraphics[width=.75\textwidth]%
					   {images/combination-mincut}\\}\\ 
					   %\hline
	   \parbox{.14\textwidth}{\centering late} & \parbox{.18\textwidth}{\emph{MRP}, \emph{MRF}} & 
					   \parbox{.75\textwidth}{~\\
					   \includegraphics[width=.75\textwidth]%
					   {images/combination-mrp}\\}\\ 
					   %\hline
	   \parbox{.14\textwidth}{\centering late} & \parbox{.18\textwidth}{\sloppy\emph{Quartet-based supertree}} 
	                                 & \parbox{.75\textwidth}{~\\
					   \includegraphics[width=.75\textwidth]%
					   {images/combination-quartet}\\}\\ 
					   \hline
	   \parbox{.14\textwidth}{\centering medium} & \parbox{.18\textwidth}{\sloppy\emph{Superquartet puzzling (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 
               alignments on the left to the final tree on the right.}
      \label{fig:combination-incompl}
   \end{figure}

\RB{Fig 4.11: Is this the title row? In this case, how do I read the right-hand entry?\\
	I cannot read this 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-tl}. Supertrees approaches can 
be divided into two classes, agreement supertrees \cite{bininda2004}
and optimization supertrees \cite{wilkinson2004}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5
\subsubsection{Agreement supertrees}

\emph{Agreement supertrees} \cite{bininda2004} are based on 
common nestings in rooted input trees to build the supertree.
\RB{This sentence is unclear}
To that end, rooted input trees are decomposed into rooted triplets
\RB{I do not find this in fig 4.11}
(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.
In an attempt to overcome this drawback \cite{semple2000} 
a minimum-cut step was introduced that greedily resolves tree contradictions in the
\textsc{MinCut Supertree} algorithm. This algorithm was 
\RB{I do not understand the whole paragraph}
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}

\RB{This is too short. Do you have an example for all these methods?}
In order 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 some objective function.
 
\emph{Matrix Representation Methods} are the most abundant (optimization) 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}, figure~\ref{fig:MRP-schemes}c) 
  or sister groups (Purvis' scheme \cite{purvis1995}, 
  figure~\ref{fig:MRP-schemes}d)
  are coded by zeros, ones, and '?' for missing data 
  (Figure~\ref{fig:MRP-schemes}). The obtained \emph{matrix representation}
  (Figure~\ref{fig:MRP-schemes}c,d)
  is then used as input alignment to reconstruct a supertree
  (Figure~\ref{fig:combination-incompl}).
\RB{Where is the alignment?}
  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.

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 can be regarded as a special case of the 
supertree approach, because the former is limited to combining 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=.6\textwidth]{images/MRP-schemes}
  \caption[MRP Coding Schemes]
          {Coding schemes to encode tree topologies (a,b) for MRP methods:
           c) Baum/Ragan and d) 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 
\RB{TL: a patchwork of - HAS: no! too colloquial - patchy = sehr l\"uckenhaft}
supertree/consensus methods are superior to
the use of a supermatrix
\RB{These reference lists are very long. Do you have to cite everything?}
\cite{queiroz1995,miyamoto1995,bininda2002c,bininda2003a,bininda2004a,bininda2004b},
or vice versa \cite{gatesy2002,gatesy2004,eernisse1993,kluge1989,kluge1998}.
Meanwhile a number of points of critique have been raised
against either approach, as have advantages. 
The predominant critique on 
\RB{TL: critique of - HAS: no! according to Webster}
the supermatrix (total evidence) approach addresses the 
issue of choosing an evolutionary model and its parameters 
such that the various evolutionary constraints imposed on the
different concatenated datasets are reflected.
On the other hand, supertree methods are criticized for 
their careless treatment 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 (quartet) 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 the application of evolutionary models fitted to
each locus separately. Furthermore, it uses the phylogenetic
information in the sequences both for combining 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, 
that is, without outgroups or other knowledge where the root has to be placed
as is required in most supertree methods.
\RB{How can a dataset be unrooted. Are the data not sequence data, thus rooting only comes from the analysis?}

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.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Phylogenetic network methods}\label{sec:networks}
\RB{This topic deserves more detailed coverage.}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
By the nature of the biological data, the tree reconstruction methods presented so far are 
\RB{Please refer back to your introductory discussion, here.}
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. In practice, biologists try to avoid
methodological artifacts by applying a plethora of different tree-building algorithms. Still,
one may encounter a systematic error, if the methods are subject to the same bias and therefore
hide the true relationship.

A number of reasons why inconsistent trees might occur have been mentioned earlier
-- methodological as well as biological (sections \ref{sec:character-inconsistency} 
and \ref{sec:consensus}).

In case of conflicting signals a tree might not be the appropriate form
of visualization. Thus, a series of algorithms have been proposed that 
are useful additions to tree-based analysis. These methods
are able visualize to some extent conflicting alternative groupings in 
the data, that cannot be illustrated in a tree \cite{bandelt1992}. 
Nowadays, such algorithms are subsumed under the notion of (phylogenetic)
network methods \cite{posada2001f}. 

% Methods to summarize tree topologies were of course unnecessary if all data 
%  tended to support the same tree. Needless to say that this is usually not the
%  case. Most data sets do not clearly support a only single 
%  phylogenetic tree. Rather, incongruent trees\footnote{Note, that any two non-identical fully resolved, i.e.
%  binary, tree topologies are incongruent (cf. page \pageref{sec:character-inconsistency}).\RB{if you remove labels please check for references to them} are reconstructed either from different 
%  genetic loci or from the same locus using different tree reconstruction methods.
 
\subsection{From trees to split networks}
\subsubsection{Split systems}
   \begin{figure}[t!]
      \centering
	\fbox{%
		\includegraphics[width=.35\textwidth]{images/consensus-net}%
	}
      \caption[Consensus Methods]
           {Consensus network incorporating all splits from Figure~\ref{fig:consensus}.}
   \label{fig:consensus-net}
   \end{figure}
  By definition trees can only consist of compatible splits.
  One way to visualize also incompatible groupings goes along 
  the lines with consensus methods (Section~\ref{sec:consensus}).
  Instead of stopping at the 50\% cut-off which guarantees that
  the outcome is, in fact, a tree, one keeps adding splits from
  a set of input trees beyond this fraction to the split system, 
  i.e., the set of splits.
  Naturally, one can apply a variable cutoff value $r$ that allows 
  to select any system of splits $S_r$ that is present in at least 
  a portion $r$ of all input trees. Pushing $r$ to $0.5$ and
  beyond, one ends up with a network where one is represented by
  either by a single branch or by a set of parallel branches causing
  the topology to be a network, indicating incompatible splits
  as in Figure~\ref{fig:consensus-net}.

  A split system $S_r$
  does contain no subset than $\lfloor 1/r \rfloor$ of splits
  which are all pairwise incompatible, and is called 
  $(\lfloor 1/r \rfloor)$-compatible. For $r>0.5$, all split systems $S_r$
  are $1$-compatible, that means, there are no incompatible splits 
  and, hence, the topology would again be a tree.

\subsubsection{Network visualization}
  Mainly two different methods are implemented to visualize split systems.
  Median networks \cite{bandelt1995,huber2002} incorporate all 
  most parsimonious trees, which representing all splits in the
  split system regarded as binary sequences. Median networks 
  can contain cubes of dimension $\leq \lfloor 1/k\rfloor$, and
  might thus be utterly complex.
  The other type of networks are split graphs \cite{bandelt1992,dress1996,dress2004} 
  which always return planar graphs.

\subsubsection{Constructing split systems from trees}
  Often split systems are collected from a set of input trees
  with equal taxon sets, obtained, for example, from 
  Bootstrap analysis or MCMC sampling.
  From such splits one reconstructs so-called
  consensus networks \cite{holland2003}
  similar to consensus trees (cf. Section~\ref{sec:consensus}).

  Like in the supertree section (\ref{sec:supertree-methods})
  networks can also be reconstructed from overlapping trees
  using the Z-closure method \cite{huson2004b}. 
  Such networks are then called 'super-networks'\footnote{Note, that the 'super' prefix in 
  super-networks does not follow the same notation as in supertrees, superalignments,
  or superquartets, since is not network constructed from networks but from trees.}
  
\subsubsection{Constructing split systems from data}
  
  Although, applications such as consensus networks and super-networks have
  bee suggested quite recently, one should note, that the basic idea of 
  representing 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}
  have been suggested to construct split systems directly from sequence
  data. The constructed networks are able to point out incompatible signals.
  Hence, phylogenetic networks should be constructed in early stages of 
  the data analysis. 
  
  Programs like SplitsTree \cite{huson1998}, T-REX \cite{makarenkov2001a} 
  NETWORK \cite{bandelt1999}, and Spectronet \cite{huber2002} provide easy 
  to use means that can be readily applied to a phylogenetic analysis.
  These packages were used to analyze viral data \cite{dopazo1993,salemi2003-tl} 
  (Figure~\ref{fig:networks}) hybridization events \cite{lockhart2001} and 
  intra-specific data \cite{bandelt1995}, respectively.
  Applied to a viral dataset from \cite{salemi2003-tl} methods like split decomposition
  and Neighbor-Net can easily identify the presence of the three recombinant
  strains SE7812 2, UG266, and VI1310-1.7 (Figure~\ref{fig:networks}).

   \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-tl} containing 
	    reference strains (A, B, C, D, F, G, H, J) together with 
            three recombinants (SE7812\_2, UG266, VI1310-1.7). 
            Left: BioNJ tree (8 splits),
	    middle: Split Decomposition (14 splits), 
            right: Neighbor-Net (19 splits).}
   \label{fig:networks}
   \end{figure}

  It should be noted that these split-based networks provide only 
  a visualization of ambiguities in the data and do not qualify 
  as methods to infer the reasons of the net-like structure \cite{bryant2004}. 

\subsection{Reconstructing reticulate evolution and further analyses}

  As mentioned above, in case that different methods, different
  loci, or even just different parts of the very same gene,
  show conflicting phylogenetic signals, a large number of
  biological mechanisms are possible to have produced the
  observed ambiguities.

  One would certainly check whether conflicting 
  evolutionary hypotheses are really significantly different 
  \cite{hasegawa1994,shimodaira1999,goldman2000a}.
  If so, we can envision several biological mechanisms causing 
  reticulate\footnote{network-like} evolution, such that 
  tree is not appropriate for a given dataset. 
  Reassortment, the mixture of viral chromosomes called segments within a cell
  co-infected by different viral lineages \cite{klempa2003}, and recombination,
  the exchange of genomic regions among chromosomes \cite{posada2002a,paraskevis2005},
  e.g., in viruses \cite{fitch1996,salminen1995} are one example. 
  Horizontal gene transfer between organisms like bacteria
  \cite{delwiche1996,guindon2001,bergthorsson2003} and genome
  hybridization or fusion \cite{zillig1991,doolittle1999a,martin1999} 
  constitute other possibilities.
  Sometimes reticulations 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.

%   \begin{figure}[t!]
%      \centering
%	\fbox{%
%		\includegraphics[width=.32\textwidth]{images/recombination-net-a}\hfill%
%		\includegraphics[width=.32\textwidth]{images/recombination-net-V}\hfill%
%		\includegraphics[width=.32\textwidth]{images/recombination-net-W}%
%      \caption[Recombination Net]
%           {Reticulate evolution: a) The recombination between strain $V$ and $W$
%            produced the recombinant strain $R$. The two parts of the sequence b) and c)
%            reflect different evolutionary histories of the reticulation.}
%   \label{fig:networks}
%   \end{figure}

  In general, purely split-based networks are sufficient to
  illustrate an event of reticulate evolution like the recombination
  shown in Figure~\ref{fig:recombiation-net}, because you cannot 
  map this structure into a set of splits, although one can map
  the separate gee-trees could. 
  Hence, network methods have been suggested to reconstruct reticulate
  evolution, like hybridization networks, recombination networks, 
  or galled trees \cite{huson2005,gusfield2005}.

The pros and cons of the different algorithms still need to be evaluated. 
However, the comparison of different phylogenetic networking
strategies is not easy. 
\RB{I do not think that this gives the field sufficient credit. The method has been in use for over ten years. Can you be more conceret about its benefits and limits?}
From Figure~\ref{fig:networks} it is apparent that, e.g., Neighbor-Net is more liberal 
\RB{I do not find the differences so dramatic.}
in introducing non-compatible splits\footnote{19 splits compared 
to 14 splits in the split decomposition network and 8 splits in a fully resolved tree.}. 
%However, which of the two networks reflect the true (unobservable) 
%\RB{It does not have to be history, it can just be noise, e.g. introduced by incorrect alignments}
%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 adequate. 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 evolutionary process.

%One should note, that the basic idea of representing evolutionary processes by networks rather than trees has a
%  
%Subsequently, lots of methods are abound to intensify 
%  examination, many based on sliding windows. 
%  The following (obviously incomplete) list of references
%  points to studies and methods which examine, whether the 
%  conflicting signals are due to
%  recombination \cite{salminen1995,paraskevis2005}, 
%  reassortment \cite{klempa2003},
%  horizontal gene transfer \cite{delwiche1996,guindon2001,bergthorsson2003}, 
%  gene conversion \cite{archibald2002}, 
%  differential gene duplication and loss \cite{cotton2002}, 
%  incomplete lineage sorting \cite{satta2000},
%  genome hybridization or fusion \cite{zillig1991,doolittle1999a,martin1999}, 
%  or just differential mutational variability as, e.g., shown in 
%  \cite{worobey2002,bryant2004}.
%
%  Due to the variety of biological mechanisms underlying the evolution 
%  of sequences and genomes, the analytical measures to be taken, have 
%  of course to be determined according to the data and biological 
%  context at hand.
%  
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5
%\subsection{Incongruent phylogenies}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5
%\section{Further analysis}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\xxx
%\xxx
%\xxx
%\xxx
%\section{Arndt's part}
%%By the nature of the biological data, the tree reconstruction methods presented so far are 
%%\RB{Please refer back to your introductory discussion, here.}
%%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. In practice, biologists try to avoid
%%methodological artifacts by applying a plethora of different tree-building algorithms. Still,
%%one may encounter a systematic error, if the methods are subject to the same bias and therefore
%%hide the true relationship.
%
%%Thus, a series of algorithms have been proposed that are useful additions to tree-based analysis. These methods
%%are able visualize to some extent conflicting alternative groupings in the data, that cannot be illustrated
%%in a tree \cite{bandelt1992}. Nowadays, such algorithms are subsumed under the notion of (phylogenetic)
%%network methods \cite{posada2001f}. 
%% Phylogenetic networks should be constructed 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. 
%\RB{This is not true for all networks, see remarks in my mail}
%However, if phylogenetic networks exhibit a certain degree of reticulation,
%\RB{What is this?}
%this can indicate substantial departure from tree-likeness. We can envision several biological causes why a
%tree is not appropriate for a given dataset. 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
%\RB{Explain these notions.}
%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 of representing 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-tl} (Figure~\ref{fig:networks})
%%hybridization events \cite{lockhart2001} and intra-specific data \cite{bandelt1995}, respectively.
%
%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 in Section~\ref{sec:consensus}).
%In this way sets of trees with equal sets of taxa (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-tl} containing 
%%	    reference strains (A, B, C, D, F, G, H, J) together with 
%%            three recombinants (SE7812\_2, UG266, VI1310-1.7). 
%%            Left: BioNJ tree (8 splits),
%%	    middle: Split Decomposition (14 splits), 
%%            right: Neighbor-Net (19 splits).}
%%   \label{fig:networks}
%%   \end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bibliography{phylo-chapter}

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