Frédéric Havet
email: frederic.havet@sophia.inria.fr.

Martin Klazar

Jan Kratochvíl

Dieter Kratsch
email: kratsch|liedloff@univ-metz.fr.

Mathieu Liedloff

Keywords: colouring, contraintes de distances, L(2, 1)-étiquetage, algorithme exact

The notion of distance constrained graph labelings, motivated by the Frequency Assignment Problem, reads as follows: A mapping from the vertex set of a graph G = (V, E) into an interval of integers {0, . . . , k} is an L(2, 1)-labeling of G of span k if any two adjacent vertices are mapped onto integers that are at least 2 apart, and every two vertices with a common neighbor are mapped onto distinct integers. It is known that for any fixed k ≥ 4, deciding the existence of such a labeling is an NP-complete problem. We present exact exponential time algorithms that are faster than the naive O((k + 1) n ) algorithm that would try all possible mappings. The improvement is best seen in the first NP-complete case of k = 4 -here the running time of our algorithm is O(1.3006 n ). Furthermore we show that dynamic programming can be used to establish an O(3.8730 n ) algorithm to compute an optimal L(2, 1)-labeling.

Algorithmes exacts pour le L(2, 1)-étiquetage des graphes

Résumé : La notion d'étiquetage de graphes avec des contraintes de distance, qui est motivé par le Problème d'Allocationde Fréquences, est la suivante: Une application de l'ensemble des sommets d'un graphe G = (V, E) dans un intervalle d'entiers naturels {0, . . . , k} est un L(2, 1)-étiquetage de G de largeur ksi deux sommets adjacents recoivent des entiers à distance au moins 2 et des sommets ayant un voisin en commun des entiers distincts. Il est connu que pour k ≥ 4, décider de l'existence d'un tel étiquetage est un problème N P -complet. Nous présentons ici des algorithmes exacts exponentiels qui sont plus rapides que l'algorithme naive en temps O((k + 1) n ) qui essaie toutes kes possibilités. L'amélioration est particulièrement visible dans le cas où k = 4 : dans ce cas le temps d'execution de notre algorithme est O(1.3006 n ). De plus nous montrons que la programmation dynamique peut être utilisée pour obtenir un algorithme en temps O(3.8730 n ) qui calcule le L(2, 1)-étiquetage de largeur minimum.

Mots-clés : coloration, distance constrained, L(2, 1)-labeling, exact algorithm

Introduction

History. The Frequency Assignment Problem (FAP) asks for assigning frequencies to transmitters in a broadcasting network with the aim of avoiding undesired interference. One of the graph theoretical models of FAP which is well elaborated is the notion of distance constrained labeling of graphs. An L(2, 1)-labeling of a graph G is a mapping from the vertex set of G into nonnegative integers such that the labels assigned to adjacent vertices differ by at least 2, and labels assigned to vertices of distance 2 are different. The span of such a labeling is the maximum label used. In this model, the vertices of G represent the transmitters and the edges of G express which pairs of transmitters are too close to each other so that an undesired interference may occur, even if the frequencies assigned to them differ by 1. This model was introduced by Roberts [START_REF] Roberts | RR n 6587 Centre de recherche INRIA Sophia Antipolis -Méditerranée[END_REF] and since then the concept has been intensively studied. Undoubtedly, distance constrained graph labelings provide a graph invariant of significant theoretical interest. Let us mention a few of the known results and open problems: Griggs and Yeh [START_REF] Griggs | Labelling graphs with a condition at distance 2[END_REF] proved that determining the minimum possible span of G -denoted by L 2,1 (G) -is an NP-hard problem. Fiala et al. [START_REF] Fiala | Fixed-parameter complexity of λ-labelings[END_REF] later proved that deciding L 2,1 (G) ≤ k remains NP-complete for every fixed k ≥ 4, while Bodlaender et al. [START_REF] Bodlaender | Approximations for lambda-Colorings of Graphs[END_REF] proved NP-hardness for planar inputs for k = 8. (For 4 ≤ k ≤ 7 and planar inputs, the complexity is still open.) When the span k is part of the input, the problem is nontrivial even for trees -though a polynomial time algorithm based on bipartite matching was presented in [START_REF] Chang | The L(2, 1)-labeling problem on graphs[END_REF], existence of a linear time algorithm for trees is still open. Moreover, somewhat surprisingly, the problem becomes NP-complete for series-parallel graphs [START_REF] Fiala | Distance Constrained Labelings of Graphs of Bounded Treewidth[END_REF], and thus the L(2, 1)-labeling problem belongs to a handful of problems known to separate graphs of tree-width 1 and 2 by P/NP-completeness dichotomy. From the structural point of view, Griggs and Yeh [START_REF] Griggs | Labelling graphs with a condition at distance 2[END_REF] conjectured that every graph of maximum degree ∆ satisfies L 2,1 (G) ≤ ∆ 2 . Gonçalves [START_REF] Gonc ¸alves | On the L(p, 1)-labelling of graphs[END_REF] proved the upper bound L 2,1 (G) ≤ ∆ 2 + ∆ -2 by analyzing an algorithm of Chang and Kuo [START_REF] Chang | The L(2, 1)-labeling problem on graphs[END_REF]. Very recently, using probabilistic arguments, Havet, Reed and Sereni [START_REF] Havet | L(2, 1)-labellings of graphs[END_REF] settled Griggs and Yeh conjecture for large enough ∆. However, for ∆ > 2, the Moore graphs are the only graphs known to require span ∆ 2 , and for large ∆ the graphs known to require the largest span are incidence graphs of projective planes for which L 2,1 ≥ ∆ 2 -∆.

It is an open problem if there are infinitely many graphs satisfying

L 2,1 (G) > ∆ 2 -o(∆).
Generalizations have been considered, both in the direction of taking into account larger distances and in the direction of allowing a more complicated structure of the frequency space. In the latter direction, circular metric was considered by Leese et al. [START_REF] Leese | Cyclic labellings with constraints at two distances[END_REF] and Liu et al. [START_REF] Liu | Circular Distance Two Labelings and Circular Chromatic Numbers[END_REF], showing that in certain sense the circular metric is easier than the linear one (e.g., the circular span of a tree is uniquely determined by its maximum degree and can thus be determined in linear time). Fiala and Kratochvíl consider in [START_REF] Fiala | Complexity of partial covers of graphs[END_REF] the utmost generalization for the case when the metric in the frequency space can be described by a graph, say H. They define the notion of an H(2, 1)-labeling of G, which is a mapping from the vertex set of G into the vertex set of H such that vertices adjacent in G are mapped onto nonadjacent (distinct) vertices of H, and vertices with a common neighbor (in G) are mapped onto distinct vertices of H. They also show that H(2, 1)-labelings are exactly locally injective homomorphisms from G to H, the complement of H. In particular, an L(2, 1)-labeling of span k is a locally injective homomorphism into the complement of the path of length k. (The complement of the path of length 4 is depicted in Figure 1(a).) The complexity of locally injective homomorphisms was considered in [START_REF] Fiala | Complexity of partial covers of graphs[END_REF][START_REF] Fiala | Partial covers of graphs[END_REF][START_REF] Fiala | On the computational complexity of partial covers of theta graphs[END_REF] where a number of NP-complete cases were identified, but the complete characterization is still open.

Regarding larger distance constraints, the general channel assignment problem was addressed in [START_REF] Liu | Multilevel distance labelings for paths and cycles[END_REF] and [START_REF] Král | Channel assignment problem with variable weights[END_REF]. This problem asks, given a graph G and nonnegative integer weights w : E(G) → {0, 1, 2, . . .} on edges, for a labeling f : V (G) → {0, 1, . . . , k} such that |f (u)f (v)| ≥ w(uv) for every edge uv ∈ E(G); the aim is to minimize k, the span of the assignment. Král [START_REF] Král | Channel assignment problem with variable weights[END_REF] shows that, using Dynamic Programming, this problem can be solved in time O * ((l + 2) n ), where l is the maximum edge weight and n the number of vertices of G. Since an L(2, 1)-labeling on G can be expressed as the channel assignment problem on G (2) (the distance power of G) with weights 1 and 2 only -weight 1 for pairs of vertices at distance 2 in G, weight 2 for the edges of G -, an O * (4 n ) time exact algorithm for the L(2, 1)-labeling problem follows.

Our results. The goal of this paper is to explore exact exponential time algorithms for the L(2, 1)-labeling problem. Since one cannot hope for polynomial time algorithms (unless P = NP), our aim is to design algorithms with running time O * (c n ) and minimizing the constant c. 1 First we consider exact algorithms deciding whether the input graph has an L(2, 1)-labeling of span at most k. We show that it is not difficult to beat the trivial bound c ≤ k + 1 (which follows from merely checking all possible mappings from V (G) into {0, 1, . . . , k}) by presenting an algorithm of running time O * ((k -2) n ) which can also be generalized to the H(2, 1)-labeling problem. Then we refine the branching algorithm for the case of span k = 4 to achieve an algorithm of running time O * (1.3161 n ) (beating c = k -2 = 2). By a refined analysis we establish an improved running time of O * (1.3006 n ) for the same algorithm. We also obtain a lower bound of Ω(1.2290 n ) for the worst-case running time of our algorithm.

Finally we study the problem of computing an optimal L(2, 1)-labeling, i.e., one of the smallest span. By designing a general branching algorithm similar to the one for span 4, we give a polynomial space algorithm for computing an L(2, 1)-labeling of span k, if one exists, in time O * ((k -2.5) n ). Then, we show that by a dynamic programming approach the L 2,1 -span of a graph can be computed and an optimal L(2, 1)-labeling can be constructed in time O(3.8730 n ) and exponential space.

Preliminaries. Throughout the paper we consider finite undirected graphs without multiple edges or loops. The vertex set (edge set) of a graph G is denoted by V (G) (E(G), respectively). The open (closed) neighborhood of a vertex u in G is denoted by N G (u) (N G [u], respectively). The symbol n is reserved for the number of vertices of the input graph, which will always be denoted by G.

The subgraph of G = (V, E) induced by S ⊆ V is denoted by G[S]. A subset S ⊆ V fulfilling N [u] ∩ N [v] = ∅ for all u, v ∈ S, is called a 2-packing of G.

Exact algorithm for locally injective homomorphisms

A graph homomorphism is an edge preserving vertex mapping between two graphs. More formally, a mapping f :

V (G) → V (H) is a homomorphism from G to H if f (u)f (v) ∈ E(H) whenever uv ∈ V (G)
. Such a mapping is sometimes referred to as an H-coloring of G since homomorphisms provide a generalization of the concept of graph colorings -k-colorings of G are exactly homomorphisms from G to the complete graph K k . Hell and Nešetřil [START_REF] Hell | On the complexity of H-colouring[END_REF] proved that from the computational complexity point of view, homomorphisms admit a complete dichotomy -deciding existence of a homomorphism into a fixed graph H is polynomial when H is bipartite and NP-complete otherwise. The study of exact algorithms for graph homomorphisms was initiated in [START_REF] Fomin | Exact algorithms for graph homomorphisms[END_REF]. A homomorphism f : G → H is called locally injective if for every vertex u ∈ V (G), its neighborhood is mapped injectively into the neighborhood of f (u) in H, i.e., if every two vertices with a common neighbor in G are mapped onto distinct vertices in H. When deciding the existence of a locally injective homomorphism, one might try to utilize the known algorithms that list all possible homomorphisms and then check if any of them is locally injective. It is not surprising that using the local injectivity, one can often do much better. The trivial brute-force algorithm for H-homomorphism relates the base of the exponential function that expresses the running time to the number of vertices of H, while we show in Theorem 1 that H-locally-injective-homomorphism can be solved in time O * ((∆(H) -1) n ), where ∆(H) is the maximum degree of a vertex of H. This, in most cases considerable, speed-up is achieved when we label the vertices consecutively using the fact that a neighbor of an already labeled vertex has only a limited number of candidate labels.

Without loss of generality we may assume that G is a connected graph, since otherwise we solve the problem on each connected component of G separately. In the algorithm, f denotes a partial labeling of the vertices of G by vertices of H which is a candidate for a locally injective homomorphism from G to H.

Algorithm-H-LIH(G)

if ∃v ∈ V (G) s.t. v is unlabeled and v has at least one neighbor u which was already labeled then

foreach c ∈ N H (f (u)) \ f (N G (u)) do set f (v) = c Algorithm-H-LIH(G) else if ∃u ∈ V (G) s.t. u is unlabeled then foreach c ∈ V (H) do set f (u) = c Algorithm-H-LIH(G)
else if the labeling f is a locally injective homomorphism from G to H then return the labeling

Theorem 1. The H-Locally-Injective-Homomorphism problem is solved in time O * ((∆(H) -1) n ) by Algorithm-H-LIH.
Proof. In the first step the algorithm picks an unlabeled vertex, say u, and labels it in |V (H)| ways. In the second step, the first rule is used and a neighbor v of u is labeled in deg H (f (u)) ≤ ∆(H) ways. From this time on, the algorithm branches each time into at most ∆(H)-1 ways. To see this, let T = (V (G), E(T )) be an auxiliary graph which contains the edges uv from the application of the first rule. The loop invariant of the algorithm is that T is an acyclic graph consisting of one connected component -containing

INRIA

the so far labeled vertices -and remaining isolated (and unlabeled) vertices. Also, f (u)f (v) ∈ E(H) for every edge uv ∈ E(T ). From the third round on, the first rule is always applied, and one edge uv is added to T . And since u had another neighbor w in T , f (w) ∈ N H (f (u)) and so N H (f (u))\f (N G (u)) has at most ∆(H) -1 available labels for v.

Corollary 2. The L(2, 1)-labeling problem of span k can be decided in time

O * ((k -2) n ).
In particular, L(2, 1)-labeling of span 4 can be solved in time

O * (2 n ).
Proof. The maximum degree of a vertex in the complement of the path of length k is ∆(P k+1 ) = k -1.

On the other hand, the exact algorithm for channel assignment of Kral' [START_REF] Král | Channel assignment problem with variable weights[END_REF] when applied to the special case L(2, 1)-labeling has running time O * (4 n ). Thus only for small span can we hope to improve on both, the running time O * ((k -2) n ) of Corollary 2 and the running time O * (4 n ) of the dynamic programming algorithm of Kral'.

A branching algorithm for computing an L(2, 1)labeling of span 4

In this section we present a significantly faster algorithm for the case of L(2, 1)-labeling of span 4. The main idea is the same as for Algorithm-H-LIH -in the first two steps we label two adjacent vertices in all possible (i.e., at most 12) ways. Then we keep labeling the vertices one by one (and branching into several possibilities when necessary) so that the so far labeled part of the input graph G remains connected. It follows that every newly labeled vertex has (at least) one labeled neighbor, and this labeled neighbor has another (at least one) labeled neighbor. The key idea of the speed-up is two-fold. First, we list several rules and apply them in order of their preferences, thus aiming at reducing the number of branching steps. Secondly, we often label several vertices at a time which leads to a more convenient recursion for the upper bound of the running time.

Throughout this section, we assume that we are in the middle of a run of our algorithm and that f :

X → {0, 1, 2, 3, 4} is a partial L(2, 1)-labeling of G such that the labeled vertices X ⊆ V (G) induce a connected subgraph.
Note that in order to have a chance to admit a valid labeling, G must have maximum degree at most 3. It is also clear that every vertex of degree 3 must be labeled by 0 or 4, and we will keep checking that this condition is satisfied by each candidate labeling f . To avoid trivial cases we assume that G has at least one vertex of degree 3. Now we describe the rules and discuss their effect on the running time. When a rule is applied to a partially labeled graph, there are at least two labeled vertices and its labeled vertices induce a connected subgraph. In addition, it may be impossible to extend the partial L(2, 1)-labeling in which case the algorithm stops. For the sake of clarity and brevity, this is not written but implicitly assumed. Note that only Rules 4 and 5 use branchings.

Rule 1 -Forced extensions (a) If u is an unlabeled vertex whose labeled neighbor v has two labeled neighbors, then the possible label of u is uniquely determined by the labels of v and its neighbors;

(b) if u is an unlabeled vertex with a neighbor v labeled by 1, 2 or 3, then, since v has another labeled neighbor, the label of u is uniquely determined by the labels of v and this neighbor;

(c) if u is an unlabeled vertex of degree 3 with a labeled neighbor v, then the label of u is either 0 or 4 and is uniquely determined by the label of v and its other labeled neighbor;

(d) if u is an unlabeled vertex of degree 2 such that one of its neighbors is labeled and the other one is a (possibly unlabeled) degree 3 vertex, then the label of u is uniquely determined by the labels of its neighbor(s).

The configurations corresponding to these forced extensions are depicted in Figure 2. In each case the label of vertex u is uniquely determined by the ones of the already labeled vertices (in black). Rule 1 (a): Suppose that there exists a labeled vertex v having two labeled neighbors, say v 1 and v 2 , and one unlabeled neighbor u. Thus, the INRIA label of v is either 0 or 4, and the label of u must be the unique element of

N f (v) \ {f (v 1 ), f (v 2 )}.
Rule 1 (b): If there is a vertex v with f (v) ∈ {1, 2, 3} having a labeled neighbor v ′ , then its remaining unlabeled neighbor must be labeled by the unique element of

N f (v) \ {f (v ′ )}.
Rule 1 (c): Suppose that v is a vertex labeled by 2. The label of its neighbors should be in N 2 = {0, 4}. Thus, knowing the label of one of its neighbors implies the label of the other. Otherwise, if v has a label different from 2, then N f (v) contains either 0 or 4, forcing the label of a degree-three neighbor.

Rule 1 (d): Suppose that an unlabeled vertex u is adjacent to a labeled vertex v and to u ′ , a vertex of degree 3. If f (v) = 0 then f (u) must be 2, otherwise, there is no way to label u ′ . Symmetrically, if

f (v) = 4 then f (u) is set to 2. If f (v) is in {1, 2, 3} then, as in the second forced extension, the label of u is the unique element of N f (v) \ {f (v ′ )}.
Note that if Rule 1 cannot be applied, every unlabeled vertex that is adjacent to a labeled one has degree at most 2 and each of its adjacent labeled vertices is labeled by 0 or 4. Definition 3. A path in G is called an extension path if all inner vertices are unlabeled and of degree 2, at least one endpoint is labeled and the unlabeled endpoint (if there is one) has either degree 1 or 3. (With a slight abuse of notation we allow that the endpoints are the same vertex, so such an extension path is in fact a cycle and the endpoint is labeled.) The length of an extension path is its number of edges.

Lemma 4. Let P = v 0 v 1 . . . v k be an extension path such that v 0 is labeled and v k has degree 1 (and is unlabeled). Let G ′ = G[V (G)\{v 1 , . . . , v k }] be the subgraph obtained by deleting the path P and let f ′ : V (G ′ ) → {0, 1, 2, 3, 4} be a valid extension of f to an L(2, 1)-labeling of G ′ . Then f ′ can be extended to an L(2, 1)-labeling of the entire graph G.

Proof. Since deg(v 0 ) ≤ 3 and f ′ (v 0 ) ∈ {0, 4} if deg(v 0 ) = 3,
there is always a label, say ℓ, available for v 1 . The edge f ′ (v 0 )ℓ belongs to a cycle in P 5 , and we label the path P wrapping around this cycle.

Rule 2 -Easy extension

If P is an extension path with one endpoint of degree 1, Lemma 4 says that the unlabeled vertices of P are irrelevant -we delete them from G and continue with the reduced graph.

If neither Rule 1 nor Rule 2 can be applied, every unlabeled vertex that is adjacent to a labeled one has degree 2.

Rule 3 -Cheap extensions

(a) If P is an extension path with both endpoints labeled and of degree 2, we can decide by dynamic programming whether P has an L(2, 1)labeling compatible with the labeling of the labeled neighbors of its endpoints. In the affirmative case we just delete the unlabeled vertices and continue with the reduced graph, otherwise we reject the current f as allowing no extension.

(b) If P is an extension path with identical endpoints, we again decide by dynamic programming if the path has an L(2, 1)-labeling compatible with the label of the endpoint and its labeled neighbor. And we either reduce G or reject f , depending on the outcome. The dynamic programming consumes only time polynomial in the length of the path, and so does not affect the base of the exponential function bounding the running time. (To be honest, it only consumes constant time -it can be shown by case analysis that if the path is long enough, then any combination of labelings of its terminal edges is feasible, and so the dynamic programming is only applied to short paths of constant length.)

Rule 4 -Extensions with strong constraints

Let P be an extension path with both endpoints labeled, each with 0 or 4, such that each endpoint has only one labeled neighbor and at least one of them has another unlabeled neighbor that does not belong to P . In this case we branch along possible labelings of the (at most 4) unlabeled neighbors of the endpoints of P , while extending each of these labelings to entire P (by dynamic programming approach). Now we discuss the details of this branching rule and the consequences for the running time. The illustrative Figure 5 (a) will be helpful. Let b and c be the labeled endpoints of P , b of degree 3 and c of degree 2 or 3, and let a and d, respectively, be their labeled neighbors. Let further x and y be the unlabeled neighbors of b and c, respectively, on the path P , and let u = x be the other unlabeled neighbor of b; and let v = y be the other unlabeled neighbor of c, if it exists. Length 2. If the length of P is 2, then the label of x = y is uniquely determined (in fact, it has to be 2), and we do not really branch. Length 3. If the length of P is 3, we have the following possible labelings of ab..cd and their extensions to abxycd (up to the symmetric labeling

f ′ = 4 -f ): 40xy40 → 403140 40xy42 → 403142 40xy02 → 402402 40xy03 → 402403 20xy03 → 204203 20xy04 → 204204 20xy40 → 203140 20xy42 → 203142 30xy02 → 302402 30xy04 → 304204 30xy03 → 302403, 304203.
We see that most cases allow only one extension of the labeling to P , except for the last case, where branching into two cases occurs. If this happens, we gain at least three newly labeled vertices (x, y, u and possibly also v).

To analyze the running time of our algorithm we determine an upper bound on the maximum number T (n) of leaves in the search tree corresponding to an execution of the algorithm on an input with n unlabeled vertices. The overall running time will then be O * (T (n)) since the application of every rule takes only polynomial time and reduces the number of unlabeled vertices by at least one.

From our above analysis for Rule 4, we obtain two recurrences:

T (n) = 2T (n -3) (if c does not have another unlabeled neighbor v or if v = u) and T (n) = 2T (n -4) (if the neighbor v exists and is distinct from u). The solution of a recurrence T (n) = αT (n -β) is T (n) = Θ(c n ) for c = β √ α.
Here we obtain c = 3 √ 2 for the first recurrence and c = 4 √ 2 for the second one.

Length 4. The maximum number of possible extensions of the labelings of an extension path P of length 4 can be established from the exhaustive search trees in Figure 6 depicting all L(2, 1)-labelings. Table 1 summarizes the numbers of extensions and corresponding upper bounds for T (n) for extension paths of lengths 2 to 4.

Length at least 5. If the path is longer, we have two possible extensions of the labeling to the vertices x and u, and two extensions to y and v. For each of these 4 cases we check (in polynomial time, by dynamic programming as in Rule 3) if it extends to a labeling of P . If v exists and v = u, we gain length(P ) + 1 newly labeled vertices (the unlabeled vertices of P plus

INRIA length l of the path P maximum number of branchings t1 if deg(c) = 2 solution of the recurrence T (n) = t1T (n -l) maximum number of branchings t2 if deg(c) = 3 solution of the recurrence T (n) = t2T (n -l -1) 2 1 no branching 1 no branching 3 2 O(2 n 3 ) = O(1.2600 n ) 2 O(2 n 4 ) = O(1.1893 n ) 4 2 O(2 n 4 ) = O(1.1893 n ) 2 O(2 n 5 ) = O(1.1487 n )
Table 1: Branching on extension paths of length ≤ 4 with strong constraints.

u and v), which leads to the recurrences T (n) = 4T (nlength(P ) -1) and

T (n) = O(4 n 6 ) = O(1.2600 n ). If v
does not exist, it may seem to mind that we only gain length(P ) newly labeled vertices at the same cost of branching. However, in this case we only consider two possible labelings of the pair x and u, and for each of them we only check if it extends to a labeling of P or not. The actual label of y is irrelevant since c has degree 2 in this case. This leads to the recurrences T (n) = 2T (nlength(P )) and

T (n) = O(2 n 5 ) = O(1.1487 n ). If v = u,
then u would be treated by Rule 1 since u is adjacent to c and in that case c has degree 3. Thus v = u is not possible when applying Rule 4.

Comparing all cases we see that the worst case is achieved when deg(c) = 2 and length(P ) = 3. Thus using any branching of Rule 4 leads to T (n) = O(1.2600 n ).

If none of Rules 1-4 can be applied, then every unlabeled vertex that is adjacent to a labeled one belongs to an extension path with one unlabeled endpoint of degree 3. This is treated by the last branching rule.

Rule 5 -Extensions with weak constraints

Let P be an extension path with one unlabeled endpoint v of degree 3. Let w be the neighbor of v in P , let the labeled endpoint of P be b, let its labeled neighbor be a and let u be (if it exists) the unlabeled neighbor of b not belonging to P (see Figure 5 (b)). In this case we branch along possible labelings of v, w and (possibly) u, while extending each of these labelings to entire P (by dynamic programming).

Table 2 summarizes the numbers of branchings for paths of length at most 8 (these numbers can be established from the exhaustive search trees of Figure 7 giving all such possible L(2, 1)-labelings). Again, when deg(b) = 2, we only count the number of labelings of v and w that extend to a labeling of P compatible with the labeling of a and b, since the actual label used on the neighbor of b in P is irrelevant. On the other hand, when deg(b) = 3, we count the number of labelings of v, w and u that allow an extension to Proof. Let G = (V, E) be a graph with a partial labeling f . We consider the measure µ µ(G, f ) for analyzing running time of the algorithm presented 3. The analysis of the running time is quite similar to the one provided in Section 3, but since the measure involves the use of different weights (i.e., ǫ or 1) depending on the status -labeled or unlabeled -of the vertices in their neighborhoods, we obtain new recurrences. To simplify the notation, given a vertex v we denote by w(v) the weight of v. Namely w(v) = 1 for each unlabeled vertex v with no labeled neighbor, w(v) = ǫ for each unlabeled vertex v with a labeled neighbor and w(v) = 0 for each labeled vertex v. Thus summing over all vertices of G the equality µ(G, f ) = v∈V w(v) holds.

Rules 1, 2 and 3. The application of Rules 1, 2 and 3 needs only a polynomial time and cannot increase the measure µ.

Rule 4 -Extensions with strong constraints. We consider an extension path P with both endpoints labeled and we branch on the possible labelings of the unlabeled neighbors of the endpoints of P (see Section 3 and Figure 8 (a)).

Recall that by application of Rule 1 and Rule 2, the degrees of u and v (if it exists) are precisely 2. Let u ′ be the unlabeled neighbor of u. The weight w(u ′ ) can be either equal to 1 or equal to ǫ. We distinguish two cases: If w(u ′ ) = 1, labeling u would decrease the weight of u ′ to ǫ.

If w(u ′ ) = ǫ then denote by u ′′ a labeled neighbor of u ′ . Due to Rule 1, it follows that u ′ has degree 2 and thus labeling u would create an extension path P ′ = uu ′ u ′′ of length two (u ′ is the unlabeled vertex of P ′ ) that can be labeled without any branching by Rule 4 (see analysis of Rule 4 in Section 3). Thus, labeling u would decrease the weight of u ′ to 0.

If v exists, we can assume that u and v are different since otherwise if u = v, Rule 1 (d) would label u. However, in the case that v exists it is possible that u ′ = v. Consequently, labeling the path P and the vertices u and v would decrease the measure by at least (2ǫ + (length(P ) -3) + 2ǫ) if v exists, and by at least (2ǫ + (length(P ) -3) + ǫ + min(1ǫ, ǫ)) otherwise.

INRIA

Rule 5 -Extensions with weak constraints. We consider an extension path P with one unlabeled endpoint of degree 3 and we branch on the possible labelings of v, w and (possibly) u (see Section 3 and Figure 8 (b)).

Let v 1 and v 2 be the two neighbors of v which do not belong to P . Note that due to Rule 1 (d), neither v 1 nor v 2 are labeled or adjacent to a labeled vertex.

If u exists, we can assume that u and v i , i ∈ {1, 2}, are different since otherwise if u = v i , Rule 1 would label u. Thus, labeling the path P and the vertex u would decrease the by at least (ǫ+(length(P )-1)+2-2ǫ+ǫ) if u exists, and at least (ǫ + (length(P ) -2 -2ǫ) otherwise.

Setting ǫ = 0.8190 and solving the corresponding recurrences we establish a running time bounded by O(1.3006 n ).

It is an interesting question whether a more clever choice of the measure can lead to a more significant improvement of the upper bound on the worstcase running time of the algorithm.

A lower bound

It is often the case for branching algorithms that the best known running time is overestimated, even when using the Measure & Conquer technique. Thus it is natural to ask for a lower bound on the worst-case running time. Such bounds give an idea about the (yet unknown) worst-case running time of the algorithm. In this section we prove the following: Theorem 7. The worst case running time of our branching algorithm to compute an L(2, 1)-labeling of span 4 is Ω 2 + √ 5 n 7

= Ω(1.2290 n ).

Proof. Consider the graph G l = (V l , E l ) defined as follows (see also Figure 5).

Let V l = {a, b} ∪ 1≤i≤l 1≤j≤6 {v i j } ∪ 1≤i≤l {x i }. For every i, 1 ≤ i ≤ l, let E i = {v i 1 , v i 2 }, {v i 2 , v i 3 }, {v i 3 , v i 4 }, {v i 4 , v i 5 }, {v i 5 , v i 6 }, {v i 6 , x i }. The set of edges E l is defined as {a, b} ∪ {b, v 1 } ∪ 1≤i≤l E i ∪ 1≤i<l {v i 6 , v i+1 1 }.
Given an integer i, the subgraph induced by 1≤j≤6 {v i j } ∪ 1≤i≤l {x i } is called the i-th component of G l . For i > 1, we denote by P i the path induced by the vertices {v i-1 6 } ∪ 1≤j≤6 {v i j }. Note that the graph G l contains 7l + 2 vertices.

Consider an execution of the algorithm on the graph G l . Recall that, as a preliminary step, the algorithm has to label two adjacent vertices in all possible ways. Suppose that a and b have been labeled such that b receives label 0 or 4. It is not hard to check that none of the rules 1 to 3 can be applied on the resulting (partially labeled) graph. Moreover, there is no extension path with both endpoints labeled. Thus Rule 4 cannot be applied. Hence the algorithm applies Rule 5 to the extension path Table 3: Number of branchings for an extension path of length 6 using Rule 5, depending on the labels of a and b. These numbers are established using the search trees of Figure 7.

P 1 = {b, v 1 1 , v 1 2 , . . . , v 1 6 }. b a v 1 v 2 v 3 v 4 v 5 v
) possible values for (f (v 1 5 ), f (v 1 6 )) (2, 0) (3, 0) (4, 0) (0, 4) (1, 4) (2, 4
The idea is to try out all possible labelings on P 1 . More precisely, the algorithm branches along all possible labelings of v 1 5 and v 1 6 and extends these labelings to the other unlabeled vertices of P 1 . Then, by application of Rule 2, the vertex x is removed from the graph (according to Lemma 4, its label is easily obtained from a labeling of the remaining graph). The maximum number of branchings along the extension path P 1 having length 6 is given by Table 2, i.e. 5. However, depending on the label of a and b, this number can be even smaller. Table 3 gives the exact number of branchings, depending on the label of a and b.

Note that once P 1 is labeled, then x is removed, v 1 5 and v 1 6 are labeled, and v 1 6 has label 0 or 4. Thus, we can reuse the same arguments as before by renaming v 1 5 by a and v 1 6 by b, and considering the extension path P 2 from the second component. Finally, the whole graph G l is labeled by labeling component by component using Rule 5.

According to Table 3, the number of branchings is either 4 or 5, depending on the labels of a and b. To analyze the running time of the algorithm on G l , we denote by T 4 (n) the maximum number of leaves in the search tree obtained from an execution of the algorithm on a graph G l with n unlabeled vertices, providing that the first two vertices (e.g. a and b during the first step, v i 5 and v i 6 , 1 ≤ i < l, at the (i + 1)-th step) are labeled by (2, 0), (4, 0), (0, 4) or [START_REF] Chang | The L(2, 1)-labeling problem on graphs[END_REF][START_REF] Fiala | Fixed-parameter complexity of λ-labelings[END_REF]. Similarly, we define T 5 (n) as the maximum number of leaves in the search tree obtained by applying the algorithm on a graph G l with n unlabeled vertices, providing that the first two vertices are labeled by [START_REF] Fiala | Distance Constrained Labelings of Graphs of Bounded Treewidth[END_REF]0) or [START_REF] Bodlaender | Approximations for lambda-Colorings of Graphs[END_REF][START_REF] Fiala | Fixed-parameter complexity of λ-labelings[END_REF]. Consequently, for all n ≥ 1, T 5 (n) ≥ T 4 (n). If an unlabeled vertex u has at least two labeled neighbors, branch along all possible labelings of u.

(e) If an unlabeled vertex u has a labeled neighbor and two unlabeled neighbors v, w, branch along all possible labelings of u, v, w.

The configurations corresponding to these forced extensions are depicted in Figure 10. If Rule 1 cannot be applied, every labeled vertex that has an unlabeled neighbor has degree two, is labeled 0 or k, and has exactly one unlabeled neighbor. This unlabeled neighbor has only one labeled neighbor and has degree at most two, and so it belongs to an extension path consisting of unlabeled vertices of degree 2, ending either in an unlabeled vertex of degree 1 or at least 3, or in a labeled vertex of degree 2. These extension paths are treated similarly as in the algorithm of Section 3.

Rule 2 -Cheap extensions

Rule 3 -extension path branching

If an extension path ends with an unlabeled vertex u of degree at least 3, then all neighbors of u are unlabeled (otherwise Rule 1.5 would be applied). Let x be the degree 2 neighbor of u on the extension path and let y, z be two of the other neighbors. Branch along all possible labelings of u, x, y, z and for each such labeling check by dynamic programming if it is compatible with the labeling of the initial segment of the extension path.

Figure 12: Extension path branching. An extension path with one unlabeled endpoint u of degree at least 3 and no labeled neighbor.

We use the simple weight function -labeled vertices get weight zero, unlabeled vertices get label 1. The total weight in the beginning is n. Application of Rule 2 does not involve branching, does not increase the total weight, and consumes only polynomial amount of time.

Rule 1 (a). As v is labeled in [1..k -1] it forbids 3 labels for u and each of it already labeled neighbours (there is at least one) forbids another label. Hence there are at most k -3 possible labels for vertex u. This leads to recurrence T (n) ≤ (k -3)T (n -1).

Rule 1 (b). Now v forbids at least 2 labels (with equlity if it is labeled 0 or k) and each of its already labeled neighbours (there are at least two) forbids another label. Hence again there are at most k -3 possible labels for u.

Rule 1 (c).

There are at most k -2 possible labels for u and after u is labeled, at most k -3 possible labels are left for w. Hence we gain 2 labeled vertices and have (k -2)(k -3) < (k -2.5) 2 possibilities. This leads to T (n) ≤ (k -2.5) 2 T (n -2).

Rule 1 (d).

As the two labeled neighbors of u have different labels, together they forbid at least 4 labels for u. Hence T (n) ≤ (k-3)T (n-1).

Rule 1 (e). This case needs a slightly more careful analysis. Suppose the labeled neighbor of u is labeled by 0. Then u cannot be labeled 0 nor 1. If it is labeled by any i ∈ [2..k -1], we have k -3 possible labels for v (label 0 is blocked) and consequently k -4 possible labels for w. This gives (k -2)(k -3)(k -4) possible labelings. If u is labeled by k, we get k -2 possible labels for v and k -3 for w. So the overall number of possibilities is (k -2)(k -3)(k -4) + (k -2)(k -3) which is smaller than (k -2.5) 3 for k ≥ 5, while we are gaining 3 newly labeled vertices.

Rule 3. Suppose the extension path is abu 1 u 2 . . . u t-1 u, where a, b are labeled (b with label 0), u 1 , . . . , u t-1 are unlabeled vertices of degree 2, u is an unlabeled vertex of degree at least 3, and y, z are other two unlabeled neighbors of u. We may assume t ≥ 2, since the case t = 1 is actually Rule 1 (e). If t = 2, we lead the case analysis according to the label which is assigned to u. If u is labeled in [1..k -1], we have at most k -2 possible labels for x = u 1 , then k -3 labels for y and k -4 labels for z. If u is labeled by k, we get k -3 possible labels for x = u 1 , k -2 labels for y and k -3 labels for z. Altogether there are at most (k -1)(k -2)(k -3)(k -4) + (k -3)(k -2)(k -3) possibilities for labeling the four vertices u 1 , u 2 , y, z. This number is less than (k -2.5) 4 for k ≥ 5. If t > 2, we either label u with 0 or k, and get (k -1)(k -2)(k -3) possibilities for labeling x, y, z for each of the two. Or u get label i ∈ [1..k -1], and for each of these k -1 cases, we have (k -2)(k -3)(k -4) possibilities for x, y, z. Altogether we have 2

(k -1)(k -2)(k -3) + (k -1)(k -2)(k -3)(k -
4) possible labelings for u, x, y, z, and this number is less than (k -2.5) 5 for k ≥ 5. For each of the labelings of u, x, y, z, we check by dynamic programming along the extension path if the labeling is compatible with the labeling of a and b. So we are gaining at least 5 newly labeled vertices.

We have seen that the application of every rule leads to recurrence T (n) ≤ (k -2.5) ℓ T (nℓ) for some ℓ. Hence the number of leaves of the recursion tree is at most O((k -2.5) n ).

INRIA

For every pair of disjoint sets X and Y , X allows a partial labeling of span 0 such that all vertices of X in N (Y ) have labels at most -1 if and only if N (Y ) ∩ X = ∅ and X induces a 2-packing in G. Hence the initialization of Lab[X, Y, 0]. Let X and Y be disjoint sets of vertices and let i > 0. Suppose f is an L(2, 1)-labeling on X of span i such that f (u) ≤ i -1 for every u ∈ N (Y ) ∩ X. Let U ⊆ X be the set of vertices of label exactly i, and A = X \ U . Then U must be a 2-packing in G and N (Y ) ∩ U = ∅. Moreover, every labeled neighbor of a vertex from U must have a label at most i -2. Thus the labeling f restricted to A satisfies the requirements for A, U, and i -1 and Lab[A, U, i -1] should be true. On the other hand, extending a partial labeling of A of span i -1 to a labeling of X by setting f (u) = i for all u ∈ U gives a labeling satisfying our requirements, provided N (Y ) ∩ U = ∅. This justifies the computation of Lab[X, Y, i] by dynamic programming.

To analyze the running time of our algorithm, the crucial point is the estimation of the number of 2-packings in a connected graph. Let u k be the number of 2-packings of size k in our graph G. For every 2-packing U of size k, we process all pairs of disjoint subsets A, Y of V (G) \ U . Since every vertex of V (G) \ U has 3 possibilities where to end up (either in A, or in Y , or in neither of them), there are 3 n-k such pairs. Thus the running time of our algorithm is

O * n k=0 u k 3 n-k .
We emphasize that the proof of our estimate is constructive and itself leads to an algorithm enumerating all 2-packings of size k of a connected graph with running time O * n/2 k 2 k .

Lemma 10. If n is even, we have u k ≤ n/2 k 2 k (and, in particular, u k = 0 for k > n 2 ).

Proof. We partition the vertex set of G into r stars with a 1 , a 2 , . . . , a r vertices, so that a 1 + a 2 + • • • + a r = n and a i ≥ 2 for every i. Hence r ≤ n 2 . To obtain such partition, we consider a spanning tree T of G. Let u and v be, respectively, the endvertex and its neighbor on a longest path in T . All neighbors of v, with possibly one exception, are leaves in T . These leaves include u and with v they form a star with at least 2 vertices. Deleting it, we get a smaller tree T ′ which we treat in the same way. This procedure terminates with an empty tree and produces the required partition of vertices into stars of size at least 2 each.

INRIA Each 2-packing can have at most one vertex in each star, and so

u k ≤ 1≤i 1 <i 2 <•••<i k ≤r a i 1 a i 2 . . . a i k .
We obtain an upper bound on u k by maximizing this sum under the condition that the numbers a 1 , a 2 , . . . , a r are integers summing up to n and each of them is at least 2. I.e., for the purpose of the estimate, we forget about the underlying graph and regard a i as free integer variables; their number r varies as well.

It is easy to show that for a i ≥ 4, the above sum does not decrease when a i is replaced with two new numbers a ′ i = 2 and a ′′ i = a i -2. To see this, let us denote g k (A) = 1≤i 1 <i 2 <•••<i k ≤r a i 1 a i 2 . . . a i k for A = {a 1 , a 2 , . . . , a r }. Let A = A \ {a i } and A ′ = {2, a i -2} ∪ A. Then

g k (A ′ ) = 2(a i -2)g k-2 ( A) + 2g k-1 ( A) + (a i -2)g k-1 ( A) + g k ( A) ≥ a i g k-1 ( A) + g k ( A) = g k (A).
Similarly, it does not decrease when two numbers a i , both equal to 3, are replaced with three new numbers, all equal to 2. As n is even, it follows that the maximum of the above sum under the stated condition is attained for a 1 = a 2 = • • • = a r = 2, r = n/2. (If k ≥ 2, the sum strictly increases after the replacements and therefore this is the only choice with maximum sum.) The claim of the lemma follows.

A simple calculation now concludes the proof of Theorem 9 for even n:

Figure 1 :

 1 Figure 1: (a) The graph H = P 5 . (b) A graph G with an L(2, 1)-labeling of span 4 as a locally injective homomorphism into H.

Figure 2 :

 2 Figure 2: Forced extensions.

Figure 3 :

 3 Figure 3: Easy extension. An extension path with one unlabeled endpoint of degree 1.

Figure 4 :

 4 Figure 4: Cheap extensions. (a) An extension path with both endpoints labeled and of degree 2. (b) An extension path with identical endpoints.

INRIA

Figure 5 :

 5 Figure 5: Extensions with strong (a) and weak (b) constraints.

Figure 6 :

 6 Figure 6: The figures depict all possible L(2, 1)-labelings of a path starting with labeled vertices a and b and ending with labeled vertices c and d. Recall that the only possible labels of b and c are 0 or 4 when Rule 4 is applied. For example, if f (a) = 2, f (b) = 0, f (c) = 0 and f (d) = 2, the first tree shows that there are two possible labelings of a path abxyzcd : 2031402 and 2041302.

Figure 7 :

 7 Figure 7: The trees depict all possible L(2, 1)-labelings of extension paths of length 8 (the root edge corresponds to first two labeled vertices).

Figure 8 :Theorem 6 .

 86 Figure 8: Extensions with strong (a) and weak (b) constraints.

Figure 9 :

 9 Figure 9: The graph G l used to prove the lower bound.

  values of (f (a), f (b))

INRIA ( b )

 b If a labeled vertex v has at least two labeled neighbors and an unlabeled neighbor u, branch along all possible labelings of u.(c) If a labeled vertex v has two unlabeled neighbors u and w, branch along all possible labelings of u and w.

Figure 10 :

 10 Figure 10: Simple branchings.

( a )INRIAFigure 11 :

 a11 Figure 11: Cheap extensions. (a) An extension path with one unlabeled endpoint of degree 1. (b) An extension path with both endpoints labeled and of degree 2.

2 k

 2 3 n/2-k = 3 n/2 (2 + 3) n/2 = 15 n/2 = ( √ 15) n .For odd n we note that the number of 2-packings in G is obviously smaller than the number of 2-packings in a graph G ′ obtained by adding a vertex to G. Then the running time is bounded byO * (( √ 15) n+1 ) = O * (( √ 15) n ) = O(3.8730 n ).

RR n 6587

Here we use the so called O * notation:f (n) = O * (g(n)) if f (n) ≤ p(n) • g(n) for some polynomial p(n).INRIA

Partially supported by the european project FET-AEOLUS. Supported by Research grant 1M0545 of the Czech Ministry of Education.

Table 2: Branching on extension paths of length ≤ 8 with weak constraints.

a labeling of P compatible with the labels of a and b. Note that in either case both v and b may only receive labels 0 or 4.

In the case of a longer path, we have at most 6 possible labelings of v and w, yielding the recurrence

, we have at most 12 possible labelings of v, w and u, yielding the recurrence T (n) = 12T (nlength(P ) -1).

Since 9 √ 6 < 4 √ 3 and 10 √ 12 < 4 √ 3, the overall worst case for Rule 5 is achieved when b is a degree 2 vertex and the extension path has length 5. Hence

Summarizing the analysis of the algorithm, we obtain the following.

Theorem 5. The existence of an L(2, 1)-labeling of span 4 can be decided in time O * (1.3161 n ). If such a labeling exists it can be computed within the same time.

A refined time analysis

In this section, we report on an attempt to improve upon the upper bound of O * (1.3161 n ) for the running time of our algorithm. To do this we use a Measure & Conquer approach (see e.g. [START_REF] Fomin | Measure and conquer: Domination -A case study[END_REF]). To each graph G with a partial labeling f we assign the following measure

where ñ is the number of unlabeled vertices with no labeled neighbor and n is the number of unlabeled vertices having a labeled neighbor. Furthermore, ǫ is a constant to be chosen later such that 0 ≤ ǫ ≤ 1.

This means that the weight of a vertex is 0 if it is already labeled, it is ǫ if it is unlabeled with a labeled neighbor, and it is 1 otherwise. Note that µ(G, f ) ≤ n, where n is the number of vertices of G.

INRIA

Recall that each time an extension path P i of G l is labeled, the whole path becomes labeled and the corresponding vertex x i is removed. Thus, the seven vertices are either labeled or removed from G l . Moreover, note that among the 4 or 5 branchings done for finding labeling of the extension path P i , exactly one ((3, 0) or (1, 4)) produces a branching in 5 labelings in the next step aiming to find a labeling of P i+1 (see Table 3). Thus, we obtain the following two recurrences:

Subtracting ( 1) from (2) yields T 5 (n) = T 4 (n) + T 4 (n -7). Together with (1) one obtains T 4 (n) = 4T 4 (n -7) + T 4 (n -14). Solving this latest recurrence, by substituting

Larger span

In this section we show that even in the case of larger span k we can beat k -2 as the base of the exponential function bounding the running time of our branching algorithm. Unlike the case of k = 4, we do not aim at the very best running time achieved by complicated branching rules and a fine tuned analysis. Here we will be satisfied with an improvement of k -2 by an additive constant, and we rather aim at simple rules and running time analysis. We are aware that a more careful analysis would lead to a slightly better constant.

Theorem 8. Deciding if an input graph allows an L(2, 1)-labeling of span k, for a fixed k ≥ 5, can be achieved in time O * ((k -2.5) n ) and polynomial space.

Proof. Note first that in the case of span k, the label space [0..k] contains two labels, namely 0 and k, that allow k -1 labels on adjacent vertices, while the other k -1 labels from [1..k -1] allow only k -2 labels on adjacent vertices.

Our algorithm is similar to the algorithm from Section 3. Again, we start by labeling a chosen vertex in all possible ways, then label a chosen neighbor in all possible ways, and since then on, we keep the labeled part of the input graph connected. In particular, every labeled vertex has at least one labeled neighbor. We use the following rules, and assume they are applied in the preference ordering as they are listed. (See also Figures 10,[START_REF] Griggs | Labelling graphs with a condition at distance 2[END_REF] 7 An exact dynamic programming algorithm for L(2, 1)-labeling

Král [START_REF] Král | Channel assignment problem with variable weights[END_REF] shows that the channel assignment problem can be solved in time O * (4 n ) if the maximum edge weight is 2. Hence the minimum L 2,1 -span of a graph can be computed in this time. The purpose of this section is to show that in the case of L(2, 1)-labelings, we can beat the constant 4 in the base of the exponential function expressing the running time.

Theorem 9. The L(2, 1)-labeling problem can be solved in time O * (15

Proof. Let G = (V, E) be a graph. For every integer i ∈ {0, 1, . . . , 2n} and for all subsets X, Y ⊆ V such that X ∩ Y = ∅, we introduce a Boolean variable Lab[X, Y, i]. By Dynamic Programming we determine the values of these variables so that Lab[X, Y, i] is true if and only if there exists a partial L(2, 1)-labeling L of span i for X, L : X → {0, 1, . . . , i}, such that each vertex of N (Y ) ∩ X has label at most i -1.

is smaller than 2n, since labeling the vertices by distinct even integers is always a valid L(2, 1)-labeling.)


Dr Eugénie Fournier

Dr Sybille Tachon

Dr Nicholas J Fowler

Dr Guillaume Gerbaud

Dr Pascal Mansuelle

Dr Pierre Dorlet

Dr Sam P De Visser
email: sam.devisser@manchester.ac.uk

Valérie Belle

Dr A Jalila Simaan

Dr Marlène Martinho
email: marlene.martinho@univ-amu.fr

] A Jalila Simaan

Prof. V Belle

The Hunt for the Closed Conformation of the Fruit-Ripening Enzyme 1-Aminocyclopropane-1-carboxylic Oxidase: A Combined Electron Paramagnetic Resonance and Molecular Dynamics Study

Keywords: Enzyme structure and dynamics, ethylene, Molecular Dynamics, Electron paramagnetic resonance, ACC Oxidase, paramagnetic labelling

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

Introduction

The simplest unsaturated hydrocarbon, ethylene, is an essential plant hormone involved in a wide range of physiological and development processes that ranges from vegetative growth, climacteric fruits ripening, root development to mediation of stress responses. [1] 1-amino-cyclopropane-1-carboxylic oxidase (ACCO) is a non-heme iron(II) enzyme that is responsible for the last step of ethylene biosynthesis in plants. The substrate, 1aminocyclopropane-1-carboxylic acid (ACC) is transformed into ethylene by ACCO through a two-electron oxidation with cyanide and carbon dioxide as by-products (Scheme 1). [2][3][4][START_REF] Simaan | 2-Oxoglutarate-Dependent Oxygenases[END_REF] The reaction requires ascorbate (as electron donor) and dioxygen. Carbon dioxide (or bicarbonate) is also known to be essential to the reaction, although its function has yet to be determined. [START_REF] Smith | [END_REF][START_REF] Zhou | [END_REF][8] ACCO is, therefore, a complex enzymatic system that requires many cofactors and co-substrates to function and for which the mode of action is not well understood. Scheme 1. Chemical reaction of ACC into ethylene catalyzed by ACCO Knowledge about the structure and the dynamics of a protein is essential for understanding its mechanism and biological function. Currently, there are remaining questions on the active structure of ACCO. The first crystal structure of ACCO was reported for Petunia hybrida ACCO (PhACO1). [9] The structure revealed a core folded in a double-stranded-b-helix (DSBH) or b-barrel, surrounded by a-helices (Figure 1). The active site Fe(II) ion is coordinated by the side chains of H177, H234 and D179 in a 2histidine 1-carboxylate facial triad, a classical motif highly conserved among non-heme Fe(II)-dependent enzymes. [10] Although active as a monomer, PhACO1 has been crystallized as a homotetramer with the C-terminal part interlocking with the Cterminal part of an adjacent monomer by means of both hydrophobic and electrostatic interactions. The C-terminal part is therefore positioned away from the active site, leaving it rather accessible. Hence, we will refer to this crystal structure as the "open" conformation of ACCO (Figure 1A). It has been shown that the C-terminal region is essential for the enzymatic activity and C-terminal truncated enzymes are poorly active. [9,11] In addition, several residues of this part of the enzyme (e.g. K297 and R300) are important for cofactor's binding. [9,12,13] As such, it has been suggested that the open conformation does not represent an active conformation of the enzyme. Taking these findings into account, structural models of ACCO from apple and then from tomato have been constructed with the C-terminal part folded towards the protein core in a "closed" conformation (Figure 1B). [13,14] Figure 1. A) X-ray structure of ACCO from P. hybrida (pdb code 1WA6) or "open" conformation and B) modelled structure of ACCO from tomato or "closed" conformation. [14] The C-terminal region starting at residue V281 is highlighted in red, the residues that will be used to anchor spin labels are highlighted in yellow and the iron ion is represented as an orange sphere; C) labelling reaction of cysteine residues with proxyl (P).

Very recently, two structures of Zn-reconstituted ACCO from Arabidopsis thaliana (AtACO2) have been reported in which the enzyme is found monomeric. [15] For the main part, the structures are highly similar to that of PhACO1 with the Zn(II) ion bound to the facial triad, in place of the native iron ion. One main difference lies in the C-terminal part that adopts an intermediate conformation between the above-mentioned "open" and "closed" ones. It is however important to note that AtACO2 has been crystallized in a C-terminal truncated form (303 amino acids over 320 full length). The lack of the extremity of the C-terminal part may have an influence on both the conformation and the activity of the enzyme. [9,11] Overall, these structural differences might reflect a flexibility of the C-terminus possibly important for the activity of ACCO enzymes.

Site-directed spin-labelling (SDSL) followed by Electron Paramagnetic Resonance (EPR) spectroscopy has emerged as a powerful tool to probe conformation and dynamics of proteins. [16- 19] This technique relies on the covalent insertion of one (or several) stable paramagnetic probe(s) at a selected site of a protein, often a cysteine residue introduced by site-directed mutagenesis. SDSL-EPR allows to probe the micro-environment of the spin label at the residue level or to measure inter-label distances in the range of typically 1.8 -8.0 nm using pulsed-EPR techniques such as Double Electron-Electron Resonance (DEER) experiment (distances up to 16 nm have now been reported when full deuteration of the protein sample is achieved). [20,21] Given their relatively low abundance in protein sequences and their well-mastered chemical reactivity, cysteine residues are often used for chemical modification of proteins. [22,23] We have chosen to introduce a nitroxide radical (3-maleimido-2,2,5,5tetramethyl-1-pyrrolidinyloxy or proxyl (P)) on cysteine residues of ACCO (Figure 1C). Tomato ACCO contains four cysteine residues (C28, C60, C133 and C165) in the sequence that are located on the main core of the protein. In a previous study, we have reported on mutagenesis experiments to systematically replace native cysteines by other amino acids in order to reduce the number of cysteines for chemical modification. [11] We have also shown that several positions are suitable for the introduction of cysteines on the C-terminal part of the enzyme without losing activity (in particular L292C and M307C mutants were successfully produced and chemically modified). However, continuous-wave (cw) EPR spectra were found complex and not informative to monitor conformational changes upon addition of the different cofactors. We therefore directed our efforts towards inter-label distance measurements by pulsed-EPR techniques. In this manuscript we report on our combined experimental and computational studies to understand the conformation and dynamics of the C-terminal part of the enzyme. Based on our preliminary results, [11] we have generated variants displaying two accessible cysteines residues (one on the main core and one on the C-terminal part) and introduced a paramagnetic probe (P). DEER experiments were performed to measure inter-spin distance distributions under several conditions, and in particular

C60 L292 M307 A) B) SH N N O O O + S N N O O O C)
upon addition of cofactors. Molecular dynamic simulations were performed in order to bring complementary information. Both experimental and computational data reveal a flexibility of the Cterminal part of ACCO irrespective of the experimental conditions. Our studies highlight the combined use of SDSL-EPR with computational modelling as a useful tool for protein dynamics investigation.

Results and Discussion

Choice of the labelling positions.

In order to gain conformational information on the C-terminal region of the enzyme using distance distribution measurements by DEER, a pre-requisite lies in the generation of doubly modified enzymes bearing one spin label on the main core and one on the C-terminal part. ACCO from tomato contains four cysteines on the main core: C28, C60, C133 and C165. In a previous study, we have shown that only two of the existing native cysteines are accessible to the P label: C60 and C165. [11] We have then performed a complete mutagenesis study to provide proteins displaying unique modification sites on the main core while retaining their primary structure and function. Two mutants have been selected: C60Y and C165H. Chemical modification of the C60Y enzyme, i.e. introduction of a label on the C165 position (C165*; the notation * will be used all along the text referring to the presence of the label) led to a completely inactive enzyme. Thus the C165H variant, which remains active after labelling, appeared as the best candidate to introduce a label on the main core (C60*). We have also shown that introduction of a cysteine on the C-terminal region provided fully functional enzymes and two positions were selected (L292 and M307).

In order to verify that the above-mentioned positions are suitable for conformational studies, we used MMM software (Multiscale Modelling of Macromolecules), an open-source modelling toolbox that can compute distance distributions between spin labels attached to a protein having an available pdb description. [24] The P labels were introduced on cysteines at positions 60, 292 and 307 using either the "open" or "closed" conformations. The number of rotamers of P that each labelled variant can experience was calculated while the structure of the enzyme remained fixed (Figure 2A and Table S1). These rotamers were used to predict the inter-spin distance distributions between labels introduced at position C60-C292 or C60-C307. The calculated distance distributions for the open and closed conformations appear quite different (Figure 2B) and measuring C60*-C292* and C60*-C307* distances seems pertinent to discriminate the two conformations.

Mutagenesis and chemical modification with P

We have generated double mutants: C165H/L292C and C165H/M307C. The enzymes were expressed and purified according to previously reported procedures. [11,14,25] Labelling experiments were conducted using P spin label (Figure 1C) and the labelled enzymes were analysed by mass spectrometry (MS) to confirm the introduction of the two labels at the desired positions, namely C60*C292* and C60*C307* (Table S2). Far-UV CD spectra of native, double mutants and labelled enzymes were recorded to ensure that the mutations did not impact their global secondary structures (Figure S1). Specific activities of the unlabelled and labelled enzymes were measured by detection of the ethylene production (Figure 3). The double mutants display activities that range between 45 to 60 % compared to the native enzyme and between 60-70 % compared to the single C165H mutant. No significant effect of labelling was observed on the activity.

DEER experiments in absence of cofactors.

The experiments were first conducted on the enzymes in absence of substrates or cofactors. Q-band DEER traces and the resulting distance distributions are shown in Figures 4 and5. For the C60*C292* enzyme, a bimodal distance distribution was obtained with two maxima at 3.4 and 4.5 nm (Figure 4A and Figure S2). In the case of C60*C307*, the results gave a very broad distance distribution with a maximum centred at 4.1 nm, and a shoulder at 3.0 nm (Figure 5A and Figure S2). Noteworthy, the experimental distance distributions are very different from the ones predicted using MMM software for both mutants and conformations. These results suggest that the ACCO conformations derived from the crystal or modelled structures may not be the ones observed in solution. In addition, although two maxima are clearly present (Figure S2), the experimental distance distributions are broad and populate a range of distances higher than the MMM calculated ones. These results reveal that the C-terminal part of ACCO can probably adopt several conformations and suggest a flexibility of this region.

DEER experiments in presence of cofactors/substrates (ACC, HCO3 -and ascorbate) without dioxygen.

ACCO requires several substrates (ACC, O2 and ascorbate) and a cofactor (bicarbonate or CO2) to function. To date, few structural data have been reported on the binding of the different cofactors/substrates at the active site. Using EPR and ENDOR spectroscopies on a Fe(II)-NO complex (in which NO potentially binds on the iron in the place of O2), it has been shown that ACC binds to the Fe(II) ion in a bidentate fashion via the nitrogen of the amine and an oxygen of the carboxylate group. [25] Recently, an ACC bound structure of PhACO1 (in the tetrameric crystal form) reconstituted with Ni(II) has been released in which a bidentate binding mode of ACC on the Ni ion is observed (pdb 5TCV). Binding of other cofactors/substrates in the active pockets still remains under debate. Using modelling studies, it has been proposed that K297 and R300 from the C-terminal part, are involved in ascorbate and/or bicarbonate binding. [13,14] To examine whether binding of cofactors in the active site could influence the conformation of the C-terminal part, DEER experiments were performed on labelled ACCO mixed with successive addition of co-factors (ACC, HCO3 -and ascorbate).

The different distance distributions are shown in Figure 4 and 5 for the two labelled variants. Note that ascorbate is able to reduce nitroxides into hydroxylamine (EPR-silent) and was therefore added at the last moment. Despite this, in some cases, time traces recorded in presence of ascorbate display a lower modulation depth probably arising from a decrease of spin concentration due to partial reduction of the labels.

In the case of C60*C292* (Figure 4), no drastic change is observed with the distance distribution profiles, which remain overall similar to the one obtained without any cofactor. The long distance distribution centred at 4.5 nm is not modified upon substrates / cofactors addition. A small shift of the second maximum is however detected going from 3.4 nm (alone) to 3.1 nm upon addition of ACC and bicarbonate (Figure 4B and Figure S3). The distance distribution is not significantly modified upon further addition of ascorbate (Figure 4C). Furthermore, a change in the relative amplitudes of the two populations is observed, suggesting that the population at lower distance becomes less important. Note that a narrowing of the distributions is observed possibly suggesting that addition of cofactors leads to a selection of conformations that were already present.

In the case of the C60*C307* enzyme, the main distance distribution centred at 4.1 nm is not affected by the addition of cofactors (Figure 5B, 5C and Figure S3). The shoulder at 3.1 nm becomes broader and less defined in presence of cofactors. Note that distance distributions at larger values (≥ 6 nm) are not significant because located in high uncertainty region. Surprisingly, addition of ascorbate did not impact the modulation depth like in the previous case (Figure 5C) maybe reflecting a DEER experiments in presence of cofactors/substrates (ACC, HCO3 -and ascorbate) and dioxygen.

The samples were prepared anaerobically and then opened to air for 2 minutes. The DEER spectra were then recorded (Figure S4). For both mutants, the main distance distribution around 4 nm observed in the previous conditions remains unchanged. Several distributions appear at lower distances ranging from 2 to 4 nm. It has to be noted that different species can be generated upon catalytic turn-over rendering the fine interpretation of these data difficult. Overall, for both variants and in all conditions, the distance distributions remain very broad, suggesting that the Cterminal part of ACCO keeps its flexibility even in the presence of its cofactors.

Study of the core enzyme flexibility by pulsed EPR experiments

In order to get additional information on the dynamics of the protein and to find out whether the flexibility of the enzyme was limited to the C-terminal tail only or included the main body as well, we conducted two additional experiments to measure distances on the main body using pulsed-EPR experiments: (i) a nitroxidenitroxide distance and (ii) a metal-nitroxide distance. Firstly, we used the native enzyme that bears nitroxide labels on the C60 and C165 (60*165*). The data are presented in Figure S5. A single distance distribution is detected centred at 2.6 nm. Secondly, we used a copper(II)-reconstituted enzyme with the metal ion as a spectroscopic probe. We have indeed previously reported that Cu(II) binds at ACCO active site with an affinity similar to that of the native iron ion. [26] We thus reconstituted the singly C60* labelled enzyme with Cu(II) and used the RIDME sequence, a pulsed EPR particularly well-suited to determine distances between paramagnetic metal centres and radicals. [27] A main Cu-C60* distance distribution is found centred at 2.9 nm with a shoulder at 2.0 nm (Figure S6). In both cases, the distance distributions are less complex and large than the distributions measured with a label on the C-terminal part, which suggests that the main body is less dynamic than the C-terminal part. Using MMM software, the manually estimated distances between the metal and different conformers of the nitroxide range from 1.8 to 2.4 nm for the closed form and 2.1 to 2.5 nm for the open form. The RIDME data are thus in good enough agreement with the two forms. This confirms that the conformation of the main body is not affected by the flexibility of the C-term part of the protein.

Molecular Dynamics simulations on the 'open' and 'closed' forms.

To gain more insight into the conformational landscape of the Cterminal tail region of ACCO we performed molecular dynamics simulations of the C60*C292* and C60*C307* variants and started from both open and closed conformations. Model structures in an open conformation were created using the 1WA6 pdb structure with missing residues, hydrogen atoms, solvent and paramagnetic probes added as described in the Methods Section. Model structures in a closed conformation were created using the previously published model structure with missing hydrogen atoms, solvent, paramagnetic probes and cofactors added as specified below. [28] Three molecular dynamics simulations were performed for each variant for a total simulation time of 1.2 µs for open conformations and 0.6 µs for closed conformations respectively. Every 0.1 ns the distance between the O atoms of the two paramagnetic probes was measured in order to produce inter-spin distance distributions for comparison to the experimentally determined distributions.

The computed Fe-C60* distances are similar for the simulations starting from the open and closed forms (Figure S7) and are found centred around 2.3-2.4 nm. These distances are in good agreement with the RIDME experiment. As mentioned above, this supports the fact that the main core of the protein is rather rigid and that no major differences are expected on this part while the C-terminal part varies.

In Figure 7, the computed inter-spin distance distribution for the open (green line) and closed (red line) form of C60*C292* is compared against the experimentally determined distributions without (solid black line) and with cofactors (dashed black line)

included. The open form recreates the broad range seen in experiment with maxima in a similar range to those reported above. Therefore, the MD simulations give a good representation of the experimental system and confirm that the C-terminal tail region of ACCO is indeed flexible. However, our calculations suggest that the separation of tagged Cysteines in the closed form appear at shorter distances of around 1.7 nm. Although when experiments are performed in the presence of co-factors, a distribution centred around 3 nm is detected, this distance is too long to match the computed distance for the closed form. This could mean that either the closed form is too tight or that this closed form was not actually observed in our experiments. Next, we computed the inter-spin distance distributions for the open and closed forms of C60*C307* to compare to the experimentally determined distributions (Figure 8). Again, we see that the broad range of tagged Cysteines distances are reasonably well captured in our simulations, but that in this instance the maxima do not match. This could highlight the need for more sampling due to the tag at C307 being located further towards the C-terminus where it will likely be more mobile in comparison to the tag at C292. In our experiments, the addition of cofactors resulted in a distribution to appear at 2 nm and an increase at 3 nm, which could represent an increase in population of the closed form ACCO. The simulations of the closed form do not give distances at 2 nm but a distance distribution with a range from 2.5 -4 nm. Although the presence of the closed form cannot be excluded, it seems difficult to conclude on its presence from the C60*C307* distance distributions. Overall, the distances between probes computed by our simulations of the open form of both ACCO variants agree rather well with experiment, whereas the distances between probes computed for the closed form do not match those observed experimentally. This suggests that either the closed form has not been observed in experiment or that our computational model of the closed form is too tightly closed. An alternative explanation could be proposed by considering the motion of the C-terminal region in our simulations (see movies of trajectories of open form provided in the Supporting Information). In all repeats of both variants we see that the C-terminal tail region is initially highly dynamic but that after some time it tends to "bind" to the protein surface and that, in the majority of cases, the a-helix at the Cterminus is oriented towards the iron(II) centre. It is therefore possible that ACCO does not close as tightly as suggested in previous models. This could explain why the C-terminal a-helix is important for activity but that the experimentally observed distances do not match those computed from a more tightly bound model.

Conclusions

Under our experimental conditions, no direct evidence of the "closed" conformation could be obtained and the closed form, as proposed by the modelled structures, is clearly not the major form present in solution. MD simulations have pointed out that, starting from the open conformation, the C-terminal part tends to "bind" to the protein surface in a conformation that is not as tightly closed as the proposed modelled structures. [13,14] Several reasons can be evoked to explain this observation: (i) the "closed" conformation does not exist or (ii) the "closed" conformation is only a transient form during the catalytic cycle that could not be detected under our experimental conditions. The latter hypothesis is supported by our MD simulations that indicated that the closed form is stable when the cofactors are present, maintained by electrostatic interactions (e.g. between ascorbate and/or bicarbonate with K or R residues from the C-terminal part). This conformation could still be formed under catalytic conditions. Further work is in progress in our laboratories to get further insight into the active conformation (other labelling positions, rapid kinetics, etc.).

The conformation adopted by the C-terminal part does no more correspond to the "open" form derived from crystallographic studies. [9] The wideness of distance distributions (and the fact that several maxima are detected) suggests that the C-terminal part of ACCO is dynamic and adopts different (or a range of) conformations. This is confirmed by our MD simulation that show that starting from the open conformation, the C-terminal part moves around the active site, maintaining distances between the probes at C60* and C202* or C307* ranging from 3-4 nm, consistent with experimental data. The existence of two conformations switching from one to the other one upon catalytic events has been proposed for several enzymatic systems. [29,30] However, this two conformations picture is probably a very simple view of enzymatic structure-function complexity. It is now admitted that proteins are dynamic entities that possess inherent flexibility, a fundamental property that allows them to function through molecular interactions with other molecules (either substrates, cofactors or proteic partners). In particular, the presence of a dynamic part adopting a broad range of conformational setpoints has been evidenced in several enzymatic systems (e.g. flavin reductases). [31,32] These findings hence raise questions on the exact function of such flexibility on ACCO enzymatic activity.

Experimental Section

Chemicals

Unless otherwise noted, all chemicals and solvents were of analytical grade and used without further purification.

Mutagenesis

ACCO wild-type and variant were constructed from a PET21a (Novagen) plasmid containing the ACCO gene (pTOM13) from Lycopersicum esculentum. [33] C165H mutant was previously reported. [11] Site-directed mutations of the ACCO C165H encoding gene were performed by PCR using the already described primers to generate the double mutants C165H_L292C and C165H_M307C. The PCR reactions were performed following our previously described procedure. [11]

Overexpression and purification of recombinant apo Lycopersicum esculentum ACCO proteins

Plasmids encoding for ACCO wild-type and variants were transformed into thermocompetent BL21 (DE3) Escherichia coli cells. Transformants were then subcultured in LB medium containing ampicillin at 37°C (200 rpm) to reach an optical density at 600 nm (OD600) of 0.5. Cells were diluted to 0.05 and grown at 37°C in Terrific Broth medium to an OD600=1 before induction with 0.5 mM isopropyl-β-D-thiogalactopyranoside (IPTG) at 28°C during 4 h. Cultures were then harvested by centrifugation at 4°C (Sorvall Lynx 6000, Thermo Scientific) and kept at -20°C. Purification steps were performed at 4°C using the Akta Purifier FPLC System (GE Healthcare). Thawed cell pellets were resuspended in lysis buffer containing 1 X BugBuster (Merck Millipore), 10% glycerol, 3 mM EDTA, 5 mM dithiothreitol (DTT) and 1 mM benzamidine, during 30 min under gentle agitation. Cell debris were removed by centrifugation at 18000 g for 45 min.

The supernatant was dialyzed in dialysis tubing (Spectra/por, Spectrumlabs) of 12-14 kD MWCO against buffer A overnight (buffer A: 25 mM 4-(2-hydroxyethyl)-1-piperazineethanesulfonic acid (HEPES) pH 8.0, 10% glycerol, 3 mM EDTA, 1 m benzamidine, 5 mM DTT). Dialyzed ACCO was loaded on a Q Sepharose resin (Fast Flow Q Sepharose, GE Healthcare) and was eluted with gradient buffer A containing 150 mM NaCl. The fractions containing 90-95% pure ACCO (according to SDS-PAGE analysis) were pooled, dialyzed against 25 mM HEPES pH 7.2, 10% glycerol, and concentrated in a Vivaspin 2, 10 kD MWCO, using a polyethersulfone membrane (Sigma-Aldrich).

Preparation of holo ACCO proteins

As ACCO was purified as an apo-protein, 0.9 equivalent Fe(SO4)2(NH4)2.6H2O was anaerobically added to a solution of ACCOs to obtain the holo-proteins. All experiments have been performed on the holoproteins, unless otherwise stated.

ACCO activity assays

The activity of ACCO was investigated at 29°C in 1.7 mL hermetically sealed vials. The total assay volume was 200 µL of the standard reaction mixture containing 25 mM HEPES at pH 7.5 and 10% glycerol, 5 µg of apo-ACCO, 18 mM NaHCO3, 1.25 mM ACC, 8 mM L-ascorbic acid and 40 µM Fe(SO4)2(NH4)2.6H2O. After 7 min of incubation at 29°C with gentle shaking, 1 mL of the ethylene produced was withdrawn from the headspace by a gas-tight syringe and injected onto a gas chromatograph (Shimadzu GC-2014A equipped with a Poropak Q 80/100 column).

Ethylene was quantified with an external standard (1% ethylene in nitrogen, Scott Mini-Mix, Air Liquide). The specific activity is expressed as the quantity of ethylene produced per minute and per mg of enzyme.

Circular dichroism (CD) spectroscopy

CD spectra were recorded on a Jasco J-815 spectrometer at room temperature with the use of 0.1 cm path-length cells in 10 mM sodium phosphate at pH 7.5. The acquisition was performed from 190 to 250 nm at 20 nm min -1 (10 scans). Protein concentration was in the range of 3 -10 µM. The mean ellipticity values per residue ([q]mrw,l) were calculated as described before. [34] Spin-labelling procedure

The labelling experiments were performed on the apo-proteins placed in deuterated MOPS 50 mM pH 7.5 and in an ice bath. The proteins (wt and mutants) obtained after purification and concentration were labelled with 3-maleimido-2,2,5,5-tetramethyl-1-pyrrolidinyloxy (Sigma Aldrich) spin label, Proxyl, referred to as P. 100 molar equivalent of DTT were first added to the protein (protein concentration below 250 µM to avoid precipitation) to allow reduction of the cysteines. The mixture was then incubated 20 min in ice. The excess of DTT was removed using a gel filtration desalting PD-10 column (GE Healthcare). The fractions containing the protein (checked by OD280) were pooled. Four additions of 10 equivalents P (from 32 mM stock solution in acetonitrile), spaced by 30 min, were performed. Excess of free spin labels was removed using a second desalting PD-10 column. The fractions containing the labelled ACCO were checked by cw EPR at room temperature, pooled and concentrated using Vivaspin 2 (Sartorius), 10 kD MWCO to reach a concentration of ~ 9 mg ACCO / mL. The spin-labelled enzymes were stored at -20 °C.

Inter-spin distance predictions using MMM

The prediction of inter-spin distances of labelled protein was performed with Multiscale Modelling of Macromolecules (MMM) 2017 software from a selected set of label rotamers. [24] The resulting computational rotamers were used to obtain a prediction of the distance distributions between spinpairs by calculated dipolar evolution echo traces of DEER experiments. Predictions were done using the crystal and model structures for the "open" and "closed" conformations.

Mass spectrometry

Global

DEER and RIDME experiments

To get better sensitivity and higher-quality distance distributions the proteins were placed in MOPS buffer pH 7 prepared in D2O. [35] The final protein concentrations ranged from 80 to 100 µM. Glycerol-[D8] (30 % v/v) was added to the samples before rapid freezing to avoid heterogeneous protein concentration. Co-substrates and cofactors were added anaerobically in a glove box (<2 ppm O2) at the following concentrations: ACC 5 mM, HCO3 -25 mM and ascorbate 0.1 mM. For Cu(II)-reconstituted enzyme, 0.9 equivalent of Cu(II) from a solution of 10 mM CuSO4 was added to the apo-enzyme solution.

Q-band pulsed EPR experiments were performed on an Elexsys E580 spectrometer (Bruker) using the EN 5107D2 resonator and equipped with an Oxford helium cryostat temperature regulation unit. The data were recorded at a temperature of 60 K for DEER and 20K for RIDME experiments. For nitroxide-nitroxide distance measurements, a four pulse DEER sequence [20] was run using pulse durations of 20 ns (p/2 pulse) and 40 ns (p pulse) with delays t1 of 200 ns and t2 adjusted according to Tm. The pump frequency was set on the maximum of resonance and the observed one was 56 MHz higher. To suppress undesirable echoes, an 8step phase cycle was applied. Data were collected during about 18 h for each sample. For Cu(II)-nitroxide distance measurements, the five-pulse sequence RIDME [27] was run using pulse durations of 20 ns (p/2 pulse) and 40ns (p pulse) and an interpulse delay of t1= 300ns (between the first and second pulses). The initial time interval between the 4 th and 5 th pulses was 3300ns. An 8-step phase cycle was applied to cancel unwanted echoes. The RIDME time traces were recorded at two different interpulse separations between the third and the fourth pulses: Thigh= 500µs and Tlow = 10µs. Division of the time trace with Thigh by the time trace with Tlow leads to suppression of ESEEM artifacts peaks. [36] Extraction of data from DEER and RIDME traces was performed using DeerAnalysis 2015 software. [37] The dipolar evolution dataset after homogeneous 3D spin distribution background correction was processed with Tikhonov regularization to obtain inter-spin distributions. The regularization factor a was chosen according to the L-curve criterion, based on a compromise between smoothness and resolution. [38]

Molecular dynamics -Model construction

A model for the open form of ACCO (without ACC, ascorbate or bicarbonate) was constructed using chain A of the 1WA6 protein databank structure. [9] A break in one of the loops of the crystal structure was fixed using the SWISS-MODEL webserver. [39] Additional C-terminal residues present in the sequence but missing in the crystal structure were added using the build function in PyMOL. Mutant structures (C165H/L292C and C165H/M307C) were made by replacing sidechains using SCWRL4 software package. [40] The LEaP module integrated in the Ambertools14 software package [41] was used to add hydrogen atoms and solvate the protein with TIP3P water molecules in a periodic box with a volume of 81×100×90 Å. We used PROPKA 3 to ascertain an appropriate protonation state for all titratable residues at pH 7.0. [42] All Arg/Lys residues were protonated and all Glu/Asp residues were deprotonated. Histidine Fe ligands were protonated at Nd, while all other histidine residues were protonated at Ne. Counter ions (Na + and Cl -) were added to the model in random positions to neutralise the system and create an ionic strength 0.15 M. Depending on the model, cysteine residues (C60, C292 or C307) were replaced with a cysteine with an attached paramagnetic probe (termed RCY) built using the Avogadro program. [43] RCY was hydrogenated as radicals are poorly described in molecular dynamics. Parameters and topology files for standard protein residues were generated using the ff14SB forcefield. Parameters and topology files for RCY residues were generated using the general AMBER force field (GAFF) with the Antechamber software package (part of Ambertools14). [44,45] Partial charges were obtained using the AM1-BCC charge model. Parameters for the Fe centre were obtained from a DFT calculation in Gaussian-09 [46] (method: B3LYP [47,48] optimised with basis set: 6-31G**, [49] frequency calculation with basis set: 6-311++G(2sp,f)) which included the Fe, methylated ligand sidechains and three water molecules (Table S4 & Figure S8). Force constants were extracted from the frequency calculation using the VFFDT software. [50] Partial charges were obtained from the electrostatic potential at points selected according to the Merz-Singh-Kollman scheme, [51] which were then RESP fitted. [52] A model for the closed form of ACCO was obtained from a previously published study. [13] This model also included docked positions of ACC, ascorbate and bicarbonate which were included in our simulations of the closed form. A WT model was constructed using the same procedure as for the open form. Two mutant models (C165H/L292C and C165H/M307C) were also constructed using the same procedure but using snapshots from a WT simulation at 50, 100 and 150 ns in order to achieve slightly different conformations of the closed structure. Additional parameters and topology files for ACC, ascorbate and bicarbonate were generated using the GAFF using the Antechamber software package.

Topology and parameter files generated for the iron(II) centre and RCY are provided in supporting information (Table S5)

Molecular dynamics -Simulations

Molecular dynamics simulations were performed using the GPUaccelerated AMBER PMEMD program on a NVIDIA K20 GPU. [41] Solvent and ion positions were minimised for a maximum of 1000 steps switching from the steepest descent algorithm to conjugate gradient after 500 steps whilst restraining protein atoms with a force constant of 500 kcal mol -1 Å - 2 . A second step of minimisation was then performed for 2500 steps, switching minimization algorithms after 1000 steps, with restraints on protein atoms reduced to 2 kcal mol -1 Å -2 . The cut-off for non-bonded interactions was 16 Å during both minimization procedures. The system was heated from 0 to 300K over a period of 200 ps at constant volume with restraints on protein atoms (2 kcal mol -1 Å -2 ). 200 ps density equilibration with the same restraints on the protein was followed by a further 200 ps of equilibration without restraints at constant temperature and pressure. For each model, three production runs were produced at constant temperature and pressure for 200 -400 ns. The total simulation time for each of the variants was 1.2 µs for C60 C292 and C60 C307 open forms and 0.6 µs for C60 C292 and C60 C307 closed forms. Long-range electrostatics were computed with the particle mesh Ewald scheme. The cut-off for nonbonded interactions was 8.0 Å. The SHAKE algorithm was used to constrain bonds involving hydrogen to allow for a 2 fs time step. A Langevin thermostat was used to maintain a temperature of 300 K using a collision frequency of 2.0 ps -1 and a Berendsen barostat was used to maintain pressure of 1 atm. Trajectories were processed with the CPPTRAJ program. [52] The RMSD plots for the simulations are provided Figures S9 &S10.

Entry for the Table of Contents

Figure 2 .

 2 Figure 2. (A) MMM computed spin label rotamers attached to the cysteines at positions C60 (green), C292 (yellow) and C307 (pink) for the "open" (left) and "closed" (right) conformations (B) calculated inter-label distance distributions for the "open" (red) and "closed" (blue) conformations for C60*-C292* (left panel) and C60*-C307* (right panel) distances.

Figure 4 .

 4 Figure 4. Left panel. Experimental Q-band DEER traces recorded at 60K for (A) C60*C292* (B) in the presence of ACC and HCO3 -and (C) in the presence of ACC, HCO3 -and ascorbate. Red lines indicate the baseline used for background correction. Middle panel. Corrected DEER traces with superimposed fits derived from Tikhonov regularization. Right panel. Tikhonovderived distance distributions obtained using DeerAnalysis 2015 and calculated distance distributions for the "open" (red) and "closed" (blue) conformations obtained using MMM. Vertical dashed lines are a guide for the reader eye.

  accessibility of the spin label grafted at position 307 to the reductant as compared to the one at 292.

Figure 5 .

 5 Figure 5. Left panel. Experimental Q-band DEER traces recorded at 60K for (A) C60*C307* (B) in the presence of ACC and HCO3 -and (C) in the presence of ACC, HCO3 -and ascorbate. Red lines indicate the baseline used for background correction. Middle panel. Corrected DEER traces with superimposed fits derived from Tikhonov regularization. Right panel. Tikhonovderived distance distributions obtained using DeerAnalysis 2015 and calculated distance distributions for the "open" (red) and "closed" (blue) conformations obtained using MMM. Vertical dashed lines are a guide for the reader eye.

Figure 7 .

 7 Figure 7. Inter-spin distance distributions extracted from molecular dynamics simulations for the open (green line) and closed (red line) form of C60 C292 are compared against the experimentally determined distributions in absence (solid black line) and in presence of ACC, HCO3 -and ascorbate (dashed black line).

Figure 8

 8 Figure 8Inter-spin distance distributions extracted from molecular dynamics simulations for the open (green line) and closed (red line) form of C60 C307 are compared against the experimentally determined distributions in absence (solid black line) and in presence of ACC, HCO3 -and ascorbate (dashed black line).

  mass determination. Samples of 20 to 30 pmoles of unlabelled and labelled ACCO enzymes were prepared by dilution in 10μL of 0.1% trifluoroacetic acid (TFA) in water (v/v). The mixture was then spotted onto a MALDI Target plate (1 μL) and saturated solution of α-cyano-4hydroxycinnamic acid (HCCA) or sinapinic matrix (1 μL) in 70% acetonitrile in water, 0.1% TFA (v/v) was added. The global mass was measured on a MALDI-ToF mass spectrometer Microflex II (Bruker Daltonics, Deutschland) in the range from 2000 to 20000 Da and in a linear and positive mode. External mass calibration was performed on the averaged [M+H] + from the Protein Calibrant I (Bruker Daltonics).Digestion. Samples of 60 to 100 pmoles were digested by trypsin (Sigma, St Louis, MO, USA) or GluC (Madison, WI, USA) at a ratio enzyme to substrate of 1/50 (w/w) (Sigma, St Louis, MO, USA) for 4 hours at 37°C. The digested solutions were then acidified by 1 μL of 12.5% trifluoroacetic acid (TFA) in water (v/v), vacuum dried and then dissolved in 0.1% TFA in water (v/v) before being spotted onto a MALDI Target plate (1 μL) and addition of a saturated solution of matrix a-cyano-4-hydroxycinnamic acid (1 μL) of 70% acetonitrile in water, 0.1% TFA (v/v). Digested peptides were analyzed on the MALDI-ToF mass spectrometer Microflex II from Bruker Daltonics in the range from 600 to 5000 Da. Data acquisition was operated in positive and reflectron mode. External mass calibration was performed on the mono-isotopic [M+H] + from the peptide calibration standard (Bruker Daltonics). A peak list was generated by a PMF (Peptide Mass Fingerprint) method from the FlexAnalysis software and manually checked. The experimentally measured peptide masses were compared with the theoretical tryptic peptides calculated from the sequence of ACCO, with variable modifications of the cysteine residues to take into account the number of grafted labels in the protein. In unlabelled samples, C residues may be free cysteines or a S-carbamidomethylcysteines (CAM-cys) if alkylated. In labelled samples, unlabelled C residues may be free cysteines (reduced form) or CAM ( MW 57.02). A grafted P can be detected as (i) S-proxyl-cysteine (Prox-cys, MW 237.12, -O form) (ii) S-proxylcysteine-H (Prox-cys-H, MW 238.13, OH form) (iii) S-proxyl-cysteine-H2O (Prox-cys-H2O, MW 255.13) and (iv) S-proxyl-cysteine-plusH2O-H (Proxcys-H2O-H, MW 256.14). Consequently, the following mass increments were monitored throughout the set of experiments: (i) when starting material is a protein in its reduced form: 237.12 ( Prox-cys), 238.13 (Proxcys-H), 255.13 (Prox-cys-H2O), 256.14 (Prox-cys-H2O-H) and (ii) when the starting material is alkylated with iodoacetamide: 180.10 (Prox-cys), 181.11 (Prox-cys-H), 198.11 (Prox-cys-H2O), 199.12 (Prox-cys-H2O-H).

  and theoretical study was performed to unravel the conformation of the Cterminal part of ACCO Eugénie Fournier, Sybille Tachon, Nicholas J. Fowler, Guillaume Gerbaud, Pascal Mansuelle, Pierre Dorlet, Sam P. de Visser,* Valérie Belle, A. Jalila Simaan*and Marlène Martinho* Page No. -Page No. The hunt for the closed conformation of the fruit-ripening enzyme 1-amino-cyclopropane-1carboxylic oxidase: A combined EPR and MD study.

A) 60*-292* 60*-307* B)

	Figure 3. Specific activities of native ACCO (% relative to the native enzyme)
	and mutants before and after labelling with proxyl (P). Values are derived from
	means ± SD of at least three repeated experiments.

Acknowledgements

This work was supported by A*MIDEX (ANR-11-IDEX-0001-02) funded by the «Investissements d'Avenir » French Government program and Aix-Marseille Université (AMU). The authors are grateful to the EPR facilities available at the Aix-Marseille Université, to the Conseil Régional of PACA and the city of Marseille for financial support in the acquisition of equipment. Financial support from the TGE RPE FR3443 for conducting the research is gratefully acknowledged. EF is grateful to A*MIDEX and Aix-Marseille Université for her PhD Fellowship. NJF and SdV thank the BBSRC for a studentship (under grant code BB/J014478/1).