B.

Tech Project
8th Semester - End-Term Evaluation

TriRNSC: triclustering of gene expression

microarray data using restricted neighbourhood
search
Supervisor: Prof. Swati Vipsita

A Shantanu (B421001)
Panel - 2 | Group - 2
 INTRODUCTION
• Microarray data analysis has become a cornerstone in understanding gene expression patterns
and uncovering their biological significance. Traditional clustering methods have played a critical
role in grouping genes based on expression similarity, offering insights into gene functionality
and regulatory interactions. However, these techniques typically consider all conditions
simultaneously and do not account for temporal variations in gene activity.

• As biological research has shifted toward time-series experiments—such as those studying the
cell cycle or disease progression—the need for more advanced analytical tools has become
evident. Biclustering emerged as a partial solution by identifying gene-condition submatrices,
but it still falls short in scenarios where gene expression changes over time.

• This limitation has led to the rise of triclustering, which incorporates time as a third dimension,
enabling the discovery of gene groups that behave similarly under specific conditions and at
specific time points. Capturing this temporal dynamic is essential for accurately modeling
complex biological processes and understanding how gene regulation evolves in real time.

1
 PROBLEM STATEMENT
• Conventional clustering and biclustering methods fall short in analyzing gene expression data when
temporal dynamics are involved. These methods are unable to capture evolving co-expression
patterns that change across time and conditions, making them ineffective for studying complex
biological processes such as cell cycle progression, immune responses, or disease development.

• With the increasing availability of time-series microarray datasets, a three-dimensional (3D)

approach is required—one that simultaneously accounts for genes, experimental conditions, and
time points.
To address this, we implement a triclustering framework using the TriRNSC algorithm.

• This solution enables the discovery of meaningful gene modules involved in time-sensitive
pathways, offering direct applications in disease modeling, drug targeting, and understanding
regulatory mechanisms in systems biology.

2
 LITERATURE SURVEY
Author & Year of publication Title Methodology

Biswal, Bhawani Sankar (2020) TriRNSC: Triclustering of gene expression Proposed TriRNSC algorithm using
microarray data using restricted Restricted Neighborhood Search
neighborhood search. Clustering (RNSC) to discover meaningful
triclusters across genes, conditions, and
time.
Paul T. Spellman (1998) Comprehensive identification of cell Generated benchmark yeast cell cycle
cycle–regulated genes of the yeast dataset used for evaluating gene
Saccharomyces cerevisiae by microarray expression analysis algorithms.
hybridization.
Elizabeth I. Boyle (2004) GO:: TermFinder—Open source software Developed a tool for biological validation
for enriched Gene Ontology term of gene clusters using statistically
identification. enriched GO terms.

Sushmita Mitra (2006) Bioinformatics with soft computing. The Pearson Correlation Coefficient was
employed to detect co-expressed genes
by assessing the linear association
between gene expression profiles derived
from microarray data.
Biswal, Bhawani Sankar (2016) Biclustering of gene expression patterns Introduced overlapping-controlled
with an advanced overlapping control biclustering method for better pattern
strategy. detection under multiple conditions.

3
SOLUTION IMPLEMENTATION

Fig.1: Workflow
4
 DATASET INITIALIZATION
• The project uses a 3D microarray gene expression dataset from the cell cycle of
Saccharomyces cerevisiae (yeast).
• Expression levels are recorded across: Genes x Experimental conditions x Time
points. Here 301 number of genes are analysed under five conditions for 8 time
points.
• This structure creates a rich temporal gene expression profile ideal for triclustering.
• Source: NCBI Gene Expression Omnibus (GEO) [7].

5
Fig.2: Illustration of the yeast dataset structure.
 GENE CO-EXPRESSION NETWORK (GCN)
CONSTRUCTION (Link)
• Before GCN construction, random clustering was performed to initialize gene groups.
The optimal number of clusters was determined as 2, based on silhouette score analysis.

• A Gene Co-expression Network (GCN) is initialized as an empty graph where: Nodes represent
genes and Edges represent strong expression similarity.

• For every gene pair (gi , gj) Pearson correlation coefficient (ρ) is computed based on expression
profiles across all conditions and time points.

• A threshold (ρ ≥ 0.7) is applied:

• Only gene pairs exceeding this threshold are connected.
• This filters out weak correlations, preserving only robust gene-gene interactions.

• Inference:
• High ρ values indicate that the genes may be co-regulated or functionally linked.
• The GCN formed using this principle helps uncover dense modules of genes with shared
biological roles. 6
 CORRELATION COEFFICIENT
σ𝑛 σ 𝑡
ҧ
𝑖=1 𝑗=1(𝑥𝑖𝑗 − 𝑥)(𝑦 ത
𝑖𝑗 − 𝑦)
𝜌 𝑥, 𝑦 =
σ𝑛 σ 𝑡
𝑖=1 𝑗=1(𝑥𝑖𝑗 − ҧ
𝑥) 2 σ𝑛 σ𝑡 (𝑦 − 𝑦)
𝑖=1 𝑗=1 𝑖𝑗 ത 2
where,
𝜌 = Pearson correlation coefficient between genes x and y, measuring their
expression similarity
𝑛 = Number of conditions in the dataset
𝑡 = Number of time points for each condition
𝑥𝑖𝑗 and 𝑦𝑖𝑗 = Expression level of genes x and y for ith condition in jth time point
𝑥̄ҧ and 𝑦ത = Average expression levels of genes x and y across all conditions and time
points

Eq.1: Correlation coefficient

• The Pearson correlation coefficient (ρ) is a statistical measure used to evaluate the linear similarity between
the expression profiles of two genes.

• Range:
• ρ ≈ +1: Strong positive correlation (genes vary similarly)
• ρ ≈ 0: No correlation
• ρ ≈ –1: Strong negative correlation (genes vary oppositely) 7
 SILHOUETTE SCORE
• The silhouette score is used to determine the optimal number of clusters before applying RNSC. This score
measures how well each gene fits within its assigned cluster compared to others, based on intra- and inter-
cluster distances.

𝑏 𝑖 − 𝑎(𝑖)
s 𝑖 =
max(𝑎 𝑖 , 𝑏(𝑖))

where,
a(i): average distance of point i to all other points in the same cluster
b(i): average distance of point i to all points in the nearest different cluster
s(i) ranges from -1 to 1
1 = well-clustered
0 = on the boundary
< 0 = likely misclassified

Eq.2: Silhouette score equation

• The silhouette score guided the random cluster initialization phase before RNSC.
• The optimal cluster count was found to be 2, indicating that the expression patterns in our dataset naturally separate
into two distinct gene groups.
• This selection helped improve RNSC efficiency and convergence by providing a meaningful starting structure.
8
SILHOUETTE SCORE

Fig.3: Silhouette score output

9
 TRICLUSTER SELECTION USING RNSC (Link)

• After constructing the Gene Co-expression Network (GCN), the Restricted Neighborhood Search
Clustering (RNSC) algorithm is applied to extract coherent triclusters.

• RNSC is a graph-based local search technique that:

• Partitions the graph into gene clusters (subsets of nodes).
• Maximizes intra-cluster connectivity.
• Minimizes inter-cluster connections.

• The algorithm functions in two optimization phases:

• Naive Phase: Applies a basic cost function to rapidly reduce cluster noise.
• Scaled Phase: Refines clusters using a cost function scaled by neighborhood size for greater
accuracy.

• Key Parameters used in the RNSC configuration are TabuLength Ratio (0.02),
NaiveStoppingTolerance (15), ScaledStoppingTolerance (15), DiversificationFrequency (10), and
MaxExperiments (30).

• A tabu list is maintained to avoid revisiting recently explored states and encourage better global
optimization. 10
 COST FUNCTION
𝑛 𝑛
1 (𝑛 − 1) 𝑐𝑝 𝑉 + 𝑙𝑝 𝑉
∁𝑛 𝐺, 𝑃 = ෍ 𝑐𝑝 𝑉 + 𝑙𝑝 𝑉 ∁𝑝 𝐺, 𝑃 = ෍
2 3 𝑅 𝑣 ∪ 𝑝𝑣
𝑣𝜖𝑉 𝑣𝜖𝑉

Eq.3: Naive cost function Eq.4: Scaled cost function

where,
∁𝑝 𝐺, 𝑃 = The scaled cost function for graph G with partitioning P
𝑉 = Set of all vertices in the graph
𝑛 = Number of vertices (genes) in the graph
𝑐𝑝 𝑉 = Number of cross-edges incident with vertex v
𝑙𝑝 𝑉 = Number of vertices in v's cluster that are not connected to v
𝑅 𝑣 = Set of neighbor nodes of vertex v
𝑝𝑣 = The cluster to which vertex v belongs

11
 COST FUNCTION
• The cost value represents the total penalty due to: Unwanted inter-cluster edges and Missing
connections inside clusters.
• Lower cost = higher clustering quality (more cohesive, well-separated clusters).

• Both ∁𝑛 and ∁𝑝 return non-negative real numbers.

• There is no strict upper bound, but:
• Higher values → weak or noisy clustering.
• Lower values → strong internal structure, fewer interferences.

• Naive Cost is minimized in the early phase to rapidly reduce bad clustering patterns.
• Scaled Cost is optimized in the second phase using local neighborhood scaling for precision.
• After multiple experiments, the clustering with the lowest final scaled cost is selected.

• Inference:
• A drop in cost during iterations indicates better structural organization.
• Final triclusters with the lowest cost are more likely to be biologically meaningful.

12
 RESULTS OBTAINED
The visualizations below illustrate the structural transformation of the Gene Co-expression Network (GCN) across two
key stages of the TriRNSC framework. In the pre-RNSC GCN, gene pairs are connected based on high Pearson correlation
(ρ ≥ 0.7), forming a raw network of co-expressed genes without any cluster differentiation. After applying the RNSC
algorithm, the same network is reorganized into distinct color-coded triclusters, optimized using naive and scaled cost
functions. Some genes are reassigned to different clusters, not merely based on correlation but through topological
refinement, ensuring greater intra-cluster connectivity and biological coherence.

13
Fig.4: Gene Co-expression Network before applying RNSC. Fig.5: Gene Co-expression Network after applying RNSC.
 RESULTS OBTAINED
The line graphs illustrate the temporal expression profiles of genes within the two most prominent triclusters identified
through the RNSC algorithm — Cluster 0 and Cluster 1. Each colored line represents the expression of an individual gene
across time points under a specific condition, while the bold black line shows the average expression trend within the
cluster. The consistent shape of these trends highlights temporal co-expression and affirms the internal coherence of
the clusters formed through RNSC-based optimization.

Fig.6: Gene expression patterns for Cluster 0 and Cluster 1 across 8 time points.
14
Fig.7: Illustration of a tricluster on a 3D space: x-axis represents the conditions, y-axis
represents the time of observation and z-axis represents gene expression values

15
 VALIDATION OF RESULTS
This table highlights the most significantly enriched biological processes discovered in Cluster 0 using Gene Ontology
(GO) enrichment analysis. These results validate the functional coherence of the triclustered genes identified through
the TriRNSC algorithm. Key processes like transcription regulation and cell proliferation were found to be strongly
overrepresented, as indicated by extremely low adjusted p-values.

16
Fig.8: GO term enrichment output for Cluster 0
Fig.8: GO term enrichment bar-plot output for Cluster 0

16
 VALIDATION OF RESULTS
𝐾 𝑁−𝐾
min(𝐾,𝑛) 𝑖 𝑛−𝑖
p = σ𝑖=𝑘 𝑁
𝑛

where,
N = total number of genes in the background/reference genome
K = number of genes associated with the GO term
n = number of genes in our cluster
k = number of genes from our cluster that overlap with the GO term
p = probability of observing ≥ k overlapping genes by chance

Eq.5: p-value equation

17
 VALIDATION OF RESULTS
• In our GO term enrichment analysis (performed using the gseapy package), the p-value quantifies the statistical
significance of observing a certain overlap between the genes in our cluster and those annotated to a particular
biological process.

• Measures the likelihood that the observed overlap is due to random chance.
• A smaller p-value indicates higher statistical significance of enrichment.
• We consider p < 0.05 as significant; adjusted p-values are used to correct for multiple testing.

• Range: 0 ≤ p ≤10
• Closer to 0: Stronger confidence that the enrichment is not random.
• Closer to 1: Indicates weak or no significant association.

• Inference:
• p-values obtained for Cluster 0 in some GO terms (e.g., 1.7×10−26) were extremely low.
• This confirms that the genes grouped together by the RNSC algorithm are functionally related, not just
structurally for those GO terms.
• Strong enrichment in transcription-related processes reinforces the biological validity of the discovered
triclusters.

18
 CONCLUSION
The results obtained from the TriRNSC pipeline confirm its ability to identify biologically relevant triclusters
from complex gene expression datasets. The temporal expression profiles of clustered genes exhibited
consistent co-expression patterns, indicating the internal coherence of the triclusters. Structural analysis of
the Gene Co-expression Network (GCN) before and after applying RNSC revealed a significant refinement,
with genes being reorganized into compact, minimally overlapping groups based on cost function
optimization. GO enrichment analysis highlighted strong associations with critical biological functions like
transcription regulation and cell population growth.

Looking ahead, future improvements will focus on enhancing the scalability of the TriRNSC framework to
handle larger genomic datasets and integrating additional biological annotation sources for more robust
functional validation. Incorporating dynamic thresholding mechanisms in GCN construction and
experimenting with ensemble-based clustering approaches are also promising directions. These
enhancements aim to further strengthen the biological interpretability and applicability of TriRNSC in the
context of systems biology and large-scale gene expression analysis.

19
 REFERENCES
1. B. S. Biswal, S. Patra, A. Mohapatra, and S. Vipsita, “Trirnsc: triclustering ofgene expression microarray data using
restricted neighbourhood search,” IETSystems Biology, vol. 14, no. 6, pp. 323–333, 2020.
2. Mishra, A., Biswal, B.S., Mohapatra, A., Vipsita, S. "Biclustering of Gene Expression Patterns with an Advanced Overlapping
Control Strategy." IEEE International Conference on Power Electronics, Intelligent Control and Energy Systems (ICPEICES-
2016), pp. 1-5, 2016.
3. I. Boyle, S. Weng, J. Gollub, H. Jin, D. Botstein, J. M. Cherry, and G. Sher-lock, “Go:: Termfinder—open source software for
accessing gene ontology in-formation and finding significantly enriched gene ontology terms associated witha list of
genes,” Bioinformatics, vol. 20, no. 18, pp. 3710–3715, 2004.
4. D. F. Soares, R. Henriques, and S. C. Madeira, “Comprehensive assessment oftriclustering algorithms for three-way
temporal data analysis,” Pattern Recogni-tion, vol. 150, p. 110303, 2024.
5. P. T. Spellman, G. Sherlock, M. Q. Zhang, V. R. Iyer, K. Anders, M. B. Eisen,P. O. Brown, D. Botstein, and B. Futcher,
“Comprehensive identification of cellcycle–regulated genes of the yeast saccharomyces cerevisiae by microarray hy-
bridization,” Molecular biology of the cell, vol. 9, no. 12, pp. 3273–3297, 1998.
6. S. Mitra and Y. Hayashi, “Bioinformatics with soft computing,” IEEE Trans-actions on Systems, Man, and Cybernetics, Part
C (Applications and Reviews),vol. 36, no. 5, pp. 616–635, 2006.
7. Ncbi geo accession viewer - gse3406.” [Link] Accessed: 2025-
05-06.
20
Thank You