A Weigh ed C am´e ’s V Index o he
Assessmen o S abili y in he Fuzzy Clus e ing
o Class C G P o ein-Coupled Recep o s
Al edo Vellido⋆, Ch is iana Halka, and `
Angela Nebo
Depa men o Compu e Science, Uni e si a Poli `ecnica de Ca alunya,
Ba celona 08034, Spain
{a ellido,ch is iana.halka,angela}@cs.upc.edu
h p://www.cs.upc.edu/~a ellido
Abs ac . A e decades o in ensi e use, K-Means is s ill a common
choice o c isp da a clus e ing in eal-wo ld applica ions, pa icula ly in
biomedicine and bioin o ma ics. I is well-known ha diffe en ini ializa-
ions o he algo i hm can lead o diffe en solu ions, p ecluding epli-
cabili y. I has also been epo ed ha e en solu ions wi h e y simila
e o s may widely diffe . A c i e ion o he choice o clus e ing solu ions
acco ding o a combina ion o e o and s abili y measu es has ecen ly
been sugges ed. I is based on he use o C am´e ’s V index, calcula ed
om con ingency ables, which is alid only o c isp clus e ing. He e, his
c i e ion is ex ended o uzzy and p obabilis ic clus e ing by fi s defin-
ing weigh ed con ingency ables and a co esponding weigh ed C am´e ’s
V index. The p oposed me hod is illus a ed using Fuzzy C-Means in a
p o eomics p oblem.
Keywo ds: Fuzzy clus e ing; K-Means; Clus e ing s abili y analysis;
C am´e ’s V index; G P o ein-Coupled Recep o s
1 In oduc ion
G p o ein-coupled ecep o s (GPCRs) a e cell memb ane p o eins o in e es due
o hei ole in ansducing ex acellula signals a e specific ligand binding.
They ha e in ac become a co e in e es o he pha maceu ical indus y, as
hey a e a ge s o mo e han a hi d o app o ed d ugs [1].
GPCR unc ionali y is mos ly in es iga ed om i s c ys al 3-D s uc u e.
Finding such s uc u e, hough, is a difficul unde aking1and only in he las
decade, a hand ul o GPCR s uc u es has been ound, mos o hem belonging
o he class A o he GPCR supe amily [2]. Only in 2013, one ecep o no
belonging o class A bu o he F izzled class and wo class B [3, 4] we e epo ed.
⋆This esea ch was pa ially unded by Spanish MINECO TIN2012-31377 esea ch
p ojec .
1Rhodopsin was he fi s GPCR c ys al s uc u e o be de e mined, back in 2000.
2 Assessmen o S abili y in he Fuzzy Clus e ing o Class C GPCRs
The fi s s uc u es o he 7- ans-memb ane (7TM) domains o wo class C
ecep o s we e published in 2014 [5, 6].
Ou esea ch ocuses on class C GPCRs, which ha e become a key a ge
o new he apies [7]. The al e na i e app oach when he e ia y 3D c ys al
s uc u e is no a ailable, is he in es iga ion o he ecep o unc ionali y om
i s p ima y s uc u e, ha is, di ec ly om he amino acid (AA) sequences.
The compa a i e explo a ion o he sequences o he se en diffe en desc ibed
sub ypes o his class may cons i u e a fi s s ep in he s udy o he molecula
p ocesses in ol ed in ecep o signalling.
Mos o he exis ing da a-based esea ch on p ima y ecep o sequences e-
so s o hei alignmen [8], which enables he use o mo e con en ional quan i-
a i e analysis echniques. Gi en ha he leng h o he class C GPCR sequences
a ies om a ew hund ed AAs o well o e a housand, alignmen isks he loss
o ele an sequence in o ma ion. Al e na i ely, as in his pape , we can eso o
me hods o he analysis o alignmen - ee sequences om hei ans o ma ion
acco ding o he AA p ope ies ( o a e iew see [9]).
P e ious explo a ion o he class C GPCR sequences h ough isualiza ion-
o ien ed clus e ing [10] and semi-supe ised analysis [11] has shown ha he
exis ing o mal cha ac e iza ion o his class in o se en sub ypes only pa ially
co esponds o he na u al da a clus e s uc u e acco ding o unaligned se-
quence ans o ma ions. In he cu en s udy, we in es iga e his issue wi hin a
mo e gene al clus e ing amewo k.
Clus e ing analysis o en wo ks by assigning indi idual da a ins ances o one
ou o se e al clus e s acco ding o hei simila i y o ep esen a i e examples
Such assignmen is o en o a dicho omous o c isp na u e: he ins ance ei he be-
longs o o does no belong o a gi en clus e . Fuzzy and p obabilis ic clus e ing
me hods, ins ead, assign each da a ins ance o each clus e wi h an es ima ed de-
g ee o p obabili y o membe ship. As a esul , he unce ain y o he assignmen
decision is explici ly aken in o accoun in he model.
O e he las decades [12], K-Means has become a s alwa me hod o da a
clus e ing, spawning many a ian s while emaining a common choice, e en i as
a benchma k, in many eal-wo ld applica ions. K-Means is based on c isp clus e
assignmen s, al hough a ian s such as Fuzzy C-Means (FCM)[13] ha e ex ended
he model o accoun o pa ial deg ees o membe ship. K-Means limi a ions a e
well s udied and include he lack o a closed c i e ion o he choice o he numbe
o clus e s Kand he ac ha , unde diffe en ini ializa ions, he algo i hm may
yield e y diffe en solu ions.
Recen expe imen al e idence [14] has shown ha K-Means solu ions ha
migh be expec ed o be simila acco ding o he final alue o he objec i e
unc ion may in ac be qui e dissimila , and ha his effec inc eases wi h he
alue o K. This sugges s he con enience o using he objec i e unc ion as a
c i e ion o model op imali y only in combina ion wi h some clus e s abili y
c i e ion i we aim o achie e clus e pa i ion ep oducibili y. One such com-
bined c i e ion is he Sepa a ion and Conco dance (SeCo) map, which joins he
Assessmen o S abili y in he Fuzzy Clus e ing o Class C GPCRs 3
s anda d sum-o -squa es (SSQ) e o and C am´e ’s V s abili y index, a a ia ion
o Pea son’s χ2, which can also be used o in o m he choice o K.
The calcula ion o C am´e ’s V index is based on he use o con ingency ables,
which a e only sui able o c isp clus e assignmen s. In his s udy, we ex end
he SeCo c i e ion o uzzy and p obabilis ic clus e ing by fi s defining weigh ed
con ingency ables and a co esponding weigh ed C am´e ’s V index. This should
be a mo e ai h ul assessmen o he clus e ing solu ion s abili y o uzzy and
p obabilis ic me hods.
The p oposed me hods a e employed o in es iga e a class C GPCR p ima y
sequence da a se ex ac ed om a publicly a ailable da abase. Two expe imen-
al se ings o he clus e ing expe imen s a e used. The fi s fixes he numbe o
clus e s o he numbe o o mal sub ypes in he class in o de o in es iga e he
le el o co espondence be ween bo h, while he second elaxes his cons ain
in o de o analyze he s abili y o he clus e ing solu ions using SeCo maps.
2 Me hods
2.1 Alignmen -F ee Sequence T ans o ma ion Me hods
As p e iously men ioned, in his pape we eso o me hods o he analysis o
alignmen - ee sequences om hei ans o ma ion acco ding o he AA p op-
e ies. Th ee ans o ma ions we e used in ou expe imen s:
–Amino Acid Composi ion (AAC): This simple ans o ma ion eflec s he AA
composi ion o he p ima y sequence. The equencies o he 20 sequence-
cons i u ing AAs a e calcula ed o each sequence and, as a esul , an N×20
da a ma ix is ob ained, whe e Nis he numbe o da a ins ances.
–Au o C oss Co a iance (ACC): The ACC ans o ma ion aims o cap u e
he co ela ion o he physico-chemical AA desc ip o s along he sequence.
The me hod elies on he ansla ion o he sequences in o ec o s based on
he p incipal physicochemical p ope ies o he AAs. Da a a e ans o med
in o a uni o m ma ix by applying a modified au oc oss-co a iance ans o m
[15]. Fi s , he physico-chemical p ope ies a e ep esen ed by means o he
fi e z-sco es o AA as desc ibed in [16]. Then he Au o Co a iance (AC) and
C oss Co a iance (CC) a e compu ed on his fi s ans o ma ion. They, in
u n, measu e he co ela ion o he same desc ip o (AC) o he co ela ion
o wo diffe en desc ip o s (CC) be ween wo esidues sepa a ed by a lag
along he sequence. F om hese, he ACC fixed leng h ec o s can be ob ained
by conca ena ing he AC and CC e ms o each lag up o a maximum lag,
l. This ans o ma ion gene a es an N×(z2·l) ma ix, whe e z= 5 is he
numbe o desc ip o s.
–Dig am T ans o ma ion: The dig am ans o ma ion is a pa icula ins ance
o he mo e gene al n-g am ans o ma ion. I conside s he equencies o
occu ence o any gi en pai o AAs. The n-g am concep has p e iously
been used in p o ein analysis [17]. This pa icula ans o ma ion gene a es
an N×400 ma ix.
4 Assessmen o S abili y in he Fuzzy Clus e ing o Class C GPCRs
2.2 Da a Clus e ing Using K-Means and Fuzzy C-Means
The K-Means algo i hm c ea es a pa i ion o a se X={x1,...,xN}o obse ed
da a in o a se o Kclus e s Γ={Γ1, . . . , ΓK}by defining a fixed numbe K
o da a cen oids o p o o ypes {µ1, . . . , µK}. I does so by assigning indi id-
ual da a obse a ions o hei closes p o o ypes acco ding o a gi en simila i y
measu e o dis ance. Such assignmen is c isp in he sense ha indi idual ob-
se a ions a e associa ed o indi idual clus e s wi h comple e ce ain y. Fuzzy
and p obabilis ic clus e ing echniques elax his app oach by assigning, o each
obse a ion, a uzzy deg ee ( o ins ance in FCM) o a p obabili y ( o ins ance
in mix u e models) o membe ship o each clus e . Mos app oaches o K-Means
op o diffe en o ms o andom ini ialisa ion o he p o o ypes (seeds). The
algo i hm’s objec i e is finding he se Γ ha minimises a SSQ e o in he o m
∑K
k=1 ∑x∈Γk∥x−µk∥2. FCM gene alizes his objec i e unc ion o become:
C
∑
c=1
N
∑
n=1
ωm
nc∥xn−µc∥2(1)
o C uzzy clus e s, uzzy weigh s ωand uzziness pa ame e m. I is well known
ha diffe en ini ialisa ions o he algo i hm make i con e ge o diffe en local
minima and ha he e is no gua an ee o con e gence o a global minimum o he
objec i e unc ion. In p ac ical applica ions, K-Means and FCM a e un wi h a
sufficien numbe o andom ini ialisa ions and he Γgene a ing minimum e o
is chosen among he es .
2.3 Clus e ing S abili y Measu es
E en i finding a minimum e o Γis a cen al objec i e o K-Means, he s abili y
o he clus e ing solu ion is also ele an . Solu ions ha a e ep oducible a e
equi ed. Tha is, clus e pa i ions ha do no change (much) unde diffe en
ini ialisa ions, i.e., ha a e s able. This clus e s abili y is pa amoun in p ac ical
applica ions and can be quan ified using diffe en indices [18].
I was ecen ly b ough in o a en ion [14] ha K-Means pa i ions wi h
simila e o s migh be g ea ly diffe en om each o he ( hus uns able) and ha
his effec inc eases wi h he alue o K. Assuming ha solu ions ha s ike a
balance be ween low e o and high s abili y ough o be sough , Lisboa e al.
[14] p oposed a amewo k based on he calcula ion o Sepa a ion/Conco dance
(SeCo) maps o se ings using mul iple andom ini ializa ions o K-Means o
diffe en alues o K. This en ails he simul aneous display o a pai o alues
o each un o he algo i hm, namely: The ∆SSQ, calcula ed as he o al SSQ
minus he wi hin-clus e SSQ:
K
∑
k=1
N
∑
n=1
∥xn−µk∥2−
K
∑
k=1
∑
xn∈Γk
∥xn−µk∥2(2)
and a conco dance index (CI) quan i ying s abili y. In [14], he use o C am´e ’s
V index is ecommended as a basis o i . The CI is calcula ed as he median o
Assessmen o S abili y in he Fuzzy Clus e ing o Class C GPCRs 5
he (nin −1) pai wise C am´e ’s V calcula ions o nin ini ializa ions. Fo wo
clus e pa i ions Γand Γ′o , in u n, Kand K′clus e s, C am´e ’s V index is
a a ia ion o a χ2 es , calcula ed as V=√χ2/N min(K−1, K′−1), whe e
χ2=
K
∑
k=1
K′
∑
k′=1
(Okk′−Ekk′)2/Ekk′(3)
He e, Ois an obse ed con ingency able (K×K′) ma ix, whose alues Okk′
indica e he numbe o ins ances in X ha ha e been assigned o clus e kin
one un o he algo i hm and o clus e k′in ano he un. The K×K′ma ix E
con ains he co esponding expec ed alues o independen clus e alloca ions,
calcula ed as Ekk′=1
N(∑K′
j=1 Okj ∑K
i=1 Oik′).
This use o con ingency ables is sui able o c isp clus e assignmen s such
as hose p o ided by K-Means. Fo so assignmen s such as hose p o ided by
FCM o Gaussian Mix u e Models, ins ead, his use occludes he ichness o he
clus e solu ion by equi ing he assignmen o ins ances o clus e s o be based
on he highes deg ee o membe ship o p obabili y.
In his pape , we p opose a a ia ion o con ingency ables ha be e sui s
he cha ac e is ics o uzzy and p obabilis ic models. Elemen s in wha we call
weigh ed obse ed (wO) con ingency ables will now be calcula ed, ollowing
he no a ion o Eq.1 o FCM, as wOcc′=sumN
n=1ωncωnc′; his is, o da a
ins ance n, he p oduc o he deg ee o membe ship o clus e cin a fi s un
o he algo i hm and he deg ee o membe ship o clus e c′in a second un.
Consequen ly, we can ob ain a weigh ed expec ed (wE) con ingency able ma ix
whose elemen s a e defined as wEcc′= (∑C′
j=1 wOcj ∑C
i=1 wOic′)/N. This leads
o he defini ion o a new weigh ed C am´e ’s V index, whe e Ois eplaced by
wOand Eby wEin he calcula ion o χ2in Eq.3.
I FCM es ima ed ha all ins ances had a deg ee o membe ship o 1 o
a single clus e , he weigh ed C am´e ’s V index would educe o i s s anda d
o mula ion. This is unlikely o happen, which means ha he p oposed index
will lead o lowe le els o CI in SeCo. This should, he e o e, be no only a con-
se a i e conco dance es ima o , bu also a mo e eliable clus e ing assessmen
ool, capable o dis inguishing solu ions wi h a ying le els ce ain y.
No e ha SeCo can be used as a flexible ool o chose adequa e alues o he
Kpa ame e (numbe o clus e s). This is equally ue when using he modified
index, bu , in his case, he e should be no bias in a ou o “o e -op imis ic”
solu ions.
3 Expe imen s
3.1 Ma e ials and Expe imen al Se ing
The da a in he ollowing expe imen s we e ex ac ed om GPCRDB2[19] ( e -
sion 11.3.4 as o Ma ch 2011), a public da abase o G P o ein-Coupled Recep o
2h p://www.gpc .o g/7 m

6 Assessmen o S abili y in he Fuzzy Clus e ing o Class C GPCRs
(GPCR) p o ein p ima y sequences. The da a se comp ises a o al o 1,510
class C GPCR sequences, belonging o se en sub amilies and including: 351
me abo opic glu ama e (mG), 48 calcium sensing (CS), 208 GABA-B (GB),
344 ome onasal (VN), 392 phe omone (Ph), 102 odo an (Od) and 65 as e
(Ta). Thei AA leng hs a y om 250 o 1,995.
P e ious esea ch [20] in es iga ed he supe ised classifica ion o hese da a
sequences, om se e al o hei alignmen - ee ans o ma ions, including AAC,
dig am, and ACC, among o he s. He e, we use K-Means and FCM o in es iga e
o wha ex en he na u al clus e ing s uc u e o he da a fi s he sub amilies
(classes) desc ip ion. Fo ha , we fi s epo he esul s o expe imen s in which
he numbe o clus e s is fixed a p io i o be he same as he numbe o class C
GPCR sub ypes. These will p o ide us wi h a p elimina y e alua ion o he le el
o na u al sub ype o e lapping. We hen p oceed o elax ha cons ain and
he SeCo amewo k, wi h he p oposed modifica ion o he conco dance index
in he case o FCM, is applied in a se ing wi h 500 andom ini ializa ions o
he algo i hms o diffe en numbe o clus e s. Following [14], only he bes 10%
△SSQ esul s a e displayed in he SeCo plo s.
3.2 Resul s and Discussion
The h ee ans o med da a se s we e ed o he FCM and K-means algo i hms.
The class (sub ype) specifici y o each clus e o each da a se was measu ed
and he esul s a e p o ided in he ollowing pa ag aphs along wi h class-en opy
measu es. This will in o m us o wha ex en he clus e s ex ac ed by K-means
and FCM algo i hms co espond (o no ) o he heo e ically labeled sub ypes.
The class-en opy o a gi en clus e kis calcula ed as Ek=−∑C
j=1 pkj lnpkj,
whe e jis one o he C= 7 class C GPCR sub ypes and pkj =mkj /mk, whe e,
in u n, mkis he numbe o sequences in clus e kand mkj is he numbe o
sub ype jsequences in clus e k.
Fo FCM, Figu e 1 and Table 1 show ha , o he AAC da a ans o ma ion,
almos none o he defined clus e s show clea class (sub ype) specifici y. Only
in clus e 1, he fi s sub ype (mG) o GPCR achie es a specifici y ha is close
o 60%, bu e en in his case, he hi d sub ype (GB) eaches a non-negligible
30%. Se e al clus e s show common specifici y p ofiles: o ins ance, clus e s 1
and 3 a e p edominan ly a mix u e o mG and GB, which means ha hey
migh uly be a single clus e wi h some subs uc u e. Clus e 4 is a e y mixed
combina ion o Ph and VN, bu clus e s 2, 6 and 7 seem o be a ia ions o his
combina ion, again sugges ing one main clus e wi h u he subs uc u e and
impo an le els o o e lapping. The ACC and Dig am ans o ma ions (Figu es
2 and 3, and, again, Table 1), ins ead, manage o sepa a e some o hese clus e s
o become mo e sub ype-specific. mG and GB a e now mo e clea ly disc imina ed
(clus e s 1 plus 5 and clus e 3, in u n) wi h he es o sub ypes showing clea
o e lapping in some clus e s bu also high specifici y in o he s ( o ins ance,
Ph in ACC clus e 6 and Dig am in clus e 7). In any case, he mo e complex
ans o ma ions (ACC and Dig am) seem o make he FCM clus e ing model
mo e class C GPCR sub ype-specific.
Assessmen o S abili y in he Fuzzy Clus e ing o Class C GPCRs 7
Fig. 1. Class specifici y ba cha (wi h pe cen age alues) o each FCM clus e o
class C GPCR da a se wi h he AAC ans o ma ion. Classes 1 o 7 a e, in u n, mG,
CS, GB, VN, Ph, Od and Ta.
Fig. 2. As Figu e 1, o he ACC ans o ma ion.
Fig. 3. As Figu e 1, o he Dig am ans o ma ion.
8 Assessmen o S abili y in he Fuzzy Clus e ing o Class C GPCRs
Table 1. Numbe o GPCR sequences-pe -clus e (♯) and clus e -specific (Ek) and o al
en opies o he FCM clus e ing o class C GPCR da a wi h he h ee ans o ma ions.
AAC ACC Dig am
♯ Ek♯ Ek♯ Ek
Clus e 1 245 1.45 107 0.13 112 0.12
Clus e 2 239 2.16 207 1.52 374 2.39
Clus e 3 200 1.34 202 0.33 200 0.37
Clus e 4 193 1.30 237 1.17 277 1.09
Clus e 5 67 1.97 199 0.89 179 0.26
Clus e 6 263 2.15 279 1.99 205 2.02
Clus e 7 303 1.95 279 2.20 163 1.28
To al En opy 1.77 1.34 1.29
The esul s o he K-means algo i hm o he se en sub ypes o class C
GPCRs, o which, o he sake o b e i y, we only epo he en opy esul s in
Table 2, a e consis en wi h hose o FCM. Again, almos none o he defined
clus e s show clea class (sub ype) specifici y wi h AAC da a ans o ma ion.
The ACC and Dig am ans o ma ions, ins ead, manage o sepa a e some o
hese clus e s o become mo e sub ype-specific. The simila i y be ween he wo
algo i hms is ha mG and GB a e mo e clea ly disc imina ed han he es o
sub ypes. Mo eo e , in he ACC ans o ma ion, Ph ecep o s can also be dis-
c imina ed om he es sub ypes due o hei high specifici y in clus e 2. The
emaining sub ypes show clea o e lapping in some o he clus e s.
Table 2. Numbe o GPCR sequences-pe -clus e (♯), oge he wi h clus e -specific
(Ek) and o al en opies o he K-Means clus e ing o class C GPCR da a wi h he
h ee ans o ma ions.
AAC ACC Dig am
♯ Ek♯ Ek♯ Ek
Clus e 1 270 1.65 260 0.26 222 0.10
Clus e 2 406 2.17 136 0.72 398 1.47
Clus e 3 196 1.33 150 0.23 121 0
Clus e 4 189 1.24 188 1.07 284 1.10
Clus e 5 54 1.34 165 1.57 184 1.90
Clus e 6 56 1.74 379 1.79 197 1.95
Clus e 7 339 2.03 232 1.97 104 1.63
To al En opy 1.77 1.19 1.39
Compa ing he esul s o bo h algo i hms in e ms o he o al en opy mea-
su e, conclusions a e no clea -cu . ACC and Dig am show a clea ad an age
bo h in FCM and K-Means, bu nei he shows a clea ad an age o e he o he .
Assessmen o S abili y in he Fuzzy Clus e ing o Class C GPCRs 9
We now mo e o he clus e ing s abili y analyses esul s, based on andom
algo i hm ini ializa ions and a ying numbe o clus e s, using he SeCo maps.
Fo each one o he ans o med se s, h ee SeCo maps we e c ea ed using:
–The K-means objec i e unc ion and he s anda d C am´e ’s V index.
–The FCM objec i e unc ion and he s anda d C am´e ’s V index.
–The FCM objec i e unc ion and he no el weigh ed C am´e ’s V index p o-
posed.
As p e iously men ioned, a h eshold o he △SSQ alues o selec he 10%
op alues o each alue o Kis expec ed o allow he degene acy o simila
SSQ alues o be esol ed. The FCM 10% op esul s, as epo ed in Figs. 4 o
6, a e e y pa simonious (much mo e so han he comple e ones, no epo ed
he e), e ealing a high concen a ion o s abili y esul s a ound jus a hand ul
o median C am´e s V index alues, in compa ison wi h he s ill wide sp ead o
K-Means. These esul s a e also e y consis en o e da a ans o ma ions. Fo
K-Means, his effec does no necessa ily inc ease as Kinc eases o any o he
da a ans o ma ions. Fo FCM, hough, an inc ease in sp ead as Kinc eases is
e ealed. O e all, his indica es ha FCM is much mo e esilien han i s c isp
K-Means coun e pa o he a iabili y in oduced by andom ini ializa ions.
Fig. 4. Sepa a ion-Conco dance maps o he AAC da a se , including he 10% bes
esul s. Top: esul s o K-Means; bo om: esul s o FCM, a) wi h s anda d C am´e ’s
V index; b) wi h p oposed weigh ed C am´e ’s V index.