MarkovHC: Markov hierarchical clustering for the topological structure of high-dimensional single-cell omics data with transition pathway and critical point detection.

Clustering cells and depicting the lineage relationship among cell subpopulations are fundamental tasks in single-cell omics studies. However, existing analytical methods face challenges in stratifying cells, tracking cellular trajectories, and identifying critical points of cell transitions. To overcome these, we proposed a novel Markov hierarchical clustering algorithm (MarkovHC), a topological clustering method that leverages the metastability of exponentially perturbed Markov chains for systematically reconstructing the cellular landscape. Briefly, MarkovHC starts with local connectivity and density derived from the input and outputs a hierarchical structure for the data. We firstly benchmarked MarkovHC on five simulated datasets and ten public single-cell datasets with known labels. Then, we used MarkovHC to investigate the multi-level architectures and transition processes during human embryo preimplantation development and gastric cancer procession. MarkovHC found heterogeneous cell states and sub-cell types in lineage-specific progenitor cells and revealed the most possible transition paths and critical points in the cellular processes. These results demonstrated MarkovHC's effectiveness in facilitating the stratification of cells, identification of cell populations, and characterization of cellular trajectories and critical points.

BL-Hi-C is an efficient and sensitive approach for capturing structural and regulatory chromatin interactions.

In human cells, DNA is hierarchically organized and assembled with histones and DNA-binding proteins in three dimensions. Chromatin interactions play important roles in genome architecture and gene regulation, including robustness in the developmental stages and flexibility during the cell cycle. Here we propose in situ Hi-C method named Bridge Linker-Hi-C (BL-Hi-C) for capturing structural and regulatory chromatin interactions by restriction enzyme targeting and two-step proximity ligation. This method improves the sensitivity and specificity of active chromatin loop detection and can reveal the regulatory enhancer-promoter architecture better than conventional methods at a lower sequencing depth and with a simpler protocol. We demonstrate its utility with two well-studied developmental loci: the beta-globin and HOXC cluster regions.

Overshoot in biological systems modelled by Markov chains: a non-equilibrium dynamic phenomenon.

A number of biological systems can be modelled by Markov chains. Recently, there has been an increasing concern about when biological systems modelled by Markov chains will perform a dynamic phenomenon called overshoot. In this study, the authors found that the steady-state behaviour of the system will have a great effect on the occurrence of overshoot. They showed that overshoot in general cannot occur in systems that will finally approach an equilibrium steady state. They further classified overshoot into two types, named as simple overshoot and oscillating overshoot. They showed that except for extreme cases, oscillating overshoot will occur if the system is far from equilibrium. All these results clearly show that overshoot is a non-equilibrium dynamic phenomenon with energy consumption. In addition, the main result in this study is validated with real experimental data.

Using graphical adaptive lasso approach to construct transcription factor and microRNA's combinatorial regulatory network in breast cancer.

Discovering the regulation of cancer-related gene is of great importance in cancer biology. Transcription factors and microRNAs are two kinds of crucial regulators in gene expression, and they compose a combinatorial regulatory network with their target genes. Revealing the structure of this network could improve the authors' understanding of gene regulation, and further explore the molecular pathway in cancer. In this article, the authors propose a novel approach graphical adaptive lasso (GALASSO) to construct the regulatory network in breast cancer. GALASSO use a Gaussian graphical model with adaptive lasso penalties to integrate the sequence information as well as gene expression profiles. The simulation study and the experimental profiles verify the accuracy of the authors' approach. The authors further reveal the structure of the regulatory network, and explore the role of feedforward loops in gene regulation. In addition, the authors discuss the combinatorial regulatory effect between transcription factors and microRNAs, and select miR-155 for detailed analysis of microRNA's role in cancer. The proposed GALASSO approach is an efficient method to construct the combinatorial regulatory network. It also provides a new way to integrate different data sources and could find more applications in meta-analysis problem.

Population dynamics of cancer cells with cell state conversions.

Cancer stem cell (CSC) theory suggests a cell-lineage structure in tumor cells in which CSCs are capable of giving rise to the other non-stem cancer cells (NSCCs) but not vice versa. However, an alternative scenario of bidirectional interconversions between CSCs and NSCCs was proposed very recently. Here we present a general population model of cancer cells by integrating conventional cell divisions with direct conversions between different cell states, namely, not only can CSCs differentiate into NSCCs by asymmetric cell division, NSCCs can also dedifferentiate into CSCs by cell state conversion. Our theoretical model is validated when applying the model to recent experimental data. It is also found that the transient increase in CSCs proportion initiated from the purified NSCCs subpopulation cannot be well predicted by the conventional CSC model where the conversion from NSCCs to CSCs is forbidden, implying that the cell state conversion is required especially for the transient dynamics. The theoretical analysis also gives the condition such that our general model can be equivalently reduced into a simple Markov chain with only cell state transitions keeping the same cell proportion dynamics.

Kinetic behavior of the general modifier mechanism of Botts and Morales with non-equilibrium binding.

In this paper, we perform a complete analysis of the kinetic behavior of the general modifier mechanism of Botts and Morales in both equilibrium steady states and non-equilibrium steady states (NESS). Enlightened by the non-equilibrium theory of Markov chains, we introduce the net flux into discussion and acquire an expression of the rate of product formation in NESS, which has clear biophysical significance. Up till now, it is a general belief that being an activator or an inhibitor is an intrinsic property of the modifier. However, we reveal that this traditional point of view is based on the equilibrium assumption. A modifier may no longer be an overall activator or inhibitor when the reaction system is not in equilibrium. Based on the regulation of enzyme activity by the modifier concentration, we classify the kinetic behavior of the modifier into three categories, which are named hyperbolic behavior, bell-shaped behavior, and switching behavior, respectively. We show that the switching phenomenon, in which a modifier may convert between an activator and an inhibitor when the modifier concentration varies, occurs only in NESS. Effects of drugs on the Pgp ATPase activity, where drugs may convert from activators to inhibitors with the increase of the drug concentration, are taken as a typical example to demonstrate the occurrence of the switching phenomenon.

Nonlinear cooperation of p53-ING1-induced bax expression and protein S-nitrosylation in GSNO-induced thymocyte apoptosis: a quantitative approach with cross-platform validation.

Increasing evidence has been gathered for p53-dependent apoptosis, but it is still unclear how p53 initiates apoptosis by employing its transcriptional program. Pair-wise interactions of p53 with expression of other genes fail to predict p53 levels or rate of apoptosis. A more sophisticated approach, using neural networks, permits prediction of interaction among three or more genes (p53, bax, and ING1). These interactions are decidedly nonlinear. Careful measurements and advanced mathematical treatments will permit us not only to understand how expression of pro- and anti-apoptotic genes is regulated, but also to integrate cross-platform and cross-experimental data for the validation of predicted interactions.

Conservation and implications of eukaryote transcriptional regulatory regions across multiple species.

BACKGROUND: Increasing evidence shows that whole genomes of eukaryotes are almost entirely transcribed into both protein coding genes and an enormous number of non-protein-coding RNAs (ncRNAs). Therefore, revealing the underlying regulatory mechanisms of transcripts becomes imperative. However, for a complete understanding of transcriptional regulatory mechanisms, we need to identify the regions in which they are found. We will call these transcriptional regulation regions, or TRRs, which can be considered functional regions containing a cluster of regulatory elements that cooperatively recruit transcriptional factors for binding and then regulating the expression of transcripts. RESULTS: We constructed a hierarchical stochastic language (HSL) model for the identification of core TRRs in yeast based on regulatory cooperation among TRR elements. The HSL model trained based on yeast achieved comparable accuracy in predicting TRRs in other species, e.g., fruit fly, human, and rice, thus demonstrating the conservation of TRRs across species. The HSL model was also used to identify the TRRs of genes, such as p53 or OsALYL1, as well as microRNAs. In addition, the ENCODE regions were examined by HSL, and TRRs were found to pervasively locate in the genomes. CONCLUSION: Our findings indicate that 1) the HSL model can be used to accurately predict core TRRs of transcripts across species and 2) identified core TRRs by HSL are proper candidates for the further scrutiny of specific regulatory elements and mechanisms. Meanwhile, the regulatory activity taking place in the abundant numbers of ncRNAs might account for the ubiquitous presence of TRRs across the genome. In addition, we also found that the TRRs of protein coding genes and ncRNAs are similar in structure, with the latter being more conserved than the former.

Detecting differentially expressed genes by relative entropy.

DNA microarray experiments have generated large amount of gene expression measurements across different conditions. One crucial step in the analysis of these data is to detect differentially expressed genes. Some parametric methods, including the two-sample t-test (T-test) and variations of it, have been used. Alternatively, a class of non-parametric algorithms, such as the Wilcoxon rank sum test (WRST), significance analysis of microarrays (SAM) of Tusher et al. (2001), the empirical Bayesian (EB) method of Efron et al. (2001), etc., have been proposed. Most available popular methods are based on t-statistic. Due to the quality of the statistic that they used to describe the difference between groups of data, there are situations when these methods are inefficient, especially when the data follows multi-modal distributions. For example, some genes may display different expression patterns in the same cell type, say, tumor or normal, to form some subtypes. Most available methods are likely to miss these genes. We developed a new non-parametric method for selecting differentially expressed genes by relative entropy, called SDEGRE, to detect differentially expressed genes by combining relative entropy and kernel density estimation, which can detect all types of differences between two groups of samples. The significance of whether a gene is differentially expressed or not can be estimated by resampling-based permutations. We illustrate our method on two data sets from Golub et al. (1999) and Alon et al. (1999). Comparing the results with those of the T-test, the WRST and the SAM, we identified novel differentially expressed genes which are of biological significance through previous biological studies while they were not detected by the other three methods. The results also show that the genes selected by SDEGRE have a better capability to distinguish the two cell types.