Detecting list-colored graph motifs in biological networks using branch-and-bound strategy

Exploring gene-patient association to identify personalized cancer driver genes by linear neighborhood propagation

BACKGROUND

Driver genes play a vital role in the development of cancer. Identifying driver genes is critical for diagnosing and understanding cancer. However, challenges remain in identifying personalized driver genes due to tumor heterogeneity of cancer. Although many computational methods have been developed to solve this problem, few efforts have been undertaken to explore gene-patient associations to identify personalized driver genes.

RESULTS

Here we propose a method called LPDriver to identify personalized cancer driver genes by employing linear neighborhood propagation model on individual genetic data. LPDriver builds personalized gene network based on the genetic data of individual patients, extracts the gene-patient associations from the bipartite graph of the personalized gene network and utilizes a linear neighborhood propagation model to mine gene-patient associations to detect personalized driver genes. The experimental results demonstrate that as compared to the existing methods, our method shows competitive performance and can predict cancer driver genes in a more accurate way. Furthermore, these results also show that besides revealing novel driver genes that have been reported to be related with cancer, LPDriver is also able to identify personalized cancer driver genes for individual patients by their network characteristics even if the mutation data of genes are hidden.

CONCLUSIONS

LPDriver can provide an effective approach to predict personalized cancer driver genes, which could promote the diagnosis and treatment of cancer. The source code and data are freely available at https://github.com/hyr0771/LPDriver .

Predicting Disease-Associated N7-Methylguanosine (m7G) Sites via Random Walk on Heterogeneous Network

Recent studies revealed that the modification of N7-methylguanosine (m7G) has associations with many human diseases. Effectively identifying disease-associated m7G methylation sites would provide crucial clues for disease diagnosis and treatment. Previous studies have developed computational methods to predict disease-associated m7G sites based on similarities among m7G sites and diseases. However, few have focused on the influence of the known m7G-disease association information on calculating similarity measures of m7G site and disease, which potentially promotes the identification of the disease-associated m7G sites. In this work, we propose а computational method called m7GDP-RW to predict m7G-disease associations by random walk algorithm. m7GDP-RW first incorporates the feature information of m7G site and disease with the known m7G-disease associations to compute m7G site similarity and disease similarity. Then m7GDP-RW combines the known m7G-disease associations with the computed similarity of m7G site and disease to construct a m7G-disease heterogeneous network. Finally, m7GDP-RW utilizes a two-pass random walk with restart algorithm to find novel m7G-disease associations on the heterogeneous network. The experimental results show that our method achieves higher prediction accuracy compared to the existing methods. The study case also demonstrates the effectiveness of m7GDP-RW in discovering potential m7G-disease associations.

GEP-EpiSeeker: a gene expression programming-based method for epistatic interaction detection in genome-wide association studies

Background

Identification of epistatic interactions provides a systematic way for exploring associations among different single nucleotide polymorphism (SNP) and complex diseases. Although considerable progress has been made in epistasis detection, efficiently and accurately identifying epistatic interactions remains a challenge due to the intensive growth of measuring SNP combinations.

Results

In this work, we formulate the detection of epistatic interactions by a combinational optimization problem, and propose a novel evolutionary-based framework, called GEP-EpiSeeker, to detect epistatic interactions using Gene Expression Programming. In GEP-EpiSeeker, we propose several tailor-made chromosome rules to describe SNP combinations, and incorporate Bayesian network-based fitness evaluation into the evolution of tailor-made chromosomes to find suspected SNP combinations, and adopt the Chi-square test to identify optimal solutions from suspected SNP combinations. Moreover, to improve the convergence and accuracy of the algorithm, we design two genetic operators with multiple and adjacent mutations and an adaptive genetic manipulation method with fuzzy control to efficiently manipulate the evolution of tailor-made chromosomes. We compared GEP-EpiSeeker with state-of-the-art methods including BEAM, BOOST, AntEpiSeeker, MACOED, and EACO in terms of power, recall, precision and F1-score on the GWAS datasets of 12 DME disease models and 10 DNME disease models. Our experimental results show that GEP-EpiSeeker outperforms comparative methods.

Conclusions

Here we presented a novel method named GEP-EpiSeeker, based on the Gene Expression Programming algorithm, to identify epistatic interactions in Genome-wide Association Studies. The results indicate that GEP-EpiSeeker could be a promising alternative to the existing methods in epistasis detection and will provide a new way for accurately identifying epistasis.

Biogc: A novel framework for biological network classification via machine learning

Biological network classification is an eminently challenging task in the domain of data mining since the networks contain complex structural information. Conventional biochemical experimental methods and the existing intelligent algorithms still suffer from some limitations such as immense experimental cost and inferior accuracy rate. To solve these problems, in this paper, we propose a novel framework for Biological graph classification named Biogc, which is specifically developed to predict the label of both small-scale and large-scale biological network data flexibly and efficiently. Our framework firstly presents a simplified graph kernel method to capture the structural information of each graph. Then, the obtained informative features are adopted to train different scale biological network data-oriented classifiers to construct the prediction model. Extensive experiments on five benchmark biological network datasets on graph classification task show that the proposed model Biogc outperforms the state-of-the-art methods with an accuracy rate of 98.90% on a larger dataset and 99.32% on a smaller dataset.

Finding branched pathways in metabolic network via atom group tracking

Finding non-standard or new metabolic pathways has important applications in metabolic engineering, synthetic biology and the analysis and reconstruction of metabolic networks. Branched metabolic pathways dominate in metabolic networks and depict a more comprehensive picture of metabolism compared to linear pathways. Although progress has been developed to find branched metabolic pathways, few efforts have been made in identifying branched metabolic pathways via atom group tracking. In this paper, we present a pathfinding method called BPFinder for finding branched metabolic pathways by atom group tracking, which aims to guide the synthetic design of metabolic pathways. BPFinder enumerates linear metabolic pathways by tracking the movements of atom groups in metabolic network and merges the linear atom group conserving pathways into branched pathways. Two merging rules based on the structure of conserved atom groups are proposed to accurately merge the branched compounds of linear pathways to identify branched pathways. Furthermore, the integrated information of compound similarity, thermodynamic feasibility and conserved atom groups is also used to rank the pathfinding results for feasible branched pathways. Experimental results show that BPFinder is more capable of recovering known branched metabolic pathways as compared to other existing methods, and is able to return biologically relevant branched pathways and discover alternative branched pathways of biochemical interest. The online server of BPFinder is available at http://114.215.129.245:8080/atomic/. The program, source code and data can be downloaded from https://github.com/hyr0771/BPFinder.

Computational search of branched metabolic pathways is a fundamental problem in metabolic engineering and metabolic network analysis, which provides a systematic way of understanding the metabolism and discovering alternative pathways for synthesis of useful biomolecules. We propose BPFinder, a novel computational approach to identify branched metabolic pathways via atom group tracking. Different from other pathfinding methods using atom tracking, BPFinder tracks the movement of atom groups in metabolic network to find linear atom group conserving pathways, and merge the found linear pathways by the selected branched compounds to generate branched pathways. Based on the structure of conserved atom groups in branched compounds, we design two merging rules for branched compounds: overlapping rule and non-overlapping rule. The user can flexibly adopt these rules to accurately find the branched pathways that contain overlapping/non-overlapping conserved atom groups. BPFinder also enables the user to combine the information of compound similarity, Gibbs free energy of reactions, and conserved atom groups to sort resulting pathways. Compared with other existing methods, BPFinder can more accurately recover the known branched pathways. The alternative branched pathways returned by BPFinder reveal that the user can flexibly utilize our proposed merging rules to discover biochemically meaningful pathways of interest.