Iñaki Fernández Pérez

Amine Boumaza
email: amine.boumaza@loria.fr

François Charpillet
email: francois.charpillet@loria.fr

Comparison of Selection Methods in On-line Distributed Evolutionary Robotics

In this paper, we study the impact of selection methods in the context of on-line on-board distributed evolutionary algorithms. We propose a variant of the mEDEA algorithm in which we add a selection operator, and we apply it in a task-driven scenario. We evaluate four selection methods that induce different intensity of selection pressure in a multi-robot navigation with obstacle avoidance task and a collective foraging task. Experiments show that a small intensity of selection pressure is sufficient to rapidly obtain good performances on the tasks at hand. We introduce different measures to compare the selection methods, and show that the higher the selection pressure, the better the performances obtained, especially for the more challenging food foraging task. This process is carried out in an off-line fashion; once the behavior is learned and the controller optimized, the agents are deployed and their controllers' parameters remain fixed.

On the other hand, on-line evolution ([15]) takes a different approach in which behavior learning is performed during the actual execution of a task. In these algorithms, learning or optimization is a continuous process, i.e. robotic agents are constantly exploring new behaviors and adapting their controllers to new conditions in their environment. Usually, this is referred to as adaptation.

These two visions of ER can be related to on-line and off-line approaches in Machine Learning (ML). Off-line ML algorithms learn a specific task and solutions should generalize to unseen situations after the learning process, whereas on-line ML algorithms progressively adapt solutions to new presented situations while solving the task. In this sense, both on-line ML algorithms and on-line EA's perform lifelong adaptation or learning, to possibly changing environments or objectives.

In this paper, we focus on on-line distributed evolution of swarm robotic agents. We are interested in learning individual agents behaviors in a distributed context where the agents adapt their controllers to environmental conditions independently while deployed. These agents may locally communicate with each other and do not have a global view of the swarm. In this sense, this approach finds many ties with Artificial Life, where the objective is to design autonomous organisms that adapt to their environment.

On-line distributed evolution may be viewed as distributing an EA on the swarm of agents. Traditional evolutionary operators (mutation, crossover etc.) are performed on the agents and local communication ensures the spread of genetic material in the population of agents.

In EA's, selection operators drive evolution toward fit individuals by controlling the intensity of selection pressure to solve the given task. These operators and their impact on evolutionary dynamics have been extensively studied in off-line contexts ([7]). In this paper, we study their impact in on-line distributed ER, where evolutionary dynamics are different to the off-line case: selection is performed locally on partial populations and fitness values on which selection is performed are not reliable. Our experiments show that, in this context, a strong selection pressure leads to the best performances, contrary to classical approaches in which lower selection pressure is preferred, to maintain diversity in the population. This result suggests that, in distributed ER algorithms, diversity is already maintained by the disjoint sub-populations.

Several authors have addressed on-line evolution of robotic agent controllers in different contexts: adaptation to dynamically changing environments ([5]), parameter tuning ([6]), evolution of self-assembly ([2]), communication ([11]), phototaxis and navigation ([8], [12]). Some of this work is detailed in the next section. The authors use different selection mechanisms inducing different intensities of selection pressure to drive evolution. In this paper, we compare different selection operators and measure the impact they have on the performances of learning two swarm robotics tasks: navigation with obstacle avoidance and collective food foraging.

We begin by reviewing different selection schemes proposed in the context of online distributed ER and then we present the algorithm that will serve as a test bed, along with the selection methods we compare. In the fourth section, we detail our experimental setting and discuss the results. Finally, we close with some concluding remarks and future directions of research.

Introduction

Evolutionary robotics (ER) ( [START_REF] Nolfi | Evolutionary Robotics: The Biology, Intelligence, and Technology[END_REF]) aims to design robotic agents' behaviors using evolutionary algorithms (EA) ( [START_REF] Eiben | Introduction to Evolutionary Computing[END_REF]). In this context, EA's are traditionally seen as a tool to optimize agents' controllers w.r.t to an explicit objective function (fitness).

Related Work

In the following, we review several on-line distributed ER algorithms and discuss the selection mechanisms that were applied to ensure the desired intensity of selection pressure in order to drive evolution.

A common characteristic of on-line distributed ER algorithms is that each agent has one controller at a time, that it executes (the active controller), and locally spreads altered copies of this controller to other agents. In this sense, agents have only a partial view of the population in the swarm (a local repository). Fitness assignment or evaluation of individual chromosomes is performed by the agents themselves and is thus noisy, as different agents evaluate their active controllers in different conditions. Selection takes place when the active controller is to be replaced by a new one from the repository.

PGTA (Probabilistic Gene Transfer Algorithm) introduced by [START_REF] Watson | Embodied evolution: Distributing an evolutionary algorithm in a population of robots[END_REF], is commonly cited as the first implementation of a distributed on-line ER algorithm. This algorithm evolves the weights of fixed-topology neural controllers and agents exchange parts (genes) of their respective chromosomes using local broadcasts. The algorithm considers a virtual energy level that reflects the performance of the agent's controller. This energy level increases every time the agents reach an energy source and decreases whenever communication takes place. Furthermore, the rate at which the agents broadcast their genes is proportional to their energy level and conversely, the rate at which they accept a received gene is inversely proportional to their energy level. This way, selection pressure is introduced in that fit agents transmit their genes to unfit ones. [START_REF] Silva | odneat: an algorithm for distributed online, onboard evolution of robot behaviours[END_REF] introduced odNEAT, an on-line distributed version of NEAT (Neuro-Evolution of Augmenting Topologies) ( [START_REF] Stanley | Evolving neural networks through augmenting topologies[END_REF]), where each agent has one active chromosome that is transmitted to nearby agents. Collected chromosomes from other agents are stored in a local repository within niches of species according to their topological similarities, as in NEAT. Each agent has a virtual energy level that increases when the task is performed correctly and decreases otherwise. This energy level is sampled periodically to measure fitness values and, whenever this level reaches zero, the active chromosome is replaced by one in the repository. At this point, a species is selected based on its average fitness value, then a chromosome is selected within this species using binary tournament. Each agent broadcasts its active chromosome at a rate proportional to the average fitness of the species it belongs to. This, added to the fact that the active chromosome is selected from fit niches, maintains a certain selection pressure toward fit individuals.

EDEA (Embodied Distributed Evolutionary Algorithm) ( [START_REF] Karafotias | An algorithm for distributed on-line, on-board evolutionary robotics[END_REF]), was applied to different swarm robotics tasks: phototaxis, navigation with obstacle avoidance and collective patrolling. In this algorithm, each agent possesses one chromosome, whose controller is executed and evaluated on a given task. At each iteration, agents broadcast their chromosomes alongside with their fitness to other nearby agents with a given probability (fixed parameter). Upon reception, an agent selects a chromosome from those collected using binary tournament. This last chromosome is then mutated and recombined (using crossover) with the current active chromosome with probability f (x ′ ) sc×f (x) , where f (x ′ ) is the fitness of the selected chromosome, f (x) is the fitness of the agent's current chromosome and s c is a scalar controlling the intensity of selection pressure. To ensure an accurate measure of fitness values, agents evaluate their controllers for at least a minimum period of time (maturation age), during which agents neither transmit nor receive other chromosomes.

With mEDEA (minimal Environment-driven Distributed Evolutionary Algorithm), [START_REF] Bredeche | Environment-driven Embodied Evolution in a Population of Autonomous Agents[END_REF] address evolutionary adaptation with implicit fitness, i.e. without a taskdriven fitness function. The algorithm takes a gene perspective in which successful chromosomes are those that spread over the population of agents and which requires: 1) to maximize mating opportunities and 2) to minimize the risk for agents (their vehicles).

At every time step, agents execute their respective active controllers and locally broadcast mutated copies of the corresponding chromosomes. Received chromosomes (transmitted by other agents) are stored in a local list. At the end of the execution period (lifetime), the active chromosome is replaced with a randomly selected one from the agent's list and the list is emptied. An agent dies if there are no chromosomes in its list (if it did not meet other agents) and it remains dead until it receives a chromosome from another agent passing by.

The authors show that the number of living agents rises with time and remains at a sustained level. Furthermore, agents develop navigation and obstacle avoidance capabilities that allow them to better spread their chromosomes. This work shows that environment-driven selection pressure alone can maintain a certain level of adaptation in a swarm of robotic agents. A slightly modified version of this algorithm is used in this work and is detailed in the next section.

[10] proposed MONEE (Multi-Objective aNd open-Ended Evolution), an extension to mEDEA adding a task-driven pressure as well as a mechanism (called market) for balancing the distribution of tasks among the population of agents, if several tasks are to be tackled. Their experiments show that MONEE is capable of improving mEDEA's performances in a collective concurrent foraging task, in which agents have to collect items of several kinds.

The authors show that the swarm is able to adapt to the environment (as mEDEA ensures), while foraging different kinds of items (optimizing the task-solving behavior). In this context, each type of item is considered a different task. The algorithm uses an explicit fitness function in order to guide the search toward better performing solutions. The market mechanism, which takes into account the scarcity of items, ensures that agents do not focus on the most frequent kind of items (the easiest task), thus neglecting less frequent ones. In their paper, the agent's controller is selected using rank-based selection from the agent's list of chromosomes. The authors argue that when a specific task is to be addressed, a task-driven selection pressure is necessary. This idea is discussed in the remainder of this paper.

In the aforementioned works, authors used different classical selection operators from evolutionary computation in on-line distributed ER algorithms. It is however not clear if these operators perform in the same fashion as when they are used in an off-line non-distributed manner. In an on-line and distributed context, evolutionary dynamics are different, since selection is performed locally at the agent level and over the individuals whose vehicles had the opportunity to meet. In addition, and this is not inherent to on-line distributed evolution but to many ER contexts, fitness evaluation is intrinsically noisy as the agents evaluate their controllers in different conditions, which may have a great impact on their performance. A legitimate question one could ask is: does it still make sense to use selection?

In this paper, we compare different selection methods corresponding to different intensities of selection pressure in a task-driven context. We apply these methods in a modified version of mEDEA and measure their impact on two different swarm robotics tasks.

Algorithms

In this section, we describe the variant of mEDEA we used in our experiments (Algorithm 1). It is run by all the agents of the swarm independently in a distributed manner. At any time, each agent possesses a single controller which is randomly initialized at the beginning of evolution.

The main difference w.r.t. mEDEA is that the algorithm alternates between two phases, namely an evaluation phase, in which the agent runs, evaluates and transmits its controller to nearby listening agents, and a listening phase, in which the agent does not move and listens to incoming chromosomes, sent by nearby agents. The evaluation and the listening phases last T e and T l respectively, and, for different robots, they take place at different moments. Since the different robots are desynchronized, robots in the evaluation phase are able to spread their genomes to other robots that are in the listening phase.

If only one common phase takes place, an agent that turns on the spot transmits its controller to any fitter agent crossing it, as broadcast and reception are simultaneous. This separation in two phases is inspired from MONEE where it is argued that it lessens the spread of poorly achieving controllers. Also, task-driven selection was introduced in MONEE to simultaneously tackle several tasks. The agent's controller is executed and evaluated during the evaluation phase. For each agent, this phase lasts T e time-steps at most1 . During this phase, at each time-step the agent executes its current controller by reading the sensors' inputs and computing the motors' outputs. The agent also updates the fitness value of the controller, based on the outcome of the its actions, and locally broadcasts both the chromosome corresponding to its controller and its current fitness value.

Once the T e evaluation steps are elapsed, the agent begins its listening phase, which lasts T l time-steps. During this phase, the agent stops and listens for incoming chromosomes from nearby passing agents (agents that are in their evaluation phase). These chromosomes are transmitted along with their respective fitness values. Consequently, at the end of this phase, an agent has a local list of chromosomes and fitnesses, or local population. Another difference w.r.t mEDEA is that the local population also contains the agent's current chromosome. This is done to ensure that all agents always have at least one chromosome in their respective populations, which happens particularly when an agent is isolated during its listening phase and does not receive any other chromosome. In mEDEA, isolated agents stay inactive until they receive a chromosome from another agent passing by.

After the listening period, the agent needs to load a new controller for its next evaluation phase. To do so, it selects a chromosome from its list using one of the selection methods discussed further. The selected chromosome is then mutated and becomes the agent's active controller. In this case, mutation consists in adding a normal random variable with mean 0 and variance σ 2 to each gene (each synaptic weight of the neuro-controller).

Once the next controller is chosen, the list is emptied. This means selection is performed on a list of chromosomes that have been collected by the agent during the l := l listen()

12:
end for 13:

l := l {g a } 14:

selected := select(l)

15:

g a := mutate(selected) 16: end while previous listening phase. At this time, the new controller's evaluation phase begins. We consider one iteration of the algorithm (evaluation plus listening phase) as one generation.

The selection method selects the new chromosome among the collected ones based on their fitness. This can be done in different manners, depending on the desired intensity of selection pressure. In this paper we compare four different selection methods, each one defining a different intensity of task-driven selection pressure. The choice of these selection methods aims at giving a large span of intensities of selection pressure, from the strongest (Best), to the lowest (Random):

Best Selection: This method deterministically selects the controller with the highest fitness. This is the selection method with the strongest selection pressure, as the agent will never be allowed to select a controller with a lower fitness than the previous one. Best selection can be compared to an elitist selection scheme where the best fit controllers are always kept.

Algorithm 2 Best selection

1: order x i and index as x i:n such that:

f (x 1:n ) ≥ f (x 2:n ) ≥ . . . ≥ f (x n:n ) 2: return x 1:n

Rank-Based Selection:

In this case, selection probabilities are assigned to each controller according to their rank, i.e. the position of the controller in the list, once sorted w.r.t. fitness values. The best controller has the highest probability of being selected; however, less fit controllers still have a positive probability of being selected. Traditionally, this method is preferred to Roulette Wheel selection that assigns individuals probabilities proportional to their fitness values, which highly biases evolution toward best individuals.

Algorithm 3 Rank-based selection

1: order x i and index as x i:n such that:

f (x 1:n ) ≥ f (x 2:n ) ≥ . . . ≥ f (x n:n ) 2: select x i:n with probability P r(x i:n ) = n+1-i 1+2+...+n 3: return x i:n
Binary Tournament: This method uniformly samples a number of controllers equal to the size of the tournament (two in our case) and selects the one with the highest fitness. Here, the selection pressure is adjusted through the size of the tournament: the higher the size, the higher the selection pressure, the extreme case being when the tournament size is equal to the size of the population. In this case, the best controller is chosen 2 . Conversely, when the size of the tournament is two, the induced selection pressure is the lowest.

Algorithm 4 k-Tournament selection

1: uniformly sample k x i , noted {x 1:k , . . . , x k:k } 2: order x i:k such that:

f (x 1:k ) ≥ f (x 2:k ) ≥ . . . ≥ f (x k:k ) 3: return x 1:k
Random Selection: This method selects a controller in the local population at random, disregarding its fitness value and therefore inducing no task-driven selection pressure at all. Randon selection is considered as a baseline for comparisons with the other methods that effectively induce a certain task-driven selection pressure. As discussed in the previous section, this is the selection operator used by mEDEA for evolving survival capabilities of the swarm without any task-driven explicit goal. By considering Random in our experiments, we aim to compare the original mEDEA selection scheme with more selective operators.

Each one of these four selection methods induces a different intensity of selection pressure on the evolution of the swarm. In the next section, we describe our experiments comparing the impact of each one of these intensities.

Experiments

We compare these selection methods on a set of experiments in simulation for two different tasks, fast-forward navigation and collective foraging, which are two wellstudied benchmarks in swarm robotics. All our experiments were performed on the RoboRobo simulator ( [START_REF] Bredeche | Roborobo! a fast robot simulator for swarm and collective robotics[END_REF]).

Description

In all experiments, a swarm of robotic agents is deployed in a bounded environment containing static obstacles (black lines in Figure 1). Agents also perceive other agents as obstacles.

All the agents in the swarm are morphologically homogeneous, i.e. they have the same physical properties, sensors and motors, and only differ in the parameters of their respective controllers. Each agent has 8 obstacle proximity sensors evenly distributed around the agent, and 8 food item sensors are added in the case of the foraging task. An item sensor measures the distance to the closest item in the direction of the sensor. These simulated agents are similar to Khepera or e-puck robots.

We use a recurrent neural network as the architecture of the neuro-controllers of the agents (Figure 1). The inputs of the network are the activation values of all sensors and the 2 outputs correspond to the translational and rotational velocities of the agent. The activation function of the output neurons is a hyperbolic tangent, taking values in [-1, +1]. Two bias connections (one for each output neuron), as well as 4 recurrent connections (previous speed and previous rotation for both outputs) are added. This setup yields 22 connection weights for the navigation task and 38 for the foraging task in the neuro-controller. The chromosome of the controller is the vector of these weights. In the navigation task, agents must learn to move as fast and straight as possible in the environment while avoiding obstacles, whereas in the foraging task, agents must collect food items present in the environment (Figure 1). An item is collected when an agent passes over it, at which time it is replaced by another item at a random location.

We define the fitness function for the navigation task after the one introduced in ). Each agent r computes its fitness at generation g as:

f g r = Te t=1 v t (t) • (1 -|v r (t)|) • min(a s (t)) (1)
where v t (t), v r (t) and a s (t) are respectively the translational velocity, the rotational velocity and the activations of the obstacle sensors of the agent at each time-step t of its evaluation phase.

In the foraging task, a controller's fitness is computed as the number of items collected during its evaluation phase. Furthermore, since we are interested in the performance of the entire swarm, we define the swarm fitness as the sum of the individual fitness of all agents at each generation:

F s (g) = r∈swarm f g r (2)

Measures

A characteristic of on-line ER is that agents learn as they are performing the actual task in an open-ended way. In this context, the best fitness ever reached by the swarm is not a reliable measure, since it only reflects a "good" performance at one point of the evolution. Furthermore, fitness evaluation is inherently noisy, due to different evaluation conditions encountered by the agents. Therefore, we introduce four measures that will be used to compare the impact of the different selection methods. These measures summarize information on the swarm spanning over several generations. They are used only for evaluation and comparison of the selection methods and are computed once the evolution has ended. A pictorial description of these four measures is shown in Figure 2.

• Average accumulated swarm fitness (f c ): is the average swarm fitness in the last generations. This metric reflects the performance of the swarm at the end of the evolution. In our experiments, we compute the average over the last 8% generations.

• Fixed budget swarm fitness (f b ): is the swarm fitness reached at a certain generation (computational budget). This measure helps to compare different methods on the same grounds. In our experiments, we measure this value at 92% of the evolution, which corresponds to the first generation considered in the computation of f c .

f t g b f c f t f b g b f t g f f t t f f t f a
• Time to reach target (g f ): is the first generation at which a predefined target fitness is reached. If this level is never reached, g f corresponds to the last generation. We fixed the target at 80% of the maximum fitness reached over all runs and all selection methods. This metric reflects a certain convergence rate of the algorithms, i.e. how fast the swarm hits the target fitness on the task at hand.

• Accumulated fitness above target (f a ): is the sum of all swarm fitness values above a predefined target fitness. It reflects to which extent the target level is exceeded and if this performance is maintained over the long run. We used the same target fitness as with g f . These comparison measures are not to be taken individually. For instance f c and f b complement each other and give an indication of the level and stability of the performance reached by the swarm at the end of evolution. If f b and f c are close then performance of the swarm is stable. Also, g f and f a combined reflect how fast a given fitness level is reached and to which extent that level is exceeded. Adding the two latter measures to f c shows if that trend is maintained.

Results and discussion

For both navigation and foraging tasks, we run 30 independent runs for each selection method, and we measured F s at each generation in all runs. Figures 3 and4 show the median F s per generation over the 30 runs for each task. We computed the four performance metrics in the case of navigation (Figure 5) and of foraging (Figure 6). For both tasks, we performed pairwise 3 Mann-Whitney tests at 99% confidence on these measures, between the four selection methods. On the one hand, upon analysis of Figure 3 and Figure 4, we observe that the swarm rapidly reaches a high fitness level in both tasks whenever there is a taskdriven selection pressure, i.e. with Best, Rank-based or Binary tournament selection. On the other hand, without any selection pressure (Random), learning is much slower. Furthermore, for the three former selection methods the algorithm reaches comparable levels of performance in terms of median values of the swarm fitness. An exception can be noted for Best selection in the foraging task, which outperforms Rank-based and Binary tournament.

Despite the lower performances achieved by Random, the swarm still manages to learn behaviors for both tasks. This can be seen in the increasing trend of the median swarm fitness in Figure 3 and Figure 4. This result is expected on the navigation task. As it is the case in ( [START_REF] Bredeche | Environment-driven Embodied Evolution in a Population of Autonomous Agents[END_REF]), environmental pressure drives evolution toward behaviors that maximize mating opportunities and thus behaviors that explore the environment, increasing the swarm fitness. The same trend is also observed on the foraging task. The improvement is slower but still present with Random selection. This could be explained by the fact that collecting items is a byproduct of maximizing mating opportunities. Agents collect items by chance while they navigate trying to mate. When inspecting the swarm in the simulator, we observed that, when selection pressure is present, the evolved behaviors drive the agents toward food items which means that the food sensors are in fact exploited. In other words, evolution drove the controllers to use these sensors. However, without any selection pressure (Random), there can not be a similar drive. We also observed this in the simulator: agents were not attracted by food items for Random selection.

When we analyze the comparison measures we introduced earlier, similar trends are observed. Figure 5 (respectively Figure 6) shows the box and whiskers plots of the four measures for each selection method over the 30 runs for the navigation task (respectively the foraging task).

On the navigation task, the pairwise comparisons of the four measures, using Mann-Whitney tests at 99% confidence level, yield significant statistical difference between all selection methods except between Best and Rank-based (p-value=0.0795) We also observe that Best reaches a higher swarm fitness for the fixed budget than the rest of selection methods, and this level is maintained at the end of evolution, as is shown in f c and f b (upper left and right in the figure). The target fitness level is rapidly reached for the three methods inducing selection pressure, and there is not significant difference between Best and Rank-based, nor between Rank-based and Binary Tournament w.r.t g f (lower left). Furthermore, in the case of Best, the required level is not only reached but surpassed during the entire evolution, leading to a value of f a much higher than the ones of the rest of selection methods (lower right). However, this is not the case for Random selection that has much lower f b (upper right) and f c (upper left), and does not reach the target fitness level on more than half the runs that were launched (lower left and right).

On the foraging task, there is a significant difference for all pairwise comparisons, except between Binary Tournament and Random in the case of the time to reach target, g f , and the accumulated fitness above target, f a , (p-value=0.0419 in both cases). This is explained by the fact that very few runs attained the target fitness4 in which case g f is the last generation and f a is almost zero. There is also no statistical difference between Rank-based and Binary Tournament on the fixed budget swarm fitness, f b , (p-value=0.0105). This means that Binary Tournament reaches a fitness at the given budget that is comparable to the one of Rank-based, but it does not maintain this level, since for these two methods the difference is significant on f c .

Best also gives better results on the foraging task: a high swarm fitness is reached and maintained at the end of evolution (f b and f c , upper left and right). It surpasses the target fitness level in almost all runs much faster and to a larger extent than Rank-based, that also manages to reach the required level for most runs (g f , lower left), although by a lower level (f a , lower right). This is not the case for Tournament and Random that do not achieve the target fitness level for most runs (lower left and right).

We can observe that all task-driven selection pressures yield much better performances on both tasks compared to Random selection. Consequently, we may conclude that selection pressure has a positive impact on performances, when solving a given task, and when the objective is not only to achieve adaptation of the swarm as it was the original motivation of mEDEA. Further, statistical tests show a direct correlation between the selection pressure and the performances achieved by the swarm on the two considered tasks. In other words, the stronger the selection pressure, the better the performances reached by the swarm.

In general, it has been argued that elitist strategies are not desirable in traditional EA's, and the same argument holds for traditional ER. This is due to the fact that elitist strategies may lead to a premature convergence at local optima. There exists an extensive body of work, especially in non-convex optimization, where it is preferable to explicitly maintain a certain level of diversity in the population to escape local optima and to deal with the exploration vs. exploitation dilemma. This requirement is perhaps not as strong in the context of distributed ER as our experiments show. Selection is performed among a portion of the population at the agent level, therefore, one might argue that these algorithms already maintain a certain level of diversity inherent to the fact that sub-populations are distributed on the different agents. Comparisons with other approaches in which separated subpopulations are evolved, such as spatially structured EA's ( [START_REF] Tomassini | Spatially structured evolutionary algorithms[END_REF]) and island models ( [START_REF] Alba | Parallelism and evolutionary algorithms[END_REF]), could give further insights on the dynamics of this kind of evolution.

Conclusions

In this paper, we studied the impact of task-driven selection pressures in on-line distributed ER for swarm behavior learning. This kind of algorithms raises several questions concerning the usefulness of selection pressure (partial views of population, noisy fitness values, etc.). We compared four selection methods inducing different intensities of selection pressure on two tasks: navigation with obstacle avoidance and collective foraging. Our experiments show that selection pressure largely improves performances, and that the intensity of the selection operator positively correlates with the performances of the swarm.

Foraging and navigation can be considered as relatively simple tasks and we believe that more complex and challenging ones, involving deceptive fitness functions, could give further insights on selection and evolution dynamics in the distributed case.

Algorithm 1 mEDEA 1 :

 1 g a := random() 2: while true do for t = 1 to T l do 11:

Figure 1 :

 1 Figure 1: Left: the simulation environment containing agents (red dots with thin hairlines representing sensors), obstacles (dark lines) and food items (blue dots). Right: the architecture of the neuro-controller.

Figure 2 :

 2 Figure 2: A pictorial description of the four comparison measures. From top to bottom and left to right: the average accumulated swarm fitness, the fixed budget swarm fitness, the time to reach target and the accumulated fitness above target.

Figure 3 :

 3 Figure 3: Median swarm fitness per generation over the 30 runs for the navigation task.

Figure 4 :

 4 Figure 4: Median swarm fitness per generation over the 30 runs for the foraging task.

Figure 5 :

 5 Figure 5: Box and whisker plots (30 independent runs) of the comparison measures for the four selection methods on the navigation task. From top to bottom and left to right: f c , f b , g f and f a . The label p > 0.01 indicates no statistical difference for the corresponding two selection methods.

Figure 6 :

 6 Figure 6: Box and whisker plots (30 independent runs) of the comparison measures for the four selection methods on the foraging task. From top to bottom and left to right: f c , f b , g f and f a . The label p > 0.01 indicates no statistical difference for the corresponding two selection methods.

  Table 1 summarizes the different parameters used in our experiments.

	food sensors	v r
	obstacle sensors	v t
	bias

Table 1 :

 1 Experimental settings.

	Experiments
	Number of food items	150
	Swarm size	50 agents
	Exp. length	5 × 10 5 sim. steps
	Number of runs	30
		Evolution
	Evolution length	∼ 250 generations
	T e	2000 -rand(0, 500) sim. steps
	T l	200 sim. steps
	Chromosome size	Nav.: 22, Forag.: 38
	Mutation step-size	σ = 0.5
	([9]

A little random number is substracted from T e so as the evaluation phases of the agents are not synchronized.

It is assumed that sampling is performed without replacement.

Pairwise in this context means all combinations of pairs of selection methods, six combinations in our case.

For both tasks, the target fitness is 80% of the highest fitness reached by all methods during all runs.


Pierre Mallinjoud

Jean-Philippe Villemin

Hussein Mortada

Micaela Polay Espinoza

François-Olivier Desmet

Samaan Samaan

Emilie Chautard

Léon-Charles Tranchevent

Didier Auboeuf
email: didier.auboeuf@inserm.fr

Micaela Polay Espinoza

Franc Xois-Olivier Desmet

Le ´on-Charles Tranchevent

Endothelial, epithelial, and fibroblast cells exhibit specific splicing programs

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Human genes are an assemblage of exons that can be differentially selected during splicing. Alternative splicing, which can produce splicing variants with different exonic content from a single gene, is the rule rather than an exception, as 95% of human genes generate several splicing variants [START_REF] Kim | Alternative splicing and disease[END_REF][START_REF] Hallegger | Alternative splicing: Global insights[END_REF][START_REF] Kalsotra | Functional consequences of developmentally regulated alternative splicing[END_REF][START_REF] Blencowe | An exon-centric perspective[END_REF][START_REF] Kelemen | Function of alternative splicing[END_REF]. Alternative splicing relies on the combinatory action of splicing factors (e.g., SR and hnRNP proteins) that bind to exonic or intronic splicing regulatory sequences to either strengthen or inhibit splice site recognition by the splicing machinery, therefore enhancing or repressing the inclusion of alternative exons [START_REF] Barash | Deciphering the splicing code[END_REF][START_REF] Goren | Overlapping splicing regulatory motifs-combinatorial effects on splicing[END_REF][START_REF] Witten | Understanding splicing regulation through RNA splicing maps[END_REF]. Similarly to how transcription factors control transcriptional programs by directing the expression of gene networks, splicing factors control splicing programs by regulating alternative splicing of co-regulated exons [START_REF] Hartmann | Decrypting the genome's alternative messages[END_REF][START_REF] Barash | Deciphering the splicing code[END_REF][START_REF] Goren | Overlapping splicing regulatory motifs-combinatorial effects on splicing[END_REF][START_REF] Witten | Understanding splicing regulation through RNA splicing maps[END_REF]. Alternative splicing is the main mechanism used to increase the proteome diversity coded by a limited number of genes, as the majority of alternative exons contains coding sequences [START_REF] Kim | Alternative splicing and disease[END_REF][START_REF] Hallegger | Alternative splicing: Global insights[END_REF][START_REF] Kalsotra | Functional consequences of developmentally regulated alternative splicing[END_REF][START_REF] Blencowe | An exon-centric perspective[END_REF][START_REF] Kelemen | Function of alternative splicing[END_REF].

Because of the diversity generated by alternative splicing and the complexity of its regulation, functional genomics at exon-level resolution requires the development of new integrative bioinformatics approaches.

Functional genomics at exon-level resolution is necessary to better understand tissue-specific functions. Indeed, it is well established that different tissues (or organs) express different splicing variants [START_REF] Bland | Global regulation of alternative splicing during myogenic differentiation[END_REF][START_REF] De La Grange | Splicing factor and exon profiling across human tissues[END_REF][START_REF] Hartmann | Distinct regulatory programs establish widespread sexspecific alternative splicing in Drosophila melanogaster[END_REF][START_REF] Llorian | Decoding muscle alternative splicing[END_REF][START_REF] Barbosa-Morais | The evolutionary landscape of alternative splicing in vertebrate species[END_REF][START_REF] Merkin | Evolutionary dynamics of gene and isoform regulation in Mammalian tissues[END_REF]. The development of new technologies like splicing-sensitive microarrays and massive RNA sequencing fully establish that different tissues express different splicing programs as a consequence of the combinatorial actions of more-or-less tissue-specific splicing factors [START_REF] Pan | Deep surveying of alternative splicing complexity in the human transcriptome by highthroughput sequencing[END_REF][START_REF] Wang | Alternative isoform regulation in human tissue transcriptomes[END_REF][START_REF] Merkin | Evolutionary dynamics of gene and isoform regulation in Mammalian tissues[END_REF]). However, most organs are composed of common cell types, such as fibroblast and epithelial cells, which perform specific functions. Epithelial cells are tightly connected cells arranged in monolayer with several functions, such as protection, diffusion, secretion, absorption, and excretion, and establishing boundaries between compartments. Fibroblasts comprise the structural framework of tissues and synthesize the extra-cellular matrix, a supportive framework for epithelial cells. Unlike epithelial cells, fibroblasts can migrate as individual cells. Another important cell type is represented by endothelial cells that compose the endothelium, the thin layer of cells that lines the interior surface of blood vessels that supply tissues and organs with blood.

Recent large-scale analyses suggest that splicing programs may contribute to establishing cell type-specific functions. Indeed, the epithelial-to-mesenchymal transition (EMT) that corresponds to the trans-differentiation of epithelial to mesenchymal (fibroblastlike) cells relies not only on transcriptional programs but also on extensive changes in alternative splicing (Warzecha et al. 2009a[START_REF] Warzecha | An ESRP-regulated splicing programme is abrogated during the epithelial-mesenchymal transition[END_REF][START_REF] Shapiro | An EMT-driven alternative splicing program occurs in human breast cancer and modulates cellular phenotype[END_REF][START_REF] Venables | RBFOX2 is an important regulator of mesenchymal tissue-specific splicing in both normal and cancer tissues[END_REF]. Splicing factors, including ESRP1 and 2 and RBFOX2 (RBM9), have been reported to play a key role in EMT (Warzecha et al. 2009a[START_REF] Warzecha | An ESRP-regulated splicing programme is abrogated during the epithelial-mesenchymal transition[END_REF][START_REF] Shapiro | An EMT-driven alternative splicing program occurs in human breast cancer and modulates cellular phenotype[END_REF][START_REF] Dittmar | Genome-wide determination of a broad ESRP-regulated posttranscriptional network by high-throughput sequencing[END_REF][START_REF] Venables | RBFOX2 is an important regulator of mesenchymal tissue-specific splicing in both normal and cancer tissues[END_REF]. Although a recent report indicates that several dozen genes are differentially spliced when comparing normal fibroblasts to epithelial cells isolated from colon and ovarian tissues [START_REF] Venables | RBFOX2 is an important regulator of mesenchymal tissue-specific splicing in both normal and cancer tissues[END_REF], it is currently not known whether the major common cell types, namely fibroblast, epithelial, and endothelial cells, express specific splicing programs independently of their organ origin.

To address this question, we analyzed an ENCODE data set based on exon arrays performed on RNAs prepared from several dozen normal fibroblast, epithelial, and endothelial cells isolated from different tissues [START_REF] Thurman | The accessible chromatin landscape of the human genome[END_REF]. After extensive RT-PCR validation, we show that each major cell type expresses a specific splicing program independently of their tissue origin, suggesting a role of alternative splicing in establishing specific functions of common cell types shared by many tissues. Additionally, by analyzing several publicly available large-scale data sets related to these factors, we identified a set of splicing factors that coordinate these splicing programs. In order to provide the community with full support for alternative splicing analysis, we have made all of the analyzed data sets freely available through a userfriendly web interface named FasterDB, which describes all the known splicing variants of human and mouse genes as well as their splicing patterns across several dozens of normal cells, cancer cells, and tissues. Furthermore, FasterDB integrates several kinds of publicly available data sets, namely, splicing factor binding sites (CLIP-seq) and splicing factor depletion followed by exon-array analysis, to provide users with information regarding the splicing factors that potentially contribute to regulating each exon. To the best of our knowledge, FasterDB is the first database to integrate such a variety of data sets, thereby enabling functional genomics at exon-level resolution.

Results

Identification of cell type-specific splicing programs independent of tissue origin

While a splicing program switch has been shown to occur in a few models of trans-differentiation of epithelial to mesenchymal (fibroblast-like) cells (Warzecha et al. 2009a[START_REF] Warzecha | An ESRP-regulated splicing programme is abrogated during the epithelial-mesenchymal transition[END_REF][START_REF] Shapiro | An EMT-driven alternative splicing program occurs in human breast cancer and modulates cellular phenotype[END_REF][START_REF] Dittmar | Genome-wide determination of a broad ESRP-regulated posttranscriptional network by high-throughput sequencing[END_REF][START_REF] Venables | RBFOX2 is an important regulator of mesenchymal tissue-specific splicing in both normal and cancer tissues[END_REF], we tested whether epithelial cells and fibroblasts express a different splicing program independently of their tissue of origin. For this purpose, we analyzed an ENCODE data set corresponding to 18 and 12 normal fibroblast and epithelial cells, respectively, isolated from different organs (Supplemental Table S1). As shown in Figure 1A, fibroblast and epithelial cells express a transcriptome that differs both quantitatively (at the gene level) and qualitatively (at the exon level) (Supplemental Table S2). Focusing on variations at the exon level and using annotations based on known publicly available transcripts (see below), we observed that ;20% of the cases corresponded to alternative first exons (AFE) and alternative last exons (ALE), while 12% of the cases corresponded to alternatively spliced exons (ASE) (Fig. 1A). About half of the cases were not annotated (NA), indicating potentially novel alternative exons. Remarkably, using the splicing index (SI), which represents the inclusion rate of the differentially spliced exons, fibroblasts and epithelial cells were clustered independently of their organ origin (Fig. 1B; Supplemental Fig. S1). Similar results were obtained by principal component analyses, which showed a clear clustering of the variables (cell lines) depending on their type (epithelial or fibroblast; Supplemental Fig. S3).

As shown in Figure 1C (see also Supplemental Fig. S1), a large set of ASE events was validated by RT-PCR. Further demonstrating that a set of exons can be differentially spliced in major cell types even if they have the same tissue origin, the splicing pattern observed in HMEC cells, which are epithelial cells from the mammary gland, was different from the splicing pattern observed in HMF cells, which are fibroblast cells also from the mammary gland. Additionally, the splicing pattern observed in HMEC cells was similar to the splicing pattern observed in other epithelial cells from different tissues, and the splicing pattern observed in HMF cells was similar to the splicing pattern observed in other fibroblast cells from different tissues (Fig. 1C).

Endothelial cells are also a general cell type present in all organs, as they form blood vessels that supply organs with blood. Because of some functional similarities, endothelial cells are often compared to epithelial cells although they have different embryonic origins. It is not known whether endothelial cells express a specific splicing program or not. As shown in Figure 2, A andB, endothelial cells differ from epithelial cells in both transcriptional and splicing programs (Supplemental Table S3); this was additionally validated by RT-PCR (Fig. 2C; Supplemental Fig. S2). Likewise, endothelial cells differ from fibroblasts in their transcriptional and splicing programs (Supplemental Table S4).

A gene ontology (GO) annotation analysis revealed that genes regulated at the splicing level (i.e., ASE) may contribute to cell type-specific cellular programs, as they were mainly involved in cytoskeleton, cell adhesion, and motion, which are the main features distinguishing these cell types (Figs. 1A,2A).

To further challenge a model in which each of the three major cell types (fibroblast, epithelial, and endothelial) is characterized by specific splicing programs independently from their tissue of origin, we compared each cell type to the other two (Supplemental Tables S5-S7). Remarkably, we identified a set of alternative cassette exons whose splicing index allowed a perfect clustering of each major cell type (Fig. 3A; Supplemental Fig. S4). Thus, we identified a set of exons that are differentially spliced across three major cell types independently of their tissue origin, as validated by RT-PCR (Fig. 3B; Supplemental Table S1). Similar results were obtained using alternative first or last exons (AFE or ALE, respectively), demonstrating that major cell types can differ by the exonic content (ASE, AFE, and ALE) of the transcripts they express (Supplemental Figs. S5,S6).

Cell type-specific splicing programs are controlled by balanced expression of antagonist splicing factors

By focusing on splicing factors with a marked cell type-specific expression pattern (e.g., up-regulated in only one cell type and 512 Genome Research www.genome.org down-regulated in the other two; see Supplemental Table S8), we identified a set of splicing factors whose expression level allowed us to classify each cell type (Fig. 4A; Supplemental Fig. S7). In par-ticular, ESRP1 had a higher level of expression in epithelial cells than in other cell types, as confirmed by RT-qPCR (Fig. 4A,B; Supplemental Table S1), as expected (Warzecha et al. 2009a[START_REF] Warzecha | An ESRP-regulated splicing programme is abrogated during the epithelial-mesenchymal transition[END_REF]; The middle panel indicates the classification of events corresponding to exon level variations. Differentially expressed exons were classified according to their annotation using publicly available transcripts: alternative first exon (AFE), alternative last exon (ALE), and alternative skipped exon (ASE). Not annotated (NA) corresponds to exons that do not correspond to any of the above-mentioned categories. The cellular functions of genes differentially spliced when comparing fibroblasts to epithelial cells are indicated in the right panel. (B) Heatmap presentation of the splicing index (SI) values for exons differentially spliced when comparing fibroblast to epithelial cells. Each line corresponds to a regulated exon, while each column corresponds to a specific cell. Green boxes (-1.5 < SI < 0) correspond to a low inclusion level in the cell as compared to all the others; red boxes (0 < SI < 1.5), high inclusion level; black boxes (SI = 0), no difference for exon inclusion between cells; and gray boxes, missing values. Exons were computationally split into several groups depending on their inclusion rate that correlates with the two major cell types. (C ) RT-PCR validations using RNAs from fibroblasts and epithelial cells, as indicated. [START_REF] Dittmar | Genome-wide determination of a broad ESRP-regulated posttranscriptional network by high-throughput sequencing[END_REF]. Interestingly, PTBP1 (PTB) and MBNL1, which have been suggested to play a role in angiogenesis [START_REF] Pascual | The Muscleblind family of proteins: An emerging class of regulators of developmentally programmed alternative splicing[END_REF][START_REF] Pen | Molecular markers of extracellular matrix remodeling in glioblastoma vessels: Microarray study of laser-captured glioblastoma vessels[END_REF][START_REF] Masuda | RNA-binding proteins implicated in the hypoxic response[END_REF], were enriched in endothelial cells (Fig. 4A,B; Supplemental Table S1). Finally, RBFOX2 (RBM9) and NOVA1 were enriched in fibroblasts (Fig. 4A,B). Interestingly, in addition to sharing many common target exons with NOVA1, RBFOX2 is up-regulated during EMT and plays a critical role in this process [START_REF] Zhang | Defining the regulatory network of the tissue-specific splicing factors Fox-1 and Fox-2[END_REF][START_REF] Venables | RBFOX2 is an important regulator of mesenchymal tissue-specific splicing in both normal and cancer tissues[END_REF]. These results were confirmed by analyzing the expression level of these splicing factors using RNA-seq and gene expression array data sets (Supplemental Fig. S8).

To go a step further, we focused on the PTBP1, ESRP1, and RBFOX2 splicing factors, since their expression levels allowed each major cell type to be clustered (Supplemental Fig. S7B) and since large-scale data sets corresponding to these factors are publicly available (Warzecha et al. 2009b;[START_REF] Xiao | Splice site strength-dependent activity and genetic buffering by poly-G runs[END_REF][START_REF] Xue | Genome-wide analysis of PTB-RNA interactions reveals a strategy used by the general splicing repressor to modulate exon inclusion or skipping[END_REF][START_REF] Yeo | An RNA code for the FOX2 splicing regulator revealed by mapping RNA-protein interactions in stem cells[END_REF][START_REF] Katz | Analysis and design of RNA sequencing experiments for identifying isoform regulation[END_REF][START_REF] Llorian | Positiondependent alternative splicing activity revealed by global profiling of alternative splicing events regulated by PTB[END_REF][START_REF] Huelga | Integrative genome-wide analysis reveals cooperative regulation of alternative splicing by hnRNP proteins[END_REF]. As shown in Figure 4C, ESRP1 and 2 expression levels positively and negatively correlated with the inclusion rate (e.g., SI) of a set of included (EPI+) and excluded (EPI-) exons, respectively. Inversely, ESRP1 and 2 expression levels negatively and positively correlated with the inclusion rate of a set of included (FIBRO+) and excluded (FIBRO-) exons, respectively. Meanwhile, RBFOX2 expression levels positively and negatively correlated with the inclusion rate of a set of included (FIBRO+) and excluded (FIBRO-) exons, respectively. Finally, PTBP1 expression levels also nicely correlated with the inclusion rate of different exons enriched in endothelial cells.

To further explore the contribution of these splicing factors in controlling cell type-specific splicing programs, we analyzed publicly available data sets of crosslinking/immunoprecipitationsequencing (CLIP-seq) and/or exon array or RNA-seq analyses after RNAi for PTBP1, ESRP1, and RBFOX2 in human cell lines (Warzecha et al. 2009b;[START_REF] Xiao | Splice site strength-dependent activity and genetic buffering by poly-G runs[END_REF][START_REF] Xue | Genome-wide analysis of PTB-RNA interactions reveals a strategy used by the general splicing repressor to modulate exon inclusion or skipping[END_REF][START_REF] Yeo | An RNA code for the FOX2 splicing regulator revealed by mapping RNA-protein interactions in stem cells[END_REF][START_REF] Katz | Analysis and design of RNA sequencing experiments for identifying isoform regulation[END_REF][START_REF] Llorian | Positiondependent alternative splicing activity revealed by global profiling of alternative splicing events regulated by PTB[END_REF][START_REF] Huelga | Integrative genome-wide analysis reveals cooperative regulation of alternative splicing by hnRNP proteins[END_REF]). These analyses (Fig. 4D; Supplemental Table S8; see Supplemental Fig. S7 for the strategy used) and the RT-PCR validations (Fig. 4F; Supplemental Fig. S7) demonstrated that ESRP1/2, PTBP1/2, and RBFOX2 regulate a large subset within the cell type-specific alternative exons.

Additionally, ESRP1/2 binding sites were enriched in introns downstream from epithelial-included exons and upstream of epithelial-excluded exons (Fig. 4E; Supplemental Fig. S9; Supplemental Table S8), as expected from the previously reported ESRP splicing code (Warzecha et al. 2009a[START_REF] Warzecha | An ESRP-regulated splicing programme is abrogated during the epithelial-mesenchymal transition[END_REF][START_REF] Shapiro | An EMT-driven alternative splicing program occurs in human breast cancer and modulates cellular phenotype[END_REF][START_REF] Dittmar | Genome-wide determination of a broad ESRP-regulated posttranscriptional network by high-throughput sequencing[END_REF]. Likewise, RBFOX2 and PTBP1 binding sites were differentially enriched when comparing fibroblast-included and -excluded exons or endothelial-included and -excluded exons, respectively (Fig. 4E; Supplemental Fig. S9; Supplemental Table S8), in agreement with the previously reported RBFOX2 and PTBP1 splicing codes [START_REF] Xue | Genome-wide analysis of PTB-RNA interactions reveals a strategy used by the general splicing repressor to modulate exon inclusion or skipping[END_REF][START_REF] Llorian | Positiondependent alternative splicing activity revealed by global profiling of alternative splicing events regulated by PTB[END_REF].

Remarkably, a large number of fibroblast-, epithelial-, or endothelial-specific exons were predicted to be targeted by at least two splicing factors (Fig. 4G; Supplemental Table S8). Strikingly, as illustrated here for a few genes, some ESRP-regulated exons were regulated inversely by RBFOX2, while some RBFOX2-regulated exons were regulated inversely by PTBP1/2 (Supplemental Fig. S7). These data suggest that cell type-specific splicing programs may be controlled by a balanced expression of antagonist splicing factors. In other words, the splicing signature of a specific cell type likely depends on the combinatorial effects of both up-and down-regulated splicing factors, rather than by only up-regulated factors.

FasterDB: An integrative bioinformatics platform dedicated to alternative splicing analysis

In order to provide full support for performing functional genomics at exon-level resolution, the data sets presented above were organized in a freely available and user-friendly web interface. This novel database, named FasterDB (http://fasterdb.lyon.unicancer.fr/), provides researchers with information regarding the splicing variants generated for their genes of interest. Supplemental Figures S10-S21 demonstrate the use of FasterDB on the ENAH gene, which codes for the MENA protein that modulates cell adhesion and migration (Di [START_REF] Modugno | Splicing program of human MENA produces a previously undescribed isoform associated with invasive, mesenchymal-like breast tumors[END_REF]) and which has an exon (exon 12) that is specifically included in epithelial cells (Figs. 1C,3B). Thus, once the ENAH gene symbol is entered into the FasterDB search engine, FasterDB provides the description of the human and mouse genes as well as all known gene transcripts reported in public databases (Supplemental Fig. S10). Information regarding alternative use of exons, various features of exons and introns, exon conservation, UTRs, and miRNA binding site prediction can be obtained as well (Supplemental Figs. S11-S16).

FasterDB also provides information on the expression and splicing pattern of all protein-coding genes across a collection of 73 human cell lines (both normal and cancerous), 11 normal human tissues, nine mouse cell lines, and 11 normal mouse tissues corresponding to Affymetrix exon array data sets generated by The ENCODE Project Consortium and Affymetrix [START_REF] Thurman | The accessible chromatin landscape of the human genome[END_REF]. Clicking on ''Expression'' in the main toolbar (Supplemental Fig. S10B) reveals the relative level of gene expression across these panels (Supplemental Fig. S17) and provides the inclusion rate of any selected exon across the sample collection (Supplemental Fig. S18A), which can be helpful for selecting the adequate cellular model for functional studies of alternative splicing variants. To help with data mining, users can click on each cell line for a direct link to a dedicated visualization interface, named ELEXIR (Supplemental Figs. S18,S19).

Finally, FasterDB provides some clues about the splicing factors that might be involved in splicing regulation of their favorite gene. Indeed, the ''Splicing factors'' button in the main toolbar (Supplemental Fig. S10B) allows users to select different splicing factors and to access different kinds of information based on publicly available data sets [START_REF] Hung | Diverse roles of hnRNP L in mammalian mRNA processing: A combined microarray and RNAi analysis[END_REF]Warzecha et al. 2009b;[START_REF] Xiao | Splice site strength-dependent activity and genetic buffering by poly-G runs[END_REF][START_REF] Xiao | Nuclear matrix factor hnRNP U/SAF-A exerts a global control of alternative splicing by regulating U2 snRNP maturation[END_REF][START_REF] Xue | Genome-wide analysis of PTB-RNA interactions reveals a strategy used by the general splicing repressor to modulate exon inclusion or skipping[END_REF][START_REF] Yeo | An RNA code for the FOX2 splicing regulator revealed by mapping RNA-protein interactions in stem cells[END_REF][START_REF] Katz | Analysis and design of RNA sequencing experiments for identifying isoform regulation[END_REF][START_REF] Llorian | Positiondependent alternative splicing activity revealed by global profiling of alternative splicing events regulated by PTB[END_REF][START_REF] Wang | iCLIP predicts the dual splicing effects of TIA-RNA interactions[END_REF][START_REF] Grellscheid | Identification of evolutionarily conserved exons as regulated targets for the splicing activator tra2b in development[END_REF][START_REF] Lebedeva | Transcriptome-wide analysis of regulatory interactions of the RNA-binding protein HuR[END_REF][START_REF] Mukherjee | Integrative regulatory mapping indicates that the RNA-binding protein HuR couples pre-mRNA processing and mRNA stability[END_REF][START_REF] Huelga | Integrative genome-wide analysis reveals cooperative regulation of alternative splicing by hnRNP proteins[END_REF][START_REF] Lagier-Tourenne | Divergent roles of ALS-linked proteins FUS/TLS and TDP-43 intersect in processing long pre-mRNAs[END_REF][START_REF] Zarnack | Direct competition between hnRNP C and U2AF65 protects the transcriptome from the exonization of Alu elements[END_REF]. For example, selecting hnRNPH/F on the ''Splicing factors'' screen (Supplemental Fig. S20) gives access to predicted binding motifs (Fig. 5A) as well as to a dedicated CLIP-seq data visualization interface (Supplemental Fig. S21) based on the data set generated by Huelga and Katz [START_REF] Katz | Analysis and design of RNA sequencing experiments for identifying isoform regulation[END_REF]. From there, it is possible to zoom in and view the in cellulo binding sites of the selected splicing factor in the vicinity of the selected exon. For example, two hnRNPF binding sites were identified around ENAH exon 12, suggesting that hnRNPH/F might regulate ENAH splicing (Fig. 5B). To further challenge this possibility, the ''Exon Arrays'' button (Fig. 5A) gives access to Affymetrix exon array data obtained after hnRNPH/F depletion by Xiao and collaborators [START_REF] Xiao | Splice site strength-dependent activity and genetic buffering by poly-G runs[END_REF]. As shown in Figure 5C (upper panel), ENAH exon 12 probes appear red when comparing hnRNPH/F-depleted cells to control cells. This suggests that hnRNPH/F depletion favors exon inclusion, as validated by RT-PCR (Fig. 5C). Meanwhile, analysis of the ESRP data set generated by Warzecha et al. (2009b) predicts that ESRP depletion induces skipping of this exon (Fig. 5C, lower panel), as validated by RT-PCR (Fig. 4F). In sum, FasterDB will provide support for performing functional genomics at exon-level resolution by integrating publicly available large-scale data sets.

Discussion

It is well established that different tissues or organs (e.g., liver or kidney) express different splicing variants [START_REF] Pan | Deep surveying of alternative splicing complexity in the human transcriptome by highthroughput sequencing[END_REF][START_REF] Wang | Alternative isoform regulation in human tissue transcriptomes[END_REF][START_REF] Bland | Global regulation of alternative splicing during myogenic differentiation[END_REF][START_REF] De La Grange | Splicing factor and exon profiling across human tissues[END_REF][START_REF] Hartmann | Distinct regulatory programs establish widespread sexspecific alternative splicing in Drosophila melanogaster[END_REF][START_REF] Llorian | Decoding muscle alternative splicing[END_REF][START_REF] Barbosa-Morais | The evolutionary landscape of alternative splicing in vertebrate species[END_REF][START_REF] Merkin | Evolutionary dynamics of gene and isoform regulation in Mammalian tissues[END_REF]. However, all organs are composed of common major cell types like fibroblast, epithelial, and endothelial cells. In this report, we demonstrate that each major cell type expresses a specific splicing program independently of their organ origin (Figs. 123). It will be interesting to next determine whether a major cell type (e.g., endothelial cells) isolated from different tissues also expresses tissue-specific splicing programs. Looking at each column representing one specific cell type from a given organ in the clustering analyses (Figs. 1, 2; Supplemental Figs. S1-S3), the splicing pattern seems likely to integrate at least two levels of specificity, of cell type and tissue origin (Supplemental Fig. S22). Our observation has several consequences. For example, some tissue-specific splicing variants previously identified by comparing different tissues could in fact reflect the different relative proportions between common cell types in those tissues, as illustrated in Supplemental Figure S22. This could be particularly relevant for tumors that are often compared to normal control tissues to identify cancer-associated splicing variants. As many cancer cells derive from epithelial cells, some previously reported cancer-associated splicing variants could reflect epithelial cell enrichment in tumors as compared to normal tissues.

Remarkably, it has been previously shown that clustering cells based on global gene expression level also reveals that most cell lines cluster together rather than with their tissues of origin [START_REF] Lukk | A global map of human gene expression[END_REF]. As similar results were obtained using alternative spliced exons (ASE) (Fig. 3) and alternative first or last exons (AFE or ALE, respectively) (Supplemental Figs. S5, S6), this demonstrates that major cell types not only differ by the set of genes they expressed but also by the exonic content (e.g., ASE, AFE, and ALE) of the transcripts produced by the expressed genes. Therefore, our data imply that understanding the function of cell types not only requires the characterization of expressed genes but also of splicing variants generated by these expressed genes. In this context, it is interesting to underscore that genes that are differentially spliced in fibroblasts, epithelial, and endothelial cells are often involved in cell-cell or cell-substrate interactions (Supplemental Fig. S23). This suggests that alternative splicing may play a role in modeling interactions with neighboring cells and with the microenvironment.

We also identified three splicing factors, ESRP1, PTBP1, and RBFOX2, which are likely to play a major role in setting up these cell type-specific splicing programs (Fig. 4). Obviously, other splicing factors may contribute as well (Supplemental Table S8). For example, the highly related hnRNPH1 and hnRNPF splicing factors, which are in the same family as ESRP1 and are also involved in EMT (Warzecha et al. 2009a[START_REF] Warzecha | An ESRP-regulated splicing programme is abrogated during the epithelial-mesenchymal transition[END_REF][START_REF] Shapiro | An EMT-driven alternative splicing program occurs in human breast cancer and modulates cellular phenotype[END_REF][START_REF] Dittmar | Genome-wide determination of a broad ESRP-regulated posttranscriptional network by high-throughput sequencing[END_REF], were shown to also have an enriched expression in epithelial cells (Fig. 4A; Supplemental Table S8). Of note, although NOVA1 plays a role in establishing a neuronal splicing program, we observed that NOVA1 expression was enriched in fibroblasts, similar to RBFOX2 (Supplemental Table S8). Interestingly, it has been shown that the targets of RBFOX2 and of NOVA1 often overlap [START_REF] Zhang | Defining the regulatory network of the tissue-specific splicing factors Fox-1 and Fox-2[END_REF]. Conducting splicing analysis in a cell type-specific manner might allow new cellular functions of splicing factors to be identified. In this context, our data suggest a role of the PTBP1 and MBNL1 splicing factors in endothelial cell biology (Supplemental Table S8). Interestingly, PTBP1 and MBNL1 have been suggested to play a role in angiogenesis [START_REF] Pascual | The Muscleblind family of proteins: An emerging class of regulators of developmentally programmed alternative splicing[END_REF][START_REF] Pen | Molecular markers of extracellular matrix remodeling in glioblastoma vessels: Microarray study of laser-captured glioblastoma vessels[END_REF][START_REF] Masuda | RNA-binding proteins implicated in the hypoxic response[END_REF].

Functional genomics now needs to be performed at an exonic resolution level, given the prevalence and importance of alternative splicing. This will require new integrative bioinformatic ap- proaches to be developed that can handle the diversity of alternative exons and the complexity of alternative splicing regulation. In this setting, we have made the analyzed data sets used in this report freely available through the user friendly web interface of FasterDB, which describes all known splicing variants of human and mouse genes and their splicing pattern across several dozen normal and cancer cells and tissues, as well as information regarding which splicing factors contribute to individual exon regulation. The aim of this database is to help researchers identify the different splicing variants of their favorite genes as well as the tissue, cell type, or cell line in which they are expressed, in order to facilitate further functional and/or mechanistic studies. For example, when researchers identify a splicing variant in physiopathological conditions, FasterDB will be useful in deciding which cellular model might be suitable for functional analysis.

The second aim of FasterDB is to help researchers characterize the splicing factors regulating the identified splicing variants. To the best of our knowledge, FasterDB is the first database integrating large-scale data sets focused on splicing, including CLIP-seq and splicing-sensitive microarray data sets [START_REF] Hung | Diverse roles of hnRNP L in mammalian mRNA processing: A combined microarray and RNAi analysis[END_REF]Warzecha et al. 2009b;[START_REF] Xiao | Splice site strength-dependent activity and genetic buffering by poly-G runs[END_REF][START_REF] Xiao | Nuclear matrix factor hnRNP U/SAF-A exerts a global control of alternative splicing by regulating U2 snRNP maturation[END_REF][START_REF] Xue | Genome-wide analysis of PTB-RNA interactions reveals a strategy used by the general splicing repressor to modulate exon inclusion or skipping[END_REF][START_REF] Yeo | An RNA code for the FOX2 splicing regulator revealed by mapping RNA-protein interactions in stem cells[END_REF][START_REF] Katz | Analysis and design of RNA sequencing experiments for identifying isoform regulation[END_REF][START_REF] Llorian | Positiondependent alternative splicing activity revealed by global profiling of alternative splicing events regulated by PTB[END_REF][START_REF] Wang | iCLIP predicts the dual splicing effects of TIA-RNA interactions[END_REF][START_REF] Grellscheid | Identification of evolutionarily conserved exons as regulated targets for the splicing activator tra2b in development[END_REF][START_REF] Lebedeva | Transcriptome-wide analysis of regulatory interactions of the RNA-binding protein HuR[END_REF][START_REF] Mukherjee | Integrative regulatory mapping indicates that the RNA-binding protein HuR couples pre-mRNA processing and mRNA stability[END_REF][START_REF] Huelga | Integrative genome-wide analysis reveals cooperative regulation of alternative splicing by hnRNP proteins[END_REF][START_REF] Lagier-Tourenne | Divergent roles of ALS-linked proteins FUS/TLS and TDP-43 intersect in processing long pre-mRNAs[END_REF][START_REF] Zarnack | Direct competition between hnRNP C and U2AF65 protects the transcriptome from the exonization of Alu elements[END_REF]. Our next goal will be to include other data sets, such as RNA-seq data sets. We also aim to label the protein domains coded by each alternatively spliced exon in order to help users predict potential functional consequences resulting from alternative splicing.

Methods

FasterDB core database

Human and mouse exons were collected from Ensembl (release 60, assemblies GRCh37 and NCBI m37) [START_REF] Flicek | Ensembl 2013[END_REF]) and aligned against the NCBI transcript database using MEGABLAST (v 2.2.25). These exons were aligned against genomic sequences to define their chromosomal coordinates and then clustered by genomic position to define seven major events (e.g., alternative first exon, alternative last exon, alternative 39 splice site, alternative 59 splice site, intron retention, exon deletion, and exon skipping). Scores were computed using MaxEntScan for each splice site. For each gene, a nonredundant repertory of untranslated regions was established using all corresponding transcripts. UTRs were more fully characterized by describing the motifs found in their sequences using PatSearch Tool [START_REF] Grillo | PatSearch: A program for the detection of patterns and structural motifs in nucleotide sequences[END_REF]. miRNA binding sites were predicted using PITA, miRanda, and PicTar [START_REF] John | Human MicroRNA targets[END_REF][START_REF] Lewis | Conserved seed pairing, often flanked by adenosines, indicates that thousands of human genes are microRNA targets[END_REF][START_REF] Kertesz | The role of site accessibility in microRNA target recognition[END_REF]). Conserved exons between human and mouse were identified by aligning each human exon against the exons of its orthologous mouse gene as provided by Ensembl. The ''in silico PCR'' tool is based on a multialignment of the transcript exons performed with ClustalW. FasterDB is built in Perl (v5.14.2) and runs on a Ubuntu server (v12.04.1) that hosts Apache (v.2.2.16) and MySQL (v5.1.49) servers. More information is available in Supplemental Material and can be downloaded from http://fasterdb.lyon.unicancer.fr.

Exon array data set analyses

Cell lines and tissues expression data were downloaded from the GEO and Affymetrix websites and corresponded to Affymetrix Exon Arrays data sets as listed in Supplemental Table S10. The preprocessing pipeline is described in more detail in the Supple-mental Material (Part 2, Section 2.2, page 9). Briefly, low-quality and cross-hybridizing probes were removed, and signals were summarized at the gene level by using the median over all remaining probes. Three different ways of computing the inclusion/exclusion rates of a given exon were computed by measuring the ratio of (1) its expression level versus the gene expression level (NI); (2) its NI in the condition of interest relative to the NI in the control condition (global SI); or (3) its expression level versus the expression level of the flanked exons (local SI). Computation of the global and local SI is described in more detail in the Supplemental Material (Part 2, section 2.2, page 10). Identification of cell type-specific alternative exons was performed after computing local SI and selecting exons with local SI above 1.45 and with a P-value <0.05. Heatmaps were generated using the multiexperiment viewer application of the TM4 package. Hierarchical clustering of Mev4 was also used to cluster cell lines that have similar regulation. Input data contains the SI of each of the regulated ASEs in each of the analyzed cell lines. The SI was computed for each cell line in comparison with all the different types of cell lines. Functional enrichment and KEGG pathway mapping were done using DAVID [START_REF] Huang Da | Systematic and integrative analysis of large gene lists using DAVID bioinformatics resources[END_REF]).

Elexir web interface

Elexir is a web application that allows users to choose an experiment within a set of stored exon array experiments. This interface was developed to allow the end user to easily browse and query the expression levels of one or more genes between conditions, with possible replicates for each condition. Different test conditions can be chosen for each experiment. A condition can be defined as a cell line, a tissue type, or a treatment. Paired or unpaired analyses can be done depending on sample relationships used for test and control conditions. The intensity report displays a schematic graph of the gene being analyzed with corresponding probes for each exon. The height of each bar represents the normalized probe intensity (in log2). The color reflects the ratio of probe intensity between test and control conditions. Green and red indicate that the probe intensity in the test condition is lower and higher, respectively, than the control condition. Information for each probe is given in the underlying descriptive table or can be easily obtained by clicking on the bar.

Splicing factor analyses

The regulation of cell type-specific ASEs by specific splicing factors was tested using three different sources: microarray data, literature RNA-seq, and CLIP-seq data sets. Chromosomal coordinates of exons regulated by ESRP1, PTBP1, and/or RBFOX2 identified by RNA-seq were retrieved from previously published work (Warzecha et al. 2009b;[START_REF] Xiao | Splice site strength-dependent activity and genetic buffering by poly-G runs[END_REF][START_REF] Xue | Genome-wide analysis of PTB-RNA interactions reveals a strategy used by the general splicing repressor to modulate exon inclusion or skipping[END_REF][START_REF] Yeo | An RNA code for the FOX2 splicing regulator revealed by mapping RNA-protein interactions in stem cells[END_REF][START_REF] Katz | Analysis and design of RNA sequencing experiments for identifying isoform regulation[END_REF][START_REF] Llorian | Positiondependent alternative splicing activity revealed by global profiling of alternative splicing events regulated by PTB[END_REF][START_REF] Huelga | Integrative genome-wide analysis reveals cooperative regulation of alternative splicing by hnRNP proteins[END_REF]. ASEs predicted to be regulated by a splicing factor using exon array or RNA-seq data sets were compared to ASEs predicted to be cell type-specific. For each cell type, we paid attention to the ASE regulation sense. For example, PTBP1 is up-regulated, while ESRP1 and RBFOX2 are down-regulated, in endothelial cells; thus, an endothelial ASE is predicted to be regulated by one of these factors if it is skipped upon PTBP1 depletion or included by ESRP1 or RBFOX2 depletion. To be considered as confident, CLIP hits must have been detected in the exon or within 100 nt upstream of or downstream from the exon.

Splicing factor binding sites were searched with the PatSearch Tool [START_REF] Grillo | PatSearch: A program for the detection of patterns and structural motifs in nucleotide sequences[END_REF] for the genomic sequences using previously defined splicing factor binding motifs (see Supplemental Table S8).

Cell type-specific splicing programs Genome Research 519 www.genome.org A set of 1000 randomly selected alternative exons, and a set of 1000 randomly selected constitutive exons, were used as controls. Four regions were defined: 100 nt upstream of and downstream from the exon, the first 60 nt of the exon and the last 60 nt of the exon. For each region, a sliding window of a specific length was considered, and the enrichment score of the splicing factor was computed at each position as (S number of factor motifs at position X / total number of analyzed sequences) 3 100. The total number of binding sites found in each region of each exon group was used to compute the standard deviation value.

Experimental validation

RNA from different cell types were purchased as indicated in Supplemental Table S1. Primers used for RT-PCR are described in Supplemental Table S9. RT-qPCR analyses were performed using primers described in Supplemental Table S9. Epithelial MCF-7, fibroblast-like MDA-MB-231 cells, and endothelial HUVEC cells were transfected using RNAiMax (Invitrogen) with control siRNAs or siRNAs against ESRP1 and 2, RBFOX2, or PTBP1 and 2 (Supplemental Table S9) 48 h before RNA extraction. Electrophoretic gels were analyzed with ImageJ software.

Figure 1 .

 1 Figure1. Epithelial-and fibroblast-specific splicing variants. (A) Transcriptome analysis of fibroblasts (fibro) as compared to epithelial (epi) cells at both gene and exon levels. The number of genes differentially expressed at the gene and/or exon level when comparing both cell types is shown in the left panel. The middle panel indicates the classification of events corresponding to exon level variations. Differentially expressed exons were classified according to their annotation using publicly available transcripts: alternative first exon (AFE), alternative last exon (ALE), and alternative skipped exon (ASE). Not annotated (NA) corresponds to exons that do not correspond to any of the above-mentioned categories. The cellular functions of genes differentially spliced when comparing fibroblasts to epithelial cells are indicated in the right panel. (B) Heatmap presentation of the splicing index (SI) values for exons differentially spliced when comparing fibroblast to epithelial cells. Each line corresponds to a regulated exon, while each column corresponds to a specific cell. Green boxes (-1.5 < SI < 0) correspond to a low inclusion level in the cell as compared to all the others; red boxes (0 < SI < 1.5), high inclusion level; black boxes (SI = 0), no difference for exon inclusion between cells; and gray boxes, missing values. Exons were computationally split into several groups depending on their inclusion rate that correlates with the two major cell types. (C ) RT-PCR validations using RNAs from fibroblasts and epithelial cells, as indicated.

Figure 2 .

 2 Figure 2. Epithelial-and endothelial-specific splicing variants. (A) Same as in Figure 1A but comparing endothelial (Endo) to epithelial (Epi) cells. (B) Same as in Figure 1B but comparing endothelial (Endo) to epithelial (Epi) cells. (C ) RT-PCR validations using RNAs from endothelial and epithelial cells, as indicated.

Figure 3 .

 3 Figure 3. Cell type-specific splicing programs. (A) Heatmap presentation of the SI values for exons differentially spliced across fibroblast, endothelial, and epithelial cells. Exons were computationally split into several groups depending on their inclusion rate in the three major cell types. Every brace corresponds to a group (names are indicated on the left); their exons are surrounded by a yellow rectangle on the heatmap. The different categories of exons are indicated as follows: epithelial-included (EPI+), epithelial-skipped (EPI-), endothelial-included (ENDO+), endothelial-skipped (ENDO-), fibroblast-included (FIBRO+), and fibroblast-skipped (FIBRO-) exons. (B) Inclusion rate of selected exons measured after RT-PCR using cells from different origins. The gene symbol and exon position are indicated. Inclusion rates are given for epithelial cells compared to both fibroblast and endothelial cells (upper panel), fibroblasts compared to both epithelial and endothelial cells (middle panels), and endothelial cells compared to both fibroblast and epithelial cells (lower panel).

Figure 4 .

 4 Figure 4. Cell type-specific expression of splicing factors. (A) Heatmap of splicing factor expression level.Each line represents a splicing factor, while each column represents a specific cell. The color of the square corresponds to the variation of the expression level of the splicing factor in each specific cell as compared to the others (green, less expressed in the cell; red, more expressed in the cell; and black, no difference). (B) RT-qPCR analysis of the expression level of ESRP1, PTBP1, MBNL1, RBFOX2, and NOVA1 in a collection of fibroblasts, epithelial and endothelial cells. (C ) Spearman correlations between splicing factor expression level and the inclusion rate of epithelial-included (EPI+), epithelial-skipped (EPI-), endothelial-included (ENDO+), endothelial-skipped (ENDO-), fibroblast-included (FIBRO+), and fibroblast-skipped (FIBRO-) exons. Warm colors indicate positive correlation (e.g., a high exon inclusion level that correlates with a high splicing factor expression level), whereas cold colors indicate negative correlation (e.g., a low exon inclusion level that correlates with a high splicing factor expression level). Gray boxes indicate correlations that were discarded because of values that were not statistically significant or insufficient data available to compute correlations. (D) Summary table of epithelial-, fibroblast-, and endothelial-specific exons predicted to be regulated by the ESRP1, PTBP1, and RBFOX2 splicing factors using RNA-seq, exon array, and CLIP-seq data sets (see Supplemental Fig.S4for more information). The number and percentage of exons predicted to be regulated by each splicing factor in each category are indicated. (E) Schematic representation of splicing factor binding site enrichment in several sets of exons differentially regulated across epithelial, endothelial, or fibroblast cells. Columns define regions in which the binding site searches were done. (F) RT-PCR analyses of the effect of depleting ESRP1, RBFOX2, or PTBP1 on alternative splicing of selected genes in the MCF-7 epithelial cell line, the MDA-MB-231 fibroblast-like cell line, or the HUVEC endothelial cell line, respectively. (G) Venn diagrams representing the number of epithelial-, fibroblast-, and endothelial-specific exons predicted to be regulated by ESRP1, PTBP1, and/or RBFOX2.

Figure 5 .

 5 Figure 5. Dedicated CLIP-seq data visualization web interface. (A) Localization of predicted hnRNPH/F binding motifs in the vicinity of the ENAH exon 12 and their link to splicing factor data sets. (B) Reads from a CLIP-seq experiment corresponding to hnRNPF binding sites in the vicinity of the ENAH exon 12. (C ) Visualization of exon array probe intensities in hnRNPH/F-or ESRP1-depleted cells as compared to control cells. RT-PCR analysis of the ENAH exon 12 inclusion rate in hnRNPH/F-depleted or control cells.

www.genome.org

Acknowledgments

We thank the researchers who deposited their data sets in public libraries. We hope that our website will be welcomed by both users and the researchers who generated the data sets and that we did not forget to acknowledge any of those researchers in Supplemental Table S10 and on the FasterDB website. This work was supported by the Fondation pour la Recherche Me ´dicale (FRM), INSERM Plan Cancer 2009-2013, Institut National du Cancer (INCa), Agence Nationale de la Recherche (ANR), and Association Franc xaise Contre les Myopathies (AFM). P.M. was supported by Lyon Science Transfert, J-P.V. and H.M. by FRM, F-O.D. by the Association pour la Recherche sur le Cancer, M.P.E. by AFM, S.S. by the Ligue National Contre le Cancer, L-C.T. and E.C. by INSERM ''Plan Cancer 2009-2013.''

Data access

The FasterDB database is available at http://fasterdb.lyon.unicancer.fr/.