Network-Based Methods to Identify Highly Discriminating Subsets of Biomarkers

An exact algorithm to find a maximum weight clique in a weighted undirected graph

We introduce a new algorithm MaxCliqueWeight for identifying a maximum weight clique in a weighted graph, and its variant MaxCliqueDynWeight with dynamically varying bounds. This algorithm uses an efficient branch-and-bound approach with a new weighted graph coloring algorithm that efficiently determines upper weight bounds for a maximum weighted clique in a graph. We evaluate our algorithm on random weighted graphs with node counts up to 10,000 and on standard DIMACS benchmark graphs used in a variety of research areas. Our findings reveal a remarkable improvement in computational speed when compared to existing algorithms, particularly evident in the case of high-density random graphs and DIMACS graphs, where our newly developed algorithm outperforms existing alternatives by several orders of magnitude. The newly developed algorithm and its variant are freely available to the broader research community at http://insilab.org/maxcliqueweight , paving the way for transformative applications in various research areas, including drug discovery.

Data analysis methods for defining biomarkers from omics data

Omics mainly includes genomics, epigenomics, transcriptomics, proteomics and metabolomics. The rapid development of omics technology has opened up new ways to study disease diagnosis and prognosis and to define prospective information of complex diseases. Since omics data are usually large and complex, the method used to analyze the data and to define important information is crucial in omics study. In this review, we focus on advances in biomarker discovery methods based on omics data in the last decade, and categorize them as individual feature analysis, combinatorial feature analysis and network analysis. We also discuss the challenges and perspectives in this field.

Feature selection with interactions in logistic regression models using multivariate synergies for a GWAS application

BACKGROUND

Genotype-phenotype association has been one of the long-standing problems in bioinformatics. Identifying both the marginal and epistatic effects among genetic markers, such as Single Nucleotide Polymorphisms (SNPs), has been extensively integrated in Genome-Wide Association Studies (GWAS) to help derive "causal" genetic risk factors and their interactions, which play critical roles in life and disease systems. Identifying "synergistic" interactions with respect to the outcome of interest can help accurate phenotypic prediction and understand the underlying mechanism of system behavior. Many statistical measures for estimating synergistic interactions have been proposed in the literature for such a purpose. However, except for empirical performance, there is still no theoretical analysis on the power and limitation of these synergistic interaction measures.

RESULTS

In this paper, it is shown that the existing information-theoretic multivariate synergy depends on a small subset of the interaction parameters in the model, sometimes on only one interaction parameter. In addition, an adjusted version of multivariate synergy is proposed as a new measure to estimate the interactive effects, with experiments conducted over both simulated data sets and a real-world GWAS data set to show the effectiveness.

CONCLUSIONS

We provide rigorous theoretical analysis and empirical evidence on why the information-theoretic multivariate synergy helps with identifying genetic risk factors via synergistic interactions. We further establish the rigorous sample complexity analysis on detecting interactive effects, confirmed by both simulated and real-world data sets.

Detecting Pairwise Interactive Effects of Continuous Random Variables for Biomarker Identification with Small Sample Size

Aberrant changes to interactions among cellular components have been conjectured to be potential causes of abnormalities in cellular functions. By systematic analysis of high-throughput-omics data, researchers hope to detect potential associations among measured variables for better biomarker identification and phenotype prediction. In this paper, we focus on the methods to measure pairwise interactive effects among continuous random variables, representing molecular expressions, with respect to a given categorical outcome. Together with a comprehensive review on the existing measures, we further propose new measures that better estimate interactive effects, especially in small sample size scenarios. We first evaluate the performance of the existing and new methods for both small and large sample sizes based on simulated datasets that shows our proposed methods outperform previous methods in general. The best performing method for small sample size scenarios suggested by simulation experiments is then implemented to estimate interactive effects among genes with respect to the metastasis outcome in two breast cancer studies based on micro-array gene expression datasets. Our results further demonstrate that integrating detected interactive effects together with individual effects can help in finding more accurate biomarkers for breast cancer metastasis, which are indeed involved in important pathways related to cancer metastasis based on gene set enrichment analysis.

Feature selection methods for big data bioinformatics: A survey from the search perspective

This paper surveys main principles of feature selection and their recent applications in big data bioinformatics. Instead of the commonly used categorization into filter, wrapper, and embedded approaches to feature selection, we formulate feature selection as a combinatorial optimization or search problem and categorize feature selection methods into exhaustive search, heuristic search, and hybrid methods, where heuristic search methods may further be categorized into those with or without data-distilled feature ranking measures.