Luiz-Angelo Steffenel

Christophe Jaillet

Olivier Flauzac

Michael Krajecki

Impact of nodes distribution on the performance of a P2P computing middleware based on virtual rings

P2P computing middlewares are interesting options for grid computing applications that require scalability and resiliency. Nevertheless, most P2P computation systems rely on partially centralized or hybrid decentralized architectures to distribute tasks and collect the results, raising fault tolerance and bottleneck issues. CONFIIT (Computation Over Network with Finite number of Independent and Irregular Tasks) is a purely decentralized middleware for grid computing, relying on a virtual ring for topology management and for task scheduling. This paper evaluates the impact of node placement and task granularity on the performance of CONFIIT. We analyze how CONFIIT handles different distribution scenarios in a grid environment while solving the well-known Langford permutation problem.

I. INTRODUCTION

During many years, computation and storage were done in a local way. A few years ago, a new approach emerged: the distribution of computation and storage over a network. This new approach tends to the use of all available computational resources from a local network, and to a larger scale, from the Internet. This new paradigm is called grid computing. In [START_REF] Foster | Computational Grids[END_REF], authors discussed arising issues related to this new paradigm, and explained how to design efficient grid based solutions.

CONFIIT, introduced in [START_REF] Flauzac | CONFIIT: a middleware for peer to peer computing[END_REF], is a purely decentralized peerto-peer middleware. It was designed to cope with joining the computation means to be used on a local area network or on the Internet, all while providing fault tolerance and autonomy to the peers. This paper focuses on the impact of nodes placement on the communication performance when using the distributed mode of CONFIIT. Because CONFIIT relies on a virtual ring, the token passing mechanism is intrinsically bound to the network speed and the ring circumference. Using the well-known Langford's combinatorial problem as a test subject, we try to verify the impact of nodes placement in the overall system performance when deploying CONFIIT over a country-wide grid environment.

The rest of this paper is organized as follows: firstly, we present some issues in grid computing. Section III describes the CONFIIT framework. We detail how the topology management is used to improve robustness, and how tasks are locally and globally scheduled on processors. Section IV illustrates how the Langford's combinatorial problem can be implemented in this computing model. After its description, experimental results in a grid environment are presented in order to observe the impact of nodes placement in the overall performance. Finally, Section VI presents our conclusions.

II. RELATED WORKS

The grid computing concept appeared in the 90's, as an extension on the Internet of the cycle stealing principle. Former applications aimed to crack by exhaustive search encryption keys based on RC5 or DES algorithms. They showed the opportunity of aggregating hundreds of PCs to solve a problem. Web-based Computing projects arose at the end of the 90's, as Charlotte [START_REF] Baratloo | Charlotte: Metacomputing on the web[END_REF], Bayanihan [START_REF] Sarmenta | Towards bayanihan: builing an extensible framework for volonteer computing using java[END_REF] or SETI@home [START_REF] Anderson | A new major seti project based on project serendip data and 100,000 personal computers[END_REF], [START_REF] Anderson | SETI@home: An experiment in public-resource computing[END_REF].

Indeed, the SETI@home project [START_REF] Anderson | A new major seti project based on project serendip data and 100,000 personal computers[END_REF], [START_REF] Anderson | SETI@home: An experiment in public-resource computing[END_REF] popularized the Global Computing concept. It was designed for Searching ExtraTerrestrial Intelligence, distributing tasks on thousands of computers on Internet. The current version of the project is based on the BOINC platform [START_REF] Anderson | BOINC: A system for public-resource computing and storage[END_REF], and gathers more than 30 TeraFlops simultaneously. It has already produced more than the equivalent of 500,000 years of computation on a PC. After SETI@home, dozens of academic or industrial projects were developed. In the former world, projects are often dedicated to a single application (as Distributed.net) or propose complete environments: XtremWeb1 or OurGrid 2 .

Grid applications are currently designed for two main purposes: data sharing and distributed computation. Whereas data sharing applications aim to share and recover data through a network, distributed computation applications aim to share a computation over a network and build a global solution. In the remaining of this paper, we will focus almost exclusively on distributed computation grid applications. Hence, the grid related issues can be classified in three main categories.

(i) applications specially designed to compute a particular problem. The most known application of that category is the SETI project, designed to Search for Extra Terrestrial Intelligence. (ii) protocols and libraries, put together to help in writing a dedicated grid application. JXTA project is an example of this category [START_REF] Li | Jxta 2: A high-performance, massively scalable p2p network[END_REF]. It proposes a peer-to-peer communication protocol, platform and language independent. (iii) middlewares offering different services (grid construction and management, task sharing management and results gathering). In this last group we can find Globus [START_REF] Foster | Globus: A metacomputing infrastructure toolkit[END_REF], [START_REF] Allcock | Globus toolkit support for distributed data-intensive science[END_REF], XtremWeb [START_REF] Fedak | XtremWeb: A generic global computing system[END_REF], DIET [START_REF] Caron | A scalable approach to network enabled servers[END_REF] or ProActive [START_REF] Baduel | Grid Computing: Software Environments and Tools[END_REF]. Whatever the application is, and whatever the means are, a grid based application has to verify some properties to be efficient [START_REF] Foster | The anatomy of the grid: Enabling scalable virtual organizations[END_REF], [START_REF] Foster | Grid services for distributed system integration[END_REF]: (1) sharing hardware and software capacities and capabilities, (2) scheduling the use of these means and the capability of peer-to-peer computation over Internet. F. Capello presented the topical issues of peer-to-peer globalized computation system in [START_REF] Cappello | Calcul global pair à pair : extension des systèmes pair à pair au calcul[END_REF].

Notice that authors propose partially centralized, or hybrid decentralized architecture, in most cases [START_REF] Androutsellis-Theotokis | A survey of peer-to-peer file sharing technologies[END_REF]. For example, DIET is a hierarchically centralized system: global information is maintained in replicated servers, called Master Agents, and a given computer organization is managed by Local Agents. Also, the BOINC [START_REF] Anderson | BOINC: A system for public-resource computing and storage[END_REF] framework consists of two layers that operate under the client-server architecture.

III. CONFIIT MIDDLEWARE A. FIIT applications

The notion of FIIT applications was defined in [START_REF] Krajecki | An object oriented environment to manage the parallelism of the FIIT applications[END_REF], and they are composed by a Finite number of Independent and Irregular Tasks (FIIT). We assume that each task satisfies the following features:

• A task cannot make any hypothesis on the execution of any other one. Hence, there is no communication between tasks.

• Execution time of each task is unpredictable. In other words, we cannot have a good estimation of the execution time before a task ends. • A same algorithm is applied to compute all tasks. Hence, two tasks are distinguished by the set of data they have to process. The well-known Mandelbrot's set [START_REF] Dewdney | Récréation informatiques : un microscope informatique pour observer l'objet le plus complexe jamais défini par les mathématiciens[END_REF] can be seen as a FIIT application: each pixel (or set of pixels) can be computed independently from the others, and its computation time is unpredictable since it depends on the corresponding region. In such a framework, the programmer needs to decide on how to divide the problem into a finite number of independent tasks, and how to compute each individual task.

The choices carried out are significant: decomposition granularity (number of tasks) influences load-balancing quality and impacts the use of the interconnection network [START_REF] Willebeek-Lemair | Strategies for dynamic load balancing on hightly parallel computers[END_REF]. If the problem is divided into too small tasks, scheduling will induce too much communication. Conversely, if the number of tasks is too small in comparison with the number of nodes, resolution will not able to exploit available parallelism. Thus, decomposition has to be adapted to the underlying computing environment (nodes architecture and interconnection network).

B. CONFIIT outline

CONFIIT (Computation Over Network for FIIT), introduced in [START_REF] Flauzac | CONFIIT: a middleware for peer to peer computing[END_REF], is a middleware for peer-to-peer computing. It aims to:

• distribute over the network all the tasks obtained by decomposition of a FIIT problem,

• solve each distributed task,

• spread computed results of each task over the network. Each computer collaborating in a CONFIIT computation is called a node. A node is set up with three main basic thread components: a topology and communication manager, a tasks manager and one or several task solvers.

The nodes are connected according to a logical oriented ring, set up and maintained by the topological layer of the system. Basically, each node knows its predecessor and successor. Communication between nodes are achieved using a token, which carries the state of computation around the ring and ensures load balancing between nodes. Task status are exchanged to broadcast local knowledge on all nodes, and thus, to compute an accurate global view of the calculus. At the end of the computation, the ring spreads termination on nodes.

Typically, one tasks solver should be launched for each processor on the node. A task manager can cope with several tasks solvers. Over and above the main thread elements, each node owns a set of data representing the local known state of the global computation.

All CONFIIT parts are written in Java. A node runs a daemon, performing topology, communication and tasks managements, and one or several solvers in separate Java Virtual Machine. Each solver is dedicated to a specific running computation, and can be duplicated if the application is to be executed by more than one processor.

A node owns the different parameters of the current computations (a list of tasks and associated results). It is able to set up its local parameters of tasks to be computed. At the beginning of a computation, all tasks are marked as uncomputed. When a task is completed (locally), its result is stored and will be propagated to the whole ring with the token. To prevent loss of time, the task manager schedules a new task without waiting for the token. But the task could have already been scheduled by another node, and will be replicated in the ring. So, the local list of tasks owned by a node is randomly rearranged. Thus, when the task manager picks up the n th task, it probably will be different from the n th task on another node [START_REF] Flauzac | CONFIIT: a middleware for peer to peer computing[END_REF], [START_REF] Krajecki | An object oriented environment to manage the parallelism of the FIIT applications[END_REF]. This strategy also guarantees the termination of the computation regardless node faults.

C. Managing the CONFIIT community

To achieve robustness according to computer crashdowns and dynamic evolution, CONFIIT maintains a central structure representing the ring topology. Each node participating in the computation is known by the others. Information is stored in a local structure. The mechanism involves a k-tolerance to recover a functional ring when k successive nodes simultaneously fail in a n-sized ring (k ≤ n).

As data are locally stored, a distributed mechanism must be performed to maintain a global view of the ring in each node. If we assume the token for computational state follows the logical ring clockwise, changes in the ring topology will be carried by a special token (a service token) that circulates counter-clockwise. Thus, when a node enters or exits the ring, nodes that are the most interested by the information (before it clockwise) are informed first.

1) Entering the ring: When a computer wants to enter in the ring, it contacts a running node. The running node communicates it the partial topology of the ring, according to the k factor of tolerance, and the parameters of the problem being solved. With this information, the new node is able to start working on the problem. The server-side of the procedure implies on the change of the local structure of the ring and on the propagation of this new structure to all nodes in the community. For the matter of topology, the requester is inserted after the local node, thus a new node will receive and update its local ring structure directly from its predecessor. Conversely, other nodes are informed of the modification by the service token running counter-clockwise. This later one is propagated until it reaches the k th node.

2) Exiting the ring: A node can exit a CONFIIT computation ring for two reasons: (1) the user decides to stop computing collaboration; (2) a network problem occurred and the node becomes unreachable, or the system crashes. In the former case, a procedure is initiated by the voluntary exiting node. In the later one, problem is detected by its predecessor. We mainly focus here in crashdown exits, since a voluntary exit follows the same propagation procedure.

In case of computer crashdown, the trouble is detected only when a node attempts to send information toward its successor. Then, it removes the crashed node from its own view of the logical ring, and propagates the deletion to its predecessor. Propagation is stopped by the node that initiates the deletion. If a node crashes after a token reception, but before sending it to its successor, a timeout mechanism ensures the token retransmission.

Same problem can occur for back-propagation tokens: a topology alteration involves a token to circulate back to the ring, but it can be destroyed by a computer crash. This problem is solved by a similar procedure: when a node initiates a propagation of a topology alteration, it launches a timeout delay, and re-send the information if it doesn't receive its own information before the timeout ends.

D. Programming models

Since constraints of a given application could be different and sometimes in contradiction (fault tolerance, efficiency, . . . ), CONFIIT offers two main programming models: distributed and centralized mode.

The distributed mode allows an accurate fault tolerance in the computation since task results are locally stored on each node in the community. Thus, a broken computation can be re-launched using already computed tasks. Fig. 1 shows information exchanges in the community for a distributed application. At first, the launcher sends the computing request to a node. The request is propagated along the community by the token (dotted arrows). During computation, results of individual tasks are propagated across the community (thick dashed arrows) such that each node could locally store all individual results (data blocks). Concurrently to the computations, information on the global computation is exchanged according to the thin arrows.

Another interesting point from this mode is that the launcher only needs to be connected during the initiation phase. At the end of the computation, the global result can be retrieved from any node in the community.

While this mode allows greater flexibility and fault tolerance, it may induce the need of a large storage space on each node. Similarly, as results must be spread to each node, it may overload slow network connections. Fig. 2 shows information exchanges in the community for a centralized application. At first, the launcher sends the computing request to a node. The request is propagated along the community by a specific token (dotted arrows) as in the distributed mode, but the launcher must remain connected.

During computation, results of individual tasks are sent to the initial launcher (thick dashed arrows), which has the storage in charge (data blocks). As in the distributed mode, information on the global computation evolution is updated through the token (thin arrows). A crash on a computing node is not a problem for the computation since the main community ring is fault tolerant, but a crash on the launcher will stop the computation because the gathering of information cannot be achieved.

E. Placement of nodes and the ring topology

In this paper, we are especially interested on the impact of nodes placement on the communication performance when using the distributed mode of CONFIIT. Because CONFIIT relies on a virtual ring, the token passing mechanism is intrinsically bound to the network speed and the ring circumference. As consequence, it is important to verify the impact of nodes placement in the overall system performance.

Furthermore, in the case of the distributed mode, this virtual ring not only distributes tasks and prevents nodes about their launcher Fig. 2. Centralized mode Fig. 3. Geographical distribution completion, but also spreads the results among the nodes. In this case, the token must also ensure that all nodes receive the results from different tasks. According to the amount of data exchanged, the underlying network performance and the ring round-trip speed may impact the computing performance.

From these aspects, the placement of nodes becomes an important factor to be evaluated. Contrarily to traditional grid applications, which follow a structured hierarchy known as "cluster of clusters" [START_REF] Steffenel | A framework for adaptive collective communications for heterogeneous hierarchical computing systems[END_REF], dynamic P2P platforms are subjected to node volatility that may reorder the topology in a small amount of time. In the aspects that concern a ring based topology, this means that nodes can be structured according to a geographic distribution (Fig. 3) but also may face worst scenarios, like when the token hops from cluster to cluster (Fig. 4). This diversity of scenarios makes the token round trip time vary by several orders of magnitude, compromising the performance of a platform that is not prepared to face such variations.

Therefore, in the next section we evaluate how the performance of CONFIIT is affected by nodes placement (and task sizes) in a grid environment. [START_REF] Gardner | Mathematics, Magic and Mystery[END_REF], [START_REF] Simpson | Langford sequences: perfect and hooked[END_REF]. While observing his son manipulating blocks of different colors, he noticed that it was possible to arrange three pairs of blocks of different colors (yellow, red, blue) in such a way that only one block separates the red pair, two blocks separate the blue pair and finally three blocks separate the yellow one (see Fig. 5).

Yellow

Red Blue Red Yellow Blue The problem has been generalized to any number of colors n and any number of blocks having the same color s. L(s, n) consists in searching for the number of solutions to the Langford problem. In November 1967, Martin Gardner presented L(2, 4) (two cubes and four colors) as being part of a collection of small mathematical games and stated that L(2, n) has solutions for all n such that n = 4k or n = 4k -1 for k ∈ N * .

Recently, Toby Walsh and Barbara Smith formulated this problem as a Constraint Satisfaction Problem [START_REF] Walsh | Permutation problems and channelling constraints[END_REF], [START_REF] Smith | Modelling a Permutation Problem[END_REF]. The Langford Problem has been approached in different ways (discrete mathematics results, specific algorithms, specific encoding, . . . ).

A. A tree search approach

The Langford problem can be modelized as a tree search problem. In order to solve L(2, n), we consider the tree of height n and width 2n -2 (see Fig. 6):

• every node of the tree corresponds to the place in the sequence of the cubes of a determined color; • to the depth p, the first node corresponds to the place of the first cube of color p in first position and it ith node

= (X 1 , X 2 , X 3 , X 4 , X 5 , X 6 ). It proposes to model L(2, 3) by F (X, 3) = (X 1 X 3 + X 2 X 4 + X 3 X 5 + X 4 X 6 ) × (X 1 X 4 + X 2 X 5 + X 3 X 6 ) × (X 1 X 5 + X 2 X 6 ).
In this approach, each term represents a position for both cubes of a given color and a solution to the problem is equal to the polynomial coefficient of X 1 X 2 X 3 X 4 X 5 X 6 in the development. More generally, a solution to L(2, n) can be deduced from X 1 X 2 X 3 X 4 X 5 ...X 2n .

If G(X, n) = X 1 . . . X 2n F (X, n) then it has been shown that:

(x1,...,x2n)∈{-1,1} 2n G(X, n) (x1,...x2n) = 2 2n+1 L(2, n) So: (x1,...,x2n)∈{-1,1} 2n ( 2n i=1 x i ) n i=1 2n-i-1 k=1 x k x k+i+1 = 2 2n+1 L(2, n) (1) The computation of L(2, n) is in O(4 n × n 2
) and an efficient long integer arithmetic is needed. This principle can be optimized by taking into account the symmetry of the problem and using the Gray code [START_REF] Ranka | Hypercube Algorithms with Applications to Image Processing and Pattern Recognation[END_REF]. By using this approach, M. Godfrey has solved L(2, 20) in one week on three PCs in 2002.

It is quite obvious that a parallel version can be derived from Eq. [START_REF] Foster | Computational Grids[END_REF]. By choosing a value in {-1, 1} for one or more of the x i in (x1,...,x2n)∈{-1,1} 2n , a set of independent tasks is introduced. Again, a depth level of the parallelization can be defined. At depth level k, the values of x 1 , x 2 , . . . , x k are fixed (either 1 or -1). Indeed, at depth level k, a set of 2 k tasks is generated.

B. Current status

At the moment, the instances solved in practice, in a merely combinatorial manner, limit themselves to a small number of colors. In this case, one mentions the instance L(2, 19) that was solved in 2 years and a half on a DEC Alpha problem was solved in 94 days in a non-dedicated network with variable size. Using this variable network, which counted at most with 12 nodes (20 processors) at a given moment, we calculated the 46,845,158,056,515,936 possible combinations of the problem, for an equivalent of 850 days of sequential computation [START_REF] Jaillet | Parallel tree search for combinatorial problems: a comparative study between openmp and mpi[END_REF]. Up today, this is the largest solved instance of Langford's problem3 .

V. EXPERIMENTS

A. Platform Description

In order to conduct our experiments, we used up to 5 clusters from the Grid'5000 experimental platform 4 , located in Bordeaux, Nancy, Nice (Sophia Antipolis), Lille and Toulouse (see Fig. 7). For a matter of uniformity, all clusters are composed of bi-processor, dual-core machines (AMD Opteron 2218 2.66 GHz, AMD Opteron 285 2.66 GHz or Intel Xeon 5110 1.6 GHz). This way, each machine runs 4 CONFIIT threads, one by core. Machines inside the same cluster are interconnected by a Gigabit Ethernet network while the clusters are connected by a private backbone of 10 Gbps. All nodes run Debian Linux, with kernel version 2.6.26.

B. Experiment scenarios

In order to evaluate the impact of nodes placement on the performance of CONFIIT, we designed a progressive scenario where we scale-up the number of clusters from 1 to 5, while keeping the same number of computing threads. Our objective is to evaluate how CONFIIT performance behaves with the increment on the ring circumference, on both best case (geographically distributed or geo, as in Fig. 3) and worst case (Fig. 8). Indeed, if we consider only the network latency (extracted from the ping parameters from Table I), a ring with 60 machines in 5 clusters would take around 46.805ms to do a roundtrip in the best case (geo: Nancy→Bordeaux→Nice→Lille→Toulouse) and 535.788ms to do the same roundtrip in the worst case. If communication and computation do not overlap efficiently, this roundtrip time may represent a serious performance concern.

In our experiments, we also evaluate the performance of CONFIIT with different task sizes for the Langford's problem. Hence, the parallel computation of Langford's problem can be expressed by a depth level k, which generates 2 k independent tasks. A reduced number of large tasks induce less communication among the nodes but increases the size of result blocks to be spread among the nodes. On the other hand, a large number of small tasks may improve the speedup as no task will delay too much the termination of the computation (similar to a pipeline effect).

C. Analysis

Table II represents the average of 3 runs for each combination of clusters, topology and number of tasks. The ring topology is constructed in the order Nancy→Bordeaux→Nice→Lille→Toulouse for both geo and worst scenarios (the worst scenario alternates machines from each cluster, in the same order). For the matter of comparison, we also indicate the execution time in a single machine.

Therefore, Fig. 9, 10, 11 and 12 plot the computation time of the same instance of the Langford's problem when comparing 1 cluster and 2, 3, 4 and 5 clusters respectively. From the analysis of these data, we obtain the following insights: &*?%#@="6*8,.-*?56"@:*>*E*?%#@="6@*8/-*?56"@*"(?G:

&*?%#@="6 E*?%#@="6@*8)"5: E*?%#@="6@*8H56@=:

3#AB"6*54*=(@C@ ?5AD#=(=$53*=$A"*8@: &*?%#@="6*8,.-*?56"@:*>*+*?%#@="6@*8./*?56"@*"(?G:

&*?%#@="6 +*?%#@="6@*8)"5: +*?%#@="6@*8H56@=:

3#AB"6*54*=(@C@ ?5AD#=(=$53*=$A"*8@: Fig. 12. Langford on 5 clusters 1) Impact of nodes placement: In spite of the difference between the placement policies geo and worst, the computation times are barely affected by the ring circumference. While the geo strategy generally benefits from a small advantage in comparison with the worst strategy, this difference seems to vanish (or event to invert) when small tasks are used (e.g.: k = 12 or k = 13).

This can be explained by the task selection mechanism from CONFIIT. Because CONFIIT nodes randomly select unsolved tasks, nodes are allowed to start new tasks even if the token has not yet returned. With more small tasks, computation of tasks can continue with a small probability of "double work", while waiting for the token update. Also at the end of the computations, the remaining unsolved tasks will be quickly deployed and represent a small computation load that does not delay the termination.

Nevertheless, these results do not exclude performance problems if the inter-cluster networks become too slow in comparison with the local-area network (like the traversing of a PSTN or ADSL link). In Grid'5000, the impact of the wide-area latency is partially compensated by its bandwidth (a 10Gbit/s dark-fiber interconnection).

2) Number of clusters:

In spite of the increment in the number of clusters, no slowdown could be observed in the experiments. Also, the ratios between the performances of Langford's algorithm in one or several clusters remain stable, which is an interesting fact. For instance, it seems that the cost associated with the communication, no matter if in a single cluster or through several networks, is sufficiently reduced to be compensated by the computation/communication overlap.

Although these results are encouraging, especially when considering grid environments, we believe that further scalability tests should be necessary to determine the limits of the platform if we plan to deploy experiments in open networks.

3) Impact of task size: We finish the analysis of the experiments by looking on the impact of task sizes on the overall computation time. The Fig. 9, 10, 11 and 12 clearly show that a small number of tasks does not parallelizes as well as when a larger number of tasks is deployed. Actually it is not easy to determine if a task will have a long or small duration, as FIIT tasks are independent and their computation time depends on the evaluation algorithms. Nevertheless, we can estimate that in a combinatorial tree search the more we subdivide the tree, the shorter will be the average computational time of each branch.

This does not mean however that we can subdivide the problem in an infinite number of tasks. Because the token circulation represents a non-negligible barrier, it is important to find a trade-off between the computational time for a task and the communication cost. If we observe the average time for task in the 5-cluster/geo scenario, for example, we obtain 76.74s for k = 9, 28.02s for k = 10, 12.09s for k = 11, 5.71s for k = 12 and finally 3.03s for k = 13. Hence, increment (doubling) in the number of tasks gives a speed-up of at least a factor 2 up to k = 12. With k = 13, however, the average time for task does not decreases as expected, indicating that computation/communication overlap reaches its limits. This time can even increase if we insist to multiply the tasks, as indicated by previous experiences outside this work.

VI. CONCLUSION

The main purpose of this paper was to evaluate how the geographical disposition of nodes in a grid environment impact on the performance of a ring-based distributed computing platform. Using a distributed solver for the Langford's problem as the evaluation subject, we were able to observe the main factors that influence the computation performance.

We observed therefore that the load balancing scheme used in the CONFIIT distributed framework is little sensitive to the performances of the network. Indeed, tasks computation is almost independent of the token mechanism, as the nodes keep selecting uncomputed tasks even without new updates. Nonetheless, the computation performance in the distributed mode (i.e., the timespan) still depends on the number (and by extension, the size) of the tasks as the token propagates the results of the computed tasks. The experiments show a trade-off between computation and communication overlap that limits the speed-up in some cases. Hence, we can expect a larger timespan in slower networks as the token must propagate all updates to all nodes before termination is detected.

Further experiments will explore CONFIIT scalability behavior in both grid environments and open networks (P2P over Internet), an essential step towards larger problems such as Langford L(2, 27) and L(2, 28).

Fig. 1 .

 1 Fig. 1. Distributed mode

Fig. 4 .

 4 Fig. 4. Unordered distribution

Fig. 5 .

 5 Fig. 5. L(2,3): arrangement for 6 blocks of 3 colors: yellow, red and blue.

Fig. 6 .

 6 Fig. 6. Search tree for L(2, 3).

Fig. 7 .

 7 Fig. 7. Location of clusters used in the experiments

Fig. 8 .

 8 Fig. 8. Worst case distribution

Fig. 9 .

 9 Fig. 9. Comparison between Langford on 1 and 2 clusters

Fig. 10 .Fig. 11 .

 1011 Fig. 10. Langford on 3 clusters

TABLE I ROUND

 I -TRIP TIME (PING) AMONG NODES FROM DIFFERENT CLUSTERS

		Bordeaux	Nancy	Nice	Lille	Toulouse
	Bordeaux	0.090ms	18ms	14.9ms	17.2ms	18.6ms
	Nancy	18ms	0.100ms	16.8ms	8.82ms	20.6ms
	Nice	14.9ms	16.8ms	0.046ms	16.1ms	17.4ms
	Lille	17.2ms	8.82ms	16.1ms	0.092ms	19.7ms
	Toulouse	18.6ms	20.6ms	17.4ms	19.7ms	0.064ms

http://www.xtremweb.net

http://www.ourgrid.org

See http://www.lclark.edu/˜miller/langford.html

https://www.grid5000.fr

ACKNOWLEDGEMENT

Experiments presented in this paper were carried out using the Grid'5000 experimental testbed, being developed under the INRIA ALADDIN development action with support from CNRS, RENATER and several Universities as well as other funding bodies (see https://www.grid5000.fr).

This work is partially supported by ANR (Agence National de Recherche), project reference ANR 08 SEGI 022.


Xavier Turon

Nicolas Galtier

Emmanuel J P Douzery

Frédéric Delsuc
email: frederic.delsuc@univ-montp2.fr

G Tsagkogeorga

Accelerated Evolutionary Rate of Housekeeping Genes in Tunicates Georgia Tsagkogeorga •

Keywords:

Phylogenomics has recently revealed that tunicates represent the sister-group of vertebrates in the newly-defined clade Olfactores. However, phylogenomic and comparative genomic studies have also suggested that tunicates are characterized by an elevated rate of molecular evolution and a high degree of genomic divergence. Despite the recurrent interest in the group, the picture of tunicate peculiar evolutionary dynamics is still fragmentary, as it mainly lies in studies focusing on only few model species. In order to expand the available genomic data for the group, we used the high-throughput 454 technology to sequence the partial transcriptome of a previously unsampled tunicate, Microcosmus squamiger. This allowed us to get further insights into tunicate accelerated evolution through a comparative analysis based on pertinent phylogenetic markers, i.e., a core of 35 housekeeping genes conserved across bilaterians. Our results showed that tunicates evolved on average about two times faster than the other chordates, yet the degree of this acceleration varied extensively upon genes and upon lineages. Appendicularia and Aplousobranchia were detected as the most divergent groups which were also characterized by highly heterogeneous substitution rates across genes. Finally, an estimation of the d N /d S ratio in three pairs of closely related taxa within Olfactores did not reveal strong differences between the tunicate and vertebrate lineages suggesting that for this set of housekeeping genes the accelerated evolution of tunicates is plausibly due to an elevated mutation rate rather than to particular selective effects.

Introduction

Understanding chordate origins and evolution has been a preeminent challenge for biologists over the last two centuries [START_REF] Swalla | Chordate origins and evolution[END_REF]. The phylum Chordata consists of three distinct lineages: cephalochordates (lancelets), tunicates or urochordates (sea squirts, salps and appendicularians) and craniates (i.e., cyclostomes and vertebrates). Among these, tunicates embrace a diversity of more than 3,000 filter-feeding and mostly hermaphrodite marine species, characterized by both sessile (ascidians) and planktonic (salps and appendicularians) life styles, associated with a unique developmental program [START_REF] Cone | Using ascidian embryos to study the evolution of developmental gene regulatory networks[END_REF][START_REF] Lambert | Historical introduction, overview, and reproductive biology of the protochordates[END_REF][START_REF] Satoh | The ascidian tadpole larva: comparative molecular development and genomics[END_REF]).

In sharp contrast with vertebrates and lancelets, the vast majority of tunicate adults lack the hallmarks of the typical chordate body plan, namely a dorsal neural tube and a notochord. From the time it has been pointed out that ascidian larvae do possess these chordate features [START_REF] Kowalevski | Beiträge zur Entwicklungsgeschichte der Tunicaten[END_REF], tunicates have been considered as the sister group of Euchordata, i.e., cephalochordates plus craniates [START_REF] Cameron | Evolution of the chordate body plan: new insights from phylogenetic analyses of deuterostome phyla[END_REF][START_REF] Mallatt | Ribosomal RNA genes and deuterostome phylogeny revisited: more cyclostomes, elasmobranchs, reptiles, and a brittle star[END_REF][START_REF] Swalla | Urochordates are monophyletic within the deuterostomes[END_REF][START_REF] Winchell | Evaluating hypotheses of deuterostome phylogeny and chordate evolution with new LSU and SSU ribosomal DNA data[END_REF]. Although widely accepted during the pregenomic era, this euchordate view has been substantially impacted by the genome projects of the two model ascidians Ciona intestinalis [START_REF] Dehal | The draft genome of Ciona intestinalis: insights into chordate and vertebrate origins[END_REF] and Ciona savignyi (Small et al. 2007b), as well as the draft genome of the appendicularian Oikopleura dioica [START_REF] Seo | Miniature genome in the marine chordate Oikopleura dioica[END_REF].

These genomic data allowed including tunicates in phylogenomic studies and accumulating evidence soon indicated that the evolutionary positions of cephalochordates and tunicates should be reversed, erecting a clade called Olfactores that links tunicates with vertebrates [START_REF] Bourlat | Deuterostome phylogeny reveals monophyletic chordates and the new phylum Xenoturbellida[END_REF][START_REF] Delsuc | Tunicates and not cephalochordates are the closest living relatives of vertebrates[END_REF][START_REF] Delsuc | Additional molecular support for the new chordate phylogeny[END_REF][START_REF] Dunn | Broad phylogenomic sampling improves resolution of the animal tree of life[END_REF][START_REF] Singh | Tunicate mitogenomics and phylogenetics: peculiarities of the Herdmania momus mitochondrial genome and support for the new chordate phylogeny[END_REF]. Although debated at first, the Olfactores hypothesis of chordate evolution has now gained wide acceptance since it has been corroborated by analyses of the complete genome sequence of the amphioxus [START_REF] Putnam | The amphioxus genome and the evolution of the chordate karyotype[END_REF]. Moreover, the latest mitogenomic analyses also provided additional support for such a relationship within chordates [START_REF] Singh | Tunicate mitogenomics and phylogenetics: peculiarities of the Herdmania momus mitochondrial genome and support for the new chordate phylogeny[END_REF].

Comparative genomics also revealed that tunicates possess the basic developmental genetic toolkit of vertebrates in unexpectedly condensed genomes that have not undergone the subsequent vertebrate-specific duplication events [START_REF] Cañestro | Seeing chordate evolution through the Ciona genome sequence[END_REF][START_REF] Dehal | Two rounds of whole genome duplication in the ancestral vertebrate[END_REF][START_REF] Dehal | The draft genome of Ciona intestinalis: insights into chordate and vertebrate origins[END_REF]. This prompted a growing interest in tunicates as useful experimental systems to decipher the developmental mechanisms underlying chordate origins [START_REF] Davidson | Ciona intestinalis as a model for cardiac development[END_REF][START_REF] Holland | The Ciona intestinalis genome: when the constraints are off[END_REF][START_REF] Satoh | The ascidian tadpole larva: comparative molecular development and genomics[END_REF]. Despite this renewed interest, our current understanding of tunicate evolution remains fragmentary since phylogenomic and especially comparative genomic studies are taxonomically biased towards model species with available genomes [START_REF] Bourlat | Deuterostome phylogeny reveals monophyletic chordates and the new phylum Xenoturbellida[END_REF][START_REF] Delsuc | Tunicates and not cephalochordates are the closest living relatives of vertebrates[END_REF][START_REF] Delsuc | Additional molecular support for the new chordate phylogeny[END_REF][START_REF] Donmez | Polymorphism due to multiple amino acid substitutions at a codon site within Ciona savignyi[END_REF][START_REF] Imai | Regulatory blueprint for a chordate embryo[END_REF][START_REF] Kim | Diploid genome reconstruction of Ciona intestinalis and comparative analysis with Ciona savignyi[END_REF][START_REF] Satoh | The ascidian tadpole larva: comparative molecular development and genomics[END_REF][START_REF] Sierro | DBTGR: a database of tunicate promoters and their regulatory elements[END_REF][START_REF] Yandell | Large-scale trends in the evolution of gene structures within 11 animal genomes[END_REF].

Complementary EST data are available in a few additional species like Diplosoma listerianum [START_REF] Blaxter | A survey of genes expressed in the seasquirt Diplosoma listerianum[END_REF], Molgula tectiformis [START_REF] Gyoja | Analysis of large scale expression sequenced tags (ESTs) from the anural ascidian, Molgula tectiformis[END_REF]) and Halocynthia roretzi [START_REF] Kim | Generation of expressed sequence tags for immune gene discovery and marker development in the sea squirt, Halocynthia roretzi[END_REF]. However, the aforementioned species are far from covering the diversity of tunicates, so that genomic data are still disproportionately distributed among the major phylogenetic lineages. Moreover, tunicates are currently subjected to a paucity of nuclear phylogenetic markers, as indicated by the exclusive use of the 18S rRNA associated with open controversies regarding the evolutionary history of the group [START_REF] Tsagkogeorga | An updated 18S rRNA phylogeny of tunicates based on mixture and secondary structure models[END_REF][START_REF] Yokobori | Multiple origins of the ascidian-Prochloron symbiosis: molecular phylogeny of photosymbiotic and nonsymbiotic colonial ascidians inferred from 18S rDNA sequences[END_REF][START_REF] Zeng | Coloniality and sociality has evolved once in Stolidobranch ascidians[END_REF][START_REF] Zeng | Molecular phylogeny of the protochordates: chordate evolution[END_REF].

One reason invoked to explain this situation involves the high level of divergence of tunicate lineages due to their accelerated evolution [START_REF] Zeng | Coloniality and sociality has evolved once in Stolidobranch ascidians[END_REF]. Several recent genome based phylogenies inferred from either nuclear or mitochondrial genome data have provided clear-cut evidence for the particularly high rates distinguishing tunicate evolution, as illustrated by the persisting long branches of the group in the reconstructed trees [START_REF] Bourlat | Testing the new animal phylogeny: a phylum level molecular analysis of the animal kingdom[END_REF][START_REF] Delsuc | Additional molecular support for the new chordate phylogeny[END_REF][START_REF] Gissi | Evolution of the mitochondrial genome of Metazoa as exemplified by comparison of congeneric species[END_REF][START_REF] Singh | Tunicate mitogenomics and phylogenetics: peculiarities of the Herdmania momus mitochondrial genome and support for the new chordate phylogeny[END_REF]). Similar conclusions have been drawn by studies focusing on individual genes such as 18S rRNA [START_REF] Perez-Portela | Phylogeny of the families Pyuridae and Styelidae (Stolidobranchiata, Ascidiacea) inferred from mitochondrial and nuclear DNA sequences[END_REF][START_REF] Yokobori | Multiple origins of the ascidian-Prochloron symbiosis: molecular phylogeny of photosymbiotic and nonsymbiotic colonial ascidians inferred from 18S rDNA sequences[END_REF], cox1 [START_REF] Turon | Ascidian molecular phylogeny inferred from mtDNA data with emphasis on the Aplousobranchiata[END_REF], Huntingtin [START_REF] Gissi | Huntingtin gene evolution in Chordata and its peculiar features in the ascidian Ciona genus[END_REF]), P transposase [START_REF] Kimbacher | Drosophila P transposons of the urochordata Ciona intestinalis[END_REF], or chordate gene families such as CYP 1 [START_REF] Goldstone | Cytochrome P450 1 genes in early deuterostomes (tunicates and sea urchins) and vertebrates (chicken and frog): origin and diversification of the CYP1 gene family[END_REF] suggesting that tunicate sequence divergence may increase up to 30% between species of the same genus. Similarly, whole-genome sequence data analyses have also revealed high rates of molecular evolution at a within-species level, as indicated by the extremely high rates of structural (16.6 %) and single nucleotide polymorphism (4.5%) characterizing the Ciona savignyi genome (Small et al. 2007a). As far as genomic features are concerned, it has been shown that, besides genome contraction, tunicates have also undergone dramatic genomic rearrangements associated to numerous gene losses [START_REF] Holland | The Ciona intestinalis genome: when the constraints are off[END_REF]. Breaking prominent chordate paradigms, intron positions are highly variable in Oikopleura doica genes [START_REF] Edvardsen | Hypervariable and highly divergent intron-exon organizations in the chordate Oikopleura dioica[END_REF]), the Hox cluster is disintegrated in Ciona intestinalis [START_REF] Ikuta | Ciona intestinalis Hox gene cluster: Its dispersed structure and residual colinear expression in development[END_REF]) and Oikopleura doica [START_REF] Seo | Hox cluster disintegration with persistent anteroposterior order of expression in Oikopleura dioica[END_REF], and the main retinoic acid signaling genes are lacking from the Oikopleura dioica genome [START_REF] Cañestro | Development of a chordate anterior-posterior axis without classical retinoic acid signaling[END_REF]. All afore-mentioned elements suggest a high degree of tunicate genomic divergence from other chordate lineages and provide compelling evidence that tunicates exhibit high rates of molecular evolution.

Given these puzzling issues, we conducted an in silico identification of new nuclear coding phylogenetic markers for tunicates from orthologous housekeeping genes. These candidate markers were then validated in a non-model species, Microcosmus squamiger (Ascidiacea: Stolidobranchia, Pyuridae) through an in vitro transcriptomic approach involving high-throughput 454-sequencing [START_REF] Margulies | Genome sequencing in microfabricated highdensity picolitre reactors[END_REF]. In order to shed light on the patterns of evolutionary rate variation among tunicates and other chordates, we carried out a comparative analysis based on a subset of 35 highly conserved orthologs. More precisely, our study aimed at testing the hypothesis of tunicate accelerated evolution at independent nuclear loci and assessing their degree of divergence from the other chordate lineages. To this goal we addressed the following questions: (1) Are evolutionary rates of amino acid replacement consistently higher in tunicates than in vertebrates and to what extent? (2) Do chordates exhibit homogenous within-lineage rates and, if not, which genes and/or which species contribute the most to the observed heterogeneity? And finally (3) what are the underlying cause(s) of molecular evolutionary rate heterogeneities within Olfactores?

Materials and Methods

Biological sampling and 454 sequencing of Microcosmus squamiger

Microcosmus squamiger individuals were collected from an invasive population at the locality of Cubelles [START_REF] Rius | Non-lethal effects of an invasive species in the marine environment: the importance of early life-history stages[END_REF], in the Spanish 1º39'17.46" E). Muscle and gonad tissues were dissected and rapidly frozen in liquid nitrogen. Given the small size of this species, tissue material from 8 individuals was mixed and used for standard cDNA library construction in pCMV Sport 6.1 vectors (Invitrogen; Carlsbad, CA, USA). The obtained library was estimated to contain 1.9 x 10 7 cDNA clones, with inserts of about length 2 kb in average which were subsequently sequenced using the 454 Roche GS FLX standard system.

Identification of orthologs

First, we formatted three reference databases: (1) a database consisting of all Ciona intestinalis transcript sequences (19,858 transcripts); (2) a second including only the orthologous genes between Ciona intestinalis and Ciona savignyi (9,520 genes); and finally

(3) a protein database built from a previous phylogenomic dataset of 179 orthologous markers for 51 metazoans [START_REF] Delsuc | Additional molecular support for the new chordate phylogeny[END_REF]. We then scanned the 454-generated data by conducting similarity searches against these databases, and vice versa, using the programs BLASTN, TBLASTX, BLASTX and TBLASTN respectively, with a cut-off e-value of 10 -6 [START_REF] Altschul | Basic local alignment search tool[END_REF]).

Contigs of the sequences matching the third database were assembled using the program CAP3 [START_REF] Huang | CAP3: A DNA sequence assembly program[END_REF]. Orthology assignment was controlled in two ways:

(1) by reciprocal BLAST searches, i.e., by checking that the best hit for a given contig indeed corresponded to the targeted gene, and (2) by phylogenetic tree reconstruction controlling that Microcosmus contigs cluster within tunicates in highest likelihood trees reconstructed by TREEFINDER [START_REF] Jobb | TREEFINDER: a powerful graphical analysis environment for molecular phylogenetics[END_REF]) under the GTR+ 4 +I model. Using the above criteria allowed us to determine the orthologous coding sequences of Microcosmus squamiger for 68 metazoan housekeeping genes from the initial 179 candidates. Among these, 35 genes for which orthology was unequivocally assessed through phylogenetic analyses were finally retained. The resulting 35 Microcosmus squamiger sequences have been deposited in the EMBL nucleotide database under Accession Numbers FN984758 to FN984792.

Dataset assembly

Under conservative constraints of orthology assessment using phylogenetic reconstruction and adequate taxonomic representation of tunicates, the number of usable markers was restricted to 35 (Table 1). Individual gene datasets for these housekeeping genes were built upon available transcript data for 21 additional metazoan species: three non-bilaterians, one poriferan and two cnidarian species, used as outgroups; and 18 bilaterians, including 7 Protostomia and 11 Deuterostomia species. Nucleotide sequences for these taxa were retrieved from multiple online resources, such as the Ensembl Genome Browser (http://www.ensembl.org/), the EST Database (http://www.ncbi.nlm.nih.gov/dbEST/) and Trace Archive (http://www.ncbi.nlm.nih.gov/Traces/) of GenBank at the National Center for Biotechnology Information (http://www.ncbi.nlm.nih.gov/), as well as other eukaryotic genome databases hosted at the Department of Energy Joint Genome Institute (http://www.jgi.doe.gov).

Each of the 35 nuclear DNA dataset was translated into protein. Amino acid alignments were generated using MAFFT version 5 [START_REF] Katoh | MAFFT version 5: improvement in accuracy of multiple sequence alignment[END_REF]. Gaps were then reported on the corresponding DNA sequences to obtain nucleotide alignments. Some divergent regions of these alignments were subsequently refined manually using MEGA 4 [START_REF] Tamura | MEGA4: Molecular Evolutionary Genetics Analysis (MEGA) software version 4.0[END_REF]. Ambiguously aligned sites were then identified at the amino acid level and separately removed from all individual gene datasets, using the program GBLOCKS [START_REF] Castresana | Selection of conserved blocks from multiple alignments for their use in phylogenetic analysis[END_REF], according to the following parameters: a minimum of 14 sequences for conserved and flanking positions, a maximum of 8 contiguous non-conserved positions, a minimum of 5 positions for the length of a block, and a maximum of 50% of gaps per position. The resulting blocks of each protein alignment were then transposed at the DNA level. The concatenation of the 35 phylogenetic markers yielded two 28-taxon datasets: a nucleotide dataset including 25,026 unambiguously aligned sites (8,342 codons), and the corresponding amino acid dataset. The percentage of missing data in these matrices was only 10.7%. All datasets are available upon request.

Phylogenetic analyses

Probabilistic phylogenetic analyses of the two concatenated datasets were conducted following Bayesian Inference (BI) and Maximum Likelihood (ML) reconstruction approaches. Bayesian inferences were conducted under the site-heterogeneous CAT mixture model [START_REF] Lartillot | A Bayesian mixture model for across-site heterogeneities in the amino-acid replacement process[END_REF]) combined to a 4-category Gamma ( ) distribution, i.e., CAT+ for amino-acid and CAT+GTR+ for nucleotide alignments. All analyses were run using Phylobayes version 3.1 [START_REF] Lartillot | PhyloBayes 3. A Bayesian software package for phylogenetic reconstruction and molecular dating[END_REF]. For each dataset, two independent Markov Chains Monte Carlo (MCMC) were launched with parameters and trees sampled every 10 cycles until 1500 points were attained. Priors were set to default values and convergence of the two chains was checked by monitoring the marginal likelihoods through cycles. Bayesian Posterior Probabilities (PP) were obtained from the 50% majority rule consensus of the 1000 trees sampled during the stationary phase, after a burnin of 500 cycles.

ML analyses of the nucleotide dataset were conducted using PHYML 3.01 [START_REF] Guindon | A simple, fast, and accurate algorithm to estimate large phylogenies by maximum likelihood[END_REF] and PAUP* 4.0b10 [START_REF] Swofford | Phylogenetic Analysis Using Parsimony (* and Other Methods)[END_REF]. ML parameters of the GTR+ model were first estimated by conducting an initial heuristic search in PHYML using a BIONJ starting tree followed by Subtree Pruning and Regraphting (SPR) branch-swapping.

The optimal parameter values were then used in PAUP ML heuristic searches implemented by applying Tree Bisection and Reconnection (TBR) branch-swapping on a Neighbor-Joining (NJ) starting tree. For the amino acid dataset, ML analyses were performed using the program PHYML under the CAT-C20+ model with the number of CAT categories set to 20 [START_REF] Le | Empirical profile mixture models for phylogenetic reconstruction[END_REF] . The heuristic ML searches were conducted by performing SPR moves on a NJ starting tree.

For both nucleotide and amino-acid ML trees, statistical support was estimated by bootstrap resampling with 100 pseudo-replicates generated by the program SEQBOOT of the PHYLIP package [START_REF] Felsenstein | PHYLIP (Phylogeny Inference Package) In: Department of Genome Sciences UoW[END_REF]. In all replicates, ML analyses were performed as described above for the original data sets. Bootstrap percentages (BP) were obtained from the 50% majority rule consensus of the 100 pseudo-replicated trees using the program TREEFINDER.

Substitutional saturation

We evaluated the extent of substitutional saturation in our data using saturation plots [START_REF] Philippe | Comparison of molecular and paleontological data in diatoms suggests a major gap in the fossil record[END_REF]) for all types of concatenated datasets, nucleotide and amino-acid, as well as for the first plus second, and third codon positions separately. The amount of saturation was estimated by plotting the observed pairwise distances on the alignments against the tree-inferred distances. The latter patristic distances were calculated from the CAT+ branch lengths estimated by PhyloBayes under a fixed topology. All analyses were carried out using the APE package [START_REF] Paradis | APE: Analyses of Phylogenetics and Evolution in R language[END_REF]) within the R statistical environment (The The R Development Core Team 2004).

Testing relative rate variations between tunicates and vertebrates using local clocks.

Given the depth of the divergences involved in our phylogeny, all following analyses were conducted at the amino-acid level in an effort to minimize the misleading effects of saturation. The tree topology previously obtained from the Bayesian CAT+ analyses of the concatenated amino-acid dataset was used as a reference, and the variation of evolutionary rates between the tunicate and vertebrate lineages was assessed using the program CODEML of the PAML package version 4.2 [START_REF] Yang | PAML 4: phylogenetic analysis by maximum likelihood[END_REF].

We first specified two local clock models (using option Clock=2 in CODEML): (1) a two-rate model, where all branches in our phylogeny conform with the clock assumption and have a default rate (r 0 = 1) to the exception of the Olfactores clade, encompassing tunicate and vertebrate branches, which was assumed to have a different rate r 1 ; and (2) a three-rate model in which tunicate and vertebrate branches were assigned distinct rates, r 1 and r 2 .

ML analyses were performed under these two local clock models on the concatenated dataset as well as on each individual gene alignment. Given that the first model is hierarchically nested into the second, log-likelihoods of each model were compared using likelihood ratio tests (LRTs) [START_REF] Felsenstein | Evolutionary trees from DNA sequences: a maximum likelihood approach[END_REF], with degrees of freedom equal to one (i.e., the difference in the number of parameters included in the models). The associated p-values were corrected for multiple testing (e-values), by being multiplied by the total number of genes tested in parallel according to a Bonferroni correction [START_REF] Boorsma | T-profiler: scoring the activity of predefined groups of genes using gene expression data[END_REF]. In these tests, the two-rate model (1) represented the null hypothesis that the rate of evolution is homogenous between tunicates and vertebrates.

Protein evolutionary rate estimation under autocorrelated models

Because of practical constraints in using the program MULTIDIVTIME [START_REF] Thorne | Estimating the rate of evolution of the rate of molecular evolution[END_REF]), all amino-acid alignments for the 35 orthologous markers were slightly modified in order to ensure the presence of one non-bilaterian outgroup taxa in each gene dataset. In this respect, Nematostella sequences had to be removed from all gene alignments because this taxon was missing for some genes. The missing sequences of Reniera (genes rpl10l and rplp2) were replaced by the corresponding orthologs of its relative Suberites domuncula, in order to obtain a complete poriferan outgroup.

For each of the 35 resulting protein datasets, branch-specific rates of amino acid substitution were estimated with MULTIDIVTIME under the JTT model. We used the previously defined reference topology after pruning Nematostella, and set the prior age of the root at 700 Mya [START_REF] Douzery | The timing of eukaryotic evolution: does a relaxed molecular clock reconcile proteins and fossils?[END_REF]) with no additional constraints on nodes. Two independent MCMC were launched and run for 1 million generations, sampling every 100 generations and discarding the first 100,000 as the burnin. The rates assigned to terminal branches were taken as species-specific evolutionary rates expressed as the number of aminoacid replacements per 100 sites per million year (Myr).

Estimation of non-synonymous and synonymous substitution rates in Olfactores

Given the extent of substitutional saturation at the large-scale in our dataset, we selected the three pairs of more closely related species to estimate the ω = d N / d S ratio for tunicates, teleosts and mammals. This criterion resulted in the following pairs being selected: Ciona intestinalis and Ciona savignyi for tunicates, Danio rerio -Tetraodon nigroviridis for teleosts, and Monodelphis domestica -Homo sapiens for mammals.

From the 35 previously assembled individual gene datasets, we extracted the sequences of the six afore-mentioned taxa. Nucleotide alignments were then processed using Gblocks in order to exclude all codons that contained gaps (option: no gap positions allowed).

Five markers (psmb1, rplP2, rpl35A, rpl39L and rpsA) had to be discarded during this process because of too many missing characters. Thirty genes were thus analyzed, encompassing in total 19,083 nucleotide sites or 6,361 codons for the three selected pairs of tunicate, teleost and mammal species.

The numbers of synonymous substitutions per synonymous sites (d S ) and nonsynomymous substitutions per non-synonymous sites (d N ) were estimated for each of the three species pairs and all thirty housekeeping genes, using the ML method of Goldman and Yang [START_REF] Goldman | A codon-based model of nucleotide substitution for proteincoding DNA sequences[END_REF], implemented in CODEML (options seqtype = 1, runmode = -1 and CodonFreq = 2). Similar results were also obtained when analyses were repeated using the YN00 counting method [START_REF] Yang | Codon-substitution models for heterogeneous selection pressure at amino acid sites[END_REF] implemented in CODEML. Three genes for which a d S greater than 10 was obtained (rpl15, rpl7 and sars) were excluded, as they undoubtedly present unreliable estimates due to strong substitutional saturation through time.

Finally, the distributions of the synonymous and non-synonymous substitution rate (d S and d N ) estimates for tunicates, teleosts and mammals across the 27 retained housekeeping genes were plotted using R.

Results

Microcosmus squamiger 454 transcriptome sequencing and identification of orthologs

The 454 sequencing of the Microcosmus squamiger partial transcriptome on the GS FLX standard platform yielded about 50 million high quality bases in total, which correspond to 211,899 sequence reads with a mean length of 250 bp. Similarity searches using BLASTN against either the intersection between Ciona intestinalis and Ciona savignyi orthologous genes (9,520 genes) or the Ciona intestinalis full transcriptome (19,858 transcripts) resulted in 46,245 and 48,455 matching reads corresponding to 216 and 245 genes, respectively. When using TBLASTX searches, the total number of putative homologous read sequences to Ciona orthologs was raised to 126,830 belonging to 834 genes.

At a larger taxonomic scale, positive BLAST results were obtained for about 11 % of the total number of Microcosmus reads which matched 68 of the 179 initially targeted nuclear protein-coding genes conserved across metazoans. Among these, 35 genes for which orthology was unequivocally assessed were finally retained. The 35 orthologous gene sequences for Microcosmus squamiger were finally assembled from a total of 24,209 matching reads, with a mean coverage of 691 ± 24 reads per gene reflecting the high expression level of these housekeeping genes. According to the Gene Ontology [START_REF] Ashburner | Gene ontology: tool for the unification of biology. The Gene Ontology Consortium[END_REF], the 35 genes (Table 1) were mostly involved in translational elongation (ribosomal proteins) but also in metabolic or catabolic processes (AHCY, SUCLG1, PSMA6, PSMB1, HSP90AB1), glycolysis (PDHB), RNA splicing (U2AF1), tRNA processing (SARS), and protein folding (CCT5).

Tunicate phylogenetics based on 35 housekeeping genes

Saturation plots revealed a high degree of substitutional saturation at 3 rd codon positions compared to positions 1 and 2 and amino acids (Fig. 1). Consequently, 3 rd codon positions were excluded from subsequent phylogenetic analyses of the nucleotide dataset. Phylogenetic reconstructions conducted at both the amino acid and nucleotide levels using ML and BI approaches under standard and mixture models of sequence evolution yielded almost identical trees. The resulted phylogenetic picture (Fig. 2) conforms to the widely accepted view of animal evolution [START_REF] Telford | Animal phylogeny[END_REF]) according to which Bilateria can be divided into Protostomia and Deuterostomia, the former embracing two reciprocally monophyletic lineages; Lophotrochozoa (PP aa = 1, BP aa = 98, PP nt = 0.98, BP nt = 98) and Ecdysozoa (PP aa = 1, BP aa = 99, PP nt = 1, BP nt = 100). All analyses were highly congruent as far as the monophyletic origin of Protostomia was concerned (PP aa = 0.99, BP aa = 93, PP nt = 1, BP nt = 81), yet Deuterostomia relationships appeared more difficult to resolve, particularly in ML trees (PP aa = 0.89, BP aa < 50, PP nt = 0.87, BP nt < 50). In details, ML analyses on nucleotide positions 1 and 2 under the standard GTR+ model yielded a ML tree where Xenambulacraria (Xenoturbella + Hemichordata + Echinodermata) appeared as the sister-group of all other bilaterians thereby disrupting deuterostome monophyly, although without statistical support (BP nt < 50). In ML analyses of the amino acid dataset under the CAT-C20+ model, Xenoturbella emerged as the sister-group of the remaining bilaterians (BP aa < 50) and Branchiostoma clustered with Ambulacraria with moderate support (BP aa = 77). As pointed out, no significant nodal support was obtained for neither conformations, and similar results were previously shown to likely represent phylogenetic reconstruction artifacts [START_REF] Bourlat | Deuterostome phylogeny reveals monophyletic chordates and the new phylum Xenoturbellida[END_REF][START_REF] Delsuc | Additional molecular support for the new chordate phylogeny[END_REF], although the phylogenetic position of Xenoturbella is still contentious [START_REF] Hejnol | Assessing the root of bilaterian animals with scalable phylogenomic methods[END_REF].

Within Chordata, a sister-group relationship of tunicates with vertebrates was unequivocally recovered with all methods and datasets (PP aa = 1, BP aa = 94, PP nt = 1, BP nt = 95). Of note, the Olfactores clade is retrieved from nucleotide-based reconstructions, giving further credit to the robustness of the new chordate phylogeny and suggesting that the core of 35 housekeeping genes we considered carries a strong phylogenetic signal largely congruent with that of larger phylogenomic datasets [START_REF] Delsuc | Tunicates and not cephalochordates are the closest living relatives of vertebrates[END_REF][START_REF] Delsuc | Additional molecular support for the new chordate phylogeny[END_REF][START_REF] Dunn | Broad phylogenomic sampling improves resolution of the animal tree of life[END_REF][START_REF] Putnam | The amphioxus genome and the evolution of the chordate karyotype[END_REF].

Similarly, the 35 phylogenetic markers appeared informative enough to provide a clear-cut phylogenetic picture within each group. The newly sequenced Microcosmus squamiger was found firmly branched with Halocynthia (PP aa = 1, BP aa = 100, PP nt = 1, BP nt = 100), a relationship consistent with the traditional classification, both species belonging to the same order and family (Stolidobranchia: Puyridae). Likewise, the resulting relationships for the remaining tunicate species appeared highly concordant with recent phylogenies inferred from 18S rRNA data [START_REF] Tsagkogeorga | An updated 18S rRNA phylogeny of tunicates based on mixture and secondary structure models[END_REF].

For the majority of species, branch length estimates obtained from phylogenetic reconstructions based on amino acid data were similar to those inferred from nucleotide sequences, to the exception of some fast-evolving taxa within Ecdysozoa and Tunicata.

Oikopleura dioica constitutes such an exception, since its DNA branch length is 1.6 times longer than its amino acid one, with the mean ratio for the other tunicate branches being equal to 1.1. Moreover, Oikopleura dioica was found to exhibit a highly distinct compositional profile in PCA analyses (data not shown), occupying an outlier position relative to the other tunicate and deuterostome taxa, and being close to Caenorhabitis elegans, the second fastestevolving species in our phylogeny (see Fig. 2).

Individual gene rate differences between tunicates and vertebrates under local clocks

In all phylogenetic trees inferred from the full dataset of 35 proteins, tunicates displayed the longest branches within Chordata indicating an overall faster evolutionary rate than vertebrates and cephalochordates. In order to test whether this acceleration affects all genes to a similar extent, we followed a ML approach to obtain relative rate estimates for the two Olfactores lineages in each orthologous gene. LRTs between a constant-rate model and a variable-rate model allowed us to test for statistical significance in rate differences between the two groups. The results indicated that the relative rate of amino acid replacement in tunicates and vertebrates significantly differs between the two groups for 20 genes (Supplementary Table ). The tunicate rate was consistently found to be superior to the vertebrate rate for all the afore-mentioned 20 genes, upholding the assumption of tunicate rapid evolution for the housekeeping genes considered. Moreover, the rate ratio estimates ranged from 1.4 to 7.5 depending on the marker, which implies that the evolutionary shift in tunicate rates has not affected all genes to a similar extent (Fig. 3).

Unexpectedly, although the rate ratio for the remaining 15 genes was superior to 1, except for three of them (rplp2, rpl12 and rpl39l), the LRTs did not significantly reject the hypothesis of equal rate between the two groups. Thereby, in these cases the evolutionary rate within Olfactores may be considered roughly constant, a result providing evidence that tunicates do carry genes that have escaped the prevalent genomic acceleration. The outline of the estimated rate variation within Olfactores is shown in Fig. 4 which illustrates the global rate contrast between tunicates and vertebrates across the 35 proteins. When the same analytical protocol was applied to the concatenated dataset, an overall rate ratio of 1.9 was obtained.

Within-group rate variation under an autocorrelated model of rate evolution

Given the extensive variation in rate among genes, we next asked whether similar fluctuations can also be observed in species rates, and if yes, how they are linked to the afore-described contrasts. Do all tunicates contribute equally to the estimated rate differences among chordates, or the large range of among-gene variation is rather driven by only few species? To answer this question, we estimated the rate of amino acid replacement in all branches of our phylogeny over the 35 housekeeping genes using an autocorrelated model of rate evolution [START_REF] Thorne | Estimating the rate of evolution of the rate of molecular evolution[END_REF]. This allowed us to simultaneously explore two aspects of rate variation within Chordata: both across genes, and across branches of its three subclades.

The branch-specific rate distributions for tunicates, vertebrates, and cephalochordates have been estimated across the 35 molecular markers (Fig. 5). All branches of the tunicate clade were characterized by an accelerated evolutionary rate as compared to the other chordate groups, whereas the lineage-specific estimates were found to vary extensively across the sampled species. This yielded a particularly heterogeneous picture for tunicate rates, which contrasted sharply with the more homogeneous and mostly overlapping rate distributions of vertebrates, and the slow evolutionary rate characterizing the amphioxus Branchiostoma floridae (Fig. 5). More precisely, the two phlebobranch ascidians (Ciona intestinalis and C. savignyi) seemed to exhibit the lowest rates among tunicates, with the stolidobranchs (Halocynthia roretzi, Microcosmus squamiger and Molgula tectiformis) following next, conforming to previously reported phylogenetic observations [START_REF] Tsagkogeorga | An updated 18S rRNA phylogeny of tunicates based on mixture and secondary structure models[END_REF][START_REF] Yokobori | Multiple origins of the ascidian-Prochloron symbiosis: molecular phylogeny of photosymbiotic and nonsymbiotic colonial ascidians inferred from 18S rDNA sequences[END_REF][START_REF] Zeng | Coloniality and sociality has evolved once in Stolidobranch ascidians[END_REF]. Interestingly, the evolutionary rate heterogeneity appeared radically lessened when considering species of the same order, as best exemplified by the overlap of the gene rate distributions within Stolidobranchia. Notably, the aplousobranch Diplosoma listerianum and, particularly, the appendicularian Oikopleura dioica were detected as highly divergent species, with rates deviating greatly from the average values of all other sampled tunicates in particular, and chordates in general. These two representatives were also characterized by the largest variance in estimates across genes, illustrated by the wide quartiles of their rate distributions (Fig. 5).

Considering the results of the previous local clock analyses, we finally examined the among-branch variation separately for the 20 genes that showed significantly higher evolutionary rates in tunicates, and the remaining 15 genes for which LRTs did not reject the hypothesis of a homogeneous rate among Olfactores. As expected, rate estimates considering the latter 15 genes yielded a more even rate variation across Chordata (Fig. 6). Interestingly, this more homogeneous picture among chordate lineages appeared to stand mainly in the decrease of Diplosoma listerianum and Oikopleura dioica rates. The two Ciona species, and the three stolidobranch ascidians (Halocynthia roretzi, Microcosmus squamiger and Molgula tectiformis) showed rate profiles almost identical when considering either the full dataset or the two subsets of 20 and 15 genes respectively (Fig. 6).

d N /d S ratio variation among lineages

The synonymous and non-synonymous rate ratios (d N /d S ), as estimated for the three most closely related species pairs Ciona intestinalis -Ciona savignyi, Danio rerio -Tetraodon nigroviridis and Monodelphis domestica -Homo sapiens, respectively, and across a subset of 27 genes are shown in Fig. 7. All d N /d S estimates were much less than 1 reflecting the fact that the set of examined genes is under strong purifying selection in all represented lineages. This is consistent with the fact that every gene of our analysis is conserved at a notably large taxonomic scale with most of them involved in fundamental housekeeping functions of the cell.

Overall, the considered, yet none of the lineages presented a systematically higher across-gene d N /d S as compared to the others, ruling out the hypothesis that the observed evolutionary rate variation is due to a relaxation of selective constraints in one particular lineage. Instead, the resulting picture of similar global distributions of d N /d S observed for tunicates, teleosts and mammals (Fig. 8).

Discussion

Determining new phylogenetic markers for tunicates using 454 sequencing

Over the past four years, massively parallel sequencing platforms have become available, enabling the generation of large amounts of genomic data at extremely short times and accessible costs [START_REF] Shendure | Next-generation DNA sequencing[END_REF]. Using such technologies for tunicates seemed a promising perspective from a phylogenetic and comparative genomics standpoint, mainly because this lineage is far from satisfying the prerequisites for the successful development of phylogenetic markers through traditional PCR approaches. Evolving at elevated rates, tunicate protein-coding genes exhibit high levels of sequence divergence leading to large amounts of saturation, even when considering closely related species such as Ciona intestinalis and C. savignyi. Thereby, the identification of conserved regions in a gene, suitable for primer designation, appears to be a particularly difficult task. As a result, besides whole-genome projects, the currently available genomic information for tunicates comes from EST and cDNA sequencing projects that do not technically require a priori information and low sequence divergence [START_REF] Blaxter | A survey of genes expressed in the seasquirt Diplosoma listerianum[END_REF][START_REF] Gyoja | Analysis of large scale expression sequenced tags (ESTs) from the anural ascidian, Molgula tectiformis[END_REF][START_REF] Kim | Generation of expressed sequence tags for immune gene discovery and marker development in the sea squirt, Halocynthia roretzi[END_REF]).

Here, we applied for the first time the high-throughput 454 technology [START_REF] Margulies | Genome sequencing in microfabricated highdensity picolitre reactors[END_REF] to sequence the partial transcriptome of an ascidian tunicate, Microcosmus squamiger. This invasive species recently became widespread in the western Mediterranean sea while being likely of Australian origin, and has also spread and become invasive in other parts of the world [START_REF] Rius | Phylogeography of the widespread marine invader Microcosmus squamiger (Ascidiacea) reveals high genetic diversity of introduced populations and non-independent colonizations[END_REF][START_REF] Rius | Non-lethal effects of an invasive species in the marine environment: the importance of early life-history stages[END_REF]. We sought to identify orthologous sequences for a set of 179 previously determined phylogenetic markers used in large-scale comparative analyses [START_REF] Delsuc | Additional molecular support for the new chordate phylogeny[END_REF]. At the time this work was conceived, the 454 sequencing system generated an average of 100 megabases per run, at short 250 base-pair reads. Still this approach permitted us to determine in silico 68 homologous genes, among which 35 were unambiguously identified as orthologous sequences to our query genes.

Although this might seem a small number compared to the initial 50 million base pairs of resulting data, several factors argue for the great potential of the 454 sequencing approach in tunicate phylogenetics and comparative genomics. First, the sequencing of the Microcosmus transcriptome was conducted on a cDNA library that was not normalized. This yielded an important level of coverage or/and redundancy for highly expressed genes in our data, and the 35 housekeeping genes corresponded to a non-negligible amount of 24,209 sequence reads (i.e. about 10% of the initial 211,899 reads). Second, albeit high-throughput sequencing alleviates bench problems, the fast-evolving nature of tunicate species has still a substantial impact on the post-data analyses by hindering the reliable assignment of orthology between highly divergent sequences. Analyses of the Ciona intestinalis genome have demonstrated that in a transcriptome composed of 16,000 genes, only a small fraction (5%) matched to vertebrate genomes, whereas about 60% of the genes are shared with protostome animals [START_REF] Dehal | The draft genome of Ciona intestinalis: insights into chordate and vertebrate origins[END_REF]. In this respect, the limited sequence length of the 454 GS FLX standard platform at the time has reinforced the problem, since short sequences are difficult to assign with confidence through similarity searches.

In conclusion, considering tunicate scarcity in genomic data and available phylogenetic markers, the results from our pilot application of the 454 sequencing approach to the group appears promising. Given the ongoing advances of these high-throughput sequencing technologies in terms of layout, it can be foreseen that the 454 sequencing approach will represent a compelling tool for the construction of large comparative datasets allowing for more comprehensive studies on tunicate phylogenetics and molecular evolution in the near future.

Tunicates evolve twice as fast as vertebrates, but not all genes nor all lineages are equal determinants of this contrast

To quantify the tunicate molecular divergence in a comparative chordate framework, we assessed evolutionary rate variation within Chordata on the basis of 35 housekeeping genes.

Overall, our results suggested that tunicates have experienced a nearly twofold faster evolution compared to their vertebrate counterparts within Olfactores (Fig. 4), whereas the cephalochordate rate pattern appeared fairly similar to that of vertebrates (Fig. 5).

From a gene standpoint, shifts in tunicate rates have been detected in the majority of the examined genes, yet the degree of the predicted acceleration varied extensively across genes. Our estimates indicated a 1.4-to an uppermost 8-fold accelerated rate for tunicates versus vertebrates depending on the gene, clearly suggesting that not all genes are equal determinants of rate discrepancies within Chordata (Fig. 3). For a substantial proportion of genes (15 out of 35 genes), the estimated evolutionary rate in tunicates was not significantly different from that of vertebrates (Table 2). This result implies that despite the generally striking genomic divergence [START_REF] Dehal | The draft genome of Ciona intestinalis: insights into chordate and vertebrate origins[END_REF][START_REF] Seo | Miniature genome in the marine chordate Oikopleura dioica[END_REF]Small et al. 2007b), at least some coding parts of tunicate genomes have escaped the prevalent acceleration bursts.

Considering lineage-specific rate profiles, Phlebobranchia and Stolidobranchia exhibited lower among-gene variation. The inclusion of Microcosmus allowed expanding the taxonomic coverage of Stolidobranchia, providing clues for a rather uniform rate at the ordinal taxonomic level. Finally, Aplousobranchia and, particularly, Appendicularia were characterized instead by the highest and the more heterogeneous rates across the examined markers.

In overview, tunicates presented a propensity for extensive rate variation across genes and lineages but certainly our results cannot be generalized to a genome scale, since 35 housekeeping genes constitute only a small portion of the chordate gene repertoire. Due to the necessity of accurate orthology assessment among compared sequences, studies in comparative genomics are frequently based on highly conserved molecular markers, being most of the time restricted to only few functional classes of genes. The main challenge for forthcoming studies would be to counterbalance the trade-off between fast-evolving sequences and orthology assessment, in order to explore tunicate, and thereby chordate, rate variation at a larger scale. This would allow testing the validity of two prefatory hypotheses issued from this work: (1) The high heterogeneity of across-gene rates of protein evolution and (2) the preponderant impact of Appendicularia and Aplousobranchia on the whole image of chordate evolutionary rate variation.

From another point of view, it would also be interesting to attempt lower taxonomic scale analyses, with the goal to decrease the evolutionary distance separating sampled species.

The number of shared orthologous genes between two species is expected to be negatively correlated to their evolutionary distance, more closely relatives have thus a much broader potential in terms of number of molecular markers to be examined.

Insights into the underlying causes of tunicate accelerated evolution

Evolutionary rate shifts in protein-coding genes among as well as within lineages could result from different factors, such as changes on selective constraints and positive selection, or changes in mutation rates, i.e. a general acceleration of nucleotide substitutions [START_REF] Nabholz | Strong variations of mitochondrial mutation rate across mammals--the longevity hypothesis[END_REF]. In a preliminary effort to understand the causes that drove the observed tunicate rate acceleration, we compared synonymous (d S ) and non-synonymous (d N ) rates of Ciona intestinalis and Ciona savignyi versus that of teleosts and mammals.

The d N /d S ratio was roughly similar for the three lineages, albeit some pronounced differences were observed for some genes (Fig. 7). Tunicates were not systematically associated with higher d N /d S , and no signature of positive selection was traced in our data. On the contrary, all examined genes evolved under strong purifying or negative selection, which in conjunction with the rather uniform picture of (Fig. 8) implies that tunicate rate shift with regards to vertebrates, and also chordates, most probably resulted from an increase of their mutation rate rather than changes in selection regime.

Yet a generalization of these findings would be premature, obviously because of the limited gene sampling considered, but also because our estimations, of d S particularly, might suffer from the uncertainty due to the putatively confounding effects of saturation [START_REF] Kryazhimskiy | The population genetics of dN/dS[END_REF] and from potential branch length effects [START_REF] Wolf | Nonlinear dynamics of nonsynonymous (dN) and synonymous (dS) substitution rates affects inference of selection[END_REF].

Underestimated d S might indeed explain why we observe essentially similar d N /d S ratio in tunicates and vertebrates, although the former have presumably larger population sizes than the latter (Small et al. 2007a)theory would predict more efficient purifying selection, and hence reduced dN/dS ratio, in large populations [START_REF] Charlesworth | Fundamental concepts in genetics: effective population size and patterns of molecular evolution and variation[END_REF]. Still, as a first insight into the causes of tunicate acceleration, our results should stimulate a more thorough research for the underlying determinant of mutation rate variation within tunicates. Variability in mutation rate has been so far attributed to a number of intrinsic factors, such as generation time and metabolic rate, mating system and, more recently, longevity [START_REF] Nabholz | Strong variations of mitochondrial mutation rate across mammals--the longevity hypothesis[END_REF].

Undoubtedly, the highly diversified life-history traits of the group, encompassing for example both sexually and asexually reproducing species [START_REF] Lambert | Historical introduction, overview, and reproductive biology of the protochordates[END_REF], provide a challenging ground for identifying links between changes in mutation rates and environmental, functional and biological factors such as population size.

Conclusions

In this study, the comparative analysis of 35 highly conserved nuclear genes at both amino acid and nucleotide levels provides a first assessment of the within-chordate rate variation and bears a round of elements worth to be tested in larger-scale analyses. More precisely, our results revealed (1) a two-fold faster evolution of tunicates as compared to other chordates;

(2) a marked asymmetry and heterogeneity in tunicate evolutionary rates, both across genes and among major lineages; (3) the prevailing effects of Appendicularia and Aplousobranchia in the extent of rate contrasts within Chordata; and finally (4) the predominant role of changes in mutation rate as the most probable underlying cause of tunicate accelerated genomic evolution.

TABLES

Table 1 -List of the 35 metazoan-conserved housekeeping genes for which orthologous sequences have been identified in the transcriptome of Microcosmus squamiger. Markers corresponding to a subsample of the ones used in a recent phylogenomic study [START_REF] Delsuc | Additional molecular support for the new chordate phylogeny[END_REF]) and for which, a nucleotide dataset was built upon in silico available data for 27 additional metazoan taxa.

Gene

FIGURESFig. 1 -

 1 FIGURES

Fig. 2 -

 2 Fig. 2 -Superimposition of the consensus Bayesian trees inferred from amino acids

Fig. 3 -

 3 Fig. 3 -Contrasting local molecular clock estimates among tunicates and vertebrates

Fig. 4 -Fig. 5 -

 45 Fig. 4 -Average contrast of rate variation in amino acid replacements within

Fig. 6 -

 6 Fig. 6 -Branchwise distributions of tunicate, vertebrate and cephalochordate rates of

Fig. 7 -

 7 Fig. 7 -Estimation of the synonymous / non-synonymous rate ratios (d N /d S ) according

Fig. 8 -

 8 Fig. 8 -Overall estimation of the synonymous / non-synonymous rate ratios in

Figure 1 Figure 8

 18 Figure 1

# e!Ensembl* Homo sapiens orthologous gene Delsuc et al. (2008)

	10 26	ENSG00000167526 ENSG00000110700	rpl13 rps13a	RPL13 RPS13	small nucleolar RNA, C/D box 68 ribosomal protein S13
	11 27	ENSG00000174748 ENSG00000105193	rpl15a rps16	RPL15 RPS16	ribosomal protein L15 ribosomal protein S16
	12 28	ENSG00000142541 ENSG00000182498	rpl16b rps18	RPL13A RPS18	small nucleolar RNA, C/D box 32A 40S ribosomal protein S18
	13 29	ENSG00000063177 ENSG00000145425	rpl18 rps1	RPL18 RPS3A	ribosomal protein L18 small nucleolar RNA, C/D box 73A
	14 30	ENSG00000108298 ENSG00000130041	rpl19a rps27	RPL19 RPS27	ribosomal protein L19 40S ribosomal protein S27
	15 31	ENSG00000166441 ENSG00000101444	HGNC RPL27A sadhchydrolase-E1 AHCY rpl27	ribosomal protein L27a adenosylhomocysteinase
	16 32	ENSG00000161016 ENSG00000168028	rpl2 sap40	symbol RPL8 RPSA	Gene product ribosomal protein L8 small nucleolar RNA, H/ACA box 62
	17 33	ENSG00000182899 ENSG00000031698	rpl33a srs	RPL35A SARS	ribosomal protein L35a seryl-tRNA synthetase
	1	ENSG00000150753	cct-E	CCT5	chaperonin containing TCP1 subunit 5 (epsilon)
	18 34	ENSG00000163923 ENSG00000163541	rpl39 suca	RPL39L SUCLG1	ribosomal protein L39-like succinate-CoA ligase, alpha subunit
	2	ENSG00000165496	grc5	RPL10L	ribosomal protein L10-like
	19 35	ENSG00000100316 ENSG00000160201	rpl3 u2snrnp	RPL3 U2AF1	small nucleolar RNA, C/D box 43 U2 small nuclear RNA auxiliary factor 1
	3	ENSG00000096384	hsp90-C	HSP90AB1	heat shock protein 90kDa alpha (cytosolic) class B member 1
	20 *Ensembl release 54 -May 2009 ENSG00000174444	rpl4B	RPL4	ribosomal protein L4
	4	ENSG00000148303	l12e-D	RPL7A	small nucleolar RNA C/D box 24
	21	ENSG00000122406	rpl5	RPL5	small nucleolar RNA, C/D box 21
	5	ENSG00000100902	psma-G	PSMA6	proteasome (prosome, macropain) subunit, alpha type, 6
	22	ENSG00000089009	rpl6	RPL6	60S ribosomal protein L6
	6	ENSG00000008018	psmb-J	PSMB1	proteasome (prosome, macropain) subunit, beta type, 1
	23	ENSG00000147604	rpl7-A	RPL7	ribosomal protein L7
	7	ENSG00000168291	pyrdehydroe1b-mt PDHB	pyruvate dehydrogenase (lipoamide) beta
	24	ENSG00000089157	rpp0	RPLP0	ribosomal protein, large, P0
	8	ENSG00000177600	rla2-A	RPLP2	ribosomal protein, large, P2
	25	ENSG00000124614	rps10	RPS10	ribosomal protein S10
	9	ENSG00000197958	rpl12b	RPL12	ribosomal protein L12
				32 33

Acknowledgments

We thank the associated editor and two anonymous referees for their constructive comments. This work has been supported by the Research Networks Program in Bioinformatics of the High Council for Scientific and Technological Cooperation between France and Israel, by the European Research Council ("PopPhyl": Population Phylogenomics), and benefited from the ISE-M computing cluster. This is contribution ISEM 2010-049 of the Institut des Sciences de l'Evolution de Montpellier (UMR 5554 -CNRS).