**First year: 2015**

The first objective in this project was to improve the existing methods for inferring sequence/structural motifs for NLS identification.

We used for this an algorithm that had been developed in the team some years ago, Smile. The output of Smile is however sometimes not easy to be read depending on the number of motifs identified. We therefore developed a visualisation tool based on the Processing software.

Processing is an open source software suitable for visualising all types of data (and available at https://processing.org). This software is written in java and a user is able to write scripts to easily create complex images. In our case, we developed several scripts to map the occurrences of the motifs found in the original input sequences and to check whether we could identify visual patterns that stood out.

The analysis is ongoing. The initial results will also be discussed in November 2015 when we visit the Brazilian team who currently are working with other collaborators in Glasgow (team of M. Meissner).

**Second year: 2016**

We continued our study of sequence/structural motifs for NLS identification. This led to interesting results, namely to candidates that are now being experimentally tested in Brazil.

As concerns metabolism, we had previously developed the Pitufo (L. Cottret, P.V. Milreu, V. Acuna, A. Marchetti-Spaccamela, F. Viduani Martinez, M.F. Sagot, L. Stougie. Enumerating precursor sets of target metabolites in a metabolic network. Lecture Notes in Computer Science, vol. 5251, pp. 233-244, 2007; V. Acuña, P. V. Milreu, L. Cottret, A. Marchetti-Spaccamela, L. Stougie, M.-F. Sagot. Algorithms and complexity of enumerating minimal precursor sets in genome-wide metabolic networks. *Bioinformatics*, 28(19):2474-2483, 2012) family of algorithms and Gobbolino-Touché (V. Acuña, E. Birmelé, L. Cottret, P. Crescenzi, F. Jourdan, V. Lacroix, A. Marchetti-Spaccamela, A. Marino, P.V. Milreu, M.-F. Sagot, L. Stougie. Telling Stories: Enumerating maximal directed acyclic graphs with a constrained set of sources and targets. Theor. Comput. Sci., 457:1-9, 2012; P. V. Milreu, C. C. Klein, L. Cottret, V. Acuña, E. Birmelé, M. Borassi, C. Junot, A. Marchetti-Spaccamela, A. Marino, L. Stougie, F. Jourdan, P. Crescenzi, V. Lacroix, M.-F. Sagot. Telling metabolic stories to explore metabolomics data: a case study on the yeast response to cadmium exposure. *Bioinformatics*, 30(1):61-70, 2014) to, respectively, explore the metabolic exchanges between organisms and the impact of one on the metabolism of the other. Such methods were first attempts to address this exploration. We have since improved them. We recall that in all cases, we work with a directed hypergraph representation of the metabolism of an organism.

In relation to the metabolic exchanges, we start by recalling that what an organism needs at least from its environment to produce a set of metabolites, *e.g.* target(s) of interest and/or biomass, has been called a minimal precursor set. Our early approaches to enumerate all minimal precursor sets took into account only the topology of the metabolic network (topological precursor sets). Due to cycles and the stoichiometric values of the reactions, it is often not possible to produce the target(s) from a topological precursor set in the sense that there is no feasible flux. Although considering the stoichiometry makes the problem harder, it enables to obtain biologically reasonable precursor sets that we call stoichiometric. Recently a method to enumerate all minimal stoichiometric precursor sets was proposed in the literature (R. Zarecki, M.A. Oberhardt, L. Reshef, U. Gophna, E. Ruppin. A novel nutritional predictor links microbial fastidiousness with lowered ubiquity, growth rate, and cooperativeness. *PLoS Comput Biol.* 10(7):1-12, 2014). The relationship between topological and stoichiometric precursor sets had however not yet been studied.

Such relationship was explored in a recently accepted paper from the French team (R. Andrade, M. Wannagat, C.C. Klein, V. Acuña, A. Marchetti-Spaccamela, P.V. Milreu, L. Stougie, M.-F. Sagot. Enumeration of minimal stoichiometric precursor sets in metabolic networks. *Algorithms for Molecular Biology*, 11(1):25, 2016). In there, we also presented two algorithms that enumerate all minimal stoichiometric precursor sets. The first one is of theoretical interest only and is based on the above mentioned relationship. The second approach solves a series of mixed integer linear programming problems. We compared the computed minimal precursor sets to experimentally obtained growth media of several *Escherichia coli* strains using genome-scale metabolic networks.

The results showed that the second approach, called SASITA, efficiently enumerates minimal precursor sets taking stoichiometry into account, and allows for broad in silico studies of strains or species interactions that may help to understand *e.g.* pathotype and niche-specific metabolic capabilities.

SASITA is available at this address: http://sasita.gforge.inria.fr/

In relation to the impact of the metabolism of one organism on that of the another, we proposed two methods (papers in preparation) to decipher the reaction changes during a metabolic transient state using measurements of metabolic concentrations. We called these metabolic hyperstories.

TOTORO (for TOpological analysis of Transient metabOlic RespOnse) is based on a qualitative measurement of the concentrations in two steady-states to infer the reaction changes that lead to the observed differences in metabolite pools in both conditions. The software uses an ASP formulation to perform hyperarc selection in the directed hypergraph representation of a metabolic network. In the currently available release, a pre-processing and a post-processing steps are included. After the post-processing step, the solutions can be visualised using DINGHY (also developed in the French team, and available at: http://dinghy.gforge.inria.fr/).

KOTOURA (for Kantitative analysis Of Transient metabOlic and regUlatory Response And control) infers quantitative changes of the reactions using information on measurement of the metabolite concentrations in two steady-states. KOTOURA is developed in C++ and uses an IBM solver CPLEX.

Preliminary prototypes of TOTORO and KOTOURA are available upon request.