Jouvin Denis
email: denis.jouvin@liris.cnrs.fr

Liris

Claude Bernard Lyon

Continuations and behavior components engineering in multi-agent systems

Keywords: Continuations, conversational multi-agent systems, agent oriented software engineering, behavioral component, continuation-based automatons

Continuations and behavior components engineering in multi-agent systems

Introduction

Multi-agent systems (MAS for short) are a programming paradigm especially well suited to model complex systems. In MAS, agents usually interact by means of an elaborate, normalized interaction model. The interaction model used will condition numerous prized MAS properties, such as agent autonomy, interoperability, robustness, and self-organization, as mentioned in Luck et al. [START_REF] Luck | Agent Technology: Enabling Next Generation Computing, A Roadmap for Agent Based Computing[END_REF].

However, these elaborate interaction models are also a significant source of difficulties in conversational MAS implementations, as shown in former research [START_REF] Jouvin | Role Delegation as Multi-Agent Oriented Dynamic Composition[END_REF]. To address these difficulties, various multi-agent platforms propose componential approaches. Agents are then provided with reusable behavioral components, that define partially or completely their behavior with respect to a given conversation type.

In this paper we show how a well established programming concept, the continuations, can significantly facilitate the writing of such behavioral components, while bringing some flexibility and better performance in their implementation.

Section 2 introduces continuations, their applications and variants. Section 3 identifies implementation issues in conversational MAS, and the classical solutions proposed by multi-agent platforms. We present our continuation based approach in section 4, followed in section 5 by the results of an example test, and then conclude on its benefits, limitations, and integration into existing MAS platforms.

Introduction to continuations

Continuation are a well established programming concept, described for example by Strachey et al. [START_REF] Strachey | Continuations: A mathematical semantics for handling full jumps[END_REF] in the early seventies, which were originally present in functional programming languages such as Scheme or ML, in the actor model of Hewitt [START_REF] Hewitt | Viewing control structures as patterns of passing messages[END_REF], and in various process calculi.

The principle consists in capturing the currently executing program state into a variable or artifact that can be manipulated programmatically, called the continuation, in order to be able to resume again the program from this state, by activating the continuation. More precisely, we designate by execution context the program state, in reference to the execution context of a thread or process, and by continuation the object or artifact allowing to activate (i.e. switch to) this execution context. Some informal definitions of continuations are found in the literature, such as "the rest of the program", or "goto with parameters", however none of them are really satisfactory: the first implies a linear execution of the program, that should be unwind beforehand, and the second does not express that local variables and call stack are captured in a continuation.

Although there exist variants and restrictions of continuations, such as coroutines and generators (see section 2.2); continuations remain the most general form, as shown by Haynes et al. in [START_REF] Haynes | Obtaining coroutines with continuations[END_REF] and Allison in [START_REF] Allison | Continuations Implement Generators and Streams[END_REF].

Continuations are somehow related to threads, since they capture all, or part of, the stack, including local variables, in addition to the "program counter"; however their activation is done programmatically rather than by an operating system scheduler.

Implementations and examples

For illustrative purpose, we will borrow examples from various languages that support continuations natively, such as Scheme or Ruby, as well as a restricted form of continuation, to start with: Python's generators.

def simple_generator(max): i = 1 yield "let's count.." while i < max: yield "Odd %d" % i i = i+1 yield "Even %d" % i i = i+1 yield "the end" for s in simple_generator( 4 As figure 1 suggests, a generator behaves the same way as an iterator, written however as a function that returns successive values, using the yield keyword, while memorizing its current execution state between each call (see Mertz [START_REF] Mertz | Charming Python: Iterators and simple generators[END_REF]).

The advantage of generators is that the programmer does not have to explicitly manage the iterator state, using object attributes. Indeed, generators make it possible to use the flow control structures of the language (if, loops, etc.) to manage transitions between the states of the underlying automaton, as shown by Mertz in [START_REF] Mertz | Charming Python: Generator-based state machines[END_REF]. In object based languages, capturing the current execution context has the side effect of interrupting the control flow, to take it back to the caller of the "continuable" function or object, as does yield in a generator. In a sense, the continuation is relative to this callable object. In functional language however, and in Ruby, the continuation is "global" to the program, and is created implicitly by a primitive that calls a target function or lambda expression, and pass it the continuation as parameter. The callcc primitive (call with current continuation), in figure 2, calls the anonymous closure defined by the next bloc between brackets, and passes the continuation as the parameter cont. The continuation activation, cont.call(), results in the premature exit of the two for loops, by taking the control flow just after this bloc.

Note that this program could be translated in Scheme very easily, by using the Scheme primitive call-with-current-continuation. Other programming languages support continuation natively in their most complete implementations: we can mention for example Smalltalk, Haskel, and Perl 6.

More recently, continuations have been added as libraries or extensions to common object based imperative language like Javascript or Java. Since this type of extension is related to flow control and low level stack manipulation, it requires either a modification of the interpreter, class instrumentation and manipulation techniques, or source code transformations, as shown by Pettyjohn et al. in [START_REF] Pettyjohn | Continuations from Generalized Stack Inspection[END_REF]. Good examples are:

• Flowscript1 , a modified version of the Rhino Javascript interpreter implementing continuations, part of the apache Cocoon framework since version 2; • The RIFE web application framework2 , which allows limited continuations;

• And the Javaflow framework 3 , which implements continuations in Java, using a dynamic class instrumentation technique, which we will use hereafter. Figure 3 gives a simple implementation of Python style generator in Java, using Javaflow. On the contrary to Ruby or Scheme, the continuation represents here the execution state inside the Runnable object passed to the continuation capture routine, and not the execution state in the calling function. In this example, it is necessary to temporarily store the return values of the generator in the result attribute, since Javaflow does not handle continuation parameters and return values like Ruby. 1, translated in Java, and using the generator class of figure 3. The console output is identical. To work properly, these classes need to be instrumented by Javaflow at compile or class loading time.

Variants and applications

The possibilities offered by continuations and closures are numerous: one can rewrite existing or custom flow control structures, for example simulating a goto in Scheme. However the most useful applications of continuation are:

• The implementation and composition of automatons (for example in syntactic parsers and validators), that we will further develop in section 4.1; • Coroutines and cooperative threads. Coroutines are functions that retain their execution state when calling another coroutine. On the contrary to generators, coroutines never return after capturing its state, but explicitly call another coroutine that will in turn be activated. Coroutines thus allow defining cooperative threads, with explicit context switching. The main advantage is performance: cooperative threads are lightweight and fast compared to real preemptive threads. This technique is not suited when preemption is necessary, but is well suited to non preemptive concurrent models and event programming; • Continuation based Web application programming, described by Tate et al. in [START_REF] Tate | Crossing borders: Continuations, Web development, and Java programming, A stateful model for programmers, a stateless experience for users[END_REF],

which has recently focused a lot of attention. Historically introduced by the Web application framework Seaside, this technique has been followed in other frameworks like RIFE or Cocoon. The reason is simple: the interaction between a Web server and a web browser usually takes the form of a stateful conversation, for which it is necessary to store the state on the server. The routines controlling the page flow can use continuations to store this state implicitly, relieving the programmer from this tedious and error prone task. Page flow is then described as a simple instruction flow in a script. This principle being simple and elegant, it has quickly been adopted by many Web application developers.

Remark. Such a behavior may be obtained using threads; however this is usually not feasible in practice, since it would require one thread for each possible conversational state during a session, which would result in too many threads, especially if the server implements the web browser back button behavior.

Conversational agent engineering

We define here a conversational agent as an agent whose behavior requires memorizing the local context of the ongoing interactions, which we refer to as conversation. This context may take various forms. In this work we focus on agents communicating by asynchronous messages, organized into inter-related message sequences, the conversations, between several participants, in the context of a collective task.

Problem definition

Experience shows that, though bringing many useful properties to the system that they compose, conversational agents are difficult to implement. In particular, we can identify the following difficulties related to conversation management:

• Multi-party conversation parallelism. In a multi-party conversation, it is necessary to combine several behaviors simultaneously, corresponding to the bilateral subconversations with each participant separately, and possibly synchronize them; • Internal parallelism. A bilateral conversation with a single participant can itself comprise some form of parallelism: it may fork into several parallel or interlaced branches of the conversation; • Protocol error management. A great part of the complexity implied by conversation management comes from the asynchronous error management: protocol errors, timeouts, etc. This aspect being transverse, it is difficult to modularize and reuse;

Remark. The programming languages used in MAS platform are not concurrent languages, and, thus, are not designed to handle elaborate parallel processing. Concurrent languages, such as Erlang for example, could address some of these issues; however they suffer from other limitations, and are unfortunately not popular enough to have been chosen in existing MAS platforms.

It is interesting to observe that most MAS platforms propose componential approaches in order to promote reusing of behavioral components, which confirms the importance of the difficulties identified above in MAS design and implementation. The problem then becomes: how to define behavioral components in a modular way, that is to say, decoupled and encapsulated in reusable components; and how to combine and synchronize several behavioral components consistently in agents.

Considering for example FIPA interaction protocols, a FIPA compliant platform will typically propose abstract behavioral components implementing partially these protocols, and bound to the agent specific code using a platform specific composition technique (callbacks, inheritance, or event model).

Behavior component libraries help the programmer to deal with delicate aspects of conversation management, such as: timeouts, protocol error handling, following a group of participants in parallel, etc. These libraries are well developed and largely used in MAS platforms. Two strategies are possible to implement such components:

• Either a thread is assigned to each parallelizable branch of each behavioral component. A waiting state is then implemented as a blocking method on this thread, and the conversational state is defined by all the threads execution contexts. This option is not always feasible since, as we discussed it in the case of web applications, it may involve too many threads: the number of available threads is limited by the operating system, and too many threads may result in a performance loss due to an excessive scheduling with respect to the actual processing; • Or the conversational state of the behavioral component is stored explicitly. This implies that the corresponding code be fragmented according to the transitions and structure of the underlying automaton, so that it may be executed step by step, by interrupting and resuming its execution at each state. Typically, distinct methods or objects will represent the various transitions, themselves associated to objects representing the states. This technique is the most widely used, because it gives more control on the activation of the behavior components, and on the number of threads allocated. The FIPA-OS platform, described by Poslad et al. in [START_REF] Poslad | The FIPA-OS Agent Platform Open Source for Open Standards[END_REF], uses a global thread pool to activate the behavioral components of agents (called task in FIPA-OS), whereas Jade, a MAS platform described by Bellifemine et al. [START_REF] Bellifemine | JADE -A FIPA-compliant agent framework[END_REF], assigns by default one thread per agent.

Continuation-based approach

As we stated above, the need to manage parallelism and asynchrony without requiring dedicated threads implicates that behavioral components be manipulated like automatons, without blocking on threads. Besides, since existing MAS platforms comply with this strategy, our approach should also comply with it to facilitate integration. On the other hand, being able to write stateful behaviors as simple routines, leveraging native control flow structures of the hosting language, as with the first strategy described in section 3.1, but without suffering from the usual inter-thread synchronization problems, would also make MAS programmers' life easier.

With respect to these issues, continuations offer a particularly elegant solution that combines the best of both worlds. Indeed, using continuations in MAS behavioral components for conversation management allows to:

• Capture the conversation or conversation branch state implicitly in the continuation, including call stack and local variables, so that the component may be used as an automaton, without having to explicitly manipulate its state; • Get rid of inter-thread synchronization problems, since this model is not preemptive and transitions are executed sequentially.

Continuation-based automaton behavioral component

A continuation represents a program states, usually as an immutable object in object based language, but is not itself an automaton: it requires an encapsulating automaton object, similar to the generator implementation presented in section 2.1. Figure 6 shows a minimal automaton abstract base class, containing:

• a current attribute, storing a single current continuation for this automaton;

• the activate() method, the automaton step by step activation point, that updates the current continuation with a new one, corresponding to the new captured state; • a continuation capturing method, yield(), meant to be used in implementations of the abstract run() method, or other methods called by run(), that interrupts the normal control flow and jumps to the activate() method; In order to be usable in an actual agent implementation, however, these primitives are not sufficient: a way to consume events, like messages or timeouts, in the run() method, is necessary. In the case of a conversational agent platform, an agent is in principle provided with a message queue. A behavior component message queue may also be considered, associated to a message dispatch mechanism at the agent level. Such dispatch will typically be based on message response or conversation identification parameters, such as FIPA conversation-id message parameter. In comparison with the Jade component of figure 5, the version shown on figure 7 is much easier to read: it does not contain any object attribute to store and manage state information, nor does it require code fragmentation. The loop is materialized by a normal java for statement, increasing readability and reducing error proneness.

Example and comparison

Pseudo parallelism and synchronization primitives

In order to address the parallelism requirements mentioned in section 3.1, it is necessary to introduce synchronization and pseudo-parallelism mechanisms in our automaton abstract classes. We use the term "pseudo-parallelism" since transitions will in fine always be executed sequentially. However, sub-automaton states corresponding to parallel branch of the conversation need to be stored and updated separately.

The case of multi-bilateral conversations (i.e. conversations involving an initiator and a group of participants), in particular, is quite common in protocols such negotiations or auctions. This case requires interacting in parallel with n participants, possibly synchronizing at key steps of the protocol, even if the various participants all play the same role and are thus governed by the same rules in the protocol.

We introduce two primitives to handle this kind of parallelism: • parallelize(), a primitive allowing to switch to parallel mode, duplicating the current automaton in n sub-automatons, one per participant; • and join(), the reverse primitive, usable only in parallel mode, that waits for all sub-automatons to reach this point (note that this does not entail blocking on a thread), before switching back to synchronous mode;

In figure 8 the whole management of this auction protocol role is handled in a few simple lines of code, which demonstrates the applicability and elegance of this approach. An equivalent behavior, implemented using classical explicit finite state automaton, would require numerous states, conditions and switches, and would result in a fragmented code, difficult to read and debug. Note that the variables bestOffer, nbAnswered and winner are here attributes of the EnglishAuctionInitiator class. These attributes are necessary here to communicate between sub-automatons in parallel mode, since Javaflow does not support parameter passing (see the generator example in section 2.1).

The participant roles, quite symmetrical to the initiator roles, do not require of course the use of parallelize() and join(), since they don't comprise parallelism. Similarly to cooperative thread with respect to preemptive threads, a non preemptive activation of agents' behavior components, using continuation, give better performances. To evaluate this gain, we have compared the execution time of two versions of our prototype: a preemptive version with one thread per behavior component and per agent, and a non preemptive one, using round-robin activation and continuations. In this test the initiator and participant agents combine the handshake and auction behaviors. The results exhibit an average gain of 50% using Javaflow continuations.

Performance

Conclusion and future works

In this paper we have shown how to use continuations to facilitate conversational agents' behavioral components engineering. This approach allows an elegant, concise and intuitive coding of agents behavior dynamics, in the form of automatons written as "resumable" functions similar to coroutines or generators, while relieving the pro- grammer from the explicit management of the automaton state and transitions. This approach also allows benefiting from the host language native flow control structure. Its integration into existing platforms only depends on the support of continuations in the host language, and is quite straightforward. It gives to the designer a great flexibility in the mode of activation of agents and their behavior components.

In the general case, it allows to get rid of multithreading synchronization problems, but can still be combined with multithreading if necessary.

The main perspective to this work is the integration to Jade platform, by defining a ContinuationBehavior. If the adoption of continuations in the MAS community follows its adoption in the Web application programming community, they will have represent a promising new technology for agents, and become a common practice.

Fig. 1 .

 1 Fig. 1. Simple Python generator example: on the left the generator definition; on the right the code to display the successive values returned by the generator, and the console output in italic.

Fig. 2 .

 2 Fig. 2. Continuation example in Ruby, with the console output on the right (in italic)

Fig. 3 .

 3 Fig. 3. Basic implementation of Python style generators in Java, using Javaflow continuations

Fig. 4 .

 4 Fig. 4. Simple generator example in Java, instrumented by JavaflowFigure 4 takes back the example of figure 1, translated in Java, and using the generator class of figure 3. The console output is identical. To work properly, these classes need to be instrumented by Javaflow at compile or class loading time.

Fig. 6 .

 6 Fig.6. Simple continuation-based behavioral automaton abstract class, in Java, using Javaflow. Each time activate() is executed, the automaton advances one step. Each step terminates either by invoking yield(), or by the normal end of the run() method. In both cases this gives back control to activate(), which updates the continuation and returns normally.

Fig. 7 .

 7 Fig. 7. Continuation-based version of the 3 states automaton behavior of section 3.2, figure 5.

Fig. 9 .

 9 Fig. 9. Execution time, function of the number of participant agents. The upper curve corresponds to the preemptive version, the lower curve the non preemptive version.

http://cocoon.apache.org/2.1/

http://rifers.org/

http://jakarta.apache.org/commons/sandbox/javaflow/

http://www.madkit.org/

Automaton behavioral components

In Jade, behavioral components are named behaviors, and are all inherited from the abstract Behavior class. Figure 5 shows a simple 3 states behavior example, illustrating the explicit state management, and resulting code fragmentation, in the switch statement. Although not obvious from first reading, this behavior is looping two times on the three states before termination. In this example the SimpleBehavior class does not contribute much to the behavior; however, other available behaviors, like ContractNetInitiator, or AchieveRE-Initiator, define abstract implementations of common interaction protocols, bound to the agent specific code by inheritance or callback. Some composite behaviors allow various types of composition of children behavior, for example SequenceBehavior or ParallelBehavior. Inter-thread synchronization is usually not necessary in Jade since transitions are executed sequentially.

Comparable techniques can be found in other MAS platforms. Let us mention for example the multi-plan automatons of the Bond platform, by Bölöni et al. [START_REF] Bölöni | A Multi-Plane State Machine Agent Model[END_REF]; the finite state automatons of the Zeus platform, by Nwana et al. [START_REF] Nwana | ZEUS: A Toolkit and Approach for Building Distributed Multi-Agent Systems[END_REF]; the FIPA-OS tasks, by Poslad et al. [START_REF] Poslad | The FIPA-OS Agent Platform Open Source for Open Standards[END_REF]; or the automatons designed with SEdit in the MadKIT platform 4 .

The multi-plan automatons of Bond, in particular, handle the parallelism using a simplified parallel sub-automatons composition model; whereas FIPA-OS tasks are by default executed in parallel: they may launch other sub-tasks, but this requires careful multithread synchronization.

Denis Jouvin

Testing framework

In the context of this work we have realized a testing prototype and framework based on Javaflow. Two abstract classes, BilateralRole In order to represent both forms of parallelism related to conversation management, we have defined four behavioral components, corresponding respectively to: the initiator and participant roles of a simple multi-bilateral handshake protocol, consisting in a linear sequence of inform message exchanges; and the initiator and participant roles of an English auction protocol, comparable to FIPA-English-Auction. 5 By lack of space, the algorithm used to implement parallelize() and join() are not detailed here. The corresponding Java code may be downloaded from the author's web page.

Parallel section:

here the automaton is duplicated in n subautomatons, managed by n continuations, until all of them reach join(), which switches back to synchronous mode propose, inform, refuse, cfp, accept and reject are values of the enumerated type Message.Type


Samer Dweik
email: samer.dweik@math.u-psud.fr

LACK OF REGULARITY OF THE TRANSPORT DENSITY IN THE MONGE PROBLEM

In this paper, we provide a family of counter-examples to the regularity of the transport density in the classical Monge-Kantorovich problem. We prove that the W 1,p regularity of the source and target measures f ± does not imply that the transport density σ is W 1,p , that the BV regularity of f ± does not imply that σ is BV and that f ± ∈ C ∞ does not imply that σ is W 1,p , for large p.

Introduction

The mass transport problem dates back to a work from 1781 by Gaspard Monge, Mémoire sur la théorie des déblais et des remblais ( [START_REF] Monge | Mémoire sur la théorie des déblais et des remblais[END_REF]), where he formulated a natural question in economics which deals with the optimal way of moving points from one mass distribution to another so that the total work done is minimized. In his work, the cost of moving one unit of mass from x to y is measured with the Euclidean distance |x -y|, even though many other cost functions have been studied later on.

In order to explain this problem in full details, let us consider f ± two given finite positive Borel measures in Ω satisfying the mass balance condition f + (Ω) = f -(Ω), where Ω is a compact convex set in R d . Let |.| stand for the Euclidean norm in R d . Then, the classical Monge optimal transportation problem ( [START_REF] Monge | Mémoire sur la théorie des déblais et des remblais[END_REF]) consists in finding a transport map T : Ω → Ω minimizing the functional

T → Ω |x -T (x)| df + ,
among all Borel measurable maps T : Ω → Ω which satisfy the "push-forward" condition T # f + = f -, i.e f -(A) = f + (T -1 (A)) for every Borel set A ⊂ Ω.

The existence of optimal maps was addressed by many authors [START_REF] Ambrosio | Lecture notes on optimal transport problems[END_REF], [START_REF] Caffarelli | Constructing optimal maps for Monge's transport problem as a limit of strictly convex costs[END_REF], [START_REF] Evans | Differential equations methods for the Monge-Kantorovich mass transfer problem[END_REF], [START_REF] Sudakov | Geometric problems in the theory of infinite-dimensional probability distributions[END_REF] and [START_REF] Trudinger | On the Monge mass transfer problem[END_REF] (see [START_REF] Champion | The Monge problem in R d[END_REF] for the most general result, which is valid for arbitrary norms ||x-y||; however in this paper we will concentrate only on the Euclidean case). Although this problem may have no solutions, its relaxed setting (which is the Kantorovich problem [START_REF] Kantorovich | On the transfer of masses[END_REF]) always has one. The relaxed problem consists in finding a Borel measure λ over Ω × Ω (called optimal transport plan) satisfying π ± # λ = f ± , where π ± : Ω × Ω → Ω being the projections on the first and second factor, respectively (i.e π ± (x + , x -) := x ± ), which minimizes the functional λ → Ω×Ω |x -y| dλ among all Borel measures λ on Ω × Ω satisfying π ± # λ = f ± . For the details about Optimal Transport theory, its history, and the main results, we refer to [START_REF] Santambrogio | Optimal Transport for Applied Mathematicians in Progress in Nonlinear Differential Equations and Their Applications[END_REF] and [START_REF] Villani | Topics in Optimal Transportation[END_REF]. It is also possible to prove that the maximization of the functional

u → Ω u d(f + -f -),
among all the 1-Lipschitz functions u on Ω, is the dual to the Kantorovich problem (a maximizer for this problem is called Kantorovich potential). This duality implies that optimal λ and u satisfy u(x) -u(y) = |x -y| on the support of λ, but also that, whenever we find some admissible λ and u satisfying Ω×Ω |x -y|dλ = Ω ud(f + -f -), they are both optimal (a maximal segment [x, y] such that u(x) -u(y) = |x -y| is called transport ray). In such a theory it is classical to associate with any optimal transport plan λ a positive measure σ on Ω, called transport density, which represents the amount of transport taking place in each region of Ω. This measure σ is defined by

(1.1) < σ, ϕ >= Ω×Ω dλ(x, y) 1 0 ϕ((1 -t)x + ty)|x -y| dt for all ϕ ∈ C(Ω).
It is well known that (σ, u) solves a particular PDE system, called Monge-Kantorovich system:

(1.2)

         -∇ • (σ∇u) = f + -f -in Ω σ∇u • n = 0 on ∂Ω, |∇u| ≤ 1 in Ω, |∇u| = 1 σ -a.e.
The L p regularity of the transport density σ is proved successively by many authors (see, for instance, [START_REF] Pascale | Integral estimates for transport densities[END_REF][START_REF] Pascale | Regularity properties for Monge Transport Density and for Solutions of some Shape Optimization Problem[END_REF][START_REF] Pascale | Sharp summability for Monge Transport density via Interpolation[END_REF][START_REF] Feldman | Uniqueness and transport density in Monge's mass transportation problem[END_REF][START_REF] Santambrogio | Absolute continuity and summability of transport densities: simpler proofs and new estimates[END_REF]). In particular, we have the following

Proposition 1.1. Suppose f + ≪ L d or f -≪ L d .
Then, the transport density σ is unique (i.e does not depend on the choice of the optimal transport plan λ) and σ ≪ L d . Moreover, if both f + , f -∈ L p (Ω), then σ also belongs to L p (Ω).

The higher order regularity of the transport density σ is still widely open; the only known results are in R 2 : if f ± are two positive densities, continuous and have compact, disjoint, convex support, then the "monotone optimal transport map" T is continuous except on a negligible set (the endpoints of transport rays) and the transport density σ is actually continuous everywhere ( [START_REF] Fragalà | Continuity of an optimal transport in Monge problem[END_REF]). Moreover, in [START_REF] Li | Continuity for the Monge mass transfer problem in two dimensions[END_REF], the authors prove the continuity of the same map T under the assumptions that f ± are two positive densities, continuous with spt(f + ) ⊂ spt(f -) and one of the sets {f + > f -}, {f -> f + } is convex (it will be that the transport density σ is also continuous in this case). Other results exist as far as the regularity in some directions is concerned: in [START_REF] Evans | Differential equations methods for the Monge-Kantorovich mass transfer problem[END_REF], it has been proven that when f ± are Lipschitz continuous with disjoint supports (and with some extra technical condition on the supports), then the transport density is locally Lipschitz continuous "along transport rays". Also in [START_REF] Buttazzo | On Regularity of Transport Density in the Monge-Kantorovich Problem[END_REF], the authors have a more general result for the case of just summable f ± without any extra conditions on supports; they prove that if f ± ∈ L p (Ω), then for a.e x ∈ Ω, the transport density σ ∈ W 1,p loc (R x ), where R x is the transport ray passing through x. As one can see, the W 1,p (Ω) (C 0,α (Ω), BV (Ω), ...) regularity of the transport density σ is an interesting question, and the aim of this paper is to give a (negative) answer to it! In this paper we focus on examples relating the regularity of the initial data f ± with the regularity of the transport density σ. As a starting point, the following example shows that in general, the transport density σ is not more regular than the initial data : consider

χ + := [0, 1] 2 , χ -:= [2, 3] × [0, 1] and set f + (x 1 , x 2 ) := f 1 (x 1 )f 2 (x 2 )
, where we suppose that f + is concentrated on χ + , and take f -(x 1 , x 2 ) := f + (x 1 -2, x 2 ), for every (x 1 , x 2 ) ∈ χ -. In this case, it is easy to compute the transport density σ between f ± , so we get σ(x 1 , x 2 ) = ( x1 0 f 1 (t) dt)f 2 (x 2 ) for every x ∈ χ + . Hence, the transport density σ has the same regularity as f ± in the x 2 -variable. Yet, we will give examples where the regularity of the transport density σ is worse than the regularity of the initial data f ± . In particular, we will prove among others the following statements:

f ± ∈ W 1,p (Ω) ⇒ σ ∈ W 1,p (Ω), ∀ p > 1, (1.3) f ± ∈ BV (Ω) ⇒ σ ∈ BV (Ω), (1.4) f ± ∈ C ∞ ( Ω) ⇒ σ ∈ W 1,3 (Ω). (1.5) la -a Figure 1.

Main Results

Inspired by [START_REF] Colombo | Obstructions to regularity in the classical Monge problem[END_REF][START_REF] Li | Regularity in Monge's mass transfer problem[END_REF], we will construct a family of counter-examples by, first, choosing which lines will be transport rays. Set γ > 0 and consider the following transport rays:

(2.1)

l a := (x 1 , x 2 ) ∈ R 2 : x 2 = a γ 2 (x 1 + a), x 1 ∈ (-a, 1) , a ∈ [0, 1].
It is clear that the segments l a do not mutually intersect. The domain representing both source and target will be ∆ ⊂ R 2 (see Figure 1), where

∆ := interior of the triangle with vertices (-1, 0), (

The initial and final density will have the form

(2.3) f + (x 1 , x 2 ) = 1, f -(x 1 , x 2 ) = 1 + β(ζ ′′ (x 1 ) + η ′′ (x 2 )) for all x := (x 1 , x 2 ) ∈ ∆, where ζ(x 1 ) := -x 2 1 (x 1 -1) 2 (the choice of ζ is made essentially in such a way that ζ(1) = ζ ′ (1) = 0), η is a C 2 function with η(0) = η ′ (0) = 0
and β > 0 is chosen so that f -will be a non-negative density. Note that η is constructed in such a way that the following mass balance condition for the region in the domain below each l a is satisfied:

(2.4) ∆a f + = ∆a f -for all a ∈ [0, 1],
where ∆ a is the subgraph of l a in ∆, namely the triangle formed by (-a, 0), (1, 0) and (1, a γ 2 (1 + a)); or equivalently, (2.4) can be rewritten as

- ∆a ζ ′′ (x 1 ) dx 1 dx 2 = ∆a η ′′ (x 2 ) dx 1 dx 2 for all a ∈ [0, 1].
Yet, it is easy to see that

- ∆a ζ ′′ (x 1 ) dx 1 dx 2 = - a γ 2 (1+a) 0 1 2 a γ x2-a ζ ′′ (x 1 ) dx 1 dx 2 = a γ 2 (1+a) 0 ζ ′ 2 a γ x 2 -a dx 2 = a γ+2 2 (1 + a) 2
and as η(0) = η ′ (0) = 0, we have

∆a η ′′ (x 2 ) dx 1 dx 2 = 1 -a a γ 2 (x1+a) 0 η ′′ (x 2 ) dx 2 dx 1 = 1 -a η ′ a γ 2 (x 1 + a) dx 1 = η( a γ 2 (1 + a)) a γ 2 .
Then,

η(s) = s 2 a 2 (s), ∀ s ∈ (0, 1)
where a(s) is the unique solution of

(2.5) s = a γ 2 (1 + a).
Yet, by the implicit function theorem, it is easy to see that there exists a C ∞ function h defined in a neighborhood of 0 such that

s = h(s) 2 1 γ (1 + h(s)) 1 γ .
Hence, h(s

1 γ ) is a solution to (2.5) and η(s) = s 2 h 2 (s 1 γ
). After tedious computations, we can check that

η ′ (s) = 2s h 2 (s 1 γ ) + 2 γ s 1 γ +1 h(s 1 γ ) h ′ (s 1 γ ), η ′′ (s) = 2 h 2 (s 1 γ ) + 6 γ + 2 γ 2 s 1 γ h(s 1 γ ) h ′ (s 1 γ ) + 2 γ 2 s 2 γ ( (h ′ (s 1 γ )) 2 + h(s 1 γ ) h ′′ (s 1 γ )), η ′′′ (s) = 4 γ + 6 γ 2 + 2 γ 3 s 1 γ -1 h(s 1 γ ) h ′ (s 1 γ ) + 6 γ 3 + 6 γ 2 s 2 γ -1 ( (h ′ (s 1 γ )) 2 + h(s 1 γ ) h ′′ (s 1 γ )) + 6 γ 3 s 3 γ -1 h ′ (s 1 γ ) h ′′ (s 1 γ ) + 2 γ 3 s 3 γ -1 h(s 1 γ ) h ′′′ (s 1 γ ),
and

η ′′′′ (s) = 14 γ 4 + 12 γ 3 - 2 γ 2 s 2 γ -2 (h ′ (s 1 γ )) 2 + 2 γ 4 + 4 γ 3 - 2 γ 2 - 4 γ s 1 γ -2 h(s 1 γ ) h ′ (s 1 γ ) + 6 γ 4 s 4 γ -2 (h ′′ (s 1 γ )) 2 + 14 γ 4 + 12 γ 3 - 2 γ 2 s 2 γ -2 h(s 1 γ ) h ′′ (s 1 γ ) + 30 γ 4 + 12 γ 3 s 3 γ -2 h ′ (s 1 γ ) h ′′ (s 1 γ ) + 8 γ 4 s 4 γ -2 h ′ (s 1 γ ) h ′′′ (s 1 γ ) + 12 γ 4 + 4 γ 3 s 3 γ -2 h(s 1 γ ) h ′′′ (s 1 γ ) + 2 γ 4 s 4 γ -2 h(s 1 γ ) h ′′′′ (s 1 γ ).
Hence,

(2.6)

               η(|.|) ∈ C ∞ (R) if γ = 1 2 , η ∈ C ∞ [0, +∞) and η(|.|) ∈ C 4,1 (R) if γ = 1, η(|.|) ∈ C 3, 2 γ -1 (R) if 1 < γ < 2, η ∈ C 3 [0, +∞) and η(|.|) ∈ C 2,1 (R) if γ = 2, η(|.|) ∈ C 2, 2 γ (R) ∩ W 3, γ γ-2 -ε (R) if γ > 2, ε > 0.
Now, we will introduce the following key propositions, whose proofs, for simplicity of exposition, are postponed to Section 3.

Proposition 2.1. The transport density σ between f + and f -is not in W 1,p (∆) for all p satisfying

p ≥ min γ γ -1 , γ + 2 γ .
Corollary 2.2. We have the following statements:

f ± ∈ W 1,p (∆) ⇒ σ ∈ W 1, 2p+ε p+1 (∆), ∀ ε > 0, p > 1, (2.7) f ± ∈ C 1 ( ∆) ⇒ σ ∈ H 1 (∆), (2.8) f ± ∈ C 1,α (∆) ⇒ σ ∈ W 1,2+α (∆), ∀ α ∈ (0, 1), (2.9) f ± ∈ C ∞ ( ∆) ⇒ σ ∈ W 1,3 (∆). (2.10)
Proof. These statements follow immediately from (2.6) and the proposition 2.1. Indeed, for γ > 2:

η ′′ ∈ W 1, γ γ-2 -ε (R) (for all ε > 0)
and the transport density σ is not in W 1, γ γ-1 (∆), so (2.7) follows. To prove (2.8), take γ = 2 and then, in this case, we have that

η ′′ ∈ C 1 (R) and σ / ∈ H 1 (∆). For 1 < γ < 2: η ′′ ∈ C 1, 2 γ -1 (R) and σ / ∈ W 1, γ+2 γ (∆)
, so (2.9) follows. Finally, for γ = 1: η ′′ ∈ C ∞ (R) and σ / ∈ W 1,3 (∆) and the statement (2.10) follows.

Proposition 2.3. The transport density σ between f + and f -is not in C 0, 1 γ+1 +ε (∆), for all ε > 0.

Corollary 2.4. We have the following statements:

f ± ∈ C 0,α (∆) ⇒ σ ∈ C 0, α α+2 +ε (∆), ∀ ε > 0, α ∈ (0, 1), (2.11) f ± ∈ C 1 ( ∆) ⇒ σ ∈ C 0, 1 3 +ε (∆), ∀ ε > 0, (2.12) f ± ∈ C 1,α (∆) ⇒ σ ∈ C 0, 1+α 3+α +ε (∆), ∀ ε > 0, α ∈ (0, 1), (2.13) f ± ∈ C ∞ ( ∆) ⇒ σ ∈ C 0, 1 2 +ε (∆), ∀ ε > 0. (2.14)
Proof. These statements follow immediately from (2.6) and the proposition 2.3. Indeed, for γ > 2:

η ′′ ∈ C 0, 2 γ (R), for γ = 2: η ′′ ∈ C 1 (R), for 1 < γ < 2: η ′′ ∈ C 1, 2 γ -1 (R) and, finally, for γ = 1: η ′′ ∈ C ∞ (R).
Yet, in all these cases, the transport density σ / ∈ C 0, 1 γ +ε (∆), for all ε > 0.

To obtain counter-examples to interior regularity of the transport density, it suffices to reflect the domain across the x 1 -axis. Let ∆ ′ be the reflection of ∆ with respect to the x 1 -axis (see Figure 2) and set Ω := ∆ ∪ ∆ ′ . Extend the functions f ± to Ω so that they are symmetric with respect to the x 1 -axis. Let T be an optimal transport map between f ± and let σ be the transport density between them, then it is easy to prove that the map S, which is equal to T on ∆ and to the reflection of T with respect to the x 1 -axis on ∆ ′ , is an optimal transport map between the extended densities and the transport density between them is equal to σ on ∆ and to the reflection of σ, with respect to the x 1 -axis, on ∆ ′ . Using this fact and (2.6), we get the following statements:

f ± ∈ W 1,p (Ω) ⇒ σ ∈ W 1, 2p+ε p+1 loc (Ω), ∀ ε > 0, p > 1, (2.15) f ± ∈ C 0,α (Ω) ⇒ σ ∈ C 0, α α+2 +ε loc (Ω), ∀ ε > 0, α ∈ (0, 1), (2.16) f ± ∈ C 0,1 (Ω) ⇒ σ ∈ H 1 loc (Ω) ∪ C 0, 1 3 +ε loc (Ω), ∀ ε > 0, (2.17) f ± ∈ C 1,α (Ω) ⇒ σ ∈ W 1,2+α loc (Ω) ∪ C 0, 1+α 3+α +ε loc (Ω), ∀ ε > 0, α ∈ (0, 1), (2.18) f ± ∈ C 2,1 (Ω) ⇒ σ ∈ W 1,3 loc (Ω) ∪ C 0, 1 2 +ε loc (Ω), ∀ ε > 0, (2.19) f ± ∈ C ∞ ( Ω) ⇒ σ ∈ W 1,5 loc (Ω) ∪ C 0, 2 3 +ε loc (Ω), ∀ ε > 0. (2.20) ∆ ∆ ′ Figure 2.

Proof

In this section, we want to prove Propositions 2.1 & 2.3. Firstly, we will compute the transport density σ between f + and f -. To do that, let us observe that the family {l a , a ∈ (0, 1)}, where l a is defined as in (2.1), covers ∆ so that for every x := (x 1 , x 2 ) ∈ ∆, there exists a unique pair (t, a) ∈ (0, 1) 2 such that x ∈ l a and |x -(-a, 0)| = t l(a), where l(a) is the length of l a . In other words, we have

x = -a + (1 + a)t , (1 + a) ta γ 2 .
Fix (t, a) ∈ (0, 1) 2 and set,

ω ε := -s + (1 + s)τ, (1 + s) τ s γ 2 , (τ, s) ∈ [0, t] × [a, a + ε]
where ε > 0 is small enough. Recalling (1.2) and integrating -∇ • (σ∇u) = f on ω ε , we get

(3.1) - ∂ωε σ∇u • n = ωε f.
Suppose that the family of segments (l a ) a∈(0,1) are, in fact, all the transport rays on which the optimal transport map, between f + and f -, acts. In this case, we get that for every x ∈ l a :

∇u(x) = (-a, 0) -(1, (1 + a) a γ 2 ) |(-a, 0) -(1, (1 + a) a γ 2 )| = -(1, a γ 2 ) 1 + ( a γ 2 ) 2
, which means that ∇u(x) • n = 0 if n is the unit orthogonal vector to l a . Hence, (3.1) becomes

(3.2) - sε σ∇u • n = ωε f where s ε := (-s + (1 + s)t, (1 + s) ts γ 2 ), s ∈ [a, a + ε] . Yet, we have ωε f (x 1 , x 2 ) dx 1 dx 2 = ωε -β(ζ ′′ (x 1 ) + η ′′ (x 2 )) dx 1 dx 2 = a+ε a t 0 -β ζ ′′ (-s + (1 + s)τ ) + η ′′ (1 + s) τ s γ 2 J(τ, s) dτ ds,
where

J := | det(D (τ,s) (x 1 , x 2 ))|. Yet, D (t,a) (x 1 , x 2 ) :=   ∂ t x 1 ∂ a x 1 ∂ t x 2 ∂ a x 2   =   1 + a -1 + t (1+a) a γ 2 (γ (1 + a) + a) ta γ-1 2   .
Then,

(3.3) J(t, a) = (1 + a)(γ (1 + a) t + a) a γ-1 2 .
On the other hand,

-∇u • n = ∂ t x |∂ t x| • R ∂ a x = J(t, a) l(a)
where R := 0 1 -1 0 is the rotation matrix. Hence,

- sε σ∇u.n = a+ε a σ -s + (1 + s)t, (1 + s) ts γ 2 J(t,
= lim ε→0 + 1 ε a+ε a t 0 -β ζ ′′ (-s + (1 + s)τ ) + η ′′ (1 + s) τ s γ 2 J(τ, s) dτ ds.
Finally, we get

(3.4) σ(x) = l(a) t 0 -β(ζ ′′ (-a + (1 + a)τ ) + η ′′ ((1 + a) τ a γ 2 )) J(τ, a) dτ J(t, a)
. Now, we are ready to prove Proposition 2.3. Indeed, for every ε > 0, let (t ε , a ε ) be in (0, 1) 2 such that

x ε := (0, ε) = -a ε + (1 + a ε )t ε , (1 + a ε ) t ε a γ ε 2 .
As ζ ′′ (0) < 0 and η ′′ (0) = 0, then, from (3.4), we can see easily that, close to the origin, we have

σ ≈ t 0 J(τ, a) dτ J(t, a)
where f ≈ g means that there exist c ± > 0 such that c -g ≤ f ≤ c + g. Yet, by (3.3), one has

t 0 J(τ, a) dτ = t 2 J(t, a) + (1 + a) a γ 2 .
As t ε = aε 1+aε and ε =

a γ+1 ε 2 , we infer that t ε ≈ ε 1 γ+1 . Hence, σ(x ε ) ≈ ε 1 γ+1 .
This completes the proof of the proposition 2.3. Next, to prove Proposition 2.1, we will only look at ∂ x2 σ close to the origin and to do that, we want to compute, firstly, ∂ t σ and ∂ a σ. Differentiating (3.4) with respect to t and a respectively, we get

(3.5) ∂ t σ(x) = l(a) f (x) - ∂ t J(t, a) J(t, a) σ(x), and
(3.6) ∂ a σ(x) = ∂ a l(a) l(a) σ(x) - ∂ a J(t, a) J(t, a) σ(x) + K 1 (t, a) + K 2 (t, a)
where, Now, we claim that, for any γ ≥ 1 2 ,

K 1 (t, a) := l(a) t 0 -β(ζ ′′ (-a + (1 + a)τ ) + η ′′ ((1 + a) τ a γ 2 )) ∂ a J(τ, a) dτ J(t, a
(3.7) ∂ a σ ≈ t + t t + a 2 .
From Section 2, we have

|η ′′′ (x 2 )| ≤ C x 2 γ -1 2
, for all x 2 ∈ (0, 1) (3.8) where C := C(γ). Then,

τ a γ-1 2 (γ(1 + a) + a) η ′′′ (1 + a) τ a γ 2 ≤ C τ 2 γ a.
As ζ ′′′ (0) > 0, we infer that K 2 (t, a) ≈ t.

In addition, it is easy to see that

∂ a l(a) l(a) σ(x) = 4 + a 2γ + γ(1 + a) a 2γ-1 (1 + a)(4 + a 2γ ) σ(x) ≈ t.
On the other hand,

K 1 (t, a) - ∂ a J(t, a) J(t, a) σ(x) = l(a) t 0 f (-a + (1 + a)τ, (1 + a) τ a γ 2 ) (J(t, a)∂ a J(τ, a) -J(τ, a)∂ a J(t, a)) dτ J(t, a) 2 .
Yet, by (3.3), we have

∂ a J(t, a) = γ (γ -1) (1 + a) 2 t + (γ (1 + a) (1 + 2t) + a) a a γ-2 2 .
Then, it is not difficult to check that

J(t, a) ∂ a J(τ, a) -J(τ, a) ∂ a J(t, a) = γ 4 (1 + a) 2 (t -τ )a 2γ-2 .
Using (3.3) again, we infer that

K 1 (t, a) - ∂ a J(t, a) J(t, a) σ(x) ≈ t t + a 2 .
This completes the proof of (3.7). Now, our aim is to prove that (3.9)

∂ t σ ≈ 1.
Fix δ > 0. As η ′′ (0) = 0, then, near the origin, we can assume that |f (x) -2β| < δ. From (3.5), we get

∂ t σ(x) ≥ l(a) 2β -δ - t 0 ∂ t J(t, a)J(τ, a)dτ J(t, a) 2 (2β + δ) . Yet, ∂ t J(t, a) = γ 2 (1 + a) 2 a γ-1
and then,

t 0 ∂ t J(t, a)J(τ, a)dτ J(t, a) 2 = 1 2 1 - a 2 (γ (1 + a) t + a) 2 . Hence, ∂ t σ(x) ≥ β - 3δ 2 > 0.
In the same way, we can prove that ∂ t σ is bounded from above and then, (3.9) follows. Yet,

∂ x2 σ := ∂ t σ ∂ x2 t + ∂ a σ ∂ x2 a and D (x1,x2) (t, a) :=   ∂ x1 t ∂ x2 t ∂ x1 a ∂ x2 a   = 1 J(t, a)   (γ (1 + a) + a) ta γ-1 2 1 -t -(1+a) a γ 2 1 + a   .
Hence, by (3.7) & (3.9), we get

∂ x2 σ ≈ 1 J and ||∂ x2 σ|| p L p (∆) ≈ ∆ 1 J(t, a) p dx 1 dx 2 ≈ δ 0 δ 0 1 J(t, a) p-1 dt da
where δ > 0 small enough. From (3.3), we get

||∂ x2 σ|| p L p (∆) ≈ δ 0 δ 0 1 a (γ-1)(p-1) (t + a) p-1 dt da ≈ δ 0 r dr π 2 0 1 r γ(p-1) sin(θ) (γ-1)(p-1) (cos(θ) + sin(θ)) (p-1) dθ ≈ δ 0 1 r γ(p-1)-1 dr π 2 0 1 sin(θ) (γ-1)(p-1) dθ.
Then, the proposition 2.1 is proved. As in [START_REF] Colombo | Obstructions to regularity in the classical Monge problem[END_REF][START_REF] Li | Regularity in Monge's mass transfer problem[END_REF], it is not difficult to prove the existence of a Kantorovich potential u to assert that the rays (l a ) a∈(0,1) are, in fact, all the transport rays between f + and f -. This follows immediately from the fact that the unit vector of any transport ray l a is an irrotational vector field, which implies that there is a 1-Lipschitz function u such that

(3.10) u(x) -u(y) = |x -y| ∀ x, y ∈ l a .
In addition, by [START_REF] Caffarelli | Constructing optimal maps for Monge's transport problem as a limit of strictly convex costs[END_REF][START_REF] Trudinger | On the Monge mass transfer problem[END_REF], one can show that there is a unique measure preserving map T from (f + , ∆) to (f -, ∆) such that x and T (x) lie in a common l a , for all x ∈ ∆. Now, it is classical to infer that T is an optimal transport map between f ± and u is the corresponding Kantorovich potential.

BV counter-example

In this section, we will prove the statement (1.4). This means that we want to construct two densities f ± ∈ BV (Ω) such that the transport density σ between them is not in BV (Ω). First of all, we can see easily that for any γ > 0, the densities f ± , which are constructed in Section 2, are in BV (Ω), but it will be also the same for the transport density σ between them. Indeed, to get a counter-example to the W 1,p regularity of the transport density, for p → 1, we need a γ → ∞. Hence, to get a BV counter-example, we could collect an infinity of triangles (constructed as in Section 2) with a sequence of exponents γ n → ∞ (where γ n is the exponent of the slopes of the transport rays in the n-th triangle, see 2.1). Actually, if we play on other parameters, we just need to take γ n = γ > 1. To do that, let us define ∆ n as follows :

∆ n := triangle with vertices (-l n , 0), 1, -

l γ n 2 (1 + l n ) and 1, l γ n 2 (1 + l n )
where l n := 1 n . Set, ∆ ′ 1 := ∆ 1 and, for all n ≥ 2, define ∆ ′ n as a suitable roto-translation of ∆ n :

∆ ′ n := {(x 1 , x 2 ) ∈ R 2 : (cos(θ n )(x 1 + l 1 ) + sin(θ n )x 2 -l n , -sin(θ n )(x 1 + l 1 ) + cos(θ n )x 2 ) ∈ ∆ n }, (-1, 0) Ω ∆ ′ 1 ∆ ′ 2 ∆ ′ n Figure 3.
where

θ n := n-1 k=1 α k + α k+1 and sin(α k ) := l γ k 2 1 + l γ k 2 2 , α k ∈ 0, π 2 .
Finally, set

Ω := ∞ n=1 ∆ ′ n .
Fix n ∈ N * . Then, after a suitable roto-translation of axis, we can assume that ∆ ′ n = ∆ n . Set,

f + (x 1 , x 2 ) := 1 and f -(x 1 , x 2 ) := f - n (x 1 , x 2 ) := 1 + β(ζ ′′ (x 1 ) + η ′′ (|x 2 |)), for all (x 1 , x 2 ) ∈ ∆ ′ n
where ζ and η are the same functions which are constructed in the section 2. Let us denote by σ the transport density between f + and f -. Then, the restriction of to ∆ ′ n is the transport density σ n between f + n := 1 ∆ ′ n and f - n . Indeed, for all n ∈ N * , if T n is an optimal transport map between f ± n and if u n is the corresponding Kantorovich potential such that u n (-1, 0) = 0, for all n ∈ N * , then it is not difficult to check that T (x) := T n (x), for a.e x ∈ ∆ ′ n is an optimal transport map between f ± and the corresponding Kantorovich potential will be u(x) := u n (x), for all x ∈ ∆ ′ n .

By (1.1), we infer that the restriction of σ to ∆ ′ n is σ n . Yet, by Section 3, we have already shown that

|∇σ n | ≈ 1 J n
where J n is defined as in (3.3) on ∆ n . Hence,

∞ n=1 ||∇σ n || L 1 (∆ ′ n ) ≈ ∞ n=1 ln 0 δ 0 |∇σ n (t, a)|J n (t, a) dt da ≈ ∞ n=1 l n = ∞ n=1 1 n = +∞
where δ > 0 small enough. Hence, the transport density σ / ∈ BV (Ω). On the other hand, we will show that the target mass f -is in BV (R 2 ). Using (3.8), it is easy to prove that

∞ n=1 ||∇f - n || L 1 (∆ ′ n ) ≤ C ∞ n=1 (l γ n + l 2 n ) < +∞.
In addition, for a fixed n ∈ N * and after a suitable roto-translation of axis so that ∆ ′ n = ∆ n , we can assume that

f - n (x 1 , x 2 ) = 1 + β(ζ ′′ (x 1 ) + η ′′ (|x 2 |)) and f - n+1 (x 1 , x 2 ) = 1 + β(ζ ′′ (cos(θ n+1 )(x 1 +l n ) + sin(θ n+1 )x 2 -l n+1 ) + η ′′ (|-sin(θ n+1 )(x 1 + l n )+ cos(θ n+1 )x 2 |))
where

θ n+1 := α n + α n+1 ≈ l γ n+1 .
Hence, it is not difficult to check that

f - n+1 x 1 , l γ n 2 (x 1 + l n ) -f - n x 1 , l γ n 2 (x 1 + l n ) ≤ C(l γ n + l 2 n ).
Finally, we get

∞ n=1 ∂∆n∩∂∆n+1 |f - n+1 (z) -f - n (z)|dz ≤ C ∞ n=1 (l γ n + l 2 n ) < +∞.
As f -is bounded and P er(Ω) ≈ n (l γ n + l 2 n ) < +∞, we infer that the target mass f -∈ BV (R 2 ) and the statement (1.4) follows.

Counter-examples with compactly supported smooth densities on the whole plane

In this section, we want to show that is also possible to construct the target measure f -so that it will be regular on R 2 . Firstly, let us observe that the function ζ (see Section 2) can be replaced by ψζ, where ψ is a C ∞ function such that ψ = 1 on [-1, 1 -ε ′ ] and ψ = 0 on [1 -ε, 1], (0 < ε < ε ′ < 1). Let χ 1 , χ 2 be two cutoff functions supported on ∆ ∪ R(∆), where R is the reflection map with respect to the x 1 -axis, such that spt(χ 2 ) ⊂ {χ 1 = 1}, ∆ a0 ∩ {x : x 1 ≤ 1 -ε} ⊂ {χ 1 = 1} (where a 0 ∈ (ε, 1) is such that spt(χ 2 ) ⊂ ∆ a0 ∪ R(∆ a0 )), ∆ ε ∩ {x : x 1 ≤ 1 -ε} ⊂ {χ 2 = 1} and χ 1 , χ 2 are symmetric with respect to the x 1 -axis. Set, , for all a ∈ (0, 1).

By (2.4), we have Hence, for γ > 2, f -∈ W 1, γ γ-2 -ε (R 2 ), for all ε > 0.

Similarly, we get that for γ = 1 2 : f -∈ C ∞ (R 2 ), for γ = 1: f -∈ C 2,1 (R 2 ), for 1 < γ < 2:

f -∈ C 1, 2
γ -1 (R 2 ) and, finally, for γ = 2: f -∈ C 0,1 (R 2 ).

) and K 2

 2 (t, a) := l(a) t 0 -β(-(1 -τ )ζ ′′′ (-a + (1 + a)τ ) + τ a γ-1 2 (γ(1 + a) + a) η ′′′ ((1 + a) τ a γ 2 )) J(τ, a) dτ J(t, a) .

f + := χ 1 1 - 1 -

 111 andf -:= χ 1 + β(((ψζ) ′′ (x 1 ) + η ′′ (|x 2 |))χ 2 + ϕ(x 1 )c(a(x 1 , |x 2 |))),where ϕ is a non-negative C ∞ function such that spt(ϕ) ⊂ (1 -ε ′ , 1 -ε) and c is to be determined in such a way that∆a f + = ∆a f -for all a ∈ (0, 1),which is equivalent to say that-∆a ((ψζ) ′′ (x 1 ) + η ′′ (x 2 ))χ 2 (x 1 , x 2 ) = ∆a ϕ(x 1 )c(a(x 1 , x 2 )), for all a ∈ (0, 1).Differentiating this equality with respect to a, we get c(a) = a (γ(x 1 + a) + a)((ψζ) ′′ (x 1 ) + η ′′ ( a γ 2 (x 1 + a)))χ 2 (x 1 , a γ 2 (x 1 + a)) dx 1 a (γ(x 1 + a) + a)ϕ(x 1 ) dx 1

1 - 1 - 1 - 1 (η ′′ a γ 2 (x 1 + a) 1 -χ 2 x 1 2 (x 1 +a) 1 -χ 2 x 1 1 ) 0 1 a 1 -

 11112111211101 x 1 + a) + a)(ψζ) ′′ (x 1 ) dx 1 = 1 -a (γ(x 1 + a) + a)η ′′ a γ 2 (x 1 + a) dx 1, for all a ∈ (0, 1).Hence, for a < ε, we getc(a) = a (γ(x 1 + a) + a)η ′′ ( a γ 2 (x 1 + a))(1 -χ 2 (x 1 , a γ 2 (x 1 + a))) dx 1 a (γ(x 1 + a) + a)ϕ(x 1 ) dx 1 and c ′ (a) = 1 a (γ(x 1 + a) + a)ϕ(x 1 ) dx x 1 +a)+a) 2 η ′′′ a γ x 1 + a) + a) 2 η ′′ a γ 2 (x 1 + a) ∂ x2 χ 2 x 1 , a γ 2 (x 1 + a)dx 1 . By (3.8), we infer that c ′ (a) ≤ Ca and ||∇(ϕ c(a))|| p L p (∆) ≈ p |c ′ (a)| p J(t, a) p + |∇ϕ(x 1 )| p |c(a)| p dx 2 dx 1 ≈ ε (γ-(γ-2)p) da.

Acknowledgments: the author would like to thank Prof. Filippo Santambrogio for interesting discussions and suggestions. The author also acknowledges the support of the ANR project ANR-12-BS01-0014-01 GEOMETRYA.


Martial Marbouty

Romain Koszul
email: romain.koszul@pasteur.fr

Metagenome analysis exploiting high throughput chromosome conformation capture (3C) data

Keywords: Metagenome assembly, meta3C metaHi-C, Hi-C, 3C, Metagenomics, contact genomics

Microbial communities are extremely complex and constitute critical actors of our environment. Genomic analyses of these populations are a dynamic research area but remain limited by the difficulty to assemble full genomes of individual species. Recently, a new method for metagenome assembly/analysis based on chromosome conformation capture has emerged (meta3C). This approach quantifies the collisions experienced by DNA molecules to identify those sharing the same cellular compartments, allowing the characterization of genomes present within complex mixes of species. The exploitation of these chromosome 3D signatures holds important premises regarding reaching at the genome sequences from discrete species in complex populations. It also has the potential to correctly assign extra-chromosomal elements, such as plasmids, mobile elements and phages, to their host cells.

Limitations of metagenomic analysis

Microbial communities and their biochemical activities are ubiquitous and essential components of environmental and natural ecosystems. They often play important roles in the maintenance of environmental ecosystems as well as in sustaining animal and plant life [START_REF] Cryan | Mind-altering microorganisms: the impact of the gut microbiota on brain and behaviour[END_REF][START_REF] Hanski | Environmental biodiversity, human microbiota, and allergy are interrelated[END_REF][START_REF] Kau | Human nutrition, the gut microbiome and the immune system[END_REF]. Microbes that associate with a macroscopic host organism can also interact with it and exert a major influence on its metabolism with consequences on health, growth and fitness [START_REF] Joice | Determining microbial products and identifying molecular targets in the human microbiome[END_REF][START_REF] Manor | Mapping the inner workings of the microbiome: genomic-and metagenomic-based study of metabolism and metabolic interactions in the human microbiome[END_REF]. However, and despite their established importance, these mixes of microorganisms have often proven difficult to characterize to the full extent of their complexity, which often encompasses hundreds or more species engaged in co-dependant relationships. Notably, the vast majority (90-99%; reviewed in [START_REF] Sharpton | An introduction to the analysis of shotgun metagenomic data[END_REF]) of microbes cannot be cultivated and therefore isolated, impairing more refined characterization of these species. This bottleneck can be bypassed, to some extent, by studying directly DNA extracted from the microbial community. Metagenomics (see Glossary) aims at studying microbial ecosystems globally through the characterization of the genes that are present in the community as a whole. Pioneering metagenomics projects have focused on the ubiquitous 16S RNA gene to explore the diversity and nature of the species present within populations. They brought to light the tremendous diversity of microbes, unveiling a largely unexplored and unknown world, and paving the way to this flourishing field [7][START_REF] Franzosa | Sequencing and beyond: integrating molecular "omics" for microbial community profiling[END_REF][START_REF] Rappé | Phylogenetic diversity of marine coastal picoplankton 16S rRNA genes cloned from the continental shelf off Cape Hatteras, North Carolina[END_REF]. Thanks to important breakthrough in sequencing technologies and computational analysis, numerous studies based on shotgun sequencing of metagenomes have then allowed exploring the DNA molecules present in a microbial community [START_REF] Hasan | Microbial Community Profiling of Human Saliva Using Shotgun Metagenomic Sequencing[END_REF][11][START_REF] Venter | Environmental Genome Shotgun Sequencing of the Sargasso Sea[END_REF]. However, those analysis are somehow limited as it remains difficult to assemble these short DNA sequences into larger molecules (i.e. contigs and scaffolds; see Glossary; [START_REF] Simpson | The Theory and Practice of Genome Sequence Assembly[END_REF]), if not full genomes, hindering in-depth analysis of the system as a whole. Improving the ability to discriminate, characterize and assign DNA sequences to a specific species, so that eventually its complete genome can be characterize, is challenging for complex communities. Furthermore, a complete picture of the genetic content of a microbial community goes much beyond the sum of the genomes/chromosome(s) of the microorganisms that compose it. Indeed the population also contains numerous DNA molecules, either independent from the core genome or exhibiting dynamic behaviours (plasmids, transposon, viruses/prophages) that add extra and important layers of complexity to the system. The analysis of the individual chromosomes contained within a metagenomic sample has improved thanks to continuous advances in sequencing technologies: single-molecule, real-time (SMRT) sequencing [START_REF] Eid | Real-time DNA sequencing from single polymerase molecules[END_REF] as marketed by Pacific Biosciences [START_REF] Fichot | Microbial phylogenetic profiling with the Pacific Biosciences sequencing platform[END_REF] or Nanopore [16] are promising approaches likely to become prominent in the field in the future. Alternatively or in complement, single-cell technologies offer interesting perspectives as they preserve the cellular integrity [START_REF] Rinke | Insights into the phylogeny and coding potential of microbial dark matter[END_REF], though they remain prone to important biases, contamination and overall relatively out of reach of many laboratories. Computational methods can also overcome to some extent some of those limitations.

De novo assembly programs such as MetaVelvet [START_REF] Zerbino | Velvet: Algorithms for de novo short read assembly using de Bruijn graphs[END_REF] and IDBA-UD [START_REF] Peng | IDBA-UD: a de novo assembler for single-cell and metagenomic sequencing data with highly uneven depth[END_REF] have been adapted to metagenomic data [START_REF] Afiahayati | MetaVelvet-SL: an extension of the Velvet assembler to a de novo metagenomic assembler utilizing supervised learning[END_REF]. Finally, assembly of short reads into discrete genomes have also been improved by exploiting biases in base composition [START_REF] Saeed | Unsupervised discovery of microbial population structure within metagenomes using nucleotide base composition[END_REF], by leveraging variations in gene abundance [START_REF] Carr | Reconstructing the Genomic Content of Microbiome Taxa through Shotgun Metagenomic Deconvolution[END_REF][START_REF] Hug | Community genomic analyses constrain the distribution of metabolic traits across the Chloroflexi phylum and indicate roles in sediment carbon cycling[END_REF] between the genomes of different species, or by combining multiple parameters and searching for correlations for instance between variations in reads coverage and cultivation into different growth media [24]. However, the assumption that contigs/reads with similar characteristics are likely to originate from the same genome is contradicted by horizontal gene transfer events that generate genetic heterogeneity. Also, if multiple strains of a species coexist within the mix it is difficult or impossible to identify their different haplotypes. Alternative approaches to bypass these limitations are therefore actively sought.

Exploiting contact genomic to analyse metagenomes

A recent and potential breakthrough came from the realization that chromosome 3D physical signatures can be exploited to infer 1) the linear sequence of a chromosome and 2) whether different chromosomes occupies different cellular compartments or not [START_REF] Flot | Contact genomics: Scaffolding and phasing (meta)genomes using chromosome 3D physical signatures[END_REF]. This new field, dubbed 'contact genomics' [START_REF] Flot | Contact genomics: Scaffolding and phasing (meta)genomes using chromosome 3D physical signatures[END_REF], aims at exploiting the physical contacts experienced by small DNA molecules and quantified through genomic derivatives of the chromosome conformation capture technique (3C; see Glossary and Box 1; [START_REF] Dekker | Capturing Chromosome Conformation[END_REF][START_REF] Dekker | Exploring the three-dimensional organization of genomes: interpreting chromatin interaction data[END_REF]). 3C relies primarily on a fixation step, typically achieved using formaldehyde cross-linking, to freeze and capture contacts made by DNA regions within (cis) and between (trans) chromosomes. The cross-linked DNA is then digested by a restriction enzyme, diluted, religated, and pair-end sequenced (Figure 1A and Box 1). Chimeric molecules resulting from religation events between non-adjacent DNA regions are identified from the pair-end reads by mapping them along chromosomes to generate a genome-wide matrix of contact frequencies.

Performed on a population of cells, these contact maps presumably reflect the average genome organization. An immediate observation made from genomic 3C data is that contact frequencies between DNA regions decrease as a function of the distance separating them following, to some extent, a power law distribution [START_REF] Lieberman-Aiden | Comprehensive Mapping of Long-Range Interactions Reveals Folding Principles of the Human Genome[END_REF]. Given a frequency of contacts, one should therefore be able to get a robust assessment of the distance that separates two loci. This makes it possible to exploit the broad distribution of statistically significant cis-contact, ranging from a few kb to up to a Mb, to bridge the numerous assembly gaps present in most published genomes (reviewed in [START_REF] Flot | Contact genomics: Scaffolding and phasing (meta)genomes using chromosome 3D physical signatures[END_REF]). Several approaches have recently tackled this challenge and developed programs aiming at improving genome assembly through the use of large 3C contact datasets [START_REF] Burton | Chromosome-scale scaffolding of de novo genome assemblies based on chromatin interactions[END_REF][START_REF] Kaplan | High-throughput genome scaffolding from in-vivo DNA interaction frequency[END_REF][31]. These promising approaches, though perfectible, have allowed the scaffolding of contigs (see Glossary) up to several hundreds of Mb from incomplete assembly of genomes of various sizes (for instance of human contigs obtained de novo, [START_REF] Kaplan | High-throughput genome scaffolding from in-vivo DNA interaction frequency[END_REF]31]).

Beyond the great promises held by contact genomics approaches to chromosome scaffolding/genome assembly, this concept has now started to be applied to the field of metagenomics. By analogy with the physical contacts allowing discriminating multiple chromosomes within a single nuclear/cell compartment of a homogeneous population, metagenomic 3C (meta3C or metaHi-C) considers the entire population as a large ensemble of cellular compartments with specific chromosomal sets, and exploits their contact frequencies to discriminate DNA molecules occupying different compartments [32-34] (Figure 1). As, physical contacts provide quantitative and objective information regarding whether or not two pieces of DNA share the same cellular compartment, without requiring any prior knowledge of the content of the sample.

To test the validity of this approach, a first important unknown was to characterize the "background noise" frequency with which two DNA RFs originating from 2 different genomes end up fused together after a meta3C experiment. To do so, pair-end reads obtained from meta3C experiments performed on mixes of species with known genomes were aligned against those sequences, and inter-species ligation events were quantified. Religation events between RFs coming from different genomes proved extremely low for both prokaryotic and eukaryotic mixes (< 1%; [32-34] (Figure 2A-B). One must notice that experimental conditions, notably fixation, have an important impact on the end results, with low amounts of crosslinking agent leading to noisier signal, especially in bacteria [START_REF] Burton | Species-level deconvolution of metagenome assemblies with Hi-C-based contact probability maps[END_REF][START_REF] Marbouty | Metagenomic chromosome conformation capture (meta3C) unveils the diversity of chromosome organization in microorganisms[END_REF]. Overall, these control experiments confirmed that DNA/DNA contacts are a convenient and sound measurement of the co-existence of two DNA regions within the same compartment, if not the same genome (below).

In the case of environmental/natural samples, prior knowledge regarding the species present in the mix remains generally sparse and incomplete. Obtaining the genomes of the species present within the sample remains important challenge that is rarely met except for dominant members of the community [35]. To apply meta3C to such natural sample, the first step consists in assembling the metagenome from the sequencing reads in order to reduce the complexity of the data, which typically generates a large number of small contigs of various depths coverage. The paired-end reads containing the 3D contact information (Hi-C or 3C-seq, see Glossary) are then mapped on this set of contigs, producing a large meta3C network in with the nodes representing the contigs and the edges the contacts. This network is typically complex, and exhibits a community structure with subgraphs groups of densely connected nodes and sparse connections to the rest of the network. The challenges associated with complex network analysis are familiar to many scientific fields such as sociology (e.g. friendship/collaborations network) [START_REF] Weng | Virality Prediction and Community Structure in Social Networks[END_REF]37] and neurobiology [38], and important efforts have been made to develop efficient clustering algorithms in recent years [START_REF] Blondel | Fast unfolding of communities in large networks[END_REF][START_REF] Campigotto | A Generalized and Adaptive Method for Community Detection[END_REF][START_REF] Van Dongen | Using MCL to extract clusters from networks[END_REF][START_REF] Lancichinetti | Community detection algorithms: a comparative analysis[END_REF][43].

To test this approach, several group performed blind analyses of meta3C networks obtained from various controlled mixes (from 3 to 12 species) [32][START_REF] Burton | Species-level deconvolution of metagenome assemblies with Hi-C-based contact probability maps[END_REF][START_REF] Marbouty | Metagenomic chromosome conformation capture (meta3C) unveils the diversity of chromosome organization in microorganisms[END_REF]. Metagenome assembly was performed using either SOAP de novo [32] or IDBA-UD [START_REF] Burton | Species-level deconvolution of metagenome assemblies with Hi-C-based contact probability maps[END_REF][START_REF] Marbouty | Metagenomic chromosome conformation capture (meta3C) unveils the diversity of chromosome organization in microorganisms[END_REF] (Table 1), either from an independent library [32,[START_REF] Burton | Species-level deconvolution of metagenome assemblies with Hi-C-based contact probability maps[END_REF] or directly from the meta3C reads [START_REF] Marbouty | Metagenomic chromosome conformation capture (meta3C) unveils the diversity of chromosome organization in microorganisms[END_REF]. The later solution is advantageous when only a limited amount of biological material is available, especially if the meta3C data was generated using 3C-seq rather than Hi-C. Indeed, in the 3C-seq protocol the 3C library is directly sequenced, without any enrichment step for chimeric ligation products as in Hi-C [START_REF] Lieberman-Aiden | Comprehensive Mapping of Long-Range Interactions Reveals Folding Principles of the Human Genome[END_REF]. Consequently, the sequenced library is composed of 80-90% regular paired-end reads that are mainly used during the assembly step, whereas the 10-20% chimeric read pairs corresponding to religation events do not result in a significant increase of assembly errors [START_REF] Marbouty | Metagenomic chromosome conformation capture (meta3C) unveils the diversity of chromosome organization in microorganisms[END_REF]. The interaction network between the de novo generated contigs is then achieved taking advantage of the 10-20% chimeric read pairs that correspond to religation events. Different clustering algorithms can be used to identify communities of contigs within the global network of interactions generated using the meta3C PE reads (see Table 1). In the studies reviewed here, 80% to 98% of the entire genome sequences present in the controlled mixes were appropriately pooled together after processing. Interestingly, the clustering also delineated nonchromosomal DNA sequences such as plasmids. Notably, the distribution of contacts made by a F' plasmid sequence confirmed its presence in the vicinity of the E. coli chromosome, whereas a correlation analysis of the these contacts signal further revealed that it carried a large segmental duplication of this genome [START_REF] Marbouty | Metagenomic chromosome conformation capture (meta3C) unveils the diversity of chromosome organization in microorganisms[END_REF]. The clustering also pooled together chromosomes that shared the same cellular compartment, and identified multiple chromosomes within a single species.

Current limitations of meta3C approaches

Although promising, existing meta3C approaches remain perfectible. First, the presence of closely related species and/or of strains of the same species in the mix may impair the proper clustering of the corresponding sequences [32,[START_REF] Burton | Species-level deconvolution of metagenome assemblies with Hi-C-based contact probability maps[END_REF]. Notably, errors occurring during assembly step (resulting for instance from repeated sequences) can lead to chimeric contigs and misleading contact signal. Cutting the contigs into pieces of DNA of similar sizes can alleviate this problem [START_REF] Marbouty | Metagenomic chromosome conformation capture (meta3C) unveils the diversity of chromosome organization in microorganisms[END_REF], but further computational developments will be needed to fully exploit the information contained within meta3C libraries. In addition, and as mentioned above, metagenomes are more than a mix of genomic sequences. Homologous sequences, repeats, plasmids, mobile elements or horizontal gene transfer events are present, resulting in DNA sequences interacting with different host genomes at the same time. Those elements will bend the network by being equally connected to multiple communities as evidenced by an experiment performed on an completely unknown metagenome stemming from a LB-enriched sediment sample [START_REF] Marbouty | Metagenomic chromosome conformation capture (meta3C) unveils the diversity of chromosome organization in microorganisms[END_REF] (Figure 2C-D). Detection of overlapping communities is a complex problem in the field [44][START_REF] Palla | Uncovering the overlapping community structure of complex networks in nature and society[END_REF][START_REF] Wang | Fuzzy overlapping community detection based on local random walk and multidimensional scaling[END_REF], that will require further developments to be fully addressed in the case of meta3C data. Finally, another limitation is inherent to the 3C technology and results from the enzymatic restriction step (Box 1). The frequency of restriction sites is highly correlated with the GC content of the sequence, which can introduce important biases [START_REF] Cournac | Normalization of a chromosomal contact map[END_REF][START_REF] Yaffe | Probabilistic modeling of Hi-C contact maps eliminates systematic biases to characterize global chromosomal architecture[END_REF]. Such bias will notable affect meta3C experiments when members of a metagenomic sample exhibit large differences in GC content. One possibility to alleviate this problem is to build meta3C libraries with different restriction enzymes, so that all genomes are visible in at least one condition.

Alternatively, other restriction approaches, such as partial DNAse digestion [START_REF] Ma | Fine-scale chromatin interaction maps reveal the cis-regulatory landscape of human lincRNA genes[END_REF], could be envisioned.

Future directions

3C/Hi-C based approaches appear as promising tools to study the genomes of microbial communities since they give access not only to the chromosomes of the species present within the mix but also provide information regarding mobile elements such as plasmids and phages that share the same compartment [32][START_REF] Burton | Species-level deconvolution of metagenome assemblies with Hi-C-based contact probability maps[END_REF][START_REF] Marbouty | Metagenomic chromosome conformation capture (meta3C) unveils the diversity of chromosome organization in microorganisms[END_REF]. Such data are promising to the study of bacterial genomes dynamics and plasticity within population and over time. Microbial communities are not only composed of numerous different species of bacteria but also of a tremendous amount of phages, sometimes considered to be the most abundant "replicating" organisms on earth [50] and important vectors of DNA fragments [START_REF] Muniesa | Potential impact of environmental bacteriophages in spreading antibiotic resistance genes[END_REF][START_REF] Stern | CRISPR targeting reveals a reservoir of common phages associated with the human gut microbiome[END_REF]. Although their influence on the balance of bacterial communities is gradually being unveiled, not much is known about it because of the difficulty to access their sequences [START_REF] Ogilvie | Genome signature-based dissection of human gut metagenomes to extract subliminal viral sequences[END_REF][START_REF] Thurber | Laboratory procedures to generate viral metagenomes[END_REF]. Consequently, our understanding of their roles in the size, structures and function of microbial communities is only starting. Finding out their bacterial hosts and their precise role in the plasticity of bacterial genomes will be necessary to fully understand phages and their integration in microbial communities. By analysing contact between phages and bacterial genomes, Meta3C appears as a promising method to answer to these important questions.

Although it is tempting to envision reassembling de novo the individual genomes identify within these complex communities using programs such as GRAAL [31,[START_REF] Marbouty | Metagenomic chromosome conformation capture (meta3C) unveils the diversity of chromosome organization in microorganisms[END_REF], this remains challenging with such complex samples. However, the stakes of this computational challenge are high, considering the importance of these data to understand and characterize the physiology of noncultivable organisms and the population equilibrium. Developments in both assembly programs and sequencing technologies will therefore likely allow full metagenome reconstruction in the near future.

Interestingly, the meta3C approach also gives access to the genome organization of the microorganisms directly captured in their environment. An emerging picture in the field is that the high-order chromosome organization in these species reflects, to some extent, metabolic regulation and/or cell cycle progression. In Bacillus subtilis for instance, cycles of condensation/decompaction of the origin of replication correlate with replication regulation [START_REF] Marbouty | Condensin-and Replication-Mediated Bacterial Chromosome Folding and Origin Condensation Revealed by Hi-C and Super-resolution Imaging[END_REF]. In Saccharomyces cerevisiae, long-term survival following diauxic shift and entry into quiescence necessitate the settling of a "hyper-cluster" of telomeres [START_REF] Guidi | Spatial reorganization of telomeres in long-lived quiescent cells[END_REF]. Therefore, knowing the genome organization of the microorganisms within the mix will provide access to their metabolic state, paving the way for an integrated analysis of the dynamic physiology of the population.

Concluding remarks

Metagenomic analyses provide important insights on the dynamics of natural microbial communities and their response or interplay with the environment. Approaches based on contact genomics, such as meta3C, have the potential to alleviate some of the limitations of traditional metagenomic approaches. DNA is an ubiquitous and stable molecule, and using it as a marker of "compartmentalization" at cellular and population levels hold great promises. Indeed, the objective and quantitative information provided by the collisions of DNA molecule sheds light not only on the chromosomal content of various cell compartments but also on the extra-genomic sequences present within the population. This paves the way for an exhaustive description of complex communities and gene dynamics taking into account the entire pool of DNA molecules present within a community, which appears within reach using meta3C (see Outstanding Questions). Taken together, contact genomic investigations using meta3C represent a great opportunity to address the current challenges metagenomics, such as deciphering how environmental changes influence the genome organization, dynamics and plasticity of the organisms present in a given ecological niche, and how they adapt in response.

Figures & tables

Table1: Summary of published processes and data using 3C-based metagenome assembly.

Figure1: Principle of a meta3C experiment.

(A) Starting from a mix of species (metagenomicssample), a shotgun library is generated and used to generate a preliminary assembly (a 3C library can also be used here).

(B) Starting from the same sample, a 3C/HiC library is generated (see Box1).

(C) Pair-end reads from the 3C library, some of which reflect the collision frequencies between all the pairs of DNA restriction fragments present within the population, is then mapped on the contigs.

(D) Representation of the complex network resulting from the step C). Left panel: contact map representation of the contigs. Right panel: 3D representation of the data using a clustering visualization tool such as Gephi [START_REF] Bastian | Gephi: An Open Source Software for Exploring and Manipulating Networks[END_REF].

(E) The disordered contigs are then clustered and reordered based on their frequencies of interactions, unveiling the genomic sequences of the organisms present within the mix.

Genomic DNA extraction

Figure 2 :

 2 Figure 2 : meta3C experiment on different mix of species [34].

  Figure 2

Acknowledgement

The authors thank Axel Cournac, Lyam Baudry and Jean-François Flot for comments on this manuscript and discussions about this work. This research was supported by funding to R.K. from the European Research Council under the 7th Framework Program (FP7/2007-2013) / ERC grant agreement 260822. M.M. is the recipient of an Association pour la Recherche sur le Cancer fellowship (number 20100600373).

Box 1. 3C approaches unveil the multiscale organization of genomes

Chromosomes from prokaryotes and eukaryotes are long filaments that are tightly folded within a relatively confined space. Although the volume occupied by the DNA fibre is only a fraction of the total nucleus or nucleoid volume, its folding is of primary importance since it determines its accessibility and the cell's ability to mobilise the information carried by the DNA in a timely manner.

Hence, complex mechanisms have evolved that drive and regulate this organization by folding the 1D genome into a 3D structure. The principles, role and dynamics of this folding have been investigated since the birth of cytology, with remarkable advances obtained from microscopy studies. However, an important step was recently reached by combining high-throughput sequencing with the chromosome conformation capture (3C) technique [START_REF] Dekker | Capturing Chromosome Conformation[END_REF], giving access to the multiscale 3D organization of the DNA sequence. 3C and its genomic derivatives [START_REF] Dekker | Exploring the three-dimensional organization of genomes: interpreting chromatin interaction data[END_REF] have in recent years become popular tools to study spatial chromosome organization. In a 3C assays, a population of cells or a single cell is fixed using a crosslinking agent such as formaldehyde. This results in covalent bounds between histone proteins, which trap together DNA regions occurring in the vicinity of each other's.

The cross-linked DNA is digested with a restriction enzyme then religated under dilute conditions (to favour intramolecular ligation over intermolecular ones). After DNA purification, the resulting 3C library consists in a collection of restriction fragments (RFs) ligated together, resulting in molecules that are chimeric with respect to the reference genome. The relative abundance of the pairs of RFs involved in a chimeric religation event reflects the frequency with which these two chromatin segments were crosslinked, hence their spatial proximity. The relative proportions of these chimeric product were initially quantified using semi-quantitative PCR [START_REF] Dekker | Capturing Chromosome Conformation[END_REF] but 3C assays have recently boomed, mainly thanks to the advent of high-throughput sequencing techniques [57] allowing sequencing the extremities of the DNA molecules present in the 3C library and estimating in a quantitative way contact frequencies of pairs of RFs within genomes. Genome-wide contact maps are built from this quantification step. 3C-based assays have provided important advances in our understanding of the genomic architecture of mammals [START_REF] Lieberman-Aiden | Comprehensive Mapping of Long-Range Interactions Reveals Folding Principles of the Human Genome[END_REF]58] or bacteria [START_REF] Le | High-resolution mapping of the spatial organization of a bacterial chromosome[END_REF]. In all species, chromosomes appear as well individualized entities sometimes presenting large topological domains (TADs -Topological Associated Domains). Their precise roles and regulatory mechanisms are the subject of intensive investigations, with increasing evidence that the 3D architecture of chromosomes is an essential part of the cellular process and cell physiology. The next decade promises to be really exciting in this research field as improvements in sequencing technology and data treatment will certainly uncover the relationships between genome architectures and cellular processes. Contig: a consensus DNA sequence inferred from a set of overlapping DNA fragments. In a contig the order of the base pairs is known with a high confidence, without gaps.

Glossary

Hi-C: next-generation sequencing of a 3C library that was enriched in chimeric read pairs using biotinylation.

Metagenomics: scientific field that aims at studying genetic material directly obtained from environmental samples. It could also be referred as ecogenomics or environmental genomics.

NGS (next-generation sequencing): generic term applying to a group of sequencing technologies

developed at the turn of the century (Solexa [START_REF] Bennett | Solexa Ltd[END_REF], 454 [START_REF] Margulies | Genome sequencing in microfabricated high-density picolitre reactors[END_REF], Ion Torrent [START_REF] Rothberg | An integrated semiconductor device enabling non-optical genome sequencing[END_REF]) that allow affordable, massive and fast sequencing of DNA. Typically, NGS generate tens of millions of short sequences (or read), and is commonly applied to genomics and sequencing projects. Also called high-throughput sequencing.

Scaffold: a DNA sequence made out of multiple contigs with intervening gaps (the length of which is generally not precisely known).

Table1