A Bi-ordering Approach to Linking Gene
Expressions with Clinical Annotations in Cancer
Fan Shi1, Geoff MacIntyre1, Christopher Leckie1,Izhak Haviv2, Alex Boussioutas3, Adam Kowalczyk1
1 National ICT Australia, VRL & The University of Melbourne
2 Baker IDI Australia
3 Peter MacCallum Cancer Centre, Australia

Background: Gene expressions
Gene expression microarrays
The associations between genes and samples discovered in gene
expression microarrays can be used to help the diagnosis of cancers
50.4

100.2

15020-0.2

2530

-0.4
10203040502

Background: Motivation3Introduction to bi-clustering

Bi-clustering
An unsupervised method that clusters genes and samples simultaneously
Bicluster ―― a subset of genes co-expressed across a subset ofsamples

Two overlapping biclusters

2204006080100-220406080

1004

Bi-ordering Analysis: Overview
Our approach is based on a protocol for exploring biclusters that exhibit
statistical, biological and clinical significanceGiven an input gene expression data matrix
1. Generate biclusters based on Bi-Ordering Approach (BOA)
2. Merge similar biclusters into “super-biclusters” to identify robust
modules
3. Evaluation: three statistics as measurements— Over-representation of histological categories in biclusters— Gene Ontology (GO) annotations— Concordance of sample order with various phenotype gradients
4. Biological Interpretation

5

Bi-ordering Analysis: Algorithm

nG
nS
Input Gene expression matrix[ xgs ]withgenes andsamples
Standardize data and select pre-defined thresholds
θG
θandS
Randomly select a submatrix(G, S )as initial bicluster
Repeat
1. Update gene scores f [ g ] ← xgs s∈S , for g = 1,..., nG{

2. Select a subset of genes G ← g ; f [ g ] − f [ g ] g =1,..., n > θGGS

3. Update sample scoresh[ s ] ← xgs g∈G , for s = 1,..., nS{

4. Select a subset of samplesS ← s ; h[ s ] − h[ s ] s =1,..., n > θ S
SG}}o

Until G and S are stable
0(G, S ) is a bicluster with orderingf ( g )h( s ) and0
*Note: xgs s∈S denotes the mean of{xgs ; s ∈ S}
06

Bi-ordering Analysis: Super-biclustering•Multiple biclusters
oo•Distinct initializations in BOA result in different biclusters in general
Some of the biclusters differ slightly due to local optima

Super-biclustering
A hierarchical clustering is applied on ‘biclusters’ to obtain a group ofsuper-biclusters (SBC)ooo

Objects: biclusters
Distance metric: Jaccard coefficient on genes
Prototype selection: a single bicluster is selected as the prototype of SBC

Finally, we obtain a small number of distinct biclusters as output
7Bi-ordering Analysis
Heat map of a typical bicluster in gastric cancerchinaCG1020local

IM

diffuse30

4050

intestinal
60

7080

mixed
90

normal100 110 120

country
patho
1000
2000
3000
4000
5000
6000
7000

8

Bi-ordering Analysis
Heat map of a typical bicluster in gastric cancer
china
CG
10

local

IM

diffuse

30

40

2050

intestinal
60

7080

mixed
90

normal100 110 120

country
patho
100
200
300
400
500
9Experiments: Gastric cancer
Gastric Cancer dataset• 7383 genes, 124 samples• 6 pathological categories, and other clinical annotations
Phenotype

SubtypePremalignant

NormalMalignant

Malignant score*1

Chronic Gastritis (CG)2

Intestinal Metaplasia(IM)Diffused

34

Intestinal

4

Mixed

4

* Malignant score reflects the biological progression of gastric cancer
It is defined by oncologist
10Experiments: Evaluation metrics
Three evaluation metrics• Saturation metric on samples—— Homogeneity of samples in terms of clinical annotations• Trend statistics—— Associations between the sample orders and clinicalannotations• Gene Ontology (GO)—— The abundance of genes for particular pathways

11

Experiments: Results
Heat map of SBC7china
CG
1020

localIM

diffuse30

4050

intestinal
60

7080

mixed
90

normal100 110 120

countrypatho
100200300
400500
12Experiments: Results
The Significance Table of Super-biclusters

SBC Converge
SBC111
SBC2188
SBC32
SBC496
SBC515
SBC6328
SBC7359
SBC81p-value
Malignancy
MCS
Score
9.4E-04
1.8E-13
1.0E-08
1.5E-06
5.5E-08
1.8E-01
1.1E-18
7.7E-213.0E-07
4.9E-08
4.0E-14 -5.4E-22
3.0E-10 -5.2E-08

Most significant annotationGO
5.1E-09
7.1E-07
3.2E-32
2.0E-53
1.8E-14
1.8E-20
3.2E-22
2.2E-02GO
epidermis developmentlipid metabolic process
immune system process
immune system processcell cycle process
multicellular organismal process
gen. of precursor metab. & energy
lipid metabolic process

13Experiments: Saturation metricComparison with existing algorithms in terms of saturation metric

Number of Biclusters

10102

Multiple Classes Saturation Metric

1BOA
ISA
Gibbs
SAMBA
C&C

# super-biclusters

010 -201010-15# biclusters

-10-5

1010
MCS P-value

10

ISA: J. Ihmels et al.,Bioinformatics, 2004
Gibbs: Q. Sheng, et al.,Bioinformatics, 2003
SAMBA: A. Taney et al.,Bioinformatics, 2002
C&C: Y. Cheng, G. M.
0 Church, ISMB, 2000

14

Experiments: Biological interpretation
Compare with “Distinctive patterns of gene expression of premalignant gastricmucosa and gastric cancer”, Alex Boussioutas et al., 2003, Cancer Research.
Region in [Bou03]
SBC_1 SBC_2 SBC_3 SBC_4 SBC_5 SBC_6 SBC_7 SBC_8
Symbol Annotation No.Genes 41217
194158227
409515146
B
Mitochondrial 665
000001416
9D1-D3 Proliferation
201000076000E
Intestinal
294
1810000144F
Intestinal15701120071027GSquamous
37250000000HInflamation
330
70117
135
97030K
Extracellular877
3067074392
10
B: Encoding mitochondrial proteins (CG)D1-3: Cell proliferation (Intestinal GC)
E&F: Intestinal genes (IM)
H: Inflammation
K: Extra cellular matrix (Diffuse GC)
15

Experiments: Biological interpretation

Signal transduction pathways predicted to operate in SBC_6 signature-expressing cells(viaanalysis in Ingenuity Pathway Analysis®). Notice the genes PDGFRB, EGFR, DDR2, AXL
and LTK
16
are all tyrosine kinase receptors. Also noteworthy is ITGB1. The integrin and tyrosine
kinaseConclusion• Developed Bi-Ordering Analysis for gene expression data
• An effective method to find significant patterns and orderings• Scalability: very efficient on large scale gene expression data
• Evaluation of statistical significance• SCS and MCS for validating the homogeneity of samples• Gene Ontology for validating the significance of gene modules• Trend statistics for validating the concordance between sample
ordering and clinical annotations• Biological findings• The results of gastric cancer are in concordance with previousstudies• Some novel findings deserve further investigation

17

Future Work• Super-biclustering
How to choose an appropriate distance metric in super-biclustering todetect a robust set of biclusters is an important issue in computational
point of view
• Data dependency
Verify our approach in more synthetic and real datasets are critical tosolve the problem of various performance dependent on datasets18

19