Francis Bach
email: francis.bach@ens.fr

Shaping Level Sets with Submodular Functions

We consider a class of sparsity-inducing regularization terms based on submodular functions. While previous work has focused on non-decreasing functions, we explore symmetric submodular functions and their Lovász extensions. We show that the Lovász extension may be seen as the convex envelope of a function that depends on level sets (i.e., the set of indices whose corresponding components of the underlying predictor are greater than a given constant): this leads to a class of convex structured regularization terms that impose prior knowledge on the level sets, and not only on the supports of the underlying predictors. We provide a unified set of optimization algorithms, such as proximal operators, and theoretical guarantees (allowed level sets and recovery conditions). By selecting specific submodular functions, we give a new interpretation to known norms, such as the total variation; we also define new norms, in particular ones that are based on order statistics with application to clustering and outlier detection, and on noisy cuts in graphs with application to change point detection in the presence of outliers.

Introduction

The concept of parsimony is central in many scientific domains. In the context of statistics, signal processing or machine learning, it may take several forms. Classically, in a variable or feature selection problem, a sparse solution with many zeros is sought so that the model is either more interpretable, cheaper to use, or simply matches available prior knowledge (see, e.g., [START_REF] Zhao | On model selection consistency of Lasso[END_REF][START_REF] Negahban | A unified framework for highdimensional analysis of M-estimators with decomposable regularizers[END_REF][START_REF] Bach | Structured sparsity-inducing norms through submodular functions[END_REF] and references therein). In this paper, we instead consider sparsity-inducing regularization terms that will lead to solutions with many equal values. A classical example is the total variation in one or two dimensions, which leads to piecewise constant solutions [START_REF] Tibshirani | Sparsity and smoothness via the fused Lasso[END_REF][START_REF] Chambolle | On total variation minimization and surface evolution using parametric maximum flows[END_REF] and can be applied to various image labelling problems [START_REF] Boykov | Fast approximate energy minimization via graph cuts[END_REF][START_REF] Chambolle | On total variation minimization and surface evolution using parametric maximum flows[END_REF], or change point detection tasks [START_REF] Harchaoui | Catching change-points with Lasso[END_REF][START_REF] Vert | Fast detection of multiple change-points shared by many signals using group LARS[END_REF][START_REF] Kolar | Sparsistent learning of varying-coefficient models with structural changes[END_REF]. Another example is the "Oscar" penalty which induces automatic grouping of the features [START_REF] Bondell | Simultaneous regression shrinkage, variable selection, and supervised clustering of predictors with oscar[END_REF]. In this paper, we follow the approach of [START_REF] Bach | Structured sparsity-inducing norms through submodular functions[END_REF], who designed sparsity-inducing norms based on non-decreasing submodular functions, as a convex approximation to imposing a specific prior on the supports of the predictors. Here, we show that a similar parallel holds for some other class of submodular functions, namely non-negative setfunctions which are equal to zero for the full and empty set. Our main instance of such functions are symmetric submodular functions.

We make the following contributions:

-We provide in Section 3 explicit links between priors on level sets and certain submodular functions: we show that the Lovász extensions (see, e.g., [START_REF] Bach | Convex analysis and optimization with submodular functions: a tutorial[END_REF] and a short review in Section 2) associated to these submodular functions are the convex envelopes (i.e., tightest convex lower bounds) of specific functions that depend on all level sets of the underlying vector.

-In Section 4, we reinterpret existing norms such as the total variation and design new norms, based on noisy cuts or order statistics. We propose applications to clustering and outlier detection, as well as to change point detection in the presence of outliers.

-We provide unified algorithms in Section 5, such as proximal operators, which are based on a sequence of submodular function minimizations (SFMs), when such SFMs are efficient, or by adapting the generic slower approach of [START_REF] Bach | Structured sparsity-inducing norms through submodular functions[END_REF] otherwise.

-We derive unified theoretical guarantees for level set recovery in Section 6, showing that even in the absence of correlation between predictors, level set recovery is not always guaranteed, a situation which is to be contrasted with traditional support recovery situations [START_REF] Zhao | On model selection consistency of Lasso[END_REF][START_REF] Bach | Structured sparsity-inducing norms through submodular functions[END_REF].

Notation. For w ∈ R p and q ∈ [1, ∞], we denote by w q the ℓ q -norm of w. Given a subset A of V = {1, . . . , p}, 1 A ∈ {0, 1} p is the indicator vector of the subset A. Moreover, given a vector w and a matrix Q, w A and Q AA denote the corresponding subvector and submatrix of w and Q. Finally, for w ∈ R p and A ⊂ V , w(A) = k∈A w k = w ⊤ 1 A (this defines a modular set-function). In this paper, for a certain vector w ∈ R p , we call level sets the sets of indices which are larger (or smaller) or equal to a certain constant α, which we denote {w α} (or {w α}), while we call constant sets the sets of indices which are equal to a constant α, which we denote {w = α}.

Review of Submodular Analysis

In this section, we review relevant results from submodular analysis. For more details, see, e.g., [START_REF] Fujishige | Submodular Functions and Optimization[END_REF], and, for a review with proofs derived from classical convex analysis, see, e.g., [START_REF] Bach | Convex analysis and optimization with submodular functions: a tutorial[END_REF].

Definition. Throughout this paper, we consider a submodular function F defined on the power set 2 V of V = {1, . . . , p}, i.e., such that ∀A, B ⊂ V, F (A) + F (B) F (A ∪ B) + F (A ∩ B). Unless otherwise stated, we consider functions which are non-negative (i.e., such that F (A) 0 for all A ⊂ V ), and that satisfy F (∅) = F (V ) = 0. Usual examples are symmetric submodular functions, i.e., such that ∀A ⊂ V, F (V \A) = F (A), which are known to always have non-negative values. We give several examples in Section 4; for illustrating the concepts introduced in this section and Section 3, we will consider the cut in an undirected chain graph, i.e.,

F (A) = p-1 j=1 |(1 A ) j -(1 A ) j+1 |. Lovász extension.
Given any set-function F such that F (V ) = F (∅) = 0, one can define its Lovász extension f : R p → R, as f (w) = R F ({w α})dα (see, e.g., [START_REF] Bach | Convex analysis and optimization with submodular functions: a tutorial[END_REF] for this particular formulation). The Lovász extension is convex if and only if F is submodular. Moreover, f is piecewise-linear and for all A ⊂ V , f (1 A ) = F (A), that is, it is indeed an extension from 2 V (which can be identified to {0, 1} p through indicator vectors) to R p . Finally, it is always positively homogeneous. For the chain graph, we obtain the usual total variation f (w [START_REF] Fujishige | Submodular Functions and Optimization[END_REF], where we use the notation s(A) = k∈A s k . One important result in submodular analysis is that if F is a submodular function, then we have a representation of f as a maximum of linear functions [START_REF] Fujishige | Submodular Functions and Optimization[END_REF][START_REF] Bach | Convex analysis and optimization with submodular functions: a tutorial[END_REF], i.e., for all w ∈ R p , f (w) = max s∈B(F ) w ⊤ s. Moreover, instead of solving a linear program with 2 p contraints, a solution s may be obtained by the following "greedy algorithm": order the components of w in decreasing order w j1 • • • w jp , and then take for all k ∈ {1, . . . , p}, s

) = p-1 j=1 |w j -w j+1 |. Base polyhedron. We denote by B(F ) = {s ∈ R p , ∀A ⊂ V, s(A) F (A), s(V ) = F (V )} the base polyhedron
j k = F ({j 1 , . . . , j k }) -F ({j 1 , . . . , j k-1 }).
Tight and inseparable sets. The polyhedra U = {w ∈ R p , f (w) 1} and B(F ) are polar to each other (see, e.g., [START_REF] Rockafellar | Convex Analysis[END_REF] for definitions and properties of polar sets). Therefore, the facial structure of U may be obtained from the one of B(F

). Given s ∈ B(F ), a set A ⊂ V is said tight if s(A) = F (A).
It is known that the set of tight sets is a distributive lattice, i.e., if A and B are tight, then so are A ∪ B and A ∩ B [START_REF] Fujishige | Submodular Functions and Optimization[END_REF][START_REF] Bach | Convex analysis and optimization with submodular functions: a tutorial[END_REF]. The faces of B(F ) are thus intersections of hyperplanes {s(A) = F (A)} for A belonging to certain distributive lattices (see Prop. 3). A set A is said separable if there exists a non-trivial partition of A = B ∪ C such that F (A) = F (B) + F (C). A set is said inseparable if it is not separable. For the cut in an undirected graph, inseparable sets are exactly connected sets.

Properties of the Lovász Extension

In this section, we derive properties of the Lovász extension for submodular functions, which go beyond convexity and homogeneity. Throughout this section, we assume that F is a non-negative submodular set-function that is equal to zero at ∅ and V . This immediately implies that f is invariant by addition of any constant vector (that is, f (w + α1 V ) = f (w) for all w ∈ R p and α ∈ R), and that f (1 V ) = F (V ) = 0. Thus, contrary to the non-decreasing case [START_REF] Bach | Structured sparsity-inducing norms through submodular functions[END_REF], our regularizers are not norms. However, they are norms on the hyperplane {w ⊤ 1 V = 0} as soon as for A = ∅ and A = V , F (A) > 0 (which we assume for the rest of this paper).

We now show that the Lovász extension is the convex envelope of a certain combinatorial function which does depend on all levets sets {w α} of w ∈ R p (see proof in supplementary material):

Proposition 1 (Convex envelope) The Lovász extension f (w) is the convex envelope of the func- tion w → max α∈R F ({w α}) on the set [0, 1] p + R1 V = {w ∈ R p , max k∈V w k -min k∈V w k 1}.
Note the difference with the result of [START_REF] Bach | Structured sparsity-inducing norms through submodular functions[END_REF]: we consider here a different set on which we compute the convex envelope ([0, 1] p + R1 V instead of [-1, 1] p ), and not a function of the support of w, but of all its level sets. 1 Moreover, the Lovász extension is a convex relaxation of a function of level sets (of the form {w α}) and not of constant sets (of the form {w = α}). It would have been perhaps more intuitive to consider for example R F ({w = α})dα, since it does not depend on the ordering of the values that w may take; however, the latter function does not lead to a convex function amenable to polynomial-time algorithms. This definition through level sets will generate some potentially undesired behavior (such as the well-known staircase effect for the one-dimensional total variation), as we show in Section 6.

The next proposition describes the set of extreme points of the "unit ball" U = {w, f (w) 1}, giving a first illustration of sparsity-inducing effects (see example in Figure 1).

Proposition 2 (Extreme points)

The extreme points of the set U ∩ {w ⊤ 1 V = 0} are the projections of the vectors

1 A /F (A) on the plane {w ⊤ 1 V = 0}, for A such that A is inseparable for F and V \A is inseparable for B → F (A ∪ B) -F (A).
Partially ordered sets and distributive lattices. A subset D of 2 V is a (distributive) lattice if it is invariant by intersection and union. We assume in this paper that all lattices contain the empty set ∅ and the full set V , and we endow the lattice with the inclusion order. Such lattices may be represented as a partially ordered set (poset) Π(D) = {A 1 , . . . , A m } (with order relationship ), where the sets A j , j = 1, . . . , m, form a partition of V (we always assume a topological ordering of the sets, i.e., A i A j ⇒ i j). As illustrated in Figure 2, we go from D to Π(D), by considering all maximal chains in D and the differences between consecutive sets. We go from Π(D) to D, by constructing all ideals of Π(D), i.e., sets J such that if an element of Π(D) is lower than an element w > w >w w > w >w 3 (0,1,1)/F({2,3}) (0,0,1)/F({3}) (1,0,1)/F({1,3})

(1,0,0)/F({1}) (1,1,0)/F({1,2}) (0,1,0)/F({2}) 3 (0,1,0)/2 (0,0,1) (0,1,1) (1,0,1)/2
(1,0,0) (1,1,0) Figure 1: Top: Polyhedral level set of f (projected on the set w ⊤ 1 V = 0), for 2 different submodular symmetric functions of three variables, with different inseparable sets leading to different sets of extreme points; changing values of F may make some of the extreme points disappear. The various extreme points cut the space into polygons where the ordering of the component is fixed. Left: F (A) = 1 |A|∈{1,2} (all possible extreme points); note that the polygon need not be symmetric in general. Right: one-dimensional total variation on three nodes, i.e., Hasse diagram corresponding to the order (a node points to its immediate smaller node according to ). Note that this corresponds to an "allowed" lattice (see Prop.

F (A) = |1 1∈A -1 2∈A | + |1 2∈A - 1 3∈A |, leading to f (w) = |w 1 -w 2 | + |w 2 -w 3 |,
3) for the one-dimensional total variation.

of J, then it has to be in J (see [START_REF] Fujishige | Submodular Functions and Optimization[END_REF] for more details, and an example in Figure 2). Distributive lattices and posets are thus in one-to-one correspondence. Throughout this section, we go back and forth between these two representations. The distributive lattice will correspond to all authorized level sets {w α} in a single face of U, while the elements of the poset are the constant sets (over which w is constant), with the order between the subsets giving partial constraints between the values of the corresponding constants.

Faces of U. The faces of U are characterized by lattices D, with their corresponding posets Π(D) = {A 1 , . . . , A m }. We denote by U • D (and by U D its closure) the set of w ∈ R p such that (a) w is piecewise constant with respect to Π(D), with value v i on A i , and (b) for all pairs (i, j),

A i A j ⇒ v i > v j .
For certain lattices D, these will be exactly the relative interiors of all faces of U:

Proposition 3 (Faces of U) The (non-empty) relative interiors of all faces of U are exactly of the form U • D , where D is a lattice such that: (i) the restriction of F to D is modular, i.e., for all A, B ∈ D, F (A) + F (B) = F (A ∪ B) + F (A ∩ B), (ii) for all j ∈ {1, . . . , m}, the set A j is inseparable for the function C j → F (B j-1 ∪ C j ) -F (B j-1 )
, where B j-1 is the union of all ancestors of A j in Π(D), (iii) among all lattices corresponding to the same unordered partition, D is a maximal element of the set of lattices satisfying (i) and (ii). Left: original signal. Middle: best estimation with total variation (level sets are not correctly estimated). Right: best estimation with the robust total variation based on noisy cut functions (level sets are correctly estimated, with less bias and with detection of outliers). Right plot: clustering estimation error vs. noise level, in a sequence of 100 variables, with a single jump, where noise of variance one is added, with 5% of outliers (averaged over 20 replications).

Among the three conditions, the second one is the easiest to interpret, as it reduces to having constant sets which are inseparable for certain submodular functions, and for cuts in an undirected graph, these will exactly be connected sets.

Since we are able to characterize all faces of U (of all dimensions) with non-empty relative interior, we have a partition of the space and any w ∈ R p which is not proportional to 1 V , will be, up to the strictly positive constant f (w), in exactly one of these relative interiors of faces; we refer to this lattice as the lattice associated to w. Note that from the face w belongs to, we have strong constraints on the constant sets, but we may not be able to determine all level sets of w, because only partial constraints are given by the order on Π(D). For example, in Figure 2, w 2 may be larger or smaller than w 5 = w 6 (and even potentially equal, but with zero probability, see Section 6).

Examples of Submodular Functions

In this section, we provide examples of submodular functions and of their Lovász extensions. Some are well-known (such as cut functions and total variations), some are new in the context of supervised learning (regular functions), while some have interesting effects in terms of clustering or outlier detection (cardinality-based functions).

Symmetrization. From any submodular function G, one may define

F (A) = G(A) + G(V \A) - G(∅) -G(V ), which is symmetric.
Potentially interesting examples which are beyond the scope of this paper are mutual information, or functions of eigenvalues of submatrices [START_REF] Bach | Structured sparsity-inducing norms through submodular functions[END_REF].

Cut functions. Given a set of nonnegative weights

d : V × V → R + , define the cut F (A) = k∈A,j∈V \A d(k, j). The Lovász extension is equal to f (w) = k,j∈V d(k, j)(w k -w j ) +
(which shows submodularity because f is convex), and is often referred to as the total variation. If the weight function d is symmetric, then the submodular function is also symmetric. In this case, it can be shown that inseparable sets for functions A → F (A ∪ B) -F (B) are exactly connected sets. Hence, constant sets are connected sets, which is the usual justification behind the total variation. Note however that some configurations of connected sets are not allowed due to the other conditions in Prop. 3 (see examples in Section 6). In Figure 5 (right plot), we give an example of the usual chain graph, leading to the one-dimensional total variation [START_REF] Tibshirani | Sparsity and smoothness via the fused Lasso[END_REF][START_REF] Chambolle | On total variation minimization and surface evolution using parametric maximum flows[END_REF]. Note that these functions can be extended to cuts in hypergraphs, which may have interesting applications in computer vision [START_REF] Boykov | Fast approximate energy minimization via graph cuts[END_REF]. Moreover, directed cuts may be interesting to favor increasing or decreasing jumps along the edges of the graph.

Regular functions and robust total variation. By partial minimization, we obtain so-called regular functions [START_REF] Boykov | Fast approximate energy minimization via graph cuts[END_REF][START_REF] Chambolle | On total variation minimization and surface evolution using parametric maximum flows[END_REF]. One application is "noisy cut functions": for a given weight function d : W × W → R + , where each node in W is uniquely associated in a node in V , we consider the submodular function obtained as the minimum cut adapted to A in the augmented graph (see right plot of Figure 5): F (A) = min B⊂W k∈B, j∈W \B d(k, j) + λ|A∆B|. This allows for robust versions of cuts, where some gaps may be tolerated. See examples in Figure 3, illustrating the behavior of the type of graph displayed in the bottom-right plot of Figure 5, where the performance of the robust total variation is significantly more stable in presence of outliers.

Cardinality-based functions. For F (A) = h(|A|) where h is such that h(0) = h(p) = 0 and h concave, we obtain a submodular function, and a Lovász extension that depends on the order statistics of w, i.e., if

w j1 • • • w jp , then f (w) = p-1 k=1 h(k)(w j k -w j k+1 ).
While these examples do not provide significantly different behaviors for the non-decreasing submodular functions explored by [START_REF] Bach | Structured sparsity-inducing norms through submodular functions[END_REF] (i.e., in terms of support ), they lead to interesting behaviors here in terms of level sets, i.e., they will make the components w cluster together in specific ways. Indeed, as shown in Section 6, allowed constant sets A are such that A is inseparable for the function C → h(|B ∪ C|) -h(|B|) (where B ⊂ V is the set of components with higher values than the ones in A), which imposes that the concave function h is not linear on [|B|, |B|+|A|]. We consider the following examples:

1. F (A) = |A| • |V \A|, leading to f (w) = p i,j=1 |w i -w j |.
This function can thus be also seen as the cut in the fully connected graph. All patterns of level sets are allowed as the function h is strongly concave (see left plot of Figure 4). This function has been extended in [START_REF] Hocking | Clusterpath: an algorithm for clustering using convex fusion penalties[END_REF] by considering situations where each w j is a vector, instead of a scalar, and replacing the absolute value |w i -w j | by any norm w i -w j , leading to convex formulations for clustering.

2. F (A) = 1 if A = ∅ and A = V , and 0 otherwise, leading to f (w) = max i,j |w i -w j |. Two large level sets at the top and bottom, all the rest of the variables are in-between and separated (Figure 4, second plot from the left).

3. F (A) = max{|A|, |V \A|}. This function is piecewise affine, with only one kink, thus only one level set of cardinalty greater than one (in the middle) is possible, which is observed in Figure 4 (third plot from the left). This may have applications to multivariate outlier detection by considering extensions similar to [START_REF] Hocking | Clusterpath: an algorithm for clustering using convex fusion penalties[END_REF].

Optimization Algorithms

In this section, we present optimization methods for minimizing convex objective functions regularized by the Lovász extension of a submodular function. These lead to convex optimization problems, which we tackle using proximal methods (see, e.g., [START_REF] Beck | A fast iterative shrinkage-thresholding algorithm for linear inverse problems[END_REF]). We first start by mentioning that subgradients may easily be derived (but subgradient descent is here rather inefficient as shown in Figure 5). Moreover, note that with the square loss, the regularization paths are piecewise affine, as a direct consequence of regularizing by a polyhedral function.

Subgradient. From f (w) = max s∈B(F ) s ⊤ w and the greedy algorithm2 presented in Section 2, one can easily get in polynomial time one subgradient as one of the maximizers s. This allows to use subgradient descent, with slow convergence compared to proximal methods (see Figure 5).

Proximal problems through sequences of submodular function minimizations (SFMs).

Given regularized problems of the form min w∈R p L(w) + λf (w), where L is differentiable with 1)) for different functions of cardinality. From left to right: quadratic function (all level sets allowed), second example in Section 4 (two large level sets at the top and bottom), piecewise linear with two pieces (a single large level set in the middle). Right: Same plot for the one-dimensional total variation. Note that in both cases the regularization paths for orthogonal designs are agglomerative (see Section 5), while for general designs, they would still be piecewise affine but not agglomerative.

Lipschitz-continuous gradient, proximal methods have been shown to be particularly efficient firstorder methods (see, e.g., [START_REF] Beck | A fast iterative shrinkage-thresholding algorithm for linear inverse problems[END_REF]). In this paper, we use the method "ISTA" and its accelerated variant "FISTA" [START_REF] Beck | A fast iterative shrinkage-thresholding algorithm for linear inverse problems[END_REF]. To apply these methods, it suffices to be able to solve efficiently:

min w∈R p 1 2 w -z 2 2 + λf (w), (1)
which we refer to as the proximal problem. It is known that solving the proximal problem is related to submodular function minimization (SFM). More precisely, the minimum of A → λF (A) -z(A) may be obtained by selecting negative components of the solution of a single proximal problem [START_REF] Fujishige | Submodular Functions and Optimization[END_REF][START_REF] Bach | Convex analysis and optimization with submodular functions: a tutorial[END_REF].

Alternatively, the solution of the proximal problem may be obtained by a sequence of at most p submodular function minimizations of the form A → λF (A) -z(A), by a decomposition algorithm adapted from [START_REF] Groenevelt | Two algorithms for maximizing a separable concave function over a polymatroid feasible region[END_REF], and described in [START_REF] Bach | Convex analysis and optimization with submodular functions: a tutorial[END_REF].

Thus, computing the proximal operator has polynomial complexity since SFM has polynomial complexity. However, it may be too slow for practical purposes, as the best generic algorithm has complexity O(p 6 ) [17]3 . Nevertheless, this strategy is efficient for families of submodular functions for which dedicated fast algorithms exist:

-Cuts: Minimizing the cut or the partially minimized cut, plus a modular function, may be done with a min-cut/max-flow algorithm (see, e.g., [START_REF] Boykov | Fast approximate energy minimization via graph cuts[END_REF][START_REF] Chambolle | On total variation minimization and surface evolution using parametric maximum flows[END_REF]). For proximal methods, we need in fact to solve an instance of a parametric max-flow problem, which may be done using other efficient dedicated algorithms [START_REF] Gallo | A fast parametric maximum flow algorithm and applications[END_REF][START_REF] Chambolle | On total variation minimization and surface evolution using parametric maximum flows[END_REF] than the decomposition algorithm derived from [START_REF] Groenevelt | Two algorithms for maximizing a separable concave function over a polymatroid feasible region[END_REF].

-Functions of cardinality: minimizing functions of the form A → λF (A) -z(A) can be done in closed form by sorting the elements of z.

Proximal problems through minimum-norm-point algorithm. In the generic case (i.e., beyond cuts and cardinality-based functions), we can follow [START_REF] Bach | Structured sparsity-inducing norms through submodular functions[END_REF]: since f (w) is expressed as a minimum of linear functions, the problem reduces to the projection on the polytope B(F ), for which we happen to be able to easily maximize linear functions (using the greedy algorithm described in Section 2). This can be tackled efficiently by the minimum-norm-point algorithm [START_REF] Fujishige | Submodular Functions and Optimization[END_REF], which iterates between orthogonal projections on affine subspaces and the greedy algorithm for the submodular function 4 . We compare all optimization methods on synthetic examples in Figure 5. Proximal path as agglomerative clustering. When λ varies from zero to +∞, then the unique optimal solution of Eq. ( 1) goes from z to a constant. We now provide conditions under which the regularization path of the proximal problem may be obtained by agglomerative clustering (see examples in Figure 4): Proposition 4 (Agglomerative clustering) Assume that for all sets A, B such that B ∩ A = ∅ and A is inseparable for D → F (B ∪ D) -F (B), we have:

∀C ⊂ A, |C| |A| [F (B ∪ A) -F (B)] F (B ∪ C) -F (B). ( 2
)
Then the regularization path for Eq. ( 1) is agglomerative, that is, if two variables are in the same constant for a certain µ ∈ R + , so are they for all larger λ µ.

As shown in the supplementary material, the assumptions required for by Prop. 4 are satisfied by (a) all submodular set-functions that only depend on the cardinality, and (b) by the one-dimensional total variation-we thus recover and extend known results from [START_REF] Harchaoui | Catching change-points with Lasso[END_REF][START_REF] Hoefling | A path algorithm for the fused Lasso signal approximator[END_REF][START_REF] Hocking | Clusterpath: an algorithm for clustering using convex fusion penalties[END_REF].

Adding an ℓ 1 -norm. Following [START_REF] Tibshirani | Sparsity and smoothness via the fused Lasso[END_REF], we may add the ℓ 1 -norm w 1 for additional sparsity of w (on top of shaping its level sets). The following proposition extends the result for the one-dimensional total variation [START_REF] Tibshirani | Sparsity and smoothness via the fused Lasso[END_REF][START_REF] Mairal | Online learning for matrix factorization and sparse coding[END_REF] to all submodular functions and their Lovász extensions:

Proposition 5 (Proximal problem for ℓ 1 -penalized problems) The unique minimizer of 1 2 wz 2 2 + f (w) + λ w 1 may be obtained by soft-thresholding the minimizers of 1 2 w -z 2 2 + f (w). That is, the proximal operator for f + λ • 1 is equal to the composition of the proximal operator for f and the one for λ • 1 .

Sparsity-inducing Properties

Going from the penalization of supports to the penalization of level sets introduces some complexity and for simplicity in this section, we only consider the analysis in the context of orthogonal design matrices, which is often referred to as the denoising problem, and in the context of level set estimation already leads to interesting results. That is, we study the global minimum of the proximal problem in Eq. ( 1) and make some assumption regarding z (typically z = w * + noise), and provide guarantees related to the recovery of the level sets of w * . We first start by characterizing the allowed level sets, showing that the partial constraints defined in Section 3 on faces of {f (w) 1} do not create by chance further groupings of variables (see proof in supplementary material).

Proposition 6 (Stable constant sets) Assume z ∈ R p has an absolutely continuous density with respect to the Lebesgue measure. Then, with probability one, the unique minimizer ŵ of Eq. ( 1) has constant sets that define a partition corresponding to a lattice D defined in Prop. [START_REF] Bach | Structured sparsity-inducing norms through submodular functions[END_REF].

We now show that under certain conditions the recovered constant sets are the correct ones: Theorem 1 (Level set recovery) Assume that z = w * +σε, where ε ∈ R p is a standard Gaussian random vector, and z * is consistent with the lattice D and its associated poset Π(D) = (A 1 , . . . , A m ), with values v * j on A j , for j ∈ {1, . . . , m}. Denote B j = A 1 ∪ • • • ∪ A j for j ∈ {1, . . . , m}. Assume that there exists some constants η j > 0 and ν > 0 such that:

∀C j ⊂ A j , F (B j-1 ∪C j )-F (B j-1 )- |Cj | |Aj | [F (B j-1 ∪A j )-F (B j-1 )] η j min |Cj| |Aj| , 1- |Cj | |Aj | , (3) ∀i, j ∈ {1, . . . , m}, A i A j ⇒ v * i -v * j ν, (4)
∀j ∈ {1, . . . , m}, λ

F (Bj )-F (Bj-1) |Aj | ν/4. ( 5
)
Then the unique minimizer ŵ of Eq. ( 1) is associated to the same lattice D than w * , with probability greater than 1 -

m j=1 exp - ν 2 |Aj | 32σ 2 -2 m j=1 |A j | exp - λ 2 η 2 j 2σ 2 |Aj | 2 .
We now discuss the three main assumptions of Theorem 1 as well as the probability estimate:

-Eq. ( 3) is the equivalent of the support recovery of the Lasso [START_REF] Zhao | On model selection consistency of Lasso[END_REF] or its extensions [START_REF] Bach | Structured sparsity-inducing norms through submodular functions[END_REF]. The main difference is that for support recovery, this assumption is always met for orthogonal designs, while here it is not always met. Interestingly, the validity of level set recovery implies the agglomerativity of proximal paths (Eq. ( 2) in Prop. 4).

Note that if Eq. ( 3) is satisfied only with η j 0 (it is then exactly Eq. ( 2) in Prop. 4), then, even with infinitesimal noise, one can show that in some cases, the wrong level sets may be obtained with non vanishing probability, while if η j is strictly negative, one can show that in some cases, we never get the correct level sets. Eq. ( 3) is thus essentially sufficient and necessary.

-Eq. ( 4) corresponds to having distinct values of w * far enough from each other.

-Eq. ( 5) is a constraint on λ which controls the bias of the estimator: if it is too large, then there may be a merging of two clusters.

-In the probability estimate, the second term is small if all σ 2 |A j | -1 are small enough (i.e., given the noise, there is enough data to correctly estimate the values of the constant sets) and the third term is small if λ is large enough, to avoid that clusters split.

One-dimensional total variation. In this situation, we always get η j = 0, but in some cases, it cannot be improved (i.e., the best possible η j is equal to zero), and as shown in the supplementary material, this occurs as soon as there is a "staircase", i.e., a piecewise constant vector, with a sequence of at least two consecutive increases, or two consecutive decreases, showing that in the presence of such staircases, one cannot have consistent support recovery, which is a well-known issue in signal processing (typically, more steps are created). If there is no staircase effect, we have η j = 1 and Eq. ( 5) becomes λ ν 8 min j |A j |. If we take λ equal to the limiting value in Eq. ( 5), then we obtain a probability less than 1 -4p exp(-

ν 2 minj |Aj | 2 128σ 2 maxj |Aj| 2 )
. Note that we could also derive general results when an additional ℓ 1 -penalty is used, thus extending results from [START_REF] Rinaldo | Properties and refinements of the fused Lasso[END_REF]. Two-dimensional total variation. In this situation, even with only two different values for z * , then we may have η j < 0, leading to additional problems, which has already been noticed in continuous settings (see, e.g., [START_REF] Duval | The TVL1 model: A geometric point of view[END_REF] and the supplementary material).

Clustering with F (A) = |A| • |V \A|. In this case, we have η j = |A j |/2, and Eq. ( 5) becomes λ ν 4p , leading to the probability of correct support estimation greater than 1 -4p exp -ν 2 128pσ 2 . This indicates that the noise variance σ 2 should be small compared to 1/p, which is not satisfactory and would be corrected with the weighting schemes proposed in [START_REF] Hocking | Clusterpath: an algorithm for clustering using convex fusion penalties[END_REF].

Conclusion

We have presented a family of sparsity-inducing norms dedicated to incorporating prior knowledge or structural constraints on the level sets of linear predictors. We have provided a set of common algorithms and theoretical results, as well as simulations on synthetic examples illustrating the behavior of these norms. Several avenues are worth investigating: first, we could follow current practice in sparse methods, e.g., by considering related adapted concave penalties to enhance sparsity-inducing capabilities, or by extending some of the concepts for norms of matrices, with potential applications in matrix factorization [START_REF] Srebro | Maximum-margin matrix factorization[END_REF] or multi-task learning [START_REF] Argyriou | Convex multi-task feature learning[END_REF].

A Proof of Proposition 1

Proof For any w ∈ R p , level sets of w are characterized by an ordered partition (A 1 , . . . , A m ) so that w is constant on each A j , with value t j , j = 1, . . . , m, and so that (t j ) is a strictly decreasing sequence. We can now decompose minimization with respect to w using these ordered partitions and (t j ).

In order to compute the convex envelope, we simply need to compute twice the Fenchel conjugate of the function we want to find the envelope of (see, e.g., [START_REF] Boyd | Convex Optimization[END_REF][START_REF] Borwein | Convex Analysis and Nonlinear Optimization: Theory and Examples[END_REF] for definitions and properties of Fenchel conjugates).

Let s ∈ R p ; we consider the function g : w → max α∈R F ({w α}), and we compute its Fenchel conjugate:

g * (s) def = max w∈[0,1] p +R1V w ⊤ s -g(w), = max (A1,...,Am) partition max t1>•••>tm, t1-tm 1 m j=1 t j s(A j ) -max j∈{1,...,m} F (A 1 ∪ • • • ∪ A j ) , = max (A1,...,Am) partition max t1>•••>tm, t1-tm 1 m-1 j=1 (t j -t j+1 )s(A 1 ∪ • • • ∪ A j ) + t m s(V ) -max j∈{1,...,m} F (A 1 ∪ • • • ∪ A j ) by integration by parts, = ι s(V )=0 (s) + max (A1,...,Am) partition max j∈{1,...,m-1} s(A 1 ∪ • • • ∪ A j ) -max j∈{1,...,m} F (A 1 ∪ • • • ∪ A j ) ,
= ι s(V )=0 (s) + max (A1,...,Am) partition max j∈{1,...,m-1}

s(A 1 ∪ • • • ∪ A j ) - max j∈{1,...,m-1} F (A 1 ∪ • • • ∪ A j ) ,
where ι s(V )=0 is the indicator function of the set {s(V ) = 0} (with values 0 or +∞). Note that max j∈{1,...,m}

F (A 1 ∪ • • • ∪ A j ) = max j∈{1,...,m-1} F (A 1 ∪ • • • ∪ A j ) because F (V ) = 0.
Let h(s) = ι s(V )=0 (s) + max A⊂V {s(A) -F (A)}. We clearly have g * (s) h(s), because we take a maximum over a larger set (consider m = 2). Moreover, for all partitions (A 1 , . . . , A m ), if s(V ) = 0, max j∈{1,...,m-1} s(A

1 ∪ • • • ∪ A j ) max j∈{1,...,m-1} (h(s) + F (A 1 ∪ • • • ∪ A j )) = h(s) + max j∈{1,...,m-1} F (A 1 ∪ • • • ∪ A j )
, which implies that g * (s) h(s). Thus g * (s) = h(s).

Moreover, we have, since f is invariant by adding constants and f is submodular,

max w∈[0,1] p +R1V w ⊤ s -f (w) = ι s(V )=0 (s) + max w∈[0,1] p {w ⊤ s -f (w)} = ι s(V )=0 (s) + max A⊂V {s(A) -F (A)} = h(s),
where we have used the fact that minimizing a submodular function is equivalent to minimizing its Lovász extension on the unit hypercube. Thus f and g have the same Fenchel conjugates. The result follows from the convexity of f , using the fact the convex envelope is the Fenchel bi-conjugate [START_REF] Boyd | Convex Optimization[END_REF][START_REF] Borwein | Convex Analysis and Nonlinear Optimization: Theory and Examples[END_REF].

Note that

z -M v = (I -M (M ⊤ M ) -1 M ⊤ )z + λM (M ⊤ M ) -1 t,
and that for all i ∈ {1, . . . , m},

1 ⊤ Ai (I -M (M ⊤ M ) -1 M ⊤ )z = δ ⊤ i M ⊤ (I -M (M ⊤ M ) -1 M ⊤ )z = 0,
where δ i is indicator vector of the singleton {i}. Moreover, we have

1 ⊤ Ai M (M ⊤ M ) -1 t = t i = F (A 1 ∪ • • • ∪ A i ) -F (A 1 ∪ • • • ∪ A i-1 ), so that, if B i = A 1 ∪ • • • ∪ A i , [(I -M (M ⊤ M ) -1 M ⊤ )z](B i ) = 0, [M (M ⊤ M ) -1 t](B i ) = F (B i ), for all i ∈ {1, . . . , m}. This implies that 1 λ (z -M v) (A i ) = t i , and thus 1 λ (z -M v) (B i ) = F (B i
). Thus, if (a) is satisfied, then (b) is always satisfied. Thus to check if a certain lattice leads to the optimal solution, we simply have to check that 1

λ (I -M (M ⊤ M ) -1 M ⊤ )z + M (M ⊤ M ) -1 t ∈ B(F ).
We now turn to the proof of Proposition 4.

Proof We show that when λ increases, we move to a lattice which has to be merging some constant sets. Let us assume that a lattice D is optimal for a certain µ. Then, from Lemma 1, we have

1 µ (I -M (M ⊤ M ) -1 M ⊤ )z + M (M ⊤ M ) -1 t ∈ B(F ).
Moreover, since from Prop. 3, A i is separable for

C i → F (B i-1 ∪C i )-F (B i-1
), from the assumption of the proposition, we obtain:

∀C i ⊂ A i , [M (M ⊤ M ) -1 t](C i ) = |C i | |A i | (F (B i-1 ∪ A i ) -F (B i-1 )) F (B i-1 ∪ C i ) -F (B i-1 ),
which implies, for all C ⊂ V :

[M (M ⊤ M ) -1 t](C) = m j=1 [M (M ⊤ M ) -1 t](C ∩ A i ) by modularity, m i=1 F (B i-1 ∪ (C ∩ A i )) -F (B i-1 ) from above, m i=1 F ((B i-1 ∩ C) ∪ (C ∩ A i )) -F (B i-1 ∩ C) by submodularity, = m i=1 F (B i ∩ C) -F (B i-1 ∩ C) = F (C).
Thus, for any set C, we have for λ µ (which implies µ λ ∈ [0, 1]),

1 λ (I -M (M ⊤ M ) -1 M ⊤ )z + M (M ⊤ M ) -1 t (C) = µ λ 1 µ (I -M (M ⊤ M ) -1 M ⊤ )z + M (M ⊤ M ) -1 t (C) + (1 - µ λ ) M (M ⊤ M ) -1 t (C) µ λ F (C) + (1 - µ λ )F (C) = F (C).
Thus the second condition in Lemma 1 is satisfied, thus it has to be the first one which is violated, leading to merging two constant sets.

We now show that for special cases, the condition in Eq. ( 2) is satisfied, and we also show when the condition in Eq. ( 3) of Theorem 1 is satisfied or not:

• Cardinality-based functions: the condition in Eq. ( 2) is equivalent to

h(|B| + |A|) -h(|B|) |A| h(|B| + |C|) -h(|B|) |C| ,
which is a consequence of the concavity of h. Moreover the condition in Eq. ( 3) is equivalent to

h(|B| + |C|) -h(|B|) - |C| |A| [h(|B| + |A|) -h(|B|)] η min |C| |A| , 1 - |C| |A| .
For h(t) = t(p -t), this is equivalent to

|A|(|C| -|A|) η min |C| |A| , 1 - |C| |A| ,
which is true as soon as η |A|/2.

• One-dimensional total variation: we assume that we have a chain graph. Note that A must be an interval and that B only enters the problem if one of its elements is a neighbor of one of the two extreme elements of A. We thus have eight cases, depending on the three possibilities for these two neighbors of A (in B, in V \B, or no neighbor, i.e., end of the chain). We consider all 8 cases, where C is a non trivial subset of A, and compute a lower bound on

F (B ∪ C) -F (B) -|C| |A| [F (B ∪ A) -F (B)].
-left: B, right:

B. F (B) = 2, F (B ∪ A) = 0, F (C ∪ B) 2. Bound= 2 |C| |A| -left: B, right: V \B. F (B) = 1, F (B ∪ A) = 1, F (C ∪ B) 1. Bound= 0 -left: B, right: none. F (B) = 1, F (B ∪ A) = 0, F (C ∪ B) 1. Bound= |C| |A| -left: V \B, right: B. F (B) = 1, F (B ∪ A) = 1, F (C ∪ B) 1. Bound= 0 -left: V \B, right: V \B. F (B) = 0, F (B ∪ A) = 2, F (C ∪ B) 2. Bound= 2 -2 |C| |A| -left: V \B, right: none. F (B) = 0, F (B ∪ A) = 1, F (C ∪ B) 1. Bound= 1 -|C| |A| -left: none, right: B. F (B) = 2, F (B ∪ A) = 0, F (C ∪ B) 2. Bound= |C| |A| -left: none, right: V \B. F (B) = 1, F (B ∪ A) = 0, F (C ∪ B) 1. Bound= |C| |A| -left: none, right: none. F (B) = 0, F (B ∪ A) = 0, F (C ∪ B) 1. Bound= 1.
Considering all cases, we get a lower bound of zero, which shows that the paths are agglomerative. However, there are two cases where no strictly positive lower bounds are possible, namely when the two extremities of A have respective neighbors in B and V \B. Given that B is a set of higher values for the parameters and V \(A ∪ B) is a set of lower values, this is exactly a staircase. When there is no such staircase, we get a lower bound of min{|A|/|C|, 1 -|A|/|C|}, hence η = 1.

E Proof of Proposition 5

Proof We denote by w the unique mininizer of 1 2 w -z 2 2 + f (w) and s the associated dual vector in B(F ). The optimality conditions are w -z + s = 0, and f (w) = w ⊤ s (again from optimality conditions for pointwise maxima).

We assume that w takes distinct values v 1 , . . . , v m on the sets A 1 , . . . , A m . We define t as t k = sign(w k )(|w k | -λ) + (which is the unique minimizer of 1 2 w -t 2 2 + λ t 1 ). The constant sets of t are A j , for j such that |v j | > λ and zero for the union of all A j 's such that |v j | λ. Since t is obtained by soft-thresholding w, which corresponds to ℓ 1 -proximal problem, we have that t -w + λq = 0 with q ∞ 1 and q ⊤ t = t 1 .

By combining these two equalities, with have t -z + s + λq = 0 with q ∞ 1, q ⊤ t = t 1 and s ∈ B(F ). The only remaining element to show that t is optimal for the full problem is that f (t) = s ⊤ t. This is true since the level sets of w are finer than the ones of t (i.e., it is obtained by grouping some values of w), with no change of ordering [START_REF] Bach | Convex analysis and optimization with submodular functions: a tutorial[END_REF].

F Proof of Proposition 6

Proof From Lemma 1, the solution has to correspond to a lattice D and we only have to show that with probability one, the vector v = (M ⊤ M ) -1 (M ⊤ z -λt) has distinct components, which is straightforward because it has an absolutely continuous density with respect to the Lebesgue measure.

G Proof of Theorem 1

Proof From Lemma 1, in order to correspond to the same lattice D, we simply need that (a) v = (M ⊤ M ) -1 (M ⊤ z -λt) satisfies the order relationships imposed by D and that (b)

1 λ (I -M (M ⊤ M ) -1 M ⊤ )z + M (M ⊤ M ) -1 t ∈ B(F ).
Condition (a) is satisfied as soon as w -w * ∞ ν, which is implied by

σ (M ⊤ M ) -1 M ⊤ ε ∞ ν/4 and λ(M ⊤ M ) -1 t ∞ ν/4. (6)
The second condition in Eq. ( 6) is met by assumption, while the first one leads to the sufficient conditions ∀j, |ε(A j )| ν|A j |/4σ, leading by the union bound to the probabilities m j=1 exp -

ν 2 |Aj| 32σ 2 .
Following the same reasoning than in the proof of Prop. 4, condition (b) is satisfied as soon as for all j ∈ {1, . . . , m}, and all C j ⊂ A j ,

σ 1 λ (I -M (M ⊤ M ) -1 M ⊤ )ε (C j ) η j min |C j | |A j | , 1 - |C j | |A j | .
Indeed, this implies that for all j,

1 λ (I -M (M ⊤ M ) -1 M ⊤ )z + M (M ⊤ M ) -1 t (C j ) = σ λ (I -M (M ⊤ M ) -1 M ⊤ )ε + M (M ⊤ M ) -1 t (C j ) η j min |C j | |A j | , 1 - |C j | |A j | + |C j | |A j | (F (B j-1 ∪ A i ) -F (B j-1 ))
F (B j-1 ∪ C j ) -F (B j-1 ), which leads to 1 λ (I -M (M ⊤ M ) -1 M ⊤ )z +M (M ⊤ M ) -1 t ∈ B(F ) using the sequence of inequalities used in the proof of Prop. 4.

From Lemma 2 below, we thus get the probability 2 We now consider the three special cases:

• One-dimensional total variation: without the staircase effect, as shown in Appendix D, we have η j = 1. Moreover, |F (B j ) -F (B j-1 )| 2, and thus Eq. ( 5) leads to λ ν 8 min j |A j |. Using the largest possible λ in Eq. ( 5), we obtain a probability greater than

1 - m j=1 exp - ν 2 |A j | 32σ 2 -2 m j=1 |A j | exp - λ 2 η 2 j 2σ 2 |A j | 2 1 - m j=1 exp - ν 2 |A j | 32σ 2 -2 m j=1 |A j | exp - ν 2 min j |A j | 2 128σ 2 max j |A j | 2 1 - m j=1 exp - ν 2 |A j | 32σ 2 -2p exp - ν 2 min j |A j | 2 128σ 2 max j |A j | 2 1 -4p exp - ν 2 min j |A j | 2 128σ 2 max j |A j | 2 ,
because the second term is always greater than the third one.

• Two-dimensional total variation: we simply build the following counter-example: . We also illustrate this in Figure 6, where we show that depending on the shape of the level sets (which still have to be connected), we may not recover the correct pattern, even with very small noise.

Figure 3 :

 3 Figure3: Three left plots: Estimation of noisy piecewise constant 1D signal with outliers (indices 5 and 15 in the chain of 20 nodes). Left: original signal. Middle: best estimation with total variation (level sets are not correctly estimated). Right: best estimation with the robust total variation based on noisy cut functions (level sets are correctly estimated, with less bias and with detection of outliers). Right plot: clustering estimation error vs. noise level, in a sequence of 100 variables, with a single jump, where noise of variance one is added, with 5% of outliers (averaged over 20 replications).

Figure 4 :

 4 Figure 4: Left: Piecewise linear regularization paths of proximal problems (Eq. (1)) for different functions of cardinality. From left to right: quadratic function (all level sets allowed), second example in Section 4 (two large level sets at the top and bottom), piecewise linear with two pieces (a single large level set in the middle). Right: Same plot for the one-dimensional total variation. Note that in both cases the regularization paths for orthogonal designs are agglomerative (see Section 5), while for general designs, they would still be piecewise affine but not agglomerative.

Figure 5 :

 5 Figure 5: Left: Matlab running times of different optimization methods on 20 replications of a leastsquares regression problem with p = 1000 for a cardinality-based submodular function (best seen in color). Proximal methods with the generic algorithm (using the minimum-norm-point algorithm) are faster than subgradient descent (with two schedules for the learning rate, 1/t or 1/ √ t). Using the dedicated algorithm (which is not available in all situations) is significantly faster. Right: Examples of graphs (top: chain graph, bottom: hidden chain graph, with sets W and V and examples of a set A in light red, and B in blue, see text for details).

Figure 6 :

 6 Figure 6: Signal approximation with the two-dimensional total variation: For two piecewise constant images with two values, the estimation may (left case) or may not (right case) recover the correct level sets, even with infinitesimal noise. For the two cases, left: original pattern, right: best possible recovered level sets.

  where B are the black nodes, C the gray nodes and A the complement of B. We indeed have A connected, andF (B ∪ C) -F (B) = 4 -5 = -1, F (B ∪ A) -F (B) = -5, leading to F (B ∪ C) -F (B) -|C| |A| [F (B ∪ A) -F (B)] = -1 + 5 × 2 13 = -3 13

  for which the extreme points corresponding to the separable set {1, 3} and its complement disappear.

	{2}	{1,2}	{1,2,5,6}	{2}	{5,6}
			{1,2,3,4,5,6}
	{5,6}	{2,5,6}	{2,3,4,5,6}	{1}	{3,4}
	Figure 2: Left: distributive lattice with 7 elements in 2 {1,2,3,4,5,6} , represented with the Hasse
	diagram corresponding to the inclusion order (for a partial order, a Hasse diagram connects A to B

if A is smaller than B and there is no C such that A is smaller than C and C is smaller than B). Right: corresponding poset, with 4 elements that form a partition of {1, 2, 3, 4, 5, 6}, represented with the

  Lemma 2 For F (A) = min |A| p , 1 -|A| p , and s normal with mean zero and variance I -Proof Since F depends on uniquely on the cardinality |A| and is symmetric we have, with s ∈ R p the sorted (in descending order) components of s, and h(a) = min{a/p, 1 -a/p}:

									m j=1 |A j | exp -	λ 2 η 2 j 2σ 2 |Aj| 2 .
	have:			P		max A⊂V,A =∅,A =V	s(A) F (A)	t	2p exp -	t 2 2p 2 .	1V 1 ⊤ V p , we
	P	max A⊂V,A =∅,A =V	s(A) F (A)	t
	= P	max k∈{1,...,p-1}	s({1, . . . , k}) h(k)	t
	P	max k∈{1,...,⌊p/2⌋-1}	s({1, . . . , k}) h(k)	t + P	max k∈{⌊p/2⌋,...,p-1}	s({1, . . . , k}) h(k)	t
	2P	max k∈{1,...,⌊p/2⌋-1}	s({1, . . . , k}) k/p	t because of symmetry due to the covariance of s
	2P	max k∈{1,...,⌊p/2⌋-1}	s({1, . . . , k}) k/p	t
	2P	max k∈{1,...,p}	s k t/p
	2p exp(-t 2 /2p 2 ).

Note that the support {w = 0} is a constant set which is the intersection of two level sets.

The greedy algorithm to find extreme points of the base polyhedron should not be confused with the greedy algorithm (e.g., forward selection) that is common in supervised learning/statistics.

Note that even in the case of symmetric submodular functions, where more efficient algorithms in O(p 3 ) for submodular function minimization (SFM) exist[START_REF] Queyranne | Minimizing symmetric submodular functions[END_REF], the minimization of functions of the form λF (A)z(A) is provably as hard as general SFM[START_REF] Queyranne | Minimizing symmetric submodular functions[END_REF].

Interestingly, when used for submodular function minimization (SFM), the minimum-norm-point algorithm has no complexity bound but is empirically faster than algorithms with such bounds[START_REF] Fujishige | Submodular Functions and Optimization[END_REF].

Acknowledgements

This paper was partially supported by the Agence Nationale de la Recherche (MGA Project), the European Research Council (SIERRA Project) and Digiteo (BIOVIZ project).

B Proof of Proposition 2

Proof Extreme points of U correspond to full-dimensional faces of B(F ). From Corollary 3.4.4 in [START_REF] Fujishige | Submodular Functions and Optimization[END_REF], these facets are exactly the ones that correspond to sets A with the given conditions. These facets are defined as the intersection of {s(A) = F (A)} and {s(V ) = F (V )}, which leads to the desired result. Note that this is also a consequence of Prop. 3. Note that when F is symmetric, the second condition is equivalent to V \A being inseparable for F .

C Proof of Proposition 3

Proof Given that the polyhedra U and B(F ) are polar to each other [START_REF] Rockafellar | Convex Analysis[END_REF], the proposition follows from Theorem 3.43 in [START_REF] Fujishige | Submodular Functions and Optimization[END_REF], where each of our three assumptions are equivalent to a corresponding one in Theorem 3.43 from [START_REF] Fujishige | Submodular Functions and Optimization[END_REF].

D Proof of Proposition 4

We first start by a lemma, which follows common practice in sparse recovery (assume a certain sparsity pattern and check when it is actually optimal): Lemma 1 (Optimality of lattice for proximal problem) The solution of the proximal problem in Eq. ( 1) corresponds to a lattice D if and only if v = (M ⊤ M ) -1 (M ⊤ z -λt) satisfies the order relationships imposed by D and

where M ∈ R p×m is the indicator matrix of the partition Π(D), and

Proof Any w ∈ R p belongs to a single face relative interior from Prop. 3, defined by a lattice D, i.e., w is constant on A i with value v i (which implies that w = M v) and such that v i > v j as soon as A i A j . We assume a topological ordering of the sets A i , i.e, A i A j ⇒ i j. Since the Lovász extension is linear for w in U D (and equal to t ⊤ v for w = M v), the optimum over w can be found by minimizing with respect to v

We thus get, by setting the gradient to zero:

Optimality conditions for w for Eq. ( 1) are that w -z + λs = 0, for s ∈ B(F ) and f (w) = w ⊤ s (these are obtained from general optimality conditions for functions defined as pointwise maxima [START_REF] Borwein | Convex Analysis and Nonlinear Optimization: Theory and Examples[END_REF]). Thus our candidate w = M v is optimal if and only if M v -z + λs = w -z + λs = 0 for (a) s ∈ B(F ) and (b) f (w) = w ⊤ s. From Prop. 10 in [START_REF] Bach | Convex analysis and optimization with submodular functions: a tutorial[END_REF], for (b) to be valid, s ∈ B(F ) simply has to satisfy


Stefania Gimelli

Gianluca Caridi

Silvana Beri

Kyle Mccracken

Renata Bocciardi

Paola Zordan

Monica Dagnino

Patrizia Fiorio

Luisa Murer

Elisa Benetti

Orsetta Zuffardi

Roberto Giorda

James M Wells

Giorgio Gimelli
email: giorgiogimelli@ospedale-gaslini.ge.it

Gian Marco Ghiggeri

Mutations in SOX17 are associated with congenital anomalies of the kidney and the urinary tract

Keywords: Congenital anomalies of the kidney (CAKUT), SOX17, Wnt, Gene mutations Congenital anomalies of the kidney (CAKUT), SOX17, Wnt, Gene mutations

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

INTRODUCTION

Mammalian kidneys derive from two tissue compartments of the embryonic mesoderm, i.e. the ureteric bud (UB), derived from the Wolffian duct, and the metanephric mesenchyme (MM), whose interaction induces the metanephric mesenchyme to trans-differentiate into nephron epithelia [START_REF] Vainio | Coordinating early kidney development: lessons from gene targeting[END_REF][START_REF] Woolf | Evolving concepts in human renal dysplasia[END_REF]. Failure of this mechanism, such as in ectopic or supernumerary ureters [START_REF] Nishimura | Role of the angiotensin type 2 receptor gene in congenital anomalies of the kidney and urinary tract, CAKUT, of mice and men[END_REF]Mijazaki et al., 2000;[START_REF] Kume | Murine forkhead/winged helix genes Foxc1 (Mf1) and Foxc2 (Mfh1) are required for the early organogenesis of the kidney and urinary tract[END_REF], is considered an underlying cause of a wide variety of renal malformation [START_REF] Mackie | Duplex kidneys: a correlation of renal dysplasia with position of the ureteral orifice[END_REF][START_REF] Pope | How they begin and how they end: classic and new theories for the development and deterioration of congenital anomalies of the kidney and urinary tract, CAKUT[END_REF]. Gene targeting experiments in mice have led to the characterization of specific regulators of both the conversion of epithelial into mesenchymal cells and the branching of the ureteric bud. The Wingless-related signaling pathway (Wnt), for example, is critical at several stages of the process including initiation of metanephric development [START_REF] Carroll | Wnt9b plays a central role in the regulation of mesenchymal to epithelial transitions underlying organogenesis of the mammalian urogenital system[END_REF],

branching [START_REF] Majumdar | Wnt11 and Ret/Gdnf pathways cooperate in regulating ureteric branching during metanephric kidney development[END_REF] and development of the nephron [START_REF] Stark | Epithelial transformation of metanephric mesenchyme in the developing kidney regulated by Wnt-4[END_REF]. Several Wnt ligands and receptors are expressed during kidney development and activation of the Wnt pathway results in the translocation of β-catenin into the nucleus [START_REF] Karihaloo | Signals which build a tubule[END_REF]. β-catenin is a key transcriptional effector of the Wnt pathway, and it was recently demonstrated that loss of βcatenin/Wnt signaling in the developing Wolffian duct causes defects including ectopic ureters and renal aplasia [START_REF] Marose | Beta-catenin is necessary to keep cells of ureteric bud/Wolffian duct epithelium in a precursor state[END_REF]. Tight control of the Wnt pathway is critical for normal development and several Wnt antagonists are expressed during kidney and urinary tract development. One example is the HMG-box transcription factor SOX17, which is known to inhibit canonical Wnt signaling by forming a complex with β-catenin and TCF/LEF family members and targeting them for degradation in a GSK3β -independent manner [START_REF] Sinner | Sox17 and Sox4 Differentially Regulate {beta}-Catenin/T-Cell Factor Activity and Proliferation of Colon Carcinoma Cells[END_REF]. Analysis of the Genito-Urinary Development database (http://www.gudmap.org) [START_REF] Mcmahon | GUDMAP project. GUDMAP: the genitourinary developmental molecular anatomy project[END_REF] shows in situ hybridization and microarray expression data demonstrating that Sox17 is expressed at several key stages during kidney and urinary development. Specifically, Sox17 is expressed in the Here we observe a young girl with congenital defects of the urinary tract, chronic constipation and mild mental retardation, who carried a de novo pseudodicentric duplicated chromosome 8 of maternal origin. This gave us the opportunity to study the genes contained within the duplication, which include SOX17. We have identified a p.Y259N mutation in SOX17 in this girl, and we subsequently identified the same mutation in five additional patients with congenital anomalies of the kidney and the urinary tract (CAKUT). Furthermore, two patients presenting with CAKUT carried other SOX17 mutations. Functional studies of SOX17-Y259N demonstrated that this protein abnormally accumulates in cultured kidney cells, resulting in inhibition of the canonical Wnt signaling pathway. Given the vital role of this pathway in multiple stages of kidney development, we propose a model by which elevated levels of mutant SOX17-Y259N protein inhibit Wnt signaling resulting in abnormal kidney and urinary tract development.

MATERIALS AND METHODS

Patients

Fifty-eight familial cases with vesico ureteral reflux (VUR) belonging to 10 small families were analysed. In two of the families the same p.Y259N mutation in SOX17 was found (see Results).

Pedigrees of the two families are shown in Figure 1a. deficit in expressive language. She had chronic constipation. Echocardiography showed a normal heart with large PDA and a bidirectional shunt. Encephalic RM demonstrated abnormal morphology of the corpus callosum, characterized by evident thinning of the posterior portion of the body and of the isthmus. Her right kidney showed a duplicated pyeloureteral collecting system of about 7 cm in diameter and bilateral VUR (III). Ureteroplasty was performed to correct the patient's urinary defects. The patient's mother (I,2) showed VUR associated to megaureter with recurrent urinary infections, chronic constipation and coloboma of the iris in her left eye. Her father was healthy.

Family 2. Patient (II,1) is a male child with left hydronephrosis due to stenosis of the pyeloureteral joint. His mother (I,2) has vesicoureteral reflux, while his father is healthy.

Sporadic cases.

Additionally, 178 patients with proven VUR and a history of urinary tract infection were enrolled in the study. Control DNAs were obtained from 88 normal subjects, 82 cord blood samples from normal donors and 135 patients with nephrotic syndrome. While the former two groups were not controlled in respect to the presence of any defect of the urinary tract, all patients with nephrotic syndrome had an echosonography showing normality. The demographic and clinical data relative to all the above cohorts are given in Table 1.

All patients with VUR had been studied with echosonography, voiding cystography and Tc99mDMSA scan in order to verify the presence of malformations of the kidney and urinary tract and/or renal scars. Static renal scintigraphy was recorded three to four hours after injection of a weight-scaled dose of technetium-99m DMSA to obtain views in the posterior and both posterior oblique projections for 300 kilocounts or more. Focal or diffuse areas of decreased uptake in the first scan, without evidence of cortical loss, indicated acute pyelonephritis. Renal scarring was defined as decreased uptake with distortion of the contours or as cortical thinning with loss of

Cytogenetics, Immunofluorescence, and array-CGH investigations

Chromosome preparations were made from peripheral blood, skin and ureter biopsies from the proposita using standard techniques. To define the extension of the duplicated segment an array-CGH experiment was performed using the Human Genome CGH Microarray Kits 44B (Agilent Technologies, Palo Alto, CA, USA) covering the whole genome with a resolution of ∼100 kb.

Briefly, 1 µg of patient and sex-matched pooled reference DNAs were processed according to the manufacturer's protocol. Fluorescence was scanned in a dual-laser scanner and the images were extracted and analyzed with Agilent Feature Extraction software (v9.5.3.1) and CGH Analytics software (v3.5.14) respectively. Changes in test DNA copy number at a specific locus are observed as the deviation of the log ratio value from a modal value of 0.

To confirm the breakpoints, structure and orientation of the duplicated region we used fluorescent in situ hybridization (FISH) with BAC clones spanning the chromosomal 8q11.1q12.1 regions selected according to the University of California Santa Cruz (UCSC) Human Genome Assembly (March 2006 assembly). To investigate the activation status of the two centromeres present on the duplicated chromosome 8, immunofluorescence analysis was performed by CENP-C antibody, as described [START_REF] Gimelli | CENP-G in neocentromeres and inactive centromeres[END_REF].

SOX17 mutation analysis.

DNA was extracted from lymphoblasts or whole blood sample with the High Pure PCR Template Preparation Kit (Roche Diagnostics, Italy). We also obtained genomic DNA from cultured skin biopsy fibroblasts and from the proband's ureteric tissue. Amplification and sequencing of the SOX17 (NM_022454.2) gene and its promoter region were performed by PCR amplification using the following primer pairs: All amplification reactions were performed with standard PCR conditions in a GeneAmp 9700 PCR System (Applied Biosystems). Unincorporated dNTP's and primers were removed from 5µl of PCR product by digestion with 2 µl of ExoSAP-IT (USB, Europe GmbH). Automated sequence analysis was performed by dye-terminator reactions on an ABI3130xl (Applied Biosystems) and electropherogram analysis by Sequencer Software 4.6 (GeneCodes Corporation, Ann Arbor, MI).

Segregation analysis and somatic cell hybrids

Parental origin of the duplication was studied by generating somatic cell hybrid clones to isolate the duplicated chromosome 8 from its normal homolog [START_REF] Giorda | Selective disruption of muscle and brain-specific BPAG1 isoforms in a girl with a 6;15 translocation, cognitive and motor delay, and tracheo-oesophageal atresia[END_REF]. Genomic DNA was extracted from the proposita's EBV cell line and her parent's' lymphocytes using standard protocols; Genomic DNA from hybrid clones was extracted using DNAzol (MRC Inc., Cincinnati, OH).

Genotyping of polymorphic loci was performed by amplification with primers labelled with fluorescent probes (ABI 5-Fam, Hex and Tet) followed by analysis on a ABI 310 Genetic Analyzer (Applied Biosystems). Amplifications were performed with Taq Gold (Applied Biosystems) using standard protocols. Sequencing reactions were performed with a Big Dye Terminator Cycle Sequencing kit (Applied Biosystems) and run on an ABI Prism 3100 AV Genetic Analyzer. (DMEM) (Gibco) supplemented with 10% fetal bovine serum (FBS) (Hyclone). Cells were plated into 24-well plates 24 hours prior to transfection. For Western blotting, cells were transfected with the Sox17 plasmids (100-300 ng), and a GFP plasmid (100 ng) as a transfection control, using Lipofectamine 2000 (Invitrogen) according to the manufacturer's protocol. Total amount of DNA was kept constant by adding empty vector DNA. Total cell lysates were prepared 48 hours posttransfection using RIPA buffer and analyzed by Western immunoblotting. Antibodies used were goat anti-Sox17 (1:5000, R&D Systems) and mouse anti-tubulin (1:5000, Sigma); the secondary antibodies were rabbit anti-goat HRP (1:10,000, Vector Laboratories) and goat anti-mouse HRP (1:10,000, Jackson ImmunoResearch). Each experiment was repeated at least three times and a representative sample is shown. For luciferase assays, cells were transfected with Sox17 plasmids (3-50 ng), either the TOPflash Wnt reporter plasmid or a SOX17 luciferase reporter plasmid (50 ng) [START_REF] Sinner | Sox17 and Sox4 Differentially Regulate {beta}-Catenin/T-Cell Factor Activity and Proliferation of Colon Carcinoma Cells[END_REF], a renilla plasmid (50 ng) as a transfection control, and a constitutively active S37A β-catenin plasmid (50 ng) for the TOPflash assay. The Sox17 reporter plasmid contained 8 copies of a Sox17 binding site and the TOPflash reporter contains TCF/LEF binding sites and were previously described [START_REF] Sinner | Sox17 and Sox4 Differentially Regulate {beta}-Catenin/T-Cell Factor Activity and Proliferation of Colon Carcinoma Cells[END_REF]Zorn et al., 1999]. Total amount of DNA was kept constant by adding empty vector DNA, and cell lysates were prepared for luciferase assay as previously described [START_REF] Sinner | Sox17 and Sox4 Differentially Regulate {beta}-Catenin/T-Cell Factor Activity and Proliferation of Colon Carcinoma Cells[END_REF].

Western blot analysis and luciferase assays

Quantitative RT-PCR analysis

For quantitative RT-PCR, total RNA was extracted from cells using a NucleoSpin RNA II Kit (Mackery and Nagel) and treated with RNase-free DNase (Roche). cDNA was synthesized with random hexamer primers. Real time RT-PCR was performed using an Opticon machine (MJ Research-Bio Rad). The primers used in this study were: hSox17 forward 5' GAC GAC CAG AGC CAG ACC 3' and hSox17 reverse 5' CGC CTC GCC CTT CAC C 3'; hβ-tubulin forward 5' GAT ACC TCA CCG TGG CTG CT 3' and hβ-tubulin reverse 5' AGA GGA AAG GGG CAG TTG sample was estimated at the log-linear amplification phase, and these values were normalized to the expression level of tubulin and the data presented as a ratio of tubulin expression.

RESULTS

Our study began with the observation of a young girl with congenital defects of the urinary tract, chronic constipation and mild mental retardation, who carried a de novo pseudodicentric duplicated chromosome 8 (Family 1, Fig. 1a). The de novo duplication dup(8)(q11.1q12.1) of 13.1

Mb on chromosome 8 was demonstrated by CGH-array (Agilent 44B) and confirmed by FISH analysis using BAC clones known to map to the duplicated region (Fig. 2). A direct duplication was demonstrated by dual-color FISH with BAC RP11-53M11 and CEP8. A pseudodicentric chromosome 8 with a inactive centromere was evidenced by FISH with CEP8 and by immunostaining with CENP-C antibody (Fig. 2D). These results allow us to define the karyotype of our proposita as: 46,XX,psudicdup(8)(q11.1q12.1) (chr8:46,958,053..60,381,578).

Among the 38 genes located in the duplicated region of chromosome 8, SOX17 seemed a good candidate to study because of its expression throughout development of the urogenital tract in the mouse and its role in regulating β-catenin signaling. We identified a point mutation at nucleotide 775 with respect to the translation start site (c.775T>A) in the SOX17 gene. This mutation results in a protein change from tyrosine at position 259 to an asparagine residue (p.Y259N). The mutation is localized between the HMG-box and the glycine-proline rich segment at the C-terminal of the protein (Fig. 1b). The same mutation was found in another family with VUR (out of 10 families for an overall of 58 affected) and in several sporadic subjects presenting VUR and renal scars. In fact, we analyzed 56 somatic cell hybrid clones, using chromosome 8q11 markers and selected three clones containing only the duplicated chromosome 8 and three containing only the normal chromosome 8. Typing with a panel of polymorphic markers demonstrated that the duplication was of maternal origin and intrachromatidic (Supp.Table 1). Amplification and sequencing of exon 2 of the SOX17 gene from the proposita, her parents and selected hybrid clones demonstrated that in both the proposita and her mother, chromosome 8 carried the p.Y259N mutation, while the paternal chromosome 8 had a normal SOX17 allele.

The screening for SOX17 mutations was extended to 178 individuals with sporadic VUR and in 305 controls consisting of 135 children with nephrotic syndrome, 88 normal subjects without a history of urinary infection who were not further characterized and 82 cord blood samples (610 chromosomes). Children with nephrotic syndrome were chosen since all had been followed for years with frequent urine analysis and echosonograpic evaluation. The same Y259N mutation was found in two patients of the sporadic VUR cohort, while two additional children carried different SOX17 mutations (Table 1) (χ 2 p<0.01): one was a point mutation (p.G178C) producing a glycine to cysteine change at position 178 and the other (p.17Q_18SinsTQ) was characterized by an in-frame insertion of threonine-glutamine at position 17 (Fig. 1b andTable 1). Finally, p.Y259N was found in 1 normal blood donor DNA who was recruited from our Transfusion Unit without having any further clinical studies, including renal sonography (Table 1). Two (p.G178C and p.Y259N) of the 3 mutations described here are localized between the HMGbox and the glycine-proline rich segment at the C-terminal of the protein; the other is at the Nterminus near the HMG-box (Fig. 1b). Comparison of the predicted amino acid sequences indicates that human and mouse Sox17 share about 85% identity over their entire sequence, while zebrafish (Dr) Sox17 shows nearly perfect conservation only in the HMG box and the N-and C-terminal S1). The Glycine 178 residue is conserved across all three species, while Tyrosine 259 is conserved between human and mouse (and the frog Xenopus laevis, data not shown); the 17Q_18S residues are located in the conserved N-terminal portion of the protein, but are not themselves conserved (Supp. Fig. S1).

Analysis of SOX17 Y259N protein activity

We investigated the impact of the Y259N mutation on SOX17 protein levels, SOX17 mRNA levels, transcriptional activity and Wnt-inhibitory activity in the kidney cell line HEK293T. Western blot analysis of total cell extracts demonstrated that, at equal amounts of transfected DNA, the mutant SOX17-Y259N protein accumulated to much higher levels than SOX17-WT protein (Fig. 3A). In numerous experiments we observed between 6-20-fold increase in protein levels as measured by western blot and densitometry analysis. These differences were not due differences in mRNA levels from the transfected plasmids, since quantitative RT-PCR on total RNA isolated from transfected cells revealed that mRNA levels of wild type and SOX17-Y259N-transfected cells were largely comparable (Fig. 3B). In the example shown, there was a slight increase (1.4 fold) in levels of SOX17-Y259N mRNA relative to wild type, but this is minimal compared to the 6-20-fold increase in protein levels of SOX17-Y259N. We analyzed SOX17 transcriptional and Wnt-β-catenin repressing activity by co-transfection of SOX17 with a SOX17 reporter plasmid [START_REF] Sinner | Sox17 and Sox4 Differentially Regulate {beta}-Catenin/T-Cell Factor Activity and Proliferation of Colon Carcinoma Cells[END_REF](Fig. 3C) and a Wnt reporter plasmid (Fig. 3D). In all cases, the Y259N mutant protein levels were significantly higher and this correlated with higher transcriptional activity as measured by the SOX17 reporter plasmid. Moreover, SOX17-Y259N suppressed Wnt-β-catenin signaling activity 2-3 fold better than wild type SOX17 (Fig. 3D). However, when luciferase activity was approximately normalized to SOX17 protein levels, the p.Y259N mutation did not appear to alter the inherent transcriptional or Wnt/β-catenin inhibitory activity of SOX17 [START_REF] Sinner | Sox17 and Sox4 Differentially Regulate {beta}-Catenin/T-Cell Factor Activity and Proliferation of Colon Carcinoma Cells[END_REF][START_REF] Wodarz | Mechanisms of Wnt signaling in development[END_REF]Zorn et al., 1999]. Since we have previously demonstrated that SOX17 can interact with β-catenin and TCF/LEF proteins and target them for degradation, one likely interpretation for

DISCUSSION

A complex mechanism drives the development of the urinary tract in mammals. Both the kidney and urinary tract segments derive from the interaction of two tissue compartments of the embryonic mesoderm, i.e. the ureteric bud (UB), derived from the Wolffian duct, and the metanephric mesenchyme (MM), that induces the metanephric mesenchyme to trans-differentiate into nephron epithelia [START_REF] Vainio | Coordinating early kidney development: lessons from gene targeting[END_REF][START_REF] Woolf | Evolving concepts in human renal dysplasia[END_REF]. These events are mediated by several soluble factors that act in a cooperative fashion either as pro-or anti-tubulogenic factors. Among the growing list of such molecules are the members of the FGF, TGF-ß, and Wnt families, as well as GDNF, HGF, and EGF [START_REF] Karihaloo | Signals which build a tubule[END_REF]. β-catenin is a key component of the canonical Wnt signaling pathway. Several Wnts are expressed during kidney development, and activation of the Wnt pathway can result in localization of β-catenin to the nucleus where it activates a pattern of gene expression that is required for normal nephron development [START_REF] Karihaloo | Signals which build a tubule[END_REF]. In fact, inhibiting β-catenin/Wnt signaling in the developing Wolffian duct results in mice with ectopic ureters and renal malformations [START_REF] Marose | Beta-catenin is necessary to keep cells of ureteric bud/Wolffian duct epithelium in a precursor state[END_REF].

We report here the identification of a novel heterozygous amino acid substitution in SOX17 in two families and several other subjects with urinary tract malformations. Our results show that the p.Y259N mutation causes an increase in SOX17 protein levels in cultured kidney fibroblast cells. Tyrosine-259 is one of four putative tyrosine-phorphorylation sites, as predicted by analysis of SOX17 primary sequence [START_REF] Blom | Sequence and structure-based prediction of eukaryotic protein phosphorylation sites[END_REF]. The interactions between protein phosphorylation and the ubiquitin-proteasome system (UPS) are well-documented [START_REF] Gao | Regulating the regulators: control of protein ubiquitination and ubiquitinlike modifications by extracellular stimuli[END_REF][START_REF] Hunter | The age of crosstalk: phosphorylation, ubiquitination, and beyond[END_REF]. Specifically, a single phosphorylated residue can either target a protein for degradation or prevent its degradation by the UPS, depending on the protein being studied. We therefore speculate SOX17 is known to directly interact with transcriptional effectors of the Wnt signaling pathway, β-catenin and TCF/LEF. SOX17 physically interacts with β-catenin to regulate SOX17 target genes [START_REF] Sinner | Sox17 and β-catenin co-operate to regulate the transcription of endodermal genes[END_REF]. In addition, SOX17 is a potent Wnt-signaling antagonist, and does so through direct physical interaction with both β-catenin and TCF/LEF factors [START_REF] Sinner | Sox17 and Sox4 Differentially Regulate {beta}-Catenin/T-Cell Factor Activity and Proliferation of Colon Carcinoma Cells[END_REF]. Formation of this trimeric complex leads to the degradation of both β-catenin and Tcf/Lef proteins through a GSK3-independent mechanism and loss of Wnt-signaling activity. Consistent with SOX17 acting to inhibit the Wnt/ β-catenin pathway, our data showed that elevated SOX17 Y259N protein inappropriately suppressed the Wnt signaling pathway in renal cells. Since mice lacking β-catenin in the developing kidney have symptoms of CAKUT, it is possible that altered levels of Wnt signaling during development could cause the observed congenital defects in these patients with CAKUT. Alternatively, elevated levels of Sox17 could effect urinary tract development through regulation of Sox17 target genes, of which several have been identified [START_REF] Sinner | Sox17 and β-catenin co-operate to regulate the transcription of endodermal genes[END_REF][START_REF] Patterson | SOX17 directly activates Zfp202 transcription during in vitro endoderm differentiation[END_REF].

SOX17 is expressed throughout different stages of kidney development (http://www.gudmap.org) [START_REF] Brunskill | Atlas of gene expression in the developing kidney at microanatomic resolution[END_REF]. For example in situ hybridization and microarray analysis shows that Sox17 is highly expressed in bladder stroma and to a minor degree in the ureteric bud and in metanephric mesenchyme at E11.5 days after fertilization, a stage where Wnt9b acts to regulate ureteric branching [START_REF] Carroll | Wnt9b plays a central role in the regulation of mesenchymal to epithelial transitions underlying organogenesis of the mammalian urogenital system[END_REF]. Other Wnt ligands, specifically Wnt2b, Wnt6, Wnt7b and Wnt9b, as well as Sox17 are also expressed at later stages of kidney development such as in the S-shaped bodies, mesonephros and metanephros, and later in the medullary collecting duct, renal medullary interstitium, maturing renal corpuscle, early proximal tubule, and cortical collecting duct. Our in vitro analysis of SOX17 activity showed a clear correlation between SOX17 protein level and the degree of β-catenin repression, demonstrating a dose dependent inhibitory effect of SOX17 on Wnt-signaling. This is interesting because the proband's duplicated chromosome 8 contained two copies of the SOX17-Y259N mutation and would be predicted to exhibit a genetic "dose-dependent" increase in phenotypic severity. In fact, the patient with the duplication and two copies of SOX 17-Y259N, which would be predicted to have higher accumulation of SOX17 and more suppression of Wnt/β-catenin, had more severe developmental defects than the patients with one copy of SOX 17-Y259N.

To our knowledge, no mutation or disease has been associated with the SOX17 gene in humans. Only two HMG box mutations were found in cell lines from colorectal cancers [START_REF] Suraweera | Mutations within Wnt pathway genes in sporadic colorectal cancers and cell lines[END_REF]. The presence of SOX17 mutations in several patients with urinary tract anomalies suggests that SOX17 is involved in regulatory and signaling pathways controlling the normal development of the urinary apparatus. The additional pathological features found exclusively in the proband of Family 1, such as psychomotor and language development delay and abnormal corpus callosum, were very likely due to the presence of the 13 Mb duplication spanning a portion of chromosome 8 containing over 30 genes. The reason for the rare association of SOX17 functional mutations with diseases in humans probably resides on the fact that to-date, over twenty SOX genes have been identified in vertebrates with closely related family members. For example, SOX17, SOX7, and SOX18, share high structural and functional similarities and have functional redundancies during development [START_REF] Bowles | Phylogeny of the SOX family of developmental transcription factors based on sequence and structural indicators[END_REF][START_REF] Travers | Recognition of distorted DNA structures by HMG domains[END_REF][START_REF] Sakamoto | Redundant roles of Sox17 and Sox18 in early cardiovascular development of mouse embryos[END_REF]. This indicates that Sox-family members that are co-expressed in the same cell type will functionally substitute for one another.

  metanephric mesenchyme of the developing kidney and urinary tract between Theiler Stage 19-23 (E11.5-15.5 days after fertilization).

Family 1 .

 1 Patient (II,1) was born from non consanguineous parents. The pregnancy was achieved after in vitro fertilization (FIVET). A cesarean section at the 34th week of gestation was performed because of polydramnios and a prenatal ultrasonography showing severe bilateral hydronephrosis in the fetus. At birth, she was put on intensive care because of her critical health conditions. In the first

  Two nuclear physicians, blind to the test results, interpreted the scans independently and resolved discrepancies by discussion.

  obtained from ATCC and cultured in Dulbecco's modified Eagle's medium

  . SYBR green dye (Qiagen) was included in the PCR mix. The amount of product in each

  the first identified patient showed the maternal origin of the mutation.

  that elevated p.Y259N mutant protein inappropriately suppresses the Wnt signaling pathway during kidney and urinary tract development causing the above-mentioned congenital defects.

  degradation of SOX17 is at least partially dependent on tyrosinephosphorylation at residue 259.

  the identification of SOX17 mutations in individuals with duplication of the urinary tract and VUR has broad implications for the genetic work-up in patients with kidney and urinary tract malformations. SOX17 is the latest in a series of genes (PAX2, ROBO2) whose alteration induces partial defects of the urinary tract (VUR). Our observations also indirectly support a key role for SOX17, possibly via Wnt/β-catenin/Tcf signaling pathway, in kidney organogenesis, ureteric branching, and urinary tract development in humans[Zhang, 2003].

  2003. Kidney development: roles of sprouty, Wnt2b and type XVIII collagen in the ureteric bud Morphogenesis. Acta Univ Oul D 717. Zorn AM, Barish GD, Williams BO, Lavender P, Klymkowsky MW, Varmus HE. 1999. Regulation of Wnt signaling by Sox proteins: XSox17 alpha/beta and XSox3 physically interact with betacatenin. Mol Cell 4: 487-498.

Figure legends Figure 1 .

 legends1 Figure legends

Figure 2 .

 2 Figure 2. (A) Array-CGH, cytogenetics and FISH results. Ratio plot of high-resolution

Figure 3 .

 3 Figure 3. Impact of the Y259N mutation on SOX17 mRNA and protein levels. (A) Steady state

Figure 1 .Figure 3 .

 13 Figure 1. (a) Pedigrees of affected families. Family 1 -I.1 healthy father. -I.2 mother with recurrent urinary infections, duplex ureter with dilatation, chronic constipation -II.1 46,XX,dirdup(8q)(q11.1q12.1)dic, duplex ureter dx, reflux dx (III degree), hydronephrosis sn, reflux (IV degree), chronic constipation, thinning of the posterior portion of the body of the corpus callosum. Family 2 -I.1 Healthy father, I.2 Vesicoureteral reflux, II.1 Hydronephrosis sn, stenosis of the pyeloureteral joint sn. (b) Localization of mutations along the SOX17 gene coding sequence. The location of the HGM box and the G/P-rich region are indicated. The positions of tyrosine residues (*) predicted to undergo phosphorylation are also indicated. One of these residues is the mutated Y259. 29x20mm (600 x 600 DPI)

Table 1 :

 1 SOX17 mutation analysis of subjects with vesico-ureteral reflux (VUR), DMSA-positive (DMSA+ UTI) and renal scars associated with recurrent urinary tract infections. Three groups of unselected control subjects were also analyzed.One of this included children with nephrotic syndrome who were excluded for VUR

		Number (n)	Sex (M/F)	SOX17 p.Y259N n.	SOX17 p.G178C n	SOX17 P17Q_18insTQ n	Diagnosis (grade, position)	Tc99m DMSA
	CAKUT
		58 (10 fam.)	26/32	4
	Familial Cases	Fam.1, II.1	F	het			VUR (III grade,R&L) double pelvis	renal scars
		Fam.1, I.2	F	het			VUR (IV grade, R)	normal
		Fam.2, II.1	M	het			VUR (III grade, L)	normal
		Fam. 2, I.2	F	het			VUR(III grade, L)	renal scars
	Sporadic cases	178	57/121	2	1	1
		pt 180	F	het			ureter dilatation L	renal scars
		pt 240	F	het			VUR (III grade, L)	renal scars
		pt 253	M		het		VUR (I grade,R&L)	renal scars
		pt 36	M			het	VUR (III grade, R&L)	renal scars
	Controls	88	40/48	1
	(CT)
		ct 1	M	het			n.a	n.a
	Cord Blood	82	40/42	0
	Nephrotic Syndrome	135	60/75	0
	Abbreviations: VUR. Vesico ureteral reflux; UTI, Urinary tract infections; n, number; M, male; F, female; het, heterozygote; L, left; R, right;
	Tc99m DMSA, Technetium99-dimercaptosuccinic acid; n.a, not available

John Wiley & Sons, Inc.Human Mutation

Acknowledgements

Gian Marco Ghiggeri and Gianluca Caridi acknowledge the Italian Telethon Foundation (project no. GGP08050) for financial support.

AUTHOR CONTRIBUTIONS

The study was coordinated by J.

Conflicts of interest

The authors have no conflicts of interest to report.