Identifying the biomarkers from the personalized gene interaction network of individual patients is important for disease diagnosis. However, existing methods not only ignore the prior biomarkers for practical use but also ignore the observability of the entire system. Therefore, this paper proposes a new constrained multi-objective optimization-based temporal network observability model (CMTNO) to identify biomarkers, which not only requires minimizing the number of selected nodes including ordinary nodes and prior nodes (the first optimization objective) but also maximizing the number of selected prior nodes (the second optimization objective) on the premise of ensuring network observability (the constraint condition). Considering the temporal feature of cancer (patients belong to different stages and each patient contains one task), an experience learning-based constrained multi-objective evolutionary algorithm is designed to solve the CMTNO problems. The selected probabilities of ordinary nodes and prior nodes are treated as experience, stored in two separate archives and updated by the optimal solutions on each task. Experience utilization refers to using two archives to generate new initial populations for new patients, in order to improve the optimization efficiency of the algorithm. Besides, a two-step neighbor-based connectivity method is proposed to distinguish different nodes with similar connectivity to further improve the effectiveness of archives. The proposed model and algorithm are evaluated on three kinds of cancer patients' data under two kinds of network models, and results show their effectiveness in identifying effective biomarkers.

Structural network control principles provided novel and efficient clues for the optimization of personalized drug targets (PDTs) related to state transitions of individual patients. However, most existing methods focus on one subnetwork or module as drug targets through the identification of the minimal set of driver nodes and ignore the state transition capabilities of other modules with different configurations of drug targets [i.e. multimodal drug targets (MDTs)] embedding the knowledge of previous drug targets (i.e. multiobjective optimization). Therefore, a novel multimodal multiobjective evolutionary optimization framework (called MMONCP) is proposed to optimize PDTs with network control principles. The key points of MMONCP are that a constrained multimodal multiobjective optimization problem is formed with discrete constraints on the decision space and multimodality characteristics, and a novel evolutionary algorithm denoted as CMMOEA-GLS-WSCD is designed by combining a global and local search strategy and a weighting-based special crowding distance strategy to balance the diversity of both objective and decision space. The experimental results on three cancer genomics data from The Cancer Genome Atlas indicate that MMONCP achieves a higher performance including algorithm convergence and diversity, the fraction of identified MDTs, and the area under the curve score than advanced algorithms. Additionally, MMONCP can detect the early state from the difference between the target activity and toxicity of MDTs and provide early treatment options for cancer treatment in precision medicine.

Biological markers (i.e., biomarkers) are the key to predicting disease states and revealing the molecular mechanisms in precision medicine of complex diseases (e.g., cancer). With the advancement of high-throughput sequencing technology, there has been a significant increase in the volume and diversity of known disease omics data, where many methods have been developed to identify potential disease biomarkers (DBs) for mining the complex dynamics. As emerging artificial intelligence techniques, evolutionary computation (EC) has found extensive application in the identification of DBs, making significant achievements in mining disease omics data. However, there is currently no survey or analysis available of the existing EC methods to identify DBs on the disease omics data, resulting in missed opportunities to enhance performance and achieve successful applications in precision medicine. This article aims to present a comprehensive overview of the latest EC methods for mining the dynamics of DBs, including the summary of biomolecular omics datasets, the classification of the EC methods for DB discovery, and performance comparisons of the typical EC methods. Additionally, this article discusses challenges and potential future directions of the EC methods in the identification of DBs, providing directions and prospects for future research.

It is a big challenge to develop efficient models for identifying personalized drug targets (PDTs) from high-dimensional personalized genomic profile of individual patients. Recent structural network control principles have introduced a new approach to discover PDTs by selecting an optimal set of driver genes in personalized gene interaction network (PGIN). However, most of current methods only focus on controlling the system through a minimum driver-node set and ignore the existence of multiple candidate driver-node sets for therapeutic drug target identification in PGIN. Therefore, this paper proposed multi-objective optimization-based structural network control principles (MONCP) by considering minimum driver nodes and maximum prior-known drug-target information. To solve MONCP, a discrete multi-objective optimization problem is formulated with many constrained variables, and a novel evolutionary optimization model called LSCV-MCEA was developed by adapting a multi-tasking framework and a rankings-based fitness function method. With genomics data of patients with breast or lung cancer from The Cancer Genome Atlas database, the effectiveness of LSCV-MCEA was validated. The experimental results indicated that compared with other advanced methods, LSCV-MCEA can more effectively identify PDTs with the highest Area Under the Curve score for predicting clinically annotated combinatorial drugs. Meanwhile, LSCV-MCEA can more effectively solve MONCP than other evolutionary optimization methods in terms of algorithm convergence and diversity. Particularly, LSCV-MCEA can efficiently detect disease signals for individual patients with BRCA cancer. The study results show that multi-objective optimization can solve structural network control principles effectively and offer a new perspective for understanding tumor heterogeneity in cancer precision medicine. The source code of our LSCV-MCEA and supplementary files can be freely downloaded from https://github.com/WilfongGuo/MONCP, with all data in this study.

Considering that cancer is resulting from the comutation of several essential genes of individual patients, researchers have begun to focus on identifying personalized edge-network biomarkers (PEBs) using personalized edge-network analysis for clinical practice. However, most of existing methods ignored the optimization of PEBs when multimodal biomarkers exist in multi-purpose early disease prediction (MPEDP). To solve this problem, this study proposes a novel model (MMPDENB-RBM) that combines personalized dynamic edge-network biomarkers (PDENB) theory, multimodal optimization strategy and latent space search scheme to identify biomarkers with different configurations of PDENB modules (i.e. to effectively identify multimodal PDENBs). The application to the three largest cancer omics datasets from The Cancer Genome Atlas database (i.e. breast invasive carcinoma, lung squamous cell carcinoma and lung adenocarcinoma) showed that the MMPDENB-RBM model could more effectively predict critical cancer state compared with other advanced methods. And, our model had better convergence, diversity and multimodal property as well as effective optimization ability compared with the other state-of-art methods. Particularly, multimodal PDENBs identified were more enriched with different functional biomarkers simultaneously, such as tissue-specific synthetic lethality edge-biomarkers including cancer driver genes and disease marker genes. Importantly, as our aim, these multimodal biomarkers can perform diverse biological and biomedical significances for drug target screen, survival risk assessment and novel biomedical sight as the expected multi-purpose of personalized early disease prediction. In summary, the present study provides multimodal property of PDENBs, especially the therapeutic biomarkers with more biological significances, which can help with MPEDP of individual cancer patients.

Constrained multiobjective optimization problems (CMOPs) involve multiple objectives to be optimized and various constraints to be satisfied, which challenges the evolutionary algorithms in balancing the objectives and constraints. This article attempts to explore and utilize the relationship between constrained Pareto front (CPF) and unconstrained Pareto front (UPF) to solve CMOPs. Especially, for a given CMOP, the evolutionary process is divided into the learning stage and the evolving stage. The purpose of the learning stage is to measure the relationship between CPF and UPF. To this end, we first create two populations and evolve them by specific learning strategies to approach the CPF and UPF, respectively. Then, the feasibility information and dominance relationship of the two populations are used to determine the relationship. Based on the learned relationship, specific evolving strategies are designed in the evolving stage to improve the utilization efficiency of objective information, so as to better solve this CMOP. By the above process, a new constrained multiobjective evolutionary algorithm (CMOEA) is presented. Comprehensive experimental results on 65 benchmark functions and ten real-world CMOPs show that the proposed method has a better or very competitive performance in comparison with several state-of-the-art CMOEAs. Moreover, this article demonstrates that using the relationship between CPF and UPF to guide the utilization of objective information is promising in solving CMOPs.

Finding personalized biomarkers for disease prediction of patients with cancer remains a massive challenge in precision medicine. Most methods focus on one subnetwork or module as a network biomarker; however, this ignores the early warning capabilities of other modules with different configurations of biomarkers (i.e. multi-modal personalized biomarkers). Identifying such modules would not only predict disease but also provide effective therapeutic drug target information for individual patients. To solve this problem, we developed a novel model (denoted multi-modal personalized dynamic network biomarkers (MMPDNB)) based on a multi-modal optimization mechanism and personalized dynamic network biomarker (PDNB) theory, which can provide multiple modules of personalized biomarkers and unveil their multi-modal properties. Using the genomics data of patients with breast or lung cancer from The Cancer Genome Atlas database, we validated the effectiveness of the MMPDNB model. The experimental results showed that compared with other advanced methods, MMPDNB can more effectively predict the critical state with the highest early warning signal score during cancer development. Furthermore, MMPDNB more significantly identified PDNBs containing driver and biomarker genes specific to cancer tissues. More importantly, we validated the biological significance of multi-modal PDNBs, which could provide effective drug targets of individual patients as well as markers for predicting early warning signals of the critical disease state. In conclusion, multi-modal optimization is an effective method to identify PDNBs and offers a new perspective for understanding tumor heterogeneity in cancer precision medicine.

BACKGROUND: Cancer is a heterogeneous disease in which tumor genes cooperate as well as adapt and evolve to the changing conditions for individual patients. It is a meaningful task to discover the personalized cancer driver genes that can provide diagnosis and target drug for individual patients. However, most of existing methods mainly ranks potential personalized cancer driver genes by considering the patient-specific nodes information on the gene/protein interaction network. These methods ignore the personalized edge weight information in gene interaction network, leading to false positive results. RESULTS: In this work, we presented a novel algorithm (called PDGPCS) to predict the Personalized cancer Driver Genes based on the Prize-Collecting Steiner tree model by considering the personalized edge weight information. PDGPCS first constructs the personalized weighted gene interaction network by integrating the personalized gene expression data and prior known gene/protein interaction network knowledge. Then the gene mutation data and pathway data are integrated to quantify the impact of each mutant gene on every dysregulated pathway with the prize-collecting Steiner tree model. Finally, according to the mutant gene's aggregated impact score on all dysregulated pathways, the mutant genes are ranked for prioritizing the personalized cancer driver genes. Experimental results on four TCGA cancer datasets show that PDGPCS has better performance than other personalized driver gene prediction methods. In addition, we verified that the personalized edge weight of gene interaction network can improve the prediction performance. CONCLUSIONS: PDGPCS can more accurately identify the personalized driver genes and takes a step further toward personalized medicine and treatment. The source code of PDGPCS can be freely downloaded from https://github.com/NWPU-903PR/PDGPCS .

BACKGROUND: Recently, many computational methods have been proposed to predict cancer genes. One typical kind of method is to find the differentially expressed genes between tumour and normal samples. However, there are also some genes, for example, 'dark' genes, that play important roles at the network level but are difficult to find by traditional differential gene expression analysis. In addition, network controllability methods, such as the minimum feedback vertex set (MFVS) method, have been used frequently in cancer gene prediction. However, the weights of vertices (or genes) are ignored in the traditional MFVS methods, leading to difficulty in finding the optimal solution because of the existence of many possible MFVSs. RESULTS: Here, we introduce a novel method, called weighted MFVS (WMFVS), which integrates the gene differential expression value with MFVS to select the maximum-weighted MFVS from all possible MFVSs in a protein interaction network. Our experimental results show that WMFVS achieves better performance than using traditional bio-data or network-data analyses alone. CONCLUSION: This method balances the advantage of differential gene expression analyses and network analyses, improves the low accuracy of differential gene expression analyses and decreases the instability of pure network analyses. Furthermore, WMFVS can be easily applied to various kinds of networks, providing a useful framework for data analysis and prediction.

In the past few years, a wealth of sample-specific network construction methods and structural network control methods has been proposed to identify sample-specific driver nodes for supporting the Sample-Specific network Control (SSC) analysis of biological networked systems. However, there is no comprehensive evaluation for these state-of-the-art methods. Here, we conducted a performance assessment for 16 SSC analysis workflows by using the combination of 4 sample-specific network reconstruction methods and 4 representative structural control methods. This study includes simulation evaluation of representative biological networks, personalized driver genes prioritization on multiple cancer bulk expression datasets with matched patient samples from TCGA, and cell marker genes and key time point identification related to cell differentiation on single-cell RNA-seq datasets. By widely comparing analysis of existing SSC analysis workflows, we provided the following recommendations and banchmarking workflows. (i) The performance of a network control method is strongly dependent on the up-stream sample-specific network method, and Cell-Specific Network construction (CSN) method and Single-Sample Network (SSN) method are the preferred sample-specific network construction methods. (ii) After constructing the sample-specific networks, the undirected network-based control methods are more effective than the directed network-based control methods. In addition, these data and evaluation pipeline are freely available on https://github.com/WilfongGuo/Benchmark_control.

To understand tumor heterogeneity in cancer, personalized driver genes (PDGs) need to be identified for unraveling the genotype-phenotype associations corresponding to particular patients. However, most of the existing driver-focus methods mainly pay attention on the cohort information rather than on individual information. Recent developing computational approaches based on network control principles are opening a new way to discover driver genes in cancer, particularly at an individual level. To provide comprehensive perspectives of network control methods on this timely topic, we first considered the cancer progression as a network control problem, in which the expected PDGs are altered genes by oncogene activation signals that can change the individual molecular network from one health state to the other disease state. Then, we reviewed the network reconstruction methods on single samples and introduced novel network control methods on single-sample networks to identify PDGs in cancer. Particularly, we gave a performance assessment of the network structure control-based PDGs identification methods on multiple cancer datasets from TCGA, for which the data and evaluation package also are publicly available. Finally, we discussed future directions for the application of network control methods to identify PDGs in cancer and diverse biological processes.

Counting the occurrence frequency of each $k$k-mer in a biological sequence is a preliminary yet important step in many bioinformatics applications. However, most $k$k-mer counting algorithms rely on a given $k$k to produce single-length $k$k-mers, which is inefficient for sequence analysis for different $k$k. Moreover, existing $k$k-mer counters focus more on DNA and RNA sequences and less on protein ones. In practice, the analysis of $k$k-mers in protein sequences can provide substantial biological insights in structure, function, and evolution. To this end, an efficient algorithm, called MulMer (Multiple-Mer mining), is proposed to mine $k$k-mers of various lengths termed multi-mers via inverted-index technique, which is orders of magnitude faster than the conventional forward-index methods. Moreover, to the best of our knowledge, MulMer is the first able to mine multi-mers in a variety of sequences, including DNA, RNA, and protein sequences.

Although existing computational models have identified many common driver genes, it remains challenging to identify the personalized driver genes by using samples of an individual patient. Recently, the methods of exploiting the structure-based control principles of complex networks provide new clues for identifying minimum number of driver nodes to drive the state transition of large-scale complex networks from an initial state to the desired state. However, the structure-based network control methods cannot be directly applied to identify the personalized driver genes due to the unknown network dynamics of the personalized system. Here we proposed the personalized network control model (PNC) to identify the personalized driver genes by employing the structure-based network control principle on genetic data of individual patients. In PNC model, we firstly presented a paired single sample network construction method to construct the personalized state transition network for capturing the phenotype transitions between healthy and disease states. Then, we designed a novel structure-based network control method from the Feedback Vertex Sets-based control perspective to identify the personalized driver genes. The wide experimental results on 13 cancer datasets from The Cancer Genome Atlas firstly showed that PNC model outperforms current state-of-the-art methods, in terms of F-measures for identifying cancer driver genes enriched in the gold-standard cancer driver gene lists. Furthermore, these results showed that personalized driver genes can be explored by their network characteristics even when they are hidden factors in transcription and mutation profiles. Our PNC gives novel insights and useful tools into understanding the tumor heterogeneity in cancer. The PNC package and data resources used in this work can be freely downloaded from https://github.com/NWPU-903PR/PNC.

Motivation: It is a challenging task to discover personalized driver genes that provide crucial information on disease risk and drug sensitivity for individual patients. However, few methods have been proposed to identify the personalized-sample driver genes from the cancer omics data due to the lack of samples for each individual. To circumvent this problem, here we present a novel single-sample controller strategy (SCS) to identify personalized driver mutation profiles from network controllability perspective. Results: SCS integrates mutation data and expression data into a reference molecular network for each patient to obtain the driver mutation profiles in a personalized-sample manner. This is the first such a computational framework, to bridge the personalized driver mutation discovery problem and the structural network controllability problem. The key idea of SCS is to detect those mutated genes which can achieve the transition from the normal state to the disease state based on each individual omics data from network controllability perspective. We widely validate the driver mutation profiles of our SCS from three aspects: (i) the improved precision for the predicted driver genes in the population compared with other driver-focus methods; (ii) the effectiveness for discovering the personalized driver genes and (iii) the application to the risk assessment through the integration of the driver mutation signature and expression data, respectively, across the five distinct benchmarks from The Cancer Genome Atlas. In conclusion, our SCS makes efficient and robust personalized driver mutation profiles predictions, opening new avenues in personalized medicine and targeted cancer therapy. Availability and implementation: The MATLAB-package for our SCS is freely available from http://sysbio.sibcb.ac.cn/cb/chenlab/software.htm. Contact: [email protected] or [email protected] or [email protected]. Supplementary information: Supplementary data are available at Bioinformatics online.

The inference of gene regulatory networks (GRNs) from expression data can mine the direct regulations among genes and gain deep insights into biological processes at a network level. During past decades, numerous computational approaches have been introduced for inferring the GRNs. However, many of them still suffer from various problems, e.g., Bayesian network (BN) methods cannot handle large-scale networks due to their high computational complexity, while information theory-based methods cannot identify the directions of regulatory interactions and also suffer from false positive/negative problems. To overcome the limitations, in this work we present a novel algorithm, namely local Bayesian network (LBN), to infer GRNs from gene expression data by using the network decomposition strategy and false-positive edge elimination scheme. Specifically, LBN algorithm first uses conditional mutual information (CMI) to construct an initial network or GRN, which is decomposed into a number of local networks or GRNs. Then, BN method is employed to generate a series of local BNs by selecting the k-nearest neighbors of each gene as its candidate regulatory genes, which significantly reduces the exponential search space from all possible GRN structures. Integrating these local BNs forms a tentative network or GRN by performing CMI, which reduces redundant regulations in the GRN and thus alleviates the false positive problem. The final network or GRN can be obtained by iteratively performing CMI and local BN on the tentative network. In the iterative process, the false or redundant regulations are gradually removed. When tested on the benchmark GRN datasets from DREAM challenge as well as the SOS DNA repair network in E.coli, our results suggest that LBN outperforms other state-of-the-art methods (ARACNE, GENIE3 and NARROMI) significantly, with more accurate and robust performance. In particular, the decomposition strategy with local Bayesian networks not only effectively reduce the computational cost of BN due to much smaller sizes of local GRNs, but also identify the directions of the regulations.