Lucas Mello Schnorr

Arnaud Legrand

Jean-Marc Vincent

Interactive Analysis of Large Distributed Systems with Topology-based Visualization

Keywords: Distributed application analysis, interactive analysis, topological visualization

The performance of parallel and distributed applications is highly dependent on the characteristics of the execution environment. In such environments, the network topology and characteristics directly impact data locality and movements as well as contention, which are key phenomena to understand the behavior of such applications and possibly improve it. Unfortunately few visualization available to the analyst are capable of accounting for such phenomena. In this paper, we propose an interactive topology-based visualization technique based on data aggregation that enables to correlate network characteristics, such as bandwidth and topology, with application performance traces. We claim that such kind of visualization enables to explore and understand non trivial behavior that are impossible to grasp with classical visualization techniques. We also claim that the combination of multi-scale aggregation and dynamic graph layout allows our visualization technique to scale seamlessly to large distributed systems. We support these claims through a detailed analysis of a high performance computing scenario and of a grid computing scenario.

Analyse interactive de grands systèmes distribués avec une visualisation topologique de la plate-forme passant à l'échelle Résumé : Les performances des applications parallèles et distribuées dépendent fortement des caractéristiques de l'environnement d'exécution. Dans de tels environnements, la topologie du réseau et ses caractéristiques ont un impact direct sur la localité et les mouvements des données ainsi que sur la contention, qui sont des phénomènes clés pour comprendre le comportement de ces applications et éventuellement les améliorer. Malheureusement, peu de visualisation permettent de mettre en évidence ces phénomènes. Dans cet article, nous proposons une technique de visualisation interactive et topologique basée sur l'agrégation de données qui permet de corréler les caractéristiques du réseau, telles que la bande passante et la topologie, avec des traces de performances des applications. Ce type de visualisation permet d'explorer et de comprendre des comportements non triviaux qui sont impossibles à appréhender avec les techniques de visualisation classiques. Nous affirmons également que la combinaison de l'agrégation multi-échelle et l'agencement dynamique du graphe permet à notre technique de visualisation de passer à l'échelle. Nous étayons ces affirmations par l'analyse détaillée d'un scénario de calcul haute performance et d'un scénario de grid computing.

Mots-clés : Analyse des applications distribuées, analyse interactive, visualisation topologique 1 Introduction

To achieve desirable scale, today's parallel or distributed platforms generally consist of hundreds to millions of processing units interconnected by complex hierarchical networks. The performance of large scale distributed application is thus highly dependent on the characteristics (bandwidth, latency, topology) of the interconnection network and of the processing nodes. To obtain good performance, application developers need to keep in mind data locality and to organize data movement both in space and time without being harmed by potential congestion arising from the application itself or from other applications competing for resources. To perform such optimization and understand performance issues in such systems it is thus crucial to rely on well-suited analysis tools.

Several visualization techniques have been developed to tackle the issue of performance analysis and give a view of the behavior of applications. Besides statistical charts with profiling information, a common technique is called timeline views, based on Gantt-charts [START_REF] Wilson | Gantt charts: A centenary appreciation[END_REF]. It depicts the individual behavior of processes and the interactions among them. Several types of performance problems can be detected: slower processes, late senders, critical path identification and evaluation and so on. In the situations when performance issues might be correlated to the network, this visualization technique fails to link the application state to the actual cause of problem. The main reason is because timelines have no way to depict topology together with application traces. Other visualization techniques share the same problem. Communication matrices and statistical charts, for example, present per-process interactions and global summaries, with no network correlation. Existing solutions [START_REF] Desell | Overview: A framework for generic online visualization of distributed systems[END_REF][START_REF] Aguerre | Fully-distributed debugging and visualization of distributed systems in anonymous networks[END_REF] for a topological analysis of distributed systems suffer from serious scalability problems.

In this paper, we propose a novel scalable technique for interactive analysis of large-scale distributed systems using a topology-based visualization. The method easily correlates network bandwidth and topology with the application behavior. Although topology-based visualization are not new, they are generally difficult to configure and to use in practice and scale generally badly with the amount of information to display. We address these issues with a combination of two techniques:

Multi-scale data aggregation. Some behavior appears only in subtle information scales.

Our approach uses a data aggregation policy to reduce and analyze information in different user-defined space and time scales. The space dimension is chosen by the analyst by grouping nodes in the topology-based representation, while the time dimension is configured through the use of time-slices.

Dynamic and interactive graph layout. Dynamic node aggregation requires to dynamically recompute graph layout, which may confuse the analyst if there is too much changes between the two layouts. Therefore, our topology-based representation relies on a force-directed graph algorithm that enables a smooth evolution of nodes position. The user influences the algorithm by interactively moving and aggregating/disaggregating group of nodes and possibly by adjusting repulsion and attraction parameters.

By letting the analyst a complete control on a few key parameters, we allow him to easily and dynamically explore the application trace in relation with the platform topology. The paper is structured as follows. Section 2 presents the related work and a discussion on the differences between our approach and existing solutions. Section 3 details the main ingredients of our proposal: how traces are mapped to the graph, the multiscale data aggregation and the dynamic and interactive layout. Section 4 presents some implementation details about the interactivity of our approach. Section 5 presents a detailed analysis of two scenarios. The first case study is derived a from high performance computing setting and illustrates non-trivial insights that can be obtained with our visualization and that would be impossible to grasp with more classical representations. The second case study is based on a grid computing setting and illustrates the necessity of multi-scale aggregation capabilities and how it can be used to investigate locality and resource sharing between competing applications.

Related work

We classify related research in three sections: analysis methodologies, performance visualization techniques, and graph drawing techniques. The first presents the many data analysis methodologies employed to analyze collected information. The second presents interactive visualization techniques used to analyze traces. The third section presents existing graph drawing techniques that could be used in performance analysis. The section ends with a discussion about how our approach combines the techniques of these related research areas to provide a novel way to visualize performance data.

Data analysis methodologies

Several methodologies exist to do performance analysis. The analysis of profiles, traces and statistics of a given execution may be, for example, text or graphics-based, interactive or automatic, online versus postmortem and so on. The methodology adopted for a given large-scale application highly depends on the nature of performance issues that are under investigation. Questions such as the characteristics of the application, whether it is CPU or network-bound, among others, must be taken into account and be used to select the best analysis methodology for each case.

Even if there is no single solution in terms of analysis methodology for performance analysis, a simple approach is to get an overview first, then look for details. The overview can be obtained using profiling techniques, executing either a direct or indirect measurement. After solving high-level performance problems, the analyst can obtain a more detailed behavior by tracing the application with well-chosen instrumentation points. Traces from large-scale distributed and parallel applications are usually centralized to allow an interactive analysis of the data. Trace analysis is usually performed with the aid of visualization tools, sometimes called trace browsers. Examples of these tools are Vampir [START_REF] Brunst | Comprehensive performance tracking with vampir 7[END_REF], Paje [START_REF] Chassin De Kergommeaux | Pajé, an interactive visualization tool for tuning multi-threaded parallel applications[END_REF], ViTE [START_REF] Coulomb | Visual trace explorer (vite)[END_REF] among many others [START_REF] Laxmikant | Scaling applications to massively parallel machines using projections performance analysis tool[END_REF][START_REF] Pillet | Paraver: A tool to visualise and analyze parallel code[END_REF][START_REF] Zaki | Toward scalable performance visualization with jumpshot[END_REF][START_REF] Mello Schnorr | Triva: Interactive 3d visualization for performance analysis of parallel applications[END_REF].

More recently, automatic trace analysis [START_REF] Mohr | Kojak-a tool set for automatic analysis of parallel programs[END_REF][START_REF] Gonzalez | Automatic detection of parallel applications computation phases[END_REF] emerged as a solution where previously known performance problems are harvested by a program. The development of automatic pattern detection appeared to be a more scalable alternative to the interactive and serial analysis done by a human analyst. While there is development to provide intra-process pattern detection [START_REF] Freitag | A trace-scaling agent for parallel application tracing[END_REF], the combination of this with inter-process pattern detection is also already explored [START_REF] Knüpfer | Visualization of repetitive patterns in event traces[END_REF]. The automatic approach for trace analysis is also used to correlate the application-level communication topology with possible performance issues [START_REF] Song | Automatic experimental analysis of communication patterns in virtual topologies[END_REF]. Automatic trace analysis is also implemented in Scalasca to look for known performance problems, such as the source of wait states [START_REF] Becker | Automatic trace-based performance analysis of metacomputing applications[END_REF]. Although most of these solutions are used in a postmortem fashion, the online approach with automatic tuning [START_REF] Karcher | Run-time automatic performance tuning for multicore applications[END_REF] is also found in the literature.

Inria

Clustering algorithms [START_REF] Lee | Towards scalable performance analysis and visualization through data reduction[END_REF][START_REF] Joshi | Measuring benchmark similarity using inherent program characteristics[END_REF], sometimes hierarchically organized [START_REF] Aguilera | A systematic multi-step methodology for performance analysis of communication traces of distributed applications based on hierarchical clustering[END_REF], are also explored in performance analysis. The idea of grouping processes behavior by similarity is used in interactive visualization tools, such as Vampir [START_REF] Brunst | Comprehensive performance tracking with vampir 7[END_REF], to decrease the number of processes listed in the time-space view. Although the different techniques of automatic trace analysis previously discussed also employ clustering to group processes patterns, some argue that a subset of clustering algorithms used at a coarse grain level are no longer adequate [START_REF] Gonzalez | Automatic detection of parallel applications computation phases[END_REF]. Another approach tries to define a similarity metric that gives a good trace size reduction and at the same time keeps enough data for a correct analysis [START_REF] Mohror | Evaluating similarity-based trace reduction techniques for scalable performance analysis[END_REF].

Visualization techniques

Visualization techniques for performance analysis have been present since the earliest time of parallel and distributed application analysis. Different visual representations of traces give the analyst the power to observe outliers and look for performance issues by actually seeing what has happened during the execution. We classify the visualization techniques according to how data is presented: behavioral, with data depicted along a timeline; structural, showing how monitored elements are interconnected, without a timeline; and statistical, grouping scatter-plot representations.

The best well-known and intuitive example of a behavioral representation is the timeline view, derived from Gantt-charts [START_REF] Wilson | Gantt charts: A centenary appreciation[END_REF]. It lists all the observed entities, sometimes organized as a hierarchy [START_REF] Chassin De Kergommeaux | Pajé, an interactive visualization tool for tuning multi-threaded parallel applications[END_REF], in the vertical axis. Their behavior is represented along time in the horizontal axis: rectangles represent application states, while links represent communications among the observed entities. Examples of tools providing this type of visualization are Vampir [START_REF] Brunst | Comprehensive performance tracking with vampir 7[END_REF], Paje [START_REF] Chassin De Kergommeaux | Pajé, an interactive visualization tool for tuning multi-threaded parallel applications[END_REF] Projections [START_REF] Laxmikant | Scaling applications to massively parallel machines using projections performance analysis tool[END_REF] and many others [START_REF] Pillet | Paraver: A tool to visualise and analyze parallel code[END_REF][START_REF] Coulomb | Visual trace explorer (vite)[END_REF][START_REF] Zaki | Toward scalable performance visualization with jumpshot[END_REF]. The advantage of timeline views is the emphasis on time and event causality, enabling a fine grain performance analysis. Timeline views are, however, naturally limited by the size of the screen. Only a subset of entities can be observed at the same time. Some tools, especially Vampir, already incorporate techniques to turnaround these visualization scalability issues. It has a clustering algorithm [START_REF] Brunst | Comprehensive performance tracking with vampir 7[END_REF] to reduce the number of entities in the vertical axis, and a method to hide repetitive patterns in the horizontal axis [START_REF] Knüpfer | Visualization of repetitive patterns in event traces[END_REF].

Structural techniques is a different kind of trace visualization where the structure of the observed application or system is primarily depicted. Techniques that enter this classification are the topology-based visualization of ParaGraph [START_REF] Heath | Visualizing the performance of parallel programs[END_REF]; a three dimensional representation for large-scale grid environments with the network interconnection [START_REF] Mello Schnorr | Visual mapping of program components to resources representation: a 3d analysis of grid parallel applications[END_REF]; the call-graph representation of ParaProf [START_REF] Bell | Paraprof: A portable, extensible, and scalable tool for parallel performance profile analysis[END_REF] and Virtue [START_REF] Shaffer | Virtue: Performance visualization of parallel and distributed applications[END_REF]; and communication matrices, implemented in Vampir [START_REF] Brunst | Comprehensive performance tracking with vampir 7[END_REF] and others. The main difference of these representations is that they are independent of a timeline; they consider values at a given point in time or time-aggregated data.

Statistical visualization techniques is the most common way of representing data. It consists mainly in statistical charts, scatter-plots and summaries of tracing data. Vampir [START_REF] Brunst | Comprehensive performance tracking with vampir 7[END_REF] has a number of charts of this type, such as a function, process and message summary. It also has a call tree that fits into this classification. Bar and pie charts also are part of this category, and are present in several visualization tools such as ParaGraph [START_REF] Heath | Visualizing the performance of parallel programs[END_REF], Paradyn [START_REF] Miller | The paradyn parallel performance measurement tool[END_REF], and Paje [START_REF] Chassin De Kergommeaux | Pajé, an interactive visualization tool for tuning multi-threaded parallel applications[END_REF]. Kiviat diagram [START_REF] Heath | Visualizing the performance of parallel programs[END_REF] and statistical 3D representations [START_REF] Bell | Paraprof: A portable, extensible, and scalable tool for parallel performance profile analysis[END_REF] are other examples of statistical representations.

Graph Drawing

Graph drawing concerns with all the aspects related to the geometric representation of graphs. Several applications makes use of the techniques proposed by graph drawing, such as social network analysis, and cartography. Computer network topologies also applies these techniques to create graphical representations of the interconnection. By convention, graph drawings are frequently drawn as bi-dimensional node-link diagrams. Several quality measures are taken into account when drawing a graph: area used, symmetry, angular resolution (the sharpest angles among edges), and crossing number (maximum number of crossing edges) to cite some of them.

The definition of the nodes position is one of the most important parts for graph drawing. There are many methods to define them: circular, radial, hierarchical, and force-based, for example. Each of these general methods have several specific algorithms that may be applied depending on the graph configuration and visualization required. Graphviz [START_REF] Ellson | Graphviz-open source graph drawing tools[END_REF] and the Open Graph Drawing Framework [START_REF] Chimani | The open graph drawing framework[END_REF] implement many of these methods, which generally follow a static approach: nodes and edges are given to the algorithm, generating a resulting layout with node position. Some layout algorithms are better adapted to dynamic layouts, which have to evolve due to graph changes. Force-directed algorithms [START_REF] Thomas | Graph drawing by forcedirected placement[END_REF] iterate through multiple steps to converge to a stable layout, being well adapted to dynamic graphs.

Discussion

Our approach proposes a novel interactive graph visualization that considers the network topology in the performance analysis. In this comparison with related work, we contrast our approach with existing visualization techniques and then compare our methodology with other data analysis approaches.

The traditional timeline view is expected by most of users of high performance computing, as can be observed by the number of visualization tools that implement it. Although useful and well-suited to behavior analysis in homogeneous environments, such as small-scale clusters where network latency and bandwidth heterogeneity is limited, timeline views lack topological information. Contrasting behavior with topological data is sometimes crucial for the comprehension of application behavior in distributed systems and heterogeneous systems. Our graph-based representation can be classified as a structural technique, where the topology, usually that from the logical or physical interconnection, is represented. ParaGraph, Triva and OverView are examples of tools that have topological representations. ParaGraph's approach differs from ours in two points: the graph representation is fixed according to the physical network topology, whereas our method gives the analyst the freedom to choose how elements of the graph are going to be connected in the representation; and second point, our graph representation is capable to represent time and spatial aggregated data, while ParaGraph topological representation [START_REF] Heath | Visualizing the performance of parallel programs[END_REF] only shows instantaneous information. Triva already implemented a three dimensional visualization with the network topology depicted in the base of the visualization [START_REF] Mello Schnorr | Visual mapping of program components to resources representation: a 3d analysis of grid parallel applications[END_REF], but the technique only shows timestamped events along the vertical time axis, without the possibility to aggregating them in space and time and using these aggregated values to customize the graph. Another aspect of our approach is that we employ a dynamic force-directed layout system, improving the interactivity of the analyst with the monitored elements. OverView [START_REF] Desell | Overview: A framework for generic online visualization of distributed systems[END_REF] has a topological representation of distributed systems, also with force-directed algorithm for positioning, but it does not allow to spatial or temporal aggregated data, which turns out to be Inria an essential feature as we will explain later.

Our analysis methodology is interactive and exploratory [START_REF] Wilder | Exploratory Data Analysis[END_REF] in time and space. The idea is to let the analyst freely navigate through the different dimensions of performance data to find issues and potential improvements to do. The automatic analysis is a different approach were a computer program searches the traces for known and expected problems. We believe that these automatic techniques are limited to the situations they were conceived to detect, possibly missing unexpected behaviors. An automatic methodology should only be applied to guide the analyst through an exploratory and interactive performance analysis. An example of this is Vampir, applying a clustering algorithm to increase the scalability of its timeline view.

The use of multi-scale data aggregation with dynamic graph layout to obtain a scalable interactive graph-based visualization that allows to perform exploratory data analysis is the key idea of our contribution. By using such visualization, the analyst is capable to easily navigate through time and space aggregated data, while keeping the ability to correlate such data to the topology at any time. Such feature enables the easy detection of several performance issues such as performance bottlenecks and inefficiencies in the hosts or in the network of a parallel and distributed environment. Next Section details our approach, followed by implementation details and case studies that show the usefulness of our proposal.

Mapping trace metrics to the graph

In our approach, the nodes of the graph represent monitored entities, while edges indicate only a relationship between two monitored entities. The visualization is enhanced by mapping the metrics of each monitored entity to all available geometric shapes and properties of its corresponding node. For example, a square can be used to represent a host, its size according to its computing power; a diamond to a network link, its size according to the bandwidth utilization, and so on.

The key-point of a certain mapping is how easy the visual differences among the objects are perceived by the analyst. By our experience, we have observed how crucial this is to perceive the data in the visualization. For this reason, we have chosen to limit the amount of geometric shapes and attributes. Only simple shapes and properties are used: square, diamond and circle as representations; node color and size, and an optional filling of the shapes as properties.

Any mapping defined can be dynamically changed at a given point of the analysis. This might be motivated by needs from the analysis, but also by a different set of available metrics in another part of the trace file that should be represented in a different way. We detail next an example of the mapping from trace to graph.

Example of mapping

In this example, traces are composed of timestamped events that represent the available computing power for two hosts and the available bandwidth for one link. The scatter plot of Figure 1 depicts the resource availability (solid lines) and utilization (dashed lines) for them. We map hosts to squares and the link to a diamond shape. The available resource capacity defines the size of each geometric shape at a given timestamp; the resource utilization defines the proportional fill inside each of them. The plot in the left of the Figure 1 How the monitored entities are connected to each other is another information needed for the mapping. This information can be obtained for different sources. First, the traces can be used if we need to connect processes according to the messages exchanged among them. Second, the connection data can also be fixed, previously defined, as in the case when the monitored entities are part of the network topology of a distributed systems. And third, the information can be dynamically provided by the analyst, depending on the needs for the analysis.

Mapping a selected set of trace values to the topological representation enables the analyst to reduce the analysis complexity. Even if an appropriate set is chosen, the amount of data can be significant imposing restrictions on the analysis of large-scale traces containing thousands of elements and a very detailed behavior registered along time. To tackle this complex and large-scale situations, we employ in our approach a data aggregation that works in the space and time dimensions. The techniques employed are described in the next Subsection.

Multi-scale data aggregation

The observation of large-scale distributed systems over a long period of time usually leads to large amounts of trace data that are particularly hard to understand. Some behavior is present only at small time or space scale, others appear at a larger scale. The understanding of these different phenomena requires an easy navigation in all scales of trace data, especially those related to time and space.

Inria

We briefly detail how data aggregation is formally defined in our context. Let us denote by R the set of resources and by T the observation period. Assume we have measured a given quantity ρ on each resource:

ρ : R × T → R (r, t) → ρ(r, t)
In our context, ρ(r, t) could for example represent the computing power availability of resource r at time t. It could also represent the (instantaneous) amount of computing power allocated to a given project on resource r at time t. As shown in Figure 1, we may have to depict several types of information at once to investigate their correlation through a topology-based representation.

Assume we have a way to define a neighborhood N Γ,∆ (r, t) of (r, t), where Γ represents the size of the spatial neighborhood and ∆ represents the size of the temporal neighborhood. In practice, we could for example choose

N Γ,∆ (r, t) = [r -Γ/2, r + Γ/2] × [t -∆/2, t + ∆/2]
, assuming our resources have been ordered. Then, we can define an approximation F Γ,∆ of ρ at the scale Γ and ∆ as:

F Γ,∆ :    R × T → R (r, t) → NΓ,∆(r,t) ρ(r ′ , t ′ ).dr ′ .dt ′ (1)
This function averages the behavior of ρ over a given neighborhood of size Γ and ∆. Since both Γ and ∆ can be continuously adjusted by the analyst during a specific analysis, it is possible to choose a specific set of resources and a specific time-slice. Once a set of resources has been defined, we can see its evolution through time by shifting the corresponding frame considering other time intervals. Now that we have formally defined the data aggregation for our approach considering the space and time dimensions, we detail next how they affect the topology-based representation. For each of them, we detail how the neighborhood is dynamically defined by the analyst, and how they are mapped to the properties of the graph representation.

Temporal aggregation

Equation 1 shows that the data aggregation considers a neighborhood for the time and space scales. Taking into account only the time dimension, the temporal neighborhood is represented by a time-slice, defined by the analyst according to the analysis. Figure 2 illustrates an example where one monitored entity (HostA) has two trace metrics: computing power capacity and utilization. The time-slice is represented in the figure by the period of time between the two cursors (A 1 and A 2 ). Both values associated with the monitored entity are time-integrated, generating as result two values. These values are finally mapped to the graph representation, defining the size of the node HostA (in the right part of the figure) as the value of the time-integrated computing power within the time-slice, and the node filling as the time-integrated resource utilization value.

The analyst has the freedom to choose different time-slices during an analysis. Such feature should be configured with care, since the aggregation as detailed here attenuates the behavior of the traces for events that are smaller than the chosen time interval. Although this may lead to a bad interpretation of the topology-based representation, the benefit of freely choosing a time-frame usually leads to a better detection of anomalies and unexpected behavior [START_REF] Mello Schnorr | Detection and analysis of resource usage anomalies in large distributed systems through multiscale visualization[END_REF] by showing information that would be otherwise unavailable without time aggregation.

Spatial aggregation

For data aggregation in the space dimension, we consider that the analyst is capable to select a proper neighborhood of monitored entities. This neighborhood can be monitored entities that are closely interconnected, such as a cluster of hosts, or a pool of workstations in the same physical or virtual location. Depending on trace characteristics, neighborhood data can be inherited from them through the definition of groups, possibly hierarchically organized. The choice of neighborhood may also depend on the analysis, depending if the analyst wants to group similar entities to focus on outliers. Figure 3 shows an example that illustrates how the spatial aggregation affects the topology-based representation. As before, resources are represented by shapes whose size is according to their capacity; utilization is used as filling. For this example, the time-slice is fixed. In the left of the figure, GroupA indicates the first neighborhood taken into account during the first spatial aggregation. All data within this group is space aggregated following the Equation 1. The resulting representation is depicted in the center of the figure, surrounded by the dashed gray line: it combines a square, representing all hosts, and a diamond, representing all links (in this case there is only one link from GroupA). The properties of these two geometric shapes are calculated according to the space-aggregated values of the traces, considering all the entities within the group used to do the aggregation. The example ends with a second spatial aggregation, considering the whole GroupB, with all monitored entities. As of result, in the right of the figure, there are only one square and one diamond representing all the hosts and all the links of the initial representation. Besides increasing the quality of the analysis, spatial aggregation also plays a major Inria role in the scalability of the topological-based representation. Graph structures often raise scalability issues as we increase the number of nodes, computing a layout that does not hide correlation patterns becomes more and more difficult. The possibility to interactively aggregate a portion of the graph, while keeping its general behavior through the use of aggregated values, enables the analysis of large-scale scenarios. The next Subsection describes how we dynamically define the position of the nodes of the graph.

Dynamic graph layout

Another aspect of a graph view is the location of nodes and edges in the representation. In our context, the location of the node in the screen depends on two factors:

• First, the analyst needs to interact with the representation to inspect and understand the behavior of the monitored entities. This interaction requires, for instance, that some nodes be grouped using aggregated data, making a set of nodes be replaced by an aggregated node, changing their positions.

• Second, the traces we are considering register dynamic distributed systems where monitored elements might be present during a period but not on others. The presence of the different types of events might also change during the observation period, influencing the mapping of those to the graph and finally their location.

An existing and widely used solution for graph positioning is a static layout, a technique already present in several graph drawing tools as discussed in Section 2. A static layout might have several types of graph layout algorithms that are selected according to the nature of the graph. It considers a fixed set of nodes and edges, defining their position in a non-interactive step. If a node has to be added or removed, the whole algorithm must be executed again to take it into account.

Static layout techniques are unfitted within our approach mostly because they are non-interactive and do not enable to cope with analyst intervention and needs. Tools such as Graphviz [START_REF] Ellson | Graphviz-open source graph drawing tools[END_REF], which has a library to provide positioning for nodes and edges, have different layout algorithms that are usually not scalable when a larger graph is provided. These reasons, together with the requirements for our approach, indicate that a dynamic and interactive graph layout is a better solution.

We have opted to use a force-directed algorithm for graph drawing to provide a dynamic and interactive layout. This class of algorithms works by assigning physical forces to nodes and edges, where the most common way of doing this is to assign a spring force to nodes that are connected, and an electrical charge to nodes. When a new node has to be added to the graph, the algorithm keeps iterating and adapting the positions of everybody taking into account the new node. The basic force-directed algorithm has severe performance problems on scale -O(n 2 ) -with n being the number of nodes in the graph. In our approach, we adopt the scalable Barnes-hut algorithm [START_REF] Barnes | A hierarchical 0 (n log n) force-calculation algorithm[END_REF] -O(n log n) -combined with the hierarchical information from the traces.

Implementing Interactivity

Interactivity plays a major role in our approach because it is the way the analyst has to inspect and change the representation according to the analysis. This section presents implementation decisions regarding interactivity: how multiple data scales are handled, and how the force-directed algorithm is configured. The implementation is conducted as part of an existing open-source visualization tool called VIVA1 , extending its features.

Dealing with multiple scales

The analysis of traces from distributed and parallel systems, as well from applications, is generally composed of several types of information. Each type may potentially have metrics with their own scale. Computing power is likely to be measured in Megaflops, network data traffic might be measured in Megabit/second, and so on. Such differences of scale leads to a topology-based visualization with geometric shapes whose sizes might be different, and thereby not comparable. Our implementation defines an independent scaling for each kind of metric present in the traces to define the pixel size of the geometric shapes in the topological representation. This multiple-scaling feature, one for each type of trace data, enables the analysis of monitored entities of different nature. The implementation automatically defines the initial scaling so that the maximum size of all objects are the same.

Figure 4 illustrate how the automatic scaling of our implementation works. The values depicted in the figure within the geometric shapes are in Petaflops, for hosts (squares), and in Megabits/second, for links (diamond). For the schemes A and B, the host and link size scales are kept in the middle of their bottom sliders, meaning that the automatic scaling calculated by our implementation is used by default. Considering the data aggregation defined by the time-slice (on top) of scheme A, HostA has a value of 100 Petaflops, HostB is four-times smaller, with 25 Petaflops, and the LinkA has a capacity of 10000 Megabits/second. In scheme B, the change of the time-slice generates different aggregated values for the hosts. This time HostB has a bigger computing power than HostA. The size of HostB in the representation is the maximum size allowed for objects, meaning that the 40 Petaflops is mapped to a screen size that equals the 100 Petaflops size of scheme A. This is expected since we always map the bigger size of a type of object within a time-slice to the maximum pixel size of objects in the representation. Finally, in scheme C, we show a change in the interactive sliders that configure the independent per-object type scaling. We kept the same time-slice than the one of scheme B, but we configure hosts to be bigger, links to be smaller. The analyst can interactively configured these sliders to focus the analysis on one type of objects, for example, or adjust the scaling according to other requirements.

Force-directed parameters

As previously discussed in Section 3.3, nodes position are defined by the Barnes-Hut force-directed algorithm. This algorithm has three parameters that affect how fast it converges to a good result:

Charge is a screen size related force value for each nodes. If a node is an aggregated object, its charge is equal to the sum of all nodes it is grouping. These values are used in the Coulomb's repulsion physical law: higher their value, more disperse the nodes are in the view.

Spring is an attraction force present only between two connected nodes. The value is used by the force-based algorithm in the Hooke's attraction physical law. There is no difference in the value of this parameter when a node is connected to an aggregated node.

Damping is a value applied after the charge and spring forces are calculated: diminishing the force to calculate the new position of a node. It can be used by the analyst to either make the algorithm converge faster, or to stop it by affecting nodes position.

These parameters are interactively configured through sliders. Figure 5 depicts how charge and spring parameters affect the position of the nodes. They are changed by decreasing the value of charge, making nodes get closer, or decreasing the size of the spring, making only connected nodes get closer. The analyst is able to move nodes using the mouse during the algorithm execution. This is a very important feature since it may for example be important to the analyst to organize nodes according to the their respective locations in the physical world (e.g., machines being on the north of the country would be put on the top of the screen while those being on the south of the country would be put on the bottom of the screen) or to any other convention that makes sense for the situation under investigation. Furthermore, thanks to the dynamic layout algorithm, whenever a node is moved by the analyst, all his neighbors seamlessly follow this node and hence the graph always remains well organized.

Case studies and results

In this section, we present two scenarios that illustrate the potential of our visualization technique. The traces used in these case studies were obtained using SMPI [START_REF] Clauss | Single Node On-Line Simulation of MPI Applications with SMPI[END_REF] in Section 5.1 and the SimGrid simulation toolkit [START_REF] Casanova | Simgrid: a generic framework for large-scale distributed experiments[END_REF] in Section 5.2.

NAS-DT Benchmark Analysis

We use the NAS-DT class A benchmark with the White Hole (WH) algorithm to illustrate how the topology-based view can be used to detect performance issues in the network. The top-screenshot shown in Figure 6 shows the topology of the resource allocation used for the experiment: two homogeneous and interconnected clusters (Adonis, on the left, and Griffon, on the right) each with eleven hosts. Processes are allocated sequentially, starting on the hosts of Adonis cluster.

The top-screenshot of Figure 6 shows the bandwidth used by the DT-A considering the whole execution time. We can see that the links interconnecting the two clusters are almost saturated, suggesting that this might be limiting the benchmark execution. Further investigation with a smaller time slice (the three smaller screenshots on the bottom) in the beginning, middle and the end of the execution confirms that the interconnecting links are saturated most of the time. If we consider more carefully the White Hole algorithm communication pattern and the network topology of resources for this experiment (Figure 6), we can conclude that the sequential process allocation is not the best deployment. In fact, if we better explore the locality of the communications, we can obtain an overall performance improvement. The communication locality is easy to define for the NAS black hole algorithm by placing the forwarders processes close to the data sources, reducing the communication path and avoiding the interconnection between the two clusters.

To confirm the locality assumption through the topology-based visualization, we execute again the application using the new deployment. The top-screenshot of Figure 7 already shows a reduced utilization of the links interconnecting the two clusters, which is expected since we are exploring the communication locality within the clusters. The small network utilization in the cluster interconnection is caused by the beginning of the white hole algorithm execution (as shown by the leftmost screenshot in the bottom of the same figure), when the data for the first levels of white hole hierarchy are being transmitted. The center and rightmost topologies on the bottom shows the resource utilization for the middle and end of the execution. We can see that the network contention is now placed on the small network links on each of the clusters.

Using the topology-based view, we have reduced the execution time of the NAS-DT class A with the white hole algorithm by 20% with the new deployment. In this small and known scenario, such an improvement was expected because of the locality characteristic of the white hole algorithm and the topology used. Yet, such phenomenon is non-trivial and yet perfectly reflected by such topology-based visualization whereas it would remain invisible in a Gantt-chart visualization.

Non-Cooperative Master Worker Applications

We propose to study the behavior of two master-worker applications competing for resources on a grid. The platform is a realistic model of Grid5000 [START_REF] Bolze | Grid'5000: a large scale and highly reconfigurable experimental grid testbed[END_REF] (with 2170 computing hosts) and the two application servers use the bandwidth-centric optimal strategy described in [START_REF] Beaumont | Bandwidth-Centric Allocation of Independent Tasks on Heterogeneous Platforms[END_REF]. More precisely, every time a master communicates a task to a worker, it evaluates the worker's effective bandwidth and uses this value to prioritize workers' requests: when several workers request some work, the one with the largest bandwidth is served in priority. Every worker has a prefetch buffer of three tasks that it tries to maintain full to minimize his idleness. In the situation we investigate, the first application is CPU bound while the second has a slightly higher communication to computation ratio. Hence, we expect to observe the following phenomenon: (1) The first application should achieve an overall better resource usage than the second one.

(2) We can expect a form of locality from the second application since it will send taks in priority to workers that have a good bandwidth. (3) Although the two applications do not originate from the same sites, they may interfere on computing resources.

Figure 8 illustrates four different levels of spatial aggregation of the Grid5000 platform: no aggregation at all with 2170 computing hosts, aggregation of all hosts belonging to the same cluster, to the same site, and to the whole grid. These views represent the behavior of the whole platform for a given time slice of the previous scenario. Although none of the three expected phenomena (resource usage in favor of the CPUbound application, locality of the network-bound application, interference between the two applications) is visible in the host level representation, they are very visible at the cluster and site level. The site level enables to perfectly quantify how much the CPU-bound performed compared to the network-bound application. This illustrates how essential the multi-scale aggregation technique is to the analysis. The connections we have drawn between the different views to show the aggregation illustrate the fact that layout evolution is smooth when aggregating, which prevents the analyst to get confused when changing scale2 . Figure 9 illustrates another feature of the tool, which is the ability to animate through time a given view to follow the temporal evolution of workload distribution. Interestingly, even if the first application is computation bound, one can notice that its resource usage is not uniform through the whole platform. Some sites and cluster are assigned work before others. For example site B is filled quickly in [t 0 , t 2 ] whereas site C has to wait until time t 2 before starting to receive work units. This can easily be explained by the bandwidth-centric strategy of the servers. Another strategy that would not take such characteristics into account such a simple FIFO mechanism would not exhibit such locality and would exhibit an (inefficient) uniform resource usage all over the time.

Conclusion

With the advent of very large scale distributed systems through complex interconnection network, phenomenon such as locality and resource congestion have become more and more critical to study and understand the performance of parallel applications. Yet, no visualization tool enables either to handle in a scalable way such workload or to provide deep hindsight into such issues. We think such kind of tool should also need to allow for an interactive and exploratory analysis, knowing how to adapt to the variety of situations that can be investigated. In this article, we explain how we have built a graph-based visualization meeting the previous requirements. We have implemented the technique in an open-source visualization tool called VIVA3 and which enables to study the correlation between quantities at a spatial and temporal level. The multiscale capability of this visualization allows the analyst to select the adequate level of details and should be put in relation to what has been done for treemaps [START_REF] Mello Schnorr | A hierarchical aggregation model to achieve visualization scalability in the analysis of parallel applications[END_REF]. Our new visualization has the same aggregation features but also allows to display topological information. Such multiscale capability is also essential to achieve a scalable visualization both in term of fluidity and meaning. Yet, it is not sufficient in itself. The ability to dynamically aggregate and disaggregate groups of resources requires to adjust the layout of the graph, which we have done using a dynamic force-directed graph layout mechanism. Such algorithm allows the analyst to easily reorganize as well readjust the layout in a very efficient way.

Although we have illustrated on non-trivial examples the effectiveness of our proposal, a couple of issues still need to be addressed.

• Although the technique we use for aggregating CPU resources is very effective and meaningful since hosts are independent resources, using the same technique for aggregating links is more questionable. Indeed, communication flows typically span several network links and summing non independent resource usage leads to hardly explainable values. Therefore, although locality can be investigated, network saturation and bottlenecks are currently difficult to emphasize in aggregated views.

• Aggregating a large amount of values into a single object leads to an important loss of information, which may be harmful. It would thus be interesting to provide additional information (e.g., statistical indicators like the variance our the median) that would allow the analysis to know that particular care should be taken to specific areas that deserve further investigation.

• Currently only a few graphical objects are available in VIVA. Increasing graphical object flexibility (e.g.,, pie-charts, histograms, . . . ) would allow to display other kind of information like process states, hardware counters or resource energy consumption. The philosophy of tools like ggplot2 [START_REF] Wickham | ggplot2: elegant graphics for data analysis[END_REF] that rely on a grammar of graphics to allow the expression of complex views is extremely interesting and is being considered in our future directions.

Figure 1 :

 1 Figure 1: From Trace metrics (left) to the graph representation (right: with squares as hosts; diamond as link).

Figure 2 :

 2 Figure 2: Time-aggregated metrics of HostA mapped to its representation in the graph.

Figure 3 :

 3 Figure 3: Two spatial-aggregation operations and how they affect the topology-based representation.

Figure 4 :

 4 Figure 4: Three scenarios showing the definition of per-type scales and the operation of scaling interactive sliders.

Figure 5 :

 5 Figure 5: Three situations on how charge and spring parameters affect the layout of the nodes.

Figure 6 :

 6 Figure 6: Four topology-based views showing the network resource utilization in different time slices of the NAS-DT class A White Hole benchmark executed with an ordinary host file.

Inria

Figure 7 :

 7 Figure 7: Four topology-based views showing the network resource utilization in different time slices of the NAS-DT class A White Hole benchmark executed with a host file designed to explore communication locality.

Figure 8 :

 8 Figure 8: Four different levels of spatial aggregation of the Grid5000 platform correlating host power, resource usage of both master worker applications and the underlying network topology (for a fixed time interval).

Figure 9 :

 9 Figure 9: Evolution across time of platform usage at different scales. Although the sequence of screenshots hinders the perception of evolution compared to a real animation where the graphs are laid out of each others, the workload diffusion across time is visible.

RR n°8085

The Scalable Topology-based VisualizationOur visualization approach proposes an interactive analysis of large-scale distributed systems considering topological information. It tackles complexity in many aspects: the diversity of trace data and how to visually represent them; the multi-scale data aggregation techniques to address scalability issues; and the dynamic updates on the representation caused by changes of trace data in time and space, along with the interaction from the analyst. Next subsections detail each of these points.

https://github.com/schnorr/viva/ Inria

A video footage demonstrating the ease of interaction and the fluidity of such visualization is available at http://triva.gforge.inria.fr/demonstration.html.Inria

https://github.com/schnorr/viva/ RR n°8085

Schnorr & Legrand & Vincent tionale de la Recherche (ANR).

Acknowledgments

This work is partially funded by the project entitled SONGS (Simulation of Next Generation Systems) under the contract number ANR-11-INFRA-13 of the Agence Na-


Thi-Hau Hau Nguyen

Jean-Philippe Doyon

Stéphanie Pointet

Anne-Muriel Arigon Chifolleau

Vincent Ranwez

Vincent Berry

Accounting for gene tree uncertainty improves gene tree accuracy

à la diffusion de documents scientifiques 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.

Introduction

A phylogenetic tree or phylogeny is a tree depicting evolutionary relationships among biological entities that are believed to have a common ancestor. A gene family is a group of genes descended from a common ancestor that retains similar sequences and often similar functions. A species tree depicts the evolutionary history of a group of species, whereas a gene tree depicts the evolutionary history of a gene family. Gene trees and species tree are often inconsistent due to family-specific evolutionary events such as gene duplications, gene losses, horizontal gene transfers. By comparing gene trees with a species tree, reconciliation methods try to recover those major evolutionary events. Reconciliation is indeed the process of constructing a mapping between a gene tree and a species tree to explain their differences and similitudes with evolutionary events such as speciation (S), duplication (D), loss (L), and horizontal gene transfer (T) events. Reconciliations are most often inferred on the basis of a parsimony criterion: a cost is given to each event type, the cost of a reconciliation is the sum of the costs of the individual events it uses, and a reconciliation of minimum total cost is sought for. This computational problem is often called Most Parsimonious Reconciliation, or MPR in short, and many works have been devoted to it recently [START_REF] Hallett | Simultaneous identification of duplications and lateral transfers[END_REF][START_REF] Górecki | Reconciliation problems for duplication, loss and horizontal gene transfer[END_REF][START_REF] Conow | Jane: a new tool for the cophylogeny reconstruction problem[END_REF][START_REF] Doyon | An Efficient Algorithm for Gene/Species Trees Parsimonious Reconciliation with Losses, Duplications and Transfers[END_REF][START_REF] Tofigh | Simultaneous identification of duplications and lateral gene transfers[END_REF][START_REF] David | Rapid evolutionary innovation during an archaean genetic expansion[END_REF][START_REF] Bansal | Efficient algorithms for the reconciliation problem with gene duplication, horizontal transfer, and loss[END_REF]. The first proposed models focused on reconciliations involving only duplications and losses (the DL model) [START_REF] Goodman | Fitting the gene lineage into its species lineage, a parsimony strategy illustrated by cladograms constructed from globin sequences[END_REF][START_REF] Page | Extracting species trees from complex gene trees: reconciled trees and vertebrate phylogeny[END_REF][START_REF] Ma | From gene trees to species trees[END_REF] or only horizontal transfers and losses [START_REF] Nakhleh | Reconstructing reticulate evolution in species: theory and practice[END_REF]. Probabilistic methods have also been developed for the DL model, such as that of Arvestad et al. [START_REF] Arvestad | The gene evolution model and computing its associated probabilities[END_REF] (see Doyon et al. [START_REF] Doyon | Models, algorithms and programs for phylogeny reconciliation[END_REF] for a review). Most recent works using a parsimony approach have been devoted to models incorporating duplications, losses and transfers all together (the DTL model) [START_REF] Hallett | Simultaneous identification of duplications and lateral transfers[END_REF][START_REF] Górecki | Reconciliation problems for duplication, loss and horizontal gene transfer[END_REF][START_REF] Doyon | An Efficient Algorithm for Gene/Species Trees Parsimonious Reconciliation with Losses, Duplications and Transfers[END_REF][START_REF] David | Rapid evolutionary innovation during an archaean genetic expansion[END_REF], which is necessary to handle prokaryotes. When accounting for transfer events, the history proposed by a reconciliation is consistent if, for any transfer, the donor and receiver species co-exist. Ensuring such a time consistency is difficult and leads to an NP-hard problem in the general case [START_REF] Ovadia | The co phylogeny reconstruction problem is NP-complete[END_REF][START_REF] Tofigh | Simultaneous identification of duplications and lateral gene transfers[END_REF]. However, in the case divergence dates are available for nodes of the species tree, the problem becomes amenable [START_REF] Libeskind-Hadas | On the computational complexity of the reticulate cophylogeny reconstruction problem[END_REF][START_REF] Doyon | An Efficient Algorithm for Gene/Species Trees Parsimonious Reconciliation with Losses, Duplications and Transfers[END_REF]. The difficulty to handle transfers has led to a split within proposed DTL methods, namely those that ensure time-consistency [START_REF] Libeskind-Hadas | On the computational complexity of the reticulate cophylogeny reconstruction problem[END_REF][START_REF] Doyon | An Efficient Algorithm for Gene/Species Trees Parsimonious Reconciliation with Losses, Duplications and Transfers[END_REF] and those that don't [START_REF] Hallett | Simultaneous identification of duplications and lateral transfers[END_REF][START_REF] Tofigh | Simultaneous identification of duplications and lateral gene transfers[END_REF][START_REF] Bansal | Efficient algorithms for the reconciliation problem with gene duplication, horizontal transfer, and loss[END_REF]. The fastest algorithm for the later category runs in O(mn log n) where m and n are the sizes of the gene and species trees respectively [START_REF] Bansal | Efficient algorithms for the reconciliation problem with gene duplication, horizontal transfer, and loss[END_REF], while the fastest time-consistent algorithm runs in O(mn 2 ) [START_REF] Doyon | An Efficient Algorithm for Gene/Species Trees Parsimonious Reconciliation with Losses, Duplications and Transfers[END_REF].

A major problem, when applying reconciliation methods, is that parts of the gene trees can be incorrect. This leads reconciliation methods to overestimate (S), (D), (L) and (T) events [START_REF] Durand | A hybrid micro-macroevolutionary approach to gene tree reconstruction[END_REF][START_REF] Hahn | Bias in phylogenetic tree reconciliation methods: implications for vertebrate genome evolution[END_REF]. Errors within the gene tree can be due to sequence alignment problems or phylogenetic reconstruction artifacts such as long branch attraction. Such errors are well-known in phylogenetics and several support measures, such as bootstrap values or bayesian posterior probabilities, have been proposed to detect unreliable edges in a gene tree. Up to now, very few works have solved the reconciliation problem in the presence of unsupported edges, and most of them consider only the DL model [START_REF] Berglund-Sonnhammer | Optimal gene trees from sequences and species trees using a soft interpretation of parsimony[END_REF][START_REF] Chang | Reconciling Gene Trees with Apparent Polytomies[END_REF][START_REF] Durand | A hybrid micro-macroevolutionary approach to gene tree reconstruction[END_REF][START_REF] Vernot | Reconciliation with non-binary species trees[END_REF][START_REF] Chaudhary | Algorithms for Rapid Error Correction for the Gene Duplication Problem[END_REF]. Durand et al. proposed an exponential exact algorithm to find the best rearrangement of a gene tree while preserving its strongly supported edges [START_REF] Durand | A hybrid micro-macroevolutionary approach to gene tree reconstruction[END_REF]. Some approaches collapse unsupported edges, leading to the creation of nodes with more than two children, called polytomies [START_REF] Berglund-Sonnhammer | Optimal gene trees from sequences and species trees using a soft interpretation of parsimony[END_REF][START_REF] Chang | Reconciling Gene Trees with Apparent Polytomies[END_REF][START_REF] Vernot | Reconciliation with non-binary species trees[END_REF]. They then rely on a generalization of the least common ancestor mapping (LCA) to avoid the need for examining all possible binary rearrangements of the polytomies. In this way, Chang et al. [START_REF] Chang | Reconciling Gene Trees with Apparent Polytomies[END_REF], resp. Vernot et al. [START_REF] Vernot | Reconciliation with non-binary species trees[END_REF], proposed polynomial time algorithms when considering nonbinary gene trees, resp. species trees. Berglund et al. proved that when dealing with species and gene tree that are both non-binary, the problem becomes NPcomplete [START_REF] Berglund-Sonnhammer | Optimal gene trees from sequences and species trees using a soft interpretation of parsimony[END_REF]. They thus proposed a heuristic approach tackling a variant of the MPR problem where duplications and losses are optimized separately. Durand et al. used Nearest Neighbor Interchange (NNI) edit operations to rearrange the local topology of the gene tree in the regions of low supports but, unlike Berglund et al., they optimized simultaneously duplications and losses. Chaudhary et al. investigated Subtree Prune and Regraft (SPR) and Tree Bisection and reconnection (TBR) edit operations to search for the gene tree rearrangement that minimizes the number of duplications, regardless of losses and transfers [START_REF] Chaudhary | Algorithms for Rapid Error Correction for the Gene Duplication Problem[END_REF].

Due to transfer events, the LCA mapping can not be transposed to the DTL model and it seems hard to have an exact polynomial time algorithm for the MPR problem under this model even when the polytomies are present only in the gene tree or in the species tree. Following the works of Berglund et al. and Durand et al. for the DL model, we propose a heuristic method relying on NNI edit operations to search for a gene tree rearrangement that minimizes the cost of reconciliation to a fixed binary species tree, but in the context of the more complex DTL model. The resulting dynamic program, called MowgliNNI, is a generalization of Mowgli [START_REF] Doyon | An Efficient Algorithm for Gene/Species Trees Parsimonious Reconciliation with Losses, Duplications and Transfers[END_REF] a program initially developed for fixed binary gene trees. Experiments on simulated data show that MowgliNNI provides better D, T, L, S prediction while improving gene tree inference, i.e. the modified gene tree is closer to the true evolutionary history of the gene family. Experiments on real data show a significant decrease in number of events and in the number of most parsimonious reconciliations.

Preliminaries

Trees considered in this paper are rooted and only labeled at their leaves, each leaf being labeled with the name of a studied species. Given a tree T , its nodes, edges, leaves and root are resp. denoted V (T ), E(T ), L(T ) and r(T ). The label of a leaf u of T is denoted by L(u) and the set of labels of leaves of T is denoted by L (T ). When a node u has two children, they are denoted u 1 and u 2 . Given two nodes u and v of T , u ≤ T v (resp. u < T v) if and only if v is on the unique path from u to r(T ) (resp. and u = v); if neither u < T v nor v < T u then u and v are said to be incomparable. As we consider rooted trees T only, we adopt the convention than an edge denoted (u, v) means that v < T u. For a node u of T , T u denotes the subtree of T rooted at u, u p the parent node of u, while (u p , u) is the parent edge of u. A tree T is a refinement of a tree T if T can be obtained from T by collapsing some edges in T , i.e. by merging the two extremities of these edges [START_REF] Semple | Phylogenetics[END_REF].

A species tree is a rooted binary tree depicting the evolutionary relationships of ancestral (internal nodes) species leading to a set of extant (leaf) species. A species tree S is considered here to be dated, that is associated to a time function θ : V (S) → R + such that y < S x implies that θ(y) < θ(x). Such times are usually estimated on the basis of molecular sequences [START_REF] Sanderson | Inferring absolute rates of evolution and divergence times in the absence of a molecular clock[END_REF] and fossil records. Note that to ensure the time consistency of inferred transfers, absolute dates are not required, the important information being the ordering of the nodes of S induced by the dating. Given a dated binary species tree S, the reconciliation model we rely on considers a variant of S called a subdivision and denoted S (as done also in [START_REF] Tofigh | Using Trees to Capture Reticulate Evolution, Lateral Gene Transfers and Cancer Progression[END_REF][START_REF] Conow | Jane: a new tool for the cophylogeny reconstruction problem[END_REF][START_REF] Doyon | An Efficient Algorithm for Gene/Species Trees Parsimonious Reconciliation with Losses, Duplications and Transfers[END_REF]). The subdivision S is constructed from S as follows: for each node x ∈ V (S) \ L(S) and each edge (y p , y) ∈ E(S) s.t. θ S (y p ) > θ S (x) > θ S (y), an artificial node w is inserted along the edge (y p , y) in S , with θ S (w) = θ S (x).

A gene tree is a rooted binary tree explaining the evolutionary history of a gene family, that lead to a set of homologous sequences observed in current organisms. Each leaf of a species tree has a unique label, corresponding to a specific extant sequence of the gene. Though, several leaves of a gene tree can be associated to a same species due to duplication and transfert events. We denote by s(u) the species associated to leaf u ∈ V (G). Each edge (u, v) of E(G) can be uniquely identified by the subset L(T v ) ⊆ L(G). A gene tree G with supports is a gene tree whose internal edges have a support value. Let wk t (G) ⊆ E(G) be the set of edges having a support value weaker than threshold t and let str t (G) be E(G)wk t (G), that is the edges having a support equal or stronger than t.

Finding the Most Parsimonious Reconciliation. Reconciling a (binary) gene tree G with a species tree S means building a mapping α that associates each gene u ∈ V (G) to a sequence α(u) of nodes in the subdivision S . The α(u) sequence models the evolution of gene u along S with the following atomic events: (C) contemporary gene, (S) speciation, (D) duplication, (T) transfer, (SL) speciation followed by a loss, (TL) transfer followed by a loss for the donor, and (∅) going from an artificial node of S to its only child. Observe that each loss is coupled with either a speciation (SL) or a transfer (TL). Indeed, any most parsimonious reconciliation only needs to use a loss when it meets a speciation node of S where G goes into only one descending edge, or when leaving an edge due to a transfer, with no part of G remaining in the donor edge. For more details, we refer the reader to Definition 3 of Doyon et al. [START_REF] Doyon | An Efficient Algorithm for Gene/Species Trees Parsimonious Reconciliation with Losses, Duplications and Transfers[END_REF] that we follow for reconciliation, except that the mapping α considered here concerns nodes instead of branches.

The cost of a reconciliation α is denoted cost(α) = dδ + tτ + lλ, where δ, τ , and λ respectively denote the cost of D, T, and L events, and d, t, and l denote the number of the corresponding events in α. Moreover, a TL event is atomic and costs (τ + λ) and a SL costs λ. The optimal reconciliation cost is denoted C(G, S ) = min{cost(α) : α is a reconciliation between G and S }.

The optimal cost for mapping a node u of G on a vertex x of S is defined according to the minimal cost among the events C, S, D, T, ∅, and SL, together with the cost of a TL event, which are denoted c TL (u, x) and c TL (u, x), respectively (see Definition 1 below). This directly follows from the dynamic programming algorithm that computes the optimal cost C(G, S ), where the computation of the cost for a TL event follows that of the other six atomic events, since a TL event is followed by a C, S, D, T, ∅, or SL event [START_REF] Doyon | An Efficient Algorithm for Gene/Species Trees Parsimonious Reconciliation with Losses, Duplications and Transfers[END_REF].

To ensure time consistency of T and TL events, the donor x ∈ V (S ) and the receiver y ∈ V (S ) have to be located at the same time slice h(x) = h(y) of S (the term time slice of a vertex refers to its height in S ).

These intricated notions are formally detailled in definitions 1 and 2. Though, these definitions depend on one another, there is no circularity as either we progress in the gene tree or we switch from a TL event to a non-TL event.

Definition 1 (Reconciliation cost matrix). Consider a gene tree G and the subdivision S of a species tree S. Let c : V (G) × V (S ) → R + denote the cost matrix recursively defined as follows for a node u of G and a vertex x of S : c TL (u, x) = min{c E (u, x) : E ∈ {C, S, D, T, ∅, SL}} and c(u, x) = min{c TL (u, x), c TL (u, x)}, where the costs c E (u, x) for E ∈ {C, S, D, T, ∅, SL, TL} are defined below.

-c C (u, x) = 0, if u ∈ L(G), x ∈ L(S ) and L(x) = s(u). -c S (u, x) = min{c(u 1 , x 1 ) + c(u 2 , x 2 ), c(u 1 , x 2 ) + c(u 2 , x 1 )} if u / ∈ L(G) and x / ∈ L(S ). -c D (u, x) = c(u 1 , x) + c(u 2 , x) + δ, if u / ∈ L(G). -c T (u, x) = min{c(u 1 , x) + c(u 2 , z), c(u 1 , y) + c(u 2 , x)} + τ
if u has two children and where z (resp. y) denotes BR T (u 2 , x) (resp.

BR T (u 1 , x)). -c ∅ (u, x) = c(u, x 1 ), if x has a single child. event) -c SL (u, x) = min{c(u, x 1 ), c(u, x 2 )} + λ, if x has two children. -c TL (u, x) = c TL (u, y) + τ + λ, where y denotes BR TL (u, x).
If the above constraints for an event E ∈ {C, S, D, T, ∅, SL, TL} on node u and vertex x are not respected, the corresponding cost c E (u, x) is set to ∞.

Definition 2 (Best receiver). Consider a node u of G and a vertex x of S . Let BR T (u, x) denote a vertex y of S that minimizes c(u, y) = min{c(u, z) :

z ∈ V h(x) (S ) and z = x}. Similarly, let BR TL (u, x) denote a vertex y of S that minimizes c TL (u, y) = min{c TL (u, z) : z ∈ V h(x) (S ) and z = x}
The value c(u, x) is the optimal cost when mapping gene node u to node x in S or on the edge above it. The optimal cost for reconciling G with S , denoted C(G, S ), is then min x∈V (S ) (c(r(G), x). The algorithm of Doyon et al. [START_REF] Doyon | An Efficient Algorithm for Gene/Species Trees Parsimonious Reconciliation with Losses, Duplications and Transfers[END_REF], called Mowgli, fills the dynamic programming cost matrix c : V (G) × V (S ) → R + by two embedded loops that visit all slices of S in backward order and nodes of G in postorder. Due to an optimization in precomputing the best receiver edge for transfer events of nodes u in a given time slice, this algorithm runs in O(|S| 2 .|G|) time and space.

The problem considered in this paper is the following:

Most Parsimonious Reconciliation Gene Tree (MPR-GT)

INPUT: a dated species tree S with a time function θS, a gene tree G with supports on the same set of species, costs δ, τ , resp. λ for D, T, resp. L, and a threshold t.

OUTPUT: a tree G s.t. strt(G) ⊆ E(G ) and C(G , S ) is minimum among all such trees.

Methods

We describe here a heuristic for the MPR-GT problem that relies on a hill-climbing strategy to seek a (rooted) gene tree G of minimum reconciliation cost (see Def. 1) using NNI edit operations [START_REF] Felsenstein | Inferring phylogenies[END_REF].

Performing an NNI operation around an internal edge (w, v) means swapping the position of one of the two subtrees connected to v with that of the subtree connected to the sibling of v. Given an initial gene tree G and an edge (w, v) of G, two "alternative" trees can be obtained from G by performing an NNI operation around (w, v) (see Fig. 1 for an example). The hill-climbing proceeds as follows: (1) select a weak edge of G; (2) compute the reconciliation cost for the two alternative gene trees obtained by NNI on that edge; (3) if none of these trees decreases the reconciliation cost, then try another weak edge; if none of the weak edges allows to progress, then G is a local minimum and the hill climbing stops; (4) otherwise one of the alternative gene trees leads to a decrease in reconciliation cost, and the above process continues with the alternative tree of minimum reconciliation cost. MowgliNNI outputs the final binary rearrangement along with its most parsimonious reconciliation. In the worst cases, MowgliNNI examines all unreliable edges and does not find any better binary rearrangement of the given gene tree G since the topology G is already (locally) optimal. Consider Combinatorial Optimization. We now present results that take advantage of the way the dynamic programming matrix is computed (Def. 1) to avoid recomputing from scratch the cost matrix associated to a gene tree G obtained by an NNI edit operation from a gene tree G. Consider the gene tree G of Figure 1, the NNI operation applied on edge (w, v) that swaps the two subtrees G b and Gc, and the resulting gene tree denoted G . We can observe that despite the global architecture of G and G differs, the local architectures of subtrees G b , Gc, G d , Ga 0 , . . . Ga k remain unchanged. Hence, any cost that differs between the matrices c : V (G) × V (S ) → R + and c : V (G ) × V (S ) → R + (see Definition 1) is located in a column (i.e. node of the gene tree) associated to an ancestor of v (including v itself). For each of those nodes, there is two cases: (i) the node belongs to the NNI edge and its two children have subtree that have been modified (e.g. nodes w and v); (ii) the node is a strict ancestor of the NNI edge (w, v) and has exactly one child with a subtree that has been modified (e.g. g k , . . . , g0). Lemma 1 below indicates which columns of the cost matrix don't need to be recomputed.

Lemma 1. Consider a gene tree G, the subdivision S of a species tree S, an edge (w, v) of G, and G obtained from G by an NNI operation on (w, v). For each node z of G that is incomparable to v and for each vertex x of S , c(z, x) = c (z, x) holds.

Unfortunately, there is no extension of Lemma 1 to ensure that when an edge has already been unsuccessful tried for an NNI it is useless to reconsider it later, even if it is a descendant in G of the edge leading to the last successful NNI.

Algorithm 1. M owgliN N I(G, c): seek a gene tree G of minimum reconciliation cost, starting from a gene tree G and the precomputed matrix reconciliation cost c : V (G) × V (S ) → R + , where S is the subdivided species tree.

1: for all edges (w, v) ∈ wkt(G) do 2:

For each node s of G that is not an ancestor of v, set the column c (s, •) to c(s, •).

3:

For each vertex x of S , recompute the cost c (v, x) according to Def. 1.

4:

for all strict ancestors s of v according to a bottom-up traversal of G do 5:

For each vertex x of S , recompute the cost c (s, x) according to Def. 1.

6:

If c(s, x) ≤ c (s, x) holds for each vertex x of S , then examine the next edge of loop at line 1 {the NNI rearrangement tree G is refused}. 7:

end for 8:

Return MowgliNNI(G , c ) {The rearranged tree G is accepted}. 9: end for 10: Return G {No successful rearrangement of G} Theorem 1. Consider a gene tree G, the subdivision S of a species tree S, an edge (w, v) of G, a gene tree G obtained by an NNI operation on (w, v), and any strict ancestor u of w in G where the unique child of u that is an ancestor of w is u1 w.l.o.g. (i.e. w ≤ u1 in both G and G'). If c(u1, x) ≤ c (u1, x) holds for all x ∈ V (S ), then (1) c(u, x) ≤ c (u, x) holds for all x ∈ V (S ); and ( 2

) C(G, S ) ≤ C(G , S ). Computing the cost matrix c : V (G ) → V (S ) given c : V (G) → V (S ) is then achieved in worst-case time O(|S | • h(G)), where h(G) is the height of G. Theorem 2. MowgliNNI has worst case running time O(|S| 2 • |G| + |S| 2 • h(G) • N ).
Indeed the steps of Algorithm 1 can be described as follows: initializing the reconciliation matrix for the initial gene tree is done in O(|S| 2 • |G|) time; updating the matrix for each NNI now only costs

O(|S | • h(G)) = O(|S| 2 • h(G)).
In MowgliNNI 's naïve implementation each rearrangement requires to recompute the cost associated to each and every node of the gene tree. In contrast, in the optimized version, an NNI around edge (w, v) is examined after updating only those costs associated to ancestral nodes of w. This has no impact on the worst case complexity (when the gene tree is a caterpillar h(G) is in O(|G|)) but significantly reduces the running times in practice since in most cases the number of nodes in G is much larger than their average height. For some random tree models the average height of a node in an n-leaf tree is indeed proportional to log(n) [START_REF] Knuth | The Art of Computer Programmingm, Sorting and Searching[END_REF][START_REF] Robinson | Comparison of phylogenetic trees[END_REF].

Experimental Evaluation

Experiments on Simulated Datasets

The phylogeny of 37 proteobacteria proposed by David and Alm [START_REF] David | Rapid evolutionary innovation during an archaean genetic expansion[END_REF] was used as a reference species tree. Along this tree, we simulated the evolutionary histories (denoted RTrue) of 985 gene families (GTrue), containing 10 to 100 genes, according to the birth and death process [START_REF] Kendall | On the generalized birth-and-death process[END_REF]. The initial gene trees (GML) were inferred from the simulated molecular sequences of length 1500 -3000 bp by RAxML under GTR model [START_REF] Stamatakis | Raxml-vi-hpc: maximum likelihood-based phylogenetic analyses with thousands of taxa and mixed models[END_REF]. Mowgli [START_REF] Doyon | An Efficient Algorithm for Gene/Species Trees Parsimonious Reconciliation with Losses, Duplications and Transfers[END_REF] and Ranger-dtl-D [START_REF] Bansal | Efficient algorithms for the reconciliation problem with gene duplication, horizontal transfer, and loss[END_REF] were used to infer the most parsimonious evolutionary history (RML) between the initial gene tree and the reference species tree. Then, MowgliNNI was used to search for an alternative gene tree topology (GNNI ) of lower reconciliation cost, along with its most parsimonious evolutionary history (RNNI ). The cost of each D, T, L event considered in reconciliations was computed as follows:

Cost E =    log( |D R T rue |+|T R T rue |+|L R T rue | |E R T rue | ) if |ER T rue | = 0 log( |D R T rue |+|T R T rue |+|L R T rue | 0.1 ) otherwise (1)
where ER T rue (with E beeing D, T or L) stands for the true events of this type.

We explored the ability of MowgliNNI to improve the set of GML trees using six different bootstrap values as threshold for defining weak edges, i.e. 20, 40, 60, 80, 90, and 95. The GML trees were inferred from relatively long sequences, they thus contained a large proportion of high bootstrap values, e.g. more than 65% edges had a bootstrap value ≥ 80. Though this left only a moderate number of edges in each gene tree to be considered by MowgliNNI for rearrangement, the method was still able to improve their quality (see below).

Mowgli and Ranger-dtl-D showed a similar accuracy in inferring duplications and transfers (Fig. 2(a)), though Ranger-dtl-D proposed reconciliations with higher costs in 13% of the cases. As moreover the Ranger-dtl-D software does not provide the mapping of loss events, below we mainly compare the events inferred by MowgliNNI with those inferred by Mowgli and those of RTrue.

Table 1 reports the accuracy of the GML and GNNI trees. The number of families considered for improvement logically increases as the threshold for identifying an edge as weak increases (row 2 of Table 1). Even though bootstrap values in the initial gene trees are high on average, a large number of the 985 processed families are still subject to possible improvements, as for threshold 20, already 43% of the families are concerned, and this goes up to 99% of the families at threshold 95. The first conclusion is that Table 1. Quality of the gene trees and reconciliations inferred by MowgliNNI . For each tested threshold value, the second row indicates the number of gene families containing some weak edges (among the 985 simulated gene families). Third row indicates the percentage of these families where MowgliNNI proposes a modified tree of lower reconciliation cost. The last six rows provide the percentage of the former families where MowgliNNI provides modified gene trees (resp. reconciliations) that are closer, equally far or farther from the true gene trees (resp. the true evolutions). RF (GTrue, GX ) denotes the Robinson Fould distance between GTrue and GX , ED(RTrue, RX ) = |RTrue -RX | + |RX -RTrue|, where X stands for NNI or ML. there is a large number of cases where MowgliNNI can propose a modified gene tree. The percentage of cases where it actually did is provided in row 3 of Table 1, showing e.g. that at threshold 80, MowgliNNI proposed a new gene tree in 88% of the cases (853 cases over 965). Even for the lowest considered threshold of 20, a new gene tree is obtained for 79% of the families having weak edges, representing more than a third of the initial 985 families. These modified gene trees (GNNI ) represent an improvement over the initial trees (GML) since they are in most cases closer to the true gene trees (rows 4, 5, 6) and allow to obtain better reconciliations (rows 7, 8, 9). For instance at threshold 80, GNNI is better in 71% of the cases, and worse in only 8%. Similarly, the reconciliation is better in 79% of the cases, and worse in only 6%. The higher the threshold value, the more edges are considered for NNI moves by MowgliNNI . Up to a certain point, broadening the search space of MowgliNNI allows to improve both the gene trees and the reconciliations. Yet, for threshold greater than 80, MowgliNNI 's performance starts to decrease due to the fact that the sequence signal is no longer sufficiently taken into account.

MowgliNNI progressively reduced the number of predicted duplications, transfers and losses as the threshold increased. At threshold 0 (where MowgliNNI = Mowgli ), 5403 duplications, 2460 transfers and 12007 losses were predicted on the whole dataset; going to threshold 80, these numbers drop to 4510 duplications, 1160 transfers and 8016 losses, i.e. values that are much closer to the 4443 duplications and 8142 losses contained in the true reconciliations.

The average number of false positive events (FP) of the RNNI reconciliations decreases as the threshold increases (Fig. 2(b)). However, as in Doyon et al. [START_REF] Doyon | An Efficient Algorithm for Gene/Species Trees Parsimonious Reconciliation with Losses, Duplications and Transfers[END_REF], the average number of FP transfers is quite high compared to that of duplications and losses. This can be explained by several reasons. First, a transfer is judged incorrect as soon as i) it does not depart or end in the same edges of the species tree as the corresponding true transfer, or ii) it does not concern the same edge in the gene tree. Overall, there is an additional constraint w.r.t. duplications and loss events, leading on average to more incorrect events. This point is all the more sensitive that several most parsimonious reconciliations (MPR) are obtained in a number of cases, while we just accounted for one of them for each gene family. Hence, event error rates we report are pessimistic (note that this does not affect RF distance results). Last, incorrect gene trees lead to incorrect event inferences, but the latter are very sensitive to only small errors in gene trees. The event FP error grows exponentially when the RF distance between the initial and the true tree increases from 0 to 10% (data not shown).

Inferring GML trees from shorter sequences (400 bp), led to a decrease in their quality both in terms of RF distance to GTrue and in event distance between inferred and true reconciliation. Starting from a less accurate gene tree, the accuracy of the NNI trees and of their evolutionary histories is also lowered, though the relative improvement provided by MowgliNNI over Mowgli is higher than with long sequences (data not shown).

In order to measure the dependance of MowgliNNI on the precise costs used for each kind of event, we ran the method on GML trees with costs varying up to 10%, 20%, then 50% w.r.t. those computed from Formula (1). The paired t-test for RF distances shows that the GNNI trees obtained with the new costs are not significantly different from those obtained with the former costs (p-value=0.296, 0.2723, 0.2028 respectively). The accuracy of inferred events also does not change much. Transfers have the highest variation with 3.6% (resp. 3%) increase in FP (resp. FN) when the event costs vary up to 50%. Thus, MowgliNNI is quite robust to changes in the event costs.

In summary, MowgliNNI successfully uses the reconciliation cost as additional information to resolve the uncertain parts of gene trees inferred from sequences only. Though the gene tree resolutions are partly guided by reconciliations with the species tree, they are not attracted away from the true gene trees, but are closer to them than the initial gene trees. As a result, MowgliNNI infers gene events more accurately, which is of prior importance to distinguish orthologs from paralogs and xenologs [START_REF] Doyon | Models, algorithms and programs for phylogeny reconciliation[END_REF].

Experiments on Real Data

We constructed a dataset of ≈ 30000 homologous gene families (3 to 312 taxa) on Bacteria from the HOGENOM database (release 04) [START_REF] Penel | Databases of homologous gene families for comparative genomics[END_REF] and ran Mowgli and MowgliNNI on this dataset with fixed parameters (τ = 3, δ = 3.5, λ = 1).

MowgliNNI allows to change the gene tree, hence to lower the reconciliation cost, in 24% of the ≈ 30000 families. This gain is non-negligible and is uttermost important as changing the gene tree topology has an important impact on the inferred events (as shown on the simulated data sets and below) that are used in turn to predict the function of genes on the basis of ortholog and paralog relationships. When allowing rearrangements on weak edges under the DL model, Berglund-Sonnhammer et al. reported that 10% of their families were improved [START_REF] Berglund-Sonnhammer | Optimal gene trees from sequences and species trees using a soft interpretation of parsimony[END_REF], while Chaudhary el al. improved all their gene trees in a pure D model when rearranging gene trees with Subtree Prune and Regraft (SPR) operations [START_REF] Chaudhary | Algorithms for Rapid Error Correction for the Gene Duplication Problem[END_REF]. However, it is hard to know whether the datasets are comparable.

For all gene families, we counted the number of events of each kind (D, T, L) inferred by Mowgli and MowgliNNI . As a rule, MowgliNNI led to a decrease in the number of events in inferred evolutionary histories, the reduction being considerable for transfers and losses (88.3% and 59.9% resp.) but quite small for duplications (5.2%). These results obtained in the DTL model are consistent with those of Durand et al. reporting that in the DL model gene tree rearrangements substantially reduce the number of events needed to explain the data [START_REF] Durand | A hybrid micro-macroevolutionary approach to gene tree reconstruction[END_REF]. The differences in reductions we observed depending on the kind of events can be explained by the fact that given the costs we used for the events (τ = 3, δ = 3.5, λ = 1), it is usually more parsimonious to explain the conflicts between gene and species tree by a combination of T and L rather than a combination of D, and L. Thus, when MowgliNNI infers a gene tree closer to the species tree, it mostly removes the need for artificial transfers (and losses to a lesser extent), while not altering that much the number of duplications.

In addition to reductions in errors and number of events, the new gene tree proposed by MowgliNNI usually reduced the number of alternative MPRs, i.e. histories. On a random sample of two dozens new gene trees, the number of MPRs is reduced in 63% of the cases (by a factor of 18 in the best case), and increased in 21% (by a factor 3 at worst). This echoes similar findings of Durand et al. in a DL model [START_REF] Durand | A hybrid micro-macroevolutionary approach to gene tree reconstruction[END_REF].

We measured the running time of Mowgli and of both the non-optimized and optimized versions of MowgliNNI (see Methods) on a random sample of 100 families having from 10 to 80 taxa. The results show that the optimized version of MowgliNNI is 20 (resp. 50 and 80) times faster than the non-optimized one, when facing 1-20 (resp. 20-40 and 40-60) weak edges. The increase in accuracy due to MowgliNNI is obtained at the price of a small computation time overcost.

B

  . Raphael and J. Tang (Eds.): WABI 2012, LNBI 7534, pp. 123-134, 2012. c Springer-Verlag Berlin Heidelberg 2012

  now the time complexity of MowgliNNI . Identifying the weak edges is done in O(|G|) and generating the two alternative gene trees for an NNI operation is done in constant time. Hence, the complexity bottleneck of MowgliNNI is the number of times (denoted N ) the Θ(|S| 2 • |G|) Mowgli algorithm is called. Overall, the time complexity of MowgliNNI is Θ(|S| 2 • |G| • N ). The next section describes how we can avoid recomputing large parts of the cost matrix, and hence greatly reduce the running time of MowgliNNI .

Fig. 1 .

 1 Fig. 1. A gene tree G with a weak edge (w, v) selected for an NNI. v is connected to two subtrees Gc and G d , while w is connected to v and to the subtree G b . Performing an NNI operation around (w, v) means exchanging subtree G b with either Gc or G d , leading to trees G and G" respectively.

Threshold 20 40 60 80 90 95 5 6 8 9 10 %

 9510 Number of gene families containing weak edges 422 708 911 965 979 981 % of cases where Cost(S, GNNI ) < Cost(S, GML) 79 81 85 88 88 89 % of cases where RF (GTrue, GNNI ) < RF (GTrue, GML) 38 55 66 71 70 69 % of cases where RF (GTrue, GNNI ) = RF (GTrue, GML) 59 40 28 21 21 21 % of cases where RF (GTrue, GNNI ) > RF (GTrue, GML) 3 of cases where ED(RTrue, RNNI ) < ED(RTrue, RML) 59 70 75 79 79 78 % of cases where ED(RTrue, RNNI ) = ED(RTrue, RML) 27 23 19 15 16 15 % of cases where ED(RTrue, RNNI ) > ED(RTrue, RML)

Fig. 2 .

 2 Fig. 2. (a) The accuracy of Mowgli , Ranger-dtl-D and MowgliNNI (threshold=80) in inferring duplications and transfers, where T PDT (resp. F PDT , F NDT ) denotes the true positive (resp. false positive, false negative) of duplications and transfers predicted. (b) Average false positive (FP) of the NNI trees -note that FP values at threshold 0 correspond to Mowgli results.

Acknowledgement. We thank Gergely J. Szöllősi for his help in determining the event costs of the real dataset and the referees that helped strengthen the experimental validation. This work was funded by the Languedoc-Roussillon Chercheur d'Avenir program and by the french Agence Nationale de la Recherche, programmes Domaines Emergents (ANR-08-EMER-011 Phylariane ), 6ème Extinction (ANR-09-PEXT-000 PhyloSpace) and Investissements d'avenir / Bioinformatique (ANR-10-BINF-01-02, Ancestrome).