진화연산과적응적 -ut 기반평가를이용한유전자발현데이타의퍼지클러스터분석 68 진화연산과적응적 -ut 기반평가를이용한유전자발현데이타의퍼지클러스터분석 (Fuzzy Cluster Analysis of Gene Expression Profiles Using Evolutionary Computation and Adaptive -ut based Evaluation) 박한샘 조성배 (Han-Saem Park) (Sung-Bae Cho) 요약유전자데이타의클러스터링은방대한유전자정보를발현정도에따라비슷한그룹으로나누어분석하는방법으로유전자의기능을분석하는데사용되어왔다. 클러스터링의한종류인퍼지클러스터링은하나의샘플이소속정도에따라여러그룹에동시에소속되도록나누는방법으로, 하나의유전자데이타는여러가지유전정보를가질수있기때문에유전자발현데이타의분석에보다적절한방법이다. 그러나보통클러스터링방법은초기값에민감하고, 지역해에빠질수있는단점을갖는다. 이런단점을해결하기위해본논문에서는진화연산을이용한퍼지클러스터링방법을제안한다. 이때, 적합도평가를위해서모든데이타에대해동일한기준을적용하는베이지안검증방법의단점을개선하여, 데이타의특성을고려하여결정된적응적 -ut 기반평가방법을사용한다. SRBCT 데이타와효모세포주기데이타를이용해실험을하고결과를분석하여제안하는방법의유용성을확인하였다. 키워드 : 진화적퍼지클러스터링, 적응적 -ut 기반평가, 유전자발현데이타 Abstrat Clustering is one of widely used methods for grouping thousands of genes by their similarities of expression levels, so that it helps to analyze gene expression profiles. This method has been used for identifying the funtions of genes. Fuzzy lustering method, whih is one ategory of lustering, assigns one sample to multiple groups aording to their degrees of membership. This method is more appropriate for analyzing gene expression profiles beause single gene might involve multiple geneti funtions. Clustering methods, however, have the problems that they are sensitive to initialization and an be trapped into loal optima. To solve these problems, this paper proposes an evolutionary fuzzy lustering method, where adaptive -ut based evaluation is used for the fitness evaluation to apply different riteria onsidering the harateristis of datasets to overome the limitation of Bayesian validation method that applies the same riterion to all datasets. We have onduted experiments with SRBCT and yeast ell-yle datasets and analyzed the results to onfirm the usefulness of the proposed method. Key words : evolutionary fuzzy lustering, adaptive -ut based evaluation, gene expression profiles. 서론 클러스터링은방대한유전자정보를비슷한속성의 본연구는생체인식연구센터 (BERC) 를통해한국과학재단 (KOSEF) 에서지원받았음 학생회원 : 연세대학교컴퓨터과학과 sammy@slab.yonsei.a.kr 종신회원 : 연세대학교컴퓨터과학과교수 sbho@s.yonsei.a.kr 논문접수 : 2005년 7월 22일심사완료 : 2006년 6월 4일 그룹으로나누어분석할수있도록해줌으로써유전자발현데이타를분석하는데유용하다. 이방법은비슷한기능을가진유전자들의집단을형성하여, 집단내유전자들의기능을밝히거나, 미지의유전자를분석하는데이용되고있다 []. 그러나일반적으로실세계의데이타로부터명확한경계를가진집단을구성하기는어렵다 [2]. 하나의유전자가여러가지유전정보를동시에가질수있는유전자데이타는그대표적인예라고할수있으며, 퍼지클러스터링은이러한유전자발현데이타
682 정보과학회논문지 : 소프트웨어및응용제 33 권제 8 호 (2006.8) 를분석하는데유용한방법이다 [3]. 일반적인클러스터링알고리즘은초기값에매우민감하며목적함수를최소화시키는방향으로알고리즘이진행되기때문에지역해에빠지기쉬운문제점이있다 [4,5]. 또한클러스터의수를고정시키고실험을하기때문에데이타에대한사전지식이없으면올바른분석을하기가어렵다. 예를들어클러스터수를모르는데이타를클러스터링하려면여러번반복해서실험해야하기때문에시간비용이커지게된다. 이외에클러스터결과의검증에대한문제도존재한다. 서로다른환경에서수집된데이타는다른특성을가지기때문에모든데이타를동일한기준에의해평가하는것은적절하지못하다. 본논문에서는이와같은문제점을해결하기위해진화연산기법을이용한퍼지클러스터링방법과데이타의특성을고려한적응적 -ut 기반평가방법을제안한다. 최적화문제를해결하는데뛰어난성능을보이는유전자알고리즘 (geneti algorithm)[6] 을사용하여, 초기값에덜민감하고보다최적해에근접한클러스터링을할수있다 [7]. 클러스터링에진화연산을적용한연구는많이진행되어왔는데, 클러스터중심과클러스터내개체들의거리를최소화시키기위해유전자알고리즘을사용한 Maulik의연구 [5], 하드 -means 알고리즘과퍼지 -means 알고리즘의목적함수를최소화시키는데유전자알고리즘을사용한 Hall의연구등이대표적이다 [4]. 하지만이러한연구들은클러스터의수를고정시키고주로클러스터링알고리즘의목적함수최소화를위해유전자알고리즘을이용하였기때문에다양한클러스터집단에대한평가를동시에할수없는단점이있다. 제안하는방법은하나의클러스터분할을염색체로표현하여다양한클러스터분할을형성하도록하였고, 이집단을유전자알고리즘을이용해진화시켜최적의클러스터분할을찾아낸다. 각세대마다퍼지 -means 알고리즘을사용하여집단내개체들을클러스터링하고각개체의적합도평가에는퍼지클러스터평가척도인베이지안검증방법을개선한적응적 -ut 기반평가방법을사용한다. 결정트리 (deision tree) 의규칙을이용하여각데이타에따라클러스터결과를검증하는기준을달리하여적절한평가가이루어지도록한다. 제안하는방법을공개된유전자발현데이타인 SRBCT 데이타와효모세포주기데이타에적용하여제안하는방법의유용성을확인하였고, 마지막으로제안하는방법이찾아낸최적의클러스터분할을분석하였다. 2. 배경 2. DNA 마이크로어레이 마이크로어레이기술의등장으로한번의실험으로대량의유전자정보를습득할수있게되었다. 마이크로어레이는고밀도의 DNA나 oligonuleotide를슬라이드위에배열해놓은것으로 DNA 칩이라고도한다. 본논문에서는두가지의 DNA 마이크로어레이데이타인 SRBCT데이타와효모세포주기데이타가실험을위해사용되었다. DNA 마이크로어레이는실험을거친수천개이상의유전자를일정한간격으로배열한후유전자들의발현패턴에따른색변화로부터유전자발현정보를얻을수있도록만들어진바이오칩이다. 어레이상의각셀은두개의다른환경에서채집된유전물질에녹색의 Cy3와빨간색의 Cy5라는각기다른형광물질을합성하여동일한양으로보합한것이다. 이것을레이저형광스캐너로읽어들이면녹색부터빨간색에이르는발현정도를얻을수있는데, 식 () 과같이 Cy5/Cy3의비율에밑이 2인로그를취한값을그셀의발현정보값으로얻게된다 [8,9]. 식 () 에서 Int는강도 (intensity) 를의미한다. Int(Cy5) gene _ expression = log 2 () Int(Cy3) 2.2 퍼지 -means 알고리즘퍼지 -means 알고리즘은 Bezdek에의해제안된알고리즘으로, 가장널리이용되는퍼지클러스터링방법이다. 주어진데이타집합이 X = {x, x 2,..., x n} 이고퍼지클러스터링의중심벡터가 V = {v, v 2,..., v } 일때, 목적함수 J m 은각데이타 x j 와각클러스터중심 v i 와의거리와클러스터에대한소속정도 (degree of membership) 값으로정의된다. n m 2 J m ( X, U, V ) = ( µ ij ) d ( x j, vi ) (2) j= i= 여기서, µ ij 는 xj 의 i번째클러스터에대한소속정도를의미하며, 소속행렬 U = [ µ ij ] 의원소이다. d 2 (,) 는유클리드거리의제곱이고, 매개변수 m은각데이타의소속정도에대한퍼지파라미터를나타내며, 보통 보다큰수를사용한다 [0,]. m이 이되면퍼지 -means 알고리즘은하드 -means 알고리즘과동일해진다. 퍼지 -means 알고리즘의수행절차는다음과같다. 단계 : 클러스터수 와퍼지파라미터 m을결정 한다. 단계 2: 식 (3) 의조건을만족하도록한다. µ ij 를초기화 µ ij =, j n (3) i=
진화연산과적응적 -ut 기반평가를이용한유전자발현데이타의퍼지클러스터분석 683 단계 3: 각클러스터의중심 v i 를계산한다 (i=, 2,..., ). n m µ ij x j j= = i n m µ ij j= v 단계 4: 소속행렬 U 를계산한다. m 2 d ( x j, vi) µ = ij (5) m k = 2 d ( x j, vk) 단계 5: 아래의종료조건이만족될때까지단계 3과 (l) 단계 4를반복한다. 여기에서 J m 은 l번째루프에서의목적함수값을의미한다. 3. 제안하는방법 (4) ( l) ( l ) { J m J m } ε (6) 본논문에서는최적의클러스터분할을찾기위해그림 과같이진화연산을이용한클러스터링방법을제안한다. 제안하는방법은크게두부분으로나누어, 유전자알고리즘을이용한퍼지클러스터링알고리즘을통하여최적의클러스터분할을검색하는부분과, 데이타로부터필요한정보를추출하여미리결정트리에의해생성된규칙으로베이지안검증에필요한최적의 -ut을결정하는적응적 -ut 기반평가부분으로구성된다. 3. 적응적 -ut 기반평가여기에서는베이지안검증방법과이를개선하기위해사용될데이타의특성을고려한 -ut을결정트리의규 칙을이용해결정하는과정을설명한다. 3.. 베이지안검증방법베이지안검증방법은확률기반의검증방법으로, 데이타가주어졌을때해당데이타에대한클러스터분할의사후확률을구하여클러스터결과를검증하는방법이다 [8]. 베이지안검증방법은이처럼주어진데이타에대해각클러스터의사후확률이최대가되는것을최적의클러스터분할로한다. max P ( Cluster Dataset) (7) 베이즈이론을적용하면다음과같이사전확률을이용하여사후확률값을구할수있다. Cluster) Dataset Cluster) P ( Cluster Dataset) = (8) Dataset) 각데이타가서로독립이라가정하면식 (8) 은다음의식 (9) 와같이표현될수있다. Cluster Dataset) = Cluster d, d2,..., d N ) = Cluster d) Cluster d2)... Cluster d N ) (9) 이러한과정을이용하여식 (0) 과같이모든클러스터에대한 Cluster Dataset) 들의합을구하여이를베이지안스코어 (Bayesian sore) 라고정의한다. 이베이지안스코어 (BS) 는그값이클수록각클러스터의사후확률이커지므로좋은클러스터분할을나타낸다고볼수있다. Di ) di, di2,..., din ) di) di2 )... din ) i= i= i= BS = = = C C C Ni ) dij ) / dij ) i= j= =, Di = { dij µ ij > α, j n}, Ni = n( Di ) C (0) 여기서 n(d i) 는 D i 의개수이며, 일정한확률보다큰멤버쉽값 (u ij >α) 을가진샘플들만을선택한다. 그이유 그림 제안하는방법의개요
684 정보과학회논문지 : 소프트웨어및응용제 33 권제 8 호 (2006.8) 는 BS의계산과정중에는곱셈계산이있기때문에 u ij=0인샘플들의경우올바른값이나올수없게되고, 또한퍼지클러스터링을하는궁극적인이유는명확하지않은개체들의소속정도를분석하기위함인데, 모든개체에대해검증을하는것보다는특정한임계값이상의소속정도를가진개체들로클러스터분할을평가하는것이더정확하기때문이다. 이러한임계값을 -ut 이라하며 -ut의결정은베이지안검증방법에서매우중요한역할을한다. 각확률은다음식과같이계산될수있다. n uij j=, uij > α ) = n uij i= j= P dij ) = ) dij ) = ) uij i= i= () ( (2) 퍼지클러스터링결과로멤버쉽행렬이주어질때, 이의멤버쉽값은각샘플이각클러스터에속할확률이라고볼수있다. 그러므로각샘플의멤버쉽값 u ij 를 d ij C i) 로정의할수있다. 베이지안검증방법은최종적으로 Bayesian sore(bs) 를계산하여클러스터를검증하는데, 다음과같은과정을거친다. 베이지안검증방법의최종결과값인 BS는 0과 사이의확률값을가지며, 가장큰값을가진분할을최적의클러스터분할로평가한다. 단계 : 퍼지클러스터링의결과인멤버쉽행렬 U ij 를구한다. 단계 2: U ij 에서 u ij>α를만족하는샘플들을각클러스터별로선택한샘플들의집합인 D j 를구한다. 단계 3: 단계2에서선택한 D j 에대해 D j C j), D j), C j) 값을계산한다. 단계 4: 단계3에서계산한값을이용하여 BS를계산한다. 단계 5: BS의값을최대로하는클러스터분할을최적의분할로평가한다. 3..2 적응적 -ut기반평가앞에서설명했듯이데이타마다샘플의분포등특성이다르기때문에그에맞추어적응적으로 -ut을설정해주는것이필요하다. 본논문에서는데이타의도메인을고려하여 -ut을결정하기위해결정트리의규칙에의해각데이타에맞는 -ut을자동으로구한다. 먼저실험에사용될 N개의유전자발현데이타를퍼지 -means 알고리즘을통해클러스터링하고, 그결과를베이지안검증방법으로평가한후, 각데이타별로적절한 -ut을결정해결정트리의학습데이타을구성한 다. 규칙생성과정에서는결정트리를학습하고, 이를바탕으로규칙을생성한다. 그림 2 결정트리의학습데이타생성과정결정트리학습데이타의속성은그림 2와같이퍼지클러스터링을거쳐나온각데이타의소속행렬을이용해생성한다. 소속행렬의소속정도를 0.0부터.0까지 0.단위로증가시키며총 0구간으로나누고, 각구간의소속정도를가진샘플의빈도를계산해데이타의총샘플수로나눈값을속성으로정의해사용한다. 이렇게정한각속성을 A ~A 0 으로정의한다. 이렇게구성된학습데이타를가지고데이타가입력되면결정트리에의해만들어진규칙에의해 -ut을결정한다. 이과정은실험결과 4.2.에서설명된다. 이후이렇게결정된 -ut 을이용해베이지안검증방법의 BS를구하고이를각개체의적합도평가에이용한다. 3.2 진화연산을이용한퍼지클러스터링여기에서는최적의클러스터분할을찾기위한방법인유전자알고리즘을이용한퍼지클러스터링알고리즘에대해설명하고, 유전자알고리즘의단계별로제안하는방법에대해기술한다. 3.2. 개체의표현본논문에서는일반적인이진표현을사용하지않고, 실수표현법을사용한다. 이를통해하나의개체가여러클러스터중심에대한정보를포함하는하나의클러스터분할을표현할수있게된다. 하나의클러스터분할은 K개의클러스터를포함하고각중심값이 N차원으로표현된다고할때, 개체는 NxK 공간으로표현된다. 본논문은다양한크기의클러스터수를가진집단을평가하는것이목적이기때문에가변길이로개체를표현한다. 그림 3과같이크기가다른개체들이존재하여, 각개체가서로다른개수와값을갖는클러스터중심으로표현된다. 3.2.2 집단초기화와적합도평가하나의집단은집단내의클러스터수만큼의샘플을임의로선택하여그샘플들을클러스터중심으로초기화하는데, 개체수만큼위의과정을반복하여전체집단을초기화한다. 본논문은가변길이개체를사용하는데, 데이타샘플수의제곱근을최대길이로제한하였다 [3]. 최저길이는 2로설정하여최소두개이상의클러스터
진화연산과적응적 -ut 기반평가를이용한유전자발현데이타의퍼지클러스터분석 685 그림 3 가변길이개체의표현 를가진개체로집단을설정하였다. 적합도평가를위해서는적응적 -ut기반평가를사용하였는데, 먼저개체내의클러스터중심값을기반으로퍼지 -means 알고리즘을이용해데이타의모든샘플을클러스터링한다. 그리고각샘플과클러스터중심간의거리를계산하여식 (3) 과같이소속행렬값을구하고, 식 (4) 을이용해클러스터중심을갱신한다. 염색체내의클러스터중심정보는이렇게새로계산된클러스터중심으로바뀐다. u ij = 2 d ( x j, ν m ) i 2 (, ) m (3) k= d x j ν i n n m m ν i = uij x j uij (4) j= j= 그이후에는바뀐개체들을평가하며이과정에서데이타에대한사전지식을반영한적응적 -ut기반평 가방법을사용한다. 개체들이서로다른클러스터분할을표현하고있기때문에다양한평가값이계산되며이결과를바탕으로선택이이루어진다. 적합도에비례한확률을주어적합도가높은개체의생존확률을높이는룰렛휠 (Roulet wheel) 방법이선택을위해사용되었다 [4]. 3.2.3 교차와돌연변이연산본논문은가변길이개체를사용하기때문에, 일반적인교차나돌연변이연산을적용할수없다. 교차연산은개체의크기를고려하여교차점을선택한후앞부분의클러스터중심값을바꾸는방식으로이루어진다. 염색체의길이가 l인경우에, [, l-] 사이의범위에서교차점이선택되는데, 그림 4는교차연산의예를보여준다. 실수표현법을사용하기때문에돌연변이연산은다음과같은과정을통해이루어진다. 가 [0, ] 사이의값을가진균일한분포의변수라고하고, 가돌연변이가일어나는지점의값이라고할때, 돌연변이에의해바뀌 그림 4 교차연산의예
686 정보과학회논문지 : 소프트웨어및응용제 33 권제 8 호 (2006.8) 는 가식 (5) 와 (6) 에의해계산된다 [5]. 의값이 0 이아닐때는식 (5) 를사용하고, 가 0일때는식 (6) 을사용한다. 이때 + 와 - 부호가사용될확률은동일하다. ν ± 2 δ ν, ν 0 (5) ν ± 2 δ, ν = 0 (6) 4. 실험결과 4. 실험환경 4.. 실험데이타실험을위해서 SRBCT와효모세포주기데이타가사용되었으며, 결정트리를이용한적응적 -ut 결정실험을위해추가로림프종 (lymphoma)[5], 백혈병 (leukemia)[6], 혈청 (serum)[7] 데이타가사용되었다. SRBCT(Small Round Blue Cell Tumors) 데이타 : SRBCT 데이타는총 63개의샘플로구성되며 6567 개의유전자를갖는다. NB(neuroblastoma), RMS (rhabdomhosaroma), NHL(non-Hodgkin lymphoma), EWS (Ewing family of tumors) 의 4 클래스로나뉘며네가지모두암의일종이다. 본논문에서는 Kahn의연구 [8] 를참고해클러스터링과정에중요하다고알려진 96개의유전자를사용하여 63개의샘플을클러스터링하였다. 효모세포주기 (Yeast ell-yle) 데이타 : 효모세포주기유전자발현데이타는두번의세포주기동안약 6000개유전자들의발현정도를측정한데이타이다 [9]. 0분간격으로두번의효모세포주기에해당되는 60분에걸쳐유전자들의발현정도를 7개의시점에서측정했다. 이데이타는생물학적기능에따라분류된유전자들이주기별로지정되어있어서분석을위해자주사용된다. 본논문에서는실험과정에서의미있는발현변화를보이는 42개의유전자를선택하여클러스터링하였다 [9]. 4..2 파라미터설정모든실험은 00세대까지진화시켰고, SRBCT 데이타는집단의크기를 00으로, 효모세포주기데이타는 200으로설정하였다. SRBCT 데이타의집단의크기를더작게설정한것은샘플수가효모세포주기데이타보다적기때문이다. 최대클러스터수는 SRBCT의경우 8로, 효모세포주기데이타는 20으로설정하였다 [6]. 교 차율은 0.8, 돌연변이율은 0.0이사용되었고, 퍼지 - means 알고리즘의퍼지파라미터는모든실험에동일하게.2로설정되었다. 4.2 실험결과 4.2. 적응적 -ut 결정앞에서설명한 5가지의유전자발현데이타를사용하여결정트리의학습데이타를생성하였는데, 생성된규칙은그림 5와같다. 규칙에의해학습데이타의첫속성 (A ) 이 0.957 이상이면 -ut이 0.8로결정되며, 이와동시에세번째속성 (A 3) 도 0.0 이하이면 -ut이 0.2로결정된다. 마지막으로열번째속성 (A 0) 은 -ut 0.과 0.4를결정하는기준이된다. 그림 5 결정트리에의해생성된규칙결정트리에의해결정된 SRBCT와효모세포주기데이타의 -ut은 0.2와 0.4이다. 두데이타모두 A 의값은 0.957보다큰값을갖지만, A 3 에서다른방향으로갈라지게된다. 두데이타로부터추출한결정트리의학습데이타는표 과같다. SRBCT 데이타와효모세포주기데이타를비교해보면, SRBCT 데이타는 A 2~A 9 속성이효모세포주기데이타보다작은수치를보이고, A 0 속성은더큰수치를보인다. 이는 SRBCT 데이타 의샘플들이효모세포주기데이타의샘플들보다클러스터간의경계가명확하여 0.9 이상의큰소속정도를갖는샘플들이많기때문이다. 표 은이두데이타의특성이다르다는것을명확히보여주며, 따라서이점을고려하여검증을해야클러스터분할을올바르게평가할수있음을뒷받침한다. 4.2.2 최적의클러스터분할탐색그림 6은세대에따라진화하는 SRBCT 데이타의평균적합도추이를보여준다. 처음에빠르게진화하다가 표 결정트리의학습데이타 학습데이타의속성 데이타 A A 2 A 3 A 4 A 5 A 6 A 7 A 8 A 9 A 0 효모세포주기.000 0.23 0.4 0.086 0.07 0.064 0.059 0.069 0.62 0.546 SRBCT.000 0.06 0.000 0.06 0.000 0.06 0.000 0.000 0.048 0.937
진화연산과적응적 -ut 기반평가를이용한유전자발현데이타의퍼지클러스터분석 687 표 2 FCM과의성능비교 (SRBCT 데이타 ) 단일 FCM GA+FCM 실험 BS 목적함수값 BS 목적함수값 0.58028 56.9920 0.58042 56.998 2 0.58034 56.9925 0.58036 56.9920 3 0.5803 56.992 0.5804 56.999 4 0.58029 56.9922 0.58036 56.9920 5 0.5804 56.9926 0.58036 56.9920 6 0.58034 56.992 0.5804 56.999 7 0.5803 56.9920 0.58042 56.998 8 0.58028 56.9922 0.58042 56.998 9 0.58033 56.9922 0.5804 56.999 0 0.58036 56.9920 0.58042 56.998 평균 0.58033 56.9922 0.58040 56.999 그림 6 SRBCT 데이타의평균적합도추이변화 (P=00) 표 3 FCM과의성능비교 ( 효모세포주기데이타 ) 단일 FCM GA+FCM 실험 BS 목적함수값 BS 목적함수값 0.03354 64.472 0.3256 66.883 2 0.00875 63.670 0.246 6.542 3 0.03238 65.057 0.266 62.9 4 0.03825 62.653 0.08058 62.073 5 0.0265 63.758 0.0667 62.798 6 0.04096 64.086 0.09778 62.32 7 0.02806 63.052 0.873 62.042 8 0.04473 64.877 0.3659 62.773 9 0.02478 62.452 0.2898 62.905 0 0.04645 69.26 0.246 6.542 평균 0.0395 64.329 0.534 62.778 그림 7 효모세포주기데이타의평균적합도추이 (P=200) 20세대에가까워지면 0.6 정도의값으로평균적합도가수렴함을알수있다. 그림 7은효모세포주기데이타의평균적합도추이를보여준다. SRBCT 데이타의결과보다느리게수렴하지만 80세대정도까지평균적합도가꾸준히증가하다가그이후 0.2 정도의값에수렴하는결과를보이고있다. 두실험모두 0회반복실험을하였다. 효모세포주기데이타의평균적합도변화가 SRBCT 데이타의결과에비해심한변화를보이는데이는두데이타가가진다른특성이반영된결과이다. 이차이는표 을보면알수있는데 SRBCT 데이타는소속정도가 0.9보다크거나 0.보다작은데이타가많은반면효모세포주기데이타는다양한분포를보였다. 4.2.3 단일퍼지 -means 알고리즘과의성능비교여기에서는단일 FCM과제안하는방법인 GA+FCM 을 BS와목적함수값을이용해비교한다. 표 2는 SRBCT 데이타에대해서두방법의결과를비교한표이다. 클러스터링결과가좋을경우 BS값은커지고목적함수값은 작아진다. 큰차이는아니지만제안하는방법의결과가단일 FCM의결과보다좋은값을보인다. 표 3은역시 0번반복한효모세포주기데이타의실험결과이다. 효모세포주기데이타의경우는큰차이로제안하는방법이더좋은결과를보였다. 제안하는방법과단일 FCM을비교한결과, 제안하는방법이최적해에더근접한결과를보이는것을확인하였다. 4.3 결과분석 4.3. SRBCT 데이타의실험결과분석 SRBCT 데이타에제안하는방법을적용하여얻은실험결과를 Khan의연구 [8] 와비교하였다. 그림 8은제안하는방법으로찾은 4개의클러스터와실제샘플이속한클래스를비교한것이다. 63개샘플이모두자신이속한클래스에올바로소속되었다. 클래스 EWS와 RMS의가운데위치한샘플 EWS-T3은 EWS 클래스와 RMS 클래스에동시에비슷한소속정도로속한다는실험결과를얻었다. 이처럼 SRBCT의실험결과가좋은이유는원래의
688 정보과학회논문지 : 소프트웨어및응용제 33 권제 8 호 (2006.8) 그림 8 SRBCT 데이타의클러스터링결과 (96 개유전자 ) 데이타에서추출한 96개의유전자가이미클래스별로분포가다른발현정도를보이기때문이다. 또한 Khan의연구 [8] 에서와같이 차로최소한의불필요한정보만을제거한 2308개의전체유전자를이용한실험결과, 표 4 와같이 8개의클러스터가발견되었다. 표 5는제안하는방법이찾아낸샘플로소속정도가 0.3 이상이면서다수의클러스터에동시에속하는퍼지샘플들이다. 총 4개의샘플을찾았으며, 각각의소속정도와클러스터번호가표에표시되어있다. 마지막에표시된샘플 EWS-T3은 96개의유의한유전자를사용했을때발견된퍼지샘플이다. Cluster 3과 Cluster 4 에동시에속하는것으로나타났는데이두클러스터가 EWS와 RMS에속하는클러스터라고유추해볼수있다. 표 5 SRBCT 데이타의퍼지샘플목록퍼지샘플첫번째클러스터두번째클러스터 EWS-T9 0.549942(3) 0.379079(4) NB-C5 0.564467(6) 0.33732(7) RMS-C6 0.349232(7) 0.3335(6) RMS-C8 0.456904(5) 0.339977() EWS-T3 0.78476(3) 0.20988(4) 표 4의결과를토대로각클러스터간의관계를분석하여그결과를그림 9에정리하였다. Cluster 0과 Cluster 3은 EWS클래스에완전히소속되고 Cluster, Cluster 4, Cluster 5, Cluster 7은소속샘플의일부가 EWS클래스에속한다. 절반정도의샘플이 EWS와 RMS클래스에동시에속하는 Cluster 5는 EWS와 RMS클래스의중간성질을가진클러스터로분석할수있다. Cluster 6은 NB클래스에, Cluster 2는 BL클래스에속하며 Cluster 은 EWS, BL, NB 세개의클래스에동시에속한다. 4.3.2 효모세포주기데이타의실험결과분석효모세포주기데이타의실험결과는 Cho의연구 [9] 와비교하여알려진유전자들의기능을참고해분석을시도하였다. 0.3이상의소속정도를갖고둘이상의클러스터에소속되는퍼지유전자의분석에초점을맞추었다. 그림 0은실험결과얻어진퍼지유전자들의설명과발현정도를나타낸다. 총 25개의유전자들을소속된클러스터번호에따라크게네개의그룹으로나누어분석하였다. YBL032w, YHR03C, YCL063w는 Cluster 4, Cluster 7, Cluster 에속하며이세개의클러스 클러스터번호 Cluster 0 Cluster Cluster 2 Cluster 3 Cluster 4 Cluster 5 Cluster 6 Cluster 7 표 4 SRBCT 데이타의클러스터링결과 (2308 개유전자 ) 클러스터에속하는샘플들 EWS-C6 EWS-C8 EWS-C9 EWS-C0 EWS-C EWS-C EWS-C2 EWS-C3 BL-C BL-C2 BL-C3 BL-C4 NB-C BL-C5 BL-C6 BL-C7 BL-C8 EWS-T6 EWS-T7 EWS-T9 EWS-T EWS-T2 EWS-T4 EWS-T5 EWS-T9 EWS-T3 RMS-C4 RMS-T5 RMS-T6 RMS-T7 RMS-T8 RMS-T0 RMS-T EWS-C4 EWS-T EWS-T2 EWS-T3 EWS-T4 RMS-C8 RMS-C RMS-T RMS-T2 RMS-T3 RMS-T4 NB-C2 NB-C3 NB-C4 NB-C5 NB-C6 NB-C7 NB-C8 NB-C9 NB-C0 NB-C NB-C2 EWS-C7 RMS-C2 RMS-C3 RMS-C5 RMS-C6 RMS-C7 RMS-C9 RMS-C0
진화연산과적응적 -ut 기반평가를이용한유전자발현데이타의퍼지클러스터분석 689 선택하여, 각각의발현정도의변화를그래프로나타낸것이다. Cluster 7은 26개의유전자로구성되는데효모세포주기중 G 2 기에가장높은발현정도를보이는유전자들로구성된것으로미루어 G 2 기와관련된그룹임을알수있다. Cluster 5는 S기에서높은발현정도를보여 S기와관련된그룹임을알수있으며, 마지막그룹의 Cluster 2는 G 기와 S기사이에서최대발현정도를보인다. Cluster 2는그림 9에서 Cluster 5가속한두번째그룹에도속하는것으로보아실제로두클러스터에모두연관되어있다고할수있다. 5. 결론및향후연구 그림 9 SRBCT 데이타의클러스터별분류결과 (2308개유전자 ) 터를하나로묶었다. 마찬가지로 Cluster 5, Cluster 2, Cluster 3, Cluster 5를하나의그룹으로묶었다. 이경우에는 Cluster 5를중심으로 Cluster 2, Cluster 3, Cluster 5가관계를갖는다. 나머지두그룹은 Cluster 0, Cluster, Cluster 2를하나, Cluster 0, Cluster 2 를다른하나의그룹으로묶었다. 좌측의발현정도를나타낸그림을보면각그룹별로다른패턴을보임을확인할수있다. 그림 은네개의그룹에서각각하나의클러스터를 본논문은최적의클러스터분할을효율적으로탐색하기위해진화연산을이용한클러스터링방법을제안하였고, 클러스터링결과의적절한평가를위해베이지안검증방법의단점을개선하여데이타에따라평가기준을다르게한적응적 -ut기반평가방법을제안하였다. 제안하는방법을 SRBCT 데이타와효모세포주기데이타에적용해실제로진화가잘이루어지는것을확인하였으며, 제안하는방법을통해찾아낸최적의클러스터분할을기존연구와비교하여분석하였다. 추후연구로좀더다양한데이타에제안하는방법을적용할것이다. 참고문헌 [] U. Alon, et al., "Broad patterns of gene expression revealed by lustering analysis of tumor and normal olon tissues probed by oligonuleotide 그림 0 제안하는방법이찾은효모세포주기데이타의퍼지유전자들의정보 ( 발현정도, 유전자설명, 소속클러스터번호 )
690 정보과학회논문지 : 소프트웨어및응용제 33 권제 8 호 (2006.8) 그림 클러스터별유전자들의발현정도 ( 효모세포주기데이타 ) arrays," Pro. Natl. Aad. Si. USA, vol. 96, pp. 6745-6750, June 999. [2] A. P. Gash and M. B. Eisen, "Exploring the onditional oregulation of yeast gene expression through fuzzy k-means lustering," Genome Biology, vol. 3, no., researh 0059.-0059.22, 2002. [3] N. Bolshakova and F. Azuaje, "Cluster validation tehniques for genome expression data," SIGPRO, vol. 2, no. 82, pp. -9, 2002. [4] L. O. Hall, et al., "Clustering with a genetially optimized approah," IEEE Trans. on Evolutionary Computation, vol. 3, no. 2, pp. 03-2, 999. [5] U. Maulik and S. Bandyopadhyay, "Geneti algorithm-based lustering tehnique," Pattern Reognition, vol. 33, pp. 455-465, 2000. [6] L. Chamber, Pratial Handbook of Geneti Algorithm, CRC Press, 995. [7] J. N. Bhuyan, et al., "Geneti algorithm for lustering with an ordered representation," in Pro. 4th Int. Conf. Geneti Algorithms, pp. 408-45, 99. [8] M. B. Eisen, P. T. Spellman, P. O. Brown and D. Botstein, "Cluster analysis and display of genomewide expression patterns," Pro. Natl. Aad. Si. USA, 95, pp. 4863-4868, 998. [9] M. E. Futshik, A. Reeve and N. Kasabov, "Evolving onnetionist systems for knowledge disovery from gene expression data of aner tissue," Artifiial Intelligene in Mediine, 28, pp. 65-89, 2003. [0] R. E. Hammah and J. H. Curran, "Validity measures for the fuzzy luster analysis of orientations," IEEE Trans. on Pattern Analysis and Mahine Intelligene, vol. 22, no. 2, 2000. [] F. Hoppner, et al., Fuzzy Cluster Analysis, Wiley, pp. 43-39, 999. [2] S.-H. Yoo, H.-H. Won and S.-B. Cho, "Analysis of Saharomyes ell yle expression data using Bayesian validation of fuzzy lustering," Journal of Korea Information Siene Soiety, vol. 3, no. 2, pp. 59-60, 2004. [3] D. Dembele, and P. Kastner, "Fuzzy -means method for lustering miroarray data," Bioinformatis, vol. 9, no. 8, pp. 973-980, 2003. [4] K. Krishna and M. N. Murty, "Geneti k-means algorithm," IEEE Trans. on Systems, Man and Cybernetis, vol. 20, no. 3, pp. 433-439, 999. [5] A. A. Alizadeh, et al., "Distint types of diffuse large B-ell lymphoma identified by gene expression profiling," Nature, vol. 403, pp. 503-5, February 2000. [6] T. R. Golub, et al., "Moleular lassifiation of aner lass disovery and lass predition by gene-expression monitoring," Siene, vol. 286, no. 5, pp. 53-537, Otober 999. [7] V. R. Iyer, et al., "The transriptional program in the response of human fibroblast to serum," Siene, vol. 283, pp. 83-87, 999. [8] J. Khan, et al., "Classifiation and diagnosti predition of aners using gene expression profiling and artifiial neural networks," Nature, vol. 7, no. 6, pp. 673-679, June 200. [9] R. J. Cho, et al., "A genome-wide transriptional
진화연산과적응적 -ut 기반평가를이용한유전자발현데이타의퍼지클러스터분석 69 analysis of the mitoti ell yle," Moleular Cell, vol. 2, pp. 65-73, 998. 박한샘 2004 년 2 월연세대학교컴퓨터과학과 ( 학사 ). 2006 년 2 월연세대학교컴퓨터과학과 ( 석사 ). 2006 년 3 월 ~ 현재연세대학교컴퓨터과학과박사과정. 관심분야는패턴인식, 생물정보학, 지능형로봇, HCI 조성배정보과학회논문지 : 소프트웨어및응용제 33 권제 3 호참조