Integer programming-based method for observability of singleton attractors in Boolean networks

Disease biomarker identification based on sample network optimization

A large amount of evidence shows that biomarkers are discriminant features related to disease development. Thus, the identification of disease biomarkers has become a basic problem in the analysis of complex diseases in the medical fields, such as disease stage judgment, disease diagnosis and treatment. Research based on networks have become one of the most popular methods. Several algorithms based on networks have been proposed to identify biomarkers, however the networks of genes or molecules ignored the similarities and associations among the samples. It is essential to further understand how to construct and optimize the networks to make the identified biomarkers more accurate. On this basis, more effective strategies can be developed to improve the performance of biomarkers identification. In this study, a multi-objective evolution algorithm based on sample similarity networks has been proposed for disease biomarker identification. Specifically, we design the sample similarity networks to extract the structural characteristic information among samples, which used to calculate the influence of the sample to each class. Besides, based on the networks and the group of biomarkers we choose in every iteration, we can divide samples into different classes by the importance for each class. Then, in the process of evolution algorithm population iteration, we develop the elite guidance strategy and fusion selection strategy to select the biomarkers which make the sample classification more accurate. The experiment results on the five gene expression datasets suggests that the algorithm we proposed is superior over some state-of-the-art disease biomarker identification methods.

Data-Driven Boolean Network Inference Using a Genetic Algorithm With Marker-Based Encoding

The inference of Boolean networks is crucial for analyzing the topology and dynamics of gene regulatory networks. Many data-driven approaches using evolutionary algorithms have been proposed based on time-series data. However, the ability to infer both network topology and dynamics is restricted by their inflexible encoding schemes. To address this problem, we propose a novel Boolean network inference algorithm for inferring both network topology and dynamics simultaneously. The main idea is that, we use a marker-based genetic algorithm to encode both regulatory nodes and logical operators in a chromosome. By using the markers and introducing more logical operators, the proposed algorithm can infer more diverse candidate Boolean functions. The proposed algorithm is applied to five networks, including two artificial Boolean networks and three real-world gene regulatory networks. Compared with other algorithms, the experimental results demonstrate that our proposed algorithm infers more accurate topology and dynamics.

Exploring Observability of Attractor Cycles in Boolean Networks for Biomarker Detection

Boolean Network (BN) is a simple and popular mathematical model that has attracted significant attention from systems biology due to its capacity to reveal genetic regulatory network behavior. In addition, observability, as an important network feature, plays a vital role in deciphering the underlying mechanisms driving a genetic regulatory network and has been widely investigated. Prior studies examined observability of BNs and other complex networks. That said, observability of attractor, which can serve as a biomarker for disease, has not been fully examined in the literature. In this study, we formulated a new definition for singleton or cyclic attractor observability in BNs and developed an effective methodology to resolve the captured problem. We also showed complexity is of O(Pmn), when the maximal period of cyclic attractor is P, the number of attractor is m and the number of genes is n. Importantly, we have confirmed our method can faithfully predict the expression pattern of segment polarity genes in Drosophila melanogaster and showed it can effectively and efficiently deal with the captured observability problem.

Global Stabilization of Boolean Networks to Control the Heterogeneity of Cellular Responses

Boolean networks (BNs) have been widely used as a useful model for molecular regulatory networks in systems biology. In the state space of BNs, attractors represent particular cell phenotypes. For targeted therapy of cancer, there is a pressing need to control the heterogeneity of cellular responses to the targeted drug by reducing the number of attractors associated with the ill phenotypes of cancer cells. Here, we present a novel control scheme for global stabilization of BNs to a unique fixed point. Using a sufficient condition of global stabilization with respect to the adjacency matrix, we can determine a set of constant controls so that the controlled BN is steered toward an unspecified fixed point which can then be further transformed to a desired attractor by subsequent control. Our method is efficient in that it has polynomial complexity with respect to the number of state variables, while having exponential complexity with respect to in-degree of BNs. To demonstrate the applicability of the proposed control scheme, we conduct simulation studies using a regulation influence network describing the metastatic process of cells and the Mitogen-activated protein kinase (MAPK) signaling network that is crucial in cancer cell fate determination.

Discovery of Boolean metabolic networks: integer linear programming based approach

Background

Traditional drug discovery methods focused on the efficacy of drugs rather than their toxicity. However, toxicity and/or lack of efficacy are produced when unintended targets are affected in metabolic networks. Thus, identification of biological targets which can be manipulated to produce the desired effect with minimum side-effects has become an important and challenging topic. Efficient computational methods are required to identify the drug targets while incurring minimal side-effects.

Results

In this paper, we propose a graph-based computational damage model that summarizes the impact of enzymes on compounds in metabolic networks. An efficient method based on Integer Linear Programming formalism is then developed to identify the optimal enzyme-combination so as to minimize the side-effects. The identified target enzymes for known successful drugs are then verified by comparing the results with those in the existing literature.

Conclusions

Side-effects reduction plays a crucial role in the study of drug development. A graph-based computational damage model is proposed and the theoretical analysis states the captured problem is NP-completeness. The proposed approaches can therefore contribute to the discovery of drug targets. Our developed software is available at “http://hkumath.hku.hk/~wkc/APBC2018-metabolic-network.zip”.