MetNetComp: Database for Minimal and Maximal Gene-Deletion Strategies for Growth-Coupled Production of Genome-Scale Metabolic Networks.

Growth-coupled production, in which cell growth forces the production of target metabolites, plays an essential role in the production of substances by microorganisms. The strains are first designed using computational simulation and then validated by biological experiments. In the simulations, gene-deletion strategies are often necessary because many metabolites are not produced in the natural state of the microorganisms.

Gene Deletion Algorithms for Minimum Reaction Network Design by Mixed-Integer Linear Programming for Metabolite Production in Constraint-Based Models: gDel_minRN.

Genome-scale constraint-based metabolic networks play an important role in the simulation of growth-coupled production, which means that cell growth and target metabolite production are simultaneously achieved. For growth-coupled production, a minimal reaction-network-based design is known to be effective. However, the obtained reaction networks often fail to be realized by gene deletions due to conflicts with gene-protein-reaction (GPR) relations.

Trimming Gene Deletion Strategies for Growth-Coupled Production in Constraint-Based Metabolic Networks: TrimGdel.

When simulating genome-scale metabolite production using constraint-based metabolic networks, it is often necessary to find gene deletion strategies which lead to growth-coupled production, which means that target metabolites are produced when cell growth is maximized. Existing methods are effective when the number of gene deletions is relatively small, but when the number of required gene deletions exceeds approximately 1% of whole genes, the time required for the calculation is often unfeasible. Therefore, a complementing algorithm that is effective even when the required number of gene deletions is approximately 1% to 5% of whole genes would be helpful because the number of deletable genes in a strain is increasing with advances in genetic engineering technology.

Dynamic Solution Space Division-Based Methods for Calculating Reaction Deletion Strategies for Constraint-Based Metabolic Networks for Substance Production: DynCubeProd.

Flux balance analysis (FBA) is a crucial method to analyze large-scale constraint-based metabolic networks and computing design strategies for strain production in metabolic engineering. However, as it is often non-straightforward to obtain such design strategies to produce valuable metabolites, many tools have been proposed based on FBA. Among them, GridProd, which divides the solution space into small squares by focusing on the cell growth rate and the target metabolite production rate to efficiently find the reaction deletion strategies, was extended to CubeProd, which divides the solution space into small cubes.

Circulating Exosomal miRNA Profiles Predict the Occurrence and Recurrence of Hepatocellular Carcinoma in Patients with Direct-Acting Antiviral-Induced Sustained Viral Response.

Direct-acting antiviral (DAA) therapy for chronic hepatitis C virus (HCV) infection patients (CH) results in a sustained viral response (SVR) in over 95% of patients. However, hepatocellular carcinoma (HCC) occurs in 1-5% of patients who achieved an SVR after treatment with interferon. We attempted to develop a minimally invasive and highly reliable method of predicting the occurrence and recurrence of HCC in patients who achieved an SVR with DAA therapy.

Grid-based computational methods for the design of constraint-based parsimonious chemical reaction networks to simulate metabolite production: GridProd.

Background: Constraint-based metabolic flux analysis of knockout strategies is an efficient method to simulate the production of useful metabolites in microbes. Owing to the recent development of technologies for artificial DNA synthesis, it may become important in the near future to mathematically design minimum metabolic networks to simulate metabolite production.

Results: We have developed a computational method where parsimonious metabolic flux distribution is computed for designated constraints on growth and production rates which are represented by grids.

Computing Minimum Reaction Modifications in a Boolean Metabolic Network.

In metabolic network modification, we newly add enzymes or/and knock-out genes to maximize the biomass production with minimum side-effect. Although this problem has been studied for various problem settings via mathematical models including flux balance analysis, elementary mode, and Boolean models, some important problem settings still remain to be studied. In this paper, we consider the Boolean Reaction Modification (BRM) problem, where a host metabolic network and a reference metabolic network are given in the Boolean model.

Toward more accurate prediction of caspase cleavage sites: a comprehensive review of current methods, tools and features.

As one of the few irreversible protein posttranslational modifications, proteolytic cleavage is involved in nearly all aspects of cellular activities, ranging from gene regulation to cell life-cycle regulation. Among the various protease-specific types of proteolytic cleavage, cleavages by casapses/granzyme B are considered as essential in the initiation and execution of programmed cell death and inflammation processes. Although a number of substrates for both types of proteolytic cleavage have been experimentally identified, the complete repertoire of caspases and granzyme B substrates remains to be fully characterized.

Computational Methods for Modification of Metabolic Networks.

In metabolic engineering, modification of metabolic networks is an important biotechnology and a challenging computational task. In the metabolic network modification, we should modify metabolic networks by newly adding enzymes or/and knocking-out genes to maximize the biomass production with minimum side-effect. In this mini-review, we briefly review constraint-based formalizations for Minimum Reaction Cut (MRC) problem where the minimum set of reactions is deleted so that the target compound becomes non-producible from the view point of the flux balance analysis (FBA), elementary mode (EM), and Boolean models.

Computing smallest intervention strategies for multiple metabolic networks in a boolean model.

This article considers the problem whereby, given two metabolic networks N1 and N2, a set of source compounds, and a set of target compounds, we must find the minimum set of reactions whose removal (knockout) ensures that the target compounds are not producible in N1 but are producible in N2. Similar studies exist for the problem of finding the minimum knockout with the smallest side effect for a single network. However, if technologies of external perturbations are advanced in the near future, it may be important to develop methods of computing the minimum knockout for multiple networks (MKMN).

Colony-live--a high-throughput method for measuring microbial colony growth kinetics--reveals diverse growth effects of gene knockouts in Escherichia coli.

Background: Precise quantitative growth measurements and detection of small growth changes in high-throughput manner is essential for fundamental studies of bacterial cell. However, an inherent tradeoff for measurement quality in high-throughput methods sacrifices some measurement quality. A key challenge has been how to enhance measurement quality without sacrificing throughput.

Integer programming-based method for designing synthetic metabolic networks by Minimum Reaction Insertion in a Boolean model.

In this paper, we consider the Minimum Reaction Insertion (MRI) problem for finding the minimum number of additional reactions from a reference metabolic network to a host metabolic network so that a target compound becomes producible in the revised host metabolic network in a Boolean model. Although a similar problem for larger networks is solvable in a flux balance analysis (FBA)-based model, the solution of the FBA-based model tends to include more reactions than that of the Boolean model. However, solving MRI using the Boolean model is computationally more expensive than using the FBA-based model since the Boolean model needs more integer variables.

On control of singleton attractors in multiple Boolean networks: integer programming-based method.

Background: Boolean network (BN) is a mathematical model for genetic network and control of genetic networks has become an important issue owing to their potential application in the field of drug discovery and treatment of intractable diseases. Early researches have focused primarily on the analysis of attractor control for a randomly generated BN. However, one may also consider how anti-cancer drugs act in both normal and cancer cells.

Flux balance impact degree: a new definition of impact degree to properly treat reversible reactions in metabolic networks.

Motivation: Metabolic pathways are complex systems of chemical reactions taking place in every living cell to degrade substrates and synthesize molecules needed for life. Modeling the robustness of these networks with respect to the dysfunction of one or several reactions is important to understand the basic principles of biological network organization, and to identify new drug targets. While several approaches have been proposed for that purpose, they are computationally too intensive to analyze large networks, and do not properly handle reversible reactions.

Finding optimal control policy in probabilistic Boolean Networks with hard constraints by using integer programming and dynamic programming.

Boolean Networks (BNs) and Probabilistic Boolean Networks (PBNs) are studied in this paper from the viewpoint of control problems. For BN CONTROL, by applying external control, we propose to derive the network to the desired state within a few time steps. For PBN CONTROL, we propose to find a control sequence such that the network will terminate in the desired state with a maximum probability.

Network completion using dynamic programming and least-squares fitting.

We consider the problem of network completion, which is to make the minimum amount of modifications to a given network so that the resulting network is most consistent with the observed data. We employ here a certain type of differential equations as gene regulation rules in a genetic network, gene expression time series data as observed data, and deletions and additions of edges as basic modification operations. In addition, we assume that the numbers of deleted and added edges are specified.

A clique-based method using dynamic programming for computing edit distance between unordered trees.

Many kinds of tree-structured data, such as RNA secondary structures, have become available due to the progress of techniques in the field of molecular biology. To analyze the tree-structured data, various measures for computing the similarity between them have been developed and applied. Among them, tree edit distance is one of the most widely used measures.

Finding a periodic attractor of a Boolean network.

In this paper, we study the problem of finding a periodic attractor of a Boolean network (BN), which arises in computational systems biology and is known to be NP-hard. Since a general case is quite hard to solve, we consider special but biologically important subclasses of BNs. For finding an attractor of period 2 of a BN consisting of n OR functions of positive literals, we present a polynomial time algorithm.

A clique-based method for the edit distance between unordered trees and its application to analysis of glycan structures.

Background: Measuring similarities between tree structured data is important for analysis of RNA secondary structures, phylogenetic trees, glycan structures, and vascular trees. The edit distance is one of the most widely used measures for comparison of tree structured data. However, it is known that computation of the edit distance for rooted unordered trees is NP-hard.

Compound analysis via graph kernels incorporating chirality.

High accuracy is paramount when predicting biochemical characteristics using Quantitative Structural-Property Relationships (QSPRs). Although existing graph-theoretic kernel methods combined with machine learning techniques are efficient for QSPR model construction, they cannot distinguish topologically identical chiral compounds which often exhibit different biological characteristics. In this paper, we propose a new method that extends the recently developed tree pattern graph kernel to accommodate stereoisomers.

A dynamic programming algorithm to predict synthesis processes of tree-structured compounds with graph grammar.

For several decades, many methods have been developed for predicting organic synthesis paths. However these methods have non-polynomial computational time. In this paper, we propose a bottom-up dynamic programming algorithm to predict synthesis paths of target tree-structured compounds.

Integer programming-based method for completing signaling pathways and its application to analysis of colorectal cancer.

Signaling pathways are often represented by networks where each node corresponds to a protein and each edge corresponds to a relationship between nodes such as activation, inhibition and binding. However, such signaling pathways in a cell may be affected by genetic and epigenetic alteration. Some edges may be deleted and some edges may be newly added.

Analysis and prediction of nutritional requirements using structural properties of metabolic networks and support vector machines.

Properties of graph representation of genome scale metabolic networks have been extensively studied. However, the relationship between these structural properties and functional properties of the networks are still very unclear. In this paper, we focus on nutritional requirements of organisms as a functional property and study the relationship with structural properties of a graph representation of metabolic networks.

Algorithms and complexity analyses for control of singleton attractors in Boolean networks.

A Boolean network (BN) is a mathematical model of genetic networks. We propose several algorithms for control of singleton attractors in BN. We theoretically estimate the average-case time complexities of the proposed algorithms, and confirm them by computer experiments.