Timothée Lacroix

Nicolas Usunier

Guillaume Obozinski

Canonical Tensor Decomposition for Knowledge Base Completion

 seems like a natural solution; however, current implementations of CP on standard Knowledge Base Completion benchmarks are lagging behind their competitors. In this work, we attempt to understand the limits of CP for knowledge base completion. First, we motivate and test a novel regularizer, based on tensor nuclear p-norms. Then, we present a reformulation of the problem that makes it invariant to arbitrary choices in the inclusion of predicates or their reciprocals in the dataset. These two methods combined allow us to beat the current state of the art on several datasets with a CP decomposition, and obtain even better results using the more advanced ComplEx model.

Introduction

In knowledge base completion, the learner is given triples (subject, predicate, object) of facts about the world, and has to infer new triples that are likely but not yet known to be true. This problem has attracted a lot of attention (Nickel et al., 2016a;[START_REF] Nguyen | An overview of embedding models of entities and relationships for knowledge base completion[END_REF] both as an example application of large-scale tensor factorization, and as a benchmark of learning representations of relational data.

The standard completion task is link prediction, which consists in answering queries (subject, predicate, ?) or (?, predicate, object). In that context, the canonical decomposition of tensors (also called CANDECOMP/PARAFAC or CP) [START_REF] Hitchcock | The expression of a tensor or a polyadic as a sum of products[END_REF] is known to perform poorly compared to more specialized methods. For instance, DistMult [START_REF] Yang | Embedding entities and relations for learning and inference in knowledge bases[END_REF], a particular case of CP which shares the fac-Proceedings of the 35 th International Conference on Machine Learning, Stockholm, Sweden, PMLR 80, 2018. Copyright 2018 by the author(s).

tors for the subject and object modes, was recently shown to have state-of-the-art results [START_REF] Kadlec | Knowledge Base Completion: Baselines Strike Back[END_REF]. This result is surprising because DistMult learns a tensor that is symmetric in the subject and object modes, while the datasets contain mostly non-symmetric predicates.

The goal of this paper is to study whether and how CP can perform as well as its competitors. To that end, we evaluate three possibilities.

First, as [START_REF] Kadlec | Knowledge Base Completion: Baselines Strike Back[END_REF] showed that performances for these tasks are sensitive to the loss function and optimization parameters, we re-evaluate CP with a broader parameter search and a multiclass log-loss.

Second, since the best performing approaches are less expressive than CP, we evaluate whether regularization helps. On this subject, we show that the standard regularization used in knowledge base completion does not correspond to regularization with a tensor norm. We then propose to use tensor nuclear p-norms [START_REF] Friedland | Nuclear norm of higher-order tensors[END_REF], with the goal of designing more principled regularizers.

Third, we propose a different formulation of the objective, in which we model separately predicates and their inverse: for each predicate pred, we create an inverse predicate pred -1 and create a triple (obj, pred -1 , sub) for each training triple (sub, pred, obj). At test time, queries of the form (?, pred, obj) are answered as (obj, pred -1 , ?). Similar formulations were previously used by [START_REF] Shen | Implicit reasonet: Modeling large-scale structured relationships with shared memory[END_REF] and [START_REF] Joulin | Fast linear model for knowledge graph embeddings[END_REF], but for different models for which there was no clear alternative, so the impact of this reformulation has never been evaluated.

To assess whether the results we obtain are specific to CP, we also carry on the same experiments with a state-of-theart model, ComplEx [START_REF] Trouillon | Complex embeddings for simple link prediction[END_REF]. ComplEx has the same expressivity as CP in the sense that it can represent any tensor, but it implements a specific form of parameter sharing. We perform all our experiments on 5 common benchmark datasets of link prediction in knowledge bases.

Our results first confirm that within a reasonable time budget, the performance of both CP and ComplEx are highly dependent on optimization parameters. With systematic parameter searches, we obtain better results for ComplEx than what was previously reported, confirming its status as a state-of-the-art model on all datasets. For CP, the results are still way below its competitors.

Learning and predicting with the inverse predicates, however, changes the picture entirely. First, with both CP and ComplEx, we obtain significant gains in performance on all the datasets. More precisely, we obtain state-of-the-art results with CP, matching those of ComplEx. For instance, on the benchmark dataset FB15K (Bordes et al., 2013), the mean reciprocal rank of vanilla CP and vanilla ComplEx are 0.40 and 0.80 respectively, and it grows to 0.86 for both approaches when modeling the inverse predicates.

Finally, the new regularizer we propose based on the nuclear 3-norm, does not dramatically help CP, which leads us to believe that a careful choice of regularization is not crucial for these CP models. Yet, for both CP and Com-plEx with inverse predicates, it yields small but significant improvements on the more difficult datasets.

Tensor Factorization of Knowledge Bases

We describe in this section the formal framework we consider for knowledge base completion and more generally link prediction in relational data, the learning criteria, as well as the approaches that we will discuss.

Link Prediction in Relational Data

We consider relational data that comes in the form of triples (subject, predicate, object), where the subject and the object are from the same set of entities. In knowledge bases, these triples represent facts about entities of the world, such as (Washington, capital_of, USA). A training set S contains triples of indices S = {(i 1 , j 1 , k 1 ), ..., (i |S| , j |S| , k |S| )} that represent predicates that are known to hold. The validation and test sets contain queries of the form (?, j, k) and (i, j, ?), created from triples (i, j, k) that are known to hold but held-out from the training set. To give orders of magnitude, the largest datasets we experiment on, FB15K and YAGO3-10, contain respectively 15k/1.3k and 123k/37 entities/predicates.

Tensor Decomposition for Link Prediction

Relational data can be represented as a {0, 1}-valued third order tensor Y ∈ {0, 1}

N ×P ×N , where N is the total number of entities and P the number of predicates, with Y i,j,k = 1 if the relation (i, j, k) is known. In the rest of the paper, the three modes will be called the subject mode, the predicate mode and the object mode respectively. Tensor factorization algorithms can thus be used to infer a predicted tensor X ∈ R N ×P ×N that approximates Y in a sense that we describe in the next subsection. Validation/test queries (?, j, k) are answered by ordering entities i by decreasing values of Xi ,j,k , whereas queries (i, j, ?) are answered by ordering entities k by decreasing values of Xi,j,k .

Several approaches have considered link prediction as a low-rank tensor decomposition problem. These models then differ only by structural constraints on the learned tensor. Three models of interest are:

CP. The canonical decomposition of tensors, also called CANDECOM/PARAFAC [START_REF] Hitchcock | The expression of a tensor or a polyadic as a sum of products[END_REF], represents a tensor X ∈ R N1×N2×N3 as a sum of R rank one tensors u

(1)

r ⊗ u (2) r ⊗ u (3)
r (with ⊗ the tensor product) where r ∈ {1, ..., R}, and u

(m) r ∈ R Nm : X = R r=1 u (1) r ⊗ u (2) r ⊗ u (3) r .
A representation of this decomposition, and the score of a specific triple is given in Figure 1 (a). Given X, the smallest R for which this decomposition holds is called the canonical rank of X.

DistMult. In the more specific context of link prediction, it has been suggested in [START_REF] Bordes | Learning structured embeddings of knowledge bases[END_REF]; [START_REF] Nickel | A three-way model for collective learning on multi-relational data[END_REF] that since both subject and object mode represent the same entities, they should have the same factors. DistMult [START_REF] Yang | Embedding entities and relations for learning and inference in knowledge bases[END_REF] is a version of CP with this additional constraint. It represents a tensor X ∈ R N ×P ×N as a sum of rank-1 tensors u

(1)

r ⊗ u (2) r ⊗ u (1)
r :

X = R r=1 u (1) r ⊗ u (2) r ⊗ u (1) r .
ComplEx. By contrast with the first models that proposed to share the subject and object mode factors, Dist-Mult yields a tensor that is symmetric in the object and subject modes. The assumption that the data tensor can be properly approximated by a symmetric tensor for Knowledge base completion is not satisfied in many practical cases (e.g., while (Washington, capital_of, USA) holds, (USA, capital_of, Washington) does not). Com-plEx [START_REF] Trouillon | Complex embeddings for simple link prediction[END_REF] proposes an alternative where the subject and object modes share the parameters of the factors, but are complex conjugate of each other. More precisely, this approach represents a real-valued tensor X ∈ R N1×N2×N3 as the real part of a sum of R complex-valued rank one tensors u

(1)

r ⊗ u (2) r ⊗ u (1)
r where r ∈ {1, ..., R}, and u

(m) r ∈ C Nm X = Re R r=1 u (1) r ⊗ u (2) r ⊗ u (1) r ,
where u

(1) r is the complex conjugate of u

(1) r . This decomposition can represent any real tensor [START_REF] Trouillon | Complex embeddings for simple link prediction[END_REF]. The good performances of DistMult on notoriously nonsymmetric datasets such as FB15K or WN18 are surprising.

First, let us note that for the symmetricity to become an issue, one would have to evaluate queries (i, j, ?) while also trying to answer correctly to queries of the form (?, j, i) for a non-symmetric predicate j. The ranking for these two queries would be identical, and thus, we can expect issues with relations such as capital_of . In FB15K, those type of problematic queries make up only 4% of the test set and thus, have a small impact. On WN18 however, they make up 60% of the test set. We describe in appendix 8.1 a simple strategy for DistMult to have a high filtered MRR on the hierarchical predicates of WN18 despite its symmetricity assumption.

Training

Previous work suggested ranking losses (Bordes et al., 2013), binary logistic regression [START_REF] Trouillon | Complex embeddings for simple link prediction[END_REF] or sampled multiclass log-loss [START_REF] Kadlec | Knowledge Base Completion: Baselines Strike Back[END_REF]. Motivated by the solid results in [START_REF] Joulin | Fast linear model for knowledge graph embeddings[END_REF], our own experimental results, and with a satisfactory speed of about two minutes per epoch on FB15K, we decided to use the full multiclass log-loss.

Given a training triple (i, j, k) and a predicted tensor X, the instantaneous multi-class log-loss

i,j,k (X) is i,j,k (X) = (1) i,j,k (X) + (3) i,j,k (X) (1)
(1)

i,j,k (X) = -X i,j,k + log k exp(X i,j,k ) (3) i,j,k (X) = -X i,j,k + log i exp(X i ,j,k ) .
These two partial losses are represented in Figure 1 (b). For CP, the final tensor is computed by finding a minimizer of a regularized empirical risk formulation, where the factors u

(d)
r are weighted in a data-dependent manner by w

(d) S ,
which we describe below:

min (u (d) r ) d=1..3 r=1..R (i,j,k)∈S i,j,k R r=1 u (1) r ⊗ u (2) r ⊗ u (3) r + λ R r=1 3 d=1 w (d) S u (d) r 2 2 , (2)
where is the entry-wise multiplication of vectors. For DistMult and ComplEx, the learning objective is similar, up to the appropriate parameter sharing and computation of the tensor.

As discussed in Section 3.2, the weights w

(d)
S may improve performances when some rows/columns are sampled more than others. They appear naturally in optimization with stochastic gradient descent when the regularizer is applied only to the parameters that are involved in the computation of the instantaneous loss. For instance, in the case of the logistic loss with negative sampling used by [START_REF] Trouillon | Complex embeddings for simple link prediction[END_REF], denoting by q d i the marginal probability (over S) that index i appears in mode d of a data triple, these weights are w (d) S,i = q d i + α for some α > 0 that depends on the negative sampling scheme.

We focus on redefining the loss (1) and the regularizer (2).

Related Work

We discuss here in more details the work that has been done on link prediction in relational data and on regularizers for tensor completion.

Link Prediction in Relational Data

There has been extensive research on link prediction in relational data, especially in knowledge bases, and we review here only the prior work that is most relevant to this paper. While some approaches explicitly use the graph struc-ture during inference [START_REF] Lao | Random walk inference and learning in a large scale knowledge base[END_REF], we focus here on representation learning and tensor factorization methods, which are the state-of-the-art on the benchmark datasets we use. We also restrict the discussion to approaches that only use relational information, even though some approaches have been proposed to leverage additional types [START_REF] Krompass | Type-constrained representation learning in knowledge graphs[END_REF][START_REF] Ma | Transt: Type-based multiple embedding representations for knowledge graph completion[END_REF] or external word embeddings [START_REF] Toutanova | Observed versus latent features for knowledge base and text inference[END_REF].

We can divide the first type of approaches into two broad categories. First, two-way approaches score a triple (i, j, k) depending only on bigram interaction terms of the form subject-object, subject-predicate, and predicate-object. Even though they are tensor approximation algorithms of limited expressivity, two-way models based on translations TransE, or on bag-of-word representations [START_REF] Joulin | Fast linear model for knowledge graph embeddings[END_REF] have proved competitive on many benchmarks. Yet, methods using three-way multiplicative interactions, as described in the previous section, show the strongest performances [START_REF] Bordes | Learning structured embeddings of knowledge bases[END_REF][START_REF] Garcia-Duran | Combining two and three-way embedding models for link prediction in knowledge bases[END_REF]Nickel et al., 2016b;[START_REF] Trouillon | Complex embeddings for simple link prediction[END_REF]. Compared to general-purpose tensor factorization methods such as CP, a common feature of these approaches is to share parameters between objects and subjects modes [START_REF] Nickel | A three-way model for collective learning on multi-relational data[END_REF], an idea that has been widely accepted except for the twoway model of [START_REF] Joulin | Fast linear model for knowledge graph embeddings[END_REF]. DistMult [START_REF] Yang | Embedding entities and relations for learning and inference in knowledge bases[END_REF] is the extreme case of this parameter sharing, in which the predicted tensor is symmetric in the subject and object modes.

Regularization for Matrix Completion

Norm-based regularization has been extensively studied in the context of matrix completion. The trace norm (or nuclear norm) has been proposed as a convex relaxation of the rank [START_REF] Srebro | Maximum-margin matrix factorization[END_REF] for matrix completion in the setting of rating prediction, with strong theoretical guarantees [START_REF] Candès | Exact matrix completion via convex optimization[END_REF]. While efficient algorithms to solve the convex problems have been proposed (see e.g. [START_REF] Cai | A singular value thresholding algorithm for matrix completion[END_REF][START_REF] Jaggi | A simple algorithm for nuclear norm regularized problems[END_REF], the practice is still to use the matrix equivalent of the nonconvex formulation (2). For the trace norm (nuclear 2-norm), in the matrix case, the regularizer simply becomes the squared 2-norm of the factors and lends itself to alternating methods or SGD optimization (Rennie & Srebro, 2005;[START_REF] Koren | Matrix factorization techniques for recommender systems[END_REF]. When the samples are not taken uniformly at random from a matrix, some other norms are preferable to the usual nuclear norm. The weighted trace norm reweights elements of the factors based on the marginal rows and columns sampling probabilities, which can improve sample complexity bounds when sampling is non-uniform [START_REF] Foygel | Learning with the weighted trace-norm under arbitrary sampling distributions[END_REF][START_REF] Negahban | Restricted strong convexity and weighted matrix completion: Optimal bounds with noise[END_REF]. Direct SGD implementations on the nonconvex formulation implicitly take this reweighting rule into account and were used by the winners of the Netflix challenge (see [START_REF] Srebro | Collaborative filtering in a non-uniform world: Learning with the weighted trace norm[END_REF], Section 5).

Tensor Completion and Decompositions

There is a large body of literature on low-rank tensor decompositions (see [START_REF] Kolda | Tensor decompositions and applications[END_REF], for a comprehensive review). Closely related to our work is the canonical decomposition of tensor (also called CANDECOMP/PARAFAC or CP) [START_REF] Hitchcock | The expression of a tensor or a polyadic as a sum of products[END_REF], which solves a problem similar to (4) without the regularization (i.e., λ = 0), and usually the square loss.

Several norm-based regularizations for tensors have been proposed. Some are based on unfolding a tensor along each of its modes to obtain matricizations, and either regularize by the sum of trace norms of the matricizations [START_REF] Tomioka | Estimation of low-rank tensors via convex optimization[END_REF] or write the original tensor as a sum of tensors T k , regularizing their respective kth matricizations with the trace norm [START_REF] Wimalawarne | Multitask learning meets tensor factorization: task imputation via convex optimization[END_REF]. However, in the large-scale setting, even rank-1 approximations of matricizations involve too many parameters to be tractable.

Recently, the tensor trace norm (nuclear 2-norm) was proposed as a regularizer for tensor completion [START_REF] Yuan | On tensor completion via nuclear norm minimization[END_REF], and an algorithm based on the generalized conditional gradient has been developed by [START_REF] Cheng | Scalable and sound low-rank tensor learning[END_REF]. This algorithm requires, in an inner loop, to compute a (constrained) rank-1 tensor that has largest dot-product with the gradient of the data-fitting term (gradient w.r.t. the tensor argument). This algorithm is efficient in our setup only with the square error loss (instead of the multiclass log-loss), because the gradient is then a low-rank + sparse tensor when the argument is low-rank. However, on large-scale knowledge bases, the state of the art is to use a binary log-loss or a multiclass log-loss [START_REF] Trouillon | Complex embeddings for simple link prediction[END_REF][START_REF] Kadlec | Knowledge Base Completion: Baselines Strike Back[END_REF]; in that case, the gradient is not adequately structured, thereby causing the approach of [START_REF] Cheng | Scalable and sound low-rank tensor learning[END_REF] to be too computationally costly.

Nuclear p-Norm Regularization

As discussed in Section 3, norm-based regularizers have proved useful for matrices. We aim to reproduce these successes with tensor norms. We use the nuclear p-norms defined by [START_REF] Friedland | Nuclear norm of higher-order tensors[END_REF]. As shown in Equation (2), the community has favored so far a regularizer based on the square Frobenius norms of the factors [START_REF] Yang | Embedding entities and relations for learning and inference in knowledge bases[END_REF][START_REF] Trouillon | Complex embeddings for simple link prediction[END_REF]. We first show that the unweighted version of this regularizer is not a tensor norm. Then, we propose4 a variational form of the nuclear 3-norm to replace the usual regularization at no additional computational cost when used with SGD. Finally, we discuss a weighting scheme analogous to the weighted trace-norm proposed in [START_REF] Srebro | Collaborative filtering in a non-uniform world: Learning with the weighted trace norm[END_REF].

From Matrix Trace-Norm to Tensor Nuclear Norms

To simplify notation, let us introduce the set of CP decompositions of a tensor X of rank at most R:

U R (X) = (u (d) r ) d=1..3 r=1..R X = R r=1 u (1) r ⊗ u (2) r ⊗ u (3) r , ∀r, d, u (d) r ∈ R N d .
We will study the family of regularizers:

Ω α p (u) = 1 3 R r=1 3 d=1 u (d) r α p .
Note that with p = α = 2, we recover the familiar squared Frobenius norm regularizer used in (2). Similar to showing that the squared Frobenius norm is a variational form of the trace norm on matrices (i.e., its minimizers realize the trace norm, inf

M =U V T 1 2 ( U 2 F + V 2 F ) = M * )
, we start with a technical lemma that links our regularizer with a function on the spectrum of our decompositions. Lemma 1.

min u∈U R (X) 1 3 R r=1 3 d=1 u (d) r α p = min u∈U R (X) R r=1 3 d=1 u (d) r α/3 p .
Moreover, the minimizers of the left-hand side satisfy:

u (d) r p = 3 3 d =1 u (d ) r p .
Proof. See Appendix 8.2. This Lemma motivates the introduction of the set of p-norm normalized tensor decompositions:

U p R (X) = (σ r , (ũ r )) r=1..R σ r = 3 d=1 u (d) r p , ũ(d) r = u (d) r u (d) r p , ∀r, d, u ∈ U R (X) .
Lemma 2, shows that Ω α p behaves as an α/D penalty over the CP spectrum for tensors of order D. We recover the nuclear norm for matrices when α = p = 2.

Using Lemma 2, we have :

min u∈U R (X) Ω 2 2 (u) ≤ η ⇐⇒ min (σ,ũ)∈U 2 R (X) σ 2/3 ≤ η 3/2
(3)

We show that the sub-level sets of the term on the right are not convex, which implies that Ω 2 2 is not the variational form of a tensor norm, and hence, is not the tensor analog to the matrix trace norm.

Proposition 1. The function over third order-tensors of R N1×N2×N3 defined as

|||X||| = min σ 2/3 (σ, ũ) ∈ U 2 R (X), R ∈ N is not convex. Proof. See Appendix 8.2.
Remark 1. Cheng et al. (2016, Appendix D) already showed that regularizing with the square Frobenius norm of the factors is not related to the trace norm for tensors of order 3 and above, but their observation is that the regularizer is not positively homogeneous, i.e., min u∈αU R (X) Ω 2 2 (u) = |α| min u∈U R (X) Ω 2 2 (u). Our result in Proposition 1 is stronger in that we show that this regularizer is not a norm even after the rescaling (3) to make it homogeneous.

The nuclear p-norm of X ∈ R N1×N2×N3 for p ∈ [1, +∞],
is defined in [START_REF] Friedland | Nuclear norm of higher-order tensors[END_REF] as

X * ,p := min σ 1 (σ, ũ) ∈ U p R (X), R ∈ N .
Given an estimated upper bound on the optimal R, the original problem (2) can then be re-written as a non-convex problem using the equivalence in Lemma 2:

min (u (d) r ) d=1..3 r=1..R (i,j,k)∈S i,j,k R r=1 u (1) r ⊗ u (2) r ⊗ u (3) r + λ 3 R r=1 3 d=1 u (d) r 3 p . ( 4
)
This variational form suggests to use p = 3, as a means to make the regularizer separable in each coefficients, given that then u

(d) r 3 p = n d i=1 u (d) r,i | 3 .

Weighted Nuclear p-Norm

Similar to the weighted trace-norm for matrices, the weighted nuclear 3-norm can be easily implemented by keeping the regularization terms corresponding to the sampled triplets only, as discussed in Section 3.2. This leads to a formulation of the form

min (u (d) r ) d=1..3 r=1..R (i,j,k)∈S i,j,k R r=1 u (1) r ⊗u (2) r ⊗u (3) r (5) + λ 3 R r=1 u (1) r,i | 3 + u (2) r,j | 3 + u (3) r,k | 3 .
For an example (i, j, k), only the parameters involved in the computation of Xi,j,k are regularized. The computational complexity is thus the same as the currently used weighted Frobenius norm regularizer. With q (1) (resp. q (2) , q (3) ) the marginal probabilities of sampling a subject (resp. predicate, object), the weighting implied by this regularization scheme is

X * ,3,w = ( 3 q (1) ⊗ 3 q (2) ⊗ 3 q (3) ) X * ,3
We justify this weighting only by analogy with the matrix case discussed by [START_REF] Srebro | Collaborative filtering in a non-uniform world: Learning with the weighted trace norm[END_REF]: to make the weighted nuclear 3-norm of the all 1 tensor independent of its dimensions for a uniform sampling (since the nuclear 3-norm grows as 3 √ M N P for an (M, N, P ) tensor).

Comparatively, for the weighted version of the nuclear 2norm analyzed in [START_REF] Yuan | On tensor completion via nuclear norm minimization[END_REF], the nuclear 2-norm of the all 1 tensor scales like √ N M P . This would imply a formulation of the form

min (u (d) r ) d=1..3 r=1..R (i,j,k)∈S i,j,k R r=1 u (1) r ⊗ u (2) r ⊗ u (3) r + λ 3 R r=1 3 d=1 q (d) u (d) r 3 2 . ( 6
)
Contrary to formulation (5), the optimization of formulation ( 6) with a minibatch SGD leads to an update of every coefficients for each mini-batch considered. Depending on the implementation, and size of the factors, there might be a large difference in speed between the updates of the weighted nuclear {2, 3}-norm. In our implementation, this difference for CP is of about 1.5× in favor of the nuclear 3-norm on FB15K.

A New CP Objective

Since our evaluation objective is to rank either the lefthand side or right-hand side of the predicates in our dataset, what we are trying to achieve is to model both predicates and their reciprocal. This suggests appending to our input the reciprocals of each predicates, thus factorizing [Y ; 2 Ỹ ] rather than Y , where [ ; 2 ] is the mode-2 concatenation, and Y i,j,k = Ỹk,j,i . After that, we only need to model the object fibers of this new tensor Y . We represent this transformation in Figure 1 (c). This reformulation has an important side-effect: it makes our algorithm invariant to the arbitrary choice of including a predicate or its reciprocal in the dataset. This property was introduced as "Semantic Invariance" in [START_REF] Bailly | Semantically Invariant Tensor Factorization[END_REF]. Another way of achieving this invariance property would be to find the flipping of predicates that lead to the smallest model. In the case of a CP decomposition, we would try to find the flipping that leads to lowest tensor rank. This seems hopeless, given the NP-hardness of computing the tensor rank. (i, j, k) becomes :

i,j,k (X) = -X i,j,k + log k exp(X i,j,k ) (7) -X k,j+P,i + log i exp(X k,j+P,i ) .
At test time we use Xi,j,: to rank possible right hand sides for query (i, j, ?) and Xk,j+P,: to rank possible left hand sides for query (?, j, k).

Using CP to factor the tensor described in (7), we beat the previous state of the art on many benchmarks, as shown in Table 2. This reformulation seems to help even the ComplEx decomposition, for which parameters are shared between the entity embeddings of the first and third mode.

Experiments

We conducted all experiments on a Quadro GP 100 GPU. The code is available at https://github.com/ facebookresearch/kbc.

Datasets and Experimental Setup

WN18 and FB15K are popular benchmarks in the Knowledge Base Completion community. The former comes from the WordNet database, was introduced in [START_REF] Bordes | A semantic matching energy function for learning with multirelational data[END_REF] and describes relations between words. The most frequent types of relations are highly hierarchical (e.g., hypernym, hyponym). The latter is a subsampling of Freebase limited to 15k entities, introduced in Bordes et al. (2013). It contains predicates with different characteristics (e.g., oneto-one relations such as capital_of to many-to-many such as actor_in_film).

Toutanova & Chen (2015) and [START_REF] Dettmers | Convolutional 2d knowledge graph embeddings[END_REF] identified train to test leakage in both these datasets, in the form of test triplets, present in the train set for the reciprocal predicates. Thus, both of these authors created two modified datasets: FB15K-237 and WN18RR. These datasets are harder to fit, so we expect regularization to have more impact. [START_REF] Dettmers | Convolutional 2d knowledge graph embeddings[END_REF] In all our experiments, we distinguish two settings: Reciprocal, in which we use the loss described in equation ( 7) and Standard, which uses the loss in equation ( 1). We compare our implementation of CP and ComplEx with the best published results, then the different performances between the two settings, and finally, the contribution of the regularizer in the reciprocal setting. In the Reciprocal setting, we compare the weighted nuclear 3-norm (N3) against the regularizer described in (2) (FRO). In preliminary experiments, the weighted nuclear 2-norm described in (6) did not seem to perform better than N3 and was slightly slower. We used Adagrad [START_REF] Duchi | Adaptive subgradient methods for online learning and stochastic optimization[END_REF] as our optimizer, whereas [START_REF] Kadlec | Knowledge Base Completion: Baselines Strike Back[END_REF] favored Adam [START_REF] Kingma | A method for stochastic optimization[END_REF], because preliminary experiments didn't show improvements.

We ran the same grid for all algorithms and regularizers on the FB15K, FB15K-237, WN18, WN18RR datasets, with a rank set to 2000 for ComplEx, and 4000 for CP. Our grid consisted of two learning rates: 10 -1 and 10 -2 , two batch-sizes: 25 and 100, and regularization coefficients in [0, 10 -3 , 5.10 -3 , 10 -2 , 5.10 -2 , 10 -1 , 5.10 -1 ].

On YAGO3-10, we limited our models to rank 1000 and used batch-sizes 500 and 3000, the rest of the grid was identical. We used the train/valid/test splits provided with these datasets and measured the filtered Mean Reciprocal Rank (MRR) and Hits@10 ( Bordes et al. (2013)). We used the filtered MRR on the validation set for early stopping and report the corresponding test metrics. In this setting, an epoch for ComplEx with batch-size 100 on FB15K took about 110s and 325s for a batch-size of 25. We trained for 100 epochs to ensure convergence, reported performances were reached within the first 25 epochs.

All our results are reported in Table 2 and will be discussed in the next subsections. Besides our implementations of CP and ComplEx, we include the results of ConvE and DistMult in the baselines. The former because [START_REF] Dettmers | Convolutional 2d knowledge graph embeddings[END_REF] includes performances on the WN18RR and YAGO3-10 benchmarks, the latter because of the good performances on FB15K of DistMult and the extensive experiments on WN18 and FB15K reported in [START_REF] Kadlec | Knowledge Base Completion: Baselines Strike Back[END_REF]. The performances of DistMult on FB15K-237, WN18RR and YAGO3-10 may be slightly underestimated, since our baseline CP results are better. To avoid clutter, we did not include in our table of results algorithms that make use of external data such as types [START_REF] Krompass | Type-constrained representation learning in knowledge graphs[END_REF], external word embeddings [START_REF] Toutanova | Observed versus latent features for knowledge base and text inference[END_REF], or using path queries as regularizers [START_REF] Guu | Traversing knowledge graphs in vector space[END_REF]. The published results corresponding to these methods are subsumed in the "Best Published" line of Table 2, which is taken, for every single metric and dataset, as the best published result we were able to find.

Reimplementation of the Baselines

The performances of our reimplementation of CP and Com-plEx appear in the middle rows of previously published results used a rank of around 200; the more extensive search for optimization/regularization parameters and the use of nuclear 3-norm instead of the usual regularization are also most likely part of the explanation.

Standard vs Reciprocal

In this section, we compare the effect of reformulation (7), that is, the middle and bottom rows of Table 2. The largest differences are obtained for CP, which becomes a state of the art contender going from 0.2 to 0.95 filtered MRR on WN18, or from 0.46 to 0.86 filtered MRR on FB15K.For ComplEx, we notice a weaker, but consistent improvement by using our reformulation, with the biggest improvements observed on FB15K and YAGO3-10. Following the analysis in Bordes et al. (2013), we show in Table 3 the average filtered MRR as a function of the degree of the predicates. We compute the average in and out degrees on the training set, and separate the predicates in 4 categories : 1-1, 1-m, m-1 and m-m, with a cut-off at 1.5 on the average degree. We include reciprocal predicates in these statistics. That is, a predicate with an average in-degree of 1.2 and average out-degree of 3.2 will count as a 1-m when we predict its right-hand side, and as an m-1 when we predict its left-hand side. Most of our improvements come from the 1-m and m-m categories, both on ComplEx and CP.

Frobenius vs Nuclear 3

We focus now on the effect of our norm-based N3 regularizer, compared to the Frobenius norm regularizer favored by the community. Comparing the four last rows of Table 2, we notice a small but consistent performance gain across datasets. The biggest improvements appear on the harder datasets WN18RR, FB15K-237 and YAGO3-10. We checked on WN18RR the significance of that gain with a Signed Rank test on the rank pairs for CP.

Effect of Optimization Parameters

During these experiments, we noticed a heavy influence of optimization hyper-parameters on final results. This influence can account for as much as 0.1 filtered MRR and is illustrated in Figure 2. The difference is large even after 100 epochs and the effect is inverted in the two settings, making it hard to choose the batchsize a priori.

Conclusion and Discussion

The main contribution of this paper is to isolate and systematically explore the effect of different factors for large-scale knowledge base completion. While the impact of optimization parameters was well known already, neither the effect of the formulation (adding reciprocals doubles the mean reciprocal rank on FB15K for CP) nor the impact of the regularization was properly assessed. The conclusion is that the CP model performs nearly as well as the competitors when each model is evaluated in its optimal configuration. We believe this observation is important to assess and prioritize directions for further research on the topic.

In addition, our proposal to use nuclear p-norm as regularizers with p = 2 for tensor factorization in general is of independent interest.

The results we present leave several questions open. Notably, whereas we give definite evidence that CP itself can perform extremely well on these datasets as long as the problem is formulated correctly, we do not have a strong theoretical justification as to why the differences in performances are so significant.

Figure 1 .

 1 Figure 1. (a) On the left, the link between the score of a triple (i,j,k) and the tensor estimated via CP. (b) In the middle, the two type of fiber losses that we will consider. (c) On the right, our semantically invariant reformulation, the first-mode fibers become third-mode fibers of the reciprocal half of the tensor.

Figure 2 .

 2 Figure 2. Effect of the batch-size on FB15K in the Standard (top) and Reciprocal (bottom) settings, other parameters being equal.The difference is large even after 100 epochs and the effect is inverted in the two settings, making it hard to choose the batchsize a priori.

Table 1 .

 1 Dataset statistics.

	More precisely, the instantaneous loss of a training triple

Table 2 .

 2 also introduced the dataset YAGO3-10, which is larger in scale and doesn't suffer from leakage. All datasets statistics are shown in Table1. * Results taken as best from[START_REF] Dettmers | Convolutional 2d knowledge graph embeddings[END_REF] and[START_REF] Kadlec | Knowledge Base Completion: Baselines Strike Back[END_REF]. † Results taken as best from[START_REF] Dettmers | Convolutional 2d knowledge graph embeddings[END_REF] and[START_REF] Trouillon | Complex embeddings for simple link prediction[END_REF]. We give the origin of each result on the Best Published row in appendix.

		Model	WN18	WN18RR	FB15K	FB15K-237	YAGO3-10
			MRR H@10 MRR H@10 MRR H@10 MRR H@10 MRR H@10
	Past SOTA	CP ComplEx † DistMult * ConvE *	0.08 0.94 0.82 0.94	0.13 0.95 0.94 0.95	-0.44 0.43 0.46	-0.51 0.49 0.48	0.33 0.70 0.80 0.75	0.53 0.84 0.89 0.87	-0.25 0.24 0.32	-0.43 0.42 0.49	-0.36 0.34 0.52	-0.55 0.54 0.66
		Best Published	0.94	0.97	0.46	0.51	0.84	0.93	0.32	0.49	0.52	0.66
	Standard	CP-N3 ComplEx-N3	0.20 0.95 0.96 0.33	0.12 0.47	0.20 0.54	0.46 0.80	0.65 0.89	0.33 0.35	0.51 0.54	0.38 0.49	0.65 0.68
	Reciprocal	CP-FRO CP-N3 ComplEx-FRO ComplEx-N3	0.95 0.95 0.95 0.95	0.95 0.96 0.96 0.96	0.46 0.47 0.47 0.48 0.57 0.86 0.48 0.86 0.54 0.86 0.54 0.86	0.91 0.91 0.91 0.91	0.34 0.36 0.35 0.37 0.56 0.58 0.71 0.51 0.54 0.68 0.54 0.57 0.71 0.53 0.57 0.71

Table 2 (

 2 Standard setting).

	We only kept the results for the nuclear 3-norm, which didn't
	seem to differ from those with the Frobenius norm. Our
	results are slightly better than their published counterparts,
	going from 0.33 to 0.46 filtered MRR on FB15K for CP
	and 0.70 to 0.80 for ComplEx. This might be explained
	in part by the fact that in the Standard setting (2) we use a
	multi-class log-loss, whereas Trouillon et al. (2016) used
	binomial negative log-likelihood. Another reason for this
	increase can be the large rank of 2000 that we chose, where

Table 3 .

 3 Average MRR per relation type on FB15K.

Acknowledgements

The authors thank Armand Joulin and Maximilian Nickel for valuable discussions.

Appendix

DistMult on hierarchical predicates

Suppose we are trying to embed a single hierarchical predicate p which is a n-ary tree of depth d. This tree will have n d leaves, 1 root and K d n = n d -n n-1 ∼ n d-1 internal nodes. We forget any modeling issues we might have, but focus on the symmetricity assumption in Distmult.

Leaves and the root only appear on one side of the queries (i, p, j) and hence won't have any problems with the symmetricity. We now focus on an internal node i. It has n children (c i k ) k=1..n and one ancestor a i . Assuming n > 2, the MRR associated with this node will be higher if the query (i, p, ?) yields the ranked list [c i 1 , ..., c i n , a i ]. Indeed, the filtered rank of the n queries (i, p, c i k ) will be 1 while the filtered rank of the query (a i , p, i) will be n + 1.

Counting the number of queries for which the filtered rank is 1, we see that they far outweigh the queries for which the filtered rank is n + 1 in the final filtered MRR. For each internal nodes, n queries lead to a rank of 1, and only 1 to a rank of n + 1. For the root, n queries with a rank of 1, for the leaves, n d queries with a rank of 1.

Our final filtered MRR is :

Hence for big hierarchies such as hyponym or hypernym in WN, we expect the filtered MRR of DistMult to be high even though its modeling assumptions are incorrect.

Proofs

Lemma 2.

Moreover, the minimizers of the left-hand side satisfy:

Proof. First, we characterize the minima :

We study a summand, for c i , a i > 0 :

Using constrained optimization techniques, we obtain that this minimum is obtained for :

and has value ( 3 d=1 a i ) α/3 , which completes the proof.

Proposition 2. The function over third order-tensors of R N1×N2×N3 defined as

Proof. We first study elements of R 2×2×1 , tensors of order 3 associated with matrices of size 2 × 2. We have that

Let A = 1 2 I 2 , the mean of these two matrices. Identifying A with a 2 × 2 × 1 tensor A to obtain the decomposition (σ, u) yielding |||A|||, we have that the matrix A can be written as

r . This comes from the fact that u

(3) r is a normalized 1 × 1 vector, so its only entry is equal to 1. We then write that trace

Moreover, we have σ 2/3 ≥ σ 1 with equality only for σ with at most one non-zero coordinate. Since A is of rank 2, its representation has at least 2 non-zero coordinates, hence |||A||| = σ 2/3 > 1, which contradicts convexity. This proof can naturally be extended to tensors of any sizes.

Best Published results

We report in


L-Ala D-Isogln Dap Nh2 D-Ala D-Ala

Keywords: Amidation, Amidotransferase, Mycobacterium tuberculosis, Peptidoglycan, Transpeptidase

Critical impact of peptidoglycan precursor amidation on the activity of L,D-transpeptidases from Enterococcus faecium and Mycobacterium tuberculosis

Flora Ngadjeua #,[a] , Emmanuelle Braud #, [b] , Saidbakhrom Saidjalolov [b] , Laura Iannazzo [b] , Dirk Schnappinger [c] , Sabine Ehrt [c] , Jean-Emmanuel Hugonnet [a] , Dominique Mengin-Lecreulx [d] , Delphine Patin [d] , Mélanie Ethève-Quelquejeu* , [b] , Matthieu Fonvielle,* , [a] and Michel Arthur* , [a] Abstract: The bacterial cell wall peptidoglycan contains unusual L and D amino acids assembled in branched peptides. Insight into the biosynthesis of the polymer has been hampered by limited access to substrates and to suitable polymerization assays. Here we report the full synthesis of the peptide stem of peptidoglycan precursors from two pathogenic bacteria, Enterococcus faecium and Mycobacterium tuberculosis, and the development of a sensitive post-derivatization assay for their cross-linking by L,D-transpeptidases. Access to series of stem peptides showed that amidation of free carboxyl groups is essential for optimal enzyme activity, in particular the amidation of diaminopimelate (DAP) residues for the cross-linking activity of the L,D-transpeptidase LdtMt2 from M. tuberculosis. Accordingly, construction of a conditional mutant established the essentiality of AsnB indicating that this DAP amidotransferase is an attractive target for the development of anti-mycobacterial drugs.

Peptidoglycan is an essential and specific component of the bacterial cell wall. [1] The main role of this giant (cell-sized) macromolecule is to protect bacterial cells against the osmotic pressure of the cytoplasm. The peptidoglycan subunit consists of a disaccharide substituted by a pentapeptide stem (figure 1), which is polymerized by glycosyltransferases for the elongation of the glycan chains (all glycosidic bonds are β-1,4) and by D,D- transpeptidases for cross-linking the glycan chains to each other. [2] The amide bond formed by the D,D-transpeptidases links the carbonyl of D-Ala at the 4 th position of an acyl donor stem to the side-chain amino group at the 3 rd position of an acyl acceptor stem (4→3 cross-link). These enzymes are the targets of βlactam antibiotics such as penicillin.

The structure of peptidoglycan is generally conserved in bacteria belonging to the same species, but highly diverse between species, including members of the same genus. [3] The polymorphisms include the N-deacetylation, O-acetylation, and Nglycolylation of either or both GlcNAc and MurNAc. These modifications are mostly, if not exclusively, due to maturation of subunits containing the canonic GlcNAc-MurNAc motif. The most frequent variations in the sequence of the pentapeptide stem occur at the 3 rd (e.g. L-Lys instead of diaminopimelic acid [DAP]) and at the 5 th (e.g. D-Lac instead of D-Ala) positions (figure 1b). Modifications of the pentapeptide stem involve the addition of a side-chain to the 3 rd residue (e.g. D-isoAsn or Gly5) and the amidation of the carboxyl groups (e.g. the α-carboxyl of D-Glu and D-isoAsp or the ε-carboxyl of DAP). A last source of polymorphism originates from the presence of 3→3 instead of 4→3 cross-links in mycobacteria (e.g. Mycobacterium tuberculosis) and in βlactam-resistant mutants generated in vitro (e.g. Enterococcus faecium) (figure 1a). The 3→3 cross-links are formed by transpeptidases of the L,D specificity, which cleave the L-Lys 3 -D-Ala 4 or DAP 3 -D-Ala 4 bond of an acyl donor containing a tetrapeptide stem and form L-Lys 3 →L-Lys 3 or DAP 3 →DAP 3 crosslinks.

Variability in the peptidoglycan structure has been known for decades based on biochemical analyses of the cell wall. [3a] The corresponding enzymes have been described more recently, mostly because the complexity of their substrates has hampered their characterization. [4] Consequently, the biological significance of structural variability is poorly understood. It may involve various selective advantages. [3b] Resistance to vancomycin is mediated by replacement of D-Ala by D-Lac or D-Ser at the 5 th position of peptide stems since this prevents binding of the drug to the precursors. Specific links in mature peptidoglycan are cleaved by hydrolytic enzymes produced by eukaryote hosts, such as lysozyme, which cleaves the MurNAc-GlcNAc β-1,4 bond, or by competing bacteria, such as lysostaphin, which cleaves glycylglycine bonds in the D-Ala 4 →(Gly5)-L-Lys 3 cross-bridges of Staphylococcus aureus. Variations in peptidoglycan structure are therefore potential defense mechanisms against hydrolytic enzymes.

Diversification of the structure of peptidoglycan precursors associated with speciation is thought to lead to a parallel evolution of the substrate specificity of the transpeptidases. [5] Genetic evidence in favor of this hypothesis is limited since impaired maturation of peptidoglycan precursors may have combined effects on numerous peptidoglycan biosynthetic steps in addition to transpeptidation. Scarce evidence has been provided by biochemical studies due to limited access to purified enzymes and substrates. [6] In this study, we have developed the chemical synthesis of peptidoglycan precursor analogues and a postderivatization assay to directly assess the impact of amidation of peptidoglycan precursors on the formation of cross-links by purified L,D-transpeptidases from E. faecium and M. tuberculosis. We show that defects in amidation strongly impair the efficacy of these enzymes indicating that the amidotransferases [7] are attractive targets to develop alternatives to transpeptidase inhibition by β-lactam antibiotics in drug resistant bacteria. Peptidoglycan precursors contain unusual amino acids (D-isoGln, D-Ala, D-isoAsn, amidated DAP), a non-peptide bond linking the γ-carboxyl of D-isoGln to the α-amino group of L-Lys or DAP, and a side-chain linked to the ε-amino group of L-Lys (figure 1b). Thus, solid-support peptide synthesis required access to non-commercial Fmoc-protected amino acids and the use of orthogonal protecting groups for the synthesis of branched peptides (Scheme 1). Synthesis of the Fmoc-protected DAP and amidated DAP has been performed using a cross-metathesis reaction as a key step (Scheme 1a). [8] Synthesis of the other protected amino acids is described in the Supplementary Material. Orthogonal Fmoc and 1-(4,4-dimethyl-2,6-dioxocyclohexylidene)-3-methylbutyl (ivDde) protecting groups were used for sequential assembly of the peptide stem and of the side-chain residue branched at the 3 rd position, respectively (Scheme 1b). Using this approach 9 peptides mimicking peptidoglycan precursors have been synthesized and fully characterized.

A post-functionalization assay was developed to quantify the substrates and the product of the enzymatic cross-linking reaction catalyzed by Ldtfm from E. faecium, the prototypic enzyme of the L,D-transpeptidase family (figure 2a). We took advantage of the presence of a single primary amine on these molecules to specifically introduce a 4-fluoro-7-nitrobenzofurazan group by nucleophilic aromatic substitution. This post-functionalization reaction applied to the crude enzymatic reaction converted the unreacted donor and acceptor substrates as well as the L,D- transpeptidation product (dimer) into fluorescent peptides. The post-functionalized peptides were separated by rpHPLC and detected by fluorescence (figure 2b). Since the fluorescence yield may vary with the acetonitrile concentration required for elution and with the molecular environment of the fluorophore within the peptides, calibration curves were obtained for every substrate and every product (figure 2c). For this purpose, each substrate and each product were individually post-functionalized with 4-fluoro-7nitrobenzofurazan and known amounts of each fluorescent peptide were analyzed by rpHPLC. Access to sensitive determination of the peptides in the 10-to 200-pmol range provided a versatile method to determine the rate of the crosslinking reaction catalyzed by Ldtfm.

Scheme 1. a) Synthetic scheme for the protected DAP and amidated DAP building blocks. i) 5% Grubb's II catalyst, CH2Cl2, RT, 12 h; ii) 3% PtO2 , H2, CH2Cl2/CH3OH/H2O (9/1/1), RT, 12 h; iii) 20% Grubb's II catalyst, CH2Cl2, 70°C, 48 h; iv) PtO2, H2, CH3OH, 4 atm, RT, 18 h. b) Solid-phase-synthesis of the peptidoglycan precursor analogues using orthogonal Fmoc and ivDde protecting groups.

(R) O OtBu R 1 O NH 2 R 2 OH O (S) (CH2)4 -NH HN O NH (S) O HN (R) O OH R 2 R 2 = CO 2 H or CONH 2 (S) BnO 2 C NHFmoc (R) NHBoc CO 2 t Bu (R) NHBoc CONH 2 BnO 2 C (S) NHFmoc (R) CO 2 t Bu NHBoc BnO 2 C (S) NHFmoc (R) CONH 2 NHBoc HO 2 C (S) NHFmoc (R) CO 2 t Bu NHBoc HO 2 C (S) NHFmoc (R) CONH 2 NHBoc i ii iii iv + R 1 = CO 2 tBu or CONH 2 (R) (R) (R) (R) (R) (R) (R) b) a) strand 4→3 Subunit (Disaccharide-pentapeptide) Peptidoglycan subunit

Enterococcus faecium

Mycobacterium tuberculosis

b) a)

The reaction catalyzed by Ldtfm involves two peptidoglycan precursors that act as an acyl donor and as an acyl acceptor (figure 2a). For the donor, we used a linear tetrapeptide that cannot be used as an acyl acceptor since it does not harbor the D-isoAsn residue branched to L-Lys. Conversely, the peptides used as acyl acceptors cannot be used as acyl donors since they do not harbor the essential C-terminal D-Ala residue (D-Ala 4 ). To specifically assess the impact of amidation in the acceptor substrate, we tested a tetrapeptide donor containing a D-isoGln residue (acyl donor 3A) and acceptors containing the four combinations of amidation of the D-isoGlu and D-isoAsp αcarboxyl groups (acyl acceptors 4A to 4D). The rate of formation of peptidoglycan dimers by Ldtfm was the highest for the fully amidated acceptor, corresponding to the amidation status found in the peptidoglycan of the E. faecium host (figures 2d and 2e). The lack of amidation of D-isoGln had a moderate impact on the transpeptidase activity of Ldtfm (36% residual activity). The impact of the lack of amidation was greater for the side-chain D-isoAsn residue (8.4% residual activity), whereas the combination of both modifications almost completely abolished the activity of Ldtfm (0.83% residual activity). No transpeptidation product was observed for substrates fully lacking amidation both in the acyl donor and acceptor substrates (data not shown). In conclusion, amidation of the D-isoGlu and D-isoAsp α-carboxyl groups of the acyl acceptor substrate was essential for optimal formation of peptidoglycan cross-links by Ldtfm in vitro.

Our following objective was to evaluate the role of amidation of the α-and ε-carboxyl groups of D-isoGlu and DAP on the efficacy of formation of 3→3 cross-links by L,D-transpeptidases from M. tuberculosis. We based our analysis on LdtMt2 as a representative of the five L,D-transpeptidase paralogues produced by this species. Substrates containing the four combinations of amidation of the linear tetrapeptide stem of M. tuberculosis were synthesized and independently tested in the quantitative cross-linking assay (figure 3). No cross-linked dimer was observed with substrates lacking amidation of DAP, D-isoGlu, or both. To assess the impact of the lack of amidation of peptidoglycan precursors on the growth of M. tuberculosis, we constructed mutants of strain H37Rv conditionally producing the DAP amidotransferase AsnB (Rv2201). This analysis showed that the amidation of the ε-carboxyl of DAP is required for growth of M. tuberculosis H37Rv. In conclusion, we have developed routes of synthesis of the peptide stems of peptidoglycan precursors that provide access to the full structural diversity found in bacteria, including the presence of DAP or L-Lys at the 3 rd position, the presence or absence of a side-chain, and the amidation of carboxyl groups. We have also developed a sensitive assay for the detection of the products of the cross-linking reaction. Based on these new tools, functional analysis was focused on the impact of amidation of carboxyl groups in the D-isoGlu and DAP residues of peptidoglycan precursors on the activity of L,D-transpeptidases. For the first time, we directly establish that the diversification of the structure of peptidoglycan precursors is associated with a parallel evolution of the substrate specificity of cross-linking enzymes. Amidation of carboxyl groups was essential for the in vitro activity of L,D-transpeptidases from E. faecium and M. tuberculosis. Amidation of DAP was also essential for growth of M. tuberculosis indicating that the amidotransferase AsnB is a potential target for development of new drugs active on multi-drug resistant bacilli.

Substrate

Product Cross-linking efficacy (Used as donor and acceptor) (Dimer) Turnover x 10 6 (s -1 ) % 3B R1=NH2 R2=NH2 (3B/3B) 1,300 ± 100 100

3C R1=OH R2=NH2 (3C/3C) < 26 < 2 3D R1=NH2 R2=OH (3D/3D) < 26 < 2 3E R1=OH R2=OH (3E/3E) < 26 < 2

1-General information

All reagents were obtained from commercial suppliers and used without further purification. Solvents were dried using standard methods and distilled before use. TLC: recoated silica gel thin layer sheets 60F254 plates (Merck) were used for analytical thin layer chromatography. Flash column chromatography was performed on silica gel 60 (40-63 µm, Merck). Optical rotations were measured with a sodium lamp (589 nm) at 20°C on a Perkin Elmer polarimeter. NMR spectra were recorded at 300 K on Bruker AM250 or Bruker Advance II 500 spectrometers. Chemical shifts (δ) are expressed in ppm relative to the residual solvent resonance and coupling constants (J) are in Hertz (Hz).

Multiplicities are reported as follows: singlet (s), doublet (d), triplet (t), multiplet (m), and broad resonance (br). Low resolution mass spectra (LRMS) were obtained on a LCQ Advantage mass spectrometer (ThermoElectron) and high resolution mass spectra (HRMS) were recorded on a TOF mass analyzer under electrospray ionisation.

2-Organic synthesis 2a-Synthesis of Fmoc-D-Glu-NHTrt (Compound 4)

Scheme S1. Synthesis of Fmoc-D-Glu-NHTrt ( 4).

(R)-Benzyl 5-amino-4-((tert-butoxycarbonyl)amino)-5-oxopentanoate (1)

Ethyl chloroformate (0.31 mL, 3.25 mmol) was added dropwise at -20 °C to a solution of Boc-D-Glu(OBn)-OH (1.00 g, 2.96 mmol) and triethylamine (0.45 mL, 3.25 mmol) in anhydrous THF (15 mL).

The solution was stirred for 30 minutes before addition of NH4OH (28%, 1 mL, 14.80 mmol) at 0 °C.

The reaction mixture was stirred at 0 °C for 2 hours. The solvent was removed under reduced pressure and the residue dissolved in dichloromethane. The organic phase was washed with a saturated solution of NH4Cl, dried over MgSO4, filtered and concentrated to afford Boc-D-Glu(OBn)-NH2 1 as a white powder (0.96 g, 96%). 1

(R)-Benzyl 4-((((9H-fluoren-9-yl)methoxy)carbonyl)amino)-5-amino-5-oxopentanoate (2)

A solution of Boc-D-Glu(OBn)-NH2 1 (0.94 g, 2.85 mmol) in HCl (4 N) /dioxane (21 mL) was stirred at room temperature for 2 hours. The reaction mixture was concentrated and the residue was dissolved in H2O/dioxane (80 mL, v/v). NaHCO3 (1.43 g, 17.10 mmol) and FmocCl (0.96 g, 3.70 mmol) were then added. After 2 hours stirring at room temperature, EtOAc was added to the mixture. The organic phase was washed with a saturated solution of NaHCO3, dried over MgSO4, filtered, and concentrated under reduced pressure. A silica gel chromatography (cyclohexane/EtOAc, 8:2) was performed on the residue to obtain the Fmoc-D-Glu(OBn)-NH2 2 as a white powder (0.86 g, 71%). [α]D -2.2° (10 mg/mL, DMF). (C=O), 155.9 (C=O), 143.8, 143.7, 140.7, 136.1, 128.4, 127.9, 127.8, 127.6, 127.0, 125.2, 120.0, 65.6 (CH2) 144.2, 143.8, 143.2, 141.2, 141.1, 136.1, 128.4, 128.1, 127.8, 127.7, 127.3, 126.7, 126.5, 124.8, 124.7, 119.5, 70.1 (Cq), 66.6 (CH2), 66.0 (CH2), 54.6 (CH), 48.4 (CH), 29.8 (CH2), 26.2 (CH2). LRMS: Calcd for C46H40N2NaO5 [M+Na] + 723.2; Found: 722.9. 144. 1, 143.7, 143.6, 141.3, 128.6, 127.9, 127.8, 127.1, 127.0, 125.1, 120.0, 70.6 (Cq) The solution was stirred for 30 minutes. NH4OH (28%, 0.52 mL, 7.75 mmol) was added at 0 °C and the reaction mixture was stirred at 0 °C for 2 hours. The solvent was removed under reduced pressure and the residue was dissolved in dichloromethane. The organic phase was washed with water, dried over MgSO4, filtered and concentrated affording Boc-D-Asp(OBn)-NH2 5 as a white powder (0.46 g, 93%). 1 H NMR (250 MHz, CDCl3): δ 7.38 (br s, 5H, Ar-H), 6.45 (br s, 1H, NH), 5.70 (br s, 1H, NH), 5.43 (br s, 1H, NH), 5.17 (s, 2H, CH2), 4.56 (br s, 1H, CH), 3.10 (dd, J = 17.0 Hz, J = 4.0 Hz, 1H, CH2), 2.74 (dd, 1H, CH2), 1.48 (s, 9H, CH3-Boc). The spectroscopic data were consistent with the literature data for the S enantiomer. [1] (R)-4-Amino-3-((tert-butoxycarbonyl)amino)-4-oxobutanoic acid (6) 10 wt. % Pd/C (0.014 g, 0.13 mmol) was added to a solution of Boc-D-Asp(OBn)-NH2 5 (0.46 g, 1.43 mmol) in anhydrous THF (16 mL). The reaction mixture was hydrogenated overnight under atmospheric pressure. The solution was filtered through celite and evaporated under reduced pressure. Flash chromatography (Dichloromethane/MeOH, 9:1) afforded Boc-D-Asp-NH2 6 as a white powder (0.28 g, 86%). [α]D + 29.4° (10 mg/mL, DMF). 1

(R)-2-(tert-Butoxy)propanoic acid (8)

A suspension of compound 7 (1.80 g, 7.62 mmol) in MeOH (75 mL) was treated with 10 wt. % Pd/C (0.26 g, 2.44 mmol) under 4 bar H2. The reaction mixture was stirred for 12 hours at room temperature.

The residue was filtered through celite and concentrated under reduced pressure to afford D-lactic acid derivative 8 as a colorless oil (1.00 g, 90%). [α]D + 42.3˚ (10 mg/mL, EtOH). 1 H NMR (500 MHz, CDCl3): δ 4.12 (q, J = 7 Hz, 1H, CH), 1.36 (d, J = 7 Hz, 3H, CH3), 1.20 (s, 9H, t Bu). 13 11) [2] A solution of vinyl-glycine 9 2 (0.42 g, 1.06 mmol) in dichloromethane (10 mL) was treated with allylglycine 10 [3] (0.24 g, 0.88 mmol) and Grubb's second generation catalyst (0.04 g, 0.04 mmol). The solution was stirred for 18 hours at room temperature. Dichloromethane was removed under reduced pressure. The obtained residue was purified by flash chromatography (Cyclohexane/EtOAc, 7:3) affording olefin 11 as a colorless oil (0.32 g, 55%). 1 [2] The product 11 (0.32 g, 0.49 mmol) was dissolved in DCM/MeOH/H2O (9:1:1 v/v/v) (33 mL) and PtO2 (0.004 g, 0.02 mmol) was added under H2 atmosphere. The reaction mixture was allowed to stir for 18 hours at room temperature. The solution was filtered through celite and concentrated under reduced pressure. The obtained residue was purified by flash chromatography (dichloromethane/MeOH, 9:1) to afford protected diaminopimelic acid (DAP) 12 as a white powder (0.29 g, 90%). 1 4, 145.2, 142.6, 128.7, 128.2, 126.2, 120.9, 82.5 (Cq), 80.4 (Cq), 67.8 (CH2-Fmoc), 55.9 (CH), 54.7 (CH), 49.7 (CH-Fmoc), 32.5 (CH2), 30.6 (CH2), 28. (R)-2-((tert-Butoxycarbonyl)amino)pent-4-enoic acid (13) [4] To a solution of commercially available (2S)-2-aminopent-4-enoic acid (1.00 g, 8.70 mmol) in 1 M NaOH (20 mL) and dioxane (10 mL) at 0 ˚C was added di-tbutyl dicarbonate (2.28 g, 10.5 mmol). The reaction mixture was allowed to warm to room temperature and stirred for an additional 18 hours. The pH was checked and adjusted to basic when necessary. The reaction mixture was concentrated under reduced pressure and the aqueous phase washed with Et2O (2 x 10 mL). The aqueous phase was acidified to pH = 2 with 2 M H2SO4 and extracted with EtOAc (4 x 20 mL) while saturating the aqueous phase each time with NaCl. The combined organic layers were dried over MgSO4, filtered and concentrated under reduced pressure to afford the product 13 as a colorless oil (1.68 g, 90%). 1 H NMR (250 MHz, CDCl3): δ 5.75-5.61 (d, J = 15 Hz, 1H, Hallyl), 5.14-5.03 (m, 2H, Hallyl), 4.47-4.40 (m, 1H, CH), 2.49-2.43 (m, 2H, CH2), 1.33 (s, 9H, CH3-Boc).

(2S,6R)-2-((((9H-Fluoren-9-yl)methoxy)carbonyl)amino)-7-(tert-butoxy)-6-((tertbutoxycarbonyl)amino)-7-oxoheptanoic acid (12)

(R)-tert-Butyl (1-amino-1-oxopent-4-en-2-yl)carbamate (14)

To a solution of compound 13 (1.00 g, 4.67 mmol) in dry THF (40 mL), triethylamine (0.71 mL, 5.12 mmol) and ethyl chloroformate (0.43 mL, 5.6 mmol) were added at 0 ˚C. The reaction mixture was warmed to room temperature and stirred for 2 hours. The reaction mixture was then cooled to 0 ˚C and treated dropwise with a solution of NH4OH (28%, 1 mL, 14.80 mmol). The solution was stirred for extra 3 hours at room temperature. THF was removed under reduced pressure and the residue was dissolved in dichloromethane. The reaction mixture was washed with brine, dried over MgSO4, filtered and concentrated under reduced pressure. The obtained residue was purified by flash chromatography (Cyclohexane/EtOAc ,7:3) to afford the allyl-glycine 14 as a white solid (0.90 g, 90%). [α]D + 7° (10 mg/mL, CHCl3). 1 H NMR (500 MHz, CDCl3): δ 6.08 (br s, 1H, NH), 5.84-5.68 (m, 1H, Hallyl), 5.44 (br, 1H, NH), 5.19-5.14 (m, 2H, Hallyl), 4.16-4.13 (m, 1H, CH), 2.52-2.47 (m, 2H, CH2) 15) [5] A solution of vinyl-glycine 9 [2] (0.22 g, 0.53 mmol) in dichloroethane (10 mL) was treated with allylglycine 14 (0.27 g, 1.06 mmol) and Grubb's Second Generation Catalyst (0.09 g, 0.16 mmol). The reaction mixture was stirred for 48 hours at 70 ˚C. The solution was cooled to room temperature, treated with DMSO (0.5 mL), and stirred for additional 8 hours. The solution was diluted in dichloromethane (100 mL), washed with water (2 x 20 mL), dried over MgSO4, filtered and concentrated under reduced pressure. The obtained residue was purified by flash chromatography (DCM/MeOH, 9:1) to afford a mixture (0.14 g) of 15 and unreacted 14 with a ratio of 1:2 (15:14) which was engaged in the next step. 1 H NMR (500 MHz, CDCl3): δ 7.81 (d, J = 7.5 Hz, 2H, Ar-H), 7.63 (d, J = 7.5 Hz, 2H, Ar-H), 7.46-7.38 (m, 9H, Ar-H), 6.1 (br, 1H, NH), 5.79 (br, 1H, NH), 5.69-5.68 (m, 2H, Hallyl), 5.30 (br, 1H, NH), 5.18 (s, 2H, CH2-Ar), 4.89 (m, 1H, CH-Fmoc or CH), 4.43-4.31 (m, 2H, CH2-Fmoc), 4.26-4.10 (m, 1H, CH-Fmoc or CH), 2.63-2.37 (m, 2H, CH2), 1.46 (s, 9H, CH3-Boc). LRMS: Calcd for C34H38N3O7 [M+H] + 600.2; Found: 600.1.

(2S,6R)-2-((((9H-Fluoren-9-yl)methoxy)carbonyl)amino)-7-amino-6-((tert-butoxycarbonyl)amino)-7oxoheptanoic acid (16)

The mixture 14:15 (0.22 g) was dissolved in MeOH (15 mL) and treated with PtO2 (0.10 g, 0.44 mmol) under 4 bar H2. The reaction mixture was stirred for 24 hours at room temperature. The mixture was filtrated through celite and concentrated under reduced pressure. The obtained residue was purified by flash chromatography (DCM/MeOH/H2O, 8:2:1) to afford amidated DAP 16 as a white powder (0.06 g, 30% over 2 steps). [α]D + 2˚ (5 mg/mL, MeOH). 1 H NMR (500 MHz, MeOD): δ 7.76 (d, J = 7.5 Hz, 2H, Ar-H), 7.65-7.62 (m, 2H, Ar-H), 7.37-7.27 (m, 4H, Ar-H), 4.33-4.31 (m, 2H, CH2-Fmoc), 4.20-4.17

3-Solid-phase synthesis of linear peptides (3A to 3E)

Peptides were manually assembled on a Fmoc-D-Ala-Wang resin (0.80 mmol.g -1 , 75 mg). Coupling reactions were performed in 2 mL of anhydrous DMF containing 3 or 1.5 molar equivalent excess of commercial and non-commercial Fmoc-amino acids, respectively, 3 equivalents of K-Oxyma, and 6 equivalents of DIC and DIPEA. Each coupling was performed twice for 5 hours and 12 hours. Fmoc was removed twice (5 minutes and 7 minutes) with a 20% solution of piperidine in DMF. Final deprotection of acid labile protecting groups and cleavage from the resin were carried out under gentle agitation at room temperature for 2 hours with 2 mL of a TFA solution containing DCM, TIPS and water (80:20:5:5 v/v/v/v). The solution was filtered and the resin was washed with 1 mL of TFA. The TFA solutions were pooled and evaporated under reduced pressure. The crude product was dissolved in a 10% acetic acid solution (5 mL) and extracted with chloroform (3 x 10 mL). The aqueous solution was lyophilized and the peptides were purified by rpHPLC on a 5 µm Nucleosil preparative C-18 column (22 x 250 mm) using a linear gradient (0 to 100% buffer B) applied between 10 minutes and 40 minutes (Buffer A: 0.1 % TFA in H2O; buffer B: 0.1 % TFA in CH3CN; 10 mL.min -1 ). Peptide-containing fractions were identified at 214 nm and analyzed by mass spectrometry (Supplementary figure S1). Peptides were lyophilized and dissolved in water at a final concentration of 10 mg.mL -1 . Purity was assessed by rpHPLC (analytical C18 Nucleosil column, 3 µm, 4.6 x 250 mm) using a linear gradient (0 to 50 buffer B) applied between 10.5 and 40.5 min (Buffer A: 0.1 % TFA in H2O; buffer B: 0.1 % TFA in CH3CN; 1 mL.min -1 ) (Supplementary figure S2). Peptide concentration was determined in duplicate by acid hydrolysis and injection into a Hitachi L8800 amino acid analyzer equipped with a 2620 MSC-PS column.

HO (R) NH (S) HN (R) NH (S) HN O O NH 2 O O (CH2)4 H 2 N O (R) OH O 3A HO (R) NH (S) HN (R) NH (S) HN O O NH 2 O O (CH2)3 (R) O (R) OH O 3B H 2 N H 2 N O HO (R) NH (S) HN (R) NH (S) HN O O OH O O (CH2)3 (R) O (R) OH O 3C H 2 N H 2 N O HO (R) NH (S) HN (R) NH (S) HN O O NH 2 O O (CH2)3 (R) O (R) OH O 3D H 2 N HO O HO (R) NH (S) HN (R) NH (S) HN O O OH O O (CH2)3 (R) O (R) OH O 3E H 2 N HO O
4-Solid-phase synthesis of branched peptides (4A to 4D)

HO (R) NH (S) HN (R) NH (S) HO O O NH 2 O O (CH2)4 N H O (R) H 2 N O H 2 N O 4A HO (R) NH (S) HN (R) NH (S) HO O O OH O O (CH2)4 N H O (R) H 2 N O H 2 N O 4B HO (R) NH (S) HN (R) NH (S) HO O O NH 2 O O (CH2)4 N H O (R) H 2 N O HO O 4C HO (R) NH (S) HN (R) NH (S) HO O O OH O O (CH2)4 N H O (R) H 2 N O HO O

4D

Branched peptides were synthesized via divergent Fmoc solid phase peptide synthesis using orthogonal protecting groups on the lysine residue. The starting material was a commercial Wang resin containing L-Lys with the α and ε NH2 groups protected with Fmoc and ivDde groups, respectively.

Peptides were manually assembled on the resin (0.69 mmol.g -1 , 75 mg), starting with the linear tripeptide to afford O t Bu-D-Lac-L-Ala-D-iGlx-L-Lys(ivDde)-WANG resin, as described above. Then, the ε NH2 group of L-Lys was deprotected by hydrazinolysis of the ivDde protective group (5% of hydrazine mono-hydrate in DMF, 3 x 15 minutes). Fmoc-D-isoAsn or Fmoc-D-isoAsp was incorporated and the final deprotection steps were performed as described above.

5-Mass spectrometry analyses of the peptide

Peptide

7-Protein purification

The catalytic domain of Ldtfm (residues 341 to 466) and a soluble form of LdtMt2 (residues 55 to 408)

were produced in Escherichia coli BL21(DE3) and purified by metal affinity and size-exclusion chromatography, as previously described. [6] Protein concentration was determined by the Bradford method (Bio-Rad protein assay).

8-Cross-linking assay

Formation of 3→3 cross-links was determined in 140 µl of phosphate buffer (15 mM, pH 7.0) containing Ldtfm (2.5 µM), the donor peptide 3A (30 µM), and one of four branched acceptor peptides (4A, 4B, 4C, or 4D; 30 µM). LdtMt2 (10 µM) was independently incubated with one of four DAP-containing tetrapeptides (3B, 3C, 3D, or 3E; 100 µM), which were each used both as a donor and as an acceptor by the L,D-transpeptidase. The reaction was allowed to proceed at 37°C and aliquots of 4 µl were withdrawn at various times (0 to 120 min). For post-derivatization, each aliquot was incubated with Macherey-Nagel) at a flow rate of 1 mL.min -1 . For the substrates and products of Ldtfm, a three-step gradient with buffer B (50% ACN, 0.035% TFA) was applied between 10 and 15 min (0 to 40%), 15 and 20 min (40 to 60%), and 20 and 40 min (60 to 100%). For the substrates and products of LdtMt2, a threestep gradient with buffer B was applied between 10 and 12.5 min (0 to 20%), 12.5 and 32.5 min (20 to 60%), and 32.5 and 40 min (60 to 100%). Derivatized peptides were detected by fluorescence (λex = 470 nm; λem = 530 nm).

To determine the relative fluorescence intensity of the substrates and products, authentic peptides (6 to 240 pmol) were derivatized and independently analyzed by rpHPLC, as described above.

For this approach, dimers were obtained by incubation of Ldtfm or LdtMt2 with their respective substrates and purified by rpHPLC. The concentration of the peptides was determined twice by acid hydrolysis and injection on a Hitachi L8800 amino acid analyzer equipped with a 2620 MSC-PS column.

Figure 1 .

 1 Figure 1. Peptidoglycan structure. a) Peptidoglycan is a giant mesh-like polymer that completely surrounds bacterial cells. b) Peptidoglycan is polymerized from disaccharide-pentapeptide subunits, which are assembled in the cytoplasm. MurNAc, N-acetyl muramic acid; MurNGlyc, N-glycolyl muramic acid; GlcNAc, N-acetyl glucosamine; D-isoGln, D-iso-glutamine; D-isoAsn, D-iso-asparagine; DAPNH2, diaminopimelic acid amidated at the ε position.

Figure 2 .

 2 Figure 2. Post-functionalization assay for the cross-linking activity of peptidoglycan transpeptidases. a) Reaction catalyzed by the L,D-transpeptidase Ldtfm . Inset, post-functionalization reaction. b) Separation by rpHPLC of the post-functionalized substrates 3A and 4A and of the reaction product (dimer 3A/4A), which were detected by fluorescence (λ ex = 470 nm; λ em = 530 nm). c) Calibration curves for quantitative determination of the substrates (left panel) and reaction products (right panel). d) Kinetics of dimer synthesis by Ldtfm . e) Impact of amidation of the acyl acceptor on the cross-linking efficacy of Ldtfm .

Figure 3 .

 3 Figure 3. Impact of impaired peptidoglycan precursor amidation on the activity of M. tuberculosis L,D-transpeptidase LdtMt2. a) Transpeptidation reaction catalyzed by LdtMt2. b) In vitro cross-linking activity of LdtMt2. c) Impact of impaired amidation of DAP by AsnB (Rv2201) on the growth of M. tuberculosis H37Rv. Ten-fold dilutions of cultures of mutants Rv2201-TetON-2 and Rv2201-TetON-6 were spotted on the indicated media showing that depletion of AsnB in the absence of anhydrotetracycline prevents growth.

  the peptide stem of peptidoglycan precursors and a sensitive fluorescent cross-linking assay were developed to assess the impact of structural variability on peptidoglycan polymerization. In the search for new targets for anti-mycobacterial drug development, this strategy was applied to the evaluation of diaminopimelate amidation in Mycobacterium tuberculosis, revealing the essential role of the AsnB amidotransferase for peptidoglycan transpeptidation both in vitro and in vivo. Flora Ngadjeua # , Emmanuelle Braud # , Saidbakhrom Saidjalolov, Laura Iannazzo, Dirk Schnappinger, Sabine Ehrt, Jean-Emmanuel Hugonnet, Dominique Mengin-Lecreulx, Delphine Patin, Mélanie Ethève-Quelquejeu*, Matthieu Fonvielle,* and Michel Arthur

  H NMR (250 MHz, CDCl3): δ 7.39 (br s, 5H, Ar-H), 6.23 (br s, 1H, NH), 5.43 (br s, 1H, NH), 5.28 (d, J = 7.2 Hz, 1H, NH), 5.16 (s, 2H, CH2), 4.26-4.19 (m, 1H, CH), 2.68-2.43 (m, 2H, CH2), 2.27-2.13 (m, 1H, CH2), 2.03-1.88 (m, 1H, CH2), 1.46 (s, 9H, CH3-Boc). 13 C NMR (125 MHz, CDCl3): δ 175.7 (C=O), 172.8 (C=O), 156.3 (C=O), 136.1, 128.1, 127.7, 79.3 (C-Boc), 65.9 (CH2), 53.5 (CH), 30.0 (CH2), 27.3 (CH3), 27.2 (CH2). LRMS: Calcd for C17H24N2NaO5 [M+Na] + 359.3; Found: 359.3.

  1 H NMR (250 MHz, DMSO): δ 7.89 (d, J = 7.2 Hz, 2H, Ar-H), 7.73 (d, 2H, Ar-H), 7.47-7.29 (m, 9H, Ar-H), 7.07 (s, 1H, NH), 5.10 (s, 2H, CH2), 4.30-4.21 (m, 3H, CH2-Fmoc and CH-Fmoc), 4.06-3.92 (s, 1H, CH), 2.39 (t, J = 7.2 Hz, 2H, CH2-CO), 2.00-1.76 (m, 2H, CH2-CH). 13 C NMR (125 MHz, CDCl3): δ 173.2 (C=O), 172.1

  , 65.4 (CH2), 53.7 (CH), 46.7 (CH), 30.2 (CH2), 27.1 (CH2). LRMS: Calcd for C27H26N2NaO5 [M+Na] + 481.4; Found: 481.3. (R)-Benzyl 4-((((9H-fluoren-9-yl)methoxy)carbonyl)amino)-5-oxo-5-(tritylamino)pentanoate (3)To a mixture of Fmoc-D-Glu(OBn)-NH2 (2) (0.68 g, 1.60 mmol) and trityl alcohol(4.16 g, 16.00 mmol) in acetic acid(5.6 mL), sulfuric acid (51 µL, 0.96 mmol) and acetic anhydride (4.00 mmol) were added at 50 °C. The reaction mixture was stirred at 50 °C for 3.5 hours and diluted with EtOAc. The organic phase was washed with a saturated solution of NaHCO3, dried over MgSO4, filtered and concentrated under reduced pressure. Silica gel chromatography (cyclohexane/EtOAc, 7:3) afforded Fmoc-D-Glu(OBn)-NHTrt 3 as a white powder (0.82 g, 73%). [α]D + 31.2° (10 mg/mL, MeOH).1 H NMR (250 MHz, CDCl3): δ 7.78(d, 2H, J = 7.5 Hz, Ar-H), 7.60-7.57 (m, 2H, Ar-H), 7.46-7.28 (m, 24H, Ar-H), 5.64-5.62 (m, 1H, NH), 5.14 (br s, 2H, CH2), 4.40 (m, 3H, CH2-Fmoc and CH-Fmoc or CH), 4.22-4.19 (m, 1H, CH-Fmoc or CH), 2.61-1.87 (m, 4H, 2 CH2). 13 C NMR (125 MHz, CDCl3): δ 172.8 (C=O), 171.6 (C=O), 157.2 (C=O),

  % Pd/C (0.04 g, 0.38 mmol) was added to a solution of Fmoc-D-Glu(OBn)-NHTrt 3 (0.40 g, 0.57 mmol) in anhydrous THF (6 mL). The solution was hydrogenated overnight under atmospheric pressure. The catalyst was removed by filtration through celite and the filtrate was evaporated. Silica gel chromatography (dichloromethane/MeOH, 95:5) afforded the Fmoc-D-Glu-NHTrt 4 as a white powder (0.29 g, 83%). [α]D + 42.6° (10 mg/mL, MeOH).1 H NMR (250 MHz, CDCl3): δ 7.78(d, J = 5.2 Hz, 2H, Ar-H), 7.60-7.57 (m, 2H, Ar-H), 7.55-7.42 (m, 2H, Ar-H), 7.39-7.23 (m, 17H, Ar-H), 5.66 (d, J = 6.5 Hz, 1H, NH),4.49-4.39 (m, 3H, CH2-Fmoc and CH), 4.22-4.16 (t, J = 6.8 Hz, 1H, CH-Fmoc), 2.53-2.07 (m, 3H, CH2), 1.95-1.83 (m, 1H, CH2).13 C NMR (125 MHz, CDCl3): δ 176.4 (C=O), 170.4 (C=O), 156.8 (C=O),

  Scheme S2. Synthesis of Boc-D-Asp-NH2 (6).

  Scheme S3. Synthesis of D-lactic acid derivate (8).

  Scheme S4. Synthesis of DAP derivative (12).

  H NMR (500 MHz, CDCl3): δ 7.80 (d, J = 7.5 Hz, 2H, Ar-H), 7.64 (d, J = 5 Hz, 2H, Ar-H), 7.46-7.34 (m, 9H, Ar-H), 5.72-5.68 (m, 2H, Hallyl), 5.53 (d, J = 7.5 Hz, 1H, NH), 5.28-5.10 (m, 3H, CH2-Bn and NH), 4.99-4.94 (m, 1H, CH), 4.45-4.39 (m, 2H, CH2-Fmoc), 4.30-4.22 (m, 2H, 2 CH), 2.62-2.43 (m, 2H, CH2), 1.45 (s, 18H, CH3-t Bu/Boc). HRMS: Calcd for C38H45N2O8 [M+H] + 657.3170; Found: 657.3176.

  H NMR (500 MHz, MeOD): δ 7.75(d, J = 7.8 Hz, 2H, Ar-H), 7.64 (d, J = 7.8 Hz, 2H, Ar-H), 7.39-7.26 (m, 2H, Ar-H), 7.00-6.79 (m, 2H, Ar-H), 4.36-4.31 (m, 2H, CH2-Fmoc or 2 CH), 4.21-4.07 (m, 2H, CH2-Fmoc or 2 CH), 3.97-3.93 (m, 1H, CH), 1.89-1.59 (m, 6H, CH2), 1.44 (s, 9H, CH3), 1.43 (s, 9H, CH3). 13 C NMR (125 MHz, MeOD): δ 173.8 (C=O), 158.5 (C=O), 158.1 (C=O), 145.

  Scheme S5. Synthesis of D-Allyl-Glycine (14).

  Scheme S6. Synthesis of amidated DAP (16).

  (m, 1H, CH-Fmoc), 4.05-3.99 (m, 2H, 2CH), 1.89-1.49 (m, 6H, CH2) 1.40 (s, 9H, CH3-Boc). 13 C NMR (125 MHz, MeOD): δ 178.1 (C=O), 158.5 (C=O), 157.8 (C=O), 145.4 (Cq), 145.2 (Cq), 142.6 (Cq), 128.8 (CH-Fmoc), 128.2 (CH-Fmoc), 126.2 (CH-Fmoc), 120.9 (CH-Fmoc), 80.6 (Cq), 67.9 (CH2-Fmoc), 56.6 (CH), 55.8 (CH), 48.4 (CH-Fmoc), 33.2 (CH2), 33.1 (CH2), 28.7 (CH3-Boc), 23.30 (CH2). HMRS: Calcd for C27H32N3O7 [M -H] -510.2246; Found: 510.2245.

HO

HO

  Mass spectrometry analysis of peptides. Left panels, mass spectrometry; right panels, tandem mass spectrometry.

  Analysis of peptides by rpHPLC.

the 4 -

 4 fluoro-7-nitrobenzofurazan probe (12.5 mM; NBDF; SIGMA®F5883) for 8 min at 65°C in phosphate buffer (100 mM, pH 7.5) containing EDTA (1 mM) and β-mercaptoethanol (10 mM) in a total volume of 12.5 µl. The excess of unreacted NBDF was removed in a three-step extraction procedure comprising (i) acidification with citric acid (10% v/v) (total volume 162 µl), (ii) three extractions with 250 µl of isoamyl alcohol/chloroform (50/50 v/v), and (iii) five washings with 250 µl of chloroform. A portion of the aqueous phase containing the substrates and products (60 µl and 30 µl for the analyses of the reactions catalyzed by Ldtfm and LdtMt2, respectively) was mixed with an equal volume of the (H2O, TFA 0.05%) and injected into a C18 rpHPLC column (Nucleosil ®100-3, EC 250/4.6;

Formula for [M+H] + Calc.

	p	p				,	,			,																								p		p			,	,	,
	T: + p ESI Full ms [150,00-2000,00]																											T: + p ESI Full ms2 489,30@cid28,00 [150,00-2000,00]
		100					489,27																										100			383,13
		95																																	95
		90																																	90
		85																																	85
		80																																	80
		75																																	75
		70																																	70
		65																																	65
	Relative Abundance	40 45 50 55 60																																Relative Abundance	40 45 50 55 60			472,20
		35																																	35
		30																																	30
		25																																	25			400,07
		20																																	20		195,13	489,13
		15													977,20																			15			240,00
		10																																	10			346,20
																																							218,00
		0 5	217,07	284,33	391,13		511,27	648,87 740,93	849,07	1048,13		1222,13	1402,47	1465,20		1636,93	1709,53	1822,73	1912,67		0 5	177,40	201,00	222,27	257,00 271,93	284,07	311,07	328,93	355,07 365,07	417,20	454,07 444,33	500,93
			200			400			600				800			1000			1200			1400			1600				1800		2000				180		200	220	240	260	280	300	320	340	360	380	400	420	440	460	480	500
																m/z																						m/z
																																	p p			_p		_
	T: + p ESI Full ms [250,00-2000,00]																											T: + p ESI Full ms2 532,30@cid26,00 [150,00-550,00]
		100				532,20																										100					426,07	515,13
		95																																95
		90																																90
		85																																85
		80																																80
		75																																75
		70																																70
		65																																65
	Relative Abundance	40 45 50 55 60																															Relative Abundance	40 45 50 55 60
		35																																35					443,07
		30																																30
		25													1063,20																		25					389,13
		20																																20
		15																																15					498,13
		10						660,27																									10					283,07	300,07
		0 5	327,27	404,27	515,20	554,27	682,40	846,07	935,87	1117,20	1191,20	1328,67		1505,47	1595,33	1722,60	1861,73	1967,60	0 5		261,13 265,07	290,27	310,07	327,00	337,33	355,13	372,20	409,07 423,20	438,27	453,00	470,20	487,13	532,13
			300		400	500		600	700		800		900	1000	1100		1200	1300	1400		1500			1600	1700	1800	1900	2000				260		280	300	320	340	360	380	400	420	440	460	480	500	520
																m/z																						m/z
	p	y p			g		,	,			,	,			,																			g p p			g g
	T: + p ESI Full ms [250,00-2000,00]																											T: + p ESI Full ms2 533,10@cid27,00 [150,00-550,00]
	100				533,13																										100					301,07	444,00
		95																																95
		90																																90
		85																																85
		80																																80
		75																																75					390,07
		70																																70
		65																																65
	Relative Abundance	45 50 55 60																															Relative Abundance	45 50 55 60
		40																																40
		35																																35			172,07
		30																																30					515,00
		25																																25					261,07	426,07
		20																																20
		15																																15
		10																																10					283,07
		0 5	376,27 362,00	503,07	662,13 604,27 704,20	789,07	893,93		1065,13 1127,20 1020,33	1194,47	1306,60	1487,73	1587,60	1661,27			1827,87	1914,20			0 5	155,07		199,07	227,00	244,07	265,00	327,13	342,93	372,07	409,07	462,00	479,80	497,07	533,00
			300		400	500	600	700		800		900		1000	1100	1200	1300	1400	1500	1600	1700		1800	1900	2000				160	180	200	220	240	260	280	300	320	340	360	380	400	420	440	460	480	500	520	540
																m/z																							m/z
	T: + p ESI Full ms [250,00-2000,00]																												T: + p ESI Full ms2 533,30@cid25,00 [250,00-2000,00]
		100				533,20																												100			516,07
		95																																	95
		90																																	90
		85																																	85
		80																																	80			427,07
		70 75																																	70 75			Found
	Relative Abundance	65 35 40 45 50 55 60			3A 3B 3C									C20H37N6O8 + C21H38N7O9 + C21H37N6O10 +									65 489.27 532.27 533.26 35 40 45 50 55 60 Relative Abundance			489.27 532.20 533.13	444,00
		25 30 10 15 20			3D 3E									C21H37N6O10 + 1065,13 C21H36N5O11 +									533.26 25 30 534.24 10 15 20			533.20 534.13	390,13	533,13
		0 5	300 328,13	4A 400 500 516,13 427,00	600 555,20 595,07	700 705,13	800 822,20	900 887,60	C21H38N7O9 + 1000 1100 1200 1300 1400 1087,20 1192,07 937,00 1332,13 1450,53 1500 1526,93	1600 1597,13	1700	1800 1785,33	532.27 1900 2000 1897,73	0 5	260 262,13 271,87 280 284,07 289,00 300 301,07	320 328,13 532.27 340 360 372,93 380 382,00 398,67 400 355,93	420 409,13	440	460 452,80	471,13	480 488,07	500 498,20	520 520,33	540	560
					4B									C21H37N6O10 + m/z									533.26				533.27	m/z
					4C									C21H37N6O10 +									533.26				533.27
					4D									C21H36N5O11 +									534.24				534.20

Acknowledgements

This work was supported by the project NAPCLI from the JPI AMR program to MA.

Supporting Information

Critical impact of peptidoglycan precursor amidation on the activity of L,Dtranspeptidases from Enterococcus faecium and Mycobacterium tuberculosis

Flora Ngadjeua, Emmanuelle Braud, Saidbakhrom Saidjalolov, Laura Iannazzo, Dirk Schnappinger, Sabine Ehrt, Jean-Emmanuel Hugonnet, Dominique Mengin-Lecreulx, Delphine Patin, Mélanie Ethève-Quelquejeu, Matthieu Fonvielle, and Michel Arthur

9-Conditional production of the DAP amidase AsnB in M. tuberculosis

To generate mutants that conditionally produce AsnB (Rv2201), asnB was tagged in situ with a DAS+4 tag as described. [7] The resulting strain was transformed with plasmids that express the DAS+4recognition protein SspB under the control of a tetracycline-controlled promoter and integrate into the chromosomal Giles phage attachment site. We used two regulated SspB-encoding plasmids (TetON-2 and TetON-6) that mediate SspB production only in the absence of anhydrotetracycline (atc).

In the resulting mutants, designated AsnB-TetOn-2 and AsnB-TetOn-6, SspB-mediated AsnB degradation occurs in the absence of atc.