Emanuele Conte

Gianpiero Landolfi

Gabriele Vincelli

Alessandra Stefan

Alejandro Hochkoeppler
email: a.hochkoeppler@unibo.it

Prof Alejandro Hochkoeppler

pGOODs: new plasmids for the co-expression of proteins in

Keywords: ColE1 origin, compatible plasmid, Escherichia coli, expression vector, p15A origin

  L'archive ouverte pluridisciplinaire

Introduction

The study of protein-protein interactions is a major challenge in modern biochemistry and molecular biology, and important efforts have been made to design and construction of tools for the rapid identification of interacting proteins. An important advance in this field was the introduction of the yeast two-hybrid system [START_REF] Fields | A novel genetic system to detect protein-protein interactions[END_REF]. More recently, bacterial two-hybrid systems have also been developed [START_REF] Karimova | A bacterial two-hybrid system based on a reconstituted signal transduction pathway[END_REF][START_REF] Joung | A bacterial two-hybrid selection system for studying protein-DNA and protein-protein interactions[END_REF].

Both methodologies are suitable for extensive screenings of interactors.

Generally, two-hybrid systems rely on the use of fusion proteins: the proteins to be tested are fused, generating hybrids, to appropriate reporters of the intervening interaction. Unfortunately, this approach cannot be applied to those proteins (e.g. of small molecular mass) whose folding is significantly altered by the fusion with a reporter. Other powerful techniques relying on protein reporters, such as FRET [START_REF] Stryer | Energy transfer: a spectroscopic ruler[END_REF][START_REF] Ha | Probing the interaction between two single molecules: fluorescence resonance energy transfer between a single donor and a single acceptor[END_REF], suffer from the same limitations. A possible solution to this drawback is the co-expression of native proteins, whose interaction has yet to be tested and studied in detail.

Moreover, protein-DNA interactions can also be studied by co-transforming a bacterial host with: i) a plasmid bearing the target DNA; ii) a vector suitable for the expression in vivo of the protein of interest. This method was reported in an elegant study by Müller-Hill, who dissected the interaction of lac repressor with operators [START_REF] Lehming | The interaction of the recognition helix of lac repressor with lac operator[END_REF]. In recent years, different co-expression vectors have been constructed and described [START_REF] Zhang | A novel high-copy plasmid, pEC, compatible with commonly used Escherichia coli cloning and expression vectors[END_REF][START_REF] Walia | Development of expression vectors for Escherichia coli based on the pCR2 replicon[END_REF][START_REF] Zeng | Over-producing soluble protein complex and validating protein-protein interaction through a new bacterial co-expression system[END_REF]. These vectors are useful because they are compatible with the most commonly used expression plasmids for Escherichia coli, containing a ColE1type origin of replication (ori). In particular, the pEC plasmid [START_REF] Zhang | A novel high-copy plasmid, pEC, compatible with commonly used Escherichia coli cloning and expression vectors[END_REF] contains the pEIB1 ori, an L-arabinose-inducible promoter, and a kanamycinresistance cassette. This vector is a stable and high-copy number plasmid in E.

coli. The pCR2 series comprises plasmids containing the pCR2 ori from Corynebacterium renale, the lac or the T7 promoter, and an ampicillin-or a chloramphenicol-resistance cassette [START_REF] Walia | Development of expression vectors for Escherichia coli based on the pCR2 replicon[END_REF]. These vectors were reported as high-copy number and were successfully used for the expression in E. coli of GFP or human interferon-γ. The pHEX plasmid contains the p15A ori, the T7 promoter, and a kanamycin-resistance cassette [START_REF] Zeng | Over-producing soluble protein complex and validating protein-protein interaction through a new bacterial co-expression system[END_REF]. This vector was successfully used to co-express two proteins from Mycobacterium tubercolosis H37Rv in E. coli. While useful for co-expression experiments, these plasmids do not provide either a low-copy number expression system, or a multiple-cloning-site (MCS) identical to one already available in another plasmid. Importantly, a co-expression vector featuring both these properties would allow: i) the easy shuttling of clones between low-and high-copy number expression vectors sharing the same MCS; ii) the co-expression of two proteins, one in excess of the other, and vice versa. To take advantage of these features, we have constructed the pGOOD expression vector, featuring the p15A ori, a tetracycline-resistance cassette, the lac repressor-promoter-operator regulatory elements, and the MCS from pTrcHisB. This MCS is identical to the one present in the pBADHis series, making the entry of two clones into pBADHis and into pGOOD easily reversable. In addition, we have constructed two additional plasmids, i.e. pGOOD1 and pGOOD2, both devoid of the lacI gene, and respectively containing the Oid and the O3 lac operator. The expression of genes hosted in these plasmids can be tightly controlled by the lac repressor produced from a different vector, e.g. pBADHis.

This paper describes the co-expression of proteins in E. coli using pGOODs and pBADHisB, along with the stability features of the new plasmids.

Materials and methods

Bacterial strains, plasmids and growth media

All the experiments were performed using Escherichia coli TOP10 (genotype: F -, mcrA, lacX74,80lacZ M15,deoR,endA1,recA1,araD139,galU,galK,rpsL,nupG). The plasmids pTrcHisB and pBADHisB were obtained from Invitrogen (Carlsbad, USA). The pACYC184 vector was a generous gift of New England Biolabs (Ipswich, USA). The pBAD-α1160 and pBAD-ε243 plasmids were previously described [START_REF] Bressanin | Proteolysis of the proofreading subunit controls the assembly of Escherichia coli DNA polymerase III catalytic core[END_REF]. The DNA fragment coding for ε243 was excised from pBAD (using NcoI and PstI enzymes) and inserted into pGOOD (NcoI and PstI sites), yielding pGOOD-ε243. Bacteria were grown, unless specified, at 37 °C using LB medium (tryptone, yeast extract, and NaCl at 10, 5, and 10 g/l, respectively). The growth medium was supplemented, when appropriate, with ampicillin and/or tetracycline at 100 and 10 μg/ml, respectively.

DNA manipulation

DNA restriction, ligation, and transformation of E. coli were performed according to standard procedures [START_REF] Sambrook | Molecular Cloning: A Laboratory Manual[END_REF]. The partial digestion of pTrcHisB with SspI was performed at 37 °C for 4 h using an enzyme concentration 20 times lower than that recommended by the manufacturer for standard restrictions. In addition, the SspI enzyme was used in a sub-optimal reaction buffer (20 mM Tris/acetate, 10 mM magnesium acetate, 50 mM potassium acetate, 1 mM dithiothreitol, pH 7.9), in the presence of which activity is 50% when compared to the maximal value.

Co-expression experiments

E. coli TOP10 was transformed with the pBAD-α1160 vector. Transformants were selected using LB/ampicillin medium. They were then purified and used to obtain electrocompetent cells into which the pGOOD-ε243 plasmid was introduced. Overnight cultures of co-transformants (selected and purified with LB-ampicillin-tetracycline medium) were diluted (1:500) into fresh medium. At late logarithmic phase (5 h after dilution of pre-cultures) inducer(s) were added to the culture medium and cells harvested 3 h after inducer(s) addition. Total protein extracts were obtained by sonication and the soluble fraction isolated by centrifugation (16,000 g, 20 min). Gel filtration was performed with a 1.6x70 cm Superdex 200 column, calibrated with HMW and LMW Gel Filtration Calibration kits (GE Healthcare). According to the calibration, fractions 6, 42, and 52 contained proteins featuring molecular mass equal to 819, 52 and 24 kDa, respectively. The pGOOD-ε243-θ plasmid was obtained by inserting (using PstI and EcoRI sites) into pGOOD-ε243 a synthetic gene containing the araB-araA intergenic region and the holE gene. Gene synthesis was performed by Entelechon GmbH (Regensburg, Germany).

Stability of pGOOD in vivo

To assess the stability of pGOOD in E. coli TOP10, pre-cultures grown in selective medium (LB supplemented with tetracycline) were diluted in LB devoid of tetracycline and propagated for 30 generations. At intervals corresponding to 10 generations, aliquots of the cultures were withdrawn, diluted and spread onto LB and LB+tetracycline medium. The fraction of tetracycline-resistant individuals was then determined. Each aliquot of the cultures was also used to extract and purify pGOOD; after gel electrophoresis, the amount of pGOOD recovered from each sample was estimated with Quantity One software (Bio-Rad, Hercules, USA).

Assay for mutator phenotype

E. coli TOP10 was co-transformed with pGOOD1 containing an insert (NcoI and PstI sites) coding for the D12A variant of DNA Pol-III ε subunit. Mutation of the catalytic residue D12 should abolish the proofreading activity of this subunit [START_REF] Fijalkowska | Mutants in the exo motif of Escherichia coli dnaQ: defective proofreading and inviability due to error catastrophe[END_REF]. E.coli TOP10/pGOOD1-εD12A was then cotransformed with pBAD containing (between NcoI and PstI sites) the lacI gene or a lacI ts mutant previously described by [START_REF] Bukrinsky | Multicopy expression vector based on temperature-regulated lac repressor: expression of human immunodeficiency virus env gene in Escherichia coli[END_REF]. Cotransformants were pre-cultured at 30 °C in LB medium supplemented with 13 mM arabinose; pre-cultures were then diluted (1:500) in fresh arabinosecontaining LB medium and grown at 30 °C for about 10 generations. Finally, the cultures were diluted (1:500) in fresh arabinose-free LB medium and grown at 42 °C for a further 10 generations. All growth media were used devoid of IPTG.

The frequency of mutant individuals was assayed by spreading aliquots of the cultures (grown at 30 or at 42 °C) onto LB-agar Petri dishes supplemented or not with kanamycin (30 μg/ml). It is important to note that resistance to kanamycin can be a more sensitive phenotype than rifampicin-resistance [START_REF] Monteiro | Environmental and genetic factors affecting mutability to aminoglycoside antibiotics among Escherichia coli K12 strains[END_REF]. The frequency of mutants was determined by considering three independent cultures of each sample.

Results and discussion

To construct pGOOD, the pACYC184 vector was subjected to total digestion with BstZ17I and MscI restriction enzymes (Fig. 1), yielding three DNA fragments of 2345 (BstZ17I-MscI), 1042 (MscI-MscI) and 858 (MscI-BstZ17I) bp, respectively (Fig. 1). The digested DNA was electrophoresed and the 2345 bp fragment containing the p15A ori and the tetracycline-resistance marker was recovered and purified (Fig. 1). The pTrcHisB vector was in parallel subjected to total digestion with BStZ17I and AlwNI restriction enzymes, and the reaction products were further treated with SspI enzyme. In this case, a partial digestion with SspI was performed to recover a 2480 bp fragment containing the lac repressor, promoter-operator, the MCS and the transcriptional terminators of pTrcHisB (Fig. 1). This fragment was purified by gel electrophoresis, and then ligated to the BstZ17I-MscI fragment of pACYC184, yielding the pGOOD vector (Fig. 1). Due to their presence in the BstZ17I-MscI fragment of pACYC184 the restriction sites recognized by BamHI, BstBI, HindIII, and NheI are not uniquely located in the MCS of the pTrcHisB portion of pGOOD. However, the MCS of pGOOD does contain the following unique sites: NcoI, BsaBI, SacI,Eco53kI,TliL,Paer7I,XhoI,BglII,PstI,KpnI,Acc65I,NdeI,and EcoRI. With the exception of BsaBI and NdeI, these sites are also present in the MCS of pBADHisB, facilitating gene shuttling between this plasmid and pGOOD.

The stability of the new plasmid was tested in Escherichia coli TOP10: pGOOD was introduced into this strain, the transformants were selected and pre-cultured in the presence of tetracycline, and then cultured in antibiotic-free LB medium for 30 generations. We did not observe a significant loss of plasmid during this time; remarkably, after 30 generations 100% of individuals were still tetracycline-resistant and the yield of plasmid recovery was not significantly affected by propagation in host cells (data not shown).

These observations indicate a good maintenance of pGOOD, especially when considering that the plasmids containing the p15A ori are known as low-copy number vectors in E. coli. Moreover, pACYC184 was reported as an unstable plasmid when the host strain is cultivated in minimal medium supplemented with a limiting amount of glucose [START_REF] Lenski | Effects of segregation and selection on instability of plasmid pACYC184 in Escherichia coli[END_REF]. Notably, these previous findings suggest an easy procedure for the cure of pGOOD from host cells, i.e. the shift of transformant cultures from rich to minimal medium. The performance of pGOOD as a co-expression vector was tested by co-transforming E. coli TOP10 with: i) the pBAD-α1160 plasmid [START_REF] Bressanin | Proteolysis of the proofreading subunit controls the assembly of Escherichia coli DNA polymerase III catalytic core[END_REF], which contains an insert coding for the α (polymerase) subunit of E. coli DNA polymerase III (DNA Pol-III); ii) the pGOOD vector bearing the gene coding for the ε (proofreading) subunit of DNA Pol-III. Co-transformants were grown in the presence of both ampicillin and tetracycline, and induced for overexpression of α or ε by addition to the culture medium of arabinose or IPTG, respectively. In addition, control cultures were grown in the absence of any inducer. When only arabinose was used, overexpression of DNA Pol-III α subunit was observed, while in the absence of inducer no appreciable expression from pBAD of this protein was detectable (Fig. 2A, cf. lanes 1 and 2). This observation agrees with the regulatory properties of the pBAD vectors, which were described as tightlyregulated expression tools [START_REF] Guzman | Tight regulation, modulation, and high-level expression by vectors containing the arabinose PBAD promoter[END_REF]. When only IPTG was used, overexpression of the DNA Pol-III ε subunit was detected (Fig. 2A, lane 3). In the absence of inducer, a limited but significant expression of ε was observed (Fig. 2A, lane 1). The expression of ε from pGOOD in the absence of IPTG was confirmed by western blotting (data not shown), using a previously described rabbit polyclonal anti-ε antibody [START_REF] Bressanin | Proteolysis of the proofreading subunit controls the assembly of Escherichia coli DNA polymerase III catalytic core[END_REF]. Again, this finding is in line with previous reports demonstrating that the basal expression level of cloned genes is higher in lac-based expression vectors than in pBAD plasmids [START_REF] Guzman | Tight regulation, modulation, and high-level expression by vectors containing the arabinose PBAD promoter[END_REF].

When the growth medium was supplemented with both arabinose and IPTG, a consistent overexpression of DNA Pol-III α and ε subunits was observed (Fig. 2A, lane 4), indicating that the pBAD-pGOOD vector couple can be efficiently used to co-express proteins in E. coli. Moreover, we were able to modulate the levels of co-expressed α and ε; when IPTG was added 30 min before arabinose, the concentration of ε increased at the expense of the overexpression of α (data not shown). To test the feasibility of co-expression of a ternary protein complex, the holE gene, coding for the θ subunit of DNA Pol-III, was inserted into pGOOD-ε243 (using the PstI and EcoRI sites) and the expression of DNA Pol-III catalytic core (constituted by the αεθ complex) was attempted. Protein extracts isolated from E. coli TOP10 simultaneously overexpressing α, ε, and θ were subjected to gel filtration. Aliquots of each fraction were used to assay exonuclease activity according to [START_REF] Hamdan | Hydrolysis of the 5'-p-nitrophenyl ester of TMP by the proofreading exonuclease (epsilon) subunit of Escherichia coli DNA polymerase III[END_REF], and to perform gel electrophoresis. The activity profile features three distinct and sharp peaks (Fig. 2B), which can be ascribed to DNA Pol-III holoenzyme, DNA Pol-III catalytic core, and to the ε subunit associated with proteins other than α (center of peaks at fractions 6, 23, and 41, respectively). This interpretation is sustained by electrophoretic analyses of the fractions representing the maximum of each activity peak (Fig. s 2C and 2D). Altogether, these observations indicate that the protein extracts isolated from E. coli overexpressing α, ε, and θ can be used to analyze proteinprotein interactions directly, and suggest an efficient tool for the production and purification of the DNA Pol-III catalytic core.

In addition, by constructing two pGOOD variants (pGOOD1 and pGOOD2), we devised a tightly-controlled expression system. In both pGOOD derivatives, the lacI gene was deleted and replaced with the lacO id or lacO3 operator [START_REF] Oehler | Quality and position of the three lac operators of E. coli define efficiency of repression[END_REF], yielding pGOOD1 and pGOOD2, respectively (Fig. 1). The artificial operator lacO id features perfect symmetry, and is strongly bound by the LacI repressor. In particular, when a single operator is present in the lac operon, the expression of lacZ is repressed up to 7300, 4700, 320, and 16 times in the presence of lacO id , lacO1, lacO2, and lacO3, respectively [START_REF] Oehler | Quality and position of the three lac operators of E. coli define efficiency of repression[END_REF].

Moreover, the presence of two operators in the lac operon further increases the extent of repression [START_REF] Oehler | Quality and position of the three lac operators of E. coli define efficiency of repression[END_REF]. Accordingly, pGOOD1 (containing the lacO id -lacO1 couple, Fig. 1) should sustain very tight repression, while genes cloned in pGOOD2 (containing the lacO3-lacO1 couple, Fig. 1) should be easier to induce.

To complete our expression system, we inserted the lacI gene or the lacI ts mutant described by [START_REF] Bukrinsky | Multicopy expression vector based on temperature-regulated lac repressor: expression of human immunodeficiency virus env gene in Escherichia coli[END_REF] into pBAD (Fig. 1). By phenotypic analyses, this temperature-sensitive variant of LacI was inferred to be stable at 30 °C, and labile at 42 °C [START_REF] Bukrinsky | Multicopy expression vector based on temperature-regulated lac repressor: expression of human immunodeficiency virus env gene in Escherichia coli[END_REF]. To test our expression system, we inserted the D12A variant of the ε subunit into pGOOD1. This variant should be devoid of proofreading activity and, accordingly, be responsible for strong mutator phenotypes [START_REF] Fijalkowska | Mutants in the exo motif of Escherichia coli dnaQ: defective proofreading and inviability due to error catastrophe[END_REF]. In addition, the double mutant εD12A,E14A was described as lethal in strains subjected to replacement of the wt dnaQ gene (coding for ε subunit) with the gene coding for this variant [START_REF] Fijalkowska | Mutants in the exo motif of Escherichia coli dnaQ: defective proofreading and inviability due to error catastrophe[END_REF]. Accordingly, we reasoned that: i) a tight repression of the gene coding for εD12A would correspond to E. coli populations hosting this gene and featuring normal growth rate; ii) the mutation frequency of the host populations would increase under conditions corresponding to instability of LacI repressor, i.e. under non-permissive temperatures. To test these hypotheses, we co-transformed E. coli TOP10 with: i) pGOOD1 and pBAD-lacI or pBAD-lacI ts ; ii) pGOOD1-εD12A and pBAD-lacI or pBAD-lacI ts . Each cotransformant was grown at 30 and 42 °C, and the frequency of mutations was determined at each culture temperature. All the co-transformants grew at similar rates both at 30 and 42 °C (data not shown). Interestingly, populations of E. coli TOP10 containing the pGOOD1-εD12A and pBAD-lacI vectors did not feature any significant increase in mutation frequency when grown at 30 °C and compared with control populations containing the empty pGOOD1 plasmid (Fig. 3). On the contrary, when grown at 42 °C, populations containing pGOOD1-εD12A and pBAD-lacI plasmids mutated at a frequency two to three orders of magnitude higher than the control cultures (Fig. 3). This observation suggests that the LacI repressor is not fully stable at 42 °C or, alternatively, that at this temperature LacI associates with lac operators with reduced affinity. When the gene coding for the mutagenic εD12A variant was hosted in cells containing LacI ts , the observed frequency of mutations was higher, both at 30 and 42 °C, than the frequencies detected in control cultures (Fig. 3), suggesting that the LacI ts variant described by [START_REF] Bukrinsky | Multicopy expression vector based on temperature-regulated lac repressor: expression of human immunodeficiency virus env gene in Escherichia coli[END_REF] is partially labile at 30 °C.

Altogether, our observations indicate that: i) the expression of extremely toxic proteins in E. coli, such as εD12A, can be tightly controlled using the pGOOD1/pBAD-lacI vector couple; ii) conditional mutators spanning a wide range of frequency of mutations can be obtained using the pGOOD1-εD12A plasmid. Remarkably, the desired mutator phenotype, fully conditional or attaining extreme mutation frequencies, can be chosen by exerting repression of εD12A with LacI or LacI ts (Fig. 3).

In conclusion, the two expression systems described herein represent efficient tools for: i) the co-expression of proteins to analyze protein-protein interactions, using the pGOOD-pBAD vector couple; ii) the expression of very toxic proteins in E. coli, using the pGOOD1 and pBAD-lacI plasmids.

Figure legends

Figure 1

 1 Figure 1

Figure 2 (

 2 Figure 2

Figure 3

 3 Figure 3

Acknowledgements

We are indebted to Dr. Alberto Danielli (Department of Biology, University of Bologna) for advice and encouragement throughout this work. Thanks are also due to Anne Prudence Collins (Koinè SaS, Editorial Service for Academic Publications) for language editing. Financial support by Mipaaf, Project "Bioenergie" (D.M. n. 337/7303/06, December 21, 2006) is gratefully acknowledged.


Emmanuel Jeandel
email: emmanuel.jeandel@lirmm.fr

Pascal Vanier
email: pascal.vanier@lif.univ-mrs.fr

Hardness of Conjugacy and Factorization of multidimensional Subshifts of Finite Type

Keywords: Subshift of finite type, factorization, conjugacy, arithmetical hierarchy, computability, tilings

We investigate here the hardness of conjugacy and factorization of subshifts of finite type (SFTs) in dimension d > 1. In particular, we prove that the factorization problem is Σ 0 3 -complete and the conjugacy problem Σ 0 1 -complete in the arithmetical hierarchy.

Introduction

A d-dimensional Subshift of Finite Type (SFT) is the set of colorings of Z d by a finite set of colors in which a finite set of forbidden patterns never appear. One can also see them as tilings of Z d , and in particular in dimension 2, they are equivalent to the usual notion of tilings introduced by Wang [START_REF] Hao | Proving theorems by Pattern Recognition II[END_REF]. SFTs are discrete dynamical systems, and as such, their factoring and conjugacy relations are of great importance. If two dynamical systems are conjugate, then they exhibit the same dynamics. When X factors on Y , then the dynamic of Y is a subdynamic of the one of X.

Conjugacy is an equivalence relation and separates SFTs into classes. Classifying SFTs is a long standing open problem in dimension one [START_REF] Boyle | Open Problems in Symbolic Dynamics[END_REF] which has been proved decidable in the particular case of one-sided SFTs on N, see [START_REF] Williams | Classification of subshifts of finite type[END_REF]. It has been known for a long time that the problem was undecidable when * Both authors are partially supported by ANR-09-BLAN-0164 1 given two SFTs, since it can be reduced to the emptyness problem which is Σ 0 1 -complete [START_REF] Berger | The Undecidability of the Domino Problem[END_REF]. However, we prove here a slightly stronger result: even by fixing the class in advance, it is still undecidable to decide whether some given SFT belongs to it: Theorem 0.1. For any fixed X, given Y as an input, it is Σ 0 1 -complete to decide if X and Y are conjugate.

The more general problem of knowing if some SFT exhibits subdynamics of another has also been studied intensively. In dimension one, it is only partly solved for the case when the entropies of the two SFTs X, Y verify h(X) > h(Y ), see [START_REF] Boyle | Lower entropy factors of sofic systems[END_REF]. Factor maps have also been studied with the hope of finding universal SFTs: SFTs that can factor on any other and thus contain the dynamics of all of them. However it has been shown that such SFTs do not exist, see [START_REF] Hochman | A note on universality in multidimensional symbolic dynamics[END_REF][START_REF] Boyer | On factor universality in symbolic spaces[END_REF]. We prove here that it is harder to know if an SFT is a factor of another than to know if it is conjugate to it.

Theorem 0.2. Given two SFTs X, Y as inputs, it is Σ 0 3 -complete to decide if X factors onto Y .
An interesting open question for higher dimensions that would probably help solve the one dimensional problem would be is conjugacy of subshifts with a recursive language decidable?. A positive answer to this question would solve the one dimensional case, even if the SFTs are considered on N 2 instead of Z 2 .

The paper is organised as follows: first we give the necessary definitions and fix the notation is section 1, after what we give the proofs of theorems 0.1 and 0.2 in sections 2 and 3 respectively.

Preliminary definitions

Subshifts of finite type

We give here some standard definitions and facts about multidimensional subshifts, one may consult Lind [START_REF] Lind | Multi-Dimensional Symbolic Dynamics[END_REF] or Lind/Markus [START_REF] Lind | An introduction to symbolic dynamics and coding[END_REF] for more details.

Let Σ be a finite alphabet, its elements are called symbols, the d-dimensional full shift on Σ is the set Σ Z d of all maps (colorings) from Z d to the Σ (the colors). For v ∈ Z d , the shift functions

σ v : Σ Z d → Σ Z d , are defined locally by σ v (c x ) = c x+v . The full shift equipped with the distance d(x, y) = 2 -min{ v |v∈Z d ,xv =yv}
is a compact metric space on which the shift functions act as homeomorphisms. An element of Σ Z d is called a configuration.

Every closed shift-invariant (invariant by application of any σ v ) subset X of Σ Z d is called a subshift. An element of a subshift is called a point of this subshift.

Alternatively, subshifts can be defined with the help of forbidden patterns. A pattern is a function p : P → Σ, where P , the support, is a finite subset of Z d . Let F be a collection of forbidden patterns, the subset X F of Σ Z d containing the configurations having nowhere a pattern of F . More formally, X F is defined by

X F = x ∈ Σ Z d ∀z ∈ Z d , ∀p ∈ F, x |z+P = p .
In particular, a subshift is said to be a subshift of finite type (SFT) when the collection of forbidden patterns is finite. Usually, the patterns used are blocks or r-blocks, that is they are defined over a finite subset P of Z d of the form B r = -r, r d , r is called its radius. We may assume that all patterns of F are defined with blocks of the same radius r, and say the SFT has radius r.

Given a subshift X, a pattern p is said to be extensible if there exists x ∈ X in which p appears, p is also said to be extensible to x. We also say that a pattern p 1 is extensible to a pattern p 2 if p 1 appears in p 2 . A block or pattern is said to be admissible if it does not contain any forbidden pattern. Note that every extensible pattern is admissible but that the converse is not necessarily true. As a matter of fact, for SFTs, it is undecidable (in Π 0 1 to be precise) in general to know whether a pattern is extensible while it is always decidable efficiently (polytime) to know if a pattern is admissible.

As we said before, SFTs are compact spaces, this gives a link between admissible and extensible: if a pattern appears in an increasing sequence of admissible patterns, then it appears in a valid configuration and is thus extensible. More generally, if we have an increasing sequence of admissible pattern, then we can extract from it a sequence converging to some point of the SFT.

Note that instead of using the formalism of SFTs we could have used the formalism of Wang tiles, in which numerous results have been proved. In particular the undecidability of knowing whether a SFT is empty. Since we will be using a construction based on Wang tiles, we review their definitions.

Wang tiles are unit squares with colored edges which may not be flipped or rotated. A tileset T is a finite set of Wang tiles. A coloring of the plane is a mapping c : Z 2 → T assigning a Wang tile to each point of the plane. If all adjacent tiles of a coloring of the plane have matching edges, it is called a tiling.

The set of tilings of a Wang tileset is a SFT on the alphabet formed by the tiles. Conversely, any SFT is isomorphic to a Wang tileset. From a recursivity point of view, one can say that SFTs and Wang tilesets are equivalent. In this paper, we will be using both terminologies indiscriminately.

Factorization and Conjugacy

In the rest of the paper, we will use the notation Σ X for the alphabet of the subshift X.

A subshift X ⊆ Σ Z 2 X factors on a subshift Y ⊆ Σ Z 2 Y if there exists a finite set V = {v 1 , . . . , v k } ⊂ Z 2 , the window, and a local map f : Σ |V | X → Σ Y ,
such that for any point y ∈ Y , there exists a point x ∈ X such that for all z ∈ Z d , y z = f (x z+v1 , . . . , x z+v k ). That is to say, the global map F : X → Y associated to f , the factorization or factor map, verifies F (X) = Y . Without loss of generality, we may suppose that the window is an r-block, r being then called the radius of f and (2r + 1) its diameter.

When the map F is invertible and its inverse is also a factorization, the subshifts X and Y are said to be conjugate. In the rest of the paper, we will note with the same symbol the local and global functions, the context making clear which one is being used.

The entropy of a subshift X is defined as

h(X) = lim n→∞ log E n (X) n d
where E n (X) is the number of extensible patterns of X of support 0, n d where d is the dimension. The entropy is a conjugacy invariant, that is to say, if X and Y are conjugate, then h(X) = h(Y ). It is in particular easy to see thanks to the entropy that the full shift on n symbols is not conjugate to the full shift with n symbols when n = n .

Arithmetical Hierarchy and computability

We give now some background in computability theory and in particular about the arithmetical hierarchy. More details can be found in Rogers [START_REF] Hartley Rogers | Theory of recursive functions and effective computability[END_REF].

In computability, the arithmetical hierarchy is a classification of sets according to their logical characterization. A set A is Σ 0 n if there exists a total computable predicate R such that x ∈ A ⇔ ∃y 1 , ∀y 2 , . . . , Qy n R(x, y 1 , . . . , y n ), where Q is a ∀ or an ∃ depending on the parity of n. A set A is Π 0 n if there exists a total computable predicate R such that x ∈ A ⇔ ∀y 1 , ∃y 2 , . . . , Qy n R(x, y 1 , . . . , y n , where Q is a ∀ or an ∃ depending on the parity of n. Equivalently, a set is Σ 0 n iff its complement is Π 0 n . We say a set A is many-one reducible to a set B, A ≤ m B if there exists a computable function f such that for any x, f (x) ∈ A ⇔ x ∈ B. Given an enumeration of Turing Machines M i with oracle X, the Turing jump X of a set X is the set of integers i such that M i halts on input i. We note X (0) = X and X (n+1) = (X (n) ) . In particular 0 is the set of halting Turing machines.

A set A is Σ 0 n -hard (resp. Π 0 n ) iff for any Σ 0 n (resp. Π 0 n ) set B, B ≤ m A. The problem 0 (n) is Σ 0 n -complete. Furthermore, it is Σ 0 n -complete if it is in Σ 0 n . The sets in Σ 0
1 are also called recursively enumerable and the sets in Π 0 1 are called the co-recursively enumerable or effectively closed sets.

Conjugacy

We prove here the Σ 0 1 -completeness of the conjugacy problem in dimension d ≥ 2, even for a fixed SFT.

Theorem 2.1. Given two SFTs X, Y as an input, it is Σ 0 1 to decide whether X and Y are conjugate. Proof. To decide whether X and Y are conjugate, we have to check if there exists two local functions F : Σ X → Σ Y , and

G : Σ Y → Σ X such that F • G = id X and G • F = id Y .
To do this, we define two new functions F , G :

• Let r X and r F be the radiuses of X and F , then F : (Σ X { }) Br F → Σ Y { } is defined with a window of radius r F = max(r F , r X ):

F =
F if the window does not contain a forbidden pattern or a otherwise

• Let r Y and r G be the radiuses of Y and G, then

G : (Σ Y { }) Br G → Σ X { } is defined with a window of radius r G = max(r F , r X ): G =
G if the window does not contain a forbidden pattern or a otherwise

This definition may look gruesome, but is actually simple: F and G act exactly as F and G, except they keep track of forbidden patterns. That is, if for some pattern p, F • G(p) does not contain a , then G(p) does not contain a forbidden pattern. This will allow us to prove at the same time that

F (X) ⊆ Y (resp. G(Y ) ⊆ X) and that F • G = id X (resp. G • F = id Y ).
We want to prove that X and Y are conjugate if and only if there exists F, G and k > (r

F + r G ) such that for any admissible block b of size k of X (resp. Y ), F • G (b) (resp. G • F (b)) is equal to b at 0.
We prove this by contraposition for F •G , the proof is identical for the other composition. Suppose there is a configuration x ∈ X such that F • G (x) = x, we may suppose they differ in 0 by shifting x. So for any k there is an admissible block b of size k such that F • G (b) differs from b at 0. Conversely, if there is a sequence of blocks b k of size k, for k > (r F + r G ) such that F • G (b k ) differs from b k in 0, then by compactness we can extract a sequence converging to some configuration x ∈ X, and by construction F • G (x) differs from x in 0.

Theorem 2.2. For any X, given Y as an input, it is Σ 0 1 -hard to decide if X and Y are conjugate.

Proof. We reduce the problem to 0 , the halting problem. Given a Turing machine M we construct a SFT Y M such that Y M is conjugate to X iff M halts.

Let R M be Robinson's SFT [START_REF] Raphael | Undecidability and Nonperiodicity for Tilings of the Plane[END_REF] encoding computations of M : R M is empty iff M halts1 . Now take the full shift on one more symbol than X, note it F . Y M is now the disjoint union of X and R M × F .

If M halts, Y M = X and hence is conjugate to X. In the other direction, suppose M does not halt, then R M × F has entropy strictly greater than that of X and hence Y M is not conjugate to X. patterns converging to y. All of them have at least one admissible preimage m i . By compactness, we can extract from this sequence a converging subsequence, note x its limit. By construction x is a point of X and a preimage of y.

Lemma 3.5. Given F, X, Y as an input, deciding if

F (X) ⊆ Y is Σ 0 1 .
Proof. It is clear that F (X) ⊆ Y if and only if F (X) does not contain any configuration where a forbidden patterns of Y appears. We now show that this is equivalent to the following Σ 0 1 statement: there exists a radius r such that for any admissible r-block M of X, F (M ) does not contain any forbidden pattern in its center.

We prove the result by contraposition, in both directions. Suppose there is a configuration x ∈ X such that F (x) contains a forbidden pattern. Then for any radius r > 0, there exists an extensible, hence admissible, pattern M of size r such that F (M ) contains a forbidden pattern in its center.

Conversely, if for any radius r > 0, there exists an admissible pattern M of X of size r such that F (M ) contains a forbidden pattern in its center, then by compactness, there exists a configuration x ∈ X such that F (x) contains a forbidden pattern in its center.

Factorization is Σ 0 3 -hard

To prove the hardness, we use the base construction that we introduced in [JV11]: we note it T . This construction introduces a new way to put Turing machine computations in SFTs, in particular, the base construction has exactly one point (up to shift) in which computations may be encoded. We call this point configuration α, its schematic view is shown in figure 1a. The computation is encoded in the inner grid which is sparse. Each crossing between a horizontal line and a vertical one forms a cell. The constraints are carried along the vertical and horizontal lines, so that we may view the encoding of the Turing machine as a tiling on the grid. For each time step, the tape of the Turing machine is encoded in the NW-SE diagonals and the size of the diagonal steadily increases in size when going north-east. At each growth of the diagonal size, it gains two cells. Configuration α is made of two layers: one producing the horizontal lines and the other the vertical ones. The layer producing the vertical lines is shown in figure 2, the vertical lines are the black vertical lines. The configuration producing the horizontal lines is its exact symetric along the south-west/northeast diagonal. The key property of these layers is that when a corner tile (the tile in the lower left corner of the first square) appears, then the point is necessarily of this form.

In the original construction, corner tiles of the horizontal and vertical layers could only be superimposed to each other. We just change this so that instead, the corner tile of the vertical layer has to be at position (1, -1) relative to the corner tile of the horizontal one. This change does not impact any of the properties of T , but simplifies a bit the proof of lemma 3.7. Our reduction will use two SFTs based on this construction, both of them will be feature a different tiling on its grid. We will say that an SFT which is basically T with a tiling on its grid as having T -structure. Definition 3.6 (T -structure). We say an SFT X has T -structure it is a copy of T to which we superimposed new symbols only on the symbols representing the horizontal/vertical lines and their crossings.

Note that an SFT may have T -structure while having no α-configuration: for instance if you put a computation of a Turing machine that produces an error whenever it halts. The next lemma states a very intuitive result, that will be used later, namely that if an SFT with T -structure factors to another one, then the structure of each point is preserved by factorization. Furthermore, it shows that the factor map can only send a cell to its corresponding one, that is to say cell of the preimage has to be in the window of the image.

Lemma 3.7. Let X, Y be two SFTs with T -structure, such that X factors onto Y . Let r be the radius of the factorization, then any α-configuration of Y is factored on by an α-configuration of X, and can be shifted by v iff v ∞ ≤ r.

Proof. By [JV11, lemma 1], we know that non-α-configurations have at most one vertical line and one horizontal line. And therefore that they have two uniform (same symbols everywhere) quarter-planes and four uniform eighth-planes, as seen on figure 3. The two north east eighth-planes are not uniform in α. thus they cannot factor on α.

It remains to prove the second part: that in the factorization process the α-structure is at most shifted by the radius of the factorization. We do that by contradiction, suppose that an α-configurations x of X factors on an αconfiguration y of Y and shifts it by v = (v x , v y ), with v ∞ > r. Without loss of generality we may suppose that v x > r and v y > 0 and that the vertical and horizontal corner tiles of the preimage are at positions (0, 1) and (1, 0) respectively. We are now going to show that this is not possible.

On the horizontal layer, for all k ∈ N * there is a square with lower left corner at (2k 2 +k, 2k 2 +k), see figure 2. Inside this square, there are two (k-1)×(k-1) uniform smaller squares, see figure 4. This being also true for the vertical layer, these squares remain uniform when they are superimposed. Now take k such that k > ( v ∞ +2r +1). By hypothesis, there is a vertical line symbol t at z p = (2k 2 +2k +1, 2k 2 +k) on x, and thus at z i = (2k 2 +2k +1+v x , 2k 2 +k +v y ) on y. We know x |zi+Br has image t, and by what precedes that x |zi+Br = x |zi+(1,0)+Br since they are both uniform, therefore, there should be two t symbols next to eachother in y at z i and z i + (1, 0). This is impossible.

k -1 k -1 k k -1 2k (2k 2 + k, 2k 2 + k)
Figure 4: For every k ∈ N * , the square starting at position (2k 2 +k, 2k 2 +k) is of the form on the right on the component producing the vertical lines (and is the symetric along the diagonal for the one producing the horizontal lines). We can see that there are two uniform (k-1)×(k-1) squares at (2k 2 +2k+2, 2k 2 +k+1) and (2k 2 + k + 1, 2k 2 + 2k + 2) respectively.

Theorem 3.8. Given two SFTs X, Y as an input, deciding whether X factors onto Y is Σ 0 3 -hard.

For this proof, we will reduce to the problem COFINITE, which is known to be Σ 0 3 -complete, see Kozen [START_REF] Kozen | Theory of Computation[END_REF]. COFINITE is the set of Turing machines which run infinitely only on a finite set of inputs.

d > n n

Figure 5: Computation on input n in the SFT Z, the number of white diagonals d preceeding the computation is strigtly greater than the input n.

Proof. Given a Turing machine M , we construct two SFTs X M and Y M such that X M factors on Y M iff the set of inputs on which M does not halt is finite. We first introduce an SFT Z M on which both will be based. It will of course have T structure. Above the T base, we allow the cells of the grid to be either white or blue according to the following rules:

• All cells on a NW-SE diagonal are of the same color.

• A blue diagonal may follow (along direction SW-NE) a white diagonal, but not the contrary.

• A transition from white diagonal to blue may only appear when the grid grows.

We now allow computation on blue cells only. Only the diagonals after the growth of the grid may contain computations. The Turing machine M is launched on the input formed by the size of the first blue line (in number of cells of course). We forbid the machine to halt So for each n on which M does not halt, there is a configuration with white cells until the first blue diagonal appears, then computation occurs inside the blue cone, see figure 5 for a schematic view. If M halts on n, then there is no tiling where the first blue line codes n. By compactness, there is of course a configuration with only white diagonals. If M is total, then the only αconfiguration in Z M is the one with only white diagonals. Now from Z M , we can give X M and Y M :

• X M : Let Z M be a copy of Z M to which we add two decorations 0 and 1 on the blue cells only, and all blue cells in a configuration must have the same decoration. Now X M is Z M to which we add a third color, red, that may only appear alone, instead of white and blue. No computation is superimposed on red.

• Y M is a copy of Z M where we decorated only the horizontal corner tile with two symbols 0 and 1.

We now check that X M factors onto Y M iff M does not halt on a finite set of inputs: ⇒ Suppose M does not halt on a finite set of inputs: there exists N such that M halts on every input greater than N . The following factor map F works:

-F is the identity on Z M . Note that the additional copy of T is also sent onto Z M .

-F has a radius big enough so that when its window is centered on the corner tile, it would cover the beginning of the computation on input N .

-An α-configuration x of X M is sent on the same α-configuration y in Y M . For the decorations, when there is a computation on x, the factor map can see it and gives the same decoration to the corner tile of y. When there is no computation, the factor map doesn't see a computation zone and gives decoration 0 to the corner tile. The configuration with only white diagonals and decoration 1 of Y M is factored on by the α-configuration colored in red contained in X M .

Note that this also works when M is total.

⇐ Conversely, suppose M does not halt on an infinite set of inputs, and that there exists a factor map F with radius r: lemma 3.7 states that all α-configurations of Y M are factored on by α-configurations of X M . Now, there is an infinite number of α-configurations with corner tile decorated with 0 (resp. 1) in Y M , they all must be factored on by some α-configuration of X M . Still by lemma 3.7, the corner tile of the preimage must be in the window of the corner tile of the image. However, there can only be a finite number of configurations in which the symbols in this window differ. So the α-configurations of X M factor to a finite number of α-configurations of Y M with one of the decorations. This is impossible.

Note that the construction of X M and Y M from the description of M is computable and uniform. The reduction is thus many-one.

Figure 1 :

 1 Figure 1: (a) The skeleton of configuration α. (b) How the computation is superimposed to α.

Figure 2 :

 2 Figure2: Point α, the meaningful point of X T . The corner tile may be seen on the first non all-white column: it is the lower left corner of the square.

Figure 3 :

 3 Figure 3: Uniform quarter-and eighth-planes in non-α-configurations.

Robinson's SFT is in dimension

of course, for higher dimensions, we take the rules that the symbol in x ± e i equals the symbol in x, for i > 2.

Factorization

We start with two small examples to see why factorization is more complex than conjugacy. Here the examples are the simplest ones possible: we fix the SFT to which we factor in a very simple way, thus making the factor map known in advance.

Theorem 3.1. Let Y be the SFT containing exactly one configuration, a uniform configuration. Given X as an input, it is Π 0 1 -complete to know whether X factors onto Y .

Proof. In this case the factor map is forced: it has to send everything to the only symbol of Σ Y . And the problem is hence equivalent to knowing whether a SFT is not empty, which is Π 0 1 -complete.

Theorem 3.2. Let Y be the empty SFT. Given X as an input, it is Σ 0 1 -complete to know whether X factors onto Y .

Proof. Here any factor map is suitable, the problem is equivalent to knowing whether X is empty, which is Σ 0 1 -complete.

We study now the hardness of factorization in the general case, that is to say when two SFTs are given as inputs and we want to know whether one is a factor of the other. We prove here with theorems 3.3 and 3.8 the Σ 0 3 -completeness of the factorization problem.

3.1 Factorization is in Σ 0 3 Theorem 3.3. Given two SFTs X, Y as an input, deciding whether X factors onto Y is in Σ 0 3 .

Proof. X factors onto Y iff there exists a factor map F , a local function, such that F (X) = Y . This is the first existential quantifier.The result follows from the two next lemmas.

Proof. We prove here that the statement Y ⊆ F (X), that is to say, for every point y ∈ Y , there exists a point x ∈ X such that F (x) = y, is equivalent to the following Π 0 2 statement: for any admissible pattern m of Y , if m is extensible, then F -1 (m) contains an admissible pattern. This statement is Π 0 2 since checking that m is not extensible is Σ 0 1 , that is to say: there exists a radius r such that all r-blocks containing m are not admissible.

We now prove the equivalence. Suppose that Y ⊆ F (X), then any extensible pattern m of Y appears in a configuration y ∈ Y which has a preimage x ∈ X. A preimage of m being extensible, it is also admissible. This proves the first direction.

Conversely, suppose all extensible patterns m of Y have an admissible preimage. Let y be a point of Y , then we have an increasing sequence m i of extensible


Mehrez Zribi
email: mehrez.zribi@ird.fr

Nicolas Baghdadi

Michel Nolin

Remote Sensing of Soil

Over the past few decades, the Earth's surface has witnessed major changes in land use. These changes are likely to continue, driven by demographic pressure or by climate change. In this context, monitoring tools are needed for maintaining a sustainable ecological status, improving soil conservation and water resource management. Floods, excess runoff, soil erosion, and related contamination and disequilibrium of the water and carbon cycles are, among others, key issues that are controlled and influenced by soil surface characteristics. The implementation of sustainable agricultural, hydrological, and environmental management requires an improved understanding of the soil, at increasingly finer scales. Conventional soil sampling and laboratory analyses cannot efficiently provide this information, because they are slow, expensive, and could not retrieve all temporal and spatial variabilities.

In this context, remote sensing has shown a high potential in soil characteristics retrieving in the last three decades. Different methodologies have been proposed for the estimation of soil parameters, based on different remote sensing sensors and techniques (passive and active). For passive remote sensing, we can consider four principal types of sensors:

(i) optical remote sensing with limited number of bands (e.g., SPOT, ASTER, LANDSAT..., etc.) particularly adapted for vegetation cover description, land use analysis,

(ii) optical remote sensing based on hyperspectral sensors, particularly adapted for soil texture description, (iii) optical remote sensing with thermal infrared band, adapted for soil temperature estimation, (iv) passive microwave remote sensing adapted to soil moisture and vegetation estimation.

For active remote sensing, different studies have shown a considerable potential for the characterization of different soil parameters: moisture, roughness, and texture. Active remote sensing is particularly based on two types of sensors: synthetic aperture radar (SAR) with high spatial resolution adapted to local and regional studies and scatterometer sensor more adapted to global estimations of soil parameters. Three types of methodologies are generally used for soil parameters estimation: empirical models based only on satellite and ground databases, semiempirical models based on a mixture between physical modelling and real data, and finally physical models based only on the description of radiative transfert physics to analyze relationship between remote sensing signals and soil parameters.

These remote sensing studies concern particularly four soil parameters (moisture, roughness, temperature, and texture).

(i) Soil moisture is a key parameter, influencing the manner in which rainwater is shared between the phenomena of evapotranspiration, infiltration, and runoff. (ii) Soil surface roughness is involved in the separation of water flow into infiltration and runoff. Moreover, monitoring the evolution of surface roughness is a way to estimate erosion risk particularly in agricultural areas. (iii) Soil texture is one of the most important soil properties influencing most physical, chemical, and biological soil processes. Hence, it is a key property for soil management.

Applied and Environmental Soil Science (iv) Soil temperature is a key parameter in the description of evapotranspiration and surface-atmosphere interface processes.

Based on this high potential of remote sensing to retrieve surface parameters, a high number of sensors have been launched in the last years to improve different methodologies proposed to retrieve operationally surface parameters.

In this context, our principal objective of this special issue is to present different studies illustrating quantitative analyses based on these different new sensors.

Pasolli et al. propose a technique for estimating soil moisture based on the support vector regression algorithm and the integration of ancillary data, using active remote sensing (RADARSAT 2 SAR data).

Liu et al. investigated the impact of soil moisture on gross primary production (GPP), chlorophyll content, and canopy water content represented by remotely sensed vegetation indices (VIs) in an open grassland and an oak savanna in California.

Using SAR (RADARSAT-1) remote sensing, Khaldoune et al. provide a classification of frozen/unfrozen soils in the entire Bras d'Henri River watershed near Quebec City (Quebec, Canada). It was developed to produce frozen soil maps under snow cover.

Browning and Duniway present a method to map soils with Landsat ETM+ imagery and high-resolution (5 m) terrain (IFSAR) data. They then characterize soil classes mapped using this semiautomated technique. The method distinguished spectrally distinct soil classes that differed in subsurface rather than surface properties.

Baptista et al. study tested the feasibility of applying AVIRIS sensor (Airborne Visible/InfraRed Imaging Spectrometer) for mapping and quantifying mineralogical components of three Brazilian soils. They showed to be possible mapping and quantifying the weathering degree of the studied soils.

Hively et al. propose the use of airborne hyperspectral imagery to map tilled agricultural fields properties. Soil hyperspectral reflectance imagery was obtained using an airborne imaging spectrometer (400-2450 nm, ∼10 nm resolution, 2.5 m spatial resolution). The resulting raster maps showed variation associated with topographic factors, indicating the effect of soil redistribution and moisture regime on in-field spatial variability.

Finally, Oguro et al. discuss brightness temperature (BT) measurements and statistics over Taklimakan Desert. They are retrieved from the data of Landsat-7/ETM+ band 6 and Terra/MODIS band 31 and 32.

In spite the limited number of scientific papers and the difficulty to cover all techniques of remote sensing of soil, we hope that the readers will find this as a useful source of information.

Acknowledgments

We would like to thank the reviewers who helped us in reviewing the articles and timely recommendations. We also would like to thank the staff of the Editorial Section of Applied and Environmental Soil Science (AESS), who had faith in us and cooperated at all stages of compilation.

Mehrez Zribi Nicolas Baghdadi

Michel Nolin