\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


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5




\section{Introduction}
The large amounts of molecular sequence data currently available
serve two needs in the phylogenetic analysis of the
relationship of species. On the one hand, the number
of interesting species available for analysis grows (vertical growth). 
On the other hand, more different sequences per species get available 
(horizontal growth).
Unfortunately, the number of sequences is not distributed evenly 
among species of interest. This often makes collecting a dataset 
for phylogenetic analysis a painful decision on the trade-off 
between the amount of taxa and the number of sequences.

While methods abound to infer phylogenies from a set of 
aligned sequences \cite{swofford1996}, only a small number of methods 
exists to combine data of different genes, proteins, or genomic areas for 
joint analysis. 

There has been a large ongoing debate how to combine different 
datasets to reconstruct trees (cf. \cite{queiroz1995},
\cite{bininda2002}, and \cite{page1998}, chap.~8 for review). 
Two paradigms have been discussed, which we will classify by
the 'distance' of the combination event from the underlying data
into \emph{low level} and \emph{high level} methods
(cf. Fig.~\ref{fig:combination-level}). 
Note that \emph{low} and \emph{high} does not imply a quality rating.

The first paradigm is \emph{total evidence} (also often called 
\emph{combined} or \emph{simultaneous analysis}) where the data 
is combined directly by concatenating the alignments. 
Hence, \emph{total evidence} methods will 
be referred to as \emph{low level methods} 
(cf. Fig.~\ref{fig:combination-level}).

The other paradigm is the so-called \emph{separate analysis}
(also called \emph{taxonomic congruence} and \emph{consensus}
or \emph{supertree approach}). Such methods combine trees reconstructed
separately from the single datasets. Since the combination takes place 
far from the underlying data, such methods are referred to as 
\emph{high level methods} (cf. Fig.~\ref{fig:combination-level}).

Both paradigms have their advantages and drawbacks (for review see 
\cite{queiroz1995}, \cite{bininda2002}, and references therein). 
Major criticisms are, e.g., the problems to jointly model the evolutionary 
process for the concatenated dataset in \emph{low level methods} and
the loss of information in the \emph{high level methods} since the 
underlying data is in general not considered when the trees are
combined. These arguments gave rise to the design of an alternative method 
which will be proposed in this chapter. 

The method presented here follows a \emph{medium level} paradigm, 
according to the level of combination (cf. Fig.~\ref{fig:combination-level}).
Before particularizing the procedure (section \ref{sec:quartet-combin}), 
commonly used \emph{high} and \emph{low level methods} are described
(section \ref{sec:supertree-methods}). 
Then the new method is applied to a biological dataset in section 
\ref{sec:grass-tree}. The results are discussed in the context of 
\emph{total evidence} and \emph{consensus/supertree methods}. 
Finally, problems will be discussed and an outlook on further 
improvement and extensions will be given.

\section{Methods to Combine Datasets}
\label{sec:supertree-methods}
\begin{figure}[t!]

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

%%%%%%%%%%%%
\subsection{\emph{Low Level} Combination: Total Evidence}

As mentioned above, \emph{low level methods} are commonly referred to as 
\emph{total evidence}, \emph{combined} or \emph{simultaneous analysis} 
methods.
Claiming that all information (evidence) available should be used 
for phylogenetic analysis, all single datasets are combined into 
one single \emph{'supermatix'} \cite{sanderson1998} as shown in 
Fig.~\ref{fig:combination-level}. This is achieved 
by concatenating all source alignments filling missing data with
gap characters. The overall alignment is then used as input for
phylogenetic analysis.
This method seems unproblematic for complete datasets, where
for each species one sequence in each source dataset exists.
How \emph{total evidence} approaches handle missing data
crucially depends on the method used to reconstruct a phylogeny from the 
concatenated alignment.
Since some programs exclude alignment columns with gaps, 
such programs will end up only with data from genes which are available for 
the whole set of species. Datasets with missing sequences are discarded. 

%%%%%%%%%%%%
\subsection{\emph{High Level} Methods}

While \emph{low level methods} combine the source datasets directly, 
\emph{high level methods} construct a tree for each source dataset.
The trees from the source datasets are then combined to an overall tree 
(Fig.~\ref{fig:combination-level}).
If all source datasets contain the full set of species, 
consensus techniques
can be applied combining all the equally sized trees into one consensus tree.
To combine sets of trees with unequal, but overlapping sets of species, 
so-called \emph{supertree} methods have been developed which amalgamate 
the input trees into one overall \emph{supertree}.

%%%%%%%%%%%%%%
\subsubsection{Combining Equal-Sized Datasets: Consensus Methods}
\label{sec:consensus}

\begin{figure}[t]
  \centering
  \includegraphics[width=\textwidth]{fig-missing/consensus-all}
  \caption[Consensus Methods]
          {Consensus methods}
  \label{fig:consensus-all}
\end{figure}

Consensus methods aim to construct a consensus tree from a set of 
trees preserving common topological details of the source trees.
Commonly applied consensus methods are strict consensus, 
majority-rule consensus \cite{margush1981}, semi-strict consensus 
\cite{bremer1990}, and Adams consensus \cite{adams1986}. 

Most consensus methods are based on splits or bipartitions 
(cf. \ref{sec:intro:treenota})
found in a majority of the source trees ($M_l$ consensus 
\emph{sensu} \cite{mcmorris1983}, where $l$ represents 
the percent occurrence of included splits). 
Sets of non-contradicting bipartitions are chosen to reconstruct 
the consensus tree. 

The \emph{majority-rule consensus} \cite{margush1981} uses all splits
occurring in the majority of input trees. Usually a \emph{majority-rule
consensus} is assumed ($M_l$ consensus with $l>0.5$, \cite{mcmorris1983}). 
This means all splits occurring in more than $50\%$ of the source trees 
(see Fig.~\ref{fig:consensus-all}). 
Considering $l>0.5$ ensures that all splits can be incorporated in a
tree topology, because no two contradicting splits are able to 
occur in more than $50\%$ of the input trees.

For the \emph{strict consensus} tree only bipartitions are chosen that
are found in all input trees ($M_{1.0}$, see Fig.~\ref{fig:consensus-all}).
The \emph{semi-strict consensus} \cite{bremer1990} contains all splits 
that are not contradicted in any of the input trees, e.g. the 
split $ABCD|EF$ is uncontradicted by the $ABC$-trifurcation in 
tree A and B in Fig.~\ref{fig:consensus-all}.
Note that such splits can occur in less than half of the source 
trees. If all trees are binary trees \emph{strict} and \emph{semi-strict
consensus} will always produce the same trees.

   \begin{figure}[t]
     \centering
     \includegraphics[width=.8\textwidth]{fig-missing/consensus-adams}
     \caption[Adams Consensus]
             {Adams Consensus}
     \label{fig:consensus-adams}
   \end{figure}

Contrary to most consensus methods which are based on bipartitions and their 
percent occurrence in the source trees, the \emph{Adams consensus} 
is based on common nestings in trees, i.e., taxa frequently occurring
together in the same subtree. This method tries to find 
groups of sequences that are commonly occurring together in the
source trees \cite{adams1986}. \emph{Adams consensus trees}
can contain groups that cannot be found in any of the source trees.
This makes it difficult to interpret. Yet it can be informative
when there are sequences that are difficult to place. Such sequences 
are moved to the root of the \emph{Adams consensus tree} 
(Fig.~\ref{fig:consensus-adams}).

%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Combining Overlapping Datasets: Supertree Methods}

Supertree methods have been developed to combine sets of overlapping trees 
into \emph{'supertrees'} containing all leaves found in the source trees.
Some of the methods are restricted to rooted trees, based on the argument 
that the broad majority of trees published are rooted trees. 
Input trees cannot be produced from different datasets only, 
but can also be obtained from the literature.

%%%%%%%%%
\paragraph{Matrix Representation Methods}

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

A commonly used method to construct supertrees is 
\emph{Matrix Representation using Parsimony} 
(MRP, \cite{baum1992,ragan1992}), which uses binary coding to
represent the input trees. The splits induced by all source trees 
are coded into a matrix with binary characters ('0', '1') 
with missing data ('?').
The binary matrix is then used to construct an overall tree 
(cf. Fig.~\ref{fig:combination-level}) 
using \emph{Maximum Parsimony} methods \cite{swofford1996}. 
The most abundant coding schemes are those independently 
suggested by \cite{baum1992} and \cite{ragan1992} and the 
modified scheme by \cite{purvis1995}.
Baum/Ragan code the bipartitions 
of an input tree assigning '1' to all leaves in the one part of the 
bipartition and '0' to the other that contains the root. All missing taxa
are assigned the missing data character '?' (Fig. \ref{fig:MRP-schemes}).
\cite{purvis1995} differs in that only the sistergroup of a clade
is assigned '0', while all other leaves of that part outside the clade
are assigned '?' (Fig.~\ref{fig:MRP-schemes}).

To give input trees different weights in the analysis, different weighting
schemes have been suggested (see \cite{salamin2002}, 
\cite{sanderson1998}, and references herein for more details).

Recently, another method has been proposed called \emph{Matrix Representation
using Flipping} (MRF, \cite{chen2003}), which also uses a binary matrix 
coding of the trees as described above. The MRF supertree is constructed 
by 'flipping' conflicting character states from '1' to '0', or vice versa
to produce a matrix that does not contain contradictions.
Their optimal solution is the tree that needs the least 'flips'.


%%%%%%%%%
\paragraph{Direct Supertree Methods}

%\begin{figure}[p!]
%     \centering
%     \includegraphics[width=.8\textwidth]{fig-missing/mincut}
%     \caption[\textsc{MinCut Supertree} Algorithm]
%             {The \textsc{MinCut Supertree} Algorithm. 
%              For more details, see text.}
%     \label{fig:mincut}
%\end{figure}

%\begin{algorithm}[p!]
%\caption[\textsc{MinCut Supertree}]
%        {\textsc{MinCut Supertree}~(Set of rooted trees $\mcT$, 
%                                   set of $n$ leaves)}
%\label{alg:mincut}
%
%  \Switch{number of leaves $n$}{
%  \lCase{($n=1$)}{\KwRet a single node $x_1$\;}
%  \lCase{($n=2$)}{\KwRet a tree with 2 leaves $x_1$ and $x_2$\;}
%  \Other{
%\lnl{alg:mincut-ST}%
%      Construct the graph $S_{\mcT}$ by connecting
%      each pair of taxa $a$ and $b$ by an edge $e_{(a,b)}$ ~if~ they are 
%      connected in at least one tree in $\mcT$ by a path that does
%      not pass the root of that tree, i.e., $\MRCA(a, b) \neq root$
%      (cf. Fig.~\ref{fig:mincut}, $S_{\mathrm{\{Tree A,B\}}}$)\;
%
%      Weight the edge $e_{(a,b)}$ by the number of trees supporting 
%      $\MRCA(a, b) \ne root$\;
%  }}
%  \eIf{$S_{\mcT}$ is a disconnected graph}{
%      Let $S_i$ be the components of $S_{\mcT}$\;
%  }{
%      Construct $S_{\mcT}/E_{\mcT}^{Max}$ as follows: 
%      Merge all nodes $a$ and $b$ connected by an edge $e_{(a,b)}$ with 
%      maximum weight $|\mcT|$, i.e., supported by the whole set of trees
%      and remove edge $e_{(a,b)}$ (cf. Fig.~\ref{fig:mincut})\;
%
%\lnl{alg:mincut-cut}%
%      Remove all edges from $S_{\mcT}/E_{\mcT}^{Max}$ that are
%      a minimum cut set of $S_{\mcT}$.
%
%      Let $S_i$ be the resulting components of $S_{\mcT}/E_{\mcT}^{Max}$\;
%   }
%  \ForEach {component $S_i$}{ 
%     $T_i$ = ~\textsc{MinCut Supertree}~($\mcT|S_i, L=S_i$), 
%             where $\mcT|S_i$ denotes the trees from $\mcT$ with all leaves 
%             $r \not\in S_i$ pruned\;
%  }
%  Construct a new tree $T$ by connecting the roots of $T_i$ to a new tree\;
%  \KwRet $T$\
%\end{algorithm}


Another family of supertree methods use a more graph theoretical 
approach. Members of that family are 
  the \textsc{OneTree}/BUILD algorithm \cite{aho1981,bryant1995},
  \textsc{MinCut Supertree} algorithm \cite{semple2000}, and
  the modified \textsc{MinCut Supertree} algorithm
  (\textsc{ModMinCut Supertree}, \cite{page2002d}).
These algorithms take as input sets of rooted trees. The 
BUILD algorithm and the \textsc{OneTree} algorithm produce
a supertree only if the input trees are compatible, i.e., the trees
are not contradictory (cf. strict consensus in \ref{sec:consensus}).
Since this is almost never the case for biological data, these 
algorithms are mainly useful to test for compatibility of trees.

\textsc{MinCut Supertree} tries to yield a supertree applying 
a minimum cut algorithm to the graph $S_{\mcT}$ constructed
from the set of input trees $\mcT$, following 
Alg.~\ref{alg:mincut} (see also Fig.~\ref{fig:mincut} and
Fig.~\ref{fig:combination-level}). The notations follow \cite{page2002d} --
for further details see there.

%\begin{figure}[t]
%     \centering
%     \includegraphics[width=\textwidth]{fig-missing/modmincut}
%     \caption[\textsc{ModMinCut Supertree} Algorithm]
%             {The \textsc{ModMinCut Supertree} algorithm. 
%              For more details, see text.}
%     \label{fig:modmincut}
%\end{figure}

\cite{page2002d} suggested a modification (here called \textsc{ModMinCut}) 
to choose the minimum cuts, 
that takes into account preserving uncontradicted information from 
the source trees. The \textsc{ModMinCut Supertree} algorithm marks all edges 
in the graph $S_{\mcT}$ (step \ref{alg:mincut-ST}) not contradicted 
by any tree in $\mcT$. 
If $S_{\mcT}$ has to be cut in step \ref{alg:mincut-cut}
minimum cuts are preferred which do not cut uncontradicted edges.
Hence, the amount of uncontradicted information from the source trees
is preserved in the supertree (cf. Fig.~\ref{fig:modmincut}).

%%%%%%%%%%%%%
\paragraph{Quartet-Based Supertree}
Recently a quartet-based supertree method has been proposed by
\cite{robinson2001}. Instead of using a matrix representation, all source 
trees are decomposed into sets of quartets contained in the topologies
(Fig.~\ref{fig:combination-level}). 
Each quartet is weighted by the highest support value found on the 
path of the quartet's middle edge in any of the input trees (the authors used 
the TREE-PUZZLE package to compute the trees and support values).
From this set of weighted quartets an overall tree is constructed with
the quartet method implemented in the AllTree program \cite{bendor1998}.
In a first step, this method computes all subsets of taxa and keeps those 
satisfying the most quartets. In a second step, it performs an exact 
search on each subset constructing an overall tree satisfying most quartets.

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

\section{\emph{Medium Level} Combined Phylogenetic Analysis}
\label{sec:quartet-combin} 

%%%%%%%%%%%%
\subsection{Notation}
\label{sec:nota-incompl}

In the present chapter we assume a collection $\mcS = \{s_1, \ldots, s_n\}$ 
of $n$ species and $k$ different genes to be used for combined analysis.

With $\mcS_1, \mcS_2, \ldots,\mcS_k$ we denote subsets of $\mcS$, such that
\begin{eqnarray}
 \left| \mcS_g \right| \le 4 \mbox{\qquad for each \quad} g&
 \mbox{\qquad and \qquad}&
 \bigcup_{g=1}^k \mcS_g = \mcS.
\end{eqnarray}
Each $\mcS_g$ represents the subset of species for which a
multiple alignment based on gene $g$ is available. These subsets 
will be called genesets. Finally, $\mcQ_g , g=1, \ldots, k$ represent 
the corresponding sets of possible quartets.

Instead of reconstructing the trees $T(\mcS_g)$ for each set $\mcS_g$, 
we will compute an overall tree $T(\mcS)$ combining the
information provided from the evaluation of the quartet sets
$\mcQ_1, \mcQ_2, \ldots,\mcQ_k$ from the $k$ different alignments.
Note that a taxon is not represented by one sequence any more.

%%%%%%%%%%%%%%%%%
\subsection{The Combined Quartet Method to Combine Genesets}
\label{sec:missing:qp-combine}


%%%%%%%%%%%%%%%%%
\subsubsection{Combining the ML Quartets}

In the method proposed, the genesets will be combined on the level
of the quartets. As a guideline to combine the quartets we use 
the log-likelihood $\ell^{(g)}_{ab|cd}$, $\ell^{(g)}_{ac|bd}$, 
and $\ell^{(g)}_{ad|bc}$ for quartet $\{a,b,c,d\} \in \mcQ_g$
on the geneset $\mcS_g$.

To combine the datasets for each geneset $\mcS_1$, $\mcS_2$, 
\ldots $\mcS_k$, all three $\log$-likelihoods for each quartet in
$\mcQ_1$, $\mcQ_2$, \ldots $\mcQ_k$ are evaluated first 
(cf. \emph{ML step} in \ref{sec:qp-alg}).

Then, we compute
\begin{eqnarray}
  \label{eq:missing:tlh1}
  \ell_{ab|cd} & = & \sum_{g=1}^k \ell^{(g)}_{ab|cd} \\
  \label{eq:missing:tlh2}
  \ell_{ac|bd} & = & \sum_{g=1}^k \ell^{(g)}_{ac|bd}\\
  \label{eq:missing:tlh3}
  \ell_{ad|bc} & = & \sum_{g=1}^k \ell^{(g)}_{ad|bc}
\end{eqnarray}
for each quartet. For the sake of simplicity, the log-likelihoods
$\ell^{(g)}_{\tau}=0$ if the quartet with the sequences $\mcL(\tau)$
is not represented by alignment $g$.

Alternatively, one can also compute
\begin{eqnarray}
  \label{eq:missing:quartmean1}
  \overline{\ell_{ab|cd}} &=& \frac{\ell_{ab|cd}}
                           {|\left\{g:\{a,b,c,d\}\in\mcQ_g\right\}|}\\
  \label{eq:missing:quartmean2}
  \overline{\ell_{ac|bd}} &=& \frac{\ell_{ac|bd}}
                           {|\left\{g:\{a,b,c,d\}\in\mcQ_g\right\}|}\\
  \label{eq:missing:quartmean3}
  \overline{\ell_{ad|bc}} &=& \frac{\ell_{ad|bc}}
                           {|\left\{g:\{a,b,c,d\}\in\mcQ_g\right\}|}.
\end{eqnarray}
$\overline{\ell_{\tau}}$ can be viewed as the average support a 
quartet tree $\tau$ receives from the set of sequence alignments.
In case that a quartet is not represented by any alignment the averages
are set equal to zero. % and the quartet is ignored in the procedure.

%%%%%%%%%%%%%%%%%
\subsubsection{Computing the Overall Tree}

To reconstruct a phylogeny $T(\mcS)$ based on the collection of 
log-likelihoods from Equations \ref{eq:missing:tlh1} to \ref{eq:missing:tlh3} 
or \ref{eq:missing:quartmean1} to \ref{eq:missing:quartmean3} we apply
the PUZZLE idea from \ref{sec:qp-alg}.
The straightforward application of the \emph{QP} algorithm is only possible 
if information exist for each quartet in $\mcQ$. This, for instance, 
is the case if at least one alignment $\mcS_g$ comprises all the species 
in $\mcS$. 

If some quartets are missing, which usually happens if each $\mcS_g$ is 
a proper subset of $\mcS$, then these quartets are treated as unresolved. 
A quartet tree is selected randomly among the three possible topologies.
In this case it is necessary to examine whether the overlapping genesets 
can be combined. This will be explained in the following.


%%%%%%%%%%%%%%%%%
\subsubsection{Assessing Whether Genesets Can Be Combined}


To combine two genesets $\mcS_i$ and $\mcS_j$ 
a minimum pairwise overlap of 3 sequence among the two subsets is required, 
\begin{equation}
   \left| \mcS_i \cap \mcS_j \right| \ge 3
   \label{eq:missing:pairoverlap} \mbox{.}
\end{equation}
We call Eq.~\ref{eq:missing:pairoverlap} the \emph{pair-overlap condition}.
The \emph{pair-overlap condition} is different from the 
\emph{overlap condition} (Eq.~\ref{eq:overlap}) in section \ref{sec:modifiedqp} 
where the subsets were constructed from one complete set of sequences 
to ensure combinability of the subsets.
Here the subsets are genesets. Their sizes and overlap are defined by 
the availability of sequence data for the species in $\mcS$. 
Note, that not every pair of genesets might share a sufficient overlap.

To assess whether these gene datasets can be combined, we construct an overlap
graph $G_{\mathit{ovl}}=(\mcV,\mcE)$ with a set of nodes $\mcV$ (genesets) and a set of 
undirected edges $\mcE$ (overlaps) with
\begin{eqnarray}
  \mcV & = & \{\mcS_1, \mcS_2, \ldots \mcS_k\}\\
  \mcE & = & \{e_{(\mcS_i,\mcS_j)}\mbox{ for }\left|\{\mcS_i \cap \mcS_j\}\right| \ge 3\}
  \quad 1\le i < j \le k.
\end{eqnarray}
The edge weights consist of the amount of overlap fulfilling the 
\emph{pairwise-overlap condition} (see for an example 
Fig.~\ref{fig:missing:overlap}). This representation of the 
datasets provides insight into several properties of the entire dataset. 

If the graph consists of unconnected subgraphs, not all data is suited 
for a combined analysis. According to the \emph{pairwise-overlap condition}
gene datasets from different connected components cannot be used 
simultaneously in the same analysis because no quartet information is 
are available to reasonably guide the insertion of the sequences.

Genesets from one connected component, however, can be used for combined 
analysis. Although genesets might exist within a connected component which
do not share sufficient overlap with each other to be combined, they can be linked
by means of other genesets which first have to be added 
satisfying the \emph{pairwise overlap condition}, to connect the two.

Note, that by applying the \emph{overlap condition} from Eq.~\ref{eq:overlap},
sets from one connected component can gain an overlap $\ge 3$
to the leafset $\mcL(T_i)$ of a tree $T_i$ so far reconstructed
from genesets of another connected component. 
Nevertheless, combining those sets will produce a very doubtful tree,
because too little information is available to guide the
insertion of sequences.

The combinability of the genesets from a connected component is characterized
by two features of the \emph{overlap graph}. A high connectivity
within a component (each geneset shows overlap to many other geneset)
results in network-like quartet information among the genesets.
This reduces the need for mediating sets to connect non-overlapping genesets.
Even more important is the size of the overlap. The higher the overlap,
the more quartets are shared among two neighboring genesets. 
Consequently, a higher amount of information is available to guide the
insertion of sequences from a geneset into a tree already reconstructed. 

%%%%%%%%%%%%%%%%%
\subsubsection{Overlap-Guided Puzzling Step}

As described above, sufficient overlapping information is needed 
to reasonably insert a new leaf $s_{i+1}$ into a tree $T_i$. Hence,
instead of using a random permutation of leaves, the permutation
has to follow certain restrictions. 
To satisfy the \emph{pairwise overlap condition}, 
we apply a graph based procedure similar to Prim's minimum spanning tree 
(MST) algorithm (see, e.g., \cite{cormen2001}) assuming equal edge weights.
We start with the leaves from a randomly picked geneset 
$\mcS' \in \{\mcS_1\ldots \mcS_k\}$. 
We define a front set $\mcF$ containing all unused nodes (genesets) 
from the overlap graph that are connected by an edge to any geneset 
already used in the tree. 
From the sequences in $\mcS'$ we construct the tree $T(\mcS')$
applying the usual puzzling step algorithm 
(see section \ref{sec:qp-alg} and chapter \ref{chap:complex}).
Then we randomly draw one geneset $\mcS''$ from $\mcF$. We remove 
$\mcS''$ from $\mcF$ and add the sets connected
to $\mcS''$, but not yet used to $\mcF$. The sequences of $\mcS''$ 
are then added to the tree. 
Guided by the overlap graph we thus construct an 
intermediate tree by sequentially adding the genesets. 
As in the usual \emph{puzzling step} many intermediate trees are 
constructed using different orders of leaves and genesets.

%%%%%%%%%%%%
\subsubsection{Relative Majority Consensus}
\label{sec:missing:mrel}

Since missing data adds more ambiguity, this naturally hampers the 
construction of a resolved majority-rule consensus tree. We therefore 
decided to apply a majority consensus which is slightly different 
from the majority-rule consensus used in section \ref{sec:qp-alg}. 
Instead of using only splits occurring in more than $50\%$ 
($M_l$ with $l>0.5$) of the intermediate trees, also splits 
below $50\%$ are considered. 
The aim is to use as many splits as are supported 
by relative majority to extract a maximum 
uncontradicted information from the intermediate trees.

The relative majority consensus $M_{\mathit{rel}}$ adds all congruent
splits from the set of intermediate trees in descending order of occurrence.
No splits will be accepted for the consensus that have the same or
lower percentage occurrence as any incongruent split.
This consensus procedure does not imply a fixed threshold but 
uses a variable percentage down to the first incongruence 
guided by the relative majority. 

