Abstract Motivation Single-cell sequencing technologies allow researchers to study cell-cell variation within a cell population. Variations between cells are driven by the underlying biological network, particularly gene regulatory networks (GRNs). GRNs rewire as cells evolve, and different cells can have different GRNs. However, while single-cell RNA-sequencing (scRNA-seq) and single-cell multi-omics data have been used to reconstruct GRNs, the output GRNs are rarely cell-specific, but rather, most existing methods infer population-level or cell-type-level GRNs. Results We propose CeSpGRN (Cell-Specific Gene Regulatory Network inference), a method that infers cell-specific GRNs from scRNA-seq, paired scRNA-seq and scATAC-seq, or spatial transcriptomic data. In particular, existing methods that use matching scRNA-seq and scATAC-seq data incorporate population-level region information in GRN inference, whereas CeSpGRN utilizes single-cell resolution region information. CeSpGRN infers cell-specific GRNs using a kernel-weighted Gaussian Copula Graphical Model, and incorporates multi-omic or spatial location information when constructing the objective function. We tested CeSpGRN on both simulated and real datasets, and the results show that CeSpGRN has a superior performance compared to baseline methods in reconstructing GRNs and detecting regulatory interactions that differ between cells. CeSpGRN uncovered regulatory interactions that rewire during biological processes on real datasets. Availability and implementation CeSpGRN is a Python package available at https://github.com/PeterZZQ/CeSpGRN.

MOTIVATION: The study of the evolutionary history of biological networks enables deep functional understanding of various bio-molecular processes. Network growth models, such as the Duplication-Mutation with Complementarity (DMC) model, provide a principled approach to characterizing the evolution of protein-protein interactions (PPIs) based on duplication and divergence. Current methods for model-based ancestral network reconstruction primarily use greedy heuristics and yield sub-optimal solutions. RESULTS: We present a new Integer Linear Programming (ILP) solution for maximum likelihood reconstruction of ancestral PPI networks using the DMC model. We prove the correctness of our solution that is designed to find the optimal solution. It can also use efficient heuristics from general-purpose ILP solvers to obtain multiple optimal and near-optimal solutions that may be useful in many applications. Experiments on synthetic data show that our ILP obtains solutions with higher likelihood than those from previous methods, and is robust to noise and model mismatch. We evaluate our algorithm on two real PPI networks, with proteins from the families of bZIP transcription factors and the Commander complex. On both the networks, solutions from our ILP have higher likelihood and are in better agreement with independent biological evidence from other studies. AVAILABILITY AND IMPLEMENTATION: A Python implementation is available at https://bitbucket.org/cdal/network-reconstruction. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.