Zhenzhang Ye

Bjoern Haefner

Yvain Quéau

Thomas Möllenhoff

Daniel Cremers

Sublabel-Accurate Multilabeling Meets Product Label Spaces

Keywords: Variational Methods, Manifold-Valued Problems, Convex Relaxation, Global Optimization

Functional lifting methods are a promising approach to determine optimal or near-optimal solutions to difficult nonconvex variational problems. Yet, they come with increased memory demands, limiting their practicability. To overcome this drawback, this paper presents a combination of two approaches designed to make liftings more scalable, namely product-space relaxations and sublabel-accurate discretizations. Our main contribution is a simple way to solve the resulting semi-infinite optimization problem with a sampling strategy. We show that despite its simplicity, our approach significantly outperforms baseline methods, in the sense that it finds solutions with lower energies given the same amount of memory. We demonstrate our empirical findings on the nonconvex optical flow and manifold-valued denoising problems.

Introduction

Many tasks in imaging and low-level computer vision can be transparently modeled as a variational problem. In practice, the resulting energy functionals are often nonconvex, for example due to data terms based on image-matching costs or manifold-valued constraints. The goal of this work is to develop a convex optimization approach to total variation-regularized problems of the form

inf u:Ω→Γ Ω c(x, u 1 (x), . . . , u k (x)) dx + k i=1 λ i TV(u i ). (1)
Here, Γ = {(γ 1 , . . . , γ k ) ∈ R N : γ i ∈ Γ i , i = 1 . . . k} is based on compact, embedded manifolds Γ i ⊂ R Ni with N = N 1 + . . . + N k . Throughout this paper we only consider imaging applications and pick Ω ⊂ R 2 to be a rectangular image domain. The cost function c : Ω × Γ → R ≥0 in (1) can be a general nonconvex function. Notably, we only assume that we can evaluate the cost function c(x, u(x)) but no gradient information or projection operators are available. This allows us to consider degenerate costs that are out of reach for gradient-based approaches.

As a regularization term in [START_REF] Bach | Submodular functions: from discrete to continuous domains[END_REF] we consider a simple separable total variation regularization TV(u i ) on the individual components u i : Ω → R Ni weighted by a tunable hyper-parameter λ i > 0. The total variation (TV) encourages a spatially smooth but edge-preserving solution. It is defined as

TV(u i ) := sup p:Ω→R N i ×2 p(x) * ≤1 Ω Div x p(x), u i (x) dx = Ω ∇u i (x) dx, (2)
where the last equality holds for sufficiently smooth u i . We denote by ∇u i (x) ∈ R Ni×2 the Jacobian matrix in the Euclidean sense and by • * the dual norm. Since our focus is on the data cost c, we consider only this separable TV case. Problems of the form (1) find applications in low-level vision and signal processing. An example is the optical flow estimation between two RGB images I 1 , I 2 : Ω → R 3 , where Γ 1 = Γ 2 = [a, b] ⊂ R are intervals and the cost function is given by c(x, u 1 (x), u 2 (x)) = |I 1 (x+(u 1 (x), u 2 (x)))-I 2 (x)|. In many applications, Γ i is a curved manifold, see [START_REF] Lellmann | Total variation regularization for functions with values in a manifold[END_REF][START_REF] Weinmann | Total variation regularization for manifoldvalued data[END_REF]. Examples include Γ i = S 2 in the case of normal field processing [START_REF] Lellmann | Total variation regularization for functions with values in a manifold[END_REF], SO [START_REF] Bauermeister | Lifting the convex conjugate in lagrangian relaxations: A tractable approach for continuous Markov random fields[END_REF] in the case of motion estimation [START_REF] Görlitz | Piecewise rigid scene flow with implicit motion segmentation[END_REF] or the circle S 1 for processing of cyclic data [START_REF] Cremers | Total cyclic variation and generalizations[END_REF][START_REF] Steinke | Nonparametric regression between general Riemannian manifolds[END_REF].

As one often wishes to estimate multiple quantities in a joint fashion, one naturally arrives at the product space formulation as considered in [START_REF] Bach | Submodular functions: from discrete to continuous domains[END_REF]. A popular approach to address such joint optimization problems are expectation maximization procedures [START_REF] Dempster | Maximum likelihood from incomplete data via the EM algorithm[END_REF] or block-coordinate descent and alternating direction-type methods [START_REF] Boyd | Distributed optimization and statistical learning via the alternating direction method of multipliers[END_REF], where one estimates a single quantity while holding the other ones fixed. Sometimes, such approaches depend on a good initialization and can be prone to getting stuck in bad local minima. Our goal is to devise a convex relaxation of Problem (1) that can be directly solved to global optimality with standard proximal methods (possibly implemented on GPUs) such as the primal dual algorithm [START_REF] Pock | Diagonal preconditioning for first order primal-dual algorithms in convex optimization[END_REF]. To achieve this, we offer the following contributions:

• To tackle relaxations of (1) in a memory-efficient manner, we propose a sublabel-accurate implementation of the product-space lifting [START_REF] Goldluecke | Tight convex relaxations for vectorvalued labeling[END_REF]. This implementation is enabled by building on ideas from [START_REF] Möllenhoff | Sublabel-accurate discretization of nonconvex freediscontinuity problems[END_REF], which views sublabelaccurate multilabeling as a finite-element discretization. • Our main contribution presented in Sec. 4 is a simple way to implement the resulting optimization problem with a sampling strategy. Unlike previous liftings [START_REF] Möllenhoff | Sublabel-accurate relaxation of nonconvex energies[END_REF][START_REF] Möllenhoff | Sublabel-accurate discretization of nonconvex freediscontinuity problems[END_REF][START_REF] Vogt | Lifting methods for manifoldvalued variational problems[END_REF], our approach does not require epigraphical projections and can therefore be applied in a black-box fashion to any cost c(x, u(x)). • We show that our sublabel-accurate implementation attains a lower energy than the product-space lifting [START_REF] Goldluecke | Tight convex relaxations for vectorvalued labeling[END_REF] on optical flow estimation and manifoldvalued denoising problems.

The following Section 2 is aimed to provide an introduction to relaxation methods for (1) while also reviewing existing works and our contributions relative to them. We present the relaxation for (1) and its discretization in Section 3. In Section 4, we show how to implement the discretized relaxation with the proposed sampling strategy. Section 5 presents numerical results on optical flow and manifold-valued denoising and our conclusions are drawn in Section 6.

Related work: convex relaxation methods

Let us first consider a simplified version of problem [START_REF] Bach | Submodular functions: from discrete to continuous domains[END_REF] where Ω consists only of a single point, i.e., the nonconvex minimization of one data term:

min γ∈Γ c(γ 1 , . . . , γ k ). (3)
A well-known approach to the global optimization of ( 3) is a lifting or stochastic relaxation procedure, which has been considered in diverse fields such as polynomial optimization [START_REF] Lasserre | Global optimization with polynomials and the problem of moments[END_REF], continuous Markov random fields [START_REF] Fix | Duality and the continuous graphical model[END_REF][START_REF] Peng | Convex max-product algorithms for continuous MRFs with applications to protein folding[END_REF][START_REF] Bauermeister | Lifting the convex conjugate in lagrangian relaxations: A tractable approach for continuous Markov random fields[END_REF], variational methods [START_REF] Pock | A convex formulation of continuous multi-label problems[END_REF], and black-box optimization [START_REF] De Boer | A tutorial on the crossentropy method[END_REF][START_REF] Ollivier | Information-geometric optimization algorithms: A unifying picture via invariance principles[END_REF][START_REF] Schaul | Studies in Continuous Black-box Optimization[END_REF]. The idea is to relax the search space in (3) from γ ∈ Γ to probability distributions4 u ∈ P(Γ ) and solve

min u∈P(Γ ) Γ c(γ 1 , . . . , γ k ) du(γ 1 , . . . , γ k ). (4)
Due to linearity of the integral wrt. u and convexity of the relaxed search space, this is a convex problem for any c. Moreover, the minimizers of (4) concentrate at the optima of c and can hence be identified with solutions to (3). If Γ is a continuum, this problem is infinite-dimensional and therefore challenging.

Discrete/traditional multilabeling. In the context of Markov random fields [START_REF] Ishikawa | Exact optimization for Markov random fields with convex priors[END_REF][START_REF] Kappes | A comparative study of modern inference techniques for discrete energy minimization problems[END_REF] and multilabel optimization [START_REF] Chambolle | A convex approach to minimal partitions[END_REF][START_REF] Lellmann | Convex multi-class image labeling by simplex-constrained total variation[END_REF][START_REF] Lellmann | Continuous multiclass labeling approaches and algorithms[END_REF][START_REF] Zach | Fast global labeling for realtime stereo using multiple plane sweeps[END_REF] one typically discretizes Γ into a finite set of points (called the labels) Γ = {v 1 , . . . , v }. This turns (4) into a finitedimensional linear program min u∈∆ c , u where c ∈ R denotes the label cost and ∆ ⊂ R is the ( -1)-dimensional unit simplex.. If we evaluate the cost at the labels, this program upper bounds the continuous problem (3), since instead of all possible solutions, one considers a restricted subset determined by the labels.

Since the solution will be attained at one of the labels, typically a fine meshing is needed. Similar to black-box and zero-order optimization methods, this strategy suffers from the curse of dimensionality. When each Γ i is discretized into labels, the overall number is k which quickly becomes intractable since many labels are required for a smooth solution. Additionally, for pairwise or regularizing terms, often a large number of dual constraints has to be implemented. In that context, the work [START_REF] Lellmann | Discrete and continuous models for partitioning problems[END_REF] considers a constraint pruning strategy as an offline-preprocessing.

Sublabel-accurate multilabeling. The discrete-continuous MRF [START_REF] Fix | Duality and the continuous graphical model[END_REF][START_REF] Zach | Dual decomposition for joint discrete-continuous optimization[END_REF][START_REF] Zach | A convex discrete-continuous approach for Markov random fields[END_REF] and lifting methods [START_REF] Laude | Sublabel-accurate convex relaxation of vectorial multilabel energies[END_REF][START_REF] Möllenhoff | Sublabel-accurate relaxation of nonconvex energies[END_REF][START_REF] Möllenhoff | Sublabel-accurate discretization of nonconvex freediscontinuity problems[END_REF] attempt to find a more label-efficient convex formulation. These approaches can be understood through duality [START_REF] Fix | Duality and the continuous graphical model[END_REF][START_REF] Möllenhoff | Sublabel-accurate discretization of nonconvex freediscontinuity problems[END_REF]. Applied to (3), the idea is to replace the cost c : Γ → R with a dual variable q : Γ → R:

min u∈P(Γ ) sup q:Γ →R Γ q(γ 1 , . . . , γ k ) du(γ 1 , . . . , γ k ), s.t. q(γ) ≤ c(γ) ∀γ ∈ Γ. ( 5
)
The inner supremum in the formulation (5) maximizes the lower-bound q and if the dual variable is sufficiently expressive, this problem is equivalent to (4). Approximating q, for example with piecewise linear functions on Γ , one arrives at a lower-bound to the nonconvex problem (3). It has been observed in a recent series of works [START_REF] Laude | Sublabel-accurate convex relaxation of vectorial multilabel energies[END_REF][START_REF] Möllenhoff | Sublabel-accurate relaxation of nonconvex energies[END_REF][START_REF] Möllenhoff | Sublabel-accurate discretization of nonconvex freediscontinuity problems[END_REF][START_REF] Vogt | Lifting methods for manifoldvalued variational problems[END_REF][START_REF] Zach | A convex discrete-continuous approach for Markov random fields[END_REF] that piecewise linear dual variables can lead to smooth solutions even when q (and therefore also u) is defined on a rather coarse mesh. As remarked in [START_REF] Fix | Duality and the continuous graphical model[END_REF][START_REF] Laude | Sublabel-accurate convex relaxation of vectorial multilabel energies[END_REF][START_REF] Möllenhoff | Sublabel-accurate relaxation of nonconvex energies[END_REF], for an affine dual variable this strategy corresponds to minimizing the convex envelope of the cost, min γ∈Γ c * * (γ), where c * * denotes the Fenchel biconjugate of c.

The implementation of the constraints in ( 5) can be challenging even in the case of piecewise-linear q. This is partly due to the fact that the problem ( 5) is a semi-infinite optimization problem [START_REF] Blankenship | Infinitely constrained optimization problems[END_REF], i.e., an optimization problem with infinitely many constraints. The works [START_REF] Möllenhoff | Sublabel-accurate relaxation of nonconvex energies[END_REF][START_REF] Zach | A convex discrete-continuous approach for Markov random fields[END_REF] implement the constraints via projections onto the epigraph of the (restricted) conjugate function of the cost within a proximal optimization framework. Such projections are only available in closed form for some choices of c and expensive to compute if the dimension is larger than one [START_REF] Laude | Sublabel-accurate convex relaxation of vectorial multilabel energies[END_REF]. This limits the applicability in a "plug-and-play" fashion.

Product-space liftings. The product-space lifting approach [START_REF] Goldluecke | Tight convex relaxations for vectorvalued labeling[END_REF] attempts to overcome the aforementioned exponential memory requirements of labeling methods in an orthogonal way to the sublabel-based methods. The main idea is to exploit the product-space structure in (1) and optimize over k marginal distributions of the probability measure u ∈ P(Γ ), which we denote by u i ∈ P(Γ i ). Applying [START_REF] Goldluecke | Tight convex relaxations for vectorvalued labeling[END_REF] to the single data term (3) one arrives at the following relaxation:

min {ui∈P(Γi)} sup {qi:Γi→R} k i=1 Γi q i (γ) du i (γ) s.t. k i=1 q i (γ) ≤ c(γ) ∀γ ∈ Γ. (6)
Since one only has to discretize the individual Γ i this substantially reduces the memory requirements from O( N ) to O( k i=1

Ni ). While at first glance it seems that the curse of dimensionality is lifted, the difficulties are moved to the dual, where we still have a large (or even infinite) number of constraints. A global implementation of the constraints with Lagrange multipliers as proposed in [START_REF] Goldluecke | Tight convex relaxations for vectorvalued labeling[END_REF] again leads to the same exponential dependancy on the dimension.

As a side note, readers familiar with optimal transport may notice that the supremum in ( 6) is a multi-marginal transportation problem [START_REF] Carlier | On a class of multidimensional optimal transportation problems[END_REF][START_REF] Villani | Optimal Transport: Old and New[END_REF] with transportation cost c. This view is mentioned in [START_REF] Bach | Submodular functions: from discrete to continuous domains[END_REF] where relaxations of form [START_REF] Boyd | Distributed optimization and statistical learning via the alternating direction method of multipliers[END_REF] are analyzed under submodularity assumptions.

In summary, the sublabel-accurate lifting methods, discrete-continuous MRFs [START_REF] Zach | A convex discrete-continuous approach for Markov random fields[END_REF][START_REF] Möllenhoff | Sublabel-accurate relaxation of nonconvex energies[END_REF] and product-space liftings [START_REF] Goldluecke | Tight convex relaxations for vectorvalued labeling[END_REF] all share a common difficulty: implementation of an exponential or even infinite number of constraints on the dual variables. Summary of contribution. Our main contribution is a simple way to implement the dual constraints in an online fashion with a random sampling strategy which we present in Section 4. This allows a black-box implementation, which only requires an evaluation of the cost c and no epigraphical projection operations as in [START_REF] Möllenhoff | Sublabel-accurate relaxation of nonconvex energies[END_REF][START_REF] Zach | A convex discrete-continuous approach for Markov random fields[END_REF]. Moreover, the sampling approach allows us to propose and implement a sublabel-accurate variant of the product-space relaxation [START_REF] Goldluecke | Tight convex relaxations for vectorvalued labeling[END_REF] which we describe in the following section.

Product-space relaxation

Our starting point is the convex relaxation of (1) presented in [START_REF] Goldluecke | Tight convex relaxations for vectorvalued labeling[END_REF][START_REF] Strekalovskiy | Convex relaxation of vectorial problems with coupled regularization[END_REF]. In these works, Γ i ⊂ R is chosen to be an interval. Following [START_REF] Vogt | Lifting methods for manifoldvalued variational problems[END_REF] we consider a generalization to manifolds Γ i ⊂ R Ni which leads us to the following relaxation:

min {ui:Ω→P(Γi)} sup {qi:Ω×Γi→R} {pi:Ω×Γi→R 2 } k i=1 Ω Γi q i (x, γ i ) -Div x p i (x, γ i ) du x i (γ) dx, (7)
s.t.

P Tγ i ∇ γi p i (x, γ i ) * ≤ λ i , for all 1 ≤ i ≤ k, (x, γ i ) ∈ Ω × Γ i , (8)
k i=1 q i (x, γ i ) ≤ c(x, γ), for all (x, γ) ∈ Ω × Γ. (9)
This cost function appears similar to (6) explained in the previous section, but with two differences. First, we now have marginal distributions u i (x) for every x ∈ Ω since we do not consider only a single data term anymore. The notation du x i in [START_REF] Caillaud | Error estimates for finite differences approximations of the total variation[END_REF] denotes the integration against the probability measure u i (x) ∈ P(Γ i ). The variables q i play the same role as in [START_REF] Boyd | Distributed optimization and statistical learning via the alternating direction method of multipliers[END_REF] and lower-bound the cost under constraint [START_REF] Chambolle | A convex approach to minimal partitions[END_REF]. The second difference is the introduction of additional dual variables p i and the term -Div x p i in [START_REF] Caillaud | Error estimates for finite differences approximations of the total variation[END_REF]. Together with the constraint [START_REF] Carlier | On a class of multidimensional optimal transportation problems[END_REF], this can be shown to implement the total variation regularization [START_REF] Lellmann | Total variation regularization for functions with values in a manifold[END_REF][START_REF] Vogt | Lifting methods for manifoldvalued variational problems[END_REF]. Following [START_REF] Vogt | Lifting methods for manifoldvalued variational problems[END_REF], the derivative ∇ γi p i (x, γ i ) in (8) denotes the (N i × 2)-dimensional Jacobian considered in the Euclidean sense and P Tγ i the projection onto the tangent space of Γ i at the point γ i . Next, we describe a finite-element discretization of (7).

Finite-element discretization

We approximate the infinite-dimensional problem [START_REF] Caillaud | Error estimates for finite differences approximations of the total variation[END_REF] by restricting u i , p i and q i to be piecewise functions on a discrete meshing of Ω × Γ i . The considered discretization is a standard finite-element approach and largely follows [START_REF] Vogt | Lifting methods for manifoldvalued variational problems[END_REF]. Unlike the forward-differences considered in [START_REF] Vogt | Lifting methods for manifoldvalued variational problems[END_REF] we use lowest-order Raviart-Thomas elements (see, e.g., [START_REF] Caillaud | Error estimates for finite differences approximations of the total variation[END_REF]Section 5]) in Ω, which are specifically tailored towards the considered total variation regularization.

Discrete mesh. We approximate each d i -dimensional manifold Γ i ⊂ R Ni with a simplicial manifold Γ h i , given by the union of a collection of d i -dimensional simplices T i . We denote the number of vertices ("labels") in the triangulation of Γ i as i . The set of labels is denoted by Data term and the u i , q i variables. We assume the cost c : Ω × Γ → R ≥0 is constant in x ∈ Ω on each face and denote its value as c(x(f ), γ) for f ∈ F, where x(f ) ∈ Ω denotes the midpoint of the face f . Similarly, we also assume the variables u i and q i to be constant in x ∈ Ω on each face but continuous piecewise linear functions in γ i . They are represented by coefficient functions

L i = {v i,1 , . . . , v i, i }. As assumed, Ω ⊂ R 2 is
u h i , q h i ∈ R F • i , i.e.
, we specify the values on the labels and linearly interpolate inbetween. This is done by the interpolation operator W i,f,γi : R F • i → R which given an index 1 ≤ i ≤ k, face f , and (continuous) label position γ i ∈ Γ i computes the function value: W i,f,γi u h i = u i (x(f ), γ i ). Note that after discretization, u i is only defined on Γ h i but we can uniquely associate to each γ i ∈ Γ h i a point on Γ i .

Divergence and p i variables. Our variable p i is represented by coefficients p h i ∈ R E• i which live on the edges in Ω and the labels in Γ i . The vector p i (x, γ i ) ∈ R 2 is obtained by linearly interpolating the coefficients on the vertical and horizontal edges of the face and using the interpolated coefficients to evaluate the piecewise-linear function on Γ h i . Under this approximation, the discrete divergence Div h x : R

E• i → R F • i is given by (Div h x p h i )(f ) = p h i (e r ) + p h i (e t ) -p h i (e l ) -p h i (e b ) /
i,f,α,t : R E• i → R di×2 .
Here, f ∈ F and α ∈ [0, 1] 2 correspond to a point x ∈ Ω while t ∈ T i is the simplex containing the point corresponding to γ i ∈ Γ i . First, the operator computes coefficients in R i of two piecewise-linear functions on the manifold by linearly interpolating the values on the edges based on the face index f ∈ F and α ∈ [0, 1] 2 . For each function, the derivative in simplex t ∈ T i on the triangulated manifold is given by the gradient of an affine extension. Projecting the resulting vector into the d i -dimensional tangent space for both functions leads to a d i × 2-matrix which approximates P Tγ i ∇ γi p i (x, γ i ).

Final discretized problem. Plugging our discretized u i , q i , p i into [START_REF] Caillaud | Error estimates for finite differences approximations of the total variation[END_REF], we arrive at the following finite-dimensional optimization problem:

min {u h i ∈R F • i } max {p h i ∈R E• i }, {q h i ∈R F • i } h 2 x • k i=1 u h i , q h i -Div h x p h i + f ∈F i{u h i (f ) ∈ ∆ i }, (10) s
.t. D i,f,α,t p h i * ≤ λ i , ∀1 ≤ i ≤ k, f ∈ F, α ∈ {0, 1} 2 , t ∈ T i , (11)
k i=1 W i,f,γi q h i ≤ c (x(f ), γ) , ∀f ∈ F, γ ∈ Γ, (12)
where i{•} is the indicator function. In our applications, we found it sufficient to enforce the constraint [START_REF] Cremers | Total cyclic variation and generalizations[END_REF] at the corners of each face which corresponds to choosing α ∈ {0, 1} 2 . Apart from the infinitely many constraints in [START_REF] Dempster | Maximum likelihood from incomplete data via the EM algorithm[END_REF], this is a finite-dimensional convex-concave saddle-point problem.

Solution recovery

Before presenting in the next section our proposed way to implement the constraints (12), we briefly discuss how a primal solution {u h i } of the above problem is turned into an approximate solution to [START_REF] Bach | Submodular functions: from discrete to continuous domains[END_REF]. To that end, we follow [START_REF] Lellmann | Total variation regularization for functions with values in a manifold[END_REF][START_REF] Vogt | Lifting methods for manifoldvalued variational problems[END_REF] and compute the Riemannian center of mass via an iteration τ = 1, . . . , T :

V τ j = log u τ i (v i,j ), v τ = i j=1 u h i (f, j)V τ j , u τ +1 i = exp u τ i (v τ ). (13)
Here, u 0 i ∈ Γ i is initialized by the label with the highest probability according to u h i (f, •). log u τ i and exp u τ i denote the logarithmic and exponential mapping between Γ h i and it's tangent space at u τ i ∈ Γ i , which are both available in closedform for the manifolds we consider here. In our case T = 20 was enough to reach convergence. For flat manifolds, T = 1 is enough, as both mappings boil down to the identity and ( 13) computes a weighted Euclidean mean.

In general, there is no theory which shows that u T (x) = (u T 1 (x), . . . , u T k (x)) from ( 13) is a global minimizer of (1). Tightness of the relaxation in the special case k = 1 and Γ ⊂ R is shown in [START_REF] Pock | Global solutions of variational models with convex regularization[END_REF]. For higher dimensional Γ , the tightness of related relaxations is ongoing research; see [START_REF] Ghoussoub | Hidden convexity in a problem of nonlinear elasticity[END_REF] for results on the Dirichlet energy. By computing a-posteriori optimality gaps, solutions of ( 7) were shown to be typically near the global optimum of the problem (1); see, e.g., [START_REF] Goldluecke | Tight convex relaxations for vectorvalued labeling[END_REF].

Implementation of the constraints

Though the optimization variables in [START_REF] Chambolle | A first-order primal-dual algorithm for convex problems with applications to imaging[END_REF] are finite-dimensional, the energy is still difficult to optimize because of the infinite constraints in [START_REF] Dempster | Maximum likelihood from incomplete data via the EM algorithm[END_REF].

Before we present our approach, let us first describe what we refer to as the baseline method in the rest of this paper. For the baseline approach, we consider the direct solution of [START_REF] Chambolle | A first-order primal-dual algorithm for convex problems with applications to imaging[END_REF] where we implemented the constraints only at the label/discretization points L 1 × . . . × L k via Lagrange multipliers. This strategy is also employed by the (global variant) of the product-space approach [START_REF] Goldluecke | Tight convex relaxations for vectorvalued labeling[END_REF].

We aim for a framework that allows for solving a better approximation of (12) than the above baseline while being of similar memory complexity. To achieve this, our algorithm alternates the following two steps in an iterative way.

1) Sampling. Based on the current solution we prune previously considered but feasible constraints and sample a new subset of the infinite constraints in [START_REF] Dempster | Maximum likelihood from incomplete data via the EM algorithm[END_REF]. From all current sampled constraints, we consider the most violated constraints for each face, add one sample at the current solution and discard the rest.

2) Solving the subsampled problem. Considering the current finite subset of constraints, we solve problem (10) using a primal-dual algorithm.

These two phases are performed alternatingly, with the aim to eventually approach the solution of the continuous problem [START_REF] Chambolle | A first-order primal-dual algorithm for convex problems with applications to imaging[END_REF]. The details of our constraint sampling strategy are shown in Alg. 1. For each face in F, the algorithm generates a finite set of "sublabels" S f ⊂ Γ at which we implement the constraints [START_REF] Dempster | Maximum likelihood from incomplete data via the EM algorithm[END_REF]. In the following, we provide the motivation behind each line in the algorithm.

Algorithm 1: Sampling strategy at face f ∈ F.

Inputs : Solution u = (u1, . . . , u k ) at face f , sublabel-set S f , n, δ, r 1 S f ← uniformSample(Γ , n) /* global exploration */ 2 S f ← S f ∪ localPerturb(u, δ, n) /* local exploration around sol. */ 3 S f ← γ ∈ S f : k i=1 qi(f, γ) > c(f, γ) /* remove feas. cons. */ 4 S f ← top-k(S f , r) ∪ S f
/* add the most violated r samples */ 5 S f ← S f ∪ {u}.

/* have one sample at cur. sol. */ 6 return S f Algorithm 2: Proposed algorithm for problem [START_REF] Bach | Submodular functions: from discrete to continuous domains[END_REF].

Inputs : c : Ω × Γ → R, λi > 0, Nit > 0, Mit > 0, n > 0, δ > 0, r > 0 1 u h,0 i = 1/ i, q h,0 i = 0, p h,0 i = 0, S 0 f = L1 × . . . × L k . 2 for it = 0 to Nit do 3 Obtain u h,it+1 i , q h,it+1 i , p h,it+1
i by running Mit iterations of the primal-dual method [START_REF] Pock | Diagonal preconditioning for first order primal-dual algorithms in convex optimization[END_REF] on [START_REF] Chambolle | A first-order primal-dual algorithm for convex problems with applications to imaging[END_REF], with constraints ( 12) implemented at S it f for each f ∈ F via Lagrange multipliers; warmstart at u h,it i , q h,it i , p h,it i .

4

Compute current approximate solution u it+1 to (1) via [START_REF] Fix | Duality and the continuous graphical model[END_REF].

5 Get S it+1 f by calling Alg. 1 with (u it+1 (f ), S it f , n, δ, r) for each f ∈ F. 6 end
Random uniform sampling (Line 1). To have a global view of the cost function, we consider a uniform sampling on the label space Γ . The parameter n > 0 determines the number of the samples for each face.

Local perturbation around the mean (Line 2). Besides the global information, we apply local perturbation around the current solution u. In case the current solution is close to the optimal one, this strategy allows us to refine it with these samples. The parameter δ > 0 determines the size of the local neighbourhood. In experiments, we always used a Gaussian perturbation with δ = 0.1.

Pruning strategy (Lines 3-4). Most samples from previous iterations are discarded because the corresponding constraints are already satisfied. We prune all current feasible constraints as in [START_REF] Blankenship | Infinitely constrained optimization problems[END_REF]. Similarly, the two random sampling strategies (Lines 1 and 2) might return some samples for which the constraints are already fulfilled. Therefore, we only consider the samples with violated constraints and pick the r most violated from them. This pruning strategy is essential for a memory efficient implementation as shown later.

Sampling at u (Line 5). Finally, we add one sample which is exactly at the current solution u ∈ Γ to have at least one guaranteed sample per face. Overall algorithm. After implementing the constraints at the finite set determined by Alg. 1, we apply a primal-dual method [START_REF] Chambolle | A first-order primal-dual algorithm for convex problems with applications to imaging[END_REF] with diagonal preconditioning [START_REF] Pock | Diagonal preconditioning for first order primal-dual algorithms in convex optimization[END_REF] to solve [START_REF] Chambolle | A first-order primal-dual algorithm for convex problems with applications to imaging[END_REF]. Both constraints [START_REF] Cremers | Total cyclic variation and generalizations[END_REF] and ( 12) are implemented using Lagrange multipliers. Based on the obtained solution, a new set of samples is determined. This scheme is alternated for a fixed number of outer iterations N it and we have summarized the overall algorithm in Alg. 2. While we do not prove convergence of the overall algorithm, convergence results for related procedures exist; see, e.g., [START_REF] Blankenship | Infinitely constrained optimization problems[END_REF]Theorem 2.4].

Finally, let us note that a single outer iteration of Alg. 2 with large number of M it corresponds to the baseline method.

Numerical validation

Our approach and the baseline are implemented in PyTorch. Code for reproducing the following experiments can be found here: https://github.com/zhenzhangye/ sublabel_meets_product_space. Note that a specialized implementation as in [START_REF] Goldluecke | Tight convex relaxations for vectorvalued labeling[END_REF] will allow the method to scale by factor 10 -100×.

Illustration of our sampling idea

To illustrate the effect of the sampling strategies, we consider the minimization of a single nonconvex data term. The cost c and the corresponding dual variable q are plotted in Fig. 1. As shown in (a), the primal-dual method can obtain the optimal q h for the sampled subproblem only. Our sampling strategy can provide necessary samples and prune the feasible ones as, cp. (b). These few but necessary samples lead the q h to achieve global optimality, cp. (c). If one more iteration is performed, the sampling at u it can stabilize the optimal q.

Ablation study

Next, we study the effect of each line in Alg. 1. We evaluate our method on the truncated quadratic energy c(x, u(x)) = min{(u(x)-f (x)) 2 , ν}. where f : Ω → R is the input data. For this specific experiment, the parameters are chosen as ν = 0.025, = 0.25, N it = 10, M it = 200, n = 10 and r = 1. To reduce the effect of randomness, we run each algorithm 20 times and report mean and standard deviation of the final energy for different number of labels in Table 1.

Adding uniform sampling and picking the most violated constraint per face already decreases the final energy significantly, i.e. Line 1 and Line 4 of Alg. 1. We also consider local exploration around the current solution, cf. Line 2, which helps to find better energies at the expense of higher memory requirements.

To circumvent that, we introduce our pruning strategy in Line 3 of Alg. 1. However, the energy deteriorates dramatically because some faces could end up having no samples after pruning. Therefore, keeping the current solution as a sample (Line 5) per face prevents the energy from degrading.

Including all the sampling strategies, the proposed method can achieve the best energy and run-time, at comparable memory usage to the baseline method.

We further illustrate the comparison on the number of iterations and time between the baseline and our proposed method in Fig. 2. Due to the replacement on the samples, we have a peak right after each sampling phase. The energy however converges immediately, leading to an overall decreasing trend.

Optical flow

Given two input images I 1 , I 2 , we compute the optical flow u : Ω → R 2 . The label space Γ = [a, b] 2 in our case is chosen as a = -2.5 and b = 7.5. We use a simple 2 -norm for the data term, i.e. c(x, u(x)) = ||I 2 (x) -I 1 (x + u(x))|| and set the regularization weight as λ = 0.04. The baseline approach runs for 50K iterations, while we set N it = 50 and M it = 1000 for a fair comparison. Additionally, we choose n = 20 and r = 1 in Alg. 1.

The results are shown in Fig. 3. Our method outperforms the baseline approach regarding energy under the same number of labels and requires the same amount of memory. We can achieve lower energy with about half number of labels. Comparison between the baseline and our approach on a 64×64 image, degraded with Gaussian and salt-and-papper noise. Our approach finds lower energies in fewer iterations and time, which implements the constraints only at the label points.

Denoising in HSV color space

In our final application, we evaluate on a manifold-valued denoising problem in HSV color space. The hue component of this space is a circle, i.e., Γ 1 = S 1 , Γ 2 , Γ 3 = [0, 1]. The data term of this experiment is a truncated quadratic distance, where for the hue component the distance is taken on the circle S 1 . Both the baseline and our method are implemented with 7 labels. 30K iterations are performed on the baseline and N it = 100 outer iterations for our method with 300 inner primal-dual steps are used to get an equal number of total iterations. Other parameters are chosen as λ = 0.015, n = 30 and r = 5. As shown in Fig. 4, our method can achieve a lower energy than the baseline. Qualitatively, since our method implements the constraints not only at the labels but also inbetween, there is less bias compared to the baseline.

Conclusion

In this paper we made functional lifting methods more scalable by combining two advances, namely product-space relaxations [START_REF] Goldluecke | Tight convex relaxations for vectorvalued labeling[END_REF] and sublabel-accurate discretizations [START_REF] Möllenhoff | Sublabel-accurate discretization of nonconvex freediscontinuity problems[END_REF][START_REF] Vogt | Lifting methods for manifoldvalued variational problems[END_REF]. This combination is enabled by adapting a cutting-plane method from semi-infinite programming [START_REF] Blankenship | Infinitely constrained optimization problems[END_REF]. This allows an implementation of sublabel-accurate methods without difficult epigraphical projections. Moreover, our approach makes sublabel-accurate functional-lifting methods applicable to any cost function in a simple black-box fashion. In experiments, we demonstrate the effectiveness of the approach over a baseline based on the productspace relaxation [START_REF] Goldluecke | Tight convex relaxations for vectorvalued labeling[END_REF] and provided a proof-of-concept experiment showcasing the method in the manifold-valued setting. Fig. 4. Denoising of an image in HSV color space (Γ1 = S 1 ) using our method and the baseline. Since our approach implements the constraints adaptively inbetween the labels it reaches a lower energy with less label bias.

  a rectangle which we split into a set of faces F of edge-length h x with edge set E. The number of faces and edges are denoted by F = |F|, E = |E|.

Fig. 1 .

 1 Fig.1. Illustration of sampling strategies. (a) Two samples (red dots) are considered leading to the shown optimal dual variable q after running primal-dual iterations. (b) The two samples are pruned because the constraints are feasible. Several random samples are proposed (gray dots) and only one of them is picked (red dot). (c) One more sample on u it is added and the q is refined.

  Fig.2. Comparison between the baseline and our approach on a 64×64 image, degraded with Gaussian and salt-and-papper noise. Our approach finds lower energies in fewer iterations and time, which implements the constraints only at the label points.

Fig. 3 .

 3 Fig.3. We compute the optical flow on Grove3[START_REF] Baker | A database and evaluation methodology for optical flow[END_REF] using our method and our baseline for a varying amount of labels. Given an equal number of labels/memory, our sampling strategy performs favorably to an implementation of the constraints at the labels.InputBaseline Ours

  h x where e r , e t , e l , e b are the right, top, left and bottom edges of f , respectively. Total variation constraint. Computing the operator P Tγ i ∇ γi is largely inspired by [36, Section 2.2]. It is implemented by a linear map D

Table 1 .

 1 Ablation study indicating the effect of individual lines in Alg. 1. Numbers in parentheses indicate the standard deviation across 20 runs.

		Labels Baseline	+Line 1&4	+Line 2	+Line 3	+Line 5
	Energy		4589 (±0.00) 2305 (±3.73) 2291 (±3.6) 8585 (±130.4) 2051 (±10.7)
	Time [s]	3	8.98	22.77	23.22	23.22	23.33
	Mem. [Mb]		11.21	13.94	15.53	11.65	12.05
	Energy		2582 (±0.00) 2020 (±2.68) 2012 (±1.3) 7209 (±116.7) 1969 (±3.6)
	Time [s]	7	74.13	16.02	16.61	15.56	18.38
	Mem. [Mb]		28.35	32.96	33.49	28.356	28.68
	Energy		2029 (±0.00) 1935 (±1.14) 1926 (±0.7) 5976 (±75.7) 1901 (±3.7)
	Time [s]	13	183.80	37.65	38.84	38.29	38.22
	Mem. [Mb]		52.85	60.55	60.94	54.35	54.73

P(Γ ) is the set of nonnegative Radon measures on Γ with total mass u(Γ ) = 1.


Gabriel Clavijo

Manuella Van Munster

Baptiste Monsion

Nicole Bochet

Véronique Brault
email: veronique.brault@colmar.inra.fr

Ve ´ronique Brault

Transcription of densovirus endogenous sequences in the Myzus persicae genome

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

INTRODUCTION

Insects are the most diverse and largest animal group, causing economically significant losses in a wide range of crops, either as direct pests or as disease vectors [START_REF] Chilana | Insect genomic resources: status, availability and future[END_REF]. Studying insect biology and virus transmission by insects is therefore critical to identify control targets to minimize their impact. Advances in sequencing technology have dramatically increased the amount of information available on insect genomes, creating new opportunities for development of research programmes focused on insect biology. Deep-sequence analysis of insect genomes has revealed that they may contain integrated viral sequences that are not of retroviral origin [START_REF] Katzourakis | Endogenous viral elements in animal genomes[END_REF]Liu et al., 2011b;[START_REF] The ´ze | Paleozoic origin of insect large dsDNA viruses[END_REF]. These ancestral endogenous sequences share similarity with viruses in different families: ssDNA viruses (family Parvoviridae), dsDNA viruses (families Baculoviridae, Polydnaviridae and Nudiviridae), reverse-transcribed DNA viruses (family Hepadnaviridae), ssRNA positive-sense (family Flaviviridae) or negative-sense (families Rhabdoviridae and Orthomyxoviridae) viruses, and dsRNA viruses (family Reoviridae) [START_REF] Be ´zier | Polydnaviruses of braconid wasps derive from an ancestral nudivirus[END_REF][START_REF] Cheng | Brown planthopper nudivirus DNA integrated in its host genome[END_REF][START_REF] Katzourakis | Endogenous viral elements in animal genomes[END_REF]Liu et al., 2011c;[START_REF] The ´ze | Paleozoic origin of insect large dsDNA viruses[END_REF]. Integration of such a great diversity of viral sequences suggests that many different replication strategies can induce integration of these sequences into host genomes. Typically, viral sequences are found scattered throughout insect genomes, and in most cases, no complete virus genome has been found. However, in some cases, integrated viral ORFs are uninterrupted and can therefore potentially be expressed in host cells [START_REF] Be ´zier | Polydnaviruses of braconid wasps derive from an ancestral nudivirus[END_REF][START_REF] Katzourakis | Endogenous viral elements in animal genomes[END_REF]Liu et al., 2011b). In plants, insects and vertebrates, integration of viral sequences is predicted to confer selective advantages to the host by generating antiviral immunity against related viruses [START_REF] Belyi | Unexpected inheritance: multiple integrations of ancient Bornavirus and Ebolavirus/ Marburgvirus sequences in vertebrate genomes[END_REF][START_REF] Bertsch | Retention of the virus-derived sequences in the nuclear genome of grapevine as a potential pathway to virus resistance[END_REF][START_REF] Flegel | Hypothesis for heritable, anti-viral immunity in crustaceans and insects[END_REF][START_REF] Goic | RNAmediated interference and reverse transcription control the persistence of RNA viruses in the insect model Drosophila[END_REF][START_REF] Maori | Reciprocal sequence exchange between non-retro viruses and hosts leading to the appearance of new host phenotypes[END_REF].

Viral sequences from viruses in the subfamily Densovirinae (family Parvoviridae) have been shown to be integrated into the genome of Drosophila, Rhodnius prolixus and the pea aphid (Acyrthosiphon pisum) (Liu et al., 2011b). Densoviruses (DNVs) are small, non-enveloped ssDNA 3These authors contributed equally to this study. viruses encapsidated in icosahedral particles of about 25 nm diameter. Their genomes are 4-6 kb and encode only a few proteins referred to as either non-structural (NS) or capsid (CP, also referred to as VP) proteins [START_REF] Bergoin | Densoviruses: a highly diverse group of arthropod Parvoviruses[END_REF]. NS proteins are implicated in virus replication and in the activation of the promoter driving the synthesis of CP proteins [START_REF] Legendre | Terminal regions of the NS-1 protein of the parvovirus minute virus of mice are involved in cytotoxicity and promoter trans inhibition[END_REF][START_REF] Rhode | Characterization of the transactivation-responsive element of the parvovirus H-1 P38 promoter[END_REF], while CP proteins are involved in virion formation [START_REF] Croizier | Protein requirements for assembly of virus-like particles of Junonia coenia densovirus in insect cells[END_REF]. Genome organization varies among the different genera in the subfamily, with the two sets of genes being in tandem on the same DNA strand in the genera Iteravirus, Brevidensovirus, Hepandensovirus and Penstyldensovirus and on complementary strands in the genus Ambidensovirus. DNVs are found in a wide range of insect families and can cause acute diseases that are often fatal for their insect host [START_REF] Barreau | Pathogenicity of the Aedes albopictus parvovirus (AaPV), a denso-like virus, for Aedes aegypti mosquitoes[END_REF][START_REF] Mutuel | Pathogenesis of Junonia coenia densovirus in Spodoptera frugiperda: a route of infection that leads to hypoxia[END_REF][START_REF] Suto | Characterization of a virus newly isolated from the smoky-brown cockroach, Periplaneta fuliginosa (Serville)[END_REF][START_REF] Szelei | Susceptibility of North-American and European crickets to Acheta domesticus densovirus (AdDNV) and associated epizootics[END_REF]. As DNVs are not known to infect mammals [START_REF] Dupont | Risk assessment of the use of autonomous parvovirus-based vectors[END_REF][START_REF] El-Far | Lack of infection of vertebrate cells by the densovirus from the maize worm Mythimna loreyi (MlDNV)[END_REF], biopesticides derived from engineered or natural DNVs have been developed to reduce lepidopteran, mosquito and cockroach populations [START_REF] Buchatskii | Development and basic properties of the viral preparation viroden[END_REF][START_REF] Carlson | Densoviruses for control and genetic manipulation of mosquitoes[END_REF][START_REF] Hu | Pathogenicity island: a novel pesticide enhanced by insect hormone for controlling cockroaches[END_REF][START_REF] Jiang | Genetic engineering of Periplaneta fuliginosa densovirus as an improved biopesticide[END_REF][START_REF] Monsarrat | Densovirus en lutte biologique[END_REF][START_REF] Tal | Insecticidal potential of insect parvovirus GmDNV[END_REF]. However, some DNVs may only induce sublethal infection and may even confer a beneficial effect on their host (i) by increasing the production of the winged morph and therefore promoting insect dispersal, or (ii) by protecting against pathogenic baculovirus infection [START_REF] Ryabov | Densovirus induces winged morphs in asexual clones of the rosy apple aphid, Dysaphis plantaginea[END_REF]van Munster et al., 2003a;[START_REF] Xu | Densovirus is a mutualistic symbiont of a global crop pest (Helicoverpa armigera) and protects against a baculovirus and Bt biopesticide[END_REF].

We utilized the recent release of the genome sequence of the aphid Myzus persicae to look for integrated viral sequences originating from viruses of the subfamily Densovirinae. We identified and confirmed the presence of genomic sequences sharing partial homology with Myzus persicae densovirus (MpDNV) and Dysaphis plantaginea densovirus (DplDNV) [START_REF] Ryabov | Densovirus induces winged morphs in asexual clones of the rosy apple aphid, Dysaphis plantaginea[END_REF]van Munster et al., 2003b). Interestingly, we also showed that these integrated viral sequences are transcribed in M. persicae. Previous studies have shown that MpDNV has a moderate effect on the development and fecundity of M. persicae with no significant effect on the intrinsic growth rate of the population (van Munster et al., 2003a). It is possible that integration and transcription of densovirus-like sequences (DLSs) sharing similarities with MpDNV could be responsible for the low pathogenicity of MpDNV in M. persicae.

RESULTS

Detection and organization of DLSs in the M. persicae genome

We screened the assembled genome of M. persicae (clone G006) for integrated sequences homologous to DNV, hereafter referred to as DLSs. BLAST searches were performed using as queries the reference strain sequences from each of the five genera in the subfamily Densovirinae (Brevidensovirus, Hepandensovirus, Iteradensovirus, Penstyldensovirus and Ambidensovirus) together with the genome sequences of the two known aphid DNVs, MpDNV and DplDNV. Twenty-one genomic sequences sharing significant sequence identity with MpDNV and DplDNV (E-values ranging from 2.10 2116 to 1.10 24 ) were identified on 10 scaffolds (Table 1). An additional genomic sequence from scaffold_883 exhibited sequence identity with the lepidopteran densovirus Junonia coenia densovirus (JcDNV), the type member of the genus Ambidensovirus (Table 1). DLS integrations covered genomic sequence lengths ranging from 87 to 1887 bp. Embedded in these sequences, deduced amino acid sequences of different lengths (from 29 to 664 aa) shared 24-74 % identity with NS or CP proteins of MpDNV, DplDNV or JcDNV (Table 1).

An almost-complete ambidensovirus-like genome was found on scaffold_1839 with the NS protein-coding sequences on one strand of the genome and the CP protein-coding sequences on the complementary strand. This organization of the coding sequences was consistent with that of genomes found in infectious virions (Fig. 1). A more peculiar situation was encountered on scaffold_794 where two almost-complete ambidensovirus-like genomes were integrated, both in reverse orientation (Fig. 1). This coding sequence structure may imply two independent but neighbouring insertions in the genome. The other scaffolds contained ambidensovirus-like sequences sharing homology with either NS or CP protein sequences. In most cases, these viral sequences were only partial. As several integrations were detected at the beginning or at the end of a scaffold (scaffold_564, _1826, _1646, _1268 and _1885), we cannot completely exclude the existence of additional virus-like sequences that may be missing in the available data.

The presence of DLS integrations in M. persicae genome was confirmed in another available M. persicae genome sequence (clone_O). All the integration events detected in the G006 clone were observed in clone_O (Table S1, available in the online Supplementary Material). This analysis was further extended to the genome of another aphid species, A. pisum (International Aphid Genomics Consortium, 2010). Using an updated full-genome sequence of A. pisum (assembly v.2), we retrieved 53 DLS integrations (Table S2). Previously, Liu et al. (2011b) described the presence of 49 DLS integrations in the A. pisum genome. The discrepancy between our analyses and those of Liu et al. (2011b) might result from the new assembly of an A. pisum genome. In contrast to the M. persicae genome, the DLS integrations in A. pisum shared sequence identity not only with MpDNV, DplDNV and JcDNV but also with two other DNVs belonging to the genus Ambidensovirus, Galleria mellonella densovirus (GmDNV) and Helicoverpa armigera densovirus (HaDNV) (Table S2). The observed DLS integrations covered genomic sequence lengths ranging from 165 to 462 bp. Portions of these sequences (55-1547 aa) shared amino acid sequence identity ranging from 23 to 46% when compared with the reference sequences of MpDNV, DplDNV, JcDNV, GmDNV and HaDNV proteins (Table S2).

The probability that these endogenous viral sequences correspond to DLSs was reinforced by the prediction of functional ORFs corresponding to either CP or NS proteins (Fig. 2, Table S3). On scaffold_1839, three ORFs potentially encoded one NS and two CP proteins, whereas on scaffold_794 each densovirus full-length integration could encode two NS and one CP protein (Fig. 2, Table S3). DLS integrations were confirmed experimentally by PCR amplification on an M. persicae clone originating from Colmar (France). In order to avoid potential non-specific detection of non-integrated MpDNV sequences, free MpDNV was eliminated from this clone by isolating individual larvae immediately after birth and depositing them on sugar beets (see Methods). A first set of primers was designed to specifically amplify the internal integrated sequences showing the highest nucleotide identity with the aphid DNV sequences (primers referred to as 'integration' in Table S4; primer positions shown in Fig. 2a). As shown in Fig. 2(b, upper panel), the presence of the integrated viral sequences was confirmed by amplification from the virus-free aphid genome of DNA fragments of the expected sizes (Table S4). The pair of primers for P XV amplified two fragments on the M. persicae genome: one of the expected size (142 bp) and a second representing a longer fragment (*200 bp), probably corresponding either to a nonspecific hybridization in the aphid genome (Fig. 2b, upper panel) or to a larger sequence that is fragmented in the current genome assembly upon which fragment size predictions were based. A second set of primers was designed to amplify DNA fragments encompassing insect and viral-like sequences (primers referred to as 'junction' in Table S4; primer positions shown in Fig. 2a). These fragments of larger size (1054-4131 bp) were also amplified from the M. persicae genome, although with a lower efficiency when using the two pairs of primers for P I and P IX (Fig. 2b, lower panel). Taken together, these results confirmed the presence of DLSs in the genome of M. persicae.

Phylogenetic analysis

To evaluate the genetic relationships between DLSs present in both the M. persicae and A. pisum genomes with known DNV sequences, we performed a phylogenetic analysis using all integrated sequences that contained a 300 bp DNA sequence from the NS1 gene. This sequence corresponds to highly conserved domains (DNA helicase and ATPase domains) of the rep gene in parvoviruses. As the nucleotide sequences were too divergent to be reliably aligned, we used the translated sequence of all 300 bp sequences (100 aa) to build a phylogenetic tree. Two nodes potentially corresponding to different integration events were observed (Fig. 3). The first cluster contained a mixture of DLSs found in the M. persicae and A. pisum genomes that grouped with MpDNV and DplDNV (Hub 1, bootstrap value 93%). In particular, M. persicae DLSs seemed to be closely related to these two aphid DNVs (bootstrap value 82%). The second cluster was almost exclusively composed of DLSs from A. pisum, and might result from a different integration event (Fig. 3).

Only one DLS in the M. persicae genome (MpDLS_28) grouped in this cluster, but the tree robustness at this level (Hub 2, bootstrap value 15%) was not sufficient to confirm with confidence the affiliation of MpDLS_28 to this cluster.

Transposable element (TE) detection in proximity to DLS integrations

We addressed the question of the frequency of TEs in proximity to DLS integrations to identify elements possibly responsible for the integration of the infectious virus sequence into the host genome (endogenization). Some parvoviruses appear to have evolved towards a transposon-like propagation during evolution, as was shown in

NS

Scaffold_413

(266 173 nt)

Scaffold_564

(193 318 nt)

Scaffold_794

(108 655 nt)

Scaffold_883

(69 518 nt)

Scaffold_1268

(27 708 nt)

Scaffold_1335

(26 965 nt)

Scaffold_1646

(16 671 nt)

Scaffold_1826

(10 113 nt)

Scaffold_1839

(9957 nt)

Scaffold_1885

(8960 nt)

Scaffold_28

( S4.

the acorn worm Saccoglossus kowalevskii (Liu et al., 2011a). We investigated the presence of TEs in genomic sequences of the clone G006 of M. persicae covering 30 kb upstream and downstream of each DLS using Repbase and National Center for Biotechnology Information (NCBI) sequence analysis tools (BLASTX and BLASTN) (Table S5). In four scaffolds (scaffold_794, _413, _1335 and _883), we detected TEs on both sides of DLS integrations (Fig. 1). On the other scaffolds, only one TE was located at either the 39 or 59 side of the DLS (Fig. 1). Several full-length (or almost-complete) sequences of TEs were present in some scaffolds (Table S5). Most of the putative TEs were DNA transposons from class II in the classification originally proposed by [START_REF] Finnegan | Eukaryotic transposable elements and genome evolution[END_REF]. Despite the presence of TEs in scaffolds containing DLSs, their presence could not be correlated with the presence of DLSs, as a similar frequency of TE integrations was also observed in DLSfree regions (data not shown). We also did not observe terminal inverted repeats flanking the DLSs, which are hallmarks of proliferation by transposition (data not shown). 1 andS2. Bootstrap values correspond to 1000 replications and are indicated for values .50 %. Sequences of 100 aa corresponding to translation of the integrated DLSs in M. persicae (see Table 1) and A. pisum genomes (see Table S2) sharing similarity with NS1 of parvoviruses were aligned with densovirus sequences arising from: Aedes albopictus densovirus (AaDNV; GenBank accession no. NC_004285.1), infectious hypodermal and haematopoietic necrosis virus (IHHNV; NC_002190.2), Bombyx mori densovirus 5 (BmDNV5; NC_004287.1), Fenneropenaeus chinensis hepatopancreatic densovirus (FchDV-1; NC_014357.1), JcDNV (NC_004284.1), MpDNV (NC_005040.1), DplDNV (EU851411.1), Periplaneta fuliginosa densovirus (PfDNV; NC_000936.1), GmDNV (NC_004286.1) and HaDNV (JQ894784.1). Chicken parvovirus NS1 (AJB28748.1) was used to root the tree. The scale represents probabilities of change from one amino acid to another in terms of a unit, which is an expected 1 % change between two amino acid sequences.

Transcription of DLSs in M. persicae

We addressed whether DLSs in the M. persicae genome were transcribed by performing reverse transcription (RT)-PCR and real-time RT-PCR experiments on polyadenylated mRNA extracted from whole aphids (clone Colmar deprived from MpDNV) (see Fig. 2 for position of the potential DLS ORFs). Absence of residual genomic DNA was first confirmed by a lack of amplification when the PCRs were performed directly on total RNA (data not shown). Primers (Table S4) were designed to specifically analyse transcription of each of the potential viral coding sequences on scaffold_1839 and _794. The expected DNA fragments were obtained for the NSint_1 and CPint_2 ORFs on scaffold_1839 or from the CPint_1 and CPint_2 ORFs on scaffold_794 (data not shown). Amplification was also observed using the primer pair for P IV (Fig. 2), which suggested a potential transcription of NSint_1 and/or NSint_4. Indeed, the high sequence identity between these two ORFs prevented detection of each specific mRNA. The specificity of the amplification reactions was confirmed by sequencing the amplified fragments. In contrast, no fragments or fragments of unexpected size were obtained using the other sets of primers amplifying potential transcripts from CPint_1 on scaffold_1839 or NSint_2 and/or NSint_3 on scaffold_794, suggesting an absence of transcription of these potential ORFs (data not shown). In a second step, in order to measure the rate of accumulation of the viral transcripts detected by RT-PCR, four independent real-time RT-PCRs were performed on polyadenylated mRNAs extracted from whole aphids, and the results of one representative experiment is presented in Fig. 4. The relative accumulation of mRNA transcribed from DLS ORFs was normalized to two housekeeping genes (RLP7 and L27). Interestingly, we observed amplification of mRNA for each of the DLS integrations assayed (Fig. 4). These expressions were confirmed in three additional experiments, although some variation in the transcription levels of CPint_1 on scaffold_794 and of CPint_2 on scaffold_1839 was observed between the different biological replicates (Fig. S1). Despite these variations, the tendency was in favour of a higher transcription of the DNV CP-like genes compared with the DNV NS-like genes.

DISCUSSION

Our study provides evidence of the presence of DLSs in the M. persicae genome. Integration of viral genomes belonging to the subfamily Densovirinae (family Parvoviridae) into arthropods has been reported previously and, in particular, DLSs have been identified in the genome of the pea aphid, A. pisum (Liu et al., 2011b). The presence of DLSs in the genome of M. persicae implies that the ancestor of M. persicae was infected with a DNV whose genome was endogenized. Three almost-complete ambidensovirus-like genomes were integrated into the genome of the two sequenced M. persicae clones, which have distinct geographical origins (clone_O from Europe and clone G006 from the USA). This suggests old and stable integration events. The high capacity of parvoviruses to integrate into their host genome is probably due to the virus replication cycle in the nucleus, which requires synthesis of a double-stranded replicative form and the presence of inverted terminal repeats that facilitate integration into the host DNA [START_REF] Berns | Parvovirus replication[END_REF][START_REF] Yang | Cellular recombination pathways and viral terminal repeat hairpin structures are sufficient for adeno-associated virus integration in vivo and in vitro[END_REF]. The mechanism by which DLS integrations occurred in the M. persicae genome is still unknown but is not thought to be linked to TEs, as no hallmarks of transposition were found in the proximities of DLSs. It is therefore likely that the integration paradigm of adeno-associated virus, which has been extensively studied, could apply to other members of the family Parvoviridae including DNVs. Adeno-associated virus integration relies on the endonuclease activity of its rolling-circle replication protein, a function that is shared with the NS1 protein of DNV [START_REF] Ding | Biochemical characterization of Junonia coenia densovirus nonstructural protein NS-1[END_REF][START_REF] Krupovic | Single-stranded DNA viruses employ a variety of mechanisms for integration into host genomes[END_REF].

Interestingly, potential coding capacities retained within the DLSs were identified, and transcription in M. persicae of the integrated NS-or CP-encoding sequences (hereafter referred to as NSint and CPint) was confirmed. As the predicted viral ORFs were not all transcribed, and the transcript levels from transcribed ORFs appeared unequal, the presence of functional promoters was assessed (Neural Network Promoter Prediction software, http://www. fruitfly.org/seq_tools/promoter.html; data not shown). In scaffold_1839, potential promoters upstream of CPint_2 were identified, whereas no promoter sequences were detected upstream of CPint_1. This observation could explain the lack of CPint_1 transcription observed in our experiments. On the same scaffold, potential promoters that could control transcription of NSint_1 were also found. On the other scaffold (scaffold_794), promoter-like sequences with the potential to control transcription of CPint_1 and CPint _2 were found upstream of each ORF. Transcription of NSint_1 and/or NSint_4 could also be explained by the presence of promoter-like sequences upstream of these two ORFs. As occurs in MpDNV, NS ORFs are supposed to be transcribed from a single promoter (van Munster et al., 2003b), so transcription of the downstream NSint_2 and NSint_3 was expected but not observed in our experiments. The absence of transcription of these ORFs could indicate a transcription termination signal between the two NSint ORFs. Altogether, promoter sequence identification coincided with our detection of viral transcripts. All potential promoter sequences driving transcription of the endogenous viral ORFs are probably of aphid origin, as they do not share any sequence similarity with the predicted promoters in MpDNV or with other viral sequences of MpDNV or DplDNV (data not shown). The higher level of transcription of CP-like genes compared with NS-like genes could therefore reflect a difference in endogenous host promoter transcription efficiency. Transcription of endogenized parvovirus sequences in A. pisum was also suggested previously, as expressed sequence tags exhibiting similarities to parvovirus-related DNA were reported in the NCBI public databases (Liu et al., 2011b). However, no experimental confirmation of mRNA accumulation of these parvovirus-related DNAs was reported. Although we clearly detected polyadenylated RNA originating from DLSs in M. persicae, the question of their translation remains.

Transcription, and potentially translation, of these sequences could explain the low pathogenicity of DNV in aphids. To date, there are only two DNVs described in aphids: MpDNV, which is highly specific to M. persicae (van Munster et al., 2003a), and DplDNV, identified in D. plantaginea [START_REF] Ryabov | Densovirus induces winged morphs in asexual clones of the rosy apple aphid, Dysaphis plantaginea[END_REF]. Interestingly, these aphid DNVs do not harm their host, in contrast to other DNVs which are highly pathogenic to their insect hosts [START_REF] Barreau | Pathogenicity of the Aedes albopictus parvovirus (AaPV), a denso-like virus, for Aedes aegypti mosquitoes[END_REF]Liu et al., 2011c;[START_REF] Mutuel | Pathogenesis of Junonia coenia densovirus in Spodoptera frugiperda: a route of infection that leads to hypoxia[END_REF][START_REF] Suto | Characterization of a virus newly isolated from the smoky-brown cockroach, Periplaneta fuliginosa (Serville)[END_REF]. MpDNV and DplDNV only slightly affect the development or reproduction of aphids [START_REF] Ryabov | Densovirus induces winged morphs in asexual clones of the rosy apple aphid, Dysaphis plantaginea[END_REF]van Munster et al., 2003a). Moreover, the existence of a selective advantage for the aphid to harbour the virus has been shown for DplDNV, which confers a beneficial effect on D. plantaginea by inducing the production of winged morphs at a low insect density, therefore promoting aphid dispersal [START_REF] Ryabov | Densovirus induces winged morphs in asexual clones of the rosy apple aphid, Dysaphis plantaginea[END_REF]. Concerning MpDNV, although there is a clear advantage for the virus to maintain a suboptimal infection that does not kill the host (van Munster et al., 2003a), no beneficial effect of MpDNV on M. persicae has been discovered so far (V. Brault, unpublished).

The cause for latency in DNV infections of these viruses within aphid hosts could be due to DLS integrations in the aphid genome, as reported in this study. Indeed, transcription of these viral integrated sequences could prime a silencing-based defence mechanism that could target cognate viruses and inhibit the development of an acute infection, as has been shown for Drosophila [START_REF] Goic | RNAmediated interference and reverse transcription control the persistence of RNA viruses in the insect model Drosophila[END_REF] and bees [START_REF] Maori | Reciprocal sequence exchange between non-retro viruses and hosts leading to the appearance of new host phenotypes[END_REF]. In this respect, DLSs in scaffold_794 or _1839 contained 12 stretches of 21-29 nt sharing either a perfect nucleotide sequence identity with MpDNV or having only one or two mismatches with MpDNV or DplDNV (Table S6). Although these sequence homologies were limited to a small portion of the viral genome, they were of an appropriate length to induce viral RNA degradation, or translation inhibition, which could control and limit infectious DNV multiplication. Another mechanism of protection induced by the integrated viral sequences could be the synthesis of nonfunctional DNV-like proteins that could inhibit virus multiplication, as has been shown for human immunodeficiency virus type 1 (HIV-1). Expression of a Gag protein from a human endogenous retrovirus impaired progeny release and HIV-1 infectivity [START_REF] Monde | Human endogenous retrovirus K Gag coassembles with HIV-1 Gag and reduces the release efficiency and infectivity of HIV-1[END_REF]. The formation of empty particles from endogenized CP protein genes able to prime insect immune protection against further infections could also be an alternative hypothesis explaining protection conferred by viral endogenized sequences. In addition, the activation of the immune system of the insect could be responsible for reducing the pathogenicity of the DNV. These different aspects of virus control should be addressed in the future.

METHODS

Insect rearing and virus clearing. An M. persicae (Sulzer) clone from Colmar (France) was reared on pepper (Capsicum anuum) at 20 uC with a 16 h photoperiod. This clone was infected with MpDNV. The same clone was cured of MpDNV by transferring individual larvae directly after birth onto beets (Beta vulgaris) to avoid contamination by contact. The absence of MpDNV was monitored by PCR (van Munster et al., 2003a), and one aphid colony cured of MpDNV was maintained on B. vulgaris.

DLS detection in the M. persicae and A. pisum genomes. To screen for DLSs in the M. persicae genome, BLASTN and tBLASTn searches were performed online against the AphidBase database (http://www.aphidbase.com/aphidbase/), using M. persicae clone G006 (originating from the USA; [START_REF] Ramsey | Genomic resources for Myzus persicae: EST sequencing, SNP identification, and microarray design[END_REF] as a reference genome (scaffolds). Full DNA genomes of the following subfamily Densovirinae member types: infectious hypodermal and haematopoietic necrosis virus (IHHNV, genus Penstyldensovirus), Aedes albopictus densovirus (AaDNV, genus Brevidensovirus), Bombyx mori densovirus 5 (BmDNV5, genus Iteradensovirus), Fenneropenaeus chinensis hepandensovirus (FchDV-1, genus Hepandensovirus) and JcDNV (genus Ambidensovirus), as well as full DNA genomes and NS and CP protein sequences of MpDNV and DplDNV, were used as queries. All non-redundant hits from these searches with E-values of v1.10 23 were extracted and used in further analyses.

To eliminate possible chimeras or errors in DLS regions of the genome assembly, BLAST searches using extracted DLSs from M. persicae clone G006 were performed against the genome of M. persicae clone_O (available in AphidBase and originating from the UK). In a similar manner, BLAST searches were performed on the updated assembly of the A. pisum genome (assembly v.2) also available in AphidBase. A. pisum sequences showing similarity to subfamily Densovirinae representatives were also identified and extracted for phylogenetic analysis.

Integration of DLSs in M. persicae clones was confirmed by amplifying virus-like sequences using specific primer pairs designed with the Primer3 program [START_REF] Rozen | Primer3 on the WWW for general users and for biologist programmers[END_REF] and with binding sites in both flanking host and virus insertion sequence (Table S4, Fig. 2). Total genomic DNA was extracted from 30 aphids, which were ground in liquid nitrogen using the QIAamp DNA Mini kit protocol (Qiagen). One microlitre of DNA (20-30 ng ml 21 ) was used for PCRs containing the specific primers and performed in a thermal cycler (Eppendorf) using standard protocols. PCR products were analysed by 0.7 or 2% agarose gel electrophoresis depending on amplicon size and visualized under UV after ethidium bromide staining.

Alignment and phylogenetic reconstruction. Phylogenetic trees were reconstructed using the predicted amino acid sequences of DLSs. Protein sequences of 100 aa corresponding to a region of the DLS sharing similarity with NS1 of parvoviruses were aligned with the corresponding sequences of known DNVs including subtypes of the subfamily Densovirinae using the MUSCLE program configured for high accuracy [START_REF] Edgar | MUSCLE: Multiple sequence alignment with high accuracy and high throughput[END_REF]. The DNV sequences used in the alignment were: AaDNV (GenBank accession no. NC_004285.1), IHHNV (NC_002190.2), BmDNV5 (NC_004287.1), FchDV-1 (NC_014357.1), JcDNV, (NC_004284.1), MpDNV (NC_005040.1), DplDNV (EU851411.1), Periplaneta fuliginosa densovirus (NC_000936.1), GmDNV (NC_004286.1) and HaDNV (JQ894784.1). Phylogenetic relationships among DLS integrations and DNVs were assessed using the Phylogeny.fr platform [START_REF] Dereeper | Phylogeny.fr: robust phylogenetic analysis for the non-specialist[END_REF]. The phylogenetic tree was reconstructed using the maximum-likelihood method implemented in the PhyML program (v.3.1/3.0 aLRT). The JTT 1 G model [START_REF] Jones | The rapid generation of mutation data matrices from protein sequences[END_REF], a commonly used probabilistic amino acid replacement matrix at the 85% identity level allowing heterogeneity across sites, was selected. Reliability for the internal branch was assessed using the aLRT test (SH-Like). Node support was estimated using bootstrap resampling procedures (1000 trials). Trees were edited using TREEDYN (v.198.3) [START_REF] Chevenet | TreeDyn: towards dynamic graphics and annotations for analyses of trees[END_REF].

Detection of TEs in the M. persicae genome. A 30 000 bp region encompassing each DLS was scanned for adjacent TEs or repetitive sequences using CENSOR (Repbase; http://www.girinst.org/censor/ index.php) with a reference collection of sequence repeats [START_REF] Kohany | Annotation, submission and screening of repetitive elements in Repbase: RepbaseSubmitter and Censor[END_REF]. BLASTX and tBLASTx queries on these flanking DLS regions against the non-redundant (nr) protein database at NCBI were also performed. As a control, repetitive sequences in DLS-free regions of scaffolds harbouring DLSs and on scaffolds where no DLSs could be detected were also analysed.

Transcription of DLSs in M. persicae. Transcription of DLSs was analysed by real-time RT-PCR in fourth-instar individuals of M. persicae (clone Colmar). Total RNA was extracted from aphids cured of MpDNV (four biological replicates) ground in liquid nitrogen following the Qiagen RNeasy Plant Mini kit protocol (animal tissue protocol). On-column DNase treatment was carried out using an RNase-Free DNase set (Promega). Synthesis of cDNA (from 2 mg RNA) was primed using oligo(dT) (Promega) and cDNA synthesis was done using the Moloney murine leukemia virus reverse transcriptase (Promega). The cDNA was then used as a template for real-time PCR amplification (primers listed in Table S4) using an iTaq universal SYBR Green supermix (Bio-Rad Laboratories). Ribosomal proteins RLP7 and L27 were used as internal controls. The amplification reaction consisted of 10| SYBR Green supermix and 10 pmol forward and reverse primers (Table S4) in a final volume of 20 ml. Three technical repeats were performed using a CFX96 Touch Real-Time PCR Detection System (Bio-Rad Laboratories). The mRNA synthesis was normalized with RLP7 and L27 using the 2 2DDCt method [START_REF] Livak | Analysis of relative gene expression data using real-time quantitative PCR and the 2 2DDC T method[END_REF] and analysed with Bio-RadCFX Manager software (Bio-Rad Laboratories).

  4Present address: Institut de Biologie Mole ´culaire des Plantes, Laboratoire propre du CNRS conventionne ´avec l'Universite ´de Strasbourg, 12 rue du Ge ´ne ´ral Zimmer, 67084 Strasbourg, France. One supplementary figure and five tables are available with the online Supplementary Material.

Fig. 1 .

 1 Fig. 1. DLSs and surrounding transposable elements (TEs) in the M. persicae genome. The shaded arrows correspond to DLSs with similarity to NS proteins of DNV, the hatched grey arrows to DLSs with similarity to CP proteins of DNVs, the filled arrows to TEs and the open arrows to host genes. The size of each scaffold is indicated in parentheses. The position of full-length DLSs is shown as FL*.

Fig. 2 .

 2 Fig. 2. (a) Schematic representation of DLSs in scaffold_1839 (upper panel) and scaffold_794 (lower panel) of the M. persicae genome (clone G006). Shaded arrows on the black line stand for potential ORFs of DLS (NSint and CPint). The percentage identity with the corresponding sequence in the genome of MpDNV is indicated above. The nucleotide position of these potential ORFs in the scaffold together with the first methionine ([INSERT Fig. 002][INSERT Fig. 001]) in the sequence is indicated. The MpDNV genome organization is presented below with variously shaded arrowheads. The position of primers used to confirm DLS integrations and transcription is shown by short arrows. (b) Confirmation of DLS integration in scaf-fold_1839 and scaffold_794 in the genome of M. persicae DNA (clone Colmar) by PCR amplification of internal integrated viral sequences (upper panel) or junctions between DLSs and the M. persicae sequence (lower panel). PCR products were separated by gel electrophoresis on a 2 % (upper panel) or 0.7 % (lower panel) agarose gel. The names of primers and the targeted scaffolds (S) are indicated above each lane. The position of molecular mass markers (lane L) is shown on the left. The asterisk indicates a non-specific amplification, while arrowheads show DNA fragments of low intensity. The primer sequences are listed in TableS4.

Fig. 3 .

 3 Fig. 3. Phylogenetic relationships of DLS integrations in M. persicae, A. pisum and exogenous DNVs (underlined). DLS nomenclature is consistent with Tables1 and S2. Bootstrap values correspond to 1000 replications and are indicated for values .50 %. Sequences of 100 aa corresponding to translation of the integrated DLSs in M. persicae (see Table1) and A. pisum genomes (see TableS2) sharing similarity with NS1 of parvoviruses were aligned with densovirus sequences arising from: Aedes albopictus densovirus (AaDNV; GenBank accession no. NC_004285.1), infectious hypodermal and haematopoietic necrosis virus (IHHNV; NC_002190.2), Bombyx mori densovirus 5 (BmDNV5; NC_004287.1), Fenneropenaeus chinensis hepatopancreatic densovirus (FchDV-1; NC_014357.1), JcDNV (NC_004284.1), MpDNV (NC_005040.1), DplDNV (EU851411.1), Periplaneta fuliginosa densovirus (PfDNV; NC_000936.1), GmDNV (NC_004286.1) and HaDNV (JQ894784.1). Chicken parvovirus NS1 (AJB28748.1) was used to root the tree. The scale represents probabilities of change from one amino acid to another in terms of a unit, which is an expected 1 % change between two amino acid sequences.

Fig. 4 .

 4 Fig. 4. Transcription profiles of DLSs in M. persicae. The relative mRNA abundance of potential DLS ORFs in M. persicae (clone Colmar without free MpDNV) were measured by real-time RT-PCR and normalized to the values for the ribosomal housekeeping genes RLP7 and L27. Error bars correspond to technical triplicates. The names of primers (see TableS4) and potential ORFs transcribed are indicted below each bar.

  Fig. 4. Transcription profiles of DLSs in M. persicae. The relative mRNA abundance of potential DLS ORFs in M. persicae (clone Colmar without free MpDNV) were measured by real-time RT-PCR and normalized to the values for the ribosomal housekeeping genes RLP7 and L27. Error bars correspond to technical triplicates. The names of primers (see TableS4) and potential ORFs transcribed are indicted below each bar.

Table 1 .

 1 Inventory of DLS integrations within the M. persicae genome (clone G006) using five genera of DNVs as queries

	E-value Name of DLS	in Phylogeny		2E-76 MpDLS_28		1E-08		2E-25	1E-04		5E-24	3E-99 MpDLS_794-1	3E-14	1E-14	3E-99 MpDLS_794-2	1E-108	5E-18		2E-20		3E-04	1E-34		1E-22		8E-08	8E-08	5E-105 MpDLS_1826	2E-116 MpDLS_1839		7E-105	2E-13	4E-38
	Alignment	length	(aa)	316		138		116	36		200	365	143	151	365	560	50		136		59	115		154		29	49	664	292		571	166	149
	Aa	ID	(%)	43.0		24.0		42.2	58.3		33.0	51.2	36.4	35.8	51.2	41.1	74.00		41.9		39.0	60.9		40.3		51.7	34.7	37.5	63.0		40.6	33.7	51.0
	GenBank accession no.			gi|204324151|gb|ACI01073_1|		gi|204324151|gb|ACI01073_1|		gi|33235701|ref|NP_874378_1|	gi|204324153|gb|ACI01075_1|		gi|33235702|ref|NP_874377_1|	gi|33235700|ref|NP_874376_1|	gi|33235699|ref|NP_874375_1|	gi|33235699|ref|NP_874375_1|	gi|33235700|ref|NP_874376_1|	gi|33235702|ref|NP_874377_1|	gi|204324153|gb|ACI01075_1|		gi|204324154|gb|ACI01076_1|		gi|257676|gb|AAB23698_1|	gi|204324154|gb|ACI01076_1|		gi|204324154|gb|ACI01076_1|		gi|33235699|ref|NP_874375_1|	gi|33235699|ref|NP_874375_1|	gi|33235700|ref|NP_874376_1|	gi|204324151|gb|ACI01073_1|		gi|33235702|ref|NP_874377_1|	gi|33235701|ref|NP_874378_1|	gi|204324154|gb|ACI01076_1|
	Related	gene		NS		NS		CP	CP		CP	NS	NS	NS	NS	CP	CP		CP		CP	CP		CP		NS	NS	NS	NS		CP	CP	CP
	Scaffold Nt DNV genus Top viral BLAST hit	size (bp) position of (reference strain)	integration	1 079 708 674429-675373 Ambidensovirus Dysaphis plantaginea	densovirus	1 079 708 673450-673863 Ambidensovirus Dysaphis plantaginea	densovirus	266 173 193157-192810 Ambidensovirus Myzus persicae densovirus	193 318 1124-1231 Ambidensovirus Dysaphis plantaginea	densovirus	108 655 11516-12106 Ambidensovirus Myzus persicae densovirus	108 655 13426-12422 Ambidensovirus Myzus persicae densovirus	108 655 13904-13491 Ambidensovirus Myzus persicae densovirus	108 655 15297-15734 Ambidensovirus Myzus persicae densovirus	108 655 15799-16803 Ambidensovirus Myzus persicae densovirus	108 655 18741-17119 Ambidensovirus Myzus persicae densovirus	108 655 18750-18601 Ambidensovirus Dysaphis plantaginea	densovirus	108 655 19148-18762 Ambidensovirus Dysaphis plantaginea	densovirus	69 518 62012-62188 Ambidensovirus Junonia coenia densovirus	27 708 714-370 Ambidensovirus Dysaphis plantaginea	densovirus	26 965 15334-15789 Ambidensovirus Dysaphis plantaginea	densovirus	16 671 298-212 Ambidensovirus Myzus persicae densovirus	16 671 456-316 Ambidensovirus Myzus persicae densovirus	10 113 2042-156 Ambidensovirus Myzus persicae densovirus	9 957 6335-7213 Ambidensovirus Dysaphis plantaginea	densovirus	9 957 9111-7447 Ambidensovirus Myzus persicae densovirus	9 957 9505-9041 Ambidensovirus Myzus persicae densovirus	8 960 8151-8591 Ambidensovirus Dysaphis plantaginea	densovirus
	Scaffold no.			scaffold_28		scaffold_28		scaffold_413	scaffold_564		scaffold_794	scaffold_794	scaffold_794	scaffold_794	scaffold_794	scaffold_794	scaffold_794		scaffold_794		scaffold_883	scaffold_1268		scaffold_1335		scaffold_1646	scaffold_1646	scaffold_1826	scaffold_1839		scaffold_1839	scaffold_1839	scaffold_1885

http://jgv.microbiologyresearch.org

Journal of General Virology 97

ACKNOWLEDGEMENTS

DNA sequence data were downloaded from AphidBase (http://www. aphidbase.com/aphidbase/). Funding for M. persicae clone G006 genomic sequencing was provided by USDA-NIFA award 2010-65105-20558 held by Alex Wilson (Miami University, OH, USA). Funding for M. persicae clone_O genomic sequencing was provided by The Genome Analyses Centre (TGAC) Capacity and Capability Challenge program project CCC-15 held by Saskia Hogenhout and from the Biotechnology and Biological Sciences Research Council (BBSRC) (BB/J004553/1) and the John Innes Foundation. We are grateful to Fabrice Legeai and Antony Bretaudeau (INRA, Rennes) for their assistance in aphid genomic sequences analysis. We also thank Denis Filloux (INRA, Montpellier, France) for his help in database analysis, Neta Luria and Aviv Dombrovsky (Volcani Center, Israel) and Pierre Gladieux (INRA, Montpellier, France) for their fruitful discussions. We are grateful to Keith Garrisson (Saint Mary's College of California, CA, USA) and A. Wilson for critically reading this manuscript.