In gene expression analysis, understanding a biological event that is observed at some time instance often requires capturing genes whose expression levels modulate before and after the event. Such genes are expected to be the responders to the event and will exhibit similar expression patterns during the event. However, after the effect of the event fades, their expression levels may loose their correlation. Hence, it is a non-trivial task to identify genes that share highly similar local expression patterns nearby the event and also allowing some level of divergent expression patterns further away from the event’s time point. Here, we propose LOCOS (LOcal COSine), a novel time-course clustering algorithm tailored to cluster genes exhibiting similar expression patterns within a specified time interval. LOCOS is an extension of the traditional Non-negative Matrix Factorization (NMF), which incorporates the cosine similarity and Euclidean distances in its update procedure. LOCOS maximizes the cosine similarity within an interval of interest, while allowing a relaxed minimization of Euclidean distance outside it. Using synthetic and non-biological time-course data, we showed that LOCOS was able to correctly detect the known local patterns within a specified interval. Furthermore, we used longitudinal single-cell RNA-seq samples from four patients showing deteriorating and recovering health conditions to identify genes related to each of the phenotype. As a result, LOCOS was able to capture gene clusters with distinct expression patterns that aligned with the intervals embedding the clinical deterioration and recovery events.

Hierarchical clustering, a traditional clustering method, has been getting attention again. Among several reasons, a credit goes to a recent paper by Dasgupta in 2016 that proposed a cost function that quantitatively evaluates hierarchical clustering trees. An important question is how to combine this recent advance with existing successful clustering methods. In this paper, we propose a hierarchical clustering method to minimize the cost function of clustering tree by incorporating existing clustering techniques. First, we developed an ensemble tree-search method that finds an integrated tree with reduced cost by integrating multiple existing hierarchical clustering methods. Second, to operate on large and arbitrary shape data, we designed an efficient hierarchical clustering framework, called integrating divisive and ensemble-agglomerate (IDEA) by combining it with advanced clustering techniques such as nearest neighbor graph construction, divisive-agglomerate hybridization, and dynamic cut tree. The IDEA clustering method showed better performance in minimizing Dasgupta's cost and improving accuracy (adjusted rand index) over existing cost-minimization-based, and density-based hierarchical clustering methods in experiments using arbitrary shape datasets and complex biology-domain datasets.