Raluca Uricaru
email: uricaru@lirmm.fr

Célia Michotey
email: celia.michotey@jouy.inra.fr

Laurent Noé

Hélene Chiapello
email: helene.chiapello@jouy.inra.fr

Eric Rivals
email: rivals@lirmm.fr

Improved sensitivity and reliability of anchor based genome alignment

Keywords: Global genome alignment, anchor based strategy, spaced seeds

Whole genome alignment is a challenging problem in computational comparative genomics. It is essential for the functional annotation of genomes, the understanding of their evolution, and for phylogenomics. Many global alignment programs are heuristic variations on the anchor based strategy, which relies on the initial detection of similarities and their selection in an ordered chain. Considering that alignment tools fail to align some pairs of bacterial strains, we investigate whether this is intrinsically due to the strategy or to a lack of sensitivity of the similarity detection method. For this, we implement and compare 6 programs based on three different detection methods (from exact matches to local alignments) on a large benchmark set. Our results suggest that the sensitivity of well known methods, like MGA or Mauve, can be greatly improved in the case of divergent genomes if one exploits spaced seeds at the detection phase. In other cases, such methods yield alignments that cover nearly the whole genome. Then, we focus on global reliability of alignments: should an aligned pair of segments be included in the global genome alignment? We investigate this reliability according to both the segment "alignability" and to inclusion of orthologs. Again, we provide evidence that for both close and divergent genomes, one of our programs, YH, achieves alignments with sometimes a lower coverage, but a higher inclusion of orthologs. It opens the way to the first reliable alignments for some highly divergent species like Buchnera aphidicola or Prochlorococcus marinus.

Introduction

Whole genome comparisons offer a unique opportunity to investigate globally the mechanisms of evolution in closely related species, are a key to the inference of functional elements in both coding and non coding regions, and serve as a basis in phylogenomics [START_REF] Bigot | KOPS: DNA motifs that control E. coli chromosome segregation by orienting the FtsK translocase[END_REF][START_REF] Delsuc | Phylogenomics and the reconstruction of the tree of life[END_REF]. In particular, the conserved parts of genomes, forming the so called backbone segments, indicate the biological components common to several species or strains, while differences in sequences, variable segments, are likely responsible for what distinguishes them (e.g., pathogenic islands). Genome alignment can deliver both at once. Due to the genome sizes and to the task complexity, genome alignment tools implement heuristic algorithms. The most used scheme is the anchor based strategy (e.g., [START_REF] Hohl | Efficient multiple genome alignment[END_REF][START_REF] Darling | Mauve: Multiple Alignment of Conserved Genomic Sequence With Rearrangements[END_REF][START_REF] Brudno | Glocal alignment: finding rearrangements during alignment[END_REF]), which operates in four phases. It starts by detecting an initial set of pairwise similarity regions (phase 1) and, through a chaining phase, selects a non-overlapping maximum-weighted subset of those similarities (phase 2), called anchors. Phases 1 and 2 are recursively applied to each pair of yet unaligned regions (phase 3). The last phase consists in systematically applying classical heuristic alignment tools (e.g., ClustalW) to all short region pairs still left unaligned.

The Mosaic database stores the alignments of backbone segments for every pair of strains of the same bacterial species. The backbones are obtained by first aligning the genomes with either MGA or Mauve (two anchor based tools), then by post-processing the alignment to remove segment pairs whose percentage of identity falls below 76%. This post-processing, although based on an arbitrary threshold, is still applied to avoid unreliable alignments. Moreover, some pairs of strains are absent from the database because the backbones covered less than 50% of the genome. It is unanswered whether cases of small coverage are due to a lack of sensitivity of the methods or to an intrinsic limitation of the strategy.

Here, we investigate this issue by implementing and comparing six methods that combine three similarity detection methods and two chaining algorithms, and by comparing the results on a large benchmark made of all pairwise intra-species bacterial genomes. As they simulate the first 2 phases of the strategy, those methods can also be compared to MGA and Mauve results. It turns out that one of the programs that exploits spaced seeds to search for similarity regions, YH, allows to align divergent collinear genomes, for which MGA and Mauve failed to produce reliable alignments. Moreover, when comparing the proportion of orthologous genes included in the alignments, YH seems to overcome some reliability problems encountered by other methods, including on well-known cases like E. coli.

In the sequel, Section 2 presents our programs, the benchmark data, and establishes a protocol for the evaluation of global alignment. In Section 3, we evaluate the performance of those methods from both computational and biological view-points, while we discuss the results in Section 4.

Methods

Genome Alignment Programs MGA and Mauve are two archetypal anchor based alignment tools, are widely used, documented and proved to be more accurate than MUMer and SLagan [START_REF] Brudno | Glocal alignment: finding rearrangements during alignment[END_REF][START_REF] Kurtz | Versatile and open software for comparing large genomes[END_REF]. They differ by two aspects: in phase 1, MGA searches for similarity regions that are maximal exact matches (MEMs) with the program Vmatch [START_REF] Hohl | Efficient multiple genome alignment[END_REF], while Mauve finds approximate matches using a special type of spaced seeds [START_REF] Darling | Mauve: Multiple Alignment of Conserved Genomic Sequence With Rearrangements[END_REF]. In phase 2, MGA executes Chainer [START_REF] Abouelhoda | Chaining algorithms for multiple genome comparison[END_REF], a program that selects the highest scoring non-overlapping set of collinear matches (consistent chain [START_REF] Brudno | Glocal alignment: finding rearrangements during alignment[END_REF]); Mauve uses a greedy breakpoint elimination algorithm [START_REF] Blanchette | Breakpoint phylogenies[END_REF] that generates an approximate solution to the maximum-weighted non collinear anchoring problem. Hence, MGA treats collinear genome pairs, while Mauve handles rearrangements.

Our 6 programs combine one of 3 similarity detection methods (Vmatch, Blast v2, Yass) and one of 2 chaining algorithms (Chainer and Hierarchical chainer). Contrarily to Vmatch, Blast v2 and Yass find similarities that are local alignments with either contiguous or spaced seeds [START_REF] Noe | YASS: enhancing the sensitivity of DNA similarity search[END_REF]. We named our 2 × 3 combinations by the initials of the methods they combine: VC, BC and YC with Chainer, VH, BH and YH with Hierarchical Chainer. By comparing those, we can measure the impact of each element on the final alignment.

The Hierarchical chainer implements a greedy chaining that allows for limited overlaps, in place inversions, and privileges region pairs with stronger similarities [START_REF] Roytberg | A hierarchical approach to aligning collinear regions of genomes[END_REF]. Similarities are ordered by decreasing numbers of identities (nid) and processed in groups according to several intervals of nid, starting with the largest ones. In each group, we consider first similarities located on the dotplot main diagonal (i.e., shift of 0) and continue with increasing shifts. collinear similarities are being chained from the left end on the reference sequence, in a greedy manner.

Genome Sequences and Comparisons

We considered all (236) pairs of bacterial strains of the same species whose complete genomes are available in GenomeReviews database as of mid-2008 [START_REF] Sterk | Genome Reviews: Standardizing Content and Representation of Information about Complete Genomes[END_REF]. The Mauve and MGA alignments, and the backbone segments positions for each pair were obtained from the Mosaic database [START_REF] Chiapello | Systematic determination of the mosaic structure of bacterial genomes: species backbone versus strain-specific loops[END_REF], except for 37 pairs corresponding to five divergent species (Buchnera aphidicola, Prochlorococcus marinus, Pseudomonas fluorescens, Rhodopseudomonas palustris and Synechococcus sp) that were recomputed with the same protocol, since excluded from the database due to poor backbone coverage. For all pairs, we compute the alignments with our 6 programs. For 13 pairs, Vmatch yields erroneous results (detects non existing MEMs), which were excluded from further analysis. The backbone according to YH is the intersection of the set of anchors on each genome.

Criteria for Evaluation

To compare alignments, all genome aligner publications use global quantitative criteria like the percentage of identity (%id) and the coverage, however not necessarily with the same definition. The usual definition of the %id, percentage of identical base pairs over the total alignment length (as in Mosaic), makes it incomparable between alignments. We define the coverage as the total length of aligned segments, and the %id as the ratio of identical bases in aligned segments (of the coverage) over the genome length.

To measure the reliability of the genome alignments, we compare their intersection with the sets of orthologous genes as defined in the OMA database [START_REF] Schneider | OMA Browser Exploring orthologous relations across 352 complete genomes[END_REF]. We retrieved from OMA the list of orthologous genes and their positions for 12 pairs. For each, we compute the number and % of the genomic sequence of orthologous genes included in the backbone.

Results

The six programs were applied on every pair of intra-species bacterial genomes (see Section 2). The results were compared to those obtained using MGA, Mauve (collected from Mosaic) with respect to the criteria defined above. Result tables and additional information can be found at the following location: http://www.lirmm.fr/˜uricaru/Appendix JOBIM09.html (Appendix).

Present Achievements

The first striking result lies in the difference of coverage between different species obtained by MGA and Mauve. For some species all pairwise alignments cover more than 90% of the genome (e.g., on Streptococcus thermophilus), while in others the coverage is below 10% (e.g., Synechococcus sp). One also observes, but more rarely, species for which the coverage of both methods varies greatly among pairs of strains (for P. marinus, the coverage of MGA varies in [0, 78]% and that of Mauve in [6, 96]%).

It is clear that these programs succeed in aligning some genome pairs and fail in others, which could be due either to a high level of divergence that makes the sequences unalignable (see Appendix) or to a methodological failure in detecting similarity regions or in chaining.

Local Similarities (LS) vs MEMs

The similarity detection phase is mainly responsible for the sensitivity of an anchor based method. Indeed, the chaining phase only discards potential anchors, however it may be unadapted to the type of similarities used. Here, to assess the impact on sensitivity, we compare the genome coverage obtained after the phases 1 and 2 of three different similarity detection methods combined with two chaining algorithms on a large panel of genome comparisons. Similarities are either short exact matches (MEMs), BLAST local alignments or local alignments based on spaced seeds (YASS). Figure 1 shows the difference of genome coverage between pairs of methods as box plots.

The left plot, which compares the effect of MEMs versus spaced seeds LS combined with Chainer, demonstrates that a classical chaining algorithm is unadapted to LS. This is due to overlaps between long local similarities, which are prohibited in the chain and cause Chainer to discard large alignment regions, especially for highly similar genomes. We thus designed a new chaining method allowing for overlaps, called Hierarchical chaining (see Section 2).

The central part of Figure 1 shows which chaining method suits a given type of similarities. Chainer does well with MEMs (VH-VC), Hierarchical performs in average better than Chainer with BLAST LS (BH-BC), and always surpasses it with spaced seeds LS (YH-YC). The right part compares the combination YH with the other best combinations. It clearly shows that YH surpasses all other methods in coverage and can even achieve important differences. Let us take the case of P. marinus strains CP 000111 GR vs CP 000095 GR as a running example of divergent strains: YH obtains 57% coverage, while BH covers 3% of the genome and VC not even 1%.

Our comparisons provide clear evidence that using spaced seeds in the similarity detection phase improves the coverage, and therefore the global sensitivity of the anchor strategy. Thus, in some cases, alignment failure was due, indeed, to a lack of sensitivity of the anchor detection phase.

YH vs MGA/Mauve

Although MGA and Mauve execute two additional steps compared to our programs, the comparison of their results allows to see which proportion of the genome can be aligned solely with the chain of anchors and how it contributes to the percentage of identities.

On the 236 genome pairs, the coverage difference YH-MGA varies from -17% to 99%, with an average of 7.2%, and is zero or positive for 140 pairs and < -2% for only 10 pairs. The difference in %id varies from -16% to 99% with an average of 7%, and is zero or positive for 183 pairs and < -2% for only 2 pairs. Hence, the hierarchical program either achieves a result similar to MGA or improves on it in both aspects: coverage and %id.

In average, over the 236 genome pairs, the alignments of Mauve cover 13% more nucleotides than that of YH (variation within [-14, 69]%) and have nearly 10% more identities. This is mostly due to its ability to handle rearrangements. However, as detected in Mosaic, a high coverage sometimes hides unreliable alignments. The segments that are aligned with ClustalW in the fourth phase (these are termed aligned gaps by Mauve) do not necessarily share sequence similarity and are often unreliably aligned. We investigated whether unreliable segments have a high impact on the coverage especially for highly divergent strains.

Our running example with a pair of P. marinus strains is in fact a typical situation for the divergent bacterial cases. In this case, Mauve covers in average with 27% more than YH (84%, corresponding to 1491kb vs 57% corresponding to 1012kb), while the difference in identity percentage is only of 8% in its favour. As both the coverage and the %id are ratios over the genome length, we can say that it covers 27 additional % (479kb) of the genome with only 8% more identities (142kb). It suggests that some pairs of aligned segments could well be false positives (i.e., should not be part of the alignment). Indeed, by plotting the cumulative coverage with segments below a given threshold of %id, we found that Mauve covers 22, resp. 30%, with segments whose %id lies ≤ 50, resp. ≤ 55%.

Finally, we looked at the reliability and the accuracy of our backbones with a biological view-point. For this we compared the percentage of nucleotides from orthologous genes and the number of such genes included in YH, MGA, or Mauve backbones. In our P. marinus example, 60% of the nucleotides are part of YH backbone, compared to only 7% for Mauve and 3% for MGA. Even for the well studied E. coli comparison (K12 vs Sakai), where all three tools report a coverage 80% on Sakai genome, YH completely includes in its backbone 8% more orthologous genes than the other tools do. Even if it can be improved, this suggests that YH gives accurate and reliable backbones, with more precise segment bounds.

Discussion

In this work, we conducted one of the first evaluations of anchor-based genome alignment methods on a large set of intra-species bacterial genome alignments. For this, we propose a protocol and implement several programs performing only the first two steps of the anchor based strategy.

First, it appears that even for short, closely related, and sometimes collinear genomes, pairwise alignment is incompletely solved by nowadays programs. Second, the anchor chain they compute can be improved by using local alignments instead of shorter exact or approximate matches as similarities, provided that the chaining algorithm authorises overlaps between adjacent anchors. This improvement measured in terms of genome coverage and of %id is more pronounced if local alignments are detected with highly sensitive spaced seeds [START_REF] Noe | YASS: enhancing the sensitivity of DNA similarity search[END_REF]. Third, even if Mauve often achieves higher coverage than our method YH, the reliability of some of its regions aligned in the fourth phase is questionable, and their %id argues in favour of discarding them from the output (see the P.marinus example).

With its publication, Mauve opened the way to a better handling of rearrangements; nonetheless our results suggest the similarity detection could be improved, and thereby the global reliability of the complete alignment. The comparison of the coverage of known orthologs between MGA, Mauve, and YH corroborates these findings. Interestingly, our program YH performs drastic improvements where both MGA and Mauve fail: on species with highly divergent strains like B. aphidicola, P.marinus.

Besides this gain in coverage and percent identities over MGA or sometimes Mauve, YH runs faster (a maximum running time of 102 s. and an average of 10 s.) and brings qualitative ameliorations. Its chain contains 150 anchors in average vs several thousands for MGA and Mauve, making it simpler to visualise and to grasp. Moreover, all local alignments it includes have an associated E-value that lies above a given threshold, ensuring they are statistically significant, which is not the case in MGA or Mauve alignments. Altogether, YH could be useful to automatically determine the backbone (a goal of Mosaic) without further post-processing based on an arbitrary threshold.

  Figure 1: Boxplots of genome coverage differences between methods over 236 genome pairs. E.g., YH-YC means, for each pair, the genome coverage of YH method minus that of YC in %. In a boxplot, circles are outliers. Left part: YC-VC coverage. Central part: comparison of each similarity detection method combined either with Chainer or our Hierarchical chaining. The 4th boxplot plus the right part: YH compared to other combinations; YH obtains larger coverage in the vast majority of cases over all four other combinations.

Acknowledgements: RU benefits from a PhD fellowship from the French Ministery of Research.This work is supported by the ANR project CoCoGen (BLAN07-1 185484).


Paolo Simonetto
email: paolo.simonetto@labri.fr

David Auber
email: auber@labri.fr

An Heuristic for the Construction of Intersection Graphs

Keywords:

Most methods for generating Euler diagrams describe the detection of the general structure of the final drawing as the first step. This information is generally encoded using a graph, where nodes are the regions to be represented and edges represent adjacency. A planar drawing of this graph will then indicate how to draw the sets in order to depict all the set intersections.

In this paper we present an heuristic to construct this structure, the intersection graph. The final Euler diagram can be constructed by drawing the sets boundaries around the nodes of the intersection graph, either manually or automatically.

Introduction

Euler diagrams were introduced a long time ago [START_REF] Euler | Lettres à une princesse d'allemagne[END_REF] and have been widely used in many fields, but their automatic generation is a quite recent topic. There may be several explanations for this.

First of all, there is no universally accepted definition of a Euler diagram. Euler diagrams were introduced informally, and scientists and mathematicians have made different interpretations of the characteristics they have.

Secondly, Euler diagrams are not always drawable. All the existing definitions of Euler diagrams have sets that can be supplied as input but cannot be represented. The exact class of non-representable instances clearly depends on the definition, but the set is never empty.

Thirdly, Euler diagrams are most useful when they are clear and visually appealing. The definition of these aspects is hard to quantify and it is even more difficult to create these conditions on the final drawing.

Recent studies on automatically drawing Euler diagrams have been facing these problems. The lack of a strict definition has initiated the analysis of several kinds of Euler or Euler-like 1 diagrams: Chow [START_REF] Christopher | Generating and drawing area-proportional Euler and Venn diagrams[END_REF] dealt with 1 Classes of diagrams that extend the most accepted definitions are generally referred as Euler-like. the most common definition, Flower and Howse [START_REF] Flower | Generating euler diagrams[END_REF] with a restricted version, while Verroust and Viaud [START_REF] Verroust | Ensuring the drawability of extended euler diagrams for up to 8 sets[END_REF] and Simonetto and Auber [START_REF] Simonetto | Visualise undrawable euler diagrams[END_REF] with two extended versions.

Fish, Stapleton et al. [START_REF] Fish | Defining euler diagrams: choices and consequences[END_REF][START_REF] Fish | Formal issues in languages based on closed curves[END_REF][START_REF] Stapleton | Properties of euler diagrams[END_REF], on the other hand, studied the differences between the many definitions and described how the characteristics enforced (for instance admitting or denying multiple curve crossing points or concurrent boundaries) influence the class of the representable instances.

Moreover, Benoy and Rodgers [START_REF] Benoy | Evaluating the comprehension of euler diagrams[END_REF] started their user study on the comprehension of Euler diagrams, analysing how easily people can understand a diagram under different aesthetic conditions.

It is finally interesting to notice how Euler diagrams have not been studied only as an abstract concept, but as a way to answer really concrete visualisation problems. The previously cited contributions came from a variety of fields spanning software engineering diagrams [START_REF] Fish | Defining euler diagrams: choices and consequences[END_REF][START_REF] Fish | Formal issues in languages based on closed curves[END_REF][START_REF] Stapleton | Properties of euler diagrams[END_REF][START_REF] Flower | Generating euler diagrams[END_REF], video database queries [START_REF] Verroust | Ensuring the drawability of extended euler diagrams for up to 8 sets[END_REF], and methods for visualising overlapping clusters on graphs [START_REF] Simonetto | Visualise undrawable euler diagrams[END_REF].

The intuitiveness of Euler diagrams and their wide range of applications show how a general method, applicable to all the possible input cases, would answer many visualisation problems.

In this paper, we present an algorithm to construct a graph that represents the skeleton of Euler representations, a class of always drawable Euler-like diagrams. As for most of the other approaches to the generation of Euler diagrams, this represent a first and crucial step for the depiction of the final structure.

Related work and definitions

The generation of Euler diagrams has been studied according to the different interpretations on Euler diagrams [START_REF] Christopher | Generating and drawing area-proportional Euler and Venn diagrams[END_REF][START_REF] Flower | Generating euler diagrams[END_REF][START_REF] Verroust | Ensuring the drawability of extended euler diagrams for up to 8 sets[END_REF]. Unfortunately, all these methods suffer of undrawable instances, which are set systems not representable with the diagrams of the class.

Undrawable instances exist because unrelated sets should not overlap. In fact, it might be impossible to draw a set without overlapping at least another unrelated one, [START_REF] Christopher | Generating and drawing area-proportional Euler and Venn diagrams[END_REF]. (b) the Euler representation described in [START_REF] Simonetto | Visualise undrawable euler diagrams[END_REF]. We can see that the set C is not formed by a single connected region and that set A has a "hole". When a set is disconnected, a link is put to connect the separate regions.

and so to create a proper Euler diagram. That conflicts with the idea of providing an output for every possible input.

To our knowledge, the only other approach able to deal with every input is the one described by Rodgers, Zhang and Fish [START_REF] Rodgers | General euler diagram generation[END_REF] extending the methods proposed in [START_REF] Flower | Generating euler diagrams[END_REF][START_REF] Rodgers | Embedding wellformed euler diagrams[END_REF]. However, the authors did not concentrate on the construction of the structure graph, particularly when the diagram cannot be represented in a planar way. For this reason, we investigated the issue further.

Euler representations. In a previous paper [START_REF] Simonetto | Visualise undrawable euler diagrams[END_REF], we analysed the conditions necessary to avoid undrawable instances in Euler-like diagrams. The study resulted in a class of Euler-like diagrams that:

• might contain holes inside the main region of a set. In other words, a set might not be bounded by exactly one closed line. • might have disconnected set regions. This means that a set might be represented with two regions that may be far from each other.

The ambiguities introduced by these two visual structures could be overcome by colouring the actual set region and by introducing links between the disconnected set regions. This leads to diagrams similar to the one showed in figure 1(b), called Euler representations.

Additional methods for improving the understanding of complex Euler representations have also been suggested. However, as these cases find a proper application only in very rare and complex cases, they are not taken into consideration in this paper.

Classes and zones. In the paper, the sets to be drawn are called classes to avoid confusion with the more common word "set". They are indicated with capital letters. The regions that are shared by a subset S of classes and are external to all the other existing classes are defined as zone. They are indicated with lower case sequences of letters, corresponding to the elements of S. 2Examples of zones are graphically shown in figure 2(b): there we can see how zone ab is formed by the intersection of the classes in the subset S = {A, B}, minus the region that is also inside C.

When referring to zones, we indicate a generic sequence of lower case letters with a Greek letter. For instance we might have that α = abd or β = ac. We use the symbol * to indicate all the zones sharing the same letters. For instance, the notation ab * indicates the set of all the zones which labels contain ab.

Finally, the function C returns the subset of classes used to generated the zone. For instance C(ab) = {A, B}.

Intersection graphs. In [START_REF] Simonetto | Visualise undrawable euler diagrams[END_REF] we showed how Euler diagram can be generated starting from a graph that summarises its structure, and vice versa. This graph, called intersection graph, has nodes corresponding to the zones of the final diagram and edges that link adjacent zones. An example of intersection graph and of the transformations involved is shown in figure 2.

Intersection graph characterisation. The intersection graph describes the connectivity of the final diagram. Thus, many characteristics of the resulting diagram depend on the topology of the intersection graph. We defined the following rules valid for well-formed intersection graphs:

1. The intersection graph must be planar. The first rule must always be respected. In order to build a proper Euler diagram, we have to construct an intersection graph that strictly satisfies also rule number 2 and 4. However, we have no other strict limitations than rule 1 when building the intersection graph of a Euler representation.

Method overview

When constructing an intersection graph, we have no flexibility in the nodes to insert: each node corresponds to a non-empty zone. The real problem is identifying which edges to insert.

Even for Euler diagrams, there might be many selections of edges that lead to a correct output. Unfortunately, their clarity might vary greatly, as shown in figure 3. The same problem appears to a greater extent with Euler representations, as we have more freedom in the construction of their intersection graphs.

Thus, the construction of intersection graphs consists of an optimisation procedure that aims to:

• identify a result as similar as possible to a proper Euler diagram,

• choose intersection graph configurations that lead to as clear diagrams as possible.

The approach. Our algorithm constructs the intersection graph inserting one edge at each step. Thus, the main part of the algorithm is constituted by a procedure that at each iteration selects one edge and inserts it. The 3 At this step it might be necessary to add a node representing the null zone, that is the area external to every class. selection of the edges is steered by a metric that encode the edge contribution in respecting the rules enounced before. The insertion procedure and the metric are described in more detail in the following sections.

The insertion procedure

The algorithm we developed follows a procedure similar to the classical Kruskal's algorithm for minimum spanning trees. We start with a graph that has no edges, and at each step we insert the edge with higher metric value. Once inserted it remains part of the resulting intersection graph.

The metric encodes the rules that characterise a wellformed intersection graph. However, there is a particular condition we prefer to handle at this level, rather than in the metric calculation: the planarity. In fact, as the resultant graph must be planar, this condition should not compete with other aesthetic aspects.

Initialisation We start with a graph that has a node for each non-empty zone, and no edges.

During the computation, we keep a pool of candidate edges for insertion. This collection is initialised with all the possible edges, and it will contain only edges that have not been inserted, discarted, or weighted with negative or null values.

Iterations At each iteration, the following steps are executed:

1. The best edge of the pool is selected.

A planarity test is executed to determine whether

the edge makes the graph unplanar. At the first step we suppose that the edge (ab, abc) with value 2 (since it would merge components for the class schemas of A and B) is the one selected to be inserted. At the second step, let us suppose we insert the edge (b, ab) with value 1 (it connects the connected components {b} and {ab, abc} in the class schema B). Because of the insertion of this edge, the edge (b, abc) updated its value to 0. The same happens to the edge (a, abc) after the insertion of (a, ab).

3. If the graph is no longer planar, the edge is discarded.

4. If the graph is still planar, the edge is added and the weights updated.

The algorithm terminates when there are no more edges in the pool, that indicates no more useful edges are available for the insertion.

The output When the algorithm terminates, we obtain the final intersection graph. Once layed out, the graph will allow us to draw the boundaries of the sets to be represented in order to generate the Euler representation.

The final intersection graph might encode a representation where classes are disconnected regions. This happens when it is impossible to connect zones of the same class without breaking the planarity. This result is perfectly normal since non-planar intersection graphs are the main cause of undrawable Euler diagrams. This is also the reason why Euler representations sometimes use links (a link is shown in figure 1(b), even if in that case it was not necessary).

The metric

The weight assigned to the edges encodes how much their insertion in the current intersection graph would contribute in the optimisation procedure. In other words, how much the insertion of an edge would contribute in obtaining a well-formed and readable Euler diagram.

Promote class connections. In order to avoid the insertion of links, we need to insert edges between all the nodes of the same class to make their induced subgraph connected. Hence, this property will be the highest priority in weighting the edges.

Reducing the number of edges is a good idea, since the more edges we need to insert, the more likely the graph violates planarity. We will favour edges that connect components in many class schemas at the same time, rather than edges that connect few of them.

For this reason, we define the function c(e). The function counts the number of class schemas in which the insertion of e would connect disconnected components. It is worth noting that this function depends on the edges previously inserted. An example of what the function c means and how it works when updating a graph, is shown in figure 4.

Promote aesthetic. In order to obtain connected set intersections and avoid unclear configurations (such as shown in figure 3), we will promote a structure where the zones connected do not differ too much from each other. This is obtained using two functions: where e is a candidate edge, and s e and t e are the zones corresponding to the two incident nodes.

The first function aims to detect the number of unrelated classes that are forced to be adjacent through this edge. For instance, the edge (ab, ac) forces classes B and C to share a boundary even when it is not necessary. This is not the case for the edge (a, abc), since no unwanted boundaries would overlap. The function u returns 1 in the first case, but 0 in the second. An example of why it is important to penalise these edges is shown in figure 5.

The second function penalises edges between nodes that differ for more than one class. For instance, the edge (a, abc) connects two zones where the second is included in two classes, B and C, more than the first. When choosing between (a, ab) or (ab, abc) there is just one class more for one of the two nodes. The function v returns 1 in the first case and 0 in the second. Figure 6 shows why this penalty is helpful. Concerning holes. The metric does not explicitly promote a final diagram without holes. In fact, the problem can be handled at a different level.

The insertion of a node relative to the null zone, as explained in [START_REF] Simonetto | Visualise undrawable euler diagrams[END_REF], has two main aims: defining the outer face of an intersection graph embedding and forcing the zones linked to it to stay on the outer face.

In our automatic approach for the generation of Euler representations we answer these issues working directly on the graph embedding. In fact, being able to operate on the embedding and choose the external face in order to maximise the number of outer nodes allowed us to extend the limits of our method.

The final metric. The metric value for each edge e is obtained combining the previous functions:

w(e) = c(e) -p 1 u(e) -p 2 v(e)
where the p 1 and p 2 are parameters that define the penalty weights.

When choosing the parameter values, we recommend that they are a small fraction of unity, in order to preserve the central importance of c. In fact, u and v have been developed with the idea that they should almost only influence the rank of edges with the same value of c.

Finally, we suggest p 1 ≥ p 2 , as the condition related to v is less confusing than the one associated to u.

Examples

We report some intersection graphs generated with this method. Figure 7 shows two set configurations involving several overlaps and inclusions. The relative Euler diagram can be easily detected by drawing lines that enclose the nodes of each class. shows, in an appealing way, the overlaps created by actors who took part in more than one film.

We can also note how the methods detected a proper Euler diagram, as there were no planarity problems. Moreover, that the metric proposed contributed in detecting a clear structure of the intersection graph, as the unclear configuration of figure 3 are avoided.

Conclusions

We presented an heuristic for the construction of intersection graphs as described in [START_REF] Simonetto | Visualise undrawable euler diagrams[END_REF]. The algorithm presented attempts to optimise the rules that characterise a good intersection graph, obtaining satisfactory results in terms of the quality of the output.

This algorithm represents the first step of a completely automatic method for the generation of Euler representations. We are currently developing a method where the constructed intersection graph is drawn along with the class boundaries, in order to obtain drawings similar to the one manually generated in figure 8(b).

Figure 1 :

 1 Figure 1: Euler and Euler-like diagrams. (a) an Euler diagram according to the most accepted definition, reported in[START_REF] Christopher | Generating and drawing area-proportional Euler and Venn diagrams[END_REF]. (b) the Euler representation described in[START_REF] Simonetto | Visualise undrawable euler diagrams[END_REF]. We can see that the set C is not formed by a single connected region and that set A has a "hole". When a set is disconnected, a link is put to connect the separate regions.

Figure 2 :

 2 Figure 2: Transformations between Euler diagrams and intersection graphs. (a) the original diagram. (b) detection of the diagram zones. (c) the resulting intersection graph. The dashed line is not part of the graph, but shows how to reverse the procedure. For drawing the boundary of the class B we need to enclose the nodes b, ab, abc and intersect the edges (a, ab), (ac, abc).

2 .

 2 Each class schema, that is the subgraph induced by the nodes of a class (the set of zones a * , b * , . . . ), should be connected. This avoids the generation of disconnected classes. 3. For each α, each subgraph induced by a set of zones α * should be connected. This avoids the same classes intersecting in disconnected regions (in figure 3(b), let α = ab. The subgraph induced by α * = {ab, abc} is not connected. Therefore, the classes A and B intersect in two separate regions). 4. Each subgraph induced by the zones external to a class (the set of zones a * , b * , . . . ) should be connected. 3 This avoid holes. 5. The intersection graph should have a compact and regular layout.

Figure 3 :

 3 Figure 3: Intersection graphs for three classes A, B, C having the zones a, b, c, ab and abc non-empty. There are many sets of edges that lead to valid intersection graphs; here three of them are shown. The configuration in subfigure (a) is clearer than the others, as in (b) classes A and B intersect in two separate regions and in (c) it is more difficult to distinguish the classes involved in each zone.

Figure 4 :

 4 Figure4: Values of c for the edges of the intersection graph for several edge insertions. At the first step we suppose that the edge (ab, abc) with value 2 (since it would merge components for the class schemas of A and B) is the one selected to be inserted. At the second step, let us suppose we insert the edge (b, ab) with value 1 (it connects the connected components {b} and {ab, abc} in the class schema B). Because of the insertion of this edge, the edge (b, abc) updated its value to 0. The same happens to the edge (a, abc) after the insertion of (a, ab).

  u(e) = min( |C(s e )|, |C(t e )| ) -|C(s e ) ∩ C(t e )| v(e) = max( |C(s e )|, |C(t e )| ) -|C(s e ) ∩ C(t e )| -1

Figure 5 :

 5 Figure 5: Unwanted proximity. At the current stage of the intersection graph we need to insert the edge (a, ab) or the edge (ab, ac). The picture shows the result of the two choices. The diagram below is much less clear, as it makes two unrelated classes to share their boundaries.

Figure 6 :

 6 Figure 6: Multiple class difference. We can now decide either to insert the edges (a, ab) and (b, ab), or the edges (a, abc) and (b, abc). The figure shows the intersection graphs and the resulting diagrams for both the choices. The first diagram shows more clearly the way the classes overlap.

Figure 8 (

 8 Figure 8(a) shows the intersection graph obtained on a real world case. We extracted film data from the Internet Movie Database 4 and we defined 17 classes composed by actors who take part to the same film. We obtained a Euler representation by manually enclosing the nodes with lines and inserting nodes to represent the class elements. The resulting diagram (see figure8(b)) shows, in an appealing way, the overlaps created by actors who took part in more than one film.We can also note how the methods detected a proper Euler diagram, as there were no planarity problems. Moreover, that the metric proposed contributed in detecting a clear structure of the intersection graph, as the unclear configuration of figure 3 are avoided.

Figure 7 :

 7 Figure7: Two intersection graphs generated with our method. The elements of the graph allowed to detect the class boundaries, which have been manually drawn.

Figure 8 :

 8 Figure 8: Application of the method to real world data. (a) the intersection graph generated and drawn in a planar way. (b) the Euler diagram manually generated from the intersection graph. The zones have been filled with the elements they contain.

As the letters in the labels derive by set elements, the actual order in which they appear is not important.