FastKnock: an efficient next-generation approach to identify all knockout strategies for strain optimization.

Overproduction of desired native or nonnative biochemical(s) in (micro)organisms can be achieved through metabolic engineering. Appropriate rewiring of cell metabolism is performed by making rational changes such as insertion, up-/down-regulation and knockout of genes and consequently metabolic reactions. Finding appropriate targets (including proper sets of reactions to be knocked out) for metabolic engineering to design optimal production strains has been the goal of a number of computational algorithms. We developed FastKnock, an efficient next-generation algorithm for identifying all possible knockout strategies (with a predefined maximum number of reaction deletions) for the growth-coupled overproduction of biochemical(s) of interest. We achieve this by developing a special depth-first traversal algorithm that allows us to prune the search space significantly. This leads to a drastic reduction in execution time. We evaluate the performance of the FastKnock algorithm using various Escherichia coli genome-scale metabolic models in different conditions (minimal and rich mediums) for the overproduction of a number of desired metabolites. FastKnock efficiently prunes the search space to less than 0.2% for quadruple- and 0.02% for quintuple-reaction knockouts. Compared to the classic approaches such as OptKnock and the state-of-the-art techniques such as MCSEnumerator methods, FastKnock found many more beneficial and important practical solutions. The availability of all the solutions provides the opportunity to further characterize, rank and select the most appropriate intervention strategy based on any desired evaluation index. Our implementation of the FastKnock method in Python is publicly available at https://github.com/leilahsn/FastKnock .

FastKnock: An efficient next-generation approach to identify all knockout strategies for strain optimization.

Overproduction of desired native or nonnative biochemical(s) in (micro)organisms can be achieved through metabolic engineering. Appropriate rewiring of cell metabolism is performed making rational changes such as insertion, up-/down-regulation and knockout of genes and consequently metabolic reactions. Finding appropriate targets (including proper sets of reactions to be knocked out) for metabolic engineering to design optimal production strains has been the goal of a number of computational algorithms. We developed FastKnock, an efficient next-generation algorithm for identifying all possible knockout strategies for the growth-coupled overproduction of biochemical(s) of interest. We achieve this by developing a special depth-first traversal algorithm that allows us to prune the search space significantly. This leads to a drastic reduction in execution time. We evaluate the performance of the FastKnock algorithm using three Escherichia coli genome-scale metabolic models in different conditions (minimal and rich mediums) for the overproduction of a number of desired metabolites. FastKnock efficiently prunes the search space to less than 0.2% for quadruple and 0.02% for quintuple-reaction knockouts. Compared to the classic approaches such as OptKnock and the state-of-the-art techniques such as MCSEnumerator methods, FastKnock found many more useful and important practical solutions. The availability of all the solutions provides the opportunity to further characterize and select the most appropriate intervention strategy based on any desired evaluation index. Our implementation of the FastKnock method in Python is publicly available at https://github.com/leilahsn/FastKnock.

Optimizing testing strategies for early detection of disease outbreaks in animal trade networks via MCMC.

The animal trades between farms and other livestock holdings form a complex livestock trade network. The movement of animals between trade actors plays an important role in the spread of infectious diseases among premises. Particularly, the outbreak of silent diseases that have no clinically obvious symptoms in the animal trade system should be diagnosed by taking special tests. In practice, the authorities regularly conduct examinations on a random number of farms to make sure that there was no outbreak in the system. However, these actions, which aim to discover and block a disease cascade, are yet far from the effective and optimum solution and often fail to prevent epidemics. A testing strategy is defined as making decisions about distributing the fixed testing budget N between farms/nodes in the network. In this paper, first, we apply different heuristics for selecting sentinel farms on real and synthetic pig-trade networks and evaluate them by simulating disease spreading via the SI epidemic model. Later, we propose a Markov chain Monte Carlo (MCMC) based testing strategy with the aim of early detection of outbreaks. The experimental results show that the proposed method can reasonably well decrease the size of the outbreak on both the realistic synthetic and real trade data. A targeted selection of an N/52 fraction of nodes in the real pig-trade network based on the MCMC or simulated annealing can improve the performance of a baseline strategy by 89%. The best heuristic-based testing strategy results in a 75% reduction in the average size of the outbreak compared to that of the baseline testing strategy.

A Temporal Network Model for Livestock Trade Systems.

The movements of animals between farms and other livestock holdings for trading activities form a complex livestock trade network. These movements play an important role in the spread of infectious diseases among premises. For studying the disease spreading among animal holdings, it is of great importance to understand the structure and dynamics of the trade system. In this paper, we propose a temporal network model for animal trade systems. Furthermore, a novel measure of node centrality important for disease spreading is introduced. The experimental results show that the model can reasonably well describe these spreading-related properties of the network and it can generate crucial data for research in the field of the livestock trade system.

Moving the epidemic tipping point through topologically targeted social distancing.

The epidemic threshold of a social system is the ratio of infection and recovery rate above which a disease spreading in it becomes an epidemic. In the absence of pharmaceutical interventions (i.e. vaccines), the only way to control a given disease is to move this threshold by non-pharmaceutical interventions like social distancing, past the epidemic threshold corresponding to the disease, thereby tipping the system from epidemic into a non-epidemic regime. Modeling the disease as a spreading process on a social graph, social distancing can be modeled by removing some of the graphs links. It has been conjectured that the largest eigenvalue of the adjacency matrix of the resulting graph corresponds to the systems epidemic threshold. Here we use a Markov chain Monte Carlo (MCMC) method to study those link removals that do well at reducing the largest eigenvalue of the adjacency matrix. The MCMC method generates samples from the relative canonical network ensemble with a defined expectation value of λ max . We call this the "well-controlling network ensemble" (WCNE) and compare its structure to randomly thinned networks with the same link density. We observe that networks in the WCNE tend to be more homogeneous in the degree distribution and use this insight to define two ad-hoc removal strategies, which also substantially reduce the largest eigenvalue. A targeted removal of 80% of links can be as effective as a random removal of 90%, leaving individuals with twice as many contacts. Finally, by simulating epidemic spreading via either an SIS or an SIR model on network ensembles created with different link removal strategies (random, WCNE, or degree-homogenizing), we show that tipping from an epidemic to a non-epidemic state happens at a larger critical ratio between infection rate and recovery rate for WCNE and degree-homogenized networks than for those obtained by random removals.