# Network based simultaneous embedding of cells and marker genes from scRNA-seq studies

Namrata Bhattacharya, Swagatam Chakraborti, Stuti Kumari, Bernadette Mathew, Abhishek Halder, Sakshi Gujral, Krishan Gupta, Aayushi Mittal, Debajyoti Sinha, Colleen Nelson, et al.

► To cite this version:

Namrata Bhattacharya, Swagatam Chakraborti, Stuti Kumari, Bernadette Mathew, Abhishek Halder, et al.. Network based simultaneous embedding of cells and marker genes from scRNA-seq studies. Briefings in Bioinformatics, 2025, 26 (5), pp.bbf537. 10.1093/bib/bbf537. inserm-05357793

HAL Id: inserm-05357793

https://inserm.hal.science/inserm-05357793v1

Submitted on 10 Nov 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Network based simultaneous embedding of cells and marker genes from scRNA-seq studies

Namrata Bhattacharya<fnref n="1" />,<fnref n="2" />,<fnref n="3" />,†, Swagatam Chakraborti<fnref n="1" />,†, Stuti Kumari<fnref n="1" />, Bernadette Mathew<fnref n="4" />, Abhishek Halder<fnref n="1" />, Sakshi Gujral<fnref n="1" />, Krishan Gupta ID<fnref n="5" />, Aayushi Mittal<fnref n="4" />, Debajyoti Sinha<fnref n="6" />, Colleen Nelson<fnref n="2" />,<fnref n="3" />, Tanmoy Chakraborty<fnref n="7" />, Gaurav Ahuja ID<fnref n="4" />,*, Debarka Sengupta ID<fnref n="1" />,<fnref n="4" />,<fnref n="8" />,*

## Abstract

The complexity of scRNA-sequencing datasets highlights the urgent need for enhanced clustering and visualization methods. Here, we propose Stardust, an iterative, force-directed graph layout algorithm that enables the simultaneous embedding of cells and marker genes. Stardust, for the first time, allows a single-stop visualization of cells and marker genes on a single 2D map. While Stardust provides its own visualization pipeline, it can be plugged in with state-of-the-art methods such as Uniform Manifold Approximation and Projection (UMAP) and t-Distributed Stochastic Neighbor Embedding (t-SNE). We benchmarked Stardust against popular visualization and clustering tools on both scRNA-seq and spatial transcriptomics datasets. In all cases, Stardust performs competitively in identifying and visualizing cell types in an accurate and spatially coherent manner.

**Keywords:** scRNA-Seq; clustering; embedding; gene expression cartography

## Introduction

Messenger RNAs (mRNAs) are positioned at the center of genetic information flow and cast phenotypic dynamicity to a cell to help it adapt to its environment and external impulses. Microfluidic breakthroughs over the past few years have enabled high-throughput measurement of mRNAs at the single-cell resolution [1]. The recent emergence of spatial transcriptomics techniques has added a much-needed dimension to the field by enabling spatially resolved characterization of cellular diversity in situ, within a tissue [2, 3]. Further to it, today, multiplexed single-molecule Fluorescence in situ hybridization (FISH) measurements allow studying subcellular compartmentalization of RNA molecules [4]. Together, these breakthroughs have provided several degrees of freedom to our interrogation of complex biological systems, under normal, developmental, or pathological conditions. Harnessing such a multifactorial molecular information deluge requires the

assistance of unsupervised learning methods. As such, efficient dimensionality reduction and clustering of single-cell expression profiles play a pivotal role in the systemic appraisal of cell-to-cell variability [5]. Remarkably, the progressive evolution of such computational methods underscores the yet unsettled nature of this field [6–8].

Single cell RNA sequencing (scRNA-seq) data are inherently noisy due to the small amounts of starting RNA material and cell-to-cell technical biases [9, 10]. Trivial biological variability due to cell cycle stage, response to pathogens, cell viability, differential replicative age, etc., further impedes expression-based characterization of cellular heterogeneity. While the advent of novel clustering methods is significantly fast-paced, dimensionality reduction techniques transcend slowly. Recently, the field has embraced Uniform Manifold Approximation and Projection (UMAP) as the best practice method for the low-dimensional

<footnote n="1">¹Department of Computer Science and Engineering, Indraprastha Institute of Information Technology-Delhi (IIIT-Delhi), Okhla Industrial Estate, Phase III, New Delhi – 110020, Delhi, India</footnote>

<footnote n="2">²Australian Prostate Cancer Research Centre-Queensland, Faculty of Health, School of Biomedical Sciences, Centre for Genomics and Personalised Health, Queensland University of Technology, Kelvin Grove Campus, Victoria Park Road, Kelvin Grove, Brisbane, Queensland 4059, Australia</footnote>

<footnote n="3">³Princess Alexandra Hospital, Translational Research Institute, 37 Kent Street, Woolloongabba, Brisbane, Queensland 4102, Australia</footnote>

<footnote n="4">⁴Department of Computational Biology, Indraprastha Institute of Information Technology-Delhi (IIIT-Delhi), Okhla Industrial Estate, Phase III, New Delhi – 110020, Delhi, India</footnote>

<footnote n="5">⁵Department of Pediatrics, Boston Children's Hospital in Harvard Medical School, 300 Longwood Avenue, Boston, MA 02115, USA</footnote>

<footnote n="6">⁶Centre de Recherche en Transplantation et Immunologie, Inserm, CHU Nantes, UMR1064, ITUN, Université de Nantes, Chem. de la Censive du Tertre, 44300 Nantes, France</footnote>

<footnote n="7">⁷Department of Electrical Engineering, India Institute of Technology Delhi, Hauz Khas, New Delhi, Delhi 110016, India</footnote>

<footnote n="8">⁸Centre for Artificial Intelligence, Indraprastha Institute of Information Technology-Delhi (IIIT-Delhi), Okhla Industrial Estate, Phase III, New Delhi – 110020, Delhi, India</footnote>

<footnote>*Corresponding authors. Debarka Sengupta, Department of Computer Science and Engineering, Indraprastha Institute of Information Technology-Delhi (IIIT-Delhi), New Delhi 110020, India Okhla Industrial Estate, Phase III, New Delhi – 110020, Delhi, India, E-mail: debarka@iiitd.ac.in; Gaurav Ahuja, Department of Computational Biology, Indraprastha Institute of Information Technology-Delhi (IIIT-Delhi), New Delhi 110020, India Okhla Industrial Estate, Phase III, New Delhi – 110020, Delhi, India, E-mail: gaurav.ahuja@iiitd.ac.in</footnote>

<footnote>†Namrata Bhattacharya and Swagatam Chakraborti contributed equally.</footnote>
embedding of single-cells [8] due to improved segregation of distinct cell-types as compared to t-Distributed Stochastic Neighbor Embedding (t-SNE), and its "linear" ancestor Principal Component Analysis (PCA). UMAP's wide adoption highlighted the importance of spatial segregation of transcriptomically distinct cell-types in a 2D portrait of cells. Despite significant improvements, cell-clusters with remarkably different lineages are found on a transitional continuum of cellular identity with loosely defined boundaries. This frequently contradicts with clustering outcomes. We asked ourselves—"How do cells form distinct clusters yet run into each other's territory on a low-dimensional map?". This leads to the conclusion that the existing dimensionality reduction techniques might not be able to manifest transcriptional heterogeneity adequately, as otherwise teased out by the clustering algorithms. Due to this inability, abstract dimensions obtained from feature extraction/dimensionality reduction techniques are usually not used as features for clustering. Another practical difficulty is cross-referencing between the 2D map and the differential expression (DE) heatmap. For instance, the recently published Human Cell Landscape (HCL) reported 102 clusters obtained from ~700 000 cells from ~50 human tissues [11]. The sheer number of potential cell-types creates cognitive overload while inspecting clusters and their marker genes across the low-dimensional visualization and the DE heatmap. To address these challenges, we implemented Stardust, an iterative graph-layout algorithm for cell-gene co-embedding that teases out transcriptional heterogeneity in a manner that preserves cell-lineage identities without getting into the trap of over-clustering.

## Results and discussion
### Overview of Stardust

Stardust integrates genes and single-cells as part of the same network topology, with two legal categories of connections/edges: cell-cell and cell-gene based on nearest neighbor principles. While cell-cell connections are established based on their expression similarity, a gene is connected to a few top cells, wherein its relative abundance is high. On the first pass, genes are selected using PCA. For graph embedding, Stardust uses OpenOrd [12], a scalable and qualitatively improved variant of the force-directed graph layout algorithm. Cell-clusters obtained from OpenOrd-based low-dimensional embedding are subjected to DE analysis. DE genes thus obtained replace the PCA selected genes, which change the network conformation and thus the cell clusters. Clustering, DE analysis, and OpenOrd based layouts are performed iteratively until we arrive at stable clusters. Typically, this is achieved in three iterations. In the end i.e. on the fourth pass, for a given expression matrix, Stardust outputs 2D embedding of cells/DE genes, and their inferred cluster identities. Cell-type specific genes get naturally inscribed within the associated cell-clusters, thereby simplifying the visual interpretation of tissue heterogeneity. Besides OpenOrd based embeddings, due to the wide acceptance of UMAP, Stardust also allows the user to visualize clusters and the associated marker genes within a UMAP defined 2D space (Supplementary Fig. S1).

### Comparative benchmarking of Stardust visualization and clustering

We benchmarked Stardust visualization and clustering against numerous best practice methods. Notably, Stardust enables cell-gene co-embedding in a unified 2D space, which is compatible with all dimensionality reduction tools. In particular, we evaluated UMAP [8], t-SNE [13], and SPRING [14] for visualization

and Louvain [15], Leiden [15], SIMLR [16], and SC3 [17] for clustering, due to their wide acceptance in the community. For performance assessment, we acquired six publicly available scRNA seq datasets, of which four had cell type annotation available at the single-cell level. We applied Stardust UMAP, t-SNE, and SPRING to demonstrate accurate placement of DE genes across 2D visualization of given single-cells (Fig. 1a–d). In each visualization, clusters are obtained using Stardust. For each cluster, a representative upregulated gene (the top one) can be found inscribed within the respective clusters. To avoid overcrowding of the plots, Stardust empowers the user to choose the genes to annotate. Notably, we found Stardust visualization is highly consonant with UMAP based 2D organization of the cells. To assess the quality of clusters, we considered four datasets PBMC, Melanoma, Pollen, and Kolod. In each case, we benchmarked the clustering outcomes against cell annotations from an external source. We recorded normalized mutual information (NMI) for Stardust alongside widely used clustering methods Louvain (from Scanpy [18]), Leiden (from Scanpy), SIMLR and SC3. Stardust performed the best in terms of the recorded average NMI value. Whereas Louvain ranked second.

We critically examined clusters obtained by Stardust and Louvain on the Melanoma data. Melanoma data comprises 4645 scRNA-seq profiles from 19 patients, spanning both malignant and non-malignant cell-subtypes from human melanoma tumors. Marker-based bioinformatic annotations of the cells were obtained from the scMatch R package [19]. scMatch mapped the malignant cells into two categories based on its reference database i.e. melanoma cell lines and primary melanocytes. In the case of Stardust, besides T cell and monocyte subtypes, the majority of the nonmalignant cells were concentrated into a single cluster. As expected, the malignant cells were found distributed across multiple clusters, underscoring inter/intratumoral heterogeneity harbored by the malignant cells (Supplementary Fig. S2a). Conversely, Louvain-based clustering using Scanpy fragmented rather homogeneous populations of CD4+ and CD8+ cell-types into multiple clusters giving rise to discordance with annotations (Supplementary Fig. S2b). A major cell-type segregation ambiguity was spotted in cluster 4 (resulted by Louvain clustering), which shared a considerable number of cells from three scMatch annotated subpopulations namely CD4+/CD8+ T cells and Natural Killers. All these results collectively suggest that Stardust outperforms the current state of the art both in low-dimensional visualization of cells and clustering.

We repeated Stardust clustering and visualization using multiple additional datasets—PBMC data (~68 000 annotated cells), Liver data (~7000 cells with bioinformatically inferred cell types) [19], mouse brain data (~20 000 cells with bioinformatically inferred cell types) [20]. In all cases we found Stardust visualization, clustering, and marker gene co-embedding to be highly consonant with standard methods, author annotation and ground truth annotations, where available (Supplementary Figs. S3–S5). For all datasets except Kolod, and Pollen, where the number of cells is less, we computed and reported Silhouette scores of the clusters using Stardust and Louvain. Stardust consistently outperformed Louvain on all datasets (Supplementary Fig. S6). Cluster-specific top differentially upregulated genes obtained using Stardust and Scanpy (Louvain for clustering) are tabulated in a study-specific manner (Supplementary Table 1).

Beyond the aforementioned evaluation, we further investigated the efficiency of Stardust against widely adopted single-cell analysis pipelines using two independent scRNA-seq datasets. The performance of Stardust was compared with two conventional
<figure><img src="image_2.png" /><figcaption>Figure 1. Stardust based visualization and clustering of scRNA-seq profiles. (a) UMAP based visualization of the *Melanoma* data, with marker gene locations inferred by Stardust. (b) Stardust based co-embedding of cells and genes from the *Melanoma* dataset. (c) Alluvial plot depicting the correspondence between unsupervised clusters obtained using both the methods, and marker-based annotation of the single-cells using scMatch. (d) NMI computed on PBMC and *Melanoma* datasets cross-referencing the clusters with cell annotations. (e) Silhouette index computed on all the datasets to measure signal-to-noise ratio associated with 2D locations of the cell clusters. (f) Alluvial plot comparing clustering assignments between Louvain clusters (left) and Stardust clusters (right) based on shared immune cell type assignments.</figcaption></figure>

methods, Scanpy [18] and Seurat [20], as well as a deep learning-
based clustering method, DESC [21]. Additionally, it was bench-
marked against two transfer learning approaches, ItClust [22], and
ProjectR [23]. ItClust performs supervised transfer learning using
an autoencoder, while ProjectR implements transfer learning
via dimensionality reduction. While Stardust and ItClust are

resolution-independent, a default resolution of 1.0 was applied
for the other methods. We first evaluated clustering performance
on an ultra-large human prostate epithelium scRNA-seq dataset
(~29 000 cells) [24]. This was followed by analysis of a complex
immune scRNA-seq dataset with multiple covariates, comprising
splenocytes and matched PBMCs from four human donors (two
<figure><img src="image_3.png" /><figcaption>Figure 2. Benchmarking clustering methods on human prostate epithelium scRNA-seq data. (a–f) UMAP-based visualization of clustering results across different methods: (a) Stardust, (b) Scanpy, (c) Seurat, (d) ItClust, (e) scETM, and (f) DESC, benchmarked on the dataset from Henry et al. The cells are colored according to the clusters identified by each method. (g) Bar plots of ARI, NMI, and Silhouette coefficients for the different methods. The default resolution was set to 1.0.</figcaption></figure>

healthy and two brain-dead) with ~5000 cells [25]. For both the datasets, we used the author provided cell type annotations for benchmarking. Notably, Stardust produced clear, well-separated clusters corresponding to known cell types in both prostate and immune cell datasets, whereas alternative methods show substantial cluster fragmentation and mixing (Figs 2a–f and 3a–f). This enhanced structural clarity is attributed to Stardust’s underlying graph layout algorithm, which simultaneously captures cellular proximity and gene-level specificity. For quantitative evaluation, we recorded the Adjusted Rand Index (ARI) along with NMI and Silhouette coefficient (Fig. 2g and 3g). Stardust consistently achieved the highest or near-equivalent performance across these metrics, outperforming the other methods. These findings align with previous benchmarking results, where Stardust demonstrated the highest average NMI across diverse datasets, including PBMC, liver, and brain tissue, as well as consistently superior Silhouette coefficients. The combination of high cluster purity, strong alignment with known biological

annotations, and resolution-free implementation positions
Stardust as a robust and efficient clustering method.

Stardust accurately segregates influenza virus
infected cells

In the above comparative studies, we observed that Stardust visualization offers a higher signal-to-noise ratio for cell-type detection and segregation. To assess it further, we posed an independent and stricter challenge. Sun and colleagues profiled ~9000 cells, including uninfected A549 cells (originating from lung) as control, exposed to H1N1 but uninfected cells (bystanders) and exposed and infected cells [26]. The distinction between bystanders and infected cells was defined bioinformatically based on the availability of viral RNA traces in the single-cells. We hypothesized that cells with viral nucleic acid traces would have a different phenotype as compared to the bystanders. Visual separation of these infected cells thereby serves as a criterion to assess the performance of various dimensionality reduction techniques.
<figure><img src="image_4.png" /><figcaption>Figure 3. Benchmarking clustering methods on immune scRNAseq data. (a–f) UMAP-based visualization of clustering results across different methods: (a) Stardust, (b) Scanpy, (c) Seurat, (d) ItClust, (e) scETM, and (f) DESC, benchmarked on the dataset from Bhattacharya et al. The cells are colored according to the clusters identified by each method. (g) Bar plots of ARI, NMI, and Silhouette coefficients for the different methods. The default resolution was set to 1.0.</figcaption></figure>

To this end we subjected the single-cells to visualization using Stardust, alongside other widely used methods—UMAP, t-SNE, and SPRING. Notably, SPRING is comparable to Stardust since it is based on networks. All methods performed reasonably well in visually segregating the infected cells (Fig. 4a–d). Leakage of infected cells to other clusters or co-clustering of uninfected/by-stander cells with the infected cells could be due to imperfections associated with bioinformatic annotation of cells.

We quantitatively estimated these results using the Silhouette score, where Stardust scored the maximum, followed by t-SNE, UMAP, and SPRING (Fig. 4e). Taken together, the aforementioned comparative analysis clearly advocates the outperformance of Stardust on challenging datasets harboring mixed transcriptomic features from host cells and infecting pathogens.

## Cell-type zonation in drosophila embryo

In eukaryotes, cells often expand within a tissue niche, giving rise to cell-type zonation and patterned gene expression activities. As such, an accurate unsupervised clustering of scRNA-seq

profiles is expected to identify cell-groups that map with precise anatomical locations. To validate this, we considered *Drosophila* embryos, with simplistic and well-characterized morphometric features. We built on a previous work by Nitzan and colleagues [27] that successfully mapped ~1300 single-cell transcriptomes to the BDTNP virtual *Drosophila* embryos [28], using the gene expression cartography technique, while accurately preserving the spatial expression patterns of the well-known cell-lineage markers including the gap genes and the pair-rule genes. Stardust inferred 10 clusters from the scRNA-seq dataset, whereas Louvain could identify only seven clusters (Fig. 5a and b, Supplementary Fig. S7). We visualized the clusters using Stouffer's scores spanning cluster-specific marker genes, as well as its manually calibrated (by introducing a suitable threshold) binarized form (Supplementary Fig. S8). Interestingly, both Louvain and Stardust exhibited a reasonable degree of zonation of the inferred cell-types and their canonical markers. However, quite evidently, the overall segregation of the spatially proximal cell-types was better in the case of Stardust.
<figure><img src="image_5.png" /><figcaption>Figure 4. Segregation of H1N1 infected cells and bystanders. (a–d) Visualization of infected and uninfected (including bystanders and mock) cells using Stardust, t-SNE, UMAP, and SPRING. (e) Silhouette scores for the infected cells, computed based on Stardust, t-SNE, UMAP, and SPRING provided coordinates.</figcaption></figure>

Similar results were obtained from the intercluster DE analysis (Supplementary Fig. S9), where Stardust clustering led to the identification of marker genes, restricted to one or more clusters (Supplementary Table 2). As a proof-of-principle, we thoroughly investigated the anterior head region of the *Drosophila* embryo

since Stardust reported a larger number of putative cell types in this region. Careful interrogation of these clusters revealed neat bifurcation of the anterior endoderm anlage and the head mesoderm by Stardust, which Louvain failed to resolve (Stardust cluster 4, and 8 versus Louvain cluster 6) (Fig. 5c–e).
To further confirm the identity of these regions, we overlaid the publicly available in situ images available through the FlyBase webserver [29], along with the loss-of-function information of the identified markers. For example, *ImpL3* a gene, which encodes for L-lactate dehydrogenase, shows restricted expression in the anterior endoderm anlage at the embryonic stage 6 of the developing *Drosophila* larvae [30,31]. Similarly, Stardust identified *gcm*, a zinc finger transcription factor as a marker for cluster 8. This is in line with the available in situ hybridization images of *gcm* (Supplementary Table 2), which shows its restricted expression in the head mesoderm anlage at embryo stage 6. Of note, *gcm* is a reported marker for the head mesoderm [32], and its targets are known to regulate components of the Notch, Hedgehog (Hh), Wingless (Wg)/Wnt, Fibroblast Growth Factor (FGF) Receptor (FGFR), and JAK/STAT signaling pathways [33]. Next, as an orthogonal validation, we used probabilistic mapping scores of the top differentially expressed genes to predict the bin coordinates on the virtual embryo. Stardust produced lower values of Root Mean Squared Errors (RMSEs) as compared to Louvain (Supplementary Fig. S10). Next, we asked if Stardust inferred cell types are consistent when transcript abundance is measured using different expression assays. To this end, we compared scRNA-seq based cell clusters with the clusters of the positional bins (based on in situ expression quantification [28]). Stardust produced a highly structured similarity matrix as compared to Louvain (Supplementary Fig. S11).

Stardust employs an iterative cell-gene co-embedding algorithm that mirrors the spirit of an expectation-maximization process. It consumes significantly more time as compared to the existing best practice methods. For instance, in the case of ~68 K PBMC data Stardust took 1 h 48 min to complete the analysis, whereas Louvain took only 3.26 min. On the positive side, Stardust offers radically cleaner embedding of single-cells, as compared to the state of the art, and allows visualization of marker genes alongside single-cells. Further, its ability to distinguish functionally distinct cell populations with overlapping gene expression patterns makes it a promising alternative to the existing pipelines for scRNA-seq data analysis.

## Materials and methods
### Description of the datasets

We worked with nine different single-cell expression datasets to evaluate the Stardust for various analyses. The first dataset comprises ~68 000 peripheral blood mononuclear cell (PBMC) transcriptomes from a healthy donor. The authors annotated the cells by correlating their expression profiles with 11 common immune cell subtypes purified using Fluorescence-Activated Cell Sorting (FACS). This dataset served as a gold standard for comparative analysis of the clustering techniques. The second dataset consists of host and viral transcriptomes of ~9000 individual cells, infected with single influenza A virus (IAV) [26]. This dataset is used for comparative analysis of the visualization techniques. The third dataset consists of ~20 k single-cell transcriptomes sampled from the arcuate-median eminence complex (Arc-ME) region of mouse brain [34]. The fourth dataset consists of 4645 single-cell expression profiles sampled from melanomas of 19 patients [35]. Based on the available annotations we discarded the clusters with cluster-specific cell populations less than 50. The fifth dataset consisted of a scRNA-seq dataset of mouse embryonic stem cells consists of 301 single-cells from 11 populations [36]. Sixth dataset consists of 704 single-cell transcriptomes of pluripotent stem cell-derived cerebral

organoids from chimpanzees [37]. The seventh dataset consists of ~29 000 single-cell transcriptomes from normal prostate specimens, including young adult human prostate and prostatic urethra [24]. The eighth dataset consists of ~5000 single-cell transcriptomes obtained from splenocytes and matched PBMCs of four polytraumatized patients who underwent splenectomy hemostasis [25]. This dataset captures complex immune cell variation between spleen and peripheral blood. The ninth dataset is a scRNA-Seq data of the human liver comprising ~7000 cells [38]. We used spatially resolved single-cell transcriptomes of *Drosophila* embryo [39] The scRNA-Seq data reported in this study consists of ~1300 high-quality single-cells having >12,500 unique transcripts and expressing more than five genes of the Berkeley *Drosophila* Transcription Network Project (BDTNP) reference atlas [28] expressed over ~8000 genes. Karaiskos and colleagues putatively resolved the spatial location of the profiled single-cells by quantifying expression similarity across single-cells and ~3000 positional bins. Notably, the BDTNP reference atlas quantifies the relative mRNA levels of 84 genes in a virtual stage 5 *D. melanogaster* embryo [28].

### Preprocessing of the scRNA-Seq data

Expression matrices are loaded as AnnData objects, as implemented in the Scanpy pipeline [40]. Cells expressing less than 30% of the average number of expressed genes across cells are filtered. Further, we retained those genes which are detected in at least three cells. The filtered dataset is subjected to Unique Molecular Identifier (UMI) count normalization where the counts per cell are normalized to the median of the total counts of all the cells before normalization. The normalized expression matrix is further log-transformed after adding one as pseudocount. Percentage of the highly variable genes based on the size of the dataset is selected from the preprocessed expression matrix using the scanpy function i.e. `sc.pp.highly_variable genes()` with the parameter `n_top genes` set to 500. The function internally uses Cell Ranger for computing normalized dispersion.

### Stardust outline

Stardust works by constructing a network of single-cells and genes such that expression-wise similar cells are connected with each other, and genes are connected to cells where those are enriched the most. This gives rise to a cell-gene multi-entity network, which is subjected to a graph layout algorithm, which provides 2D coordinates of both cells and the genes in a manner that cells that share their lineage and their marker genes maintain proximity. At this stage, cells and genes are clustered based on the coordinates associated with their low-dimensional embeddings. DE genes are obtained by contrasting the cell-clusters. The DE genes replace the highly variable genes used for the construction of the initial network. This step is followed by layouting for further refinement of the 2D embedding. Typically, three iterations of this refinement process offer an optimal representation of the cells. The subsequent sections outline the details associated with the main components of Stardust.

### Structure preserving subsampling

Random subsampling might result in the loss of rare subpopulations. To circumvent this, Stardust employs Structure Preserving Sampling (SPS) [5] on the preprocessed datasets. SPS involves rapid construction of the nearest neighbor network of single-cells, followed by graph clustering. To ascribe a higher retention rate to rare cells, cell subsampling is done based on the following decay function, which determines the proportion of cells to be sampled
<figure><img src="image_6.png" /><figcaption>Figure 5. Precise delineation of cell-types in *Drosophila* early embryos. (a) UMAP visualization of cell-type clusters identified using Scanpy reveals a clear separation of transcriptionally distinct cell populations in early *Drosophila* embryos. (b) Cell-type clusters and their associated marker genes are visualized spatially using Stardust, providing initial insights into the anatomical localization of each cluster. (c) Detailed spatial mapping of Stardust clusters 4 and 8 on the *Drosophila* virtual embryo. For each cluster, the left subpanels show continuous spatial enrichment scores derived from Stouffer's method, while the right subpanels display the corresponding binarized maps that highlight discrete regions of predicted gene expression. This dual representation enables both nuanced and thresholded interpretations of spatial localization. (d) Equivalent analysis for Louvain cluster 6, showing both the gradient-based and binarized spatial distribution of its marker genes. This comparison highlights similarities and potential differences in the spatial predictions obtained using alternative clustering strategies. (e) A schematic lateral view of a stage 6 *Drosophila* larva is provided as a reference, with key anatomical regions color-coded to facilitate interpretation of the spatial localization patterns observed in panels (c) and (d).</figcaption></figure>
per cluster.

$$p_i = p_l - e^{-\frac{s_i}{k}} (p_l - p_u),$$

where $p_i$ represents the proportion of samples for $i^{th}$ cluster, $p_l$ and $p_u$ represents the lower bound and upper bound proportion respectively, $s_i$ is the size of the cluster and $k$ is the scaling factor.

## Cell-gene nearest neighbor network

The sampled cells after SPS and the qualified genes based on the gene selection technique (discussed earlier) conjointly construct the cell-gene nearest neighbor network (CGNNN). A CGNNN consists of two legal types of edges—cell-cell and cell-gene. For cell-cell connections, PCA is performed on the preprocessed, normalized and log transformed expression matrix. The default number of top components is set to 500. The concept of approximate nearest neighbor is used for establishing cell-cell connections by employing Locality Sensitive Hashing (LSH). Each cell is connected to its k nearest cells based on Annoy (Approximate Nearest Neighbors Oh Yeah) a C++ library with Python bindings, on the basis of top principal components. The construction of the Nearest Neighbor Network (NNN) takes O (nlog n) where n denotes the number of single-cell expression profiles. The usage of LSH results in reduction of the computation time of NNN. Similarly, each gene is connected to top n cells in terms of normalized expression estimates. The default values of k and n are set to 20 and 10 respectively. The count of qualified genes per pass for construction of CGNNN is described in detail in the section titled “OpenOrd based iterative graph layouting”. As the number of qualified genes is lesser in the fourth pass as compared to other passes, so the number of cell-gene connections is slightly different. In the fourth pass, each cluster-specific gene identified in the third pass at rank i in the cluster is connected to p cells of the same cluster s.t. $p = 5 - \lfloor i/10 \rfloor$. The intent here is to attach cluster-specific genes of higher quality to more cells within the cluster.

## Post hoc cluster assignment

In every pass, density-based clustering (DBSCAN) is performed on coordinates corresponding to 2D embeddings of the subsampled transcriptomes. Cells leftover during the subsampling phase are assigned posthoc, to the predefined clusters. For each of the leftover transcriptomes, k nearest neighbours are queried from the subsamples selected for the initial clustering. A leftover transcriptome is assigned to the cluster which is found maximally represented among the neighbors. The default value of the parameter k is set to 20, the same as that of the cell-cell connections parameter described in the CGNNN section. The 2D coordinates of the leftover cells are determined by averaging out the coordinates of the nearest neighbor transcriptomes residing inside the assigned cluster. Notably, the posthoc cluster assignment is performed at the end of each pass, which helps in determining the coordinates and clusters of origin for the leftover cells. The only exception is the fourth pass where cluster assignment is not necessary.

## OpenOrd based iterative graph layouting

Stardust pipeline involves iterative embedding and differential gene finding with a goal of converging into high-quality cell-type clusters. In the first pass, 500 genes with the highest absolute loadings across top 500 PCs are selected to construct the CGNNN. In the second pass and third pass, using Scanpy's `scanpy.tl-rank-genes-groups()` with t-test_overestim_var as the underlying method, 500 differentially expressed genes with adjusted $P < .5$ and $log2foldchange > 1.2$ are selected for CGNNN. In the

fourth pass, the top 20 cluster-specific differentially upregulated genes are considered for reconstruction of the CGNNNs. The multi-entity, heterogeneous network created in every pass is subjected to OpenOrd network layouting. OpenOrd algorithm uses simulated annealing for optimization of the below expression.

$$\min_{x_1, x_2, \dots, x_n} \sum_i (\sum_j (w_{ij} d(x_i, x_j))^2 + D_{x_i}),$$

where $x_i$ represents the position of the node, $D_{x_i}$ denotes the density of the edges near $x_i$. $w_{ij}$ denotes the edge weight connecting node i and j. Finally, $d(x_i, x_j)$ denotes the distance between the two nodes. Notably, OpenOrd uses an edge-cutting heuristic that allows the user to control the amount of white space. Stardust considers unit weights for all the connections (edges). The low-dimensional embedding of single-cell transcriptomes obtained in the third pass are used as input dimensions for clustering. Final coordinates of the cells and genes are determined through one last round of co-embedding in the fourth pass (see the subsection titled “Final coordinates for differential genes”).

## Final coordinates for differential genes

Cluster-specific top differentially upregulated genes obtained through DE analysis in the third pass are subjected to CGNNN formation for one final time. The detail for the NNN formation in the fourth pass is described in the section titled “Cell-gene Nearest Neighbor Network (CGNNN)”. Execution of the OpenOrd graph layout algorithm on the multi-entity network yields a new set of coordinates for the cells and the genes. The cell coordinates may vary from the third pass coordinates which we claim to be the final coordinates of the transcriptomes. fourth pass helps in mapping newly obtained cluster-specific upregulated genes back into the 2D space generated in the third pass. This is achieved by training cluster-specific regression models wherein each dimension obtained from the third pass is considered as the dependent variable, whereas the two dimensions obtained from the fourth pass are considered as the independent variables. For genes specific to each cluster obtained in the third pass, the corresponding coordinate values are generated using these models on the basis of the final embedding in the fourth pass. Non-linear K Nearest Neighbor (KNN) regression technique is used for this purpose. The default value of K is set to 5. To simplify, both 2D coordinates and clusters are obtained from the third pass. fourth i.e. the final pass is used only for determining the putative location of the cluster-specific differentially upregulated genes in the 2D space generated in the third pass.

## Projection of DE genes onto UMAP embedding

As an alternative to the OpenOrd layout, Stardust also allows cell-gene co-embedding on the UMAP projections. This is achieved simply by projecting the cluster-specific genes obtained from the third pass onto the UMAP laid 2D space. The mapping strategy is similar to the fourth to third pass mapping technique described in the previous section. In this case, the UMAP dimensions individually are considered as the decision variables for regression.

## Measures of clustering performance

We used both unannotated and annotated scRNA-seq datasets for various experiments. For assessing the signal-to-noise ratio associated with the representation of clusters on 2D maps, we made use of the Silhouette index.
## Analysis of spatial transcriptomics data of *Drosophila* embryo

As discussed earlier, we used independent single-cell expression data [41] and in situ expression estimates [28] of *Drosophila* larvae to assess the performance of Stardust and Louvain. The in-situ data was available as ~3000 positional bins expressing 84 marker genes. We performed separate analysis of in situ and the single-cell expression data using both Louvain and Stardust. To identify the correspondence among clusters obtained from the transcriptomics data and the in-situ hybridization data, we tracked the cluster-to-cluster correspondence by computing Pearson's correlation between cluster-wise average expression vectors of the common 84 genes, present in both datasets.

## Spatial zonation of cell-type clusters in *Drosophila* embryo

To track the spatial localization of the clusters generated using Stardust and Louvain, we made use of the gene expression cartography technique, implemented in the novoSpaRc [27] framework. NovoSpaRc probabilistically mapped the ~8000 genes in the scRNA-seq dataset across positional bins (coordinates of the bins were supplied as input) with the underlying assumption that relatively closer cells by position tend to share similar gene expression patterns and vice versa. These probabilities mapping scores can be treated as a surrogate of gene expression estimates across the positional bins. To pinpoint the putative spatial localization of a single-cell cluster, we computed Stouffer's Z score by combining the probabilistic mapping scores associated with the top 20 cluster-specific differentially upregulated genes. This allowed us to obtain cluster-specific continuous scores across positional bins of the virtual *Drosophila* embryo.

## Prediction of spatial coordinates using differentially expressed genes as features

The ~8 K X ~3000 matrix returned by novoSpaRc comprises probabilistic mapping scores of ~8 K genes across ~3000 positional bins. For Stardust, and Louvain, we selected a total of ~100 DE genes, while considering an equal number of marker genes per cluster. We constructed 50 bootstrapped samples of training and validation sets by sampling from the positional bins. DecisionTreeRegressor module of sklearn was used for the prediction tasks while treating the marker genes as independent and each of the coordinates as a dependent variable. The performance of the various regression tasks was tracked using RMSE.

## Conclusion

The declining cost of sequencing and wide availability of single-cell omics platforms have created an information singularity for studying cellular processes under normal and diseased conditions. High throughput capture and profiling of single-cells enable characterizing tens of cell types and states as part of a single experiment. Current clustering and differentially expressed gene detection are treated as independent processes, thereby generating independent 2D scatters and heatmaps respectively. Cross-referencing between these two types of visualizations is often challenging. Moreover, cell-type clusters are often detected with diffused identities. Stardust addresses these by iteratively clustering cells and marker genes as part of multi-entity network topology. Stardust successfully groups cells and genes together in a visually coherent manner. Stardust's iterative clustering yields cell type clusters with high signal-to-noise ratios. With

the increasing throughput of single-cell experiments, we predict Stardust would emerge as a nonredundant alternative, especially due to its compatibility with common single-cell visualization techniques such as UMAP and t-SNE.

## Key Points

* Stardust is a Python-based force-directed graph layout method for simultaneous visualization of cells and marker genes from scRNA-seq studies in a shared low-dimensional space.

* Stardust achieves superior performance across multiple benchmark datasets spanning species, tissues, and experimental conditions, consistently outperforming state-of-the-art methods in cluster robustness.

* Stardust enhances interpretability by producing clusters that closely correspond to known anatomical regions, ensuring stronger alignment between computational predictions and biological ground truth.

## Author contributions

D.S. conceived the study and supervised the overall methodological development, with input from G.A. and T.C. G.A. supervised the design of experiments with additional input from D.S. N.B., S.C., and S.K. developed the software pipeline and performed the experiments, with assistance from K.G., D.S., and A.M. N.B., A.M., and B.M. conducted the post processing of scientific illustrations. NB and SC carried out specific data analyses and data interpretation tasks. N.B., S.K., A.H., B.M., and S.G. contributed to benchmarking results. The manuscript was drafted by D.S., S.C., N.B., C.N., S.K., A.H., B.M., and G.A. All authors reviewed and approved the final manuscript.

## Supplementary data

Supplementary data is available at *Briefings in Bioinformatics* online.

## Conflict of interest

None declared.

## Funding

The Sengupta lab is funded by the DBT (IC-12044(12)/4/2022-ICD-DBT) and the Indian Council of Medical Research (ICMR)-India (EMDR/IG/16/2024-01-01321), and Science and Engineering Research Board (SERB)-India (CRG/2022/007706). The Ahuja lab is supported by the Ramalingaswami Re-entry Fellowship by the Department of Biotechnology (DBT), Ministry of Science & Technology, Govt. of India.

## Data availability

Stardust is freely available at https://github.com/namratabhattacharya/Stardust as a Python package.

## References

1. Matuła K, Rivello F, Huck WTS. Single-cell analysis using droplet microfluidics. Advanced. *Biosystems*. 2020;4:1900188. https://doi.org/10.1002/adbi.201900188.
2. Burgess DJ. Spatial transcriptomics coming of age. *Nat Rev Genet* 2019;20:317. https://doi.org/10.1038/s41576-019-0129-z.

3. Marx V. Method of the year: spatially resolved transcriptomics. *Nat Methods* 2021;18:9-14. https://doi.org/10.1038/s41592-020-01033-y.

4. Xia C, Fan J, Emanuel G, et al. Spatial transcriptome profiling by MERFISH reveals subcellular RNA compartmentalization and cell cycle-dependent gene expression. *Proc Natl Acad Sci U S A* 2019;116:19490-9. https://doi.org/10.1073/pnas.1912459116.

5. Sinha D, Kumar A, Kumar H, et al. dropClust: efficient clustering of ultra-large scRNA-seq data. *Nucleic Acids Res* 2018;46:e36. https://doi.org/10.1093/nar/gky007.

6. McCarthy DJ, Rostom R, Huang Y, et al. Cardelino: computational integration of somatic clonal substructure and single-cell transcriptomes. *Nat Methods* 2020;17:414-21. https://doi.org/10.1038/s41592-020-0766-3.

7. Schwartz GW, Zhou Y, Petrovic J, et al. TooManyCells identifies and visualizes relationships of single-cell clades. *Nat Methods* 2020;17:405-13. https://doi.org/10.1038/s41592-020-0748-5.

8. Becht E, McInnes L, Healy J, et al. Dimensionality reduction for visualizing single-cell data using UMAP. *Nat Biotechnol* 2018;37: 38-44. https://doi.org/10.1038/nbt.4314.

9. Zhang R, Atwal GS, Lim WK. Noise regularization removes correlation artifacts in single-cell RNA-seq data preprocessing. *Patterns Prejudice* 2021;2:100211. https://doi.org/10.1016/j. patter.2021.100211.

10. Bhattacharya N, Nelson CC, Ahuja G, et al. Big data analytics in single-cell transcriptomics: five grand opportunities. *Wiley Interdiscip Rev Data Min Knowl Discov* 2021;11:11. https://doi.org/10.1002/widm.1414.

11. Han X, Zhou Z, Fei L, et al. Construction of a human cell landscape at single-cell level. *Nature*. 2020;581:303-9. https://doi.org/10.1038/s41586-020-2157-4.

12. Martin S, Michael Brown W, Klavans R, et al. OpenOrd: an open-source toolbox for large graph layout. *Visualization and Data Analysis* 2011;7868:45-55. https://doi.org/10.1117/12.871402.

13. Flexa C, Gomes W, Moreira I, et al. Polygonal coordinate system: visualizing high-dimensional data using geometric DR, and a deterministic version of t-SNE. *Expert Systems with Applications* 2021;175:114741. https://doi.org/10.1016/j.eswa.2021.114741.

14. Weinreb C, Wolock S, Klein AM. SPRING: a kinetic interface for visualizing high dimensional single-cell expression data. *Bioinformatics*. 2018;34:1246-8. https://doi.org/10.1093/bioinformatics/btx792.

15. Traag VA, Waltman L, van Eck NJ. From Louvain to Leiden: guaranteeing well-connected communities. *Sci Rep* 2019;9:5233. https://doi.org/10.1038/s41598-019-41695-z.

16. Wang B, Zhu J, Pierson E, et al. Visualization and analysis of single-cell RNA-seq data by kernel-based similarity learning. *Nat Methods* 2017;14:414-6. https://doi.org/10.1038/nmeth.4207.

17. Kiselev VY, Kirschner K, Schaub MT, et al. SC3: consensus clustering of single-cell RNA-seq data. *Nat Methods* 2017;14:483-6. https://doi.org/10.1038/nmeth.4236.

18. Wolf FA, Angerer P, Theis FJ. SCANPY: Large-scale single-cell gene expression data analysis. *Genome Biol* 2018;19:15. https://doi.org/10.1186/s13059-017-1382-0.

19. Hou R, Denisenko E, Forrest ARR. scMatch: a single-cell gene expression profile annotation tool using reference datasets. *Bioinformatics*. 2019;35:4688-95. https://doi.org/10.1093/bioinformatics/btz292.

20. Butler A, Hoffman P, Smibert P, et al. Integrating single-cell transcriptomic data across different conditions, technologies, and

species. *Nat Biotechnol* 2018;36:411-20. https://doi.org/10.1038/nbt.4096.

21. Li X, Wang K, Lyu Y, et al. Deep learning enables accurate clustering with batch effect removal in single-cell RNA-seq analysis. *Nat Commun* 2020;11:2338. https://doi.org/10.1038/s41467-020-15851-3.

22. Hu J, Li X, Hu G, et al. Iterative transfer learning with neural network for clustering and cell type classification in single-cell RNA-seq analysis. *Nat Mach Intell* 2020;2:607-18. https://doi.org/10.1038/s42256-020-00233-7.

23. Sharma G, Colantuoni C, Goff LA, et al. projectR: an R/Bio-conductor package for transfer learning via PCA, NMF, correlation and clustering. *Bioinformatics*. 2020;36:3592-3. https://doi.org/10.1093/bioinformatics/btaa183.

24. Henry GH, Malewska A, Joseph DB, et al. A cellular anatomy of the normal adult human prostate and prostatic urethra. *Cell Rep* 2018;25:3530-3542.e5. https://doi.org/10.1016/j.celrep.2018.11.086.

25. Bhattacharya N, Rockstroh A, Deshpande SS, et al. Artificial intelligence approaches for tumor phenotype stratification from single-cell transcriptomic data. *Elife*. 2025;13:13. https://doi.org/10.7554/eLife.98469.

26. Sun J, Cristobal Vera J, Drnevich J, et al. Single cell heterogeneity in influenza a virus gene expression shapes the innate antiviral response to infection. *PLoS Pathog* 2020;16:e1008671. https://doi.org/10.1371/journal.ppat.1008671.

27. Nitzan M, Karaiskos N, Friedman N, et al. Gene expression cartography. *Nature*. 2019;576:132-7. https://doi.org/10.1038/s41586-019-1773-3.

28. Fowlkes CC, Hendriks CLL, Keränen SVE, et al. A quantitative spatiotemporal atlas of gene expression in the drosophila blastoderm. *Cell*. 2008;133:364-74. https://doi.org/10.1016/j.cell.2008.01.053.

29. Thurmond J, Goodman JL, Strelets VB, et al. FlyBase 2.0: the next generation. *Nucleic Acids Res* 2019;47:D759-65. https://doi.org/10.1093/nar/gky1003.

30. Frise E, Hammonds AS, Celniker SE. Systematic image-driven analysis of the spatial drosophila embryonic expression landscape. *Mol Syst Biol* 2010;6:345. https://doi.org/10.1038/msb.2009.102.

31. Weiszmann R, Hammonds AS, Celniker SE. Determination of gene expression patterns using high-throughput RNA in situ hybridization to whole-mount drosophila embryos. *Nat Protoc* 2009;4:605-18. https://doi.org/10.1038/nprot.2009.55.

32. Vivancos RBV, Bernardoni R, Vivancos V, et al. Glide/gcmls expressed and required in the scavenger cell lineage. *Dev Biol* 1997;191:118-30. https://doi.org/10.1006/dbio.1997.8702.

33. Cattenoz PB, Popkova A, Southall TD, et al. Functional conservation of the glide/Gcm regulatory network controlling glia, Hemocyte, and tendon cell differentiation in drosophila. *Genetics*. 2016;202:191-219. https://doi.org/10.1534/genetics.115.182154.

34. Campbell JN, Macosko EZ, Fenselau H, et al. A molecular census of arcuate hypothalamus and median eminence cell types. *Nat Neurosci* 2017;20:484-96. https://doi.org/10.1038/nn.4495.

35. Barh D, Azevedo V (eds). *Single-Cell Omics: Volume 1: Technological Advances and Applications*. Elsevier: Academic Press, 2019.

36. Pollen AA, Nowakowski TJ, Shuga J, et al. Low-coverage single-cell mRNA sequencing reveals cellular heterogeneity and activated signaling pathways in developing cerebral
cortex. Nat Biotechnol 2014;32:1053-8. https://doi.org/10.1038/nbt.2967.

37. Kolodziejczyk AA, Kim JK, Tsang JCH, et al. Single cell RNA-sequencing of pluripotent states unlocks modular transcriptional variation. Cell Stem Cell 2015;17:471-85. https://doi.org/10.1016/j.stem.2015.09.011.

38. MacParland SA, Liu JC, Ma X-Z, et al. Single cell RNA sequencing of human liver reveals distinct intrahepatic macrophage populations. Nat Commun 2018;9:4383. https://doi.org/10.1038/s41467-018-06318-7.

39. Mira J, Alvarez JR eds. Artificial neural nets. Problem Solving Methods: 7th International Work-Conference on

Artificial and Natural Neural Networks, IWANN 2003, Maó, Menorca, Spain, June 3-6. Proceedings, Part II. Springer-Verlag New York Inc; 2003. https://doi.org/10.1007/3-540-44869-1.

40. Riaño D, Wilk S, ten Teije A eds. Artificial intelligence in medicine: 17th conference on artificial intelligence in medicine, AIME 2019, Poznan, Poland, June 26-29, 2019, Proceedings. Springer International Publishing; 2019. https://doi.org/10.1007/978-3-030-21642-9.

41. Karaiskos N, Wahle P, Alles J, et al. The Drosophilaembryo at single-cell transcriptome resolution. Science. 2017;358:194-9. https://doi.org/10.1126/science.aan3235.