Barbara R Holland
email: b.r.holland@massey.ac.nz

Frédéric Delsuc

Vincent Moulton

Consensus networks

Visualizing conflicting evolutionary hypotheses in large collections of trees: using consensus networks to study the origins of placentals and hexapods.

2

Abstract ---Many phylogenetic methods produce large collections of trees as opposed to a single tree, which allows the exploration of support for various evolutionary hypotheses. However, to be useful the information contained in large collections of trees should be summarised; frequently this is achieved by constructing a consensus tree. Consensus trees display only those signals that are present in a large proportion of the trees. However, by their very nature consensus trees require that any conflicts between the trees are necessarily disregarded. We present a method that extends the notion of consensus trees to allow the visualisation of conflicting hypotheses in a consensus network. We demonstrate the utility of this method in highlighting differences amongst maximum likelihood bootstrap values and Bayesian posterior probabilities in the placental mammal phylogeny, and also in comparing the phylogenetic signal contained in amino acid versus nucleotide characters for hexapod monophyly.

[Phylogenetic trees; consensus trees; median networks; Bayesian posterior probabilities; nonparametric bootstrap; quartet puzzling; placental mammals; hexapods] The estimation of phylogenetic trees remains a central task in evolutionary biology. Many methods have been developed for constructing trees [START_REF] Swofford | Phylogenetic inference[END_REF]. However, a single point estimate of the optimal tree with no measure of reliability is not always useful [START_REF] Penny | Estimating the reliability of evolutionary trees[END_REF]. For this reason it is common practice to employ methods that generate a tree together with some measure of support for individual edges (branches). These methods include nonparametric bootstrap resampling with replacement [START_REF] Felsenstein | Confidence limits on phylogenies: an approach using the bootstrap[END_REF], Bayesian approaches based on Markov Chain Monte Carlo (MCMC) methods [START_REF] Huelsenbeck | Potential applications and pitfalls of Bayesian inference of phylogeny[END_REF], and quartet puzzling [START_REF] Strimmer | Quartet puzzling: a quartet maximum-likelihood method for reconstructing tree topologies[END_REF].

A common feature of all these methods is that rather than producing a single tree they produce a large set of trees. In the case of nonparametric bootstrapping this is accomplished by resampling columns of the sequence alignment and estimating a tree for each sample [START_REF] Felsenstein | Confidence limits on phylogenies: an approach using the bootstrap[END_REF]. Bayesian approaches explore the phylogenetic landscape by using MCMC, a numerical method where trees are sampled in proportion to their posterior probability [START_REF] Huelsenbeck | Potential applications and pitfalls of Bayesian inference of phylogeny[END_REF]. Quartet puzzling provides a fast estimate of the ML tree by computing all ML quartets and then puzzling them together [START_REF] Strimmer | Quartet puzzling: a quartet maximum-likelihood method for reconstructing tree topologies[END_REF]. This puzzling operation is order dependent; so many random orderings of the quartets are used, each producing a tree.

In order to summarise the large collections of trees that these methods produce, consensus trees are usually constructed, in which the weights assigned to the edges reflect their level of support. [START_REF] Bryant | A classification of consensus methods for phylogenetics[END_REF] recently provided a comprehensive overview of consensus tree methods and their classification. Consensus trees display only those signals that are supported by a large proportion of the trees. However, although a consensus tree is a concise way to summarise the information contained in a large collection of trees, by definition it cannot display conflicting signals. For instance, the following two situations would be impossible to distinguish using a consensus tree: 1) One grouping of the taxa has slightly more than 50% support and another conflicting grouping has slightly less than 50% support; 2) One grouping of the taxa has slightly more than 50% support and no other conflicting grouping has more than 10% support. In addition, a lack of resolution in the consensus tree usually implies conflict, but a polytomy could be resolved in many ways, only a few of which may have support amongst the input trees.

We present a method that generalises the notion of consensus trees to allow conflicting evolutionary hypotheses to be displayed within a network. This expands upon a method proposed by [START_REF] Bandelt | Combination of data in phylogenetic analysis[END_REF]. We illustrate the use of consensus networks by focusing on two biological examples that have recently generated controversies. First, we explore the differences between Bayesian posterior probabilities and bootstrap proportions in the case of placental mammal phylogeny (Murphy et al., 2001a;[START_REF] Suzuki | Overcredibility of molecular phylogenies obtained by Bayesian phylogenetics[END_REF], and second, we examine the extent of the conflict between amino-acid and nucleotide characters for the origins of hexapods (Nardi et al., 2003a;[START_REF] Delsuc | Comment on "Hexapod origins: monophyletic or paraphyletic?[END_REF].

THE CONSENSUS NETWORK METHOD

We begin with an example to illustrate the way in which consensus trees can be generalised to consensus networks. Consider the three trees shown in Figure 1A. We begin by making a list of the splits that are displayed by the internal edges of these trees, together with a weight indicating the number of trees displaying each split (Figure 1B). The strict consensus tree is the tree that displays only those splits which occur in all three of the trees and, since none of the splits in our list have weight 3, only the splits corresponding to the pendant edges of the trees are displayed (Figure 1C).

The majority rule consensus tree is the tree that displays only those splits which occur in two or more of the trees (Figure 1D). In this example, the required splits are those with weight 2 (AB | CDE and ABC | DE) plus the splits corresponding to the pendant edges of the input trees, and so the majority rule tree is identical to the first of the input trees. Finally, Figure 1E shows the consensus network, which displays those splits that occur in one or more trees, of which there are 9. This network may be interpreted as follows: Each split is represented by a class of parallel edges, whose lengths are proportional to the weight assigned to the split. Note that even though, for example, the splits AB | CDE and AC | BDE cannot be displayed simultaneously by any tree, they are both displayed by the network.

We now discuss our method in general. Consider as input a collection of phylogenetic trees, all on the same set of taxa. These could be generated by any of the methods mentioned above or might be the result of heuristic or exact searches that return many equally well-supported trees.

Next, as in the example, the list of splits corresponding to edges in the trees is generated and weighted according to the frequency with which they occur. The weighted splits are then displayed in a median network [START_REF] Bandelt | Phylogenetic Networks[END_REF]. These networks can be used to display any collection of weighted splits, and have some attractive properties. For example, in the case where the collection of splits corresponds to a tree (i.e. corresponds to the edges of a given phylogenetic tree), the associated median network is that tree. Moreover, median networks are straight-forward to generate using an algorithm first introduced in [START_REF] Bandelt | Mitochondrial portraits of human populations using median networks[END_REF], which has been implemented in the freely available programs Spectronet [START_REF] Huber | Spectronet: A package for computing spectra and median networks[END_REF] and jSplits (http://wwwab.informatik.uni-tuebingen.de/software/jsplits/welcome_en.html).

Even so, median networks can in general be rather complex, depending on the extent to which the displayed splits deviate from fitting into a tree [START_REF] Huber | Pruned median networks: a technique for reducing the complexity of median networks[END_REF]. To control this complexity it is convenient to quantify this deviation as follows. We say that two splits are incompatible if they can not be displayed simultaneously by any tree. Moreover, we say that a collection of splits is kcompatible if it contains no subcollection of k+1 pairwise incompatible splits. For instance, any collection of splits that can be displayed in a tree is 1-compatible, as it contains no pair of incompatible splits. Incompatible collections of splits are represented by high-dimensional hypercubes in median networks, which are difficult to visualize. Thus the parameter k is important since, for small k, collections of k-compatible splits are easier to visualize with median networks.

If the collection of splits has a high degree of incompatibility we can apply a filter to produce a subcollection of splits that has a lower degree of incompatibility, and hence results in a less complex network visualization. As with the strict and majority consensus methods, we discard those splits which are not displayed by more than some threshold proportion, 0<x≤1, of the trees. A crucial observation is that a collection of splits so generated is   1 / 1 x compatible (where   indicates rounding up to the nearest integer) (Holland and Moulton, 2003). For example, if x is 1 then the resulting consensus network will be the strict consensus tree, if x is 1/2 then the resulting consensus network will be the majority-rule tree, whereas, if x is 1/3 then the consensus network will be at most 2 dimensional, that is it may contain 2-cubes but no 3-cubes. For convenience, this result is stated with proof in the appendix.

Note that k-compatible split systems have been extensively studied [START_REF] Dress | 2nk-{(2k+1) choose 2}: A note on extremal combinatorics of cyclic split systems[END_REF], and are strongly related to circular split systems and weakly compatible split systems [START_REF] Bandelt | A canonical decomposition theory for metrics on a finite set[END_REF]. Such split systems and related phylogenetic networks-such as Split graphs [START_REF] Huson | SplitsTree: a program for analyzing and visualizing evolutionary data[END_REF]-could in principle be used as alternative methods for generating consensus networks (Holland and Moulton, 2003).

A Python script has been written that reads a list of trees in Newick format (bracket, comma notation) and produces the corresponding weighted split system in Nexus format. This file can be read by Spectronet [START_REF] Huber | Spectronet: A package for computing spectra and median networks[END_REF] which displays the corresponding consensus network.

Consensus networks can also be constructed using jSplits (http://www-ab.informatik.unituebingen.de/software/jsplits/welcome_en.html).

APPLICATIONS

The consensus network method has a wide range of potential applications. Here, we will focus on two biological examples that demonstrate its utility in displaying conflicting hypotheses existing in large collections of trees, which cannot be displayed using standard consensus tree analysis.

Indices of Phylogenetic Reliability and the Phylogeny of Placental Mammals

The sequencing and analysis of both mitochondrial and nuclear genes during the last decade has completely redefined our vision of the placental tree [START_REF] De Jong | Molecules remodel the mammalian tree[END_REF][START_REF] Waddell | Towards resolving the interordinal relationships of placental mammals[END_REF].

Recently, two large scale studies robustly identified for the first time four major placental clades: Afrotheria, Xenarthra, Euarchontoglires and Laurasiatheria, and a close relationship between the two latter ones [START_REF] Madsen | Parallel adaptative radiations in two major clades of placental mammals[END_REF]Murphy et al., 2001b). The subsequent combination of these two datasets proposed a fairly resolved picture of placental mammal relationships Murphy et al. (2001a).

This latest study has been criticized on the grounds that Bayesian posterior probabilities (PP) might provide, in this case and others, over estimation of phylogenetic reliability [START_REF] Suzuki | Overcredibility of molecular phylogenies obtained by Bayesian phylogenetics[END_REF]. In fact, large discrepancies between PP and other measures of statistical support such as nonparametric bootstrap proportions (BP) exist for a wide range of empirical studies (see Douady et al., 2003 and references therein), and the nature of the relationship between the two indices is still poorly understood from a theoretical point of view [START_REF] Huelsenbeck | Potential applications and pitfalls of Bayesian inference of phylogeny[END_REF]. These observations have recently generated a bloom of papers aiming at understanding the relation between the PP and BP indices [START_REF] Waddell | Very fast algorithms for evaluating the stability of ML and Bayesian phylogenetic trees from sequence data[END_REF][START_REF] Wilcox | Phylogenetic relationships of the dwarf boas and a comparison of Bayesian and bootstrap measures of phylogenetic support[END_REF][START_REF] Alfaro | Bayes or bootstrap? A simulation study comparing the performance of bayesian markov chain monte carlo sampling and bootstrapping in assessing phylogenetic confidence[END_REF][START_REF] Cummings | Comparing bootstrap and posterior probability values in the four-taxon case[END_REF][START_REF] Douady | Comparison of bayesian and maximum likelihood bootstrap measures of phylogenetic reliability[END_REF][START_REF] Erixon | Reliability of bayesian posterior probabilities and bootstrap frequencies in phylogenetics[END_REF][START_REF] Simmons | How meaningful are Bayesian support values?[END_REF]. Credibility values of the Bayesian phylogenetic inference seem to be excessively high under some circumstances [START_REF] Suzuki | Overcredibility of molecular phylogenies obtained by Bayesian phylogenetics[END_REF][START_REF] Cummings | Comparing bootstrap and posterior probability values in the four-taxon case[END_REF][START_REF] Douady | Comparison of bayesian and maximum likelihood bootstrap measures of phylogenetic reliability[END_REF][START_REF] Erixon | Reliability of bayesian posterior probabilities and bootstrap frequencies in phylogenetics[END_REF][START_REF] Simmons | How meaningful are Bayesian support values?[END_REF] whereas bootstrap percentages might be too conservative [START_REF] Hillis | An empirical test of boostrapping as a method for assessing confidence in phylogenetic analysis[END_REF][START_REF] Wilcox | Phylogenetic relationships of the dwarf boas and a comparison of Bayesian and bootstrap measures of phylogenetic support[END_REF][START_REF] Alfaro | Bayes or bootstrap? A simulation study comparing the performance of bayesian markov chain monte carlo sampling and bootstrapping in assessing phylogenetic confidence[END_REF]. Sensitivity to model misspecification has been suspected to be an important factor in the behaviour of PP [START_REF] Waddell | Very fast algorithms for evaluating the stability of ML and Bayesian phylogenetic trees from sequence data[END_REF] and the importance of model adequacy in Bayesian phylogenetic analyses has been recently outlined [START_REF] Lemmon | The importance of proper model assumption in Bayesian phylogenetics[END_REF]. A recent paper by [START_REF] Huelsenbeck | Frequentist properties of Bayesian posterior probabilities of phylogenetic trees under simple and complex substitution models[END_REF] attempted to put this controversy to rest. They concluded that the posterior probability of a tree can be interpreted as the probability that the tree is the true tree, with the very important proviso that the substitution model is correct. When the model is misspecified they found that posterior probabilities were biased upwards and that bootstrap values were more robust. As current substitution models are frequently likely to be misspecified [START_REF] Goldman | Statistical tests of models of DNA substitution[END_REF], these results suggest that both posterior probabilities and bootstrap values will continue to be of interest to practitioners. Some authors have also independently suggested computing Bayesian BP or bootstrapped PP (BP Bay ) as an alternative [START_REF] Waddell | Very fast algorithms for evaluating the stability of ML and Bayesian phylogenetic trees from sequence data[END_REF][START_REF] Douady | Comparison of bayesian and maximum likelihood bootstrap measures of phylogenetic reliability[END_REF]. While time consuming, this approach leads to Bayesian support values closer to the bootstrap percentages and allows the identification of excessively supported edges in a Bayesian framework. The debate on the relationships between BP and PP is reminiscent of the one engendered by the introduction of the quartet puzzling method [START_REF] Strimmer | Quartet puzzling: a quartet maximum-likelihood method for reconstructing tree topologies[END_REF] and its associated measure of edge support expressed as Reliability Percentages (RP). Indeed, it has been suggested that RP are generally higher than the corresponding BP [START_REF] Cao | Comment on the quartet puzzling method for finding maximum-likelihood tree topologies[END_REF].

We use the consensus network method to visualize the differences between the indices PP, BP ML , BP Bay , and RP by analysing the collections of trees produced by each method for the Murphy et al. (2001a) dataset. The application of this method also allows the visualisation of the remaining uncertainties in the placental mammal phylogeny.

The data set of Murphy et al. (2001a) consists of the concatenation of 22 genes (19 nuclear and three mitochondrial) representing a total of 16,397 unambiguously aligned nucleotide sites for 44 taxa. This includes 42 placentals distributed in Afrotheria (8 taxa), Xenarthra (3), Euarchontoglires (11) and Laurasiatheria (20), plus two marsupial outgroups. A schematic overview of the experimental design we used to compare the four indices of phylogenetic reliability is presented in Figure 2.

The Bayesian analysis of the original dataset was conducted using MrBayes version 3.0b4 [START_REF] Ronquist | MrBayes 3: Bayesian phylogenetic inference under mixed models[END_REF]. Four incrementally heated Metropolis-coupled Markov chains Monte Carlo (MCMCMC) were simultaneously run for 1,000,000 generations, using the programs default uninformative priors as starting values for trees, edge lengths and model parameters. We used the GTR+Ι+Γ 4 model of sequence evolution estimated to be the best fitting model by Modeltest 3.06 [START_REF] Posada | MODELTEST: testing the model of DNA substitution[END_REF]. Trees were sampled every 100 generations resulting in a collection of 10,000 MCMCMC sampled trees. We discarded the first 5,000 trees as a conservative burn-in to minimize the risk of making inferences before the convergence of the chains. A consensus network of the remaining 5,000 trees was constructed using a 10% threshold which implies that only splits that appeared in more than 500 of the 5,000 trees were included (Fig. 3A).

For the bootstrap-based analyses, we generated 100 nonparametric bootstrap pseudoreplicates of the original dataset using the program SEQBOOT of the PHYLIP version 3.6a3 package [START_REF] Felsenstein | PHYLIP (PHYLogeny Inference Package) version 3[END_REF]. These bootstrap datasets were then subsequently analysed under the maximum likelihood criterion with PAUP* version 4.0b10 [START_REF] Swofford | PAUP*. Phylogenetic Analysis Using Parsimony (* and Other Methods)[END_REF] using the parameters of the GTR+Ι+Γ 4 model previously estimated by Modeltest on the original dataset. The ML heuristic searches were conducted with a Neighbour-Joining (NJ) starting tree and the Tree Bisection Reconnection branch swapping algorithm. A consensus network of the 100 resulting ML trees was then constructed using a 10% threshold (Fig. 3B). The same 100 bootstrap datasets were also analysed under the Bayesian approach as described in [START_REF] Douady | Comparison of bayesian and maximum likelihood bootstrap measures of phylogenetic reliability[END_REF]. For each dataset, the Bayesian analysis was performed under exactly the same conditions as the original dataset described above. These analyses resulted in 10,000 MCMCMC sampled trees for each bootstrap dataset, the first half of each run was discarded as the burn-in. A consensus network of the 100 x 5,000 = 500,000 remaining trees was constructed using a 10% threshold (Fig. 3C).

The maximum likelihood quartet puzzling method was implemented using the program Tree-Puzzle version 5.0 [START_REF] Schmidt | TREE-PUZZLE: maximum likelihood phylogenetic analysis using quartets and parallel computing[END_REF]. Quartets were analysed under the TN+Ι+Γ 4 model of sequence evolution (the most general model available). The model parameters were estimated during the search and the analysis resulted in 10,000 quartet puzzling trees. A consensus network of these 10,000 was constructed using a both 10% and 25% thresholds. However, since the consensus network obtained with the 10% threshold was rather complex we chose to present the 25% threshold network (Fig. 3D).

The consensus networks computed for the collections of trees obtained by the four strategies are presented in Figure 3. The consensus network built using the trees resulting from the Bayesian analysis is very tree-like, displaying only two 2-cubes (Fig 3A). All internal edges are fully resolved except the relationships among Paenungulata (elephant, hyrax and sirenian) within Afrotheria and the interrelationships of Ostentoria (pangolin and carnivores), Perissodactyla (horse, rhino and tapir) and Cetartiodactyla (llama, pig, ruminant, hippo and whale) within Laurasiatheria.

Unlike the 50% majority rule consensus tree usually computed to obtain PP, the consensus network allows the identification of two main competing hypotheses among the three possible schemes of interrelationships for each of the two polytomies. As pointed out in the original publication (Murphy et al., 2001a), the Bayesian analysis seems to resolve the central question of the position of the root by supporting the early emergence of Afrotheria within placentals.

In contrast, the ML bootstrap consensus network reveals a congruent but less resolved picture of the placental mammal's phylogenetic relationships with the occurrence of both 2-cubes and 3cubes (Fig. 3B). Some of the 2-cubes such as the one observed within Chiroptera (bats) are elongated rectangles indicating that one of the two alternative hypotheses is only marginally supported by the data. This is also the case in the 3-cube depicting the relationships among paenungulates where the hypothesis of a close relationship between the elephant and the sirenian appears much less likely than the other two which are almost equally supported. However, the occurrence of multiple 3-cubes within Laurasiatheria indicates that the relationships among Chiroptera, Ostentoria, Perissodactyla and Cetartiodactyla are left unresolved by the ML bootstrap analysis. Interestingly, the ML bootstrap consensus network reveals that two alternative hypotheses for the position of the root coexisted in this dataset. The early emergence of Afrotheria remains the most likely, but the hypothesis of a close relationship between Afrotheria and Xenarthra, named the Atlantogenata hypothesis [START_REF] Waddell | Towards resolving the interordinal relationships of placental mammals[END_REF], appears in some of the bootstrap trees. The third hypothesis of an early emergence of Xenarthra within placentals, the classical morphologically based Epitheria hypothesis [START_REF] Mckenna | Toward a phylogenetic classification of the Mammalia[END_REF], is apparently not supported by this data. Given the contrasting levels of resolution observed between the Bayesian and ML bootstrap consensus networks, the consensus network visualization tends to support the observation that posterior probabilities are generally higher than the corresponding bootstrap values. This illustrates the fact that the collection of trees sampled in the Bayesian analysis are more restricted in the treespace than the bootstrap trees.

The application of the bootstrap to the Bayesian method yielded a consensus network very similar to the ML bootstrap consensus network (Fig. 3C). Minor differences between the two networks involve the appearance in the Bayesian bootstrap consensus network of an additional 2cube for the position of Eulipotyphla (hedgehog, mole and shrew) within Laurasiatheria and the disappearance of the 2-cube linking Primates to the grouping of tree-shrew and flying lemur. Apart from these differences, the two networks agree on the lack of resolution for the relationships within Laurasiatheria and among Paenungulata. The same hierarchy of hypotheses is observed for the position of the root, with the early emergence of Afrotheria being favoured over Atlantogenata.

These results support the fact that the application of the bootstrap resampling to the Bayesian method leads to values comparable to the ML bootstrap ones. This confirms the utility of this approach for computing bootstrap support values in a Bayesian framework allowing the implementation of complex models of sequence evolution [START_REF] Waddell | Very fast algorithms for evaluating the stability of ML and Bayesian phylogenetic trees from sequence data[END_REF][START_REF] Douady | Comparison of bayesian and maximum likelihood bootstrap measures of phylogenetic reliability[END_REF].

In striking contrast to the other methods, the quartet puzzling based consensus network computed with a 10% threshold was highly unresolved and complicated by the occurrence of hypercubes (data not shown). Therefore, we present the consensus network obtained with a more stringent 25% threshold (Fig 3D). This led to a more tree-like consensus network roughly compatible with the ones obtained for the other methods. However, some of the 2-cubes do not appear in the other consensus networks such as the one disrupting the otherwise strongly supported monophyly of Afrotheria or two additional 2-cubes within rodents. It is noteworthy that the position of the root appears particularly unresolved with this method compared to the others. This might reflect the fact that phylogenetic reconstruction based on quartets of species is highly sensitive to rate variation between the taxa involved in the quartet [START_REF] Philippe | The pitfalls of molecular phylogeny based on four species, as illustrated by the Cetacea/Artiodactyla relationships[END_REF]Adachi and Hasegawa 1996a;[START_REF] Ranwez | Quartet-based phylogenetic inference: improvements and limits[END_REF]. Indeed, the marsupials used here as outgroups are very divergent from the placentals in terms of base composition and substitution patterns, likely leading to tree-reconstruction artefacts in the quartets in which they are involved.

The presence of quartets that support conflicting positions of marsupials relative to the placentals might be responsible for the observed 2-cubes at the root of the placental tree. The extreme sensitivity of quartet-based methods of phylogenetic reconstruction to systematic biases such as long-branch attraction phenomena [START_REF] Felsenstein | Cases in which parsimony or compatibility methods will be positively misleading[END_REF][START_REF] Hendy | A framework for the quantitative study of evolutionary trees[END_REF] and their tendency to led to too symmetrical topologies have been shown to be responsible for the general limitations of this kind of method [START_REF] Ranwez | Quartet-based phylogenetic inference: improvements and limits[END_REF].

The results obtained from the application of the consensus network method highlight the remaining uncertainties in the placental mammal phylogeny by allowing the visualisation of competing hypotheses coexisting in the Murphy et al. (2001a) dataset for different edges (Fig. 5).

Hence, one of the most puzzling questions remains the branching order between Ostentoria (pangolins and carnivores), Perissodactyla (odd-toed ungulates) and Cetartiodactyla (even-toed ungulates) with two competing hypotheses appearing as equally likely even based on the Bayesian analysis: Ostentoria + Perissodactyla or Cetartiodactyla + Perissodactyla. Similarly, the tricky problem of paenungulates relationships is left unresolved by the sequence data with the classical morphologically-based Tethytheria hypothesis [START_REF] Mckenna | Toward a phylogenetic classification of the Mammalia[END_REF] of a close relationship between elephants and sirenians in fact appearing to be the only one to be strongly rejected (Amrine- Madsen et al., 2003). However, the central question remaining is the position of the root. Indeed, the rooting of the placental tree is still unstable mainly because of the high degree of divergence observed between marsupials and placentals [START_REF] Delsuc | Molecular phylogeny of living xenarthrans and the impact of character and taxon sampling on the placental tree rooting[END_REF]. Recent additional sequence data still fail to statistically resolve the question (Amrine- Madsen et al., 2003). The study of indels in protein sequences has been shown to prove useful by constraining the rooting possibilities [START_REF] De Jong | Indels in protein-coding sequences of Euarchontoglires constrain the rooting of the eutherian tree[END_REF]. The study of rare genomic changes such as protein sequence signatures or indels and SINEs insertions might also be required to distinguish between the alternative hypotheses revealed by the consensus network method in order to firmly resolve the remaining uncertainties in the phylogeny of placental mammals.

Amino-acids versus Nucleotides and the Origin of Hexapods

Recent analyses of mitochondrial data have raised a controversy on the origins of six-legged arthropods (hexapods). Analysing a concatenation of the four most conserved genes of the mitochondrial genome (COXI, COXII, COXIII, CYTB), Nardi et al. (2003a) found strong support for the paraphyly of hexapods due the emergence of two collembolan species before crustaceans and the other hexapod taxa. These results imply that the colonisation of land by hexapods happened at least twice, and that the developmental and morphological features shared by collembolans and others hexapods consequently arose by convergence (Nardi et al., 2003a;[START_REF] Thomas | Wingless insects and plucked chickens[END_REF].

However, it has been shown that nucleotide-based phylogenetic analyses of the initial 35-taxa dataset of Nardi et al. (2003a) can support the retrieval of the respective monophyly of insects and hexapods when RY (purine-pyrimidine) coding is used to alleviate the compositional bias at 1 st and 3 rd codon positions [START_REF] Delsuc | Comment on "Hexapod origins: monophyletic or paraphyletic?[END_REF]. Furthermore, the analysis of nucleotides with RY-coded 3 rd codon positions from a 25-taxa dataset-excluding both closely related and rapidly evolving taxa-confirmed the previous results in supporting hexapod monophyly with a high Bayesian posterior probability (0.99) but with a ML bootstrap value of only 57 [START_REF] Delsuc | Comment on "Hexapod origins: monophyletic or paraphyletic?[END_REF]. The Bayesian analysis of the amino-acids of this 25-taxa dataset yielded a tree where hexapods were still paraphyletic but with a moderate posterior probability value of 0.70 (Nardi et al., 2003b).

Although not statistically decisive, these analyses showed that two contradictory signals concerning the origin of extant hexapods seemed to coexist in this mitochondrial dataset and that their relative strengths appeared to depend upon the use of amino-acid or nucleotide characters. Here, we have used the consensus network representation to examine the extent of the conflicting signals contained in this dataset by analysing the collection of trees produced by maximum likelihood bootstrap and Bayesian analyses of the nucleotides and corresponding amino-acids of the 25-taxa dataset of [START_REF] Delsuc | Comment on "Hexapod origins: monophyletic or paraphyletic?[END_REF].

To make things comparable, the 25-taxa dataset of [START_REF] Delsuc | Comment on "Hexapod origins: monophyletic or paraphyletic?[END_REF] containing 3,777 aligned nucleotide sites was translated into the 1,259 corresponding amino-acid sites using MEGA version 2.1 [START_REF] Kumar | MEGA2: molecular evolutionary genetics analysis software[END_REF]. The Bayesian analysis of the nucleotide dataset with RY-coded 3 rd codon positions was conducted with MrBayes using a partitioned-likelihood model attributing a GTR+Ι+Γ 8 model to the 1 st and 2 nd codon positions and a two-state substitution model +Ι +Γ 8 to the RY-coded 3 rd codon positions. For the amino-acid dataset, we used the empirical mitochondrial MtRev substitution matrix +Ι+Γ 8 (Adachi and Hasegawa, 1996b). For both datasets, five incrementally heated MCMCMC chains were simultaneously run for 1,000,000 generations, using the programs default uninformative priors as starting values for trees, edge lengths and model parameters. Trees were sampled every 10 generations leading to a collection of 100,000 MCMCMC sampled trees whose first 50,000 were discarded as a the burn-in period of the chains.

Consensus networks of the remaining 50,000 trees were constructed using a 10% threshold which implies that only splits that appear in more than 5,000 of the 50,000 trees were displayed.

Maximum likelihood bootstrap analyses of the two datasets were performed by analysing 100 bootstrap resampled datasets generated by SEQBOOT using PHYML version 2.0.3 [START_REF] Guindon | A simple, fast, and accurate algorithm to estimate large phylogenies by maximum likelihood[END_REF]. The use of this very fast ML program allowed parameters to be estimated for each replication in a reasonable computation time. As 3 rd codon positions were RY-coded in the nucleotide dataset, we independently generated the bootstrap pseudo-replicates from each of the three codon positions using the same random seed in SEQBOOT. This ensured that the proportion of each codon position was kept constant in each bootstrap resampled dataset. These concatenated bootstrap datasets were then analysed under the GTR+Ι+Γ 8 model with PHYML. The amino-acid bootstrap resampled datasets were analysed under the MtRev+Ι+Γ 8 model. Consensus networks of the 100 ML bootstrap trees obtained for each of the two datasets were constructed using a 10% threshold.

The consensus networks obtained for the ML bootstrap and Bayesian analyses of the aminoacids and nucleotides of the 25-taxa dataset are compared in Figure 4. The Bayesian analysis of both amino-acid and nucleotide datasets yielded notably tree-like consensus networks (Fig. 4A,B), compared to the ML bootstrap analyses of the same datasets which led to consensus networks with many 3-cubes (Fig. 4C,D). As seen in the previous example, this highlights the differences between the two methods, the collections of trees sampled by the Bayesian analysis being much more restricted in tree space than the ML bootstrap ones. The question of the monophyletic or paraphyletic origin of hexapods relies on the interrelationships between crustaceans (CRU), collembolans (COL), and insects (INS) for which classical phylogenetic analyses of nucleotides and amino-acids appears to conflict in supporting hexapod monophyly [START_REF] Delsuc | Comment on "Hexapod origins: monophyletic or paraphyletic?[END_REF] or paraphyly (Nardi et al., 2003b), respectively. The consensus network representation sheds light on this apparent conflict. It reveals that if the Bayesian analysis of nucleotides indeed supports hexapods monophyly with a split clearly separating crustaceans from collembolans and insects (Fig. 4B), the collection of trees coming from the Bayesian analysis of amino-acids contain two competing signals pertaining to the origin of hexapods (Fig. 4A). Indeed, the consensus network displays a 2-cube (Fig. 4A) according almost the same credit to the hypothesis of hexapod monophyly (COL+INS) as to their paraphyly (CRU+INS). The comparison of the ML bootstrap consensus networks also shows that there is less signal pertaining to the question of hexapod origins in the amino-acid dataset (Fig. 4C) than in the nucleotide data (Fig. 4D). In fact, in the amino-acid consensus network, the relationships between crustaceans, collembolans and insects are depicted by a complex network (Fig. 4C), whereas the nucleotide consensus network reveals a split in favour of hexapod monophyly that clearly separates crustaceans from collembolans and insects (Fig. 4D) as in the Bayesian nucleotide consensus network (Fig. 4B).

Overall, the consensus network results on arthropods phylogeny indicate that there is simply not enough signal in these datasets, especially in the amino-acid data, to adequately resolve the position of collembolans. This result is not necessarily surprising given the relatively short length of the datasets (3,777 nucleotide or 1,259 amino-acid sites) and the divergence level under scrutiny [START_REF] Philippe | How good are deep phylogenetic trees?[END_REF]. Indeed, mitochondrial genes are likely to contain sites that have undergone many substitutions, causing difficulties for phylogenetic reconstruction between the major arthropod lineages. Such difficulties have already been observed for much younger divergences such as the ones between placental mammal orders [START_REF] Springer | Mitochondrial versus nuclear gene sequences in deep-level mammalian phylogeny reconstruction[END_REF]. These considerations have led to the preferential analysis of amino-acid characters for this dataset (Nardi et al., 2003a,b). However, it has been demonstrated that amino-acid characters do not necessarily outperform nucleotides even at deep phylogenetic levels [START_REF] Simmons | Amino acid vs. nucleotide characters: challenging preconceived notions[END_REF], especially when there is compositional bias in the data [START_REF] Foster | Compositional bias may affect both DNA-based and proteinbased phylogenetic reconstructions[END_REF]. These results are in agreement with the fact that RY-coding the mtDNA nucleotide datasets of Nardi et al. (2003) produces the more generally accepted result of arthropod monophyly [START_REF] Delsuc | Comment on "Hexapod origins: monophyletic or paraphyletic?[END_REF]. It is thus worth noting that the consensus network of the relatively conservative ML bootstrap analysis of nucleotides, displays a split that supports the classically admitted monophyly of hexapods by clearly separating them from crustaceans (Fig. 4D). For this reason, it appears safe to consider the hypothesis of hexapod paraphyly (Nardi et al., 2003a) as no more than a working hypothesis that needs to be tested further by the future analysis of more slowly evolving nuclear genes. Interestingly, recent improved analyses of the nuclear small subunit rRNA (18S) retrieved the monophyly of hexapods including collembolans, especially when using rRNA specific alignment and substitution models [START_REF] Kjer | Aligned 18S and insect phylogeny[END_REF].

DISCUSSION

We have introduced a consensus method that extends the notion of strict and majority consensus trees to allow the display of conflicting evolutionary hypotheses within a collection of trees using a network. This method can be used in conjunction with many existing phylogenetic techniques that generate large sets of trees such as bootstrapping, Bayesian inference, and quartet puzzling. It might also be applicable in case the trees are generated from multiple data sets (such as gene trees), but this requires additional analysis which will be presented elsewhere. Consensus networks are intended as a visualisation tool rather than as a confidence set of trees (although they might be a useful display of a confidence set). Their interpretation differs depending on the source of the trees being displayed. For instance, a consensus network of bootstrap trees has a different interpretation to a consensus network of trees from a MCMC Bayesian analysis, which has a different interpretation again to a set of equally scoring parsimony trees.

While consensus networks, like other network methods such as median networks and split decomposition, are capable of displaying incompatible split systems, unlike median networks they do not become too visually complex. This is because the dimensionality of the consensus network can be controlled by choosing an appropriate threshold value. The worst case complexity is described in the appendix, but in practice we found that it was easy to use Spectronet and jSplits to experiment with thresholds that produced 2 or 3 dimensional networks, and that the thresholds used were typically much lower than the theoretical worst case would suggest. For example, many of the networks presented here use a threshold of 10%, which means they could in theory contain 9dimensional hypercubes, however, in practice this is not observed. One way to quickly choose an appropriate threshold value would be to examine the output produced by PAUP* bootstrap runs or the MrBayes sumt command to see how many splits have above, say 20% or 10% support.

Consensus networks and split decomposition [START_REF] Bandelt | A canonical decomposition theory for metrics on a finite set[END_REF]) could be used in combination as the two methods have different limitations and advantages. Split decomposition represents distance data as a set of weighted weakly compatible splits, where the weight for each split is a function that is minimised over all quartets (subsets of size four). The nature of this function means that for large data sets the method tends to produce star-like topologies with little resolution. In addition split decomposition will never produce a split system with three mutually incompatible splits. Consensus networks do not have these limitations but they could give a misleading picture when tree estimation suffers from systematic bias. For example, in the "Felsenstein zone" for parsimony [START_REF] Felsenstein | Cases in which parsimony or compatibility methods will be positively misleading[END_REF] you might get 100% bootstrap support for the wrong tree, in this case the consensus network of the bootstrap trees would show no conflict but a split decomposition network could display that the data does have conflicting signal.

We applied the consensus network technique to two biological data sets. Consensus networks helped identify areas of uncertainty that remain in the placental mammal phylogeny and understand to what degree the competing hypotheses have support in the data of Murphy et al. (2001a). The networks make it possible to compare the different levels of support for clades that are conferred using either an ML bootstrap or Bayesian approach. The results support the findings of various authors [START_REF] Waddell | Very fast algorithms for evaluating the stability of ML and Bayesian phylogenetic trees from sequence data[END_REF][START_REF] Wilcox | Phylogenetic relationships of the dwarf boas and a comparison of Bayesian and bootstrap measures of phylogenetic support[END_REF][START_REF] Suzuki | Overcredibility of molecular phylogenies obtained by Bayesian phylogenetics[END_REF][START_REF] Alfaro | Bayes or bootstrap? A simulation study comparing the performance of bayesian markov chain monte carlo sampling and bootstrapping in assessing phylogenetic confidence[END_REF][START_REF] Cummings | Comparing bootstrap and posterior probability values in the four-taxon case[END_REF][START_REF] Douady | Comparison of bayesian and maximum likelihood bootstrap measures of phylogenetic reliability[END_REF][START_REF] Erixon | Reliability of bayesian posterior probabilities and bootstrap frequencies in phylogenetics[END_REF][START_REF] Simmons | How meaningful are Bayesian support values?[END_REF] that Bayesian posterior probabilities are generally more extreme than the corresponding ML bootstrap values. The consensus network approach also confirms that the method independently suggested by [START_REF] Waddell | Very fast algorithms for evaluating the stability of ML and Bayesian phylogenetic trees from sequence data[END_REF] and [START_REF] Douady | Comparison of bayesian and maximum likelihood bootstrap measures of phylogenetic reliability[END_REF] of computing a bootstrap-based measure of phylogenetic reliability in a Bayesian framework represents a valuable alternative to posterior probabilities. Consensus networks also shed light on apparently conflicting results for hexapod monophyly using either nucleotide or amino acid characters. As the networks are capable of displaying conflicting hypotheses it was easy to see that the amino acid data has quite strong support for both trees where hexapods are monophyletic, and trees where they have paraphyletic origins. This information would have been lost in a standard consensus tree analysis in which the two data sets would have appeared to be in conflict.

Many phylogenetic techniques expend significant computational effort to generate large sets of trees, it is not only wasteful to throw away much of the information by restricting their display to a single tree, but it can also be misleading since it is the conflicting signals that are often of most interest to evolutionary biologists. For example, this kind of approach might be useful for representing multiple gene trees, particularly for organisms such as Bacteria and Archea, whose genomes underwent numerous horizontal gene transfer events and for which the adequate representation might be a phylogenetic tree of the "core" untransferred genes nested within a network of all genes [START_REF] Philippe | Horizontal gene transfer and phylogenetics[END_REF].

ACKNOWLEDGMENTS

Calculations were conducted using the Helix supercomputing facility of the Allan Wilson Centre for Molecular Ecology and Evolution, consisting of a cluster of 66 dual-processor AMD Athlon © computing nodes (http://awcmee.massey.ac.nz/helix-service.htm). Tim White provided invaluable assistance in setting up the calculations on the Helix supercomputer. Mark S. Springer

APPENDIX

We briefly describe the result indicated in the Consensus Network Method section. Suppose that X is a finite set. A split A|B of X is a bipartition of X, i.e. a partition of X into two non-empty sets A and B with X B A = ∪ and B A ∩ = Ø. We call a collection of splits a split system for short.

A split system is called compatible if there is a phylogenetic tree that displays every split in the system (see Method section). We say that a split system is incompatible if it contains no subset of cardinality two that is compatible. Note that a split system which is not compatible need not be incompatible. For k a positive integer, we say that a split system is k-compatible if it contains no incompatible subset of splits with cardinality k+1.

The concept of k-compatibility was introduced and studied in [START_REF] Dress | 2nk-{(2k+1) choose 2}: A note on extremal combinatorics of cyclic split systems[END_REF]. By definition, a k-compatible split system is compatible if and only if k=1, in which case the median network associated to it must be a tree, but, as k increases, the associated median network can become progressively more complex. We now state the main result of Holland and Moulton (2003).

Theorem ---Given N phylogenetic trees each with leaf set X and some 1 0 ≤ < x , let S x denote the split system containing those splits of X that are displayed in  

Nx or more of these trees. Then

S x is   x 1 -compatible.
Proof ---Suppose that S x contains   x 1 + 1 incompatible splits. Then, since each of these splits is displayed by at least   Nx of the trees, it follows by the Pigeonhole Principle that one of the trees must display at least two of the incompatible splits. But this is impossible. This result allows control of the complexity of the median network associated to the split system: Larger values of x imply a lower extent of incompatibility in the split system S x . Note that in case x = 1, the median network associated to split system S x will be the strict consensus tree associated to the phylogenetic trees, and that if x=1/2, the associated median network will be the majority rule consensus tree.

Figure captions

Figure 1:

The strict consensus tree (C), majority consensus tree (D), and consensus network (E) for three trees (A). Each edge in a phylogenetic tree corresponds to a split or bipartition of the taxa set, as removing an edge from a tree divides it into two subtrees, which also partitions its labels. The pendent edges always appear in a phylogenetic tree -these correspond to trivial splits that separate one taxon from the rest. All the non trivial splits displayed in the trees are listed in the weighted splits box (B).

  kindly sent the aligned mammalian data set. Christophe Douady and Emmanuel Douzery provided helpful comments on early versions of the manuscript. Suggestions from Chris Simon, Allan J. Baker and George F. Barrowclough improved the latest version of the manuscript. The authors thank The Swedish Foundation for International Cooperation and Research in Higher Education (STINT), and The Linnaeus Centre for Bioinformatics for their support. FD acknowledges the support of a Lavoisier Postdoctoral Grant from the French Ministry of Foreign Affairs.

Figure 2 :

 2 Figure 2:

Figure 3 :

 3 Figure 3:

B

  . Consensus network (10% threshold) of the 100 trees computed in the Maximum Likelihood analyses of the 100 nonparametric bootstrap resampled datasets. These trees are usually used to compute Maximum Likelihood Bootstrap Proportions (BP ML ).C. Consensus network (10% threshold) of the 500,000 trees computed in the Bayesian analyses of the 100 nonparametric bootstrap resampled datasets. These trees can be used to calculate Bayesian Bootstrap Proportions (BP Bay ). D. Consensus network (25% threshold) of the 10,000 trees computed in the quartet puzzling analysis of the original dataset. These trees are usually used to obtain Reliability Percentages (RP).

Figure 4 :

 4 Figure 4: