Date: October 22th, 2014
Place: room 102, Faculty of Science Bldg. 7, Hongo Campus, The University of Tokyo
Title: Multivariate Normal Approximation for the Stochastic Simulation Algorithm: limit theorem and applications
Speaker: Vincent Picard, Doctoral Student at IRISA-INRIA Rennes, INRIA Dyliss, Université de Rennes 1
Stochastic approaches in systems biology are being used increasingly to model the heterogeneity and the
intrinsic stochasticity of living systems, especially at the single-cell level. The stochastic simulation algorithm
— also known as the Gillespie algorithm — is currently the most widely used method to simulate the
time course of a system of bio-chemical reactions in a stochastic way.
In this talk, I will present a central limit theorem for the Gillespie stochastic trajectories when the living
system has reached a steady-state, that is when the internal bio-molecules concentrations are assumed to
be at equilibrium. It appears that the stochastic behaviour in steady-state is entirely characterized by the
stoichiometry matrix of the system and a single vector of reaction probabilities.
I propose several applications of this result such as deriving multivariate confidence regions for the time
course of the system and a constraints-based approach which extends the flux balance analysis framework
to the stochastic case.
Keywords: Stochastic Simulation, Multivariate statistics, Random walks
Title: On the route to the best flow against multilink attacks (MLA) in networks!
Speaker: Jean-François Baffier, Doctoral Student at The University of Tokyo – JFLI
Constructing a flow that resists attacks or failures has been considered in many studies. Often the problem is too complicated (in the way it targets a large range of problem) and tends to be hard to compute for many instances. Some approaches are too specific and their method cannot be used in the general case. In this work, we target a set of 3 problems that were based on the amount of information the attacker possesses about the network, and focus on solving the classical maximum flow problem in those conditions.
In the first setup, called MLA-robust, the attacker knows only about the structure of the graph (links, nodes,links capacities). In the second one, the MLA-reliable flow, the attacker also knows about the amount of flow going through each link. And lastly, for the MLA-decomposition, the attacker also knows our routing informations. Despite their simple formulation, those problems are hard (at least two are NP-hard).
However, by using a parametric variant of the multiroute flow (a flow with natural robustness properties), we are able to solve MLA-robust and MLA-reliable for 98% of the randomly generated instances. For those instances, we give a polynomial time method called iterative multiroute flow that construct the best (maximum) flow in MLA-robust and MLA-reliable setup. For any network, including the MLA-decomposition setup, we provide polynomial time approximation algorithm giving close to optimal value in our experiments.