Philippe Gambette
email: philippe.gambette@univ-mlv.fr

Vincent Berry
email: vberry@lirmm.fr

Christophe Paul
email: paul@lirmm.fr

QUARTETS AND UNROOTED PHYLOGENETIC NETWORKS

Keywords: phylogenetic networks, quartets, level-k networks, NP-hardness, exact algorithms

HAL is

Introduction

Phylogeny aims at reconstructing the evolution of a set of taxa (species for example), given information on this set of taxa, such as DNA sequences of some representatives. A tree, whose leaves are bijectively associated with the taxa, is often considered as the most appropriate model. This tree is rooted when the ancestor of the taxa can be located, unrooted otherwise. But sometimes, when exchanges of genetic material between coexisting species is suspected to occur, phylogenetic networks are preferred to trees. There exist two kinds of phylogenetic networks 1 : abstract networks are used to visualize evolutionary data but their vertices and edges cannot be interpreted as biological events. On the contrary, explicit phylogenetic networks model evolution with their vertices representing ancestral species. Abstract networks are usually faster to compute, but difficult to interpret and to visualize efficiently.

Methods based directly on sequences are usually slow, as sequences are very large, and approaches have been proposed to reconstruct unrooted phylogenetic networks from various input: distances, unrooted trees, quartets (i.e. unrooted phylogenetic trees on four taxa). Most of these methods work by computing a split system2 on the taxa (except T-Rex which reconstructs reticulograms directly from a distance matrix [START_REF] Makarenkov | T-REX: reconstructing and visualizing phylogenetic trees and reticulation networks[END_REF] ). After filtering some splits [START_REF] Whitfield | Filtered Z-closure supernetworks for extracting and visualizing recurrent signal from incongruent gene trees[END_REF][START_REF] Holland | Using supernetworks to distinguish hybridization from lineage-sorting[END_REF] , it is represented by a split network [START_REF] Dress | Constructing splits graphs[END_REF][START_REF] Holland | Visualizing conflicting evolutionary hypotheses in large collections of trees: Using consensus networks to study the origins of placentals and hexapods[END_REF][START_REF] Grünewald | QNet: An agglomerative method for the construction of phylogenetic networks from weighted quartets[END_REF][START_REF] Grünewald | Constructing phylogenetic supernetworks from quartets[END_REF] , or by a galled network [START_REF] Dh Huson | Reconstruction of reticulate networks from gene trees[END_REF][START_REF] Dh Huson | Beyond galled trees -decomposition and computation of galled networks[END_REF] . These indirect reconstruction approaches, which first compute an abstract representation of the data, and then try to deduce an explicit phylogenetic network of a restricted subclass of phylogenetic networks, have drawbacks. If we choose to visualize the output with a split network, its number of edges may be quadratic in the number of splits, which results in a high dimensional network, or a grid, quite difficult to interpret biologically. If we choose galled networks, the output has topological constraints which may not reflect all the possibilities of biological evolution, if for example an ancestral species which appeared following hybridization events also gives rise to a new species through another hybridization event. Furthermore, the reconstruction of this network may be ambiguous, as a final step to choose among the possible networks which represent the split system may be necessary [START_REF] Kloepper | Algorithms for the Calculation and Visualisation of Phylogenetic Networks[END_REF] .

In a rooted context on the contrary, a lot of methods were designed to directly output explicit phylogenetic networks, in particular from triplet input, i.e. from rooted phylogenetic trees on three taxa. However, approaches where the root is chosen at the last step are usually preferred, because choosing the position of the root is a difficult task, which could cause important errors if done too early [START_REF] Orp Bininda-Emonds | Getting to the roots of matrix representation[END_REF] . Unrooted tree data is most often available, for example in databases like Hogenom [START_REF] Dufayard | Tree pattern matching in phylogenetic trees: Automatic search for orthologs or paralogs in homologous gene sequence databases[END_REF] or PhylomeDB [START_REF] Huerta-Cepas | PhylomeDB v3.0: an expanding repository of genomewide collections of trees, alignments and phylogeny-based orthology and paralogy predictions[END_REF] .

In this article, we generalize to unrooted networks the level parameter proposed to describe the complexity of explicit rooted phylogenetic networks [START_REF] Jansson | Inferring a level-1 phylogenetic network from a dense set of rooted triplets[END_REF] . We focus on unrooted binary phylogenetic networks, defined as graphs whose vertices have either degree 3 (internal vertices), or degree 1 (the leaves, bijectively labeled by a set X of taxa). Note that as the network is unrooted and undirected, it is impossible to decide whether an internal vertex corresponds to a speciation event or a reticulation event. This interpretation task will however be possible after a rooting step (see Fig. 1), which can be done according to various criteria.

Methods were proposed to reconstruct rooted level-k networks from triplets [START_REF] Jansson | Inferring a level-1 phylogenetic network from a dense set of rooted triplets[END_REF][START_REF] He | Inferring phylogenetic relationships avoiding forbidden rooted triplets[END_REF][START_REF] Jansson | Algorithms for combining rooted triplets into a galled phylogenetic network[END_REF][START_REF] Van Iersel | Constructing level-2 phylogenetic networks from triplets[END_REF][START_REF] Van Iersel | Constructing the simplest possible phylogenetic network from triplets[END_REF][START_REF] To | Level-k phylogenetic networks are constructable from a dense triplet set in polynomial time[END_REF][START_REF] Byrka | Worst-case optimal approximation algorithms for maximizing triplet consistency within phylogenetic networks[END_REF] . In this article, we show how to translate some of them Quartets and unrooted phylogenetic networks 3 to reconstruct unrooted level-k networks from quartets. Some of the results can be deduced easily with the appropriate changes in definitions for the unrooted context (SN-splits instead of SN-sets, for instance), while others involve very different algorithmic tools and ideas, such as testing whether a quartet is consistent with an unrooted level-k network.

The links we uncover here between abstract and explicit networks also provide a new point of view on combinatorial objects like circular split systems, quartets and unrooted trees. In the same way as the inclusion relationship between clusters consistent with a rooted level-1 network and weak hierarchies [START_REF] Gambette | On encodings of phylogenetic networks of bounded level[END_REF] , the properties we give here may have interesting algorithmic consequences, and help better understand the combinatorics of the unrooted case, which is often more complex than the rooted one [START_REF] Av Aho | Inferring a tree from lowest common ancestors with an application to the optimization of relational expressions[END_REF][START_REF] Steel | The complexity of reconstructing trees from qualitative characters and subtrees[END_REF] .

Outline of the article. We first introduce some basic definitions in Section 2, then we detail the relationships between rooted and unrooted level-k networks in Section 3. Section 4 provides results about splits systems consistent with level-1 networks, which have consequences for quartet sets consistent with such networks. In Section 5, we address the complexity of two basic problems involving unrooted levelk networks and quartets. We show that deciding whether a quartet is consistent with an unrooted level-k network is polynomial time solvable. On the contrary, we prove that reconstructing an unrooted level-1 network consistent with an unrestricted quartet set is NP-complete. Therefore, we study a restricted case in Section 6: we show how to obtain a tree decomposition of an unrooted level-k network knowing its complete quartet set. Finally, in Section 7, we focus on the case of unrooted level-1 networks and show that it is possible to reconstruct such networks in polynomial time from their complete quartet set. We also study the dense case, to give puzzling properties and open problems.

Basic Definitions

Let us recall from graph theory that an articulation vertex is a vertex whose deletion disconnects the graph. A biconnected component of a graph G = (V, E) is a maximal induced subgraph of G without articulation vertex. For any E ′ ⊂ E, we denote by G -E ′ the graph G ′ = (V, E -E ′ ), i.e. the graph obtained from deleting the edges of E ′ from G. We say that a block of a directed graph is a biconnected component of its underlying undirected graph [START_REF] Gusfield | A decomposition theory for phylogenetic networks and incompatible characters[END_REF] . Note that throughout this paper, the graphs and directed graphs we consider do not have multiple edges or arcs. Definition 1. [START_REF] Jansson | Inferring a level-1 phylogenetic network from a dense set of rooted triplets[END_REF] A rooted level-k network N is a directed acyclic graph in which exactly one vertex has indegree 0 and outdegree 2 (the root) and all other vertices have either indegree 1 and outdegree 2 (split vertices), indegree 2 and outdegree ≤ 1 (hybrid vertices), or indegree 1 and outdegree 0 (leaves, distinctly labeled) and such that any block contains at most k hybrid vertices.

In fact, an equivalent definition can be obtained by imposing the same degree conditions, and adding that in any block, it is possible to get a tree by removing at most k arcs (one arc per hybrid vertex).

In this paper, we extend the latter definition to unrooted phylogenetic networks. A cut-edge or bridge is an edge whose removal disconnects the graph, we say it is trivial if it is linked to a degree 1 vertex. We say that the blobs of an undirected graph are its maximal bridgeless components. Note that contrary to the biconnected components of a graph used to define blocks, there is no blob with exactly two vertices. A minimal cut is a set of edges whose removal disconnects the graph, which is minimal for inclusion. Definition 2. An unrooted phylogenetic network N on a set X of taxa is a loopless graph whose vertices have either degree 3 (internal vertices), or degree 1 (the leaves), and such that its set L(N ) of leaves is bijectively labeled by X. An unrooted level-k network N on a set X of taxa is an unrooted phylogenetic network such that an unrooted tree connecting all vertices of N can be obtained by removing at most k edges per blob, as illustrated in the network N in Fig. 1. An unrooted phylogenetic network is simple if all its cut-edges are trivial.

N N ′ 1 N ′ 2
Fig. 1. An unrooted level-2 network N with leaf set {a, b, c, d, e, f, g, h, i}. All unlabeled vertices are internal vertices. The gray areas correspond to the blobs of N , and the bold arcs are such that their deletion transforms N into an unrooted tree. As we discuss in Section 3, there may be many possibilities (e.g. N ′ 1 and N ′ 2 , whose arcs are directed downwards) to root an unrooted phylogenetic network, even if the root is chosen at the same position, which all provide a rooted phylogenetic network of the same level.

An unrooted level-0 network is usually called an unrooted phylogenetic tree and an unrooted level-1 network is simply an unrooted galled tree [START_REF] Gusfield | Optimal, efficient reconstruction of phylogenetic networks with constrained recombination[END_REF] . Note that an unrooted level-1 network is outerplanar, i.e. it has an embedding in the plane with no crossing edges, and all vertices on its outer face. For the sake of simplicity, in the following, we will identify each leaf with its label.

Note that, as usually done [START_REF] Van Iersel | Constructing the simplest possible phylogenetic network from triplets[END_REF][START_REF] Van Iersel | Uniqueness, intractability and exact algorithms: reflections on level-k phylogenetic networks[END_REF] , we consider that all rooted or unrooted level-k phylogenetic networks do not contain any block or blob with less than four vertices. This restriction is natural, as it prevents from adding superfluous edges which make the network more complex but do not have any influence on the set of triplets or quartets consistent with it. A quartet ab|cd is an unrooted phylogenetic tree on four leaves a, b, c, d ∈ X, where a and b (resp. c and d) share a common neighbor, as shown in Fig. 2. Definition 3. We say that an unrooted phylogenetic network N on a set X of taxa is consistent with the quartet ab|cd (or equivalently ab|cd is consistent with N ) if N contains two distinct vertices u and v, four leaves a, b, c and d ∈ L(N ), and pairwise internally vertex-disjoint paths (i.e. which share no internal vertex) from a to u, from b to u, from u to v, from v to c and from v to d.

For example the unrooted level-2 network N of Fig. 1 is consistent with, amongst other, the quartets cd|ef , f e|dg, f d|eg and f g|ed, and not with, amongst other, ac|bd or ai|dh. This definition is equivalent to the following: Also note that these definitions of quartet consistency are appropriate for the completely resolved unrooted phylogenetic networks we are studying here, i.e. networks with vertices of degree at most three. In the context of unresolved unrooted phylogenetic networks, with vertices of degree greater than 3, this definition should be adapted to allow multiple quartet resolutions for quartets involving these vertices.

A set Q of quartets is consistent with a network N if every quartet of Q is consistent with N . The set of all quartets consistent with N is denoted by Q(N ). We say that Q is dense if it contains at least one quartet on any subset of four leaves from X. For A X, we define the restriction of Q to A to be

Q |A = {ab|cd such that a, b, c, d ∈ A}.
Given a set X of taxa, a split S = A| Ā (or equivalently Ā|A) is a bipartition of X into two nonempty and complementary sets. We call

S trivial if |A| = 1 or | Ā| = 1. Two distinct splits S 1 = A 1 |A ′ 1 and S 2 = A 2 |A ′ 2 are compatible if one of the four intersections A 1 ∩ A 2 , A 1 ∩ A ′ 2 , A ′ 1 ∩ A 2 or A ′ 1 ∩ A ′ 2 is empty 2 .
A split system S is a set of splits, it is compatible if its splits are all pairwise compatible. It is circular if there exists an order σ on X such that for any split A| Ā of S, A or Ā is an interval of σ (i.e. a set of consecutive elements of σ).

A split A| Ā is consistent with an unrooted phylogenetic tree T if T contains an edge which disconnects A and Ā, i.e. A and Ā belong to two distinct connected components. An unrooted phylogenetic tree T on a set X of taxa is contained in an unrooted level-k network N if T can be obtained from N by a sequence of edge removals and edge contractions. We can now define split consistency with an unrooted phylogenetic network, following Woolley et al. [START_REF] Woolley | A comparison of phylogenetic network methods using computer simulation[END_REF] Definition 5. A split A| Ā is consistent with an unrooted phylogenetic network N if it is consistent with an unrooted phylogenetic tree contained in N .

We finally call S(N ) the set of all splits consistent with an unrooted phylogenetic networks, and say that a split system S is consistent with N if S ⊂ S(N ).

Rooted and Unrooted Level-k Networks

In this section, we illustrate the fact that there are many possible ways to root an unrooted level-k network by directing its edges. We first give a definition to formally explain how to root an unrooted level-k network to get a rooted level-k phylogenetic network. Definition 6. Rooting an unrooted level-k network N = (V, E) consists in obtaining a rooted phylogenetic network N ′ = (V ∪ {r}, A) in the following way:

(i) locating the root, i.e. choosing an edge xy of N and subdividing it to create a degree 2 vertex r (which will become the root of N ′ , parent of x and y), which provides a graph N ′′ ; (ii) orienting the edges of N ′′ to transform them into the arcs of N ′ , i.e.:

choosing an order σ :

V ∪ {r} → [0..|V |] such that σ(r) = 0 and ∀u ∈ V, ∃v ∈ V ∪ {r} such that:
Quartets and unrooted phylogenetic networks 7

Proposition 1. For any integer k ≥ 2, there exists an unrooted level-k network N k with 2k leaves such that N k has at least 2 k rootings where the root r is put on the same edge of N k .

Proof: We first describe how to recursively build N k . To build N 1 , we consider a cycle with two vertices v 0 0 and v 1 0 which are linked respectively to a leaf x 0 0 and a leaf

x 1 0 . To build N k+1 from N k , call e 0 k-1 the edge incident to v 0 k-1 but not to v 1 k-1
, and

e 1 k-1 the edge incident to v 1 k-1 but not to v 0 k-1 .
Subdivide these two edges (to build N 2 from N 1 , as both edges link v 0 0 and v 1 0 , just subdivide one of these two edges twice) and connect the two vertices created by the subdivision, then subdivide this new edge twice to obtain two vertices : v 0 k (the closest to v 0 k-1 ) and v 1 k . Finally, add two leaves x 0 k and x 1 k connected respectively to v 0 k and v 1 k . For example N 3 is illustrated in Fig. 3.

N 3 N ′ 3
Fig. 3. Lower bound on the number of rootings: the unrooted level-3 network N 3 has at least 2 [START_REF] Makarenkov | T-REX: reconstructing and visualizing phylogenetic trees and reticulation networks[END_REF] rootings. The level-3 network N ′ 3 , whose arcs are directed downwards, is an example of these rootings.

To check that N k has at least 2 k rootings, we show how every integer in a

= k-1 i=0 a i 2 i ∈ [0..2 k -1]
, where a i ∈ {0, 1}, can be bijectively associated to a rooting of N k . The idea is to root N k such that the leaf x ai i is below a hybrid vertex and the leaf x 1-ai i is below a split vertex. For example we show a rooting

N ′ 3 of N 3 corresponding to 4 = 0 × 2 0 + 0 × 2 1 + 1 × 2 2 in Fig. 3.
Theorem 1. Any rooting of an unrooted level-k network N provides a rooted level-k network N ′ . Proof: At step (ii) of the rooting process, orientations of the arcs are chosen such that if v can be reached by a directed path from u in N ′ then σ(u) < σ(v). Hence N ′ is acyclic, otherwise it would contain two vertices u and v such that σ(u) < σ(v) and σ(v) < σ(u), a contradiction.

We now check that N ′ respects the degree condition of level-k networks.

Step (i) of the rooting process ensures that N ′ has a root. Step (ii) guarantees that every degree 1 vertex in N is an indegree 1 vertex in N ′ . The remaining vertices have degree 3 in N . Step (ii) forces them to have indegree at least 1 and outdegree at least 1 in N ′ . Then, depending on the orientation of their third incident edge, they become split or hybrid vertices in N ′ .

Finally, we prove that the block B ′ of N ′ corresponding to an unrooted level-x blob B of N , for x > 0, contains x hybrid vertices. In the following, we focus on the graph B and the digraph B ′ themselves, without considering the rest of the graph N or the digraph N ′ . Recall that as B has unrooted level x, removing x edges from B provides a tree T .

We denote by e(B ′ ) the number of arcs of B ′ and v(B ′ ) its number of vertices. We also call respectively h and s its number of hybrid and split vertices (excluding the root of B ′ ). Then we have v(B ′ ) = 1 + h + s. If we consider the arcs of B ′ as incoming arcs, we have e(B ′ ) = 2h + s.

Thus, h = e(B ′ ) -v(B ′ ) + 1.
Now, note that the number v(B) (respectively e(B)) of vertices (resp. edges) of B can be v(B ′ ) -1 (resp. e(B ′ ) -1) or v(B ′ ) (resp. e(B ′ )) depending on whether the root of N ′ belongs to B ′ or not. Thus, we have e(B) -

v(B) = e(B ′ ) -v(B ′ ).
As the tree T covers all vertices of B, it has v(B) -1 edges. We also know that B has x edges more than T , so e(B) = v(B) -1 + x. Finally, we conclude that h = e(B ′ )v(B ′ ) + 1 = e(B)v(B) + 1 = x, so B ′ has x hybrid vertices, so the level is the same in the rooted and unrooted context.

Splits and Unrooted Level-k Networks

In this section, we give properties which link abstract and explicit phylogenetic networks.

The following definition of split consistency with an unrooted network, based on minimal cuts, is similar to the one given by Brandes and Cornelsen [START_REF] Brandes | Phylogenetic graph models beyond trees[END_REF] . Although they claim that explicit networks "represent sets of splits differently" than the minimal cut representation they propose for the networks they consider, we show that the following definition and Definition 5 are equivalent. Definition 7. A split A| Ā is consistent with an unrooted phylogenetic network N if there is a minimal cut of N which disconnects A and Ā. Proposition 2. Definitions 5 and 7 are equivalent.

Proof: Suppose N is disconnected by a minimal cut E into N A which contains all leaves of A and N Ā which contains Ā. Then let uv be an edge of E, and consider two spanning trees T u of N A and T v of N Ā such that u ∈ T u and v ∈ T v . Then A| Ā is consistent with a tree T ′ contained in N , obtained by the union of T u , T v and uv, and contraction of degree-2 vertices with one of their neighbors (avoiding of course the contraction of edge uv). Now suppose A| Ā is consistent with a tree contained in N . Then there exists an edge e x of T which disconnects T into two subtrees, T A which contains A and T Ā which contains Ā. Reversing the edge deletion and edge contraction operations performed to obtain T from N , we call x an edge of N corresponding to e x , and N A (respectively N Ā) the induced subgraph of N corresponding to the vertices of T A (respectively T Ā). We consider the set E of edges of N with one vertex in N A and the other one in N Ā. This set E is a minimal cut of N which disconnects A from Ā. It is a cut because when we delete the edges of E, we disconnect N A from N Ā. If it was not minimal, then there would exist another cut E ′ E. Consider an edge x ′ ∈ E -E ′ : it connects N A and N Ā, which are both connected, so E ′ is not a cut of N . Thus, we have found a minimal cut, E, which disconnects A and Ā.

Note that the fact that all splits consistent with an unrooted phylogenetic tree T are consistent with an unrooted phylogenetic network N does not necessarily imply that T is contained in N . For example, the splits of the tree T of Fig. 5(iii) are consistent with the network N ′ of Fig. 5

(ii) but T is not contained in N ′ . (i) (ii) (iii)
Fig. 5. An unrooted level-1 network N (i) and a simple unrooted level-1 network N ′ = Simple(N ) built from the order σ = abcdef g (ii) such that S(N ) ⊂ S(N ′ ) and Q(N ) ⊂ Q(N ′ ) (see Lemmas 1 and 2). However the tree T is contained in N but not in N ′ .

We now introduce a transformation operation to obtain a simple unrooted level-1 network from an unrooted level-1 network, illustrated in Fig. 5. Definition 8. Given an unrooted level-1 network N , we define as Simple(N ) a network obtained from N in the following way:

• as N is outerplanar, we consider the order σ of its leaves around the outer face of a planar embedding of N , • the graph Simple(N ) is obtained by attaching the leaves of X to a cycle respecting the order σ.

As Simple(N ) contains only one cycle and cut-edges leading to the leaves, it is clearly a simple unrooted level-1 network.

Lemma 1. Let N be an unrooted level-1 network and N ′ = Simple(N ), then S(N ) ⊂ S(N ′ ).

Proof: Let A| Ā be a split consistent with N , represented by a minimal cut of N , i.e. either a single cut-edge e, or a pair of edges {e 1 , e 2 } of the same cycle of N . Now consider the embedding of N used to build N ′ , and the order σ of leaves around the outer face in this embedding.

If A| Ā is represented by a single cut-edge e in N as in Fig. 6(i), then we can draw a closed curve intersecting only edge e of N . Otherwise, we draw a closed curve intersecting only edges e 1 and e 2 of N , as in Fig. 6(ii). In both cases, this curve splits the outerface of N in two parts, one containing A and the other Ā, and the set of leaves contained in one of these parts appears as an interval of σ. Thus, these leaves also appear consecutively around the cycle of N ′ , which implies that A| Ā also belongs to S(N ′ ).

(i) (ii)
Theorem 2. Let S be a split system on a set X of taxa. Then S is circular if and only if there exists an unrooted level-1 network N such that S ⊂ S(N ).

Proof: ⇒: As S is circular, consider one of the orders σ such that for each split A| Ā ∈ S, either A or Ā appears as an interval in σ. We build the simple unrooted level-1 network N by attaching the leaves of X to a cycle respecting the order σ. Then, for any split A| Ā, N restricted to A and their neighbors is a connected graph, which is connected through two edges e 1 and e 2 to the rest of the graph, as illustrated in Fig. 5(ii) for A = {b, c, d}. Thus {e 1 , e 2 } is a minimal cut of N which disconnects A and Ā, so A| Ā is consistent with N . Finally, S ⊂ S(N ).

⇐: Suppose there exists an unrooted level-1 network N such that S ⊂ S(N ). Then there also exists a simple unrooted level-1 network N ′ = Simple(N ) such that S(N ) ⊂ S(N ′ ) from Lemma 1, so S is also consistent with N ′ . The order σ obtained by considering the leaves around the cycle of N ′ , turning clockwise, and starting from any leaf, shows that S(N ′ ) is circular, so S is circular.

As the QNet algorithm is a heuristic algorithm to reconstruct a circular split system S from a set Q of weighted quartets 8 (aiming at optimizing the weights of consistent quartets), thanks to Theorem 2, it would be possible to find an unrooted level-1 network consistent with S. This would provide the first heuristic method to reconstruct explicit networks from quartets. We now focus on direct explicit network reconstruction from quartets, and give other quartet properties and algorithms in this perspective.

Quartets and Unrooted Level-k Networks

The first natural algorithmic question concerning quartets and unrooted phylogenetic networks is the time complexity for checking consistency. The dynamic programming approach used to compute the set of all triplets consistent with a rooted phylogenetic network in O(n 3 ) time [START_REF] Byrka | Worst-case optimal approximation algorithms for maximizing triplet consistency within phylogenetic networks[END_REF] does not extend to the unrooted case. However the problem is solvable in polynomial time.

Theorem 3. The set of all quartets consistent with an unrooted level-k network N can be computed in O n [START_REF] Holland | Using supernetworks to distinguish hybridization from lineage-sorting[END_REF] (1 + α(n, n)) time, where α is the inverse of the Ackermann function.

Proof: Using Definition 4, we just apply the best currently known algorithm for the 2-Vertex-Disjoint Paths Problem, which decides whether there exist two vertex-disjoint paths, one between a and b and the other between c and d in O(n + nα(n, n)) time [START_REF] Tholey | Improved algorithms for the 2-vertex disjoint paths problem[END_REF] , for each of the O(n 4 ) quartets ab|cd. Hence, the overall complexity of the algorithm is O n 5 (1 + α(n, n)) to retrieve all quartets consistent with N .

We now focus on reconstructing an unrooted level-k network consistent with a set of quartets.

Problem 1 (Level-k Quartet Consistency). Input: a quartet set Q on a set X of taxa. Output: decide whether there exists an unrooted level-k network on X, which is consistent with every quartet in Q.

We recall that in the rooted case, for level 0, this problem for triplets is polynomial time solvable [START_REF] Av Aho | Inferring a tree from lowest common ancestors with an application to the optimization of relational expressions[END_REF] . However, for upper levels it is NP-complete, by reduction form Set Splitting [START_REF] Jansson | Algorithms for combining rooted triplets into a galled phylogenetic network[END_REF][START_REF] Van Iersel | Uniqueness, intractability and exact algorithms: reflections on level-k phylogenetic networks[END_REF] . Steel proved in 1992 that the problem Level-0 Quartet Consistency is NP-complete [START_REF] Steel | The complexity of reconstructing trees from qualitative characters and subtrees[END_REF] , by reduction from Betweenness [START_REF] Opatrny | Total ordering problem[END_REF] .

We first prove that for level 1, this problem is equivalent to the same problem with the restriction that the network to reconstruct is simple. In this case, we refer to the problem as Simple Level-1 Quartet Consistency. Lemma 2. Let Q be a quartet set. There exists an unrooted level-1 network N consistent with Q if and only if there exists a simple unrooted level-1 network N ′ consistent with Q.

Proof: ⇒: Consider an arbitrary unrooted level-1 network N consistent with Q, and a simple unrooted level-1 network N ′ = Simple(N ) (see Fig. 5). For any quartet ad|bc in Q, as Q is consistent with N , there exists an unrooted tree which is contained in N and is consistent with ad|bc. In particular, this tree is consistent with a split A| Ā such that a, d ∈ A and b, c ∈ Ā. So A| Ā is consistent with N , and with N ′ from Lemma 1, so ad|bc is consistent with N ′ .

⇐: As N ′ is a simple unrooted level-1 network, then in particular it is an unrooted level-1 network, and it is consistent with Q.

Theorem 4. Level-1 Quartet Consistency is NP-complete. Proof: As it is possible to check in polynomial time that a quartet set is contained in an unrooted level-1 network, thanks to Theorem 3, the Level-1 Quartet Consistency problem is in NP.

To prove that it is NP-hard, as Lemma 2 shows that the Level-1 Quartet Consistency problem is strictly equivalent to the Simple Level-1 Quartet Consistency problem, it is sufficient to show that the latter is NP-complete. However, it is an equivalent formulation of the QCIRC problem [START_REF] Grünewald | Consistency of the QNet algorithm for generating planar split networks from weighted quartets[END_REF] , which is NPcomplete, by reduction from Betweenness. We recall that the QCIRC problem takes as input a set Q of quartets on a set X of taxa, and asks whether there exists an order σ on X such that for each quartet ab|cd ∈ Q, there exists a split A| Ā, where A is an interval of σ, such that a, b ∈ A and c, d ∈ Ā (or a, b ∈ Ā and c, d ∈ A). Considering that σ is the order of the leaves around the cycle of a simple level-1 network (starting from any point, and turning clockwise, for example), it is straightforward to see that the problem is strictly equivalent to Simple Level-1 Quartet Consistency.

Finding the blobs from the quartets

We now focus on the Level-k Quartet Consistency problem when the input is a dense quartet set Q, i.e. when Q contains at least one quartet on every set of four leaves. In this section, we show how to find the blobs of an unrooted phylogenetic network N consistent with Q. To this purpose, we will introduce the concept of SN-split, which is the unrooted analogue of SN-set [START_REF] Jansson | Inferring a level-1 phylogenetic network from a dense set of rooted triplets[END_REF][START_REF] To | Level-k phylogenetic networks are constructable from a dense triplet set in polynomial time[END_REF] .

Note that thanks to Lemma 2, if we know that an unrooted level-1 network is consistent with a quartet set Q, then there also exists a simple unrooted level-1 network N ′ , which is more parsimonious in terms of edges and also contains Q. However, this simple network N ′ is biologically less interesting, as it does not optimize the quantity |Q(N ′ ) -Q|, i.e. the number of quartets which could be considered "false positive" as they are consistent with N ′ , but not present in the input set Q. This explains why in practice we will first try to deduce from Q the blobs of the network to reconstruct, and then focus on reconstructing each blob of the level-1 network if possible.

Quartets and unrooted phylogenetic networks 13 6.1. Building the SN-splits Definition 9. Let Q be a set of quartets on a set X of taxa, A ⊆ X. A split A| Ā of the taxa is an SN-split of Q if it is either a trivial split, or it satisfies the following property: for any x, y ∈ A, z, t ∈ Ā, the only quartet on {x, y, z, t} in Q, if there is any, is xy|zt.

This definition of SN-split is similar to a definition of SN-sets [START_REF] To | Level-k phylogenetic networks are constructable from a dense triplet set in polynomial time[END_REF] . The original SN-set definition [START_REF] Jansson | Inferring a level-1 phylogenetic network from a dense set of rooted triplets[END_REF] can also be adapted to define SN-splits in the unrooted context as the closure of some set completion operation. However we do not describe it, as it is more complex than the one used here.

We now give an important property of SN-splits before describing an approach to efficiently compute them. Proposition 3. For a dense set Q of quartets, the set of SN-splits of Q is a compatible split system.

Proof: We consider two SN-splits

S 1 = A 1 |A ′ 1 and S 2 = A 2 |A ′ 2 .

Suppose by contradiction that none of the four intersections

A 1 ∩ A 2 , A 1 ∩ A ′ 2 , A ′ 1 ∩ A 2 and A ′ 1 ∩ A ′ 2 is empty. Then ∃a ∈ A 1 ∩ A 2 , b ∈ A 1 ∩ A ′ 2 , c ∈ A ′ 1 ∩ A 2 and d ∈ A ′ 1 ∩ A ′ 2 .
As Q is dense, it must contain a quartet on {a, b, c, d}. As S 1 is an SN-split, a, b ∈ A 1 and c, d ∈ Ā1 , this quartet should be ab|cd. But as S 2 is also an SN-split, a, c ∈ A 2 and b, d ∈ Ā2 , this quartet should be ac|bd: this contradicts the definition of an SN-split.

We recall the classical property that a compatible split system can be represented by an unrooted tree, which we call the unrooted SN-tree of a dense quartet set, whose set of edges is bijectively labeled by the set of SN-splits, as illustrated in Fig. 7(ii). We now show how to build this unrooted SN-tree in O(n 4 ) time.

(i) (ii) Fig. 7. An unrooted level-2 network N (i) and the SN-tree of its quartet set Q(N ) (ii), where we label by the leaf set A the edge corresponding to the SN-split A| Ā.

Proposition 4. For a dense set Q of quartets, there are O(n) SN-splits, and the unrooted SN-tree can be reconstructed in O(n 4 ) time.

Proof: Proposition 3 implies that the number of SN-splits is linear in the size of X.

The algorithm to reconstruct the unrooted SN-tree works as follows. We first partition the input set Q into a set Q 1 where there is exactly one quartet on each set of four leaves, and a set of remaining quartets Q 2 . Then, using the "Q * algorithm 34 ", we reconstruct from Q 1 an unrooted tree T * , not necessarily binary, whose leaves are labeled by X, which satisfies the following property:

Q(T * ) ⊆ Q 1 and Q(T * ) is of maximum size.
Finally, for each remaining quartet

q ∈ Q ′ = Q 2 ∪ (Q 1 -Q(T * )
), if q is not consistent with T * , then we modify the tree T * in the following way, to finally obtain an unrooted tree T ′ * .

Let {a, b, c, d} be the set of leaves of q, ab|cd be the quartet on {a, b, c, d} consistent with T * , u be the intersection vertex of paths ab, ac and bd, and v be the intersection vertex of paths cd, ca and db. Then contract all vertices in the path between u and v.

We can perform this step efficiently in total O(n 4 ) time in the following way: after a O(n) preprocessing, it is possible to decide in constant time, for each of the O(n 4 ) quartets of Q ′ , whether it is consistent with T * . The trick is to use constant time lowest common ancestor queries [START_REF] Harel | Fast algorithms for finding nearest common ancestors[END_REF] in a rooted version of T * . For each of the O(n) edge contractions in the tree T * , it takes O(n) time to recompute a rooted version of the tree and the data structure for lowest common ancestors queries. Hence, the total time complexity is O(n 4 + n 2 ) = O(n 4 ).

It remains to prove that the algorithm is correct, i.e. that the T ′ * tree obtained in the end is the SN-tree of Q.

Consider an edge e of T ′ * which partitions the taxa of X into A and Ā. As

Q(T ′ * ) ⊆ Q(T * ) ⊆ Q 1 ⊆ Q, ∀a, b ∈ A, b, c ∈ Ā, ab|cd ∈ Q.
Furthermore, suppose by contradiction that q 1 = ac|bd ∈ Q or q 2 = ad|bc ∈ Q. As neither q 1 nor q 2 are consistent with T * , e would have been contracted during the algorithm: impossible as e is an edge of T ′ * , so A| Ā is an SN-split of Q.

Conversely, given an SN-split

A| Ā of Q, ∀a, b ∈ A, c, d ∈ Ā, ab|cd ∈ Q, ac|bd ∈ Q and ad|bc ∈ Q so ab|cd ∈ Q(T *
), so T * contains an edge e which separates A from Ā. Suppose by contradiction that this edge is contracted by the algorithm and is no more present in T ′ * . Then there exists a set {a, b, c, d} of four leaves such that a, b ∈ A, c, d ∈ Ā, and Q contains a quartet on {a, b, c, d} which is not consistent with T * . As A| Ā is an SN-split, this is impossible, so there exists an edge of T ′ * which separates A from Ā.

Finally, the splits of T ′ * are exactly the SN-sets of Q, so T ′ * is the SN-tree of Q.

As a corollary, the set of all SN-splits of a dense quartet set Q can be computed in O(n 4 ) time. Note that this time is optimal when Q has at least one non-trivial SN-split A| Ā: in this case, |A| > 1 and | Ā| > 1, so, to ensure that A| Ā is indeed an SN-split of Q, it must be checked that none of the O(n 4 ) quartets of type ab|cd (with a, c ∈ A and b, d ∈ Ā) belongs to Q.

Quartets and unrooted phylogenetic networks 15

The link between blobs and SN-splits

We now prove two lemmas before showing the link between the SN-splits of Q and the blobs of N . Proof: Suppose this property is false, and let A| Ā be an SN-split of Q such that for each blob B in N , E(B) cannot be partitioned into two disjoint sets E A and E Ā such that A = e∈EA L B (e) and Ā = e∈E Ā L B (e), i.e. there exists a cut-edge e ∈ E(B) such that neither L B (e) ⊆ A nor L B (e) ⊆ Ā.

Let B 1 and e 1 be respectively a blob and an edge of N such that A ⊆ L B1 (e 1 ), and L B1 (e 1 ) is minimal for inclusion. The existence of such elements is guaranteed by the fact that the incident edge e x of any leaf x ∈ Ā satisfies A ⊆ L {x} (e x ). We call v the vertex incident of e 1 not in B 1 , and call B 2 the blob containing v, as shown in Fig. 8.

As stated in the beginning of the proof, there exists a cut-edge e 2 ∈ E(B 2 ) such that neither L B2 (e 2 ) ⊆ A nor L B2 (e 2 ) ⊆ Ā, so there exist a 2 ∈ A ∩ L B2 (e 2 ) and x 2 ∈ Ā ∩ L B2 (e 2 ). As A ⊆ L B1 (e 1 ), we know that no leaf of A is contained in L B2 (e 1 ), so L B2 (e 1 ) ⊆ Ā, therefore e 1 = e 2 , and there exists x 1 ∈ Ā ∩ L B2 (e 1 ).

Let us consider the edges of E(B 2 ) other than e 1 and e 2 (there is at least one). If ∀e ∈ E(B 2 ) -{e 1 , e 2 }, L B2 (e) ⊆ Ā, then e 2 and B 2 also satisfy A ⊆ L B2 (e 2 ) and L B2 (e 2 )

L B1 (e 1 ), which contradicts the minimality of L B1 (e 1 ). Otherwise, there exists e Proof: The blob B is bridgeless, and the vertices of N have maximum degree 3, so B contains no articulation vertex, so for any two pairs of distinct vertices {x, y} and {z, t} of B, by Menger's Theorem, there exists at least two vertex-disjoint paths in B between {x, y} and {z, t}.

′ 2 ∈ E(B 2 ) -{e 1 , e 2 }, a 1 ∈ L B2 (e ′ 2 ) ∩ A. Then, edge e 2 implies that x 1 a 1 |x 2 a 2 ∈ Q(N ), and x 1 x 2 |a 1 a 2 ∈ Q(N ) ⊇ Q, which contradicts the fact that A| Ā is an SN-split of Q.
Let us call respectively a ′ , b ′ , c ′ and d ′ the vertices of B adjacent to e 1 , e 2 , e 3 and e 4 . By Menger's Theorem, there exist two vertex-disjoint paths P 1 and P 2 in B between {a ′ , b ′ } and {c ′ , d ′ }.

If P 1 is a path between a ′ and c ′ and P 2 is a path between b ′ and d ′ , then we apply Menger's Theorem in B between {a ′ , c ′ } and {b ′ , d ′ } and thus find two quartets on leaves {a, b, c, d}.

If P 1 is a path between a ′ and d ′ and P 2 is a path between b ′ and c ′ , then we apply Menger's Theorem in B between {a ′ , d ′ } and {b ′ , c ′ } and thus find two quartets on leaves {a, b, c, d}. Theorem 5. Let N be an unrooted level-k phylogenetic network. Its set of cut-edges is in bijective correspondence with the SN-splits of the set Q(N ).

Proof: For each cut-edge e in N , as Q(N ) is consistent with N , the bipartition of leaves induced by e is clearly an SN-split of Q(N ). Suppose there exists an SN-split A| Ā which is not represented by any cut-edge of N . By Lemma 3, there exists a blob B of N such that E(B) is partitioned into E A and E Ā, where A = e∈EA L B (e) and Ā = e∈E Ā L B (e). As A| Ā is not represented by any cut-edge of N , |E A | ≥ 2 and |E Ā| ≥ 2, so there exist four different cut-edges e 1 , e 2 ∈ E A and e ′ 1 , e ′ 2 ∈ E Ā, and four leaves a 1 and a 2 in A, x 1 and x 2 in Ā, such that a 1 ∈ L B (e 1 ), a 2 ∈ L B (e 2 ), x 1 ∈ L B (e ′ 1 ) and x 2 ∈ L B (e ′ 2 ). Then, by Lemma 4, two different quartets on {a 1 , a 2 , x 1 , x 2 } are consistent with N , which contradicts the fact that A| Ā is an SN-split of Q(N ).

Thanks to this theorem, we can consider the SN-tree of Q(N ) as a summary of N , as both have the same set of cut edges, and only differ in their blobs, which are simple vertices in the SN-tree, and bridgeless components in N . However the structure inside the blobs of N remains unknown, we will now study this structure in case of unrooted level-1 networks.

7. Reconstructing Unrooted Level-1 Networks from Quartets 7.1. From the set of all quartets of a network Given the set of all quartets consistent with an unrooted level-1 network, it is possible to reconstruct it in polynomial time. We first show this for simple level-1 networks, after introducing the quartet ordering graph. This definition is illustrated in Fig. 9(ii). Note that G(Q) is an undirected graph because a and c have a symmetric role in the definition of the edges of E(G(Q)).

(i) (ii) Fig. 9. A simple unrooted level-1 network N (i) and the quartet ordering graphs of his quartets G(Q(N )) (ii).

Lemma 5. For a quartet set Q, we can decide in optimal O(n 4 ) time whether there exists a simple unrooted level-1 network N such that Q = Q(N ), i.e. the set of all quartets consistent with N is exactly Q. Moreover, such a network can be computed in O(n 4 ) time for any positive instance.

Proof: In a simple unrooted level-1 network N , the n leaves hang around one cycle. We label the leaves by [1..n] according to their position along the cycle. Our goal is to find this ordering given Q(N ). Any three leaves a, b and c are consecutive iff there is no other leaf d hanging between a and c on the same side of the cycle as b, which is equivalent to ac|bd ∈ Q for any leaf d of X.

Hence, the quartet ordering graph G(Q(N )) is composed of one cycle of length n as well as isolated vertices, so the ordering of the leaves around the cycle of N corresponds to the ordering of the labels of the cycle {{a, b}, {b, c}} -. . . -{{x, y}, {y, a}} -{{y, a}, {a, b}} of G(Q(N )).

To find this ordering, we build the quartet ordering graph G(Q(N )) in O(n 4 ) (for any set of three leaves {a, b, c} we test in O(n) whether an edge should be added between {a, b} and {b, c}). Then we extract the ordering in O(n) starting from any edge of G(Q(N )): if we do not obtain a cycle of length n we answer NO. We finally check that the input quartet set Q is indeed equal to Q(N ), otherwise we answer NO. Theorem 6. For a quartet set Q, we can decide in optimal O(n 4 ) time whether there exists an unrooted level-1 network N such that Q = Q(N ), i.e. the set of all quartets consistent with N is exactly Q. Moreover, such a network can be computed in O(n 4 ) time for any positive instance. We now show that as the set of vertices labeled by A is contiguous, then it is possible to transform N into another level-1 network which is still consistent with Q. As shown in Fig. 11(b), we cut the cycle into two different cycles linked by a cut-edge. On one cycle, C A , we hang, in the same order as in C, the cut-edges hanging from C which have a vertex labeled by A, while on the other cycle C Ā, we hang the cut-edges hanging from C which have a vertex labeled by Ā, in the same order as in C. If one of these two cycles has less than four vertices, then we contract it into one vertex, like C Ā in Fig. 11 We can now check that the new network, in which A| Ā is represented by a cutedge, is consistent with Q. Note that the cycle splitting operation does not affect the quartets which contain zero or just one leaf of A, or, symmetrically, of Ā, as the order of the vertices on the cycle has been conserved. For quartets having two leaves a 1 , a 2 in A and two leaves x 1 , x 2 in Ā, we know that they have to be a 1 a 2 |x 1 x 2 as A| Ā is an SN-split. Those quartets are consistent with the network after the cycle splitting operation.

So, finally, after applying to N the cycle splitting operation for each SN-split which is not represented by a cut-edge, we obtain a level-1 network N ′ whose cut-edges correspond bijectively to the SN-splits of Q.

Simple unrooted level-1 networks

Even though we are able to deduce the global structure of a level-1 solution consistent with a dense quartet set Q, if there exists one, the complexity of reconstructing a simple unrooted level-1 network from Q remains unknown. We will give properties indicating that this task may be difficult, as some dense quartet sets lead to solutions with very different structures. This suggests that the density restriction may be too weak to reconstruct unrooted level-1 networks, as it does not necessarily fix the structure of cut-edges around the cycles of the network.

Note that the problem of reconstructing a simple unrooted level-1 network from a quartet set Q is equivalent to the following problem: finding an order σ of the leaves such that for any quartet ab|cd ∈ Q such that σ(a) < σ(b) and σ(c) < σ(d), neither σ(a) < σ(c) < σ(b) < σ(d) nor σ(c) < σ(a) < σ(d) < σ(b). This formulation is similar to the Non-Betweenness problem, which is known to be NP-complete in the general case 36 but whose complexity is unknown in the dense case. Proposition 5. For any two distinct simple unrooted level-1 networks N 1 and N 2 , there exists a dense quartet set

Q such that Q ⊂ Q(N 1 ) and Q ⊂ Q(N 2 ).
Proof: For any set of four leaves {a, b, c, d}, both N 1 and N 2 are consistent with two among the three possible quartets on {a, b, c, d}. Hence, they share at least one common quartet.

It is even possible to build a dense quartet set which is consistent with an exponential number of simple unrooted level-1 networks. Proposition 6. For any integer n ≥ 3, there exists a dense quartet set on 2n leaves which is consistent with 2 n non-isomorphic simple unrooted level-1 networks.

Proof: We consider the set of leaves {x i , i ∈ [1..2n]}. Let us define some leaf pairs P i = {x 2i-1 , x 2i }, and the simple unrooted level-1 network N obtained by hanging the leaves around a cycle in the order x 1 . . . x 2n .

We now consider the following quartet set Q, which is consistent with N . For each set of four leaves a, b, c, d ∈ [1..2n]:

• case 1) if the four leaves belong to different leaf pairs P i , say that a < b < c < d, we add ab|cd and bc|ad to Q. • case 2) if exactly two leaves (say a and b) belong to a same leaf pair P i , we add ab|cd to Q. • case 3) otherwise, two leaves (say a and b) belong to a leaf pair P i and 2 others (c and d) belong to a pair P j with i < j, then we add ab|cd to Q.

Note that in this construction, two leaves belonging to a same leaf pair P i have a symmetric position in the quartet added to Q. Hence, any other network obtained

Quartets and unrooted phylogenetic networks 21 by hanging the leaves in an order equal to the one of N , up to transpositions inside the leaf pairs P i , is still consistent with Q. As there are n leaf pairs P i , there are n possible transpositions, thus 2 n simple unrooted level-1 networks consistent with Q.

To supplement these results, we have tried an approach based on "obstructions" to decide whether a dense quartet set Q is consistent with a simple level-1 network: this consists in identifying a finite size set of quartet sets of finite size (the obstructions) such that Q is consistent with a simple level-1 network if and only if it does not contain any of those obstructions. We have enumerated all 7 "minimally dense" quartet sets on five leaves (i.e. quartet sets with exactly one quartet for each set of four leaves) and have observed that each one is consistent with at least one simple unrooted level-1 network. Hence, looking for obstructions of size 5, it is necessary to consider quartet sets with at least one quartet with two conflicting resolutions.

Open Problems

Problems about quartets and unrooted phylogenetic networks are of interest from a graph-theoretical point of view, because they show more symmetry than triplets, deal with undirected graphs, thus seem to be more directly related to classical problems in graph theory, which could in turn be a way to understand better the combinatorics of triplets and rooted phylogenetic networks. The time complexity of computing the set of all quartets consistent with an unrooted level-k network may be improved with appropriate preprocessing, it should be possible to get an optimal O(n 4 ) bound.

The most puzzling open problem about unrooted phylogenetic networks and quartets is whether it is possible to reconstruct a simple unrooted level-1 network from a dense quartet set. This problem is similar to the Non-Betweenness problem with a dense set of constraints, whose complexity is also unknown. Finding a dense quartet set which is consistent with a unique unrooted levelk network, for each k, could lead, like for rooted level-k networks and triplets [START_REF] Van Iersel | Uniqueness, intractability and exact algorithms: reflections on level-k phylogenetic networks[END_REF] , to an NP-completeness proof of the Level-k Quartet Consistency problem, for k > 1. Also, the approach to know how to partition a dense triplet set into different blocks of the level-k network to reconstruct [START_REF] To | Level-k phylogenetic networks are constructable from a dense triplet set in polynomial time[END_REF] does not directly translate to the quartet context. Hence, the strategy needs to be adapted or changed more deeply in order to find a polynomial time algorithm to solve the Level-k Quartet Consistency problem, for a fixed k and a dense quartet set. The same applies for simple unrooted level-k networks, where the reconstruction algorithms for triplets in the rooted case cannot be adapted.

Finally, results on the structure of rooted level-k phylogenetic networks 37 hold for unrooted networks, which can also be decomposed as unrooted trees of unrooted level-k generators, defined as 3-regular biconnected multigraphs with 2k-2 vertices. As generators seem a promising approach to finding a fixed-parameter algorithm for rooted level-k network reconstruction from a dense triplet set [START_REF] Kelk | On the elusiveness of clusters[END_REF] , the same question is open for unrooted level-k network reconstruction from a dense quartet set.

Fig. 2 .

 2 Fig. 2. The quartet ab|cd.

Definition 4 .

 4 A quartet ab|cd is consistent with an unrooted phylogenetic network N if there exist two vertex-disjoint paths in N , one from a to b and the other from c to d. Indeed, Definition 3 trivially implies Definition 4, and the converse is true: as a, b, c and d are leaves, there has to be a path (whose extremities are u and v) not containing a, b, c nor d to join the two disjoint paths ab and cd in the connected graph N .

Quartets and unrooted phylogenetic networks 9 Fig. 4 .

 94 Fig. 4. An unrooted level-2 phylogenetic network N , separated in two networks N A and N Ā by a cut shown in bold edges, representing bipartition A| Ā, for A = {e, f }. Edges of the spanning tree Tu of N A are shown in solid gray lines, and edges of the spanning tree Tv of N Ā in dotted gray lines.

Fig. 6 .

 6 Fig. 6. Bipartitions in an unrooted level-1 network whose leaves are in the order σ = abcdef g around the outer face: {b, c}|{a, d, e, f, g} is represented by edge x and {f, g}|{a, b, c, d, e} is represented by the cut {x 1 , x 2 }.

Definition 10 .Lemma 3 .

 103 For each blob B of an unrooted phylogenetic network N , we define E(B) as the set of cut-edges {e 1 , . . . , e t } having one vertex in B. For any edge e i = b i c i ∈ E(B) where b i ∈ B and c i / ∈ B, we denote by L B (e i ) the set of leaves of the connected component of N -{e i } containing c i . Given an unrooted level-k phylogenetic network N , and a dense quartet set Q consistent with N , then for each SN-split A| Ā of Q, there exists a blob B in N such that E(B) is partitioned into two disjoint sets E A and E Ā such that A = e∈EA L B (e) and Ā = e∈E Ā L B (e).

Fig. 8 .

 8 Fig. 8. An impossible configuration if a 1 , a 2 ∈ A, x 1 , x 2 ∈ Ā, and A| Ā is an SN-split of Q.

Lemma 4 .

 4 Given an unrooted level-k phylogenetic network N , if there exists a blob B, four different edges e 1 , e 2 , e 3 and e 4 ∈ E(B) and four different leaves a ∈ L B (e 1 ), b ∈ L B (e 2 ), c ∈ L B (e 3 ), d ∈ L B (e 4 ), then at least two of the three quartets ab|cd, ac|bd and ad|bc are consistent with N .

Quartets and unrooted phylogenetic networks 17 Definition 11 .

 1711 Given a set Q of quartets, we define the quartet ordering graph as G(Q) = ({{a, b} | a = b ∈ X}, {{{a, b}, {b, c}} | ∀d ∈ X, ac|bd ∈ Q}). For any edge {{a, b}, {b, c}} of this graph, we label it by b.

Quartets and unrooted phylogenetic networks 19 SN

 19 -split of Q.

Fig. 10 .

 10 Fig.10. A configuration which cannot happen in an unrooted level-1 network if a 1 , a 2 ∈ A, x 1 , x 2 ∈ Ā and A| Ā is an SN-split.

Fig. 11 .

 11 Fig.11. The cycle splitting operation : the only cycle of the unrooted level-1 network N whose vertices are labeled, in gray, by both A and Ā (a), can be split into two parts (b) to represent the SN-split A| Ā of Q with a cut-edge, then the cycle C Ā, which has less than four vertices, is contracted (c).

Philippe Gambette, Vincent Berry, Christophe Paul

Philippe Gambette, Vincent Berry, Christophe Paul

Philippe Gambette, Vincent Berry, Christophe Paul

Acknowledgments

We thank Sylvain Guillemot for improving the proof of Lemma 4, and Stéphan Thomassé for pointing out the 2-Disjoint Path Problem. We also thank Steven Kelk and anonymous referees whose comments helped to improve this paper. This work was supported by the French ANR projects ANR-06-BLAN-0148-01 (GRAAL) and ANR-08-EMER-011-01 (PhylARIANE).

Proof: We first build the unrooted SN-tree of Q thanks to Proposition 4. By Theorem 5, the cut-edges of any solution N are in bijective correspondence with the edges of the SN-tree of Q. So, as N has maximum degree three, any vertex of degree δ ≥ 4 in the SN-tree corresponds to a blob B with at least four vertices in N .

Let u be a vertex of degree δ ≥ 4 of the SN-tree, let B(u) be the associated blob So, for each vertex u of degree δ ≥ 4 in the SN-tree, let us call A i | Āi the SN-splits corresponding to the incident edges of u (for i ∈ [1..δ]), such that A x ∩ A y = ∅ for any x, y ∈ δ. We pick one leaf l i ∈ A i for each i ∈ [1..δ], then we build in O(δ 4 ) time the simple unrooted level-1 network consistent with Q |{l1,...,l δ } , thanks to Lemma 5. If this fails for one of the vertices of degree at least four of the SN-tree, then we answer NO. Otherwise we build N by replacing every such vertex in the SN-tree by the reconstructed network for Q |{l1,...,l δ } . We finally check that Q = Q(N ), and answer NO if it is not the case. The overall time complexity of this algorithm is O(n 4 ).

From a dense quartet set

We show that in the case of a dense quartet set consistent with an unrooted level-1 network (i.e. a weaker condition than knowing all the quartets of the network), the SN-splits of Q are still related to the cut-edges of one of the solutions. Lemma 6. If a dense quartet set Q is consistent with an unrooted level-1 network N , then it is consistent with an unrooted level-1 network N ′ whose cut-edges are in bijective correspondence with the SN-splits of Q.

Proof: For each cut-edge e in N , as Q is consistent with N , the bipartition of leaves induced by e clearly is an SN-split of Q. Now suppose there is a non-trivial SN-split A| Ā of Q which does not correspond to any cut-edge in N .

By Lemma 3, we know that there exists a blob C of N (in fact a cycle, as N has level 1) such that E(C) is partitioned into E A and E Ā, where A = e∈EA L C (e) and Ā = e∈E Ā L C (e). We label by X any vertex of C incident to a cut-edge in E X , as shown in gray on Fig. 10.

We prove that the set of vertices labeled by A appears consecutively on C, i.e. the subgraph of C induced by all vertices labeled by A is a connected path. Suppose that it is not the case, then we can find two vertices a ′ 1 and a ′ 2 labeled by A such that on both paths between them in C, there is a vertex labeled by Ā (called x ′ 1 and x ′ 2 respectively), as illustrated in Fig. 10. We call e 1 , e 2 , e ′ 1 and e ′ 2 the cut-edges incident respectively to a ′ 1 , a ′ 2 , x ′ 1 and x ′ 2 . So there exist two leaves a 1 , a 2 ∈ A, x 1 , x 2 ∈ Ā such that a 1 ∈ L C (e 1 ), a 2 ∈ L C (e 2 ), x 1 ∈ L C (e ′ 1 ) and x 2 ∈ L C (e ′ 2 ). This is impossible because in this case, a 1 a 2 |x 1 x 2 does not belong to Q, so A| Ā is not an


Jérôme Velut

Pierre-Axel Lentz

Dominique Boulmier

Jean-Louis Coatrieux

Christine Toumoulin

Assessment of qualitative and quantitative features in coronary artery MRA Évaluation de caractéristiques qualitatives et quantitatives en angiographie IRM des artères coronaires

Keywords: Coronary artery, MRI, Labelling, Extraction Mots-clés: Artères coronaires, IRM, étiquetage, extraction

In this paper, an analysis of the coronary trees using Magnetic Resonance Angiography (MRA) is performed. The objective is to estimate how much MRA is capable to provide insights into the vascular network. A qualitative exploration of the MRA volumes with anatomical labelling by experts is first performed, Quantitative vessel features are then manually extracted providing a ground truth which is further compared to a semi-automatic extraction. This evaluation is carried out on 10 datasets of the SSFP MRA sequence and allows getting a more precise view on the current state-of-theart as well as on future achievements to be done.

Résumé

Nous proposons une analyse des artères coronaires en angiographie IRM. L'objectif est d'estimer la profondeur à laquelle l'angio-IRM peut conduire dans un réseau vasculaire coronaire. Une exploration qualitative est décrite

Introduction

According to the recent heart disease and stroke statistics update, "death rates from cardiovascular disease (CVD) have declined, yet the burden of disease remains high" [START_REF] Lloyd-Jones | Heart disease and stroke statistics -2009 update : a report from the American Heart Association Statistics Committee and Stroke Statistics Subcommittee[END_REF]. Efforts made until now have proven profitable for western countries, where CVD are known as the leading cause of death. However, an earlier and better diagnostic of coronary artery diseases (CAD) based on the advances made in imaging modalities leads to a significant decrease of mortality [START_REF] Bi | Coronary arteries at 3.0 T : Contrast-enhanced magnetization-prepared three-dimensional breathhold MR angiography[END_REF][START_REF] Renard | Coronary artery extraction and analysis for detection of soft plaques in MDCT images[END_REF]. Moreover, new therapies that rely on cardiac veins extraction, like biventricular pacing, known as cardiac resynchronization therapy (CRT), open also new perspectives for patient care [START_REF] Daubert | Cardiac resynchronisation therapy in heart failure : Current status[END_REF]. In both cases, imaging sources play an important role as it enables to detect and characterize potential pathological patterns and to elaborate sound planning for therapy and efficient patient followup [START_REF] Rioual | MSCT labelling for pre-operative planning in cardiac resynchronization therapy[END_REF]. They provide relevant anatomical knowledge of the human heart vasculatures (either morphometric [START_REF] Dodge | Intrathoracic spatial location of specified coronary segments on the normal human heart. Applications in quantitative arteriography, assessment of regional risk and contraction, and anatomic display[END_REF][START_REF] Dodge | Lumen diameter of normal human coronary arteries. Influence of age, sex, anatomic variation, and left ventricular hypertrophy or dilation[END_REF], structural [START_REF] Chalopin | Modeling the 3D coronary tree for labeling purposes[END_REF][START_REF] Garreau | A knowledgebased approach for 3-D reconstruction and labeling of vascular networks from biplane angiographic projections[END_REF] or both [START_REF] Lorenz | A comprehensive shape model of the heart[END_REF]) which can be confronted to patient-specific data in a therapeutic or surgical decisional process. Despite the high resolution of the X-Ray angiography, the gold standard for coronary analysis, and the many attempts in reconstruction from few views [START_REF] Bousse | Motion Compensated Tomography Reconstruction of Coronary Arteries in Rotational[END_REF][START_REF] Zhou | A blob-based tomographic reconstruction of 3D coronary trees from rotational x-ray angiography[END_REF][START_REF] Schoonenberg | Three-Dimensional Coronary Visualization, Part 2 : 3D Reconstruction[END_REF], other techniques are increasingly being used in clinical protocols : Multidetector Computed Tomography (MDCT), Electron Beam Computed Tomography (EBCT) and Magnetic Resonance Angiography (MRA) [START_REF] De Veire | Magnetic resonance imaging and computed tomography in assessing cardiac veins and scar tissue[END_REF][START_REF] Kim | Coronary magnetic resonance angiography for the detection of coronary stenoses[END_REF].

MRA is of interest for several reasons : [START_REF] Lloyd-Jones | Heart disease and stroke statistics -2009 update : a report from the American Heart Association Statistics Committee and Stroke Statistics Subcommittee[END_REF] no ionizing radiation is used, (2) improved assessment of aneurysms and CAD are expected, and (3) MR imaging provides acquisition sequences that allow focusing on different anatomical or physiological characteristics. Recent works show that MRA could discriminate significant (> 50%) from non-significant stenosis [START_REF] Stuber | Coronary magnetic resonance angiography[END_REF] and is a reliable imaging method for anatomy assessment before a surgical intervention [START_REF] Sakuma | Assessment of coronary arteries with total study time of less than 30 minutes by using whole-heart coronary MR angiography[END_REF]. However, they do not report yet precise quantitative features.

The state-of-art of MR sequences used for clinical studies are those based on steady-state free precession (SSFP) technique [START_REF] Giorgi | Improved Visualization of Coronary Arteries Using a New Three-Dimensional Submillimeter MR Coronary Angiography Sequence with Balanced Gradients[END_REF][START_REF] Ozgun | Comparison of 3D Segmented Gradient-Echo and Steady-State Free Precession Coronary MRI Sequences in Patients with Coronary Artery Disease[END_REF]. Whole-heart acquisition makes the image analysis less operator dependent by including the vessels up to distal vascular parts in a single volume. Used in conjonction with navigators, it is possible to image a whole heart without β-blockers, without contrast agent and in a free-breathing fashion. These points are of importance when diagnostic is performed on symptomatic patients.

A meta-analysis of CAD diagnostic performance of coronary MRA [START_REF] Danias | Diagnostic performance of coronary magnetic resonance angiography as compared against conventional X-ray angiography : a meta-analysis[END_REF] reports a moderately high sensitivity for detecting proximal stenoses but notes that distal segments can not be evaluated. The clinical study conducted in [START_REF] Beerbaum | Coronary anomalies assessed by whole-heart isotropic 3D magnetic resonance imaging for cardiac morphology in congenital heart disease[END_REF] on congenital heart disease diagnostic based on SSFP MR Imaging focuses therefore on proximal segments. This paper is aimed at answering two questions : [START_REF] Lloyd-Jones | Heart disease and stroke statistics -2009 update : a report from the American Heart Association Statistics Committee and Stroke Statistics Subcommittee[END_REF] what can be expected in terms of visual exploration and manual extraction of vascular structures by expert ? [START_REF] Bi | Coronary arteries at 3.0 T : Contrast-enhanced magnetization-prepared three-dimensional breathhold MR angiography[END_REF] what difficulties and performance can be anticipated for semiautomatic quantitation ? 10 whole-heart coronary artery SSFP MRA have been studied. The datasets are first described (2) and then qualitatively analysed (Section 3.2).

Furthermore, a quantitative study, expert-based, is carried out in order to assess patient and inter-patient the variability of different features (Section 3.3).

A preliminary comparison of the manual extractions with an existing semiautomatic centreline tracking algorithm is then presented in Section 4 and allows concluding on factual benefits and future challenge of whole-heart coronary artery imaging.

Technical and anatomical background

Datasets

The 10 datasets were acquired on a 1.5T system (Philips Intera and Achieva) using a steady-state free precession (SSFP) MR sequence [START_REF] Giorgi | Improved Visualization of Coronary Arteries Using a New Three-Dimensional Submillimeter MR Coronary Angiography Sequence with Balanced Gradients[END_REF], at end-diastolic phase without contrast agent. The MR sequence parameters are summarized in table 1. Table 2 shows different characteristics of the MRA volumes. The field of view corresponds to the whole acquired volume, while the VOI is the volume of the bounding box comprising the visible coronary vasculature. The intensity range is measured inside the VOI. All the volume have the same in-plane resolution, being 512 × 512 isotropic pixels of size 0.59 mm whereas the interslice distance and the number of slices vary.

Anatomical considerations

In the following and for the whole paper, anatomical nomenclature is based on the classification established by the American Heart Association [START_REF] Scanlon | ACC/AHA guidelines for coronary angiography. A report of the American College of Cardiology/American Heart Association Task Force on practice guidelines (Committee on Coronary Angiography). Developed in collaboration with the Society for Cardiac Angiography and Interventions[END_REF]. Figure 1 shows the anatomical segments and their corresponding names depicted in tables 3 and 4. For clarity purpose, and because some distal segments have never been evaluated in the litterature, we propose readerfriendly acronyms in the remaining of the paper.

Labelization and manual extraction

Existing studies, even recent, on whole-heart coronary MRA lack of indepth qualitative and quantitative analysis. In this section, we present the result of the manual extraction of the coronary arterial trees from the 10 datasets. The anatomical nomenclature and the labelling performed in colla- boration with a radiologist and a cardiologist are confronted. Finally, some basic vessel features (length, diameter and image intensity) are quantified and results discussed. Refining The decimated curve is then resampled along a cardinal spline but with a 1 mm sampling step.

Figure 2 shows the ten arterial trees obtained from this interactive procedure.

By slicing the MR dataset orthogonally to the curves, it is possible to carry out a straightened reformation of the arteries. A volume rendering of such a reformation is depicted in figure 3. This view is based on the Straightened Curved Planar Reformation (Sa-CPR) described in [START_REF] Kanitsar | CPR -curved planar reformation[END_REF].

Centreline correction

A centreline correction, similar to the one presented in [START_REF] Schaap | Standardized evaluation methodology and reference database for evaluating coronary artery centerline extraction algorithms[END_REF], is performed to ensure an accurate localization of the vessel centre. The main drawback of an axial-exclusive slice pointing is that the center of a vessel is not reliabily located when the vessel runs tangentially to the axial plane. It may lead to an inaccurate location of the centreline for a non-negligible length of coronary arteries (eg RCA 3rd segment, posterio-and atrio-ventricular segments). To deal with this issue, the consideration that slicing axially the Sa-CPR is equivalent to slicing orthogonally along the vessel allows us to point trustfully the center of the vessel at each Sa-CPR axial slice. A corrected centerline is then produced, as shown in figure 4.

Radius estimation

This corrected centreline is used as a reference for the local radius measurement along the vessels. This radius is estimated on each Sa-CPR axial slice by pointing the upper north point of the vessel. Figure 5 shows a reconstruction of the vascular structure through a radial-variant tube centered on the corrected centreline. modality for quantification purposes.

Coronary arterial tree labelling

RCA(p) E E E E E E E E E E RCA(m) E E E E E E E E E E RCA(d) E E E E E E E E E E RPD E E E . E E E . E . RPA E E E E E E E . E E RPL(1

Quantitative analysis

The characteristics presented in this work are : (i) the length of each coronary arterial segments, as well as their estimated radii, according to the manually extracted and corrected centreline ; (ii) the image intensity probed along the corrected centreline.

Extracted length

Figure 9 shows the mean length of each coronary artery segment. No surprisingly, the proximal to medial segments have a length close to those reported in [START_REF] Christids | Anatomie des artères coronaires du coeur[END_REF] when they exist. The relative error is due to the anatomical variations between subjects. For distal segments, no reliable comparison can be made due to the fact that they are far to be entirely extracted.

Dataset 1 2 3 4 5 6 7 8 9 10

LM E E E E E E E E E E LAD(p) E E E E E E E E E E LAD(m) . E E E E E E E E E LAD(d) . E E . E E E . . E DIAG(1) E E E . E E E E . . DIAG (

Estimated radii

As the radius is expected to decrease along a vessel, the result is presented through a simple linear regression.

Intensity measurement

An analysis of the intensity profiles along the coronary arteries has been performed. Figure 11 shows such a profile along the RCA of the volume #1.

It can be observed that local variations are important. The simple regression line is also drawn on the chart. The results for each segment is displayed (slope a, y-intercept b, absolute correlation coefficient |r| and mean) in table 8.

Although the slope of the regression lines are closed to zero reflecting an almost-constant intensity at centreline, the correlation coefficients show in most cases significant variations.

Indeed, not only the intensity is highly-varying along the vessels but as the figure 12 shows, major differences appear between different datasets, with mean intensities along the whole trees ranging from 186 to 469. It emphases the need for normalized intensities, such as it was proposed in [START_REF] Weber | Free-breathing, three-dimensional coronary artery magnetic resonance angiography : comparison of sequences[END_REF].

Discussion

The qualitative analysis of coronary arterial tree extraction using wholeheart SSFP MRA points out that the main segments, up to distal parts, are unambiguously localized and labeled. Proximal diagonal segments have been also identified on seven of the 10 datasets. A number of marginal and septal segments were extracted. In the next section, we apply an existing semi-automatic method and compare the results with those obtained manually.

Preliminar testing of a semi-automatic segmentation method

State-of-the art methods

Most basic tools designed so far have been mainly applied to X-ray modalities and are based on intensity thresholding [START_REF] Schoepf | CT of the heart : principles and applications[END_REF]. They are daily used as part of scanner marketed software packages including 3D volume rendering functionnalities. The vessel intensities being highly variable inside and along a vessel, thresholding can not be considered as reliable. Smarter segmentation methods are based on region growing (RG) [START_REF] Boskamp | New vessel analysis tool for morphometric quantification and visualization of vessels in CT and MR imaging data sets[END_REF]. For the same reasons of heterogeneity, a RG algorithm cannot extract the whole vascular tree without many expert interactions. Other methods rely on the tube-like structure as a prior knowledge. A joint fast-marching/level set method is proposed in [START_REF] Cohen | Segmentation of 3D tubular objects with adaptive front propagation and minimal tree extraction for 3D medical imaging[END_REF] which offers the capability to build a vascular tree thanks to a minimal path technique. In [START_REF] Boldak | 3D segmentation and characterization of lower limb vessels in multi-slice computed tomography[END_REF], 3D geometrical moments were used to get the center and the principal axis of a vessel that feeds a spatial tracking algorithm. Geometrical moments and level-set methods have been combined

in [START_REF] Bousse | Coronary extraction and characterization in multi-detector computed tomography[END_REF]. An artificial life-based method is also reported in [START_REF] Mcintosh | Vessel Crawlers : 3D Physically-based Deformable Organisms for Vasculature Segmentation and Analysis[END_REF] and a mathematical morphology approach is described in [START_REF] Bouraoui | Fully automatic 3D segmentation of coronary arteries based on mathematical morphology[END_REF]. One can refer to [START_REF] Lesage | A review of 3D vessel lumen segmentation techniques : Models, features and extraction schemes[END_REF] for a review on vessel extraction methods.

Although these segmentation methods show promising results, they have been mainly tested on X-Ray angiography or MDCT modalities. In the following, we assess a modified geometrical moment-based tracking method integrating multiple hypothesis testing and regularization (MH-GMT) [START_REF] Velut | 3D coronary structure tracking algorithm with regularization and multiple hypotheses in MRI[END_REF] and we compare its performance to the manual extraction carried out above, considered here as ground truth.

Extraction results

Briefly speaking (more algorithmic details can be found in [START_REF] Velut | 3D coronary structure tracking algorithm with regularization and multiple hypotheses in MRI[END_REF]), the geometrical moment-based tracking methods are designed to extract a 3D curve from a volume, following a particular feature. As geometrical moment are able to compute the local orientation of a cylinder from image intensities, it is well-suited for vessel centreline extraction. The tracking starts from a seed point and iteratively builds a curve from the estimated orientations until a stopping criterion is reached. The idea behind the multiple hypotheses framework is to automatically browse the parameters of the algorithm (eg.

moment kernel size, stopping criterion,...) to extract multiple centrelines and then select the best one.

The bunch of candidate centrelines is shown figure 13 for the 10 arterial trees together with the seed point locations. Each centreline is the output of the algorithm for one state of the parameter set.

Distance definition for quality measurement

In the following, we use the concepts of overdetection and underdetection to assess the quality of the extracted arterial tree. Let T S be the tree obtained from MH-GMT and T R the manually extracted one. If p is a point from T S and q a point from T R , we define the overdetection distance as :

∀p ∈ T S , OD p = min q∈T R (||pq||) (1)
This measure allows detecting points that belong to the semi-automatically extracted tree T S but do not belong to the reference tree. Figure 14 The symmetric measure of ( 1) is the underdetection distance, able to detect vessels from T R that cannot be find in T S and defined as :

∀q ∈ T R , U D q = min p∈T S (||pq||) (2)
The visualization of U D for each reference point (figure 14(b) underlines the missing segments in T S . However, the histogram (figure 14(d)) shows that 77% of the points from T R are less than 2mm far from T S . 15% of points are farther than 5mm, which may be lowered by adding few seed points.

These results are summarized in table 9 for each dataset, where over-and underdetection are presented as the number of points with OD and U D less than 2mm in percent. The rates of correspondance are relatively high between the semi-automatic extraction and the ground truth. It can be seen that the number of seed points remains reasonable with respect to the interaction time required to the user. The computation time is also compatible with the clinical constraints. Tab. 9: Summary of the semi-automatic coronary artery centreline extraction.

Conclusion

Cardiac imaging is now able to provide 3D static data sets but also 3D We have shown that an unambiguous labeling of large parts of coronary arteries can be achieved. To our knowledge, such a proof of the potential of MR imaging for coronary analysis is lacking at this depth. A global coronary anatomy can thus be reconstructed, bringing useful information for interventional planning. However, the coronary tree is built from many points manually placed in the volume, requiring too much interaction and time for a clinical use.

A semi-automatic extraction method has therefore been applied. It is based on geometrical moments and outputs the central axes of the vessels.

Results are promising as the labeled vessels are retrieved thanks to only 13 seed points on average. Therefore, for qualitative applications on coronary anatomy, MR leads to a performance comparable to MDCT [START_REF] Larralde | Evaluation of a 3D Segmentation Software for the Coronary Characterization in Multi-slice Computed Tomography[END_REF] without using any contrast product.

Improvements however are necessary. They will come first from the MR imaging (new acquisition sequences, contrast agents, etc.) where continuous advances are observed. They will also come from advances of detection and segmentation algorithms with lower time computation, higher robustness and reduced interaction. The quantification of patient-specific coronary features is required to reach a better diagnosis and to help in planning the interventions such as CRT as far as the the coronary sinus and the whole left venous tree is also extracted. The competition between imaging modalities and especially MDCT and MRA is a factor of progress that will help in such objectives.

Acknowledgements

The research leading to these results has received funding from the European Community's Seventh Framework Programme (FP7/2007-2013) under grant agreement n˚224495 (euHeart project). We are also grateful toward Olivier Ecabert and Juergen Weese from Philips Research Aachen for providing the MRA data sets.

3. 1 .

 1 Coronary arterial trees extraction procedure 3.1.1. Rough manual centreline extraction The manual extractions have been performed by interactively pointing inside the vessels on the axial slices of the volumes. The resulting curves having a non-uniform sampling, a slight smoothing was applied based on a decimation/refinement procedure. Decimation The manually-extracted curves are evenly resampled along a cardinal spline interpolating the initial point set. Sampling step is 3 mm long.

Figures 6 -

 6 Figures 6-8 display several labeled slices (a) from the coronary artery MRA dataset #2. An approximate location of the slice plane is given on a schematic view of the heart (b). The arterial segments that can be seen on the slices are represented as sharp on the coronary artery map, the non visible vessels being blurred (c). Figure2illustrates the manual extraction of the coronary arteries from the ten datasets. The extracted segments are reported in tables 5 and 6. This analysis demonstrates the merits of MR imaging for coronary arteries. The whole proximal and medial segments have been extracted, and even the distal locations for the most part of the datasets. However, whereas these merits are obvious in the case of a global coronary anatomy exploration, we are interested in the following in assessing the MR

Figure 10

 10 depicts the manually-pointed data and the corresponding regression line. The regression slope is negative (-4.33E -03), that confirms the general decreasing trend expected along a vessel. Results over the whole database and for each segment are summarized in table 7. The whole database presents a slowly-decreasing radius along the arterial segments, except for CX-2 and LAD-3. The difficulty to reliably point the vessel wall can explain this low quality radius estimation. Furthermore, the radius is highly varying along the vessels. The absolute Pearson correlation coefficient |r| is adequatly lower than √ 3/2, meaning that the dispersion around the regression line prevents a correct radius prediction. The low MRA vessel contrast and the inherent difficulties to keep a 3D continuity through 2D manual analysis explain the observed errors.

1 . 5 .

 15 This quantitative analysis that aimed to extract the lengths, local radii and local intensities along the arterial centrelines leads to mixed results. The extracted lengths confirm the qualitative analysis with figures closed to anatomical references and variabilities, but the local radius estimations and intensity measurements do not provide enough reliability for diagnosis or interventional planning. Furthermore, the manual extraction of the coronary tree is highly timeconsuming and is not applicable in clinical routine. A reliable estimation of the radius requires to point more than the only upper points of the vessel lumen. These findings support the need for automatic or at least semi-automatic methods. They should avoid intra-and inter-operator biases and fasten the extraction process. The challenging points concern : The low vessel spatial resolution : 4-voxels diameter for proximal main segment, down to 1-voxel diameter for distal segments 2. The high intensity variability along a vessel, making threshold-based method setting tedious 3. The high intensity inter-patient variability 4. the loss of signal due to either pathology or artifacts (motion, susceptibility,...) The proximity of bright structures (veins, ventricles)

  (a) shows the overdetection distance (OD) for each point and the histogram in figure 14(c) points out that the majority of the points are less than 2mm far from the reference. Only 3% of points may correspond to false positive detections.

  image sequences and open new perspectives for diagnosis and image guided interventions. In this context, MR imaging is very attractive and has been widely investigated for coronary vessel analysis. With SSFP MR sequence, a whole heart volume can be acquired in a free breath fashion in less than 15 minutes, thus improving the patients comfort.

Fig. 1 :Fig. 2 :

 12 Fig.1: Coronary artery map as proposed by the AHA[START_REF] Scanlon | ACC/AHA guidelines for coronary angiography. A report of the American College of Cardiology/American Heart Association Task Force on practice guidelines (Committee on Coronary Angiography). Developed in collaboration with the Society for Cardiac Angiography and Interventions[END_REF]. A correspondance between figures and segment names is given in tables 3 and 4.

Fig. 3 :

 3 Fig. 3: Straightened Curved Planar Reformation of the 1st, 2nd and 3rd RCA segments. MIP (Maximum Intensity Projection) visualisation.

Fig. 4 :Fig. 6 : 34 (Fig. 8 :Fig. 9 :Fig. 10 :Fig. 11 :

 4634891011 Fig. 4: Centreline correction process. Corrected vessel centres are pointed slice by slice.

Fig. 12 :

 12 Fig. 12: Mean intensity along the coronary artery centreline for each dataset. Bars are gray-colored according to the intensity.

Fig. 13 :

 13 Fig. 13: Coronal view of the ten arterial tree obtained with MH-GMT method. Red spheres depict the seed points locations.

Fig. 5: Sa-CPR reconstruction of the vascular wall (1st, 2nd and 3rd segments).

Conflit d'intérêt : aucun