Kristina Straub

Mona Linde

Cosimo Kropp

Samuel Blanquart

Patrick Babinger

Rainer Merkl
email: rainer.merkl@ur.de

Sequence selection by FitSS4ASR alleviates ancestral sequence reconstruction as exemplified for geranylgeranylglyceryl phosphate synthase

Keywords: Common ancestors, oligomerization, protein design, protein evolution, sequence space

For evolutionary studies, but also for protein engineering, ancestral sequence reconstruction (ASR) has become an indispensable tool. The first step of every ASR protocol is the preparation of a representative sequence set containing at most a few hundred recent homologs whose composition determines decisively the outcome of a reconstruction. A common approach for sequence selection consists of several rounds of manual recompilation that is driven by embedded phylogenetic analyses of the varied sequence sets. For ASR of a geranylgeranylglyceryl phosphate synthase, we additionally utilized FitSS4ASR, which replaces this time-consuming protocol with an efficient and more rational approach.

FitSS4ASR applies orthogonal filters to a set of homologs to eliminate outlier sequences and those bearing only a weak phylogenetic signal. To demonstrate the usefulness of FitSS4ASR, we determined experimentally the oligomerization state of eight predecessors, which is a delicate and taxon-specific property. Corresponding ancestors deduced in a manual approach and by means of FitSS4ASR had the same dimeric or hexameric conformation; this concordance testifies to the efficiency of FitSS4ASR for sequence selection. FitSS4ASR based results of two other ASR experiments were added to the Supporting Information.

Introduction

During the last forty years, ancestral sequence reconstruction (ASR) has become a very successful means of computational biology. Its usage has elucidated completely different aspects of protein evolution, which are intractable with other methods; for recent reviews see [START_REF] Joy | Ancestral reconstruction[END_REF][START_REF] Merkl | Ancestral protein reconstruction: techniques and applications[END_REF][START_REF] Wheeler | The thermostability and specificity of ancient proteins[END_REF][START_REF] Gumulya | Exploring the past and the future of protein evolution with ancestral sequence reconstruction: the 'retro' approach to protein engineering[END_REF][START_REF] Hochberg | Reconstructing ancient proteins to understand the causes of structure and function[END_REF]. ASR algorithms compute for a given set of extant homologs a phylogenetic tree and deduce for all internal nodes the most likely sequences [START_REF] Liberles | Ancestral sequence reconstruction[END_REF].

Their composition results from the chosen phylogenetic model [START_REF] Ashkenazy | FastML: a web server for probabilistic reconstruction of ancestral sequences[END_REF] and the extant homologous sequences that specify the leaves of the tree. Driven to extremes, the most ancient sequences that can be reconstructed are related to the last universal common ancestor (LUCA) that existed in the Paleoarchean era, i.e., at least 3.5 billion years ago [START_REF] Nisbet | The habitat and nature of early life[END_REF]. The in silico and biochemical characterization of "resurrected" proteins from these early phases of evolution were key to characterize primordial proteins [START_REF] Thornton | Resurrecting the ancestral steroid receptor: ancient origin of estrogen signaling[END_REF][START_REF] Hobbs | On the origin and evolution of thermophily: reconstruction of functional precambrian enzymes from ancestors of Bacillus[END_REF] and the corresponding habitats [START_REF] Perez-Jimenez | Single-molecule paleoenzymology probes the chemistry of resurrected enzymes[END_REF]. Due to the lack of macromolecular fossils, ASR is the only informative means to gain insight into the intricacy of ancient proteins [START_REF] Reisinger | Evidence for the existence of elaborate enzyme complexes in the Paleoarchean era[END_REF] and to reproduce adaptations of extinct species to climatic, ecological and physiological changes [START_REF] Boussau | Parallel adaptations to high temperatures in the Archaean eon[END_REF][START_REF] Akanuma | Experimental evidence for the thermophilicity of ancestral life[END_REF].

A second reason for the great success is that ASR adds a further dimension to sequence analysis: From an evolutionary point of view, extant homologs represent variants observed for one point in time, thus the comparison of these proteins was termed "horizontal" approach.

Many protein families contain functionally diverse members and it is, e. g., difficult to identify residues that are sufficient to switch function by comparing recent sequences, because many of these variations are irrelevant for functional differences [START_REF] Harms | Analyzing protein structure and function using ancestral gene reconstruction[END_REF]. In contrast, ASR is a "vertical approach", as it takes into account the evolutionary history of the proteins under study. Focusing on the specific substitutions that occurred along the branches leading to different functions is more straightforward. Thus, vertical approaches can drastically reduce experimental efforts to identify key residues as demonstrated for the specificity of hormone receptors [START_REF] Ortlund | Crystal structure of an ancient protein: evolution by conformational epistasis[END_REF], the fluorescence properties of GFP variants [START_REF] Field | Retracing evolution of red fluorescence in GFP-like proteins from Faviina corals[END_REF], or hotspots of protein-protein interfaces [START_REF] Holinski | Combining ancestral sequence reconstruction with protein design to identify an interface hotspot in a key metabolic enzyme complex[END_REF].

The insight that ancestral proteins are generally more robust and often more versatile (promiscuous) than their modern successors [START_REF] Wouters | A despecialization step underlying evolution of a family of serine proteases[END_REF][START_REF] Wheeler | The thermostability and specificity of ancient proteins[END_REF] has opened new fields for the usage of reconstructed predecessors in protein design; for a review see [START_REF] Gumulya | Exploring the past and the future of protein evolution with ancestral sequence reconstruction: the 'retro' approach to protein engineering[END_REF]. For example, predecessors of serum paraoxonases and cytosolic sulfotransferases are highly active and functionally diverse and few mutations have been sufficient to introduce a new specificity [START_REF] Alcolombri | Directed evolution of sulfotransferases and paraoxonases by ancestral libraries[END_REF]. The replacement of residues that change along the branches leading to a functional switch of DNA polymerases has led to a broadened substrate spectrum [START_REF] Chen | Reconstructed evolutionary adaptive paths give polymerases accepting reversible terminators for sequencing and SNP detection[END_REF]. Generally, a stable and robust template is beneficial for directed evolution studies, as mutations that lead to a new function are often destabilizing [START_REF] Tokuriki | How protein stability and new functions trade off[END_REF]. Using ASR, a 30 -40 °C increase in denaturation temperature has been obtained, which is much larger than that typically gained with alternative protein engineering protocols; for a review see [START_REF] Wijma | Structure-and sequence-analysis inspired engineering of proteins for enhanced thermostability[END_REF].

A crucial element of ASR is the computation of a phylogenetic tree, whose topology is determined by the set of recent sequences and the phylogenetic model, which are both chosen by the user. Once a tree is available, the composition of ancestral sequences that correspond to internal nodes of the tree can be deduced from the leaves, i. e., the recent sequences [START_REF] Ashkenazy | FastML: a web server for probabilistic reconstruction of ancestral sequences[END_REF]. If the topology of this tree is wrong, some internal nodes correspond to ancestors that never existed and the relative order of mutations can be biased as well. Generally, the quality of the phylogenetic tree can be affected by systematic errors related to the evolutionary model and by stochastic errors, caused by sequences that do not contain enough phylogenetic signal to support a robust tree. One source of systematic errors could be the second step of each ASR [START_REF] Merkl | Ancestral protein reconstruction: techniques and applications[END_REF], which is the creation of an MSA. Often, MSA algorithm rely on a simplistic evolutionary model, whose assumptions specify the data for the subsequent reconstruction steps. Thus, for highly divergent data sets with less than 30% sequence identity (SeqId), the generation of MSAs is a crucial step of each phylogenetic analysis [START_REF] Essoussi | A comparison of MSA tools[END_REF]. Recent comparisons of several state-of-the-art methods indicated that all performed equally well for more homogeneous sequence sets [START_REF] Essoussi | A comparison of MSA tools[END_REF][START_REF] Le | Protein multiple sequence alignment benchmarking through secondary structure prediction[END_REF] and MAFFT [START_REF] Katoh | MAFFT multiple sequence alignment software version 7: improvements in performance and usability[END_REF] and PRANK [START_REF] Löytynoja | Phylogeny-aware gap placement prevents errors in sequence alignment and evolutionary analysis[END_REF] exhibited best performance for ASR [START_REF] Vialle | Alignment modulates ancestral sequence reconstruction accuracy[END_REF].

The protocols implemented for ASR are based on well-proven algorithms and evolutionary models and for each step of the reconstruction process, probability measures allow for the assessment of their outcome; see e. g. [START_REF] Straub | Ancestral sequence reconstruction as a tool for the elucidation of a stepwise evolutionary adaptation[END_REF]. For the convenience of the user, specialized servers have been implemented that execute an ASR protocol in a fully automated manner for a given set of sequences [START_REF] Dereeper | Phylogeny.fr: robust phylogenetic analysis for the non-specialist[END_REF][START_REF] Kumar | MEGA-CC: computing core of molecular evolutionary genetics analysis program for automated and iterative data analysis[END_REF][START_REF] Hanson-Smith | PhyloBot: A web portal for automated phylogenetics, ancestral sequence reconstruction, and exploration of mutational trajectories[END_REF]. Thus, by carefully examining the quality of all phases of ASR, one can avoid systematic errors e.g. those caused by fast-evolving sites, rate-variation among sites, or compositional heterogeneity. Removing columns from the MSA and choosing an adequate phylogenetic models are effective means to avoid such errors [START_REF] Rodríguez-Ezpeleta | Detecting and overcoming systematic errors in genome-scale phylogenies[END_REF].To minimize stochastic errors, the set of recent sequences selected as input has to be chosen diligently. ASR can be carried out for DNA, codon, and amino acid sequences. In the following, we exclusively focus on the compilation of a set of amino acid sequences belonging to one protein isoform, which is a key issue of ASR.

Due to their chronological order, mutations of early evolutionary phases have been manifested in many recent members of a family; therefore, it is not necessary to consider all of them for ASR. Indeed, huge numbers of homologs do not necessarily improve the reconstruction of ancestral states [START_REF] Li | More taxa are not necessarily better for the reconstruction of ancestral character states[END_REF]; thus not more than 150 to 200 input sequences are commonly picked by the user. However, the current databases offer for many functionally important proteins several thousand homologous sequences, which urges the user to choose a drastically reduced subset. This selection process is an important and difficult phase, because sequence selection greatly affects the quality of the phylogenetic tree. Quality must meet high standards for ASR [START_REF] Pagel | Bayesian estimation of ancestral character states on phylogenies[END_REF] and trees showing the strongest phylogenetic signal give more accurate reconstructions [START_REF] Litsios | Effects of phylogenetic signal on ancestral state reconstruction[END_REF]. To allow for the reconstruction of a long evolutionary time-span and early predecessors, the sequences must represent phylogenetically diverse species. On the other hand, closely related sequences that diverge by few mutations introduce redundancy only and do not support a deep reconstruction. Thus, the user has to identify a set of homologs that support a sufficiently deep but also highly robust tree.

Often, users initially create for ASR a large set of homologs by means of a BLAST search, which needs further processing. To reduce the number of sequences and redundancy, one can start by picking representatives from the sequence clusters created with the help of tools like cd-hit [START_REF]Cd-hit: a fast program for clustering and comparing large sets of protein or nucleotide sequences[END_REF] or use more specialized approaches [START_REF] Frickey | PhyloGenie: automated phylome generation and analysis[END_REF][START_REF] Fuellen | Correspondence of function and phylogeny of ABC proteins based on an automated analysis of 20 model protein data sets[END_REF][START_REF] Dereeper | Phylogeny.fr: robust phylogenetic analysis for the non-specialist[END_REF][START_REF] Tamura | MEGA5: molecular evolutionary genetics analysis using maximum likelihood, evolutionary distance, and maximum parsimony methods[END_REF]. In order to combine several orthogonal methods for sequence selection, we designed FitSS4ASR, which filters sequence sets for ASR. This tool draws upon well-proven concepts applied to iteratively refine sets and can be used in a semi-automatic manner with minimal user interaction. Our tool selects sequences that i) agree best with current evolutionary models in order to avoid systematic errors and ii) have retained a strong phylogenetic signal in order to avoid stochastic errors.

We confirmed the validity of this kind of sequence selection by means of a biochemical characterization of ancestral geranylgeranylglyceryl phosphate synthases (GGGPSs). This enzyme is involved in the biosynthesis of ether membrane lipids that are prototypical for Archaea and catalyzes the formation of an ether bond between glycerol 1-phosphate and geranylgeranyl diphosphate [START_REF] Chen | S)-geranylgeranylglyceryl phosphate synthase. Purification and characterization of the first pathway-specific enzyme in archaebacterial membrane lipid biosynthesis[END_REF][START_REF] Peterhoff | A comprehensive analysis of the geranylgeranylglyceryl phosphate synthase enzyme family identifies novel members and reveals mechanisms of substrate specificity and quaternary structure organization[END_REF]. A characteristic, taxonspecific property of GGGPS is the oligomerization state, which can be dimeric or hexameric [START_REF] Peterhoff | A comprehensive analysis of the geranylgeranylglyceryl phosphate synthase enzyme family identifies novel members and reveals mechanisms of substrate specificity and quaternary structure organization[END_REF][START_REF] Linde | Hexamerization of geranylgeranylglyceryl phosphate synthase ensures structural integrity and catalytic activity at high temperatures[END_REF]. We used the same ASR protocol, but two different sets of recent GGGPS homologs to compute ancestors. The first set of sequences was compiled in a time-consuming manner requiring extensive manual curation. The second set was created by applying FitSS4ASR that reduced user-intervention drastically. For both sets, phylogenetic trees and ancestral sequences were computed; the corresponding proteins were heterologously expressed and characterized. The accordance of the experimentally determined oligomerization states confirmed the equivalence of the resurrected enzymes with respect to this delicate property and testified to the applicability of FitSS4ASR.

Results

General criteria guiding sequence selection for ASR

Commonly, the first step of sequence selection is the generation of a set by means of BLAST [START_REF] Altschul | Gapped BLAST and PSI-BLAST: a new generation of protein database search programs[END_REF] or the choice of a precompiled dataset as offered by InterPro [START_REF] Mitchell | The InterPro protein families database: the classification resource after 15 years[END_REF] or similar databases. Owing to the success of sequencing projects, these initial sets contain much more homologous sequences than practically useful. Thus, the aim in developing FitSS4ASR was not to support the user in constructing a tree for a given set of sequences, but to find a set of representatives that allow for the reliable reconstruction of predecessors.

One major constraint of sequence selection is the phylogenetic origin of the candidates that must represent a sufficiently wide phylogenetic diversity. For example, the distribution of species in the comprehensive tree of life [START_REF] Hug | A new view of the tree of life[END_REF] suggests for the reconstruction of LUCA proteins a sequence set representing species from the six dominating bacterial and two archaeal clades. Usually, it is easy to provide a broad phylogenetic representation for a given protein due to the wide coverage of extant sequences deposited in databases. Thus, the crucial task of sequence selection is a rigorous but specific filtering, and the appropriate combination of filters might advantageously be exploited to increase the robustness of the ASR process. As a first step, a single representative can be chosen for each subset of highly similar sequences to reduce redundancy. In order to eliminate splice variants and flawed sequences caused by misassembly or gene-prediction errors, non-canonical outliers whose length differs significantly, i. e., by more than len_dev = 2 standard deviations from the mean can be eliminated as well (Figure 1A). Note that we use the term "param = value" to specify parameters of FitSS4ASR and their default values that can be altered by the user. Sequences without indels have more likely retained their ancestral length [START_REF] Akiva | Evolutionary and molecular foundations of multiple contemporary functions of the nitroreductase superfamily[END_REF] and the evolutionary correct modeling of indels is still difficult. Thus, it is appropriate to ignore also sequences with internal insertions [START_REF] Dereeper | Phylogeny.fr: robust phylogenetic analysis for the non-specialist[END_REF] as indicated by a multiple sequence alignment (MSA) (Figure 1B).

Other filter criteria [START_REF] Merkl | Ancestral protein reconstruction: techniques and applications[END_REF] are only applicable after a phylogenetic tree has been computed for the input. Horizontal gene transfer (HGT) (Figure 1C) is a frequent phenomenon in bacterial genomes [START_REF] Ochman | Lateral gene transfer and the nature of bacterial innovation[END_REF], which complicates ASR due to nonconstant mutation rates. To exclude the results of apparent HGT events, sequences that cause an aberrant phylogeny incompatible with a monophyletic origin have to be removed, which requires to compare the taxonomy of nodes and subtrees. Moreover, to support a reliable reconstruction of subsequent ancestral states, the length of each branch has to indicate a sufficiently low rate subs_r = 1.0 of substitutions per site (Figure 1D). The reconstruction of subsequent states can be unreliable, if more than one substitution occurred during the time span represented by the length of a given branch. FitSS4ASR considers substitution rates exceeding subs_r as critical. Note that low substitution rates reduce also the risk of long-branch attraction, which is a systematic error that may occur if a tree contains long and short branches.

As a consequence, two or more long branches can be grouped as sisters (nodes that share the same parent node) and distantly related species seem to be closely related [START_REF] Bergsten | A review of long-branch attraction[END_REF]. A further criterion for the robustness of subtree topology are the local bootstrap values/posterior probabilities that are compared to loc_qual = 0.75. In agreement with the literature [START_REF] Soltis | Applying the bootstrap in phylogeny reconstruction[END_REF], FitSS4ASR considers loc_qual values ≥ 0.75 as an indicator of sufficient support to reconstruct the corresponding sequences.

By removing sequences constituting an isolated subtree or by adding additional sequences, the user can modulate the topology and subdivide long branches [START_REF] Wiens | Can incomplete taxa rescue phylogenetic analyses from long-branch attraction?[END_REF].

However, the effects caused by an altered input are often unpredictable, which compels the testing of many alternative combinations. Thus, a manual sequence selection may turn into a tedious and time-consuming task.

FitSS4ASR: Filtering sequence sets for ASR

In order to support sequence selection in a comprehensive manner, FitSS4ASR consists of a series of methods that iteratively filter sequence sets and perform phylogenetic analyses to eliminate non-canonical sequences as described above (Figure 2A). To begin with, representatives are chosen based on the outcome of cd-hit [START_REF]Cd-hit: a fast program for clustering and comparing large sets of protein or nucleotide sequences[END_REF] that clusters sequences on their similarity. Subsequently, sequences that significantly deviate in length from the mean or introduce internal gaps are eliminated. The remaining sequences constitute the initial set 1  k SEQ , which is subjected to an analysis of tree topology. FitSS4ASR offers two alternatives for phylogenetic analysis, namely the maximum likelihood approach RAxML [START_REF] Stamatakis | RAxML-VI-HPC: maximum likelihood-based phylogenetic analyses with thousands of taxa and mixed models[END_REF] and the Bayesian approach MrBayes [START_REF] Ronquist | MrBayes 3: Bayesian phylogenetic inference under mixed models[END_REF].

We parametrized both programs for the computation of a series of trees i branch_distr(Alts) (Formula 2) is a measure for the existence of exceedingly long branches longer than subs_r substitution per site and pp_distr(Alts) (Formula 3) indicates the "reliability" of branches near the root of the tree. tr_rob(Alts) (Formula 4), summarizes the phylogenetic robustness of s tr with respect to perturbations and tr_mf(Alts) (Formula 5) penalizes the existence of multifurcations. We consider a dataset s SEQ a good choice for ASR, if the phylogenetic coverage is sufficient and if all other scores are close to 1.0. For a first orientation, the user can compare the ASR_score(Alts) values, which are for each dataset the product of the latter four scores (Formula 6).

Validation of FitSS4ASR by means of an ASR of GGGPS

In order to confirm the efficacy of our approach, we performed in parallel a conventional and a

FitSS4ASR-assisted ASR of the enzyme GGGPS. GGGPS is a key enzyme in the evolution of Archaea [START_REF] Payandeh | Enzyme-driven speciation: crystallizing Archaea via lipid capture[END_REF], but also occurs in bacterial species, albeit with unknown physiological function. In a previous analysis, all enzymes have been assigned to one of two groups [START_REF] Peterhoff | A comprehensive analysis of the geranylgeranylglyceryl phosphate synthase enzyme family identifies novel members and reveals mechanisms of substrate specificity and quaternary structure organization[END_REF]: Group I enzymes occur in Euryarchaeota and Firmicutes, however, most Archaea possess a group II GGGPS, which also occurs in some bacterial species like Bacteroidetes. The reconstruction of a common ancestor of both groups is not feasible due to the length of the edge (> 4 substitutions per site) that interconnects the nodes representing the ancestors of group I (AncGGGPS1) and group II (AncGGGPS2) enzymes. Whereas all group I enzymes oligomerize to dimers, group II enzymes form dimers or hexamers that can be clustered based on sequence similarity [START_REF] Peterhoff | A comprehensive analysis of the geranylgeranylglyceryl phosphate synthase enzyme family identifies novel members and reveals mechanisms of substrate specificity and quaternary structure organization[END_REF]. Thus, we expected differing oligomerization states for predecessors of group II enzymes and a dimeric last common ancestor due to the principle of parsimony. The deliberately chosen single point mutation W141A in GGGPS2 from the archaeon Methanothermobacter thermautotrophicus turns the hexameric wild-type into a dimeric complex [START_REF] Peterhoff | A comprehensive analysis of the geranylgeranylglyceryl phosphate synthase enzyme family identifies novel members and reveals mechanisms of substrate specificity and quaternary structure organization[END_REF]. This finding indicates that minor sequence alterations can affect the oligomerization state of GGGPS2, which makes its analysis to an ideal testbed for the performance and robustness of ASR protocols.

Conventional sequence selection for ASR of GGGPS2

We started sequence selection with the analysis of a comprehensive and precompiled set GGGPS2initial, which consisted of 217 entries from InterPro family IPR008205 (version 67.0).

To generate this set, the above-mentioned sequence length filters were applied; additionally, all clades represented by just one sequence were eliminated by comparing key2ann [START_REF] Pürzer | Key2Ann: a tool to process sequence sets by replacing database identifiers with a human-readable annotation[END_REF] annotations. This program replaces each sequence identifier with an easy to understand string representing the phylogenetic lineage of the contributing species, which is deduced from the NCBI taxonomy database [START_REF] Ashkenazy | Optimal data collection for correlated mutation analysis[END_REF]. We used these annotations to determine the phylogenetic diversity of this and all other sequence sets.

An MSA was computed by means of MAFFT [START_REF] Katoh | MAFFT multiple sequence alignment software version 7: improvements in performance and usability[END_REF] and exclusively for the computation of a phylogenetic tree, 75 of the 287 columns containing more than 50% gaps were eliminated by utilizing Gblocks [START_REF] Castresana | Selection of conserved blocks from multiple alignments for their use in phylogenetic analysis[END_REF]. For the resulting MSA, a first phylogenetic tree was deduced with PhyloBayes [START_REF] Lartillot | PhyloBayes 3: a Bayesian software package for phylogenetic reconstruction and molecular dating[END_REF].

Applying the above-mentioned criteria, we assessed the robustness and suitability of this and subsequently generated trees for ASR. It seems a simple task to pick a robust subset from not more than 217 sequences. However, nine rounds of optimization requiring the manual adaptation of the sequence set were needed. The resulting MSA GGGPS2_man consisted of 87 sequences and gave rise to a phylogenetic tree that fulfilled all our robustness criteria. This tree was deduced from two MCMC chains and their maximum difference of posterior probabilities of tree bipartitions was 0.00024, which indicates high MCMC convergence. The MSA consisting of the full-length sequences that were used to deduce ancestral sequences is listed in Table S1 (Supporting Information), the resulting phylogenetic tree is given in Table S3 (Supporting Information) and shown in Figure 3.

Sequence selection for an ASR of GGGPS2 by means of FitSS4ASR

The sequences GGGPS2initial used above for a conventional sequence selection were also subjected to FitSS4ASR. The program converged after two rounds of iteration and the ASR_score(Alts) of the alternatives suggested to consider a specific set { , }  s s s Alt tr SEQ .

However, it contained not more than 58 sequences and just 1 crenarchaeal sequence, as

FitSS4ASR does not preserve the phylogenetic diversity of the input. Thus, the crenarchaeal subset taken from GGGPS2initial was added to s SEQ and a further FitSS4ASR run was performed, which resulted in a final set GGGPS2_auto consisting of 61 sequences. The MSA consisting of the full-length sequences used to deduce ancestral sequences is listed in Table S2 (Supporting Information), the resulting phylogenetic tree is given in Table S4 (Supporting Information) and shown in Figure 4. This final dataset had an ASR_score (Formula 6) of 0.17 due to two multifurcations within Thermococcales and Methanosarcinales (compare Figure 4); tr_mf (Formula 5) was 0.33. An assessment of the other scores confirmed that it fulfills all criteria for ASR: branch_distr (Formula 2) was 0.99, pp_distr (Formula 3) was 0.85, and tr_rob (Formula 4) was 0.61. Moreover, a comparison of Figures 3 and4 made clear that both trees possess a highly similar topology. This finding testifies to the strong phylogenetic signal within the two sequence sets GGGPS2_man and GGGPS2_auto; interestingly, the two sets overlap by not more than 34 sequences.

Reconstruction and characterization of AncGGGPS2 predecessors

Extant GGGPS group II enzymes form dimers or hexamers and it is unknown when these oligomerization states arose. All euryarchaeal and thaumarchaeal proteins shown in Figures 3 and4 form hexamers and for these, we wanted to elucidate oligomerization for the evolutionary interval dating back to the last common ancestor AncGGGPS2. Thus, sequences representing this LCA sequence and intermediates AncGGGPS2_N* were reconstructed by means of FastML [START_REF] Ashkenazy | FastML: a web server for probabilistic reconstruction of ancestral sequences[END_REF]. To assess the robustness of our protocol, we utilized in parallel the sets GGGPS2_man and GGGPS2_auto for ASR (see Methods) and identified corresponding predecessors by comparing the topology of the trees; see Figures 3 and4.

We first analyzed the oligomerization states of the last common ancestors AncGGGPS2_N1_man and AncGGGPS2_N1_auto. Using synthetic genes, proteins were heterologously expressed in Escherichia coli and purified by means of metal chelate affinity chromatography. Their oligomerization states were determined by using analytical size exclusion chromatography (SEC) and well-characterized hexameric (mtGGGPS_wt) or dimeric variants (mtGGGPS_W141A) [START_REF] Peterhoff | A comprehensive analysis of the geranylgeranylglyceryl phosphate synthase enzyme family identifies novel members and reveals mechanisms of substrate specificity and quaternary structure organization[END_REF][START_REF] Linde | Hexamerization of geranylgeranylglyceryl phosphate synthase ensures structural integrity and catalytic activity at high temperatures[END_REF]) served as references.

The finding that both common ancestors form dimers (Figure 5A) suggests that hexamerization arose at later evolutionary phases. For euryarchaeal group II GGGPS, this transition must occur at one of the internal nodes of the trees used for ASR. Almost all recent euryarchaeal and thaumarchaeal GGGPS are hexamers [START_REF] Peterhoff | A comprehensive analysis of the geranylgeranylglyceryl phosphate synthase enzyme family identifies novel members and reveals mechanisms of substrate specificity and quaternary structure organization[END_REF][START_REF] Linde | Hexamerization of geranylgeranylglyceryl phosphate synthase ensures structural integrity and catalytic activity at high temperatures[END_REF], thus we assumed that this transition occurs at the furcation AncGGGPS2_N4_man  S1 -Table S5 (Supporting Information). Despite these differences, the phenotypes, i. e., the oligomerization state of the ancestors, as well as the location of the transition from a dimer to a hexamer within the trees derived from the GGGPS2_man and GGGPS2_auto sequence sets are identical. Thus, our experiments provide a further example for the robustness of ASR against uncertainty [START_REF] Hanson-Smith | Robustness of ancestral sequence reconstruction to phylogenetic uncertainty[END_REF] and point to a strategy to strengthen the support for conclusions of ASR experiments: In addition to ensemble methods used to sample and characterize less likely ancestors [START_REF] Bar-Rogovsky | Assessing the prediction fidelity of ancestral reconstruction by a library approach[END_REF], the support for a specific phenotype can also be increased by a co-validation of experimental findings based on two or more distinct sequence samplings.

Selecting sequences for ASR of another two enzymes

We reconstructed ancestral GGGPS2 enzymes because we wanted to retrace the advent of their different oligomerization states. In this case, sequence selection was initiated with a precompiled set of bona fide group II enzymes, which was comprehensive [START_REF] Peterhoff | A comprehensive analysis of the geranylgeranylglyceryl phosphate synthase enzyme family identifies novel members and reveals mechanisms of substrate specificity and quaternary structure organization[END_REF] but contained only 217 sequences. In order to demonstrate the usefulness of FitSS4ASR

for the filtering of larger sequence sets, we applied it to a dataset of TrpD2 sequences (16820 sequences) and a dataset of concatenated HisH/HisF sequences (1309 sequences, [START_REF] Richter | Computational and experimental evidence for the evolution of a ()8-barrel protein from an ancestral quarter-barrel stabilised by disulfide bonds[END_REF]), which are or have been in the focus of other ASR experiments. In both cases, FitSS4ASR was run with default parameters. For each test set, we could create with minimal additional effort at least one tree that strongly supports the reconstruction of early predecessors.

These trees are plotted in Figures S2,S3 and detailed in Tables S6, S7 (Supporting Information).

Discussion

ASR requires a strong phylogenetic signal necessitating a rigorous preselection of sequences

Often, the analysis of large datasets is regarded valuable for the recovery of statistically wellsupported and "true" phylogenies. However, it is known that the analysis of large datasets under optimal models of sequence evolution does not guarantee robust phylogenetic inference [START_REF] Ho | Tracing the decay of the historical signal in biological sequence data[END_REF][START_REF] Rodríguez-Ezpeleta | Detecting and overcoming systematic errors in genome-scale phylogenies[END_REF][START_REF] Salichos | Inferring ancient divergences requires genes with strong phylogenetic signals[END_REF]. Moreover, the misleading effects of certain biases are correlated with the size of a dataset [START_REF] Lartillot | A Bayesian mixture model for across-site heterogeneities in the amino-acid replacement process[END_REF]. One notoriously observed bias is long-branch attraction (LBA), which leads to a clustering of taxa with high evolutionary rates regardless of the phylogenetic relatedness.

LBA is caused by strong violations of phylogenetic model assumptions due to highly heterogeneous evolutionary rates within some lineages. To overcome this problem, it has been proposed to eliminate fast-evolving taxa [START_REF] Stefanović | Long branch attraction, taxon sampling, and the earliest angiosperms: Amborella or monocots?[END_REF][START_REF] Rivera-Rivera | LS³: a method for improving phylogenomic inferences when evolutionary rates are heterogeneous among taxa[END_REF] or fast-evolving genes from multi-gene datasets [START_REF] Brinkmann | An empirical assessment of long-branch attraction artefacts in deep eukaryotic phylogenomics[END_REF] and algorithms like Phylo-MCOA can detect outlier genes and species by comparing the topologies produced by individual genes [START_REF] De Vienne | Phylo-MCOA: a fast and efficient method to detect outlier genes and species in phylogenomics using multiple co-inertia analysis[END_REF]. However, these methods often necessitate the parallel analysis of several datasets. To reach highest flexibility, we focused on elimination methods that need for outlier detection not more than the dataset and the trees required for the intended ASR. The inspection of suboptimal trees provides insight into the interplay among conflicting noise versus phylogenetic signal [START_REF] Swofford | Phylogenetic inference[END_REF] and to reduce noise, we integrated the elimination of rogue and solitary sequences. The scores determined by FitSS4ASR for the assessment of carefully compiled datasets support the user in his decision, which should be more than the blind reliance on optimality criteria and should also consider contradictory factors adequately [START_REF] Ho | Tracing the decay of the historical signal in biological sequence data[END_REF].

A limitation of FitSS4ASR is its blindness against the phylogenetic diversity of the chosen sequences. As demonstrated for the GGGPS2 and the HisF/HisH reconstruction, it might be necessary to add sequences manually to broaden the phylogenetic basis. Additionally, some HGT events have to be resolved manually by comparing key2ann annotations.

Moreover, FitSS4ASR is less suitable for proteins, which encountered frequently length variations causing many indels or possess high evolutionary rates. For these cases, the filter routines might eliminate too many sequences of the input.

Future directions

We restricted the function of FitSS4ASR to sequence selection and implemented two filters for the elimination of sequences with a weak phylogenetic signal. The integration of further methods for sequence elimination is feasible, which could be based on the length of individual branches or novel methods assessing their robustness [START_REF] Lemoine | Renewing Felsenstein's phylogenetic bootstrap in the era of big data[END_REF].

We consider the integration of the full ASR protocol into FitSS4ASR less useful, due to the various demands of individual reconstruction projects. For example, different ASR methods and models are in use and just recently, SubRecon was introduced for the investigation of substitutions on a single branch of interest [START_REF] Monit | SubRecon: ancestral reconstruction of amino acid substitutions along a branch in a phylogeny[END_REF].

However, irrespective of the ASR problem to be solved, a sequence set has to be selected beforehand and thus the current implementation of FitSS4ASR can help to the speed up any ASR protocol.

Materials and methods

Software and parameters used for the conventional ASR protocol

Jalview [START_REF] Waterhouse | Jalview Version 2-a multiple sequence alignment editor and analysis workbench[END_REF] was used for sequence comparison, redundancy filtering and MSA generation. Phylogenetic trees were computed with the help of PhyloBayes3.0 [START_REF] Lartillot | PhyloBayes 3: a Bayesian software package for phylogenetic reconstruction and molecular dating[END_REF] utilizing a site-heterogeneous CAT model and by launching 4 independent MCMC samplings of length 50,000 to ensure convergence. For the final dataset, the first 6000 trees of each chain were discarded as burn-in and the remaining trees of two chains were concatenated to deduce a consensus tree. et al., 2011), which replaced each sequence identifier with a human-readable annotation representing the phylogenetic lineage of the contributing species. cd-hit [START_REF]Cd-hit: a fast program for clustering and comparing large sets of protein or nucleotide sequences[END_REF] was used to reduce sequence redundancy and to eliminate identical sequences. Sequences deviating in length by more than 2 standard deviations from the mean were also removed. For the resulting sequences, an initial MSA was computed with default parameters by means of MAFFT [START_REF] Katoh | MAFFT multiple sequence alignment software version 7: improvements in performance and usability[END_REF], which exhibited best performance in ASR applications [START_REF] Vialle | Alignment modulates ancestral sequence reconstruction accuracy[END_REF]. Sequences introducing internal gaps with a minimal length min_len = 5 in at least 90% of the sequences were removed; the resulting sequence set

Software and parameters used for

1  k SEQ contained  k m SEQ sequences.
For subsequent analyses aimed at the computation of robust trees, the sequences were realigned and columns containing more than 50% gap symbols were eliminated by utilizing Gblocks [START_REF] Castresana | Selection of conserved blocks from multiple alignments for their use in phylogenetic analysis[END_REF]. Two phylogenetic analyses were performed by means of RAxML or MrBayes. The RAxML option -f a and the substitution model Otherwise, sequence elimination was initiated.

For sequence elimination, the tree list generated during each iteration k was further analyzed by means of RogueNaRok [START_REF] Aberer | Pruning rogue taxa improves phylogenetic accuracy: an efficient algorithm and webservice[END_REF] to identify "rogue" sequences.

Additionally, for each and consensus method implemented in the Bio:Phylo package [START_REF] Talevich | Bio.Phylo: a unified toolkit for processing, analyzing and visualizing phylogenetic trees in Biopython[END_REF].

Indicators of ASR suitability

FitSS4ASR lists for each of the final datasets { , }  branch_distr(Alts) = # branches shorter than subs_r substitution per site / # all branches (2)

The value of branch_distr(Alts) is 1.0, if all branches are shorter than subs_r substitution per site and decreases with the number of exceedingly long branches.

, ( )

_ _ ( ) ( ) ( , ) ( ) ( , )       s v pp v loc qual v pp distr Alt pp v dist root v pp v dist root v (3)
Here, pp(v) is the posterior probability of branch v and dist (root, v) is the distance of v from the root, i. e., the number of branches. The value of pp_distr(Alts) reaches 1.0, if all branches near the root are well supported by posterior probabilities of at least loc_qual.

tr_rob(Alts) = the fraction of shared bipartitions (4)

The value of tr_rob(Alts) is 1.0, if s tr and the consensus tree * s tr resulting from our perturbation approach are identical and decreases with the number of differing bipartitions determined by means of bitstring.

tr_mf(Alts) = 1/(1 + the number of multifurcations) (5)

The value of tr_mf(Alts) is 1.0, if s tr does not contain multifurcations, which impede ASR and are introduced by some programs during the computation of consensus trees.

ASR_score(Alts) = branch_distr(Alts)pp_distr(Alts)tr_rob(Alts)tr_mf(Alts) (6)

ASR_score(Alts) is close to 1.0, if a tree fulfils all stability parameters.

Ancestral sequence reconstruction

NJplot [START_REF] Gouy | NJplot. University of Lyon[END_REF] was used for midpoint rooting a phylogenetic tree between Bacteria and Archaea. Ancestral sequences that may contain indels, were computed by means of the marginal reconstruction approach of FastML [START_REF] Ashkenazy | FastML: a web server for probabilistic reconstruction of ancestral sequences[END_REF], the substitution model JTT, and a gamma distribution. In order to adjust the length of reconstructed and of recent sequences, the parameter probability cutoff to prefer ancestral indel over character was set to 0.8 (manual approach) or 0.9 (FitSS4ASR) in order to compensate a bias towards longer than true ancestors [START_REF] Vialle | Alignment modulates ancestral sequence reconstruction accuracy[END_REF]. For each internal node of the tree, the most probable sequence was determined.

Cloning

Gene sequences for the reconstructed proteins (AncGGGPS2_N1_man, Anc-GGGPS2_N4_man, AncGGGPS2_N5_man, AncGGGPS2_N12_man, Anc-GGGPS2_N1_auto, AncGGGPS2_N17_auto, AncGGGPS2_N18_auto and Anc-GGGPS2_N22_auto) were optimized in their codon usage for expression in E. coli and ordered as GeneArt™ Strings™ DNA fragments from Thermo Fisher Scientific. Their nucleotide sequences are given in Table S5 (Supporting Information). The DNA fragments had BsaI restriction sites at the 5' and 3'-end and were cloned into a modified pET21a expression vector [START_REF] Rohweder | Standardized cloning vectors for protein production and generation of large gene libraries in Escherichia coli[END_REF], providing a C-terminal hexahistidine (His)6 tag. The constructs were verified by sequencing. The wild-type Methanothermobacter thermautotrophicus GGGPS (mtGGGPS_wt) and the mtGGGPS_W141A variant have been cloned previously into pET21a [START_REF] Peterhoff | A comprehensive analysis of the geranylgeranylglyceryl phosphate synthase enzyme family identifies novel members and reveals mechanisms of substrate specificity and quaternary structure organization[END_REF]. The sequence numbering of mtGGGPS used in this study refers to EMBL ENA entry AAB85058 and PDB-ID 4mm1, which have an N-terminal three amino acid extension compared to UniProt entry O26652.

Production and purification of recombinant proteins

Heterologous gene expression was performed in E. coli strain BL21-CodonPlus(DE3)-RIPL (Agilent Technologies). The transformed cells were grown at 37 °C in LB medium containing ampicillin (150 µg ml -1 ) and chloramphenicol (30 µg ml -1 ). When OD600 reached 0.6 -0.8, expression was induced by adding 1 mM isopropyl-β-D-1-thiogalactopyranoside (IPTG), and growth was continued overnight. After harvesting by centrifugation, cells were resuspended in 50 mM potassium phosphate, pH 7.5, 300 mM KCl, 10 mM imidazole and disrupted by sonication. The His6-tagged proteins were purified from the clarified cell extract by metal chelate affinity chromatography. An ÄKTApurifier system with a HisTrap FF crude column (5 ml, GE Healthcare) was used, and a linear gradient of imidazole (10 -500 mM) in 50 mM potassium phosphate, pH 7.5, 300 mM KCl was applied to elute the protein. Interfering imidazole and salt were removed from the purified proteins, except for AncGGGPS2_N17_auto, by dialysis against 50 mM potassium phosphate, pH 7.5 at 4 °C.

Because the AncGGGPS2_N17_auto preparation contained higher-oligomeric soluble aggregates, it was further purified by subsequent preparative SEC on a Highload TM 26/600 The 87 sequences of GGGPS2_man represent four major microbial phyla, namely Bacteroidetes, Crenarchaeota, Euryarchaeota, and Thaumarchaeota. All sequences were annotated by means of key2ann [START_REF] Pürzer | Key2Ann: a tool to process sequence sets by replacing database identifiers with a human-readable annotation[END_REF] to indicate for each species the phylogenetic lineage detailing superkingdom, phylum, class, order, family, and species. For example, the label "ACrThDeDe_She" represents the species Staphylothermus hellenicus "_She", which is from the superkingdom Archaea "A", the phylum Crenarchaeota "Cr", the class Thermoprotei "Th", the order Desulfurococcales "De", and the family Desulfurococcaceae "De". The tree was computed by means of MrBayes. For central nodes, the posterior probability and (if available) a bipartition score is given. The length of the horizontal bar corresponds to 0.2 substitutions per site. Nodes "N*_man" labelled in green correspond to evolutionary intermediates that were characterized biochemically. Their dimeric or hexameric oligomerization states, as determined by size exclusion chromatography, are indicated by red symbols. The proteins (40 µM subunit concentration each) were applied to a S75 analytical gel filtration column equilibrated with 50 mM potassium phosphate, pH 7.5, 300 mM KCl. Elution was performed at a flow rate of 0.5 ml/min, followed by measuring the absorption at 280 nm (A280) and plotted against the elution volume. mtGGGPS_wt and mtGGGPS_W141A served as references for the hexameric or dimeric oligomerization state, respectively [START_REF] Peterhoff | A comprehensive analysis of the geranylgeranylglyceryl phosphate synthase enzyme family identifies novel members and reveals mechanisms of substrate specificity and quaternary structure organization[END_REF][START_REF] Linde | Hexamerization of geranylgeranylglyceryl phosphate synthase ensures structural integrity and catalytic activity at high temperatures[END_REF].

  subsequent analysis of tree robustness, FitSS4ASR saves during each iteration k elimination phase of FitSS4ASR, the series of trees i k tr is used to identify sequences with an ambiguous or insufficient phylogenetic signal[START_REF] Sanderson | Troubleshooting molecular phylogenetic analyses[END_REF], causing in the trees an unstable phylogenetic position based on two different criteria: RogueNaRok[START_REF] Aberer | Pruning rogue taxa improves phylogenetic accuracy: an efficient algorithm and webservice[END_REF] detects "rogue" sequences that possess different sister sequences in trees generated during a phylogenetic analysis. The program eliminates sequences based on the relative bipartition information criterion (RBIC) that increases support of a tree and stops, if RBIC cannot be further improved by pruning more sequences. However, this optimality criterion does not identify all unstable taxa[START_REF] Wilkinson | Comments on detecting rogue taxa using RogueNaRok[END_REF], thus we implemented a more rigorous alternative that identifies "solitary" sequences. Solitary are the sequences r k seq of a given set k SEQ , for which each of the sisters s occurs in a fraction below min_sis = 0.75 of the k-specific trees i k tr ; see Methods. FitSS4ASR allows the user to choose one of three alternatives rules that eliminate i) rogue, ii) solitary, iii) rogue and solitary sequences that may cause the computation of incorrect ancestors. The removal of these sequences can create branches of undesired length. Thus, all other sequences inducing branches longer than subs_r substitution/site are eliminated as well and the remaining sequences are subjected to further rounds of refinement, until one of two stopping criteria is reached: FitSS4ASR stops, if k SEQ contains not more than min_seq = 60 sequences or if no sequences are eliminated during the last 10 iteration steps. Thus, FitSS4ASR generates a series of iteratively reduced sets and the output of the last iteration { completion of sequence elimination, FitSS4ASR assesses the robustness of the generated datasets to offer alternatives from which the user can choose (Figure 2B). Initially, up to 15 datasets  k Iter are chosen from the last rounds of sequence selection so that the sets  k Iter contain approximately evenly distributed between u and maximally 500 sequences. Due to the nested hierarchy of the sequence sets  k SEQ , we expect a consistent core topology of the trees  k tr and deviations in individual trees are indicative of less suitable sequence sets. To filter out such sets, FitSS4ASR deduces a supertree and discards trees  k tr that are not compatible with the core topology; see Methods. A supertree is a single phylogenetic tree resulting from a combination of trees; here it is expected that the trees  k tr overlap largely. The m remaining sets , are further subjected to a perturbation test, which we devised as a final assessment of tree robustness: We consider a sequence set s SEQ "phylogenetically robust", if the addition of randomly chosen sequences has only a minor effect on tree topology. For a broad sampling, FitSS4ASR generates 100 sequence sets * s SEQ , each of which consist of s SEQ plus 10 randomly picked sequences chosen from the initial set 1 SEQ and computes the corresponding trees. For the subsequent tree comparison, our algorithm prunes the 100 trees to the sequences s SEQ and uses the trees for the computation of a consensus tree * s tr . If the comparison of tree topologies * s tr and s tr indicates only minor differences, we consider s tr robust to perturbations and s SEQ suitable for ASR. As noted, FitSS4ASR utilizes two different methods for phylogenetic analysis and three for sequence elimination; thus, the final sets s Alt may originate from any of these six combinations and a further characterization of the sets is needed to facilitate a selection. Choosing a dataset for ASR After program termination, the user has to select one of the m alternative datasets { according to his needs. FitSS4ASR calculates five scores to support the user with his decision: Based on the score tax_num(Alts) (Formula 1), the user can survey the phylogenetic coverage of the sequence set s SEQ . Two scores assess the quality of s tr :

(

  Figure 4. AncGGGPS2_N1_man and AncGGGPS2_N1_auto share 75% SeqId and 36 of the 45 differences are similar residues that possess a positive pairwise BLOSUM (Henikoff and Henikoff, 1992) score. Similarity increases for less ancestral predecessors: The corresponding intermediates AncGGGPS2_N5_man and AncGGGPS2_N18_auto share 93%, and AncGGGPS2_N12_man and AncGGGPS2_N22_auto 91% SeqId. All sequences are listed in TableS1-TableS5(Supporting Information). Despite these differences, the phenotypes, i. e.,

  of n input sequences and ended after t rounds of iterations, if one of two stopping criteria was fulfilled; compare Figure 2. To begin with, the phylogenetic origin of the n input sequences was determined by means of key2ann (Pürzer

PROTGAMMAAUTO

  were utilized to compute 100 trees and a consensus tree. The MrBayes option sumt and the gtr and invgamma model were used to generate 1,000,000 trees and a consensus tree by means of 2 chains. During each iteration, the dataset { consensus tree and the sequences was saved for the subsequent analysis.Computation ended, if the sequence elimination step described below did not further reduce the content of k SEQ , i.e.,  k m SEQ was constant for 10 rounds or if m was ≤ min_seq = 60.

  occurrences were summed up in a matrix [ , ] k sis r s and normalized for each r to identify "solitary" sequences for which holds [ s . Depending on the chosen selection parameter, either one of the elimination methods or a combination of both was applied to eliminate rogue or/and solitary sequences. The remaining sequences constituted the set 1  k SEQ , if a further iteration k+1 was executed.Choosing and assessing the phylogenetic robustness of sequence sets: Taking the output were selected that contained approximately evenly distributed between u and maximally 500 sequences. Using the trees  k tr , a supertree was computed with the help of PluMiST[START_REF] Kupczok | Split-based computation of majority-rule supertrees[END_REF] and default parameters. The deviation from this supertree was determined for all  k tr by means of the bitstring method implemented in the Bio:Phylo package[START_REF] Talevich | Bio.Phylo: a unified toolkit for processing, analyzing and visualizing phylogenetic trees in Biopython[END_REF] and all trees classified as dissimilar were discarded. The m by means of the prune

  ) is the number of species contributing to the respective sequence set.

FiguresFigure 1 .

 1 Figures

Figure 2 .SEQ.

 2 Figure 2. Workflow of FitSS4ASR. (A) Iterative sequence elimination. Initially, highly similar sequences identified by cd-hit and sequences that deviate significantly from the mean length or introduce internal gaps are removed. The remaining sequences constitute a sequence set, which is iteratively reduced until one of two stopping criteria is fulfilled. During each iteration k, FitSS4ASR performs a phylogenetic analysis by means of RAxML or MrBayes based on an MSA created by means of MAFFT and Gblocks. The iteration-specific output { , }  k k k Iter tr SEQ consisting of a consensus tree and a sequence set is stored for subsequent analysis. The topologies of the trees generated for each iteration k are further analyzed to identify "rogue" or/and "solitary" sequences, whose localization varies among the individual trees. These and sequences causing isolated subtrees with branches longer than 1 substitution/site are eliminated. (B) Assessing the robustness of tree topologies. Taking up to 15 representative datasets

Figure 3 .

 3 Figure 3. Phylogeny of the manually curated sequence set used for ASR of GGGPS2 predecessors.

Figure 4 .

 4 Figure 4. Phylogeny of the sequence set generated by means of FitSS4ASR for ASR of GGGPS2 predecessors.The 61 sequences of GGGPS2_auto represent four major microbial phyla, namely Bacteroidetes, Crenarchaeota, Euryarchaeota, and Thaumarchaeota. All sequences were annotated by means of key2ann[START_REF] Pürzer | Key2Ann: a tool to process sequence sets by replacing database identifiers with a human-readable annotation[END_REF]; see legend of Figure3. The tree was computed by means of MrBayes. For central nodes, the posterior probability and (if available) a bipartition score is given. The length of the horizontal bar corresponds to 0.2 substitutions per site. Nodes "N*_auto" labelled in green correspond to evolutionary intermediates that were characterized biochemically. Their dimeric or hexameric oligomerization states, as determined by size exclusion chromatography, are indicated by red symbols.

Figure 5 .

 5 Figure 5. Analytical size exclusion chromatography of ancestral sequences.

Acknowledgement

This work was supported by the Deutsche Forschungsgemeinschaft (ME2259/2-1) and calculations were facilitated through the use of advanced computational infrastructure provided for account pr48fu by the Leibniz Supercomputing Center of the Bavarian Academy of Sciences and Humanities (LRZ).

Superdex TM S75 pg column (GE Healthcare). The column was equilibrated with 50 mM potassium phosphate, pH 7.5 and was run at a flow rate of 0.5 ml min -1 . Protein concentrations were determined by absorbance spectroscopy. The molar extinction coefficients ε280 and the molecular weight were calculated from the amino acid sequence by means of ProtParam [START_REF] Gasteiger | Protein identification and analysis tools on the ExPASy Server[END_REF]. The purity of all proteins was verified by SDS-PAGE; see Figure S1 (Supporting Information). The proteins were dropped into liquid nitrogen and stored at -80 °C until further analysis.

Characterization of oligomerization states of GGGPS variants

All GGGPS variants were characterized by analytical SEC experiments. Analysis was performed on a calibrated Superdex TM S75 10/300 GL column (GE Healthcare), which was operated with 50 mM potassium phosphate, pH 7.5, 300 mM KCl at a flow rate of 0.5 ml min - 1 . 100 µl of protein with a subunit concentration of 40 µM was applied. mtGGGPS_wt and mtGGGPS_W141 served as references for the hexameric and dimeric oligomerization state, respectively [START_REF] Peterhoff | A comprehensive analysis of the geranylgeranylglyceryl phosphate synthase enzyme family identifies novel members and reveals mechanisms of substrate specificity and quaternary structure organization[END_REF].


Driss Sadounl

Catherine Dubois

Yacine Ghamri-Doudane

Brigitte Grau

An Ontology for the Conceptualization of an Intelligent Environment and its Operation

Keywords: Ontology conception, specifications, formal verification, intelligent environment

Nowadays sensors and actuators are increasingly used in different spaces, creating intelligent environment. This article aims to describe a conceptualization of an intelligent environment and its operation, in order to check its consistency and its conformity. This conceptualization is done through an ontology representing the domain knowledge, whose elements will be instantiated from natural language texts describing the physical configuration of an intelligent environment and a scenario describing the operation desired by the user of the environment. We chose OWL to represent formally our environment augmented with SWRL rules to represent the dynamic aspect of the operation system and SQWRL to query our conceptual model. We show how consistency and conformity are checked thanks to this formalism.

I. INTRODUCTION

Comfort, energy saving and safety are criteria that nowadays reflect human needs in daily life environments. The profusion and the diversity of sensors, their affordable costs, let imagine different possibilities for an intelligent environment that could adapt itself to person needs. The ambition of our Project ENVIE VERTE 1 is to enable the piloting of an intelligent environment using textual descriptions in natural language. These descriptions concern on one hand information about the physical description of the intelligent environment (number of sensors, types, locations, interactions, ...) and on another hand, end user needs (do not leave empty rooms lit, detect gas, ...). In order to deploy a system that reflects the needs described by an individual, it is necessary to verify its conformity (the environment is correctly configured) and its logical consistency (no contradiction in its operation). These verifications require dealing with precise and unambiguous specifications of the environment and of the end user requirement. As natural language specifications do not fulfill these requirements, we propose to build an intermediate conceptual representation, enabling a transition 1. founded by DIGITEO, project DIM LSC 2010. towards formal specifications, and allowing checking the logical consistency and the conformity of the intelligent environment. The conceptual representation will therefore be the link, between natural language specifications and formal specifications.

Our present objective is to build a conceptual representation of an intelligent environment that will be instantiated from the description of the environment and end user requirement provided as scenarios. To achieve this, we created a high-level OWL ontology which provides the ability to reason, to do queries and to conclude on the appropriate actions to perform according to a scenario. This conceptual representation will enable to generate consistent and formal specifications which could be further verified using formal methods and tools.

The originality of our approach is the use of the ontology logic formalism to represent and check the consistency and the conformity of specifications, and to realize it in two steps : a static part leads to create individuals for representing a given environment, and a dynamic part leads to create rules for representing end user scenarios.

The paper is organized as follows. First we describe the intelligent environment, its components and the two types of textual descriptions in Section 2. In Section 3 we describe the intelligent environment checking process. In Section 4 we detail our approach to produce a conceptual model representing the natural language (NL) descriptions. In Section 5 we illustrate with an application case how our model will be used to check consistency of NL descriptions. In Section 6 we give a view of related work. And finally we conclude and define some future works.

II. INTELLIGENT ENVIRONMENTS

The intelligent environment consists of a set of communicating objects (sensors, actuators and control devices) which can be seen as a sensor network. These objects influence the operation of equipment (physical processes) located in the environment, under well defined conditions.

We can distinguish a hardware part : the kind of devices, their number, the type of each device, their location ... and a software part which represents the configuration of its operation.

In the following, we briefly describe the general functions of an intelligent environment :

-A sensor detects the occurrence of a phenomenon or measure a quantifiable phenomenon in a bounded area. -A phenomenon, to be detected or measured by a sensor, must be located in the sensing zone of the sensor and be from a type perceived by the sensor (temperature, motion ...) -An actuator is fixed on or connected with an equipment of the environment. -Once a phenomenon (or a set of phenomena) is detected or measured, a control of the collected information is processed and can lead to the activation of one or several actuators trigging a set of actions (turn on, turn off, increase, decrease) on the equipment they are fixed on or connected with. -An actuator can be activated by a sensor (or a set of sensors), if it is located in its (their) zone of control and is able to analyze the information perceived and transmitted by the sensor(s). To pilot her intelligent environment, a user will determine, according to the given physical configuration, the general functions that should hold to satisfy her needs. Figure 1 shows how a user will configure her own system by writing textual descriptions. These descriptions will be analyzed to instantiate automatically elements of an OWL ontology representing the domain knowledge, which will be used to generate formal code. Verification of the resulting model will be processed to detect inconsistencies and missing information and therefore to correct and improve the model by interacting with the user until it is consistent and satisfies her needs. In this article we will focus on the conception of the ontology and the verification it enables to perform. In this framework textual descriptions are written in English. These descriptions can be separated into two parts :

1) Description of an intelligent environment : It describes components of the intelligent environment, (sensors, actuators, physical processes ...), their number, their type, their location and how they can interact. This part will be processed before user requirement and define a static state of the environment. The simple intelligent environment described in the following example is shown Figure 2 Example : the green apartment includes a hall, two bedrooms, one bathroom and a living room which includes a kitchen and a dining room. Each room is equipped with motion sensors. Each light bulb is equipped with an actuator.

III. INTELLIGENT ENVIRONMENT CHECKING

Before deploying the intelligent environment, it is important to check whether its operation is conform to its specifications. Such verifications will be realized by using formal methods, which requires precise and unambiguous specifications. So the conceptual representation of the operation of the intelligent environment must be free of any contradiction and ambiguity. It must also represent all the properties which define the functioning of the modeled environment, to be admissible.

A. Chosen model

We decided to use OWL (Web Language Ontology) for the conception of our model. OWL provides a mean to produce a formal semantic representation, thanks to its logical formalism based on description logics [START_REF] Horrocks | Owl : a description logic based ontology language for the semantic web[END_REF] which are logic-based formalisms used for knowledge representation with a high expressivity power [START_REF]The Description Logic Handbook : Theory, Implementation, and Applications[END_REF]. OWL enables to reason on an ontology to check its logical consistency. OWL is extended by a Semantic Web Rule Language SWRL [START_REF] Horrocks | Swrl : A semantic web rule language combining owl and ruleml[END_REF] which allows us to represent the dynamic aspect of the intelligent environment operation. Thanks to the Semantic Query-Enhanced Web Rule Language SQWRL [START_REF] O'connor | Sqwrl : A query language for owl[END_REF], we can query the ontology in order to find anomalies or missing information and thus check the conformity of the model.

B. Necessary checks

Consistency and conformity of the model are checked with respect to two aspects :

-checking physical configuration, -checking user requirement. We also will check the state of the intelligent environment for different scenarios and verify general properties as human security, energy saving... An important part of the verifications will be done using OWL. However, it does not allow non-monotonic reasoning, which limits the verification process. For example it is not possible to represent a dynamic change in the state of an individual. General property verification is also outside the scope of OWL. So we envisage the second part of the verification process using Focal [START_REF] Prevosto | Certified mathematical hierarchies : the focal system[END_REF] which is an object oriented specification and proof system allowing to incrementally build components and to formally prove their correctness. We will show how we use OWL in this context.

IV. CONCEPTION OF THE ONTOLOGY

An ontology represents a domain knowledge in an understandable way for both human and computer. It is formed by a set of concepts which are organized hierarchically and defined by properties. Several studies have already shown an interest in ontology development of sensor networks [START_REF] Russomanno | Sensor ontologies : from shallow to deep models[END_REF], [START_REF] Avancha | Ontology-driven adaptive sensor networks[END_REF], intelligent environment [START_REF] Gu | An ontologybased context model in intelligent environments[END_REF], or sensor network component operation [START_REF] Wang | An ontology-based actuator discovery and invocation framework in home care systems[END_REF]. In this framework, we want to model the operation of an intelligent environment, taking into account the operation of a sensor network and its interaction with various objects of its environment.

The aim is to identify concepts (classes), terms (individuals) and relations (properties) of the domain, as well as the representation that will be the most appropriate to formally represent the intelligent environment operation.

The conceptual modeling of the intelligent environment is less likely to change than the needs of a user. Thus, the ontology structure (concepts and properties) can be defined and fixed by human study of the domain knowledge of intelligent environments and sensor networks. Contrariwise the ontology instantiation will vary depending on both environment configuration and requirement descriptions. So in the following we will focus on defining concepts and properties.

A. Concepts

From the intelligent environment section, it appears that we need to define concepts that represents sensor network components, locations, phenomena and physical processes.

In our model we decided to consider that the sensor network components are only sensors and actuators, since the operation of control devices could be modeled using the logic based formalism of OWL (constraints and inference rules). We also made the distinction of two types of phenomena, those which could appear suddenly (a person movement, gas leak...) that will belong to the class Event and those which could be measured (temperature, humidity...) that will belong to the class Measurable. It follows that we have to distinguish two concepts of sensors, those which detect an Event, that will belong to the class Detecting sensor and those that measure a Measurable, that will belong to the class Measuring sensor. Figure 3 shows the hierarchical organization of the ontology.

B. Properties

Properties represent interactions of concepts, they relate instances of concepts to some other instances or to a data type (int, string...). See below the properties that model the operating point of view on the network (between parenthesis appears the name of the related OWL property ) :

-A phenomenon has a type (Has type).

-A sensor has a location (Located in), has a zone of sensing (Zone of sensing), a zone of control (Zone of control) and perceives a type of phenomenon (Perceived type). -A Measuring sensor measures a measurable phenomenon (Measure). -A Detecting sensor detects an event (Detect).

-An actuator actuates on a physical process (Actuate on)

and manages one or several type(s) of phenomena (Managed type) Figure 3 shows how concepts interact in the ontology. The link Is a describes a taxonomic hierarchy along which concepts are inherited.

The notion of type is useful to associate phenomena, sensors and actuators which have to be involved in a same process. Thus we can warrant that a phenomenon will be handled by the proper sensor that will activate the proper actuator.

We distinguish two types of properties : i) the properties which will be created at the instantiation of the ontology, Located in, Zone of sensing and Actuate on which must be defined in the descriptions and will be used for inference ; ii) the properties that will be created by the reasoning process on the ontology, e.g. Detect and Measure which will be created by inference rules.

C. Individuals

The changing part of the ontology is its instantiation according to a specific environment and a user requirement. Individuals will be extracted automatically from the environment description and a scenario, together with their properties. These properties will be used during the reasoning process, to classify each individual in the class it belongs to.

D. Reasoning on the Ontology

During OWL reasoning, inferences are made, classifying elements of the ontology and creating new assertions while maintaining logical consistency.

1) Classification and Assertion: OWL axioms are used for the hierarchical organization of concepts and for the classification of individuals. Thus, assume C 1 , C 2 are concepts and P 1 , P 2 are properties. OWL defines two kinds of axioms. i) Inclusion axiom C 1 C 2 (P 1 P 2 ), e.g. Detecting sensor Sensor Each element of C 1 is an element of C 2 , i.e. C 1 is a sub class of C 2 ii) Equality axiom C 1 ≡ C 2 (P 1 ≡ P 2 ), e.g. Detecting sensor ≡ Sensor ∃Detect.Event Each element of C 1 is an element of C 2 and vice versa. To write more expressive conditional rules, we used the Semantic Web Rule Language (SWRL). In our model we distinguish two kinds of SWRL rules.

General rules : Are independent from textual descriptions and represent the generic behavior of the intelligent environment.

Instead of writing a rule for each kind of phenomenon, we modeled two rules in order to deduce that a phenomenon, a sensor and an actuator share the same type. Rule 1 : If the type of a phenomenon is the same as the type perceived by a sensor, then they share the same type.

Has type(?p, ?t), Perceived type(?s, ?t) → Shared type(?p, ?s) Rule 2 : If the type managed by an actuator is the same as the type perceived by a sensor, then they share the same type.

Managed type(?a, ?t), Perceived type(?s, ?t), → Shared type(?a, ?s) Rule 3 : A sensor detects an event if the event occurs in its zone of sensing.

Event(?e), Detecting sensor(?s), Shared type(?s, ?e), Located in(?e, ?l), Zone o f sensing(?s, ?l) → Detect(?s, ?e) Rule 4 : A sensor measures a measurable phenomenon if this phenomenon occurs in its zone of sensing.

Measuring sensor(?s), Measurable(?m), Shared type(?s, ?m), Located in(?m, ?l), Zone o f sensing(?s, ?l) → Measure(?s, ?m) Generated rules : Textual analysis will generate automatically rules to denote users requirement. We differentiate two parts in generated rules, a fix part and a part generated from requirement descriptions. (This second part is underlined in the rules) When a sensor detects an event, the actuator of the same type has to turn on the appliance it actuates on.

Actuator(?a), Physical process(?d), Actuate on(?a, ?d), Detect(?s, ?e), Shared type(?s, ?a), Located in(?a, ?l), Zone o f control(?s, ?l) → Turn on(?a, ?d) When a sensor measures a value greater than 30, then the actuator of the same type has to reduce the appliance it actuates on.

Actuator(?a), Physical process(?d), Actuate on(?a, ?d), Measure(?s, ?m), Shared type(?s, ?a), Located in(?a, ?l), Zone o f control(?s, ?l), Has value(?m, ?v), greaterT han(?v, 30) → Reduce(?a, ?d)

2) Consistency Checking: Classifications and assertions can be made only if they are consistent with the ontology Let C and C be classes, P a property, x and y individuals.

-If C is asserted as a subclass of C, it is necessary to verify that all individuals of the class C can belong to the class C. So if an individual of C cannot belong to C then the ontology is not consistent.

-If C(x) is asserted, it is necessary to verify that it is possible for the individual x to belong to the class C. So if x belongs to C which is disjoint with C then the ontology is not consistent.

-If P(x, y) is asserted it is necessary to check that x could belong to the domain of the property and y to the range.

3) Conformity Checking: To verify conformity of the intelligent environment, we query our ontology looking for wrong or missing specifications. We do this using SQWRL [START_REF] O'connor | Sqwrl : A query language for owl[END_REF], a SWRL-based language for querying OWL ontologies, providing SQL-like operations to retrieve knowledge from OWL. Thus, we can check whether two opposing actions may occur simultaneously.

V. APPLICATION

We will detail a case on which our model is applied in order to show how instantiations and verifications are made. The ontology building is realized under Protégé and the consistency and conformity checking are implemented under a java application using Jena, a Java framework for building Semantic Web applications.

Physical configuration description : the green apartment includes a hall, two bedrooms, one bathroom and a living room which includes a kitchen and a dining room. The sensor S temp measures the temperature of the living room. The sensor S move detects movements in the living room. The living is equipped with a light bulb L living on which an actuator AL living is fixed, and the dining room is equipped with a heater H dining on which an actuator AH dining is fixed. living room lighting scenario : When a person movement is detected in the living room, turn on the lights of the living room.

living room heating scenario : When a person movement is detected in the living room, and the temperature is below 25 degrees turn on the heater of the dining room.

A. Assertions and Consistency Checking

Below, assertions that have to be extracted from descriptions, follow by deductions they enable to produce : Static part 1) -living room which includes a kitchen. → Located in(dining room , living room) -dining room is equipped with a light bulb. → Located in(L living , dining room)

As Located in is transitive. Located in(dining room, livingroom) ∧ Located in(L living , living room) =⇒ Located in(L living , livingroom)
2) S temp measures the temperature of the living room. → Measure(S temp ,temp living ) As the domain of the property Measure is Measuring sensor. Measure(S temp ,temp living ) =⇒ Measuring sensor(S temp ) Dynamic part 1) When a person movement is detected in the living room ... Event(person movement), Sensor(S move ), Shared type(S move , person movement), Located in(person movement, living room), Zone o f sensing(S move , living room) → Detect(S move , person movement) Suppose this rule holds for for Sensor(S temp ), since the domain of Detect is Detecting sensor, it will be inferred that S temp is a Detecting sensor and thus an inconsistency will appear since in the conceptualization Detecting sensor and Measuring sensor are disjoint and so the individual S temp cannot belong to both.

2) When a person movement is detected in the living room, and the temperature is below 25 degree turn on the heater of the dining room.

Actuator(AH dining ), Located in(AH dining , living room), Actuate on(AH dining , H dining ), Physical process(H dining ), Detect(S move , person movement), Shared type(S move , AH dining ), Zone o f control(S move , living room), Measure(S temp ,temperature), Shared type(S temp , AH dining ), Zone o f control(S temp , living room), Has value(temperature, ?v), lessT hanOrEqual(?v, 24) -> Increase(AH dining , H dining )

The properties Shared type are deduced by the rule described in 5.4. We can notice that in our model actuators can react to different types of information. The types of this information have to be specified in the environment description. Suppose that there is another rule which holds, asserting Reduce(AH dining , H dining ). Since in our model properties Increase and Reduce are disjoint, an inconsistency will be generated which guarantees that an actuator cannot for a given instantiation do opposite actions. The case where another actuator tries to reduce the heater at the same time Reduce(another actuator, H dining ) cannot be prohibited by OWL. We resolve this problem thanks the conformity checking.

B. Conformity checking

By querying the ontology we can check whether the intelligent environment is correctly configured and identify missing specifications.

1) Incoherent scenario: Incoherence could result from the release of two opposite actions. Opposite properties : This query gives the intersection between sets of reduced and increased physical process. If the intersection is not empty then some asserted properties are opposite and the scenario has to be corrected. Let ?s1 is the set of reduced physical process, ?s2 is the set of increased physical process and ?s3 is the set of their intersection.

Reduce(?a1, ?d1)sqwrl : makeSet(?s1, ?d1) Increase(?a2, ?d2)sqwrl : makeSet(?s2, ?d2) sqwrl : intersection(?s3, ?s1, ?s2)sqwrl : size(?n, ?s3) → sqwrl : select(?n)

2) Missing information: Missing information can generate useless devices and prevent to use all the potential of the intelligent environment.

Sensors without Zone of Sensing : ?s1 is the set of all sensors of the ontology, ?s2 is the set of sensors which have a zone of sensing and ?s3 is the set of sensors without a defined zone of sensing.

Sensor(?s)sqwrl : makeSet(?s1, ?s)Sensor(?s zos) Zone o f sensing(?s zos, ?l)sqwrl : makeSet(?s2, ?s zos) sqwrl : di f f erence(?s3, ?s1, ?s2)sqwrl : size(?n, ?s3) → sqwrl : select(?n) Actuators without connection on a physical process : ?s1 is the set of all actuators of the ontology, ?s2 is the set of actuators which actuate on a physical process and ?s3 is the set of sensors which have without a physical process to actuate on Actuator(?a)sqwrl : makeSet(?s1, ?a)Actuate on(?ad, ?d) sqwrl : makeSet(?s2, ?ad)sqwrl : di f f erence(?s3, ?s1, ?s2) sqwrl : size(?n, ?s3) → sqwrl : select(?n)

VI. RELATED WORK

Formal models used for consistency verification or model checking of real-world systems, are generally conceived from natural language documents. Actually most of requirements are written in natural language, which could be wellunderstood by a domain expert or an ordinary person. So the issue of the transition from informal (natural language texts) to formal (specifications) arises naturally. Several studies have focused on it. [START_REF][END_REF] aims at applying several formal methods to certify documents of airport standard security regulations, these documents are analyzed by a model engineer in order to produce conceptual (graphical) models in UML applying requirements engineering methods [START_REF] Laleau | Application of requirements engineering techniques to the analysis of civil aviation security standards[END_REF]. The resulting models are transformed into formal models which will be verified by formal methods tools [START_REF] Delahaye | Certifying Airport Security Regulations using the Focal Environment[END_REF]. [START_REF] Fougères | Rédaction de spécifications formelles : élaboration à partir des spécifications écrites en langage naturel[END_REF] used conceptual graphs as an intermediary representation to formalize the interactions of telecommunication services and generate formal specifications in Z notation. [START_REF] Bryant | Two-level grammar as an objectoriented requirements specification language[END_REF] presents how the Two-Level Grammar (TLG), a specification language of requirements [START_REF] Bryant | Formal specification of natural language syntax using two-level grammar[END_REF], is used as an intermediate to transit from natural language into formal specifications in VDM++, an object-oriented version of the Vienna Development Method. These approaches reveal the need of an intermediary representation to go from informal to formal specification.

Our choice of an OWL ontology as conceptual representation is motivated by its semantic which is more expressive than the cited approaches and its logical formalism that allows the system to reason formally on the represented knowledge. Thus the kind of intermediate representation we chose allows us to make verifications at this stage of analysis, using properties of OWL, and to rely on formal methods, that are heavier, only for proving general properties.

The automatic construction of ontology from texts in natural language is a hard task, and a fully automatic approach is not realistic. Identifying the relevant concepts of a domain is semantically too difficult to be done efficiently without a human interaction. So the most common approach consists in a semi-automatic building of ontology. Several methods and tools were developed for ontology conception, [START_REF] Biebow | Terminae : a method and a tool to build a domain ontology[END_REF], [START_REF] Cimiano | Text2onto -a framework for ontology learning and data-driven change discovery[END_REF], [START_REF] Buitelaar | A protege plug-in for ontology extraction from text based on linguistic analysis[END_REF], [START_REF] Buitelaar | OntoLT : A Protege Plug-In for Ontology Extraction from Text[END_REF], however the complexity of our model that does not rely on the definition and the organization of a lot of concepts and relations, did not require their use.

The ontology we propose differs from [START_REF] Russomanno | Sensor ontologies : from shallow to deep models[END_REF] as their ontology is analogous to a database for querying and searching sensors. Thus all kinds of sensors are modeled according to the perceived types of phenomena. A same remarks can be made for [START_REF] Avancha | Ontology-driven adaptive sensor networks[END_REF] which describes sensor functionality and current state. [START_REF] Wang | An ontology-based actuator discovery and invocation framework in home care systems[END_REF] is closer to our work as it proposes an ontology for actuator discovery and the definition of high-level behaviors. However their modeling requires the description of sub-classes of devices, which entails to define all of them, and may be incomplete, and, in the same way, different types of operations, which are generic properties in our model that are inferred according to the kind of phenomenon perceived.

Our ambition is to allow a non expert user to pilot her own environment, and to recognize erroneous or incomplete specifications in order to give her some help for improving them. Thus, our approach finds its originality with the automatic instantiation of an ontology and the dynamic production of rules from the textual analysis of natural language descriptions, which allows us to do verifications. In our approach, what we need to check is not the conceptual modeling of the ontology but its instantiations, i.e. descriptions of the physical configuration of the environment and of the user requirement.

VII. CONCLUSION AND FUTURE WORK

In this article, a conceptual representation of the operation of an intelligent environment was defined and implemented, using an OWL ontology. The resulting ontology aims at facilitating the transition from natural language descriptions to formal specifications in order to check all along the consistency and the conformity of the conceptual specifications. The model we proposed acts in two steps. The first one, the static part, represents the environment and enables the system to check both its conformity and the network consistency. The second one, the dynamic part, enables to create rules that represent users' scenarios and to verify their consistency. This formalization will allow the system to navigate between texts and formal specifications to correct or improve the textual descriptions.

The conceptual representation which is the bridge between natural language specifications and formal specifications, is the first step in the process of developing easy to use and reliable tools for intelligent environment configuration. Our future work will focus on the automatic analysis of textual descriptions and the development of an interactive process with the user to translate her needs in a formal representation.

R ÉF ÉRENCES

FIGURE 1 :

 1 FIGURE 1: Architecture of the configuration process