Philippe Gambette
email: philippe.gambette@gmail.com

Katharina T Huber
email: katharina.huber@cmp.uea.ac.uk

On Encodings of Phylogenetic Networks of Bounded Level

Keywords: Phylogenetic networks, triplets, clusters, supernetwork, level-1 network, level-k network, weak hierarchy, consistency, metric, indistinguishable

Phylogenetic networks have now joined phylogenetic trees in the center of phylogenetics research. Like phylogenetic trees, such networks canonically induce collections of phylogenetic trees, clusters, and triplets, respectively. Thus it is not surprising that many network approaches aim to reconstruct a phylogenetic network from such collections. Related to the wellstudied perfect phylogeny problem, the following question is of fundamental importance in this context: When does one of the above collections encode (i.e. uniquely describe) the network that induces it? For the large class of level-1 (phylogenetic) networks we characterize those level-1 networks for which an encoding in terms of one (or equivalently all) of the above collections exists. In addition, we show that three known distance measures for comparing phylogenetic networks are in fact metrics on the resulting subclass and give the diameter for two of them. Finally, we investigate the related concept of indistinguishability and also show that many properties enjoyed by level-1 networks are not satisfied by networks of higher level.

Introduction

An improved understanding of the complex processes that drive evolution has lent support to the idea that reticulate evolutionary events, such as lateral gene transfer or hybridization, are more common than originally thought, rendering a phylogenetic tree (essentially a rooted leaf labelled graph-theoretical tree) too simplistic a model to fully understand the complex processes that drive evolution. Reflecting this, phylogenetic networks have now joined phylogenetic trees in the center of phylogenetics research. Influenced by the diversity of questions posed by evolutionary biologists that can be addressed with a phylogenetic network, various alternative definitions of these types of networks have been developed over the years (see e. g. [START_REF] Huson | Phylogenetic Networks[END_REF] for a recent overview). These include split networks [START_REF] Bryant | NeighborNet: An agglomerative method for the construction of phylogenetic networks[END_REF][START_REF] Bandelt | Mitochondrial portraits of human population using median networks[END_REF][START_REF] Holland | Using consensus networks to visualize contradictory evidence for species phylogeny[END_REF] as well as ancestral recombination graphs [START_REF] Song | Constructing minimal ancestral recombination graphs[END_REF], TOM networks [START_REF] Willson | Unique solvability of certain hybrid networks from their distances[END_REF], level-k networks1 with k a non-negative integer that in a some sense captures how complex the network structure is, networks for studying the evolution of polyploid organisms [START_REF] Moulton | Phylogenetic networks from multi-labeled trees[END_REF], tree-child and tree-sibling networks [START_REF] Cardona | A distance metric for a class of tree-sibling phylogenetic networks[END_REF], to name just a few.

Apart from split networks which aim to give an implicit model of evolution and are not the focus of this paper, all other phylogenetic networks mentioned above aim to provide an explicit model of evolution. Although slightly different in detail, they are all based on the concept of a leaf-labelled rooted connected directed acyclic graph (see the next section for a definition). For the convenience of the reader, we depict an example of a phylogenetic network in the form of a level-1 network in Fig. 1(a). Concerning these types of phylogenetic networks, it should be noted that they are closely related to galled trees [START_REF] Wang | Perfect phylogenetic networks with recombination[END_REF][START_REF] Gusfield | Efficient reconstruction of phylogenetic networks with constrained recombination[END_REF] and that, in addition to constituting the first layer of the hierarchy of level-k networks, they also give rise to a large subclass of the class of tree-sibling networks [START_REF] Arenas | Characterization of reticulate networks based on the coalescent[END_REF].

Due to the rich combinatorial structure of phylogenetic networks, different combinatorial objects have been used to reconstruct them from biological data. For a set X of taxa (e.g. species or organisms), these include cluster systems of X, that is, collections of non-empty subsets of X [START_REF] Bandelt | Weak hierarchies associated with similarity measures: an additive clustering technique[END_REF][START_REF] Huson | Summarizing multiple gene trees using cluster networks[END_REF], triplet systems on X, that is, collections of phylogenetic trees with just three leaves which are generally called (rooted) triplets (Jansson and Sung, 2006;[START_REF] To | Level-k phylogenetic network can be constructed from a dense triplet set in polynomial time[END_REF], and tree systems, that is, collections of phylogenetic trees which all have leaf set X [START_REF] Semple | Hybridization networks[END_REF]. The underlying rationale being that any phylogenetic network N induces a hardwired cluster system C(N ), a triplet system R(N ) and a tree system T (N ). Again we defer the precise definitions to later sections of this paper, and remark that for the level-1 network N with leaf set X = {a, b . . . , e} depicted in Fig. 1(a), the cluster system C(N ) is the set x∈X {{x}} ∪ {{a, b}, {c, d}, {b, c, d}, Y, X}, where Y = X -{e}, and the tree system T (N ) consists of the phylogenetic trees depicted in Fig. 1(b) and (c), respectively. Denoting a phylogenetic tree t on x, y, z such that the root of t is the parent vertex of z and the parent vertex of x and y by z|xy (or equivalently by xy|z) then the triplet system R(N ) consists of all triplets of the form e|xy with x, y ∈ Y distinct, plus the triplets a|cd, b|cd, c|ab, a|bc, d|ab and a|bd.

Although undoubtedly highly relevant for phylogenetic network reconstruction, the following fundamental question has however remained largely unanswered so far (the main exception being the case where N is in fact a phylogenetic tree in which case this question is closely related to the well-studied perfect phylogeny problem -see e.g. [START_REF] Grünewald | Identifying and defining trees[END_REF] for a recent overview): When do the systems C(N ), R(N ), or T (N ) induced by a phylogenetic network N encode N , that is, there is no other phylogenetic network N ′ for which the corresponding systems for N and N ′ coincide?

Complementing the insights for when N is a phylogenetic tree alluded to above, answers were recently provided for R(N ) in case N is a very special type of level-k network, k ≥ 2, (van Iersel et al, 2009b) and for T (N ) for the special case that N is a regular network [START_REF] Willson | Regular networks are determined by their trees[END_REF]. Undoubtedly these are important first results. However, there are many types of phylogenetic networks which are encoded by the tree system they induce but which are not regular. Similarly, there are many types of phylogenetic networks which are encoded by the triplet system they induce but they do not belong to that special class of level-k networks considered in van Iersel et al (2009b). An example for both cases is the level-1 network depicted in Fig. 1(a) modified by subdividing the incoming arc of the parent of b by a new vertex v and then adding an arc from v to a new labelled leaf. Although one might be tempted to speculate that all level-1 networks enjoy this property, this is not the case since the level-1 networks depicted in Fig. 1(a) and Fig. 3(b), respectively, induce the same tree system and the same triplet system. The main result of this paper shows that these observations are not a coincidence. More precisely, in Theorem 1 we establish that a level-1 network N is encoded by the triplet system R(N ) (or equivalently by the tree system T (N ) or equivalently the softwired cluster system S(N ) = S(T (N )) := T ∈T (N ) C(T ) which arises in the context of the softwired interpretation of N [START_REF] Huson | Summarizing multiple gene trees using cluster networks[END_REF] and contains C(N )) if and only if, when ignoring directions, N does not contain a cycle of length 4. Consequently the number of non-isomorphic (see below) phylogenetic networks which all induce the same tree system as N (or equivalently the same triplet system or the same cluster system S(N )) grows exponentially in the number of cycles of N of length 4. Furthermore, Theorem 1 implies that three known distance measures for phylogenetic networks are in fact metrics on the resulting subclass of level-1 networks and for two of them we establish their diameter on that class. It is of course highly tempting to speculate that a similar characterization might hold for higher values of k. However as our analysis of level-2 networks shows this is not the case. Moreover, we show that it is possible for a level-2 network to be encoded by some of the above systems without being encoded by the others.

The paper is organized as follows. In the next section, we present the definition of a level-1 network plus surrounding and relevant terminology. In Section 3, we present the definitions of the cluster system C(N ) and the tree system T (N ) induced by a phylogenetic network N . This also completes the definition of the cluster system S(N ) given in the introduction. Subsequent to this, we show that for any level-1 network N , the cluster systems S(N ) and C(N ) are weak hierarchies (Proposition 1) which are well-known objects in cluster analysis. In addition, we show that, in general, this property is not enjoyed by level-k networks with k ≥ 2. In Section 4, we present the definition of the triplet system R(N ) induced by a phylogenetic network N . Subsequent to this, we first investigate the system R(N ) in case N is a structurally very simple level-1 network and then establish that the triplet system induced by a phylogenetic tree T is contained in the triplet system of a level-1 network N if and only if T ∈ T (N ) holds (Proposition 2). In Section 5, we prove our main result (Theorem 1) and, in Section 6, we study the restriction of three known distance measures to the resulting subclass of level-1 networks. In Section 7, we turn our attention to higher level networks and show that an encoding of such a network in terms of one of the above systems does not imply that it is also encoded by the other systems (Proposition 5). In Section 8, we conclude with some general remarks concerning the accurate reconstruction of phylogenetic networks from triplets and phylogenetic trees in general and level-k networks in particular.

To ease the presentation of our results, in all figures the (unique) root of a network is the top vertex and all arcs are directed downwards, away from the root.

Basic terminology and results concerning level-1 networks

In this section we present the definitions of a phylogenetic network and of a level-k network, k ≥ 0. In addition we also provide the basic and relevant terminology surrounding these structures.

Suppose X is a non-empty finite set. For any directed graph G, we denote the vertex set of G by V (G), the set of leaves of G (i. e. the vertices of G with indegree 1 and outdegree 0) by L(G) and the set of arcs of G by A(G). Furthermore, we put V -(G) := V (G)-L(G). The arcs in A(G) whose removal disconnect G in the sense that for any two vertices in the resulting graph there does not exist a (possibly undirected) path between them are called the cutarcs of G. A cut-arc of G that is incident with a leaf of G is called trivial trivial.

A phylogenetic network N on X is a rooted directed acyclic graph (DAG) that satisfies the following additional properties:

(P1) L(N ) = X.
(P2) Exactly one vertex of N , called the root and denoted by ρ N , has indegree 0 and outdegree 2. (P3) All vertices of N that are not contained in L(N ) ∪ {ρ N } are either split vertices, that is, have indegree 1 and outdegree 2 or reticulation vertices, that is, have indegree 2 and outdegree 1.

The set of reticulation vertices of N is denoted by r(N ). A phylogenetic network N with r(N ) = ∅ is called a (rooted) phylogenetic tree (on X). Two phylogenetic networks N and N ′ which both have leaf set X are said to be isomorphic if there exists a bijection from V (N ) to V (N ′ ) which is the identity on X and induces a graph isomorphism between N and N ′ .

To present the definition of a level-k network, we need to introduce some terminology concerning rooted DAGs first. Suppose G is a rooted connected DAG with at least 2 vertices. Then we denote the graph obtained from G by ignoring the directions on G by U (G). If H is a graph with at least 2 vertices then we call H biconnected if H does not contain a vertex whose removal disconnects it. A biconnected component of H is a maximal subgraph of H that is biconnected. If G is a phylogenetic network and B is a rooted sub-DAG such that U (B) is a biconnected component of U (G) then we call B a block.

Following [START_REF] Choy | Computing the maximum agreement of phylogenetic networks[END_REF], we call a phylogenetic network N a level-k (phylogenetic) network for some non-negative integer k if each block of N contains at most k reticulation vertices. The quantity k is sometimes referred to as the level of N . Note that some authors define a level-1 network N to be a phylogenetic network without the above outdegree requirement on the elements in r(N ) (see e.g. Jansson and Sung (2006); [START_REF] Choy | Computing the maximum agreement of phylogenetic networks[END_REF] or the above indegree requirement on the elements in r(N ) (see e. g. [START_REF] Rosselló | All that glisters is not galled[END_REF]). Also the requirement that each block contains at most k reticulation vertices is sometimes replaced for level-1 networks by the requirement that the cycles in U (N ) are node disjoint (see e.g. Jansson et al (2006)). Although in spirit capturing the same idea, the difference between these definitions is that, according to [START_REF] Choy | Computing the maximum agreement of phylogenetic networks[END_REF], the structure depicted in Fig. 2 is a level-1 network whereas according to van Iersel et al (2009a) it is not. See also [START_REF] Rosselló | All that glisters is not galled[END_REF] for more on this.

Fig. 2 Using the definition in [START_REF] Choy | Computing the maximum agreement of phylogenetic networks[END_REF] or in Jansson and Sung (2006), N is a level-1 network. However, using the definition in Jansson et al (2006) or in van Iersel et al (2009a), N is not a level-1 network. In fact, it is not even a phylogenetic network.

Regarding the definition of a level-k network sensu van Iersel et al (2009a), it should be noted that the phylogenetic network depicted in Fig. 3(a) is a level-1 network. However the alternative level-1 network N depicted in Fig. 3(b) is a less parsimonious representation of the same biological information (expressed in terms of the systems T (N ), R(N ), C(N ), and S(N )) than the former in the sense that the arcs in gray are redundant for displaying that information.

To avoid these types of level-1 networks which cannot be encoded by any of the 4 systems of interest in this paper, we follow van Iersel et al (2009b) and require that every block in a level-1 network which is not a cut-arc contains at least 4 vertices. Fig. 3 The level-1 network N depicted in (a) induces and thus represents the same triplet system R(N ), cluster systems C(N ) and S(N ), and tree system T (N ) as the level-1 network N ′ presented in (b). However, N ′ is a less parsimonious representation of those 4 systems.

For k = 1, 2, it was shown in van Iersel et al (2009a) (see also Jansson and Sung (2006) for the case k = 1) that level-k networks can be built up by chaining together structurally very simple level-k networks called simple levelk networks (see also [START_REF] Gambette | The structure of level-k phylogenetic networks[END_REF] for more on this). More precisely, a level-k network N , k ≥ 0, is called simple if every cut-arc of N is a trivial cutarc. For example, the network obtained by first contracting the outgoing arcs of the root of the level-1 network N ′ depicted in Fig. 3(b) and then contracting the incoming arcs of c and d (retaining the label c), is a simple level-1 network on {a, b, c}.

From now on and unless stated otherwise, X is a non-empty finite set and all phylogenetic networks have leaf set X.

3 The systems C(N ), T (N ), and S(N )

In this section, we introduce for a phylogenetic network N the associated systems C(N ), T (N ), and S(N ) already mentioned in the introduction. In addition, we prove that in case N is a level-1 network the associated systems C(N ) and S(N ) are weak hierarchies. We conclude with presenting an example that shows that higher level networks do not enjoy this property in general. We start with some definitions.

Suppose N is a phylogenetic network. Then we say that a vertex a ∈ V (N ) is below a vertex b ∈ V (N ), denoted by a N b, if there exists a path P ba (possibly of length 0) from b to a. In this case, we also say that b is above a. Every vertex v ∈ V (N ) therefore induces a non-empty subset C(v) = C N (v) of X which comprises of all leaves of N below v (see e.g. Semple and Steel (2003, page 51)). We collect the subsets C(v) induced by the vertices v of N this way in the set C(N ), i.e. we put C(N ) = v∈V (N ) {C(v)}. For convenience, we refer to any collection C of non-empty subsets of X as a cluster system (on X) and to the elements of C as clusters of X. It should be noted that in case N is a phylogenetic tree, the cluster system C(N ) is a hierarchy (on X), that is, for

any two clusters C 1 , C 2 ∈ C(N ) we have that C 1 ∩C 2 ∈ {∅, C 1 , C 2 }.
Hierarchies are sometimes also called laminar families, and it is well-known that the cluster systems C(T ) induced by a phylogenetic tree T uniquely determines that tree (see e.g. Semple and Steel (2003, page 51)).

In the context of phylogenetic network construction, the concept of a weak hierarchy (on X) was introduced in [START_REF] Bandelt | Weak hierarchies associated with similarity measures: an additive clustering technique[END_REF]. These objects are defined as follows. Suppose C is a cluster system on X. Then C is called a weak hierarchy (on X) if

C 1 ∩ C 2 ∩ C 3 ∈ {C 1 ∩ C 2 , C 2 ∩ C 3 , C 1 ∩ C 3 } (1)
holds for any three elements C 1 , C 2 , C 3 ∈ C. Note that any hierarchy is in particular a weak hierarchy and that any subset of a weak hierarchy is again a weak hierarchy. Also note that weak hierarchies are well-known objects in classical hypergraph and abstract convexity theory [START_REF] Bandelt | Weak hierarchies associated with similarity measures: an additive clustering technique[END_REF] (see also the reference therein and [START_REF] Barthélémy | Combinatorial optimization and hierarchical classifications[END_REF]), and that they where originally introduced into cluster analysis as medinclus in [START_REF] Batbedat | Les isomorphismes HTE et HTS, après la bijection de Benzécri-Johnson[END_REF].

We will establish the main result of this section (Proposition 1) by showing that the cluster system S(N ) associated to a level-1 network N is a weak hierarchy. To do this, we first need to complete the definition of the softwired cluster system S(N ) given in the introduction, which relies on the definition of the system T (N ). We will do this next.

Suppose N is a phylogenetic network. Then we say that a phylogenetic tree T is displayed by N if the leaf set of T is X and T can be obtained from N via a series of vertex deletions, arc deletions, and vertex suppressions (see also [START_REF] Huson | Phylogenetic Networks[END_REF]). For a vertex v the latter operation is defined as deleting v plus its incoming and outgoing arcs a 1 and a 2 , respectively, from N and adding an arc from the tail of a 1 to the head of a 2 . The set T (N ) is then the collection of all phylogenetic trees that are displayed by N . Note that in addition to the cluster C N (v), a cluster system

S N (v) = {C T (v) : T ∈ T (N )} can be associated to every vertex v ∈ V (N ). Clearly, C N (v) ∈ S N (v) holds for every v ∈ V (N ) and S(N ) = v∈V (N ) S N (v).
To link clusters of X with level-1 networks on X, we say that a cluster C on X is level-1-consistent if there exists a level-1 network N such that C ∈ S(N ). More generally, we say that a cluster system C is level-1-consistent if there exists a level-1 network N such that C ⊆ S(N ) holds. Thus, the cluster system S(N ) associated to any level-1 network N is level-1-consistent.

Proposition 1 A level-1-consistent cluster system is a weak hierarchy. In particular, the systems S(N ) and C(N ) associated to a level-1 network N are weak hierarchies.

Proof: Suppose C is a level-1-consistent cluster system. Let N denote a level-1 network such that C ⊆ S(N ). Since, as was remarked above, a subset of a weak hierarchy is again a weak hierarchy, it clearly suffices to show that S(N ) is a weak hierarchy. To observe this, consider the phylogenetic tree T 1 on X obtained from N by randomly deleting for each reticulation vertex of N one of its incoming arcs and suppressing any resulting degree 2 vertex. If this renders the root ρ N of N to have degree 1, identify ρ N with its unique child. Construct a phylogenetic tree T 2 on X in a similar way but this time deleting for each reticulation vertex the other incoming arc. Clearly, S(N ) = C(T 1 ) ∪ C(T 2 ). Since C(T i ), i = 1, 2, is a hierarchy and the union of two hierarchies is a weak hierarchy (Bandelt and Dress, 1989, page 149), the proposition follows.

In general the number of elements in a weak hierarchy on X is at most |X|+1 2 [START_REF] Bandelt | Weak hierarchies associated with similarity measures: an additive clustering technique[END_REF]. However Proposition 1 combined with (Kanj et al, 2008, Lemma 6.8) trivially implies that for the special case of level-1-consistent cluster systems this general bound for weak hierarchies can be improved to a bound that is linear in |X|.

We remark in passing that a similarity measure D C : X × X → R can be associated to any cluster system C of X by putting

D C (a, b) = |{C ∈ C : a, b ∈ C}|, a, b ∈ X.
Proposition 1 combined with the main result from [START_REF] Bandelt | Weak hierarchies associated with similarity measures: an additive clustering technique[END_REF] implies that any level-1-consistent cluster system C can be uniquely reconstructed from its associated similarity measure D C . Using the well-known Farris transform (see e. g. Semple and Steel (2003, page 149), and Dress et al (2007) for a recent overview) a similarity measure can be canonically transformed into a distance measure D C on X. For a set Y such a measure is defined as a map from Y × Y into the non-negative reals that is symmetric, satisfies the triangle inequality, and vanishes on the main diagonal. Distance measures were investigated in [START_REF] Chan | Reconstructing an ultrametric galled phylogenetic network from a distance matrix[END_REF] from an algorithmical point of view in the context of representing them in terms of an ultrametric level-1 network. These networks are generalizations of ultrametric phylogenetic trees in the sense that every path from the root of the network to any of its leaves is of the same length.

We conclude this section with remarking that as the example of the level-2 network N presented in Fig. 4 shows, the result analogous to Proposition 1 does not hold for level-2 networks in general since {{a, b, c}, {a, b, d}, {b, c, d}} ⊆ S(N ) and {a, b, c} ∩ {a, b, d} ∩ {b, c, d} = {b} but the intersection of any 2 of the participating 3-sets is of size 2.

Fig. 4 A level-2 network N for which S(N ) is not a weak hierarchy.

Triplet systems induced by simple level-1 networks and by cluster systems

In this section, we turn our attention to triplet system induced by simple level-1 networks and also by cluster systems. In particular, we establish a property of these networks (Lemma 1) which, with regards to the encoding problem for level-1 networks, has turned out to be fundamental. Furthermore we show that a triplet system induced by a phylogenetic tree T is contained in the triplet system induced by a level-1 network N if and only if T is displayed by N (Proposition 2). Along the way, we establish various relationships between the triplet system, the softwired cluster system and the tree system induced by a level-1 network. We start with presenting the definition of the triplet system R(N ) induced by a phylogenetic network N .

For a phylogenetic network N , we say that a triplet x|yz is consistent with N if x, y, z ∈ X and there exist two vertices u, v ∈ V (N ) and pairwise internally vertex-disjoint paths in N from u to y, u to z, v to u and v to x. Note that a triplet system R is called consistent with a phylogenetic network N if every triplet in R is consistent with N . For convenience, we will sometimes say that a phylogenetic network N is consistent with a triplet t (or a triplet system R) if t (or R) is consistent with N . The set of all triplets consistent with a phylogenetic network N is denoted by R(N ), and we say that N reflects a triplet system R if R = R(N ). For example and ignoring the arc labels for the moment, each of the three simple level-1 networks L i (R) on X = {a, b, c}, i ∈ X, depicted in Fig. 5 reflects the triplet system R = {a|bc, c|ab}.

L a (R) L b (R) L c (R)
Fig. 5 Ignoring the arc labels for the moment, the three non-isomorphic simple level-1 networks on {a, b, c} that all reflect the triplet system R = {a|bc, c|ab}.

Now suppose that N is one of the simple level-1 networks L i (R), i ∈ X = {a, b, c}, on X depicted in Fig. 5. Assume that d ∈ X and let e = uv ∈ A(N ) denote a non-cut arc of N , that is, e is not a cut arc of N . Then we denote by N e ⊕ d the level-1 network obtained from N by adding a new vertex w to V (N ) ∪ {d} and replacing e by the arcs uw, wv, and wd. If the knowledge of e is of no relevance, then we will write N ⊕ d rather than N e ⊕ d.

The next result is fundamental to the proof of our main result (Theorem 1) as it assures us that although all three simple level-1 networks depicted in Fig. 5 reflect the same triplet system, this property is lost when attaching an additional leaf to a non-cut arc of each of them.

Lemma 1 Suppose X = {a, b, c, d} and R = {a|bc, c|ab}. Then, the triplet systems

R(L a (R) ⊕ d), R(L b (R) ⊕ d), and R(L c (R) ⊕ d).
are all distinct.

Proof: For each of the simple level-1 networks L x (R), x ∈ {a, b, c}, consider the arc labeling indicated in Fig. 5. With r := a|bc and r ′ := c|ab, we detail the triplet systems induced by the simple level-1 networks obtained from them by attaching a new leaf d in Table 1. Since no two of those systems are the same, the lemma follows. 1 The triplet system induced by attaching a new leaf to one of the non-cut arcs of the simple level-1 networks depicted in Fig. 5.

Turning our attention to cluster systems of X, note that any cluster C X induces a triplet system

R(C) = {c 1 c 2 |x : c 1 , c 2 ∈ C distinct and x ∈ X -C} on X.
Thus, any non-empty cluster system C on X induces the triplet system R(C) := C∈C-{X} R(C) on X. Note that R(C) is dense on X, where a triplet system R on X is called dense if for any three distinct elements a, b, c ∈ X there exists a triplet t ∈ R such that L(t) = {a, b, c}.

The next result is central for establishing the main result of this section (Proposition 2).

Lemma 2 Suppose N is a level-k network, k ≥ 0, with at least 3 leaves. Then the following holds (i) If t ∈ R(N ) then there exists a phylogenetic tree T ∈ T (N ) with t ∈ R(T ).

(ii) R(N ) = T ∈T (N ) R(T ) = C∈S(N ) R(C).
Proof: (i) Suppose t ∈ R(N ) and assume that x 1 , x 2 , x 3 ∈ X with t = x 1 x 2 |x 3 . Then there exist distinct vertices u, v ∈ V (N ) such that among the paths from u to x 1 , u to x 2 , v to u and v to x 3 no two of them share an interior vertex. Then the phylogenetic tree obtained from N by deleting, for any vertex v ∈ r(N ), one of the incoming arcs as specified below and suppressing the resulting degree two vertex is clearly contained in T (N ) and t ∈ R(T ) holds. If v is a vertex on one of the four paths above, call it P , then delete that incoming arc of v that is not also an arc on P . Otherwise, delete one of the two incoming arcs of v making sure that the resulting graph is a phylogenetic tree on X.

(ii) Clearly T ∈T (N ) R(T ) = T ∈T (N ) C∈S(T ) R(C) = C∈S(N ) R(C)
holds and it is straightforward to see that T ∈T (N ) R(T ) ⊆ R(N ). The converse set inclusion follows from (i).

To establish Proposition 2, we require some more terminology. Suppose R is a triplet system on X and C is a cluster system on X. Then we associate to R the cluster system

S(R) = {C X : x 1 , x 2 ∈ C distinct and x 3 ∈ X -C implies x 1 x 2 |x 3 ∈ R}
on X and to C the tree system

T (C) = {T ∈ T (X) : C(T ) ⊆ C}
on X where T (X) denotes the space of all phylogenetic trees on X.

Next, suppose that N is a phylogenetic network and that a, b, c ∈ V (N ) are vertices of N with a N b and c N b. Then we call b a common ancestor of a and c. A lowest common ancestor lca N (a, c) of a and c is a common ancestor of a and c and no other vertex below lca N (a, c) is a common ancestor of a and c. Note that in a level-0 or level-1 network N , the lowest common ancestor between any two distinct leaves of N is always unique whereas this need not be the case for level-k networks with larger k. More generally, suppose C is cluster of X. Then a vertex v ∈ V (N ) is called a lowest common ancestor of C if v is a common ancestor of every pair of elements in C and no other vertex in N below v satisfies this property. In view of the fact that this vertex is again unique in a level-1 network we will denote it by lca N (C).

Proposition 2 Suppose N is a level-k network, k ≥ 0, with at least 3 leaves. Then S(N ) ⊆ S(R(N )) and T (N ) ⊆ T (S(N )). Moreover, if k ≤ 1 we have

(i) S(N ) = S(R(N )). (ii) T (N ) = T (S(N )). (iii) A phylogenetic tree T is displayed by a level-k network N if and only if R(T ) ⊆ R(N ).
Proof: Suppose C ∈ S(N ). Then x 1 x 2 |x 3 ∈ R(C) holds for any two distinct elements x 1 , x 2 ∈ C and any

x 3 ∈ X -C. By Lemma 2, x 1 x 2 |x 3 ∈ C ′ ∈S(N ) R(C ′ ) ⊆ R(N )
and so C ∈ S(R(N )), as required. That T (N ) ⊆ T (S(N )) holds is trivial.

Assume for the remainder of the proof that k ≤ 1.

Clearly (i) -(iii) hold in case k = 0. So assume k = 1. (i) Suppose C ∈ S(R(N )). Then C = X and there exist distinct elements a, b ∈ C such that lca N (C) = lca N (a, b). Let x ∈ X -C. Then since C ∈ S(R(N )), we have ab|x ∈ R(N ). By Lemma 2(i) there exists a phylogenetic tree T ∈ T (N ) with ab|x ∈ R(N ). Since lca N (C) = lca N (a, b) ∈ V (T ) it follows that C ∈ C(T ) ⊆ S(N ). (ii) Suppose T ∈ T (S(N )). For all v ∈ V (N ) put E N (v) = {w ∈ V (N ) : C N (v) = C N (w)}. Note that |E N (v)| = 2 if and only if v is a reticulation vertex of N or the unique child of such a vertex of N and that |E N (v)| = 1 holds otherwise. Consider the map φ : V (T ) → V (N ) that maps every vertex v ∈ V (T ) to a vertex w v := φ(v) in V (N ) such that C(v) = C(w v )
and every element w ∈ E N (w v ) distinct from w v lies on a path from the root ρ N of N to w v . By the definition of T (S(N )) it follows that φ is well-defined. Moreover, φ is clearly injective. In fact, since w v is never a reticulation vertex of N , the map φ induces a bijection between the vertices of T and the vertex set V (N )r(N ).

Let x, y ∈ V (T ) such that xy is an arc in T and φ(x) and φ(y) are joined in N by a path P xy of length 2. Then the interior vertex r xy of P xy must be a reticulation vertex of N and every reticulation vertex of N must be the interior vertex of such a path. Let a rxy denote that incoming arc of r xy whose tail is x. Then deleting for all reticulation vertices r of N the incoming arc distinct from a r (suppressing any resulting degree 2 vertices) results in a tree T ′ ∈ T (N ) that is isomorphic with T (in fact T ′ is T ).

(iii) That R(T ) ⊆ R(N ) holds whenever a phylogenetic tree T is displayed by a level-1 network N follows from Lemma 2(ii). Conversely, suppose T is a phylogenetic tree with R(T ) ⊆ R(N ). By (i) and (ii) it suffices to show that T ∈ T (S(R(N ))). Thus, we need to show that C(T ) ⊆ S(R(N )). So suppose C ∈ C(T ) and let x 1 , x 2 ∈ C distinct, and

x 3 ∈ X -C. Then x 1 x 2 |x 3 ∈ R(T ) ⊆ R(N ). Hence, C ∈ S(R(N )).
Note that as the example of the level-2 network depicted in Fig. 6 shows, the analogous relationships (i. e. Proposition 2(i) and (iii)) do not hold in general for the corresponding systems.

Fig. 6 A level-2 network N with bc|d, bc|a ∈ R(N ) but {b, c} ∈ S(N ) and so S(R(N )) = S(N ). A phylogenetic tree T with C(T ) ⊆ S(N ) and R(T ) ⊆ R(N ) but T ∈ T (N ). For ease of verification, we have labelled an arc by the softwired cluster(s) its head induces and also write xyz for a cluster {x, y, z}.

Encodings of level-1 networks

In this section, we characterize those level-1 networks N that are encoded by the triplet system R(N ), or equivalently the tree system T (N ), or equivalently the cluster system S(N ) they induce (Theorem 1). Note in this context that the cluster system C(N ) induced by a level-1 network N is in general not an encoding of N . To see this, consider for example a simple level-1 network N with n ≥ 3 leaves such that the parent of each leaf lies on the same path from the root ρ N of N to its reticulation vertex h N . Then ρ N h N is an arc of N and C(N ) = C(T ) holds for the phylogenetic tree T ∈ T (N ) obtained via deleting the arc ρ N h N from N and identifying ρ N with its unique child.

Bearing in mind that there exist triplet systems which can be reflected by more than one level-1 network, we denote the collection of all level-1 networks that reflect a triplet system R by L 1 (R). Clearly, if R is reflected by a level-1 network N then N ∈ L 1 (R(N )) and so |L 1 (R(N ))| ≥ 1. Similarly, we denote for a tree system T the collection of all level-1 networks N for which T = T (N ) holds by L 1 (T ), and for a cluster system C the collection of all level-1 networks N for which C = S(N ) holds by L 1 (C). As in the case of triplet systems, there exist tree systems T and cluster systems C with |L 1 (T )| > 1 and |L 1 (C)| > 1, respectively.

The next lemma serves as a stepping stone in the proof of Theorem 1 and is concerned with analyzing level-1 networks N that have a large enough leaved block B, that is, B is a block of N and every arc that starts at a vertex in B ends either in a vertex of B or a leaf of N . Calling those leaves of N also the leaves of B, we remark that a leaved block is a simple level-1 network on its set of leaves.

To present the proof of the lemma, we require some more notation and definitions. Suppose N is a phylogenetic network with at least 3 leaves. Then we call a subset {x, y} ⊆ X a cherry of N if there exists a vertex v ∈ V (N ) such that vx, vy ∈ A(N ). Now suppose N is a level-1 network and x is either (i) a leaf of a leaved block B of N that is adjacent with a parent of the reticulation vertex of B or (ii) a leaf in a cherry of N . Then we denote by Nx the level-1 network obtained from N by removing x and, in case of (i), its parent y and all their incident arcs and, in case of (ii), its incident arc, both times suppressing resulting degree 2 vertices and, if the roof of N has been rendered a degree 1 vertex, identifying it with its unique child. Also, we say that N is a strict level-1 network if N is not a phylogenetic tree and associate to a triplet system R and some x ∈ t∈R L(t), the triplet system R

x := {t ∈ R : x ∈ L(t)}. Recall that for a directed graph G, we put V -(G) = V (G) -L(G).
Obviously, a level-1 network N that has a leaved block B with at least 5 non-leaf vertices must have at least 4 leaves. Also one of the two distinct parent vertices y ′ 1 , y ′ 2 ∈ V (B) of the reticulation vertex p ′ of B could be the root ρ = ρ B of B. Note however that y ′ i is adjacent with a leaf of B whenever y ′ i = ρ, i = 1, 2. We denote that leaf by y i . Also note that since |V -(B)| ≥ 5, at least one of the paths P ρy ′ i from ρ to y ′ i , i = 1, 2, must contain a vertex y ′ distinct from ρ and y i . Let y denote the leaf of B adjacent with y ′ . Note that without loss of generality we may assume that i = 1 and that y ′ is the predecessor of y ′ 1 on the path P ρy ′ 1 . Let p denote the leaf of B adjacent with p ′ . We depict the two possible configurations for B for the case |V -(B)| = 5 in Fig. 7. Lemma 3 Suppose N is a level-1 network with at least 3 leaves such that, in addition to every block having at least 5 vertices, N also has a leaved block.

Then |L 1 (R(N ))| = 1.

Proof: We prove the lemma by induction on the number n of leaves of N . Suppose that B is a leaved block of N and assume that the notations and assumptions made above for a leaved block of a level-1 network apply to B.

To see the base case of the induction assume that n = 4. Then B must equal N Proof: (i) ⇒ (iv): This is an immediate consequence of the fact that all simple level-1 networks depicted in Fig. 5 induce the same set of phylogenetic trees.

(iv) ⇒ (iii): Suppose that N is a level-1 network with |L 1 (T (N ))| > 1. Then there exists a level-1 network

N ′ ∈ L 1 (T (N )) distinct from N with T (N ) = T (N ′ ). But then S(N ) = T ∈T (N ) C(T ) = T ∈T (N ′ ) C(T ) = S(N ′ ) and so N ′ ∈ L 1 (S(N )). Thus, |L 1 (S(N ))| > 1. (iii) ⇒ (ii): Suppose that N is a level-1 network with |L 1 (S(N ))| > 1.
Then there exists a level-1 network

N ′ ∈ L 1 (S(N )) distinct from N such that S(N ) = S(N ′ ). But then Lemma 2(ii) implies R(N ) = C∈S(N ) R(C) = C∈S(N ′ ) R(C) = R(N ′ )
and so

N ′ ∈ L 1 (R(N )). Hence, |L 1 (R(N ))| > 1.
(ii) ⇒ (i) We will show by induction on the number n of leaves of N that if every block in N has at least 5 vertices then |L 1 (R(N ))| = 1. Suppose N is a level-1 network with n leaves such that every block of N has at least 5 vertices. Note that we may assume that N has at least one such block since otherwise N is a phylogenetic tree and so

|L 1 (R(N ))| = 1 clearly holds. But then n ≥ 4. If n = 4 then |L 1 (R(N ))| = 1 is a straightforward consequence of Lemma 1.
Suppose n > 4. Assume for every level-1 network N 0 with n 0 < n leaves that |L 1 (R(N 0 ))| = 1 holds whenever N 0 is a phylogenetic tree or every block in N 0 has at least 5 vertices. We distinguish the cases that N has a cherry and that it does not. Clearly, if N does not have a cherry then it must have a leaved block and so |L 1 (R(N ))| = 1 follows by Lemma 3. Now suppose that N has a cherry {x, y} ⊆ X and assume for contradiction that there exists a level-1 network N ′ in L 1 (R(N )) distinct from N . Without loss of generality, we may assume that this cherry is as far away from the root of N as possible. Then since N is a strict level-1 network all of whose blocks have at least 5 vertices, Nx must enjoy the same property with regards to its blocks. But then, by induction hypothesis, |L 1 (R(Nx))| = 1 and so Nx is the unique level-1 network that reflects R(Nx) = R x . Since by the choice of x, for every leaf z in N distinct from x and y, only the triplet z|xy out of the 3 possible triplets on {x, y, z} is contained in R(N ) = R(N ′ ), it follows that {x, y} must also be a cherry in N ′ . But then N = N ′ which is impossible. Thus, |L 1 (R(N ))| = 1 must hold in this case too which completes the proof of the theorem.

Note that the implication (ii) ⇒ (i) in the proof of Theorem 1 can also be obtained using an alternative 2-phase strategy that is based on so called SN-sets which were originally introduced in Jansson and Sung (2006). For any triplet system R on X and any subset Y ⊆ X, the SN-set associated to Y is recursively defined as SN (Y ) = SN (Y ∪ {c}) if there exists some y, y ′ ∈ Y distinct and some c ∈ X -Y such that yc|y ′ ∈ R, and SN (Y ) = Y otherwise. In Jansson and Sung (2006), it was shown that in case R is dense, a rooted leaflabelled tree can be associated to the set Σ R of strongly connected components of a certain graph G R that can be associated to the SN-sets of X of the form SN ({a, b}) with a, b ∈ X distinct. This tree is sometimes called the SN-tree T R associated to R and is used in (Jansson and Sung, 2006) to compute a level-1 network from such a triplet system in O(|X| 3 ) time. Then the first step of the alternative strategy consists of establishing that the edge set of T R(N ) is in bijective correspondence with the set of cut arcs of any level-1 network N ′ with R(N ′ ) = R(N ). Ignoring the blocks of N for the moment by viewing each one of them as being collapsed into a single vertex this implies that the structure of N is uniquely determined by R(N ). The second and final step is concerned with establishing the structure of the blocks of N . But this is a consequence of Lemma 1 since by collapsing for each vertex v of a block of N the set of vertices of N that are reachable from v by crossing the cut arc of N incident with v into a single vertex, and making the corresponding adjustments to the triplet system R(N ), the block becomes a simple level-1 network and the triplet system a triplet system on the leaf set of that block.

Theorem 1 immediately implies the following corollary about the number of networks that reflect R(N ).

Corollary 1 Let N be a level-1 network with at least 3 leaves. Then the number of non-isomorphic level-1 networks N ′ that reflect R(N ) (or equivalently for which T (N ) = T (N ′ ) or equivalently S(N ) = S(N ′ ) holds) is 3 b , where b is the number of blocks of N that have 4 vertices.

Returning to the problem of encodings of level-1 networks, we remark that phylogenetic trees on X can also be viewed as trees together with a bijective labelling map between X and the leaf set of such trees. Taking this point of view, phylogenetic trees were generalized in [START_REF] Moulton | Phylogenetic networks from multi-labeled trees[END_REF] to MUL-trees by allowing two or more leaves of such a tree to have the same label. Note that in [START_REF] Fellows | Analogs & duals of the mast problem for sequences & trees[END_REF] such trees are called rl-trees. For example, the tree obtained from the phylogenetic tree depicted in Fig. 1(c) by replacing the leaf labelled a by the cherry labelled {a, b} is such a tree. In fact, this MULtree is the MUL-tree induced by the level-1 network N depicted in Fig. 3(b) i. e. it contains all paths from the root of N to all leaves of N . For a level-1 network N it is easily seen that the MUL-tree M(N ) induced by N this way is in fact an encoding of N in the sense that N is the unique level-1 network that can give rise to M(N ).

Metrics

The problem of comparing phylogenetic networks has recently received a considerable amount of attention in the literature resulting in e.g. the definition of metrics for so called time consistent tree child and time consistent tree sibling networks see e.g. (Cardona et al, 2009a,b) and also [START_REF] Huson | Phylogenetic Networks[END_REF] for a recent overview). Denoting the class of all phylogenetic networks on X by N , and the subclass of all level-1 network on X which do not contain a block with 4 vertices by C - 1 , we carry this theme further by establishing in this section that 3 distance measures that were originally introduced in [START_REF] Huson | Phylogenetic Networks[END_REF] are in fact metrics on C - 1 . In addition we present the diameter of two of them on that subclass. Before we start, we remark that since level-1 networks contained in C - 1 are allowed to contain blocks B that contain an arc from the root of B to the reticulation vertex of B, the class C - 1 is different from the class of time consistent tree-child or time-consistent tree-sibling networks.

To start, recall that a distance measure D on N is called a metric if the following property is satisfied for all networks N 1 , N 2 ∈ N :

D(N 1 , N 2 ) = 0 if and only if N 1 and N 2 are isomorphic. (2)
Note that Property 2 is called the separation property in (Cardona et al, 2009a,b). Also note that a distance measure is sometimes called a metric and a distance measure that satisfies Property 2 a proper metric.

Two types of distance measures for phylogenetic networks that have their origin in the problem of comparing phylogenetics trees are the triplet distance D tri and the Robinson-Foulds distance D RF . For T 1 and T 2 two phylogenetic trees (i.e. level-0 networks) the former is defined as

D tri (T 1 , T 2 ) = |R(T 1 )∆R(T 2 )|/2
and the latter as D RF (T 1 , T 2 ) = |S(T 1 )∆S(T 2 )|/2. where for any two set A and B the symmetric difference between A and B is denoted by A∆B. Note however that both distance measures are different from the Robinson Foulds distance and the triplet distance introduced in (Cardona et al, 2009a) and (Cardona et al, 2009b), respectively. Also note that both can be canonically extended to obtain distance measures D tri and D RF on N by replacing T 1 and T 2 by phylogenetic networks N 1 and N 2 , respectively.

Complementing the above two distance measures, a further distance measure D tree on N was introduced in Huson et al (2011). For two phylogenetic networks N 1 and N 2 in N , this distance measure is defined as

D tree (N 1 , N 2 ) = |T (N 1 )∆T (N 2 )|/2.
In view of Theorem 1, we immediately obtain Corollary 2 The distance measures D tri , D RF and D tree are metrics on C - 1 .

To better understand the range of values a metric D on N (or a subclass C of N ) can attain, the diameter diam(D, C) of D is sometimes used which is defined as diam(D, C) := max{D(N 1 , N 2 ) : N 1 , N 2 ∈ C}.

To establish our main result of this section (Theorem 2), we first introduce a leaf-labelled rooted DAG that is central for establishing diam(D RF , C - 1 ). Let G(n) = (G(n), φ) denote the leaf-labelled graph on n := |X| ≥ 3 leaves with φ : X → L(G(n)) a bijective map and G(n) a rooted DAG that satisfies the following property: In addition to enjoying Properties (P2) and (P3) (and thus also (P1) once we have identified X with L(G(n))), G(n) consists of precisely one leaved block on n leaves that has an arc joining its root and its reticulation vertex. Note that once the aforementioned identification has been carried out, G(n) is clearly a level-1 network. Also note that the networks L a (R) and L c (R) on X = {a, b, c} depicted in Fig. 5 are examples of G(3). For clarity of our arguments and in case the knowledge of the leaf-labelling map φ is of no relevance, we omit it from our discussion. In this case we simply view G(n) as a level-1 network.

Concerning S(G(n)), we remark that a phylogenetic tree T with n ≥ 3 leaves is known to have 2n-1 vertices and thus induces 2n-1 distinct clusters. Proof: We prove the proposition by induction on n. Clearly the stated inequality holds for n = 3. So assume that it holds up to and including some n ≥ 3 and let N be a level-1 network on n + 1 leaves. We distinguish the cases that N has a cherry (i) and that N does not have a cherry (ii).

(i): Suppose {x, y} is a cherry of N . Then deleting x plus its incident arc (suppressing the resulting degree 2 vertex) results in a level-1 network N -on n leaves. Clearly |S(N )| = |S(N -)| + 2 and so, by induction hypothesis, We next introduce a leaf-labelled DAG that has turned out to be central for establishing the diameter of D tree . Let G ′ (n) = (G ′ (n), φ ′ ) denote the leaflabelled graph on n := |X| ≥ 4 leaves with φ ′ : X → L(G ′ (n)) a bijective map and G ′ (n) a rooted DAG that satisfies the following property: In addition to enjoying Properties (P2) and (P3) (and thus also (P1) once we have identified

|S(N )| = |S(N -)|+2 ≤ |S(G(n))|+2 = 3n-3+2 ≤ 3(n+1)-3 = |S(G(n+1))| (
X with L(G ′ (n))), G ′ (n) consists of l := ⌊ n-1 3 ⌋ blocks B i , 1 ≤ i ≤ l, with |V (B i )| = 5
and an arc joining the root ρ i of B i with its reticulation vertex h i and h i ρ i+1 ∈ A(G ′ (n)), 1 ≤ i ≤ l -1. In addition, G ′ (n) has ((n -1) mod 3) extra leaves one of which is a child of the root ρ G ′ (n) of G ′ (n) and the distance of the other leaf to ρ G ′ (n) is 3. Note that once the aforementioned identification has been carried out, G ′ (n) is clearly a level-1 network. We present two examples of G ′ (12) with X = {x 1 , . . . , x 12 } in Fig. 8. We are now ready to establish the aforementioned diameter results.

σ(i) = i/2 if i is even and ⌊ n 2 ⌋ + i+1 2 otherwise.
Then it is not difficult to see that X and its singletons are the only clusters common to S(N 1 ) and S(N 2 ). By Proposition 3, D RF (N 1 , N 2 ) = (2(3n -3) -2n) -2)/2 = 2n -4 follows.

We remark that the bound for D RF is also attained for 2 rooted caterpillar phylogenetic trees on n leaves (i. e. a rooted phylogenetic tree on n leaves with a unique cherry) where the leaf ordering of one is the reverse of the leaf ordering of the other.

Encodings and indistinguishability

In this section, we turn our attention to encodings of level-k networks with k ≥ 2. Our main result is summarized in Proposition 5 where we present examples of level-2 networks that are encoded by some of the induced systems of interest in this paper but not by others.

To start, consider the two simple level-3 networks depicted in Fig. 9(i) and (ii), respectively, which originally appeared in [START_REF] Huson | Phylogenetic Networks[END_REF] in slightly different form (see also [START_REF] Moret | Phylogenetic networks: Modeling, reconstructibility, and accuracy[END_REF]). As can be quickly checked, both networks induce the same hardwired cluster system and also the same tree system (and thus also the same softwired cluster system and the same triplet system). Consequently, neither of them encodes those networks. By canonically extending the definitions of the above four systems plus their surrounding terminology to also apply to the leaf labelled rooted DAG depicted in Fig. 9(iii) it is easy to check that the four systems induced by that graph coincide with the corresponding systems induced by the networks in Fig. 9(i) and (ii).

(i) (ii) (ii)
Fig. 9 Two indistinguishable simple level-3 networks (i,ii), and a multicombination network resulting from a series of multicombination contractions applied to either one of them (iii).

To also include such graphs in our discussion, we now extend our definition of a phylogenetic network N (and thus also the definition of the set r(N )) to allow reticulation vertices to have indegree 2 or more. However and in case of ambiguity, we follow [START_REF] Huson | Phylogenetic Networks[END_REF] and refer to a reticulation vertex with indegree strictly greater than 2 as a multicombination, and to a phylogenetic network containing such reticulation vertices as a multicombining network. In fact, any phylogenetic network N that contains arcs of the form r 2 r 1 with r 1 , r 2 ∈ r(N ) can be transformed into a multicombining network using a series of multicombination contractions, that is, contractions of the arcs r 2 r 1 . Extending the definition of a level of a phylogenetic network to a multicombining network N by defining the level of N as the maximum sum, among all blocks B of N , of the indegrees, minus one, of all vertices in B ∩ r(N ), it should be noted that this operation is level preserving. Within this more general framework, we formalize the notion of indistinguishability which was already indicated in [START_REF] Huson | Phylogenetic Networks[END_REF] as follows: We say that two phylogenetic networks N and N ′ are indistinguishable if C(N ) = C(N ′ ) and T (N ) = T (N ′ ) hold and distinguishable otherwise. Note that S(N ) = S(N ′ ) and R(N ) = R(N ′ ) must hold whenever two phylogenetic networks N and N ′ are indistinguishable.

It is easy to see, that the phylogenetic networks presented in Figs. 9(i) and (ii) give rise to the multicombining network depicted in Fig. 9(iii) using a series of multicombination contractions. That the observed indistinguishability property holds is not a coincidence as the following result shows.

Proposition 4 Suppose N is a level-k network (possibly containing multicombination vertices) with k ≥ 2 and N ′ is a multicombining network that can be obtained from N by a series of multicombination contractions. Then N and N ′ are indistinguishable.

Proof: Since N ′ is a multicombining network that can be obtained from N by a series of multicombination contractions, it suffices to show that at each step the hardwired cluster system and the tree system induced by N is preserved. Suppose r 1 , r 2 ∈ r(N ) with r 2 r 1 ∈ A(N ). Assume without loss of generality that N ′ is the network resulting from a multicombination contraction of r 2 r 1 and denote the generated vertex by r. Let y 1 , . . . , y t ∈ V (N ), t ≥ 2, denote the parents of r 2 , and let r 2 , z 1 , . . . , z t ′ ∈ V (N ), t ′ ≥ 2, denote the parents of r 1 . Furthermore, let x denote the (unique) child of r 1 . We illustrate these configurations for the case t = 3 and t ′ = 2 in Fig. 10 To see that C(N ) = C(N ′ ) holds, note that in N , the set of leaves simultaneously below y i , i ∈ [t], z i , i ∈ [t ′ ], r 1 , and r 2 equals the set of leaves below x. In N ′ , the set of leaves simultaneously below y i , i ∈ [t], z i , i ∈ [t ′ ], and r equals the set of leaves below x. Moreover, the set of leaves below x in N and N ′ is the same. Hence C(N ) = C(N ′ ).

We next show that T (N ) = T (N ′ ) holds. Suppose T ∈ T (N ) and assume that y j r 2 ∈ A(N ) is the unique arc in N that was not deleted to obtain N ′ . For the arcs in N with head r 1 , we have the following two cases:

(i) If r 2 r 1 is the arc that was not deleted in N then T is displayed by N ′ as all arcs y i r ∈ A(N ′ ) with i ∈ [t]j and all arcs z i r ∈ A(N ′ ) with i ∈ [t ′ ] may be deleted from N ′ .

(ii) If z j ′ r 1 with j ′ ∈ [t ′ ] is the arc which was not deleted in N then T is displayed by N ′ , as all arcs y i r ∈ A(N ′ ) with i ∈ [t] and all arcs z i r ∈ A(N ′ ) with i ∈ [t ′ ]j ′ may be deleted from N ′ . Thus, T ∈ T (N ′ ) follows in both cases. Conversely, for any tree T ∈ T (N ′ ), we need to delete all but one arc in i∈[t] {y i r} ∪ i∈[t ′ ] {z i r} from N ′ . For any of the t + t ′ possibilities and by reversing our arguments in the above analysis, we can determine which arcs to delete from N (i. e. all but one with head r 2 and all but one with head r 1 ) to see that T ∈ T (N ) holds. Hence, T (N ) = T (N ′ ), as required. Thus, N and N ′ are indistinguishable.

In consequence, two level-k, k ≥ 2, networks N 1 and N 2 are indistinguishable if the multicombining networks N ′ i obtained from N i , i = 1, 2, at the point when the respective multicombination contraction series stabilize are isomorphic.

We next present 2 examples of distinguishable level-2 networks. For the networks considered in each example the induced triplet system is the same. However in one case the induced softwired cluster systems coincide whereas in the other they do not (Proposition 5). The example presented in Proposition 5(ii) is of particular interest in the context of Theorem 1 as it implies that our arguments for establishing that theorem do not readily translate into arguments for level-k networks with k ≥ 2. More precisely, they show that adding additional leaves to both networks that make up that example by subdividing the arc from x 1 's parent to x 2 's, and attaching additional leaves, results in two distinct level-2 networks that still reflect the same triplet system.

Proposition 5 (i) There exist two non-isomorphic distinguishable simple level-2 networks N 1 and N 2 that have the same number of edges, vertices, and reticulation vertices, and R(N 1 ) = R(N 2 ) and S(N 1 ) = S(N 2 ) hold.

(ii) There exist two non-isomorphic distinguishable simple level-2 networks N 1 and N 2 that have the same number of edges, vertices, reticulation vertices, and R(N 1 ) = R(N 2 ) and S(N 1 ) = S(N 2 ) hold.

Proof: (i) The networks N 1 and N 2 depicted in Fig. 11 induce the same triplet system {a|x 1 b, b|x 1 a, x 1 |ab, a|x 2 b, b|x 2 a, x 2 |ab, x 1 |x 2 a, a|x 1 x 2 , x 1 |x 2 b, b|x 1 x 2 } but different softwired cluster systems. More precisely, S(N 1 ) = {{a}, {b}, {x 1 }, {x 2 }, {a, x 2 }, {b, x 2 }, {x 1 , x 2 }, {a, b, x 2 }, {a, x 1 , x 2 }, {b, x 1 , x 2 }, {a, b, x 1 , x 2 }} and S(N 2 ) = S(N 1 ) ∪ {{a, x 2 }} (i) (ii)

Fig. 11 Two non-isomorphic distinguishable simple level-2 networks that induce the same triplet systems but different softwired cluster systems.

(ii) The four networks presented in Fig. 12 induce the same triplet system {a|bc, a|bd, a|cd, b|cd, c|ab, d|ab, d|ac, d|bc} and the same softwired cluster system {{a}, {b}, {c}, {d}, {a, b}, {b, c}, {c, d}, {a, b, c}, {b, c, d}, {a, b, c, d}}. (i) (ii) (iii) (iv)

Fig. 12 Four non-isomorphic distinguishable simple level-2 networks that induce the same triplet and softwired cluster systems. Again, the conventions from Fig. 6 apply.

Conclusion

In this paper we have investigated under what circumstances a level-1 network N is encoded by the triplet system, softwired cluster system, or tree system it induces. In particular we have shown that this is the case if and only if N

does not have a block with 4 vertices. For the resulting subclass C - 1 of level-1 networks this implies that three known distance measures for phylogenetic networks are in fact metrics on C - 1 and for two of them we have established their diameter. Along the way we have shown that a softwired cluster system induced by a level-1 network is a weak hierarchy, that a phylogenetic tree T is displayed by a level-1 network N if and only if R(T ) ⊆ R(N ) holds and that a level-2 network may be encoded by some of the systems of interest in this paper without being encoded by the other ones. In fact our results show that many of the properties that we establish for level-1 networks are not enjoyed by level-2 networks and thus networks of higher level.

Regarding the accurate reconstruction of phylogenetic networks from triplets or phylogenetic trees, our results have profound consequences as they imply that any such network N that contains a block of size 4 cannot be encoded by any one of the three systems of interest in this paper. Furthermore if N contains one of the networks discussed in the context of Proposition 5 then N is not encoded by R(N ) and possibly S(N ).

Fig. 1

 1 Fig.1(a) A level-1 network N . (b) and (c) The phylogenetic trees that form the tree system T (N ).

Fig. 7

 7 Fig. 7 The two possible configurations for B in case |V -(B)| = 5 (see text for details).

  Since |T (G(n))| = 2 and the two trees contained in T (G(n)) only have n + 1 clusters in common (i.e. X and its singletons) it follows that |S(G(n))| = 3n-3. Moreover, the following result holds. Proposition 3 Suppose N is a level-1 network with n ≥ 3 leaves. Then |S(N )| ≤ |S(G(n))| = 3n -3

  ii): Since N does not have a cherry it must contain a leaved block B with |V (B)| ≥ 4. Consider first the case that |V (B)| ≥ 5. Let x be a leaf of N that is adjacent to a vertex of B that is not the reticulation vertex h B of B. Then deletion of x plus its incident arc (suppressing the resulting degree 2 vertex in B) results in a level-1 network N -on n leaves. Clearly |S(N )| = |S(N -)| + 3. Arguments similar to the ones used in Case (i) imply that |S(N )| ≤ |S(G(n + 1))|. Finally assume that |V (B)| = 4. Let x be the leaf of N that is adjacent with h B . Then deleting x and h B plus their incident arcs (suppressing resulting degree 2 vertices in B) results again in a level-1 network N -on n leaves. Note that |S(N )| = |S(N -)| + 3 again holds. Proceeding as in the case that |V (B)| ≥ 5 yields |S(N )| ≤ |S(G(n + 1))|.

Fig. 8

 8 Fig.8Two examples of G ′ (12) on X = {x 1 , . . . , x 12 } -see the proof of Theorem 2 for details.

  (a) and (b), respectively. For a positive integer m, put [m] := {1, . . . , m}.

Fig. 10

 10 Fig.10The situation for the networks N and N ′ -see the proof of Proposition 4 for details.

Note that these networks were originally introduced in Choy et al (2004), but the definition commonly used now is slightly different with the main difference being that every vertex of the network with

indegree 2 must have outdegree 1 (see e.g.Jansson et al (2006)).

This work was supported by the French ANR projects ANR-06-BLAN-0148-01 (GRAAL) and ANR-08-EMER-011-01 (PhylARIANE). The authors would like to thank the organizers of the MIEP 2008 workshop where this work was initiated and also the two referees for their helpful comments and suggestions. Finally, they would also like to thank the London Mathematical Society for supporting part of this work.

and that |L 1 (R(N ))| = 1 holds is a straightforward consequence of Lemma 1. To establish the induction step, assume that the induction hypothesis holds for all level-1 networks on n -1 leaves, as specified in the statement of the lemma. We distinguish the cases that |V -(B)| > 5 and that |V -(B)| = 5. Suppose first that |V -(B)| = 5. Then either ρ = y ′ 2 and so B has, in addition to the leaves y 1 , y, p, precisely one more leaf z, or ρ = y ′ 2 and the leaves of B are y 1 , y 2 , y and p (cf Fig. 7). We only consider the case ρ = y ′ 2 since the arguments for the case ρ = y ′ 2 are similar. Then By 1 is a phylogenetic tree on the leaves y, p, y 2 , i.e. the triplet t := y|py 2 . Put t ′ = y 2 |py ∈ R(N ) and R t ′ := R y1t ′ . Since Ny 1 is either a phylogenetic tree or a strict level-1 network such that each of its blocks has at least 5 vertices, the induction hypothesis implies |L 1 (R(Ny 1 ))| = 1. Thus, Ny 1 is the unique level-1 network that reflects R t ′ . Note that the only way to turn Ny 1 into a level-1 network that, in addition to reflecting R t ′ , is also consistent with t ′ is to replace t by one of the 3 level-1 networks depicted in Fig. 5 with y playing the role of a, p playing the role of b and y 2 playing the role of c. If with R = {t, t ′ } we had that that simple level-1 network B ′ were the network L c (R) then the triplet p|y 1 y would not be contained in R(N ) which is impossible. Also since {p|yy 1 , y 1 |py 2 , y|py 1 } ⊆ R(N ) it is impossible for B ′ to be the network L a (R). Consequently B ′ must be the network L b (R). Since y 1 |py, y|py 1 , and y 2 |y 1 p are triplets in R(N ), Lemma 1 implies that the only way to transform Ny 1 into a level-1 network that in addition to including y 1 in its leaf set also reflects R(N ) is to subdivide the arc y 2 p of B ′ by a vertex v and adding the arc vy 1 to the arc set of Ny 1 . But that network is N and so |L 1 (R(N ))| = 1 must hold. Now assume that |V -(B)| > 5 holds. Let N ⊖y 1 denote the level-1 network obtained from N by adding an arc from the tail of the incoming arc a of y ′ 1 to p ′ and deleting y 1 , y ′ 1 and the arcs y ′ 1 y 1 , y ′ 1 p ′ and a. Then since every block in the level-1 network N ⊖y 1 clearly has at least 5 vertices, the induction hypothesis implies |L 1 (R(N ⊖ y 1 ))| = 1. Combined with the fact that y|y 1 p, y 1 p|y 2 and y 1 |py 2 are triplets in R(N ) it follows that

follows from the fact that y|y 1 p, p|yy 1 ∈ R(N ).

We are now ready to prove our main result.

Theorem 1 Suppose N is a level-1 network with at least 3 leaves. Then the following statements are equivalent (i) N has a block with four vertices.

where b is the number of blocks in N . Also note that every network N ∈ C - 1 can be transformed into a (multifurcating) phylogenetic tree T N by collapsing every block B of N into a vertex v B with |V (B)| -1 outgoing arcs. Since a multifurcating phylogenetic tree on n leaves can have at most ⌊ n-1 3 ⌋ non-leaf vertices of outdegree 4 the stated bound follows.

To see that this bound is sharp, put X = {x 1 , . . . , x n }, n ≥ 4, and assume that G ′ (n) is embedded in the plane as indicated in either one of the two networks depicted in Fig. 8 (ignoring the leaf labelling for the moment). Moreover and starting from the unique leaf of G ′ (n) below the reticulation vertex furthest away from the root ρ G ′ (n) of G ′ (n), proceed in clockwise fashion to enumerate the leaves of G ′ (n) by 1, 2, . . . , n with the leaf that is a child of ρ G ′ (n) receiving n (if it exists). As above, put l := ⌊ n-1 3 ⌋.

Note that the latter case only applies if n = 3l + 1. (In Fig. 8, we depict N 1 and N 2 for the case X = {x 1 , . . . , x 12 }). Then it is easy to see that T (N 1 ) ∩ T (N 2 ) = ∅. Since |T (N i )| = 2 l , i = 1, 2, we have D tree (N 1 , N 2 ) = 2 l .

(ii) That 2n-4 is an upper bound for diam(D RF , C - 1 ) follows from Proposition 3 as each level-1 network contained in C - 1 induces at most 3n-3 softwired clusters (including X and its singletons). Hence, for any two level-1 networks

3) -2 -2n = 4n = 4n -8 which immediately implies the stated upper bound.

To see that the bound is sharp put X = {x 1 , . . . , x n }, n ≥ 4, and assume that G(n) is embedded in the plane such that for every interior vertex v on the path from the root ρ G(n) of G(n) to the reticulation vertex h G(n) of G(n) the left child of v always a leaf. Starting from the leaf below h G(n) proceed in clockwise fashion to enumerate the leaves of G(n) by 1, 2, . . . , n.

Let N 1 denote the graph G(n) = (G(n), φ 1 ) with leaf-labelling map φ 1 : X → L(G(n)) defined as φ 1 (x i ) = i, 1 ≤ i ≤ n. Let N 2 denote the graph G(n) = (G(n), φ 2 ) with leaf-labelling map φ : X → G(n) defined as φ(x σ(i) ) = i, 1 ≤ i ≤ n, where σ : {1, . . . , n} → {1, . . . , n} is the permutation given by


Matthieu Sanquer

Florent Chatelain

Mabrouka El-Guedri

Nadine Martin

A REVERSIBLE JUMP MCMC ALGORITHM FOR BAYESIAN CURVE FITTING BY USING SMOOTH TRANSITION REGRESSION MODELS

Keywords: Bayesian segmentation, Smooth transition regression, Reversible Jump MCMC, Non Intrusive Load Monitoring

This paper proposes a Bayesian algorithm to estimate the parameters of a smooth transition regression model. Within this modelling, time series are divided into segments and a linear regression analysis is performed on each segment. Unlike piecewise regression model, smooth transition functions are introduced to model smooth transitions between the sub-models. Appropriate prior distributions are associated with each parameter to penalize a data-driven criterion, leading to a fully Bayesian model. Then, a reversible jump Markov Chain Monte Carlo algorithm is derived to sample the parameter posterior distributions. It allows one to compute standard Bayesian estimators, providing a sparse representation of the data. Results are obtained for real-world electrical transients with a view to non-intrusive load monitoring applications.

INTRODUCTION

Piecewise regression models are a flexible class of regression models that has been widely used for abrupt changes detection [1], or segmentation [START_REF] Punskaya | Bayesian Curve Fitting Using MCMC With Application to Signal Segmentation[END_REF][START_REF] Dobigeon | Joint segmentation of piecewise autoregressive processes by using a hierachical model and a bayesian sampling approach[END_REF] problems. Within this modelling, time series are divided into several segments. Each segment is associated with a specific regime that appears during a time interval. A classical regression analysis is independently performed on each segment. Thus, piecewise regression analysis often reduces to a changepoint detection problem.

However, in many applications, the change among two regimes is not abrupt but rather smooth and classical piecewise regression methods may produce oversegmentated representation of the signal. To avoid this problem, some parametric transition functions are considered for modelling the smooth switch between two regimes. These transition functions are introduced to continuously mix the different regression models associated with neighboring segments. Some similar models have already been studied in econometrics [START_REF] Lubrano | Bayesian Analysis of Nonlinear Time Series Models with a Threshold[END_REF][START_REF] Dick Van Dijk | Smooth transition autoregressive models -a survey on recent development[END_REF], or in railway monitoring applications [START_REF] Chamroukhi | Time series modeling by a regression approach based on a latent process[END_REF] (note that in this case, the smooth switch process is hidden). However these approaches require the number of regimes to be fixed a priori.

When the number of ruptures is unknown, the estimation of the model parameters is a difficult problem. Indeed, it appears to be illposed and requires some regularization to be solved. To circumvent these difficulties, a fully Bayesian framework is introduced. Appropriate priors are associated with each parameter in order to penalize a likelihood-based criterion. As the resulting posterior density appears to be too complex to allow an analytic computation, a reversible jump Markov Chain Monte-Carlo (RJMCMC) sampling method [START_REF] Peter | Reversible Jump Markov chain Monte Carlo computation and Bayesian model determination[END_REF] is investigated. Classical Bayesian estimators are then derived from the MCMC sample, leading to a quite sparse modelling of the original time series. The RJMCMC algorithm is eventually used to provide an accurate and sparse representation of real-world electrical transient data.

This communication is organized as follows. In section 2, the smooth transition regression model is introduced. Section 3 presents the proposed hierarchical Bayesian framework. In section 4, the RJMCMC algorithm is derived for parameters estimation. Results on real-world electrical transients are reported and discussed in 5. Conclusions are drawn in section 6.

SMOOTH TRANSITION REGRESSION MODEL

Model and notations

A sequence of n samples x = (xi)i=1,..,n is considered. The time instant sequence associated with the observations x is denoted as t = (ti)i=1,..,n, while ts is the sampling period. Let τ1 < τ2 < • • • < τK-1 be a configuration of K -1 changepoint locations in the signal, K being the number of segments. For notational convenience, the convention that τ0 = t0 and τK = tn is adopted. In this work, a polynomial regression analysis is performed on each segment. More precisely, the mean value at time ti of the regime associated with the kth segment

[τ k-1 τ k ] is m i,k = X 0≤p≤P β (p) k t p i , ∀ 1 ≤ i ≤ n, (1)
where P is the order of the polynomial, and β

k , . . . , β (P ) k denotes the polynomial coefficients associated with the kth segment

[τ k-1 τ k ].
A transition function denoted as πη k (t) is associated with the kth rupture τ k , for all 0 < k < K. This function is chosen to be monotonically increasing from 0 to 1 and is governed by the vector of parameters η k i.e the rupture locations τ k , and possibly other kind of parameters that characterize the smoothness, or the shape (i.e. sigmoidal, exponential,...) of the rupture. By convention, the transitions associated with the first and last ruptures τ0 and τK are the step functions such that πη 0 (t) = 1 and πη K (t) = 0 for all t0 ≤ t ≤ tn. It yields the following expression of the observation at time ti

xi = X 1≤k≤K ˆπη k-1 (ti) -πη k (ti) ˜mi,k + ǫi, (2)
for all 1 ≤ i ≤ n, where πη k-1 (ti) accounts for the transition from m i,k-1 to m i,k and πη k (ti) accounts for the transition from m i,k to m i,k+1 (see figure 1(a)). The noise vector ǫ = (ǫ1, . . . , ǫn) T is composed of i.i.d. centered Gaussian random variables with variance σ 2 . Let η = [η1, . . . ηK-1] T be the parameter vector of the whole configuration of transitions, while

β = h β (0) 1 , . . . , β (P ) 1 , • • • , β (0)
K , . . . , β (P ) K i T denotes the K(P +1)length column vector of the regression coefficient parameters. An equivalent matrix formulation of the observation model ( 2) is given by

x = Z(η)β + ǫ, (3)
where Z(η) is a n × K(P + 1) matrix of regressors whose entries are the

Z i,(k-1)(P +1)+p+1 = ˆπη k-1 (ti) -πη k (ti) ˜tp i , (4)
for all k ∈ {1 . . . K} and p ∈ {0 . . . P }. Note that the columns of the matrix Z(η) represents the temporal evolution of the regressors. An example of a configuration of transition functions, and the corresponding regressors are depicted in Fig. 1.

τ 0 τ 1 τ 2 τ 3 0 0.5 1 1 st transition function 2 nd transition function (a) τ 0 τ 1 τ 2 τ 3 0 0.5 1 1 st segment 2 nd segment 3 rd segment (b)

Constraint on the configuration of ruptures

Eq. ( 2) induces an additional assumption on the rupture configuration. Indeed, for each segment [τ k-1 τ k ], only the transition functions associated with the (k -1)th rupture τ k-1 and the kth rupture τ k are taken into account. Thus, all the previous transition functions must be close to 1 after τ k-1 , and all the next ones must be close to 0 before τ k . More precisely, the following constraints are added

 1 -πη k-2 (τ k-1 ) < ε πη k+1 (τ k ) < ε ∀k ∈ [2, K -2], (5)
where ε is some very low threshold (basically, ε = 10 -10 ).

Transition function choice and parameterization

A large number of transition function πη are possible, depending on the application. In this paper, the following class of Kohlrausch function [START_REF] Kohlrausch | Theorie des elektrischen rückstandes in der leidener flasche[END_REF] is considered

πη (t) = ( 1 -exp ˆ- `h(α) t-τ λ + g(α) ´α˜f or t > τ -λ g(α) h(α) 0 for t < τ -λ g(α) h(α) (6)
where

g(α) = ( 0 if 0 < α ≤ 1 `α-1 α ´1 α if α > 1, (7)
h(α) = ( 1 α Γ( 1 α ) if 0 < α ≤ 1 h ( α-1 α ) 1 α + 1 α Γ( 1 α ) `1 -2P ( 1 α , α-1 α ) ´i if α > 1. (8) with P (a, x) = 1 Γ(a)
R x 0 t a-1 e -t dt being the incomplete gamma function. Such a family of functions is able to describe a wide range of shapes, from exponential to more symmetric functions such as sigmoids. This specific parameterization ensures that τ and λ match the following definitions :

τ = argmax t dπη dt (t), (9)
λ = Z τ -∞ πη (t)dt + Z +∞ τ [1 -πη (t)]dt. (10)
Finally, by introducing τ = (τ1, . . . , τK-1), λ = (λ1, . . . , λK-1) and α = (α1, . . . , αK-1), the parameter vector associated with the configuration of transitions is η = (τ , λ, α), and the resulting vector of the model parameters is θ = (η, β, K, σ 2 ).

Likelihood model

Based on eq. ( 3), the Gaussian assumption on the noise vector leads to the following expression of the observation likelihood

L(x|θ) = 1 (2πσ 2 ) n e -1 2σ 2 (x-Z(η)β) T (x-Z(η)β) . ( 11
)
When the number of segments K is given, the estimation of the parameters θ reduces to a classical non-linear least mean square problem. However, in the more general case where K is unknown, the problem is obviously ill-posed. In fact, a direct optimization of (11) w.r.t. θ leads to degenerated solutions with possibly as many parameters as observations. Following [START_REF] Punskaya | Bayesian Curve Fitting Using MCMC With Application to Signal Segmentation[END_REF][START_REF] Dobigeon | Joint segmentation of piecewise autoregressive processes by using a hierachical model and a bayesian sampling approach[END_REF], a hierarchical Bayesian approach is proposed to regularize the problem thanks to a fully datadriven criterion.

HIERARCHICAL BAYESIAN MODEL

In a Bayesian framework, the estimation problem is solved by assuming that θ is a random vector whose a priori distribution is known. The same framework as in [START_REF] Sanquer | Bayesian curve fitting for transient signals by using smooth transition regression models[END_REF] is followed.

Parameter priors

A binomial distribution is chosen for the number of segments param-

eter K f (K|µ) = µ K (1 -µ) n-K , ( 12
)
where n is the number of samples, and µ is an hyperparameter. For the parameters β and σ 2 , it is convenient to choose among the family of conjugate prior distributions with respect to the likelihood (11). The inverse gamma distribution for σ 2 is

σ 2 |(ν, ρ) ∼ IG( ν 2 , ρ 2 ), ( 13
)
where ρ is an hyperparameter, the inverse gamma shape parameter ν being fixed to 2. The polynomial coefficients β are characterized through the following conjugate multivariate Gaussian distribution

β|(η, σ 2 , δ 2 ) ∼ N " 0, δ 2 ρ h Z(η) T Z(η) i -1 « . ( 14
)
The main advantage of this parameterization is that the resulting posterior distribution is now invariant to the choice of the polynomial time basis. Moreover, the hyperparameter δ 2 is then recognizable as a signal to noise ratio since

δ 2 = E[(Z(η)β) T (Z(η)β)] nσ 2 . ( 15
)
Unfortunately, it is not possible to choose some conjugate distributions for the parameter vectors λ and α, as the dependence of the likelihood from the parameters is non-standard. Since λ characterizes the spreading times of the ruptures according to (10), a higher bound λmax = tn -t0 is given. Then a truncated inverse-gamma prior is chosen

λ k |(ν ′ , ω) ∼ IG [0 λmax] ( ν ′ 2 , ω 2 ) ∀0 < k < K, (16)
where the shape parameter ν ′ is fixed to 2. Moreover, the values of interest on the stretch exponential shape parameters α k can be bounded such that α k < αmax. Thus, the prior for the parameter α k is chosen to be uniform between 0 and αmax: α k ∼ U [0 αmax] for all 0 < k < K. In this work, αmax is set to 20. Eventually the hyperparameter vector is φ = {µ, ρ, δ 2 , ω}.

Hyperparameter priors

A second level of hierarchy is introduced on the hyperparameter vector φ. It consists of considering some hyperpriors on these hyperparameters. As no further information is available on these hyperparameters, an uniform distribution is chosen for µ, while a vague gamma prior is chosen for ω ∼ G (χ, ψ) (with χ = 1 and scale parameter ψ = 100). For the parameter ρ, an improper noninformative Jeffreys prior is introduced such that f (ρ) = 1 ρ I R+ (ρ). The overall model is then a so called hierarchical Bayesian model.

Finally, a vague conjugate inverse-gamma distribution could be chosen for δ 2 such that δ 2 ∼ IG(∆, Ξ). However, a given value should be prefered in some cases. Indeed, according to equation (15), δ 2 is a signal-to-noise ratio and is then related to the reconstruction error. Setting δ 2 to a given value allows one to control the signal fitting, preventing for example the emergence of too many ruptures.

Joint posterior distribution

The posterior distribution of the parameters θ expresses as

f (θ|x) = Z f (θ, φ|x)dφ ∝ Z L(x|θ)f (θ|φ)f (φ)dφ (17)
In the expression of the joint posterior distribution, the parameters µ, σ 2 and β can be integrated out, yielding the following expression:

f (η, K, ρ, δ 2 |x) ∝ " e -∆ δ 2 (δ 2 ) Ξ+1 « Q K-1 k=1 λ -2 k h 1 ψ + P K-1 k=1 1 2λ k i (χ+n-2) ! × Γ(K+1)Γ(n-1-K)(1+δ 2 ) -K(P +1) 2 " ρ 2 + 1 2 h x T x-δ 2 1+δ 2 (x T Z[Z T Z] -1 Z T x) i" n 2 +1 ! I * (η), (18)
where the indicator function I * (η) is equal to

1 if α k ∈ [0 αmax] and λ k ∈ [0 λmax] for all 0 < k < K and if condition (5) is respected.
Closed-form expressions of the classical Bayesian estimators, namely the maximum a posteriori (MAP) or the minimum mean square error (MMSE), are not tractable from eq. ( 18). The approach driven here is to use a Markov Chain Monte-Carlo (MCMC) algorithm to generate samples from the posterior distribution (18). Baysesian estimates can be then deduced from the empirical distribution of the parameters. As the number of parameters of the model is not given, a RJMCMC sampler is used.

REVERSIBLE-JUMP MCMC ALGORITHM

The RJMCMC algorithm, introduced in [START_REF] Peter | Reversible Jump Markov chain Monte Carlo computation and Bayesian model determination[END_REF], is an extension of the Metropolis-Hastings algorithm to the case where the number of variables is not given. In addition to the classical Metropolis-Hastings moves for updating parameters values, changing-dimension moves are proposed and accepted with arbitrary probabilities. In this paper, the following moves are considered : 1) Birth or death of a rupture, 2) Update of the rupture parameters η k , for all 1 < k < K -1, 3) Update of the hyperparameters φ.

To assess the probability of acceptance for the changingdimension moves, one must choose a probabilistic framework encompassing the whole model space. In this paper, a marked Poisson point process framework is chosen [START_REF] Daley | An Introduction To The Theory Of Point Process[END_REF]. The rupture position τ is the point process, whereas (λ, α) are the associated marks. For each rupture parameter, a reference probability density must be chosen. A probability density l based on the discrete gradient of x is chosen as a prior for the τ k , 0 < k < K -1. This density l represents the intensity function of the marked Poisson point process. This specific choice of reference density reflects the a priori knowledge that the ruptures should coincide with high values of the gradient. This is in agreement with the definition (9) of the parameter τ . In addition, non-informative reference probability densities d(λ) = 1 λ I [0 tn] and m(α) = I [0 αmax] (α) are chosen for the marks λ and α. Finally, the overall reference density for the parameter vector

η k is Q(η k ) = l(τ k )d(λ k )m(α k ).

Proposition distribution

To sample the λ k , a method based on equation ( 10) is used. A subset xs of the observation sequence x is extracted around τ k and is normalized to vary from 0 to 1. The following estimation of λ is obtained

λ = 1 ts X (t<τ k ) (xs(t)) + 1 ts X (t>τ k ) (1 -xs(t)) (19)
The proposition distribution d(λ|η) is then deduced as λ|x ∼ N ( λ, s 2 ), where s 2 = var

h xs -π τ k , λ,α k (t)
i . The rupture location τ and the rupture parameter λ are proposed according to their reference densities l and d respectively. Finally, the proposition distribution for the rupture parameters is P (η|η) = l(τ )d(λ|η)m(α).

Birth/death moves

Let η (x) be the parameter vector associated to the current configuration. In a birth move, a new marked point ηu = (τu, λu, αu) is sampled according to the proposition distribution P (ηu|η (x) ). The proposed new configuration is η (y) = η (x) S ηu, and the corresponding acceptance rate R(η (x) , η (y) ) expresses as

R(η (x) , η (y) ) = f (η (y) , K (y) , ρ, δ 2 |x) f (η (x) , K (x) , ρ, δ 2 |x) p d (ηu|η (y) ) Q(ηu) P (ηu|η (x) )
,

where p d (ηu|η (y) ) is the probability for the rupture u to be selected in the death move, when the current configuration is η (y) : p d (ηu|η (y) ) = 1 K (y) -1 . In a death move, a rupture ηu to be suppressed is selected uniformly from the current configuration η (x) . The proposed new configuration is η (y) = η (x) \ηu and the acceptance rate becomes

R(η (x) , η (y) ) = f (η (y) , K (y) , ρ, δ 2 |x) f (η (x) , K (x) , ρ, δ 2 |x) 1 p d (ηu|η (x) ) P (ηu|η (y) ) Q(ηu)

Update of the rupture parameters

A rupture ηu is chosen uniformly among the current rupture configuration η (x) . This rupture is updated to ηv. The new configuration becomes η (y) = η (x) \ηu S ηv. If ηv is sampled according to P (ηv|η (x) ), then the acceptance rate is:

R(η (x) , η (y) ) = f (η (y) , K (y) , ρ, δ 2 |x) f (η (x) , K (x) , ρ, δ 2 |x) Q(ηv) Q(ηu)
P (ηu|η (x) \ηu) P (ηv|η (y) \ηv)

Update of the hyperparameters

One can deduce from the joint posterior distribution the marginal posterior distribution of each hyperparameter. Then the new values of these hyperparameters are sampled from their true conditional posterior, leading to an acceptance ratio equal to 1. These moves correspond to the classical Gibbs moves.

APPLICATION ON ELECTRICAL TRANSIENT DATA

The algorithm introduced in this paper has been tested on modelling electrical transient signals with a view to non-intrusive load monitoring. In this context, electrical transients are analyzed to detect the turned on appliances of an electrical network. The real-world transients used in this work were provided by Electricité de France (EDF), the French leading company for electricity distribution.

In this paper, an electrical transient due to a fridge turn on event is considered. The transient envelope contains the information useful for the classification task. Thus, the proposed MCMC algorithm is applied to fit this envelope. A polynomial regression model of order P = 0 is applied on each segment. It represents a regime with a constant current consumption level. The following results are obtained in two steps. First the RJMCMC algorithm was run with a given value δ 2 = 20, during 0.5 × 10 4 iterations. This value reflects the desired reconstruction error on the observed signal. Figure 2(e) shows the resulting marginal posterior density of K. Then the same algorithm was run again, but with K = b Kmap = 4 (thus, without birth/death moves), while δ 2 was sampled according to his conditional posterior distribution. During the second step 10 4 iterations were performed. Fig. 2 Although it slightly diverges from the observation around the third rupture, one can see that the signal estimate b

x provides an accurate representation of the observed signal x and sparse as b

x depends on 13 parameters instead of initial 100 samples. The method proposed in this paper has been used for 50 real-world transients with similar results. The parameter estimates will be used in future works as characteristic features of the transient for classification.

CONCLUSION

The development of a Bayesian framework for the joint estimation of the number of segments and the parameters of the flexible smooth transition regression model is the main contribution of this paper. A RJMCMC algorithm is derived to fit a given time serie in a full Bayesian framework. This method has been tested with promising results on the envelope of real-world electrical transients in a nonintrusive load monitoring context.

Fig. 1 .

 1 Fig. 1. Configuration of transition functions and matrix of regressors Z(η) for K = 3 segments. (a) transition functions associated with the two ruptures. (b) columns of the n × K(P + 1) matrix of regressors Z(η) for a first order polynomial (P = 1) regression analysis on each segment. The same color is used for the regressors associated with the same segment k, while solid and dashed lines corresponds to the zero (p = 0) and first (p = 1) order monomial regressors respectively.

  (b)-(c)-(d) show, for each rupture, the posterior distributions for the transition parameters (α k , λ k ), while the posterior distribution of the rupture locations τ , the observed time series and the MMSE estimate b x = Z (b η mmse ) b β mmse of the observed signal x are displayed on Fig. 2(a).

  Michèle Basseville and Igor V. Nikiforov, Detection of abrupt changes : Theory and application, 1993.

  top:(blue dots) observed signal, (red line) MMSE signal estimate bottom:K posterior distribution Fig. 2. Results