MOTIVATION: Disease gene prioritization methods assign scores to genes or proteins according to their likely relevance for a given disease based on a provided set of seed genes. This scoring can be used to find new biologically relevant genes or proteins for many diseases. Although methods based on classical random walks have proven to yield competitive results, quantum walk methods have not been explored to this end. RESULTS: We propose a new algorithm for disease gene prioritization based on continuous-time quantum walks using the adjacency matrix of a protein-protein interaction (PPI) network. We demonstrate the success of our proposed quantum walk method by comparing it to several well-known gene prioritization methods on three disease sets, across seven different PPI networks. In order to compare these methods, we use cross-validation and examine the mean reciprocal ranks of recall and average precision values. We further validate our method by performing an enrichment analysis of the predicted genes for coronary artery disease. AVAILABILITY AND IMPLEMENTATION: The data and code for the methods can be accessed at https://github.com/markgolds/qdgp.

There is a lack of robust generalizable predictive biomarkers of response to immune checkpoint blockade in multiple types of cancer. We develop hDirect-MAP, an algorithm that maps T cells into a shared high-dimensional (HD) expression space of diverse T cell functional signatures in which cells group by the common T cell phenotypes rather than dimensional reduced features or a distorted view of these features. Using projection-free single-cell modeling, hDirect-MAP first removed a large group of cells that did not contribute to response and then clearly distinguished T cells into response-specific subpopulations that were defined by critical T cell functional markers of strong differential expression patterns. We found that these grouped cells cannot be distinguished by dimensional-reduction algorithms but are blended by diluted expression patterns. Moreover, these identified response-specific T cell subpopulations enabled a generalizable prediction by their HD metrics. Tested using five single-cell RNA-seq or mass cytometry datasets from basal cell carcinoma, squamous cell carcinoma and melanoma, hDirect-MAP demonstrated common response-specific T cell phenotypes that defined a generalizable and accurate predictive biomarker.

The blood cancer T cell large granular lymphocyte (T-LGL) leukemia is a chronic disease characterized by a clonal proliferation of cytotoxic T cells. As no curative therapy is yet known for this disease, identification of potential therapeutic targets is of immense importance. In this paper, we perform a comprehensive dynamical and structural analysis of a network model of this disease. By employing a network reduction technique, we identify the stationary states (fixed points) of the system, representing normal and diseased (T-LGL) behavior, and analyze their precursor states (basins of attraction) using an asynchronous Boolean dynamic framework. This analysis identifies the T-LGL states of 54 components of the network, out of which 36 (67%) are corroborated by previous experimental evidence and the rest are novel predictions. We further test and validate one of these newly identified states experimentally. Specifically, we verify the prediction that the node SMAD is over-active in leukemic T-LGL by demonstrating the predominant phosphorylation of the SMAD family members Smad2 and Smad3. Our systematic perturbation analysis using dynamical and structural methods leads to the identification of 19 potential therapeutic targets, 68% of which are corroborated by experimental evidence. The novel therapeutic targets provide valuable guidance for wet-bench experiments. In addition, we successfully identify two new candidates for engineering long-lived T cells necessary for the delivery of virus and cancer vaccines. Overall, this study provides a bird's-eye-view of the avenues available for identification of therapeutic targets for similar diseases through perturbation of the underlying signal transduction network.

BACKGROUND: Transcriptional regulation is a fundamental process in biological systems, where transcription factors (TFs) have been revealed to play crucial roles. In recent years, in addition to TFs, an increasing number of non-coding RNAs (ncRNAs) have been shown to mediate post-transcriptional processes and regulate many critical pathways in both prokaryotes and eukaryotes. On the other hand, with more and more high-throughput biological data becoming available, it is possible and imperative to quantitatively study gene regulation in a systematic and detailed manner. RESULTS: Most existing studies for inferring transcriptional regulatory interactions and the activity of TFs ignore the possible post-transcriptional effects of ncRNAs. In this work, we propose a novel framework to infer the activity of regulators including both TFs and ncRNAs by exploring the expression profiles of target genes and (post)transcriptional regulatory relationships. We model the integrated regulatory system by a set of biochemical reactions which lead to a log-bilinear problem. The inference process is achieved by an iterative algorithm, in which two linear programming models are efficiently solved. In contrast to available related studies, the effects of ncRNAs on transcription process are considered in this work, and thus more reasonable and accurate reconstruction can be expected. In addition, the approach is suitable for large-scale problems from the viewpoint of computation. Experiments on two synthesized data sets and a model system of Escherichia coli (E. coli) carbon source transition from glucose to acetate illustrate the effectiveness of our model and algorithm. CONCLUSION: Our results show that incorporating the post-transcriptional regulation of ncRNAs into system model can mine the hidden effects from the regulation activity of TFs in transcription processes and thus can uncover the biological mechanisms in gene regulation in a more accurate manner. The software for the algorithm in this paper is available upon request.

Transcriptional regulation is a fundamental process in biological systems, where transcription factors (TFs) play crucial roles. Except for TFs, an increasing number of small non-coding RNAs (ncRNAs) have been shown to mediate post-transcriptional processes in both prokaryotes and eukaryotes. In this work, we propose a novel approach to infer the activities of regulators including TFs and ncRNAs by exploring target gene expression profiles and (post) transcriptional regulatory relationships. The inference process is efficiently achieved by an iteration algorithm, in which two linear programming models are iteratively solved. In contrast to the existing works, for the first time, the effects of ncRNAs on transcription process are considered and thus more reasonable inference can be expected. Experiments on a model system of E. coli carbon source transition from glucose to acetate illustrate the effectiveness of our method.

MOTIVATION: Inferring the relationships between transcription factors (TFs) and their targets has utmost importance for understanding the complex regulatory mechanisms in cellular systems. However, the transcription factor activities (TFAs) cannot be measured directly by standard microarray experiment owing to various post-translational modifications. In particular, cooperative mechanism and combinatorial control are common in gene regulation, e.g. TFs usually recruit other proteins cooperatively to facilitate transcriptional reaction processes. RESULTS: In this article, we propose a novel method for inferring transcriptional regulatory networks (TRN) from gene expression data based on protein transcription complexes and mass action law. With gene expression data and TFAs estimated from transcription complex information, the inference of TRN is formulated as a linear programming (LP) problem which has a globally optimal solution in terms of L(1) norm error. The proposed method not only can easily incorporate ChIP-Chip data as prior knowledge, but also can integrate multiple gene expression datasets from different experiments simultaneously. A unique feature of our method is to take into account protein cooperation in transcription process. We tested our method by using both synthetic data and several experimental datasets in yeast. The extensive results illustrate the effectiveness of the proposed method for predicting transcription regulatory relationships between TFs with co-regulators and target genes.

BACKGROUND: Domains are the basic functional units of proteins. It is believed that protein-protein interactions are realized through domain interactions. Revealing multi-domain cooperation can provide deep insights into the essential mechanism of protein-protein interactions at the domain level and be further exploited to improve the accuracy of protein interaction prediction. RESULTS: In this paper, we aim to identify cooperative domains for protein interactions by extending two-domain interactions to multi-domain interactions. Based on the high-throughput experimental data from multiple organisms with different reliabilities, the interactions of domains were inferred by a Linear Programming algorithm with Multi-domain pairs (LPM) and an Association Probabilistic Method with Multi-domain pairs (APMM). Experimental results demonstrate that our approach not only can find cooperative domains effectively but also has a higher accuracy for predicting protein interaction than the existing methods. Cooperative domains, including strongly cooperative domains and superdomains, were detected from major interaction databases MIPS and DIP, and many of them were verified by physical interactions from the crystal structures of protein complexes in PDB which provide intuitive evidences for such cooperation. Comparison experiments in terms of protein/domain interaction prediction justified the benefit of considering multi-domain cooperation. CONCLUSION: From the computational viewpoint, this paper gives a general framework to predict protein interactions in a more accurate manner by considering the information of both multi-domains and multiple organisms, which can also be applied to identify cooperative domains, to reconstruct large complexes and further to annotate functions of domains. Supplementary information and software are provided in http://intelligent.eic.osaka-sandai.ac.jp/chenen/MDCinfer.htm and http://zhangroup.aporc.org/bioinfo/MDCinfer.

MOTIVATION: Haplotype reconstruction based on aligned single nucleotide polymorphism (SNP) fragments is to infer a pair of haplotypes from localized polymorphism data gathered through short genome fragment assembly. An important computational model of this problem is the minimum error correction (MEC) model, which has been mentioned in several literatures. The model retrieves a pair of haplotypes by correcting minimum number of SNPs in given genome fragments coming from an individual's DNA. RESULTS: In the first part of this paper, an exact algorithm for the MEC model is presented. Owing to the NP-hardness of the MEC model, we also design a genetic algorithm (GA). The designed GA is intended to solve large size problems and has very good performance. The strength and weakness of the MEC model are shown using experimental results on real data and simulation data. In the second part of this paper, to improve the MEC model for haplotype reconstruction, a new computational model is proposed, which simultaneously employs genotype information of an individual in the process of SNP correction, and is called MEC with genotype information (shortly, MEC/GI). Computational results on extensive datasets show that the new model has much higher accuracy in haplotype reconstruction than the pure MEC model.