Microsoft Word doc

Transcription

1 공학석사학위논문 유전알고리즘을이용한마이크로어레이표본 분류에유용한유전자선택 Selection of Informative Genes for Microarray Sample Classification Using the Genetic Algorithm 2003 년 6 월 서울대학교대학원 전기컴퓨터공학부 이정문 - 1 -

2 초록 암을정확하고세밀히분류하는것은암의진단과치료를위해매우중요하다. 그러나, 현재이용되는형태학적, 임상적기반의암분류방법들은많은발전에도불구하고여전히불확실성을내포하고있다. 이에최근들어새롭게등장한생물공학기술인 DNA 마이크로어레이 (microarray) 가암분류연구에적용되기시작하고있다. 마이크로어레이는수천개의유전자의발현량을한번에측정한것으로서, 암의종류에따라다르게발현되는양상을통계적으로발견함으로써암분류에이바지할수있다. 그런데, 마이크로어레이데이터는표본의개수에비해자질 ( 즉유전자 ) 의개수가훨씬많으므로, 과적합을피하면서분류에유용한자질을선택하는작업이매우중요하다. 기존에주로사용되는자질선택 (feature selection) 방법은표본들사이에서큰변이를보이는자질을계산하여얻은순위에서상위에위치하는것을선택하는방법이다. 하지만이와같은방법은유전자사이의상호작용을감안하지않으므로, 단독으로는높은변이를보이지않는유전자가다른유전자와함께발현함으로써분류에유용하게이용될수있다는점이고려되지않는다. 본논문에서는유전알고리즘을이용하여통계적순위기반자질선택방법에서찾지못하는표식유전자 (marker gene) 를찾기위해시도한다. 유전알고리즘은공간탐색기법의일종으로서문제해결을위해해 (solution) 들을집단적으로운용하며, 기존해들의특징을결합, 교란하여새해를만들어낸다. 본논문에서는유전알고리즘의창발성이통계적순위기반방법에서찾지못하는유전자를알아내는데기여할수있으리라는가정을실제로검증한다. 주요어 : 마이크로어레이, 암분류, 유전알고리즘 학번 :

3 목차 1. 서론 4 2. 관련연구 마이크로어레이개요 기존마이크로어레이기반암분류연구 마이크로어레이데이터의특징 암분류를위한유전자집합선정방법 Genetic Algorithm(GA) k-nearest neighbor GA/kNN 알고리즘소개 실험및분석 실험 1 급성백혈병데이터 데이터및실험방법 실험결과 실험 2 SRBCT 데이터 데이터및실험방법 실험결과 결론

4 1 장 서론 분자생물학과공학기술의결합으로탄생한 DNA 마이크로어레이 (microarray) 는생체조직표본으로부터수천개의유전자와 EST(Expressed Sequence Tag) 의발현양상을동시에관찰할수있는도구로서, 마이크로어레이데이터는마이크로어레이실험에의해생성된이미지의분석, 유전자발현패턴의다양성연구등의새로운연구분야를제시하고있다. 현재이루어지고있는마이크로어레이데이터분석은, 새로운생물학적하위그룹이나클래스의발견을목적으로하는 Cluster analysis와이미알려져있는클래스로개체를분류하고자하는 Discriminant analysis로분류된다. 이와같은연구를통하여유전자의기능예측, 질병분류및진단, 유전자망 (gene network) 구성등에응용이기대되고있는데, 이가운데질병분류및진단에의응용은가장활발히연구가진행되는분야중하나로서, 특히암에걸린환자로부터얻은마이크로어레이데이터를사용함으로써암의종류에따라유전자가차별적으로발현되는양상을통계적으로분석하여분류에유용한유전자를식별하고정확한분류도구를구축하고자하는연구가이어지고있다. 데이터마이닝의입장에서바라본마이크로어레이데이터의전형적인특징은표본 (sample) 의개수에비해자질 (feature) 의개수가훨씬많다는점이다. 이것은일반적으로데이터마이닝이적용되는다른분야의데이터가대부분자질의개수보다표본의개수가많다는점과대조되는마이크로어레이데이터의두드러진특징이 - 4 -

5 다. 마이크로어레이데이터에있어서각각의유전자는데이터의속성 (attribute) 혹은자질에해당하며이들의개수는보통수천에이르는반면, 특정목적을위해제작되는마이크로어레이샘플은보통수십개에불과하다. 예를들어, 본논문에서도사용되는백혈병 (leukemia) 데이터는 7,072개의유전자와 72개의표본으로이루어진다. 결국, 마이크로어레이데이터의분석은수십개의표본과수천개의속성을가지는희소 (sparse) 데이터의분석이되는데, 희소데이터분석은과적합으로인해학습결과의신뢰도가낮다는단점이있다. 관련기술의발전에따라, 얻을수있는표본과유전자의둘다증가할것으로예상된다. 하지만현단계에서는많은유전자중에서분류에유의미한유전자들을선택할필요가있으며, 이를위해통계학이나정보이론에서의몇가지기준을비롯한다양한방법들이이용되어왔다. 본논문에서는분류에유용한자질을선택하기위한방법으로서유전알고리즘 (Genetic Algorithm) 과 k-nearest neighbor (knn) 을사용하는방법을제안한다. 유전알고리즘은자연도태의원리를기초로한최적화방법으로서탐색, 최적화및기계학습을위한도구로많이사용되며, k-nearest neighbor 기법은 non-parametric 패턴인식방법의하나로서많은연산을요구하지않지만좋은결과를보여준다. 유전알고리즘의적합도함수 (fitness function) 로서 knn을사용함으로써, 유전알고리즘이탐색에오랜시간이걸리는단점을 knn의짧은연산시간으로보충하는효과를기대할수있다. 분석대상이되는데이터는두개로서, 첫번째는급성백혈병데이터 [Golub et al., 1999] 이며두번째는 SRBCT(Small Round Blue Cell of Tumors) 데이터 [Khan et al, 2001] 이다. 첫번째로사용되는백혈병데이터는 2-클래스데이터로서, 실험에서는인자설정에따른결과를분석하고선정된유전자들의분류성능을평가한다. 특히, 다양한 k의값이결과에미치는영향을분석한다. 두번째실험에서사용되는 SRBCT 데이터는보다복잡한 4-클래스데이터로서, 4개의 2진분류문제로분할하여각각에서분류에유용한유전자집합을선정하고선정된유전자집합을 [Khan et al, 2001] 의결과와비교한다. 또선정된유전자들의유용성을검증하 - 5 -

6 고유전알고리즘이어떻게기여했는지평가한다. 논문의구성은다음과같다. 2장에서는마이크로어레이의개요와특징을소개하고, 응용분야중특히암분류와관련된기존의연구성과들을소개한다. 3장에서는유전알고리즘과 k nearest neighbor의개념과방법을설명한후, 본논문에서구체적으로어떻게응용되는지보여준다. 4장에서는두개의마이크로어레이데이터를대상으로실제로실험한결과를보이고분석한다. 그리고마지막으로 5장에서는결론을도출하고향후개선되어야할점을논의한다

7 2 장 관련연구 2.1 마이크로어레이개요 생명체의생명현상을조절하는것은세포내에존재하는 DNA(deoxyribo nucleotide acid) 라는물질이다. DNA는두개의사슬이이중나선 (double strand) 형태로결합되어있는데, 각사슬은 A(adenine), T(thymine), G(guanine), C(cytosine) 의 4 종류염기로구성된다. A-T, G-C는서로쌍으로결합하는성질을가지고있으며이에따라 2개의사슬이이중나선형태로붙어있게된다. DNA의길이와내용은생물에따라다르며, 인간의경우약 30억 bp(base pair) 로이루어져있다. DNA로부터전사 (transcription) 를거쳐 mrna가만들어지는데, mrna에들어있는단백질 (protein) 관련정보가번역 (translation) 과정에이용되어최종산물인단백질이만들어진다. 그리고단백질은생물체의생명현상을유지및조절하는각종역할을한다. 결국, 유전자는 DNA 사슬의일부분으로서, 최종산물인단백질생성에필요한정보를담고있다고할수있다. 유전자가 mrna 형태로나타나는현상을유전자발현 (gene expression) 이라한다. 유전자는항상발현되는것이아니라, 특정상황하에서필요한단백질을만들기위해발현된다. 또각유전자의발현은복잡한상호작용에의해지배되고있어서어느유전자의발현으로인해다른유전자의발현이촉진되거나억제할수도있다. 연구자들은이미 30 여종의유기생명체의 DNA 사슬 - 7 -

8 을완전히밝혀냈으며, 인간의 DNA 사슬역시인간유전체프로젝트 (Human Genome Project) 를통해거의해독된상태이다. 그러나, 아무리많은양의 DNA 정보를안다고해도, 그것만으로는유전자가무슨일을하는지, 세포가어떤역할을하고어떻게유기체를형성하며어떻게노화되는지등에대한해답을얻을수는없다. 따라서이와같이방대한양의 DNA 서열정보를의미있게이용하기위한기술이필요한데, 이를위해분자생물학지식과기계및전자공학기술이결합된것이 DNA 마이크로어레이 (microarray) 이다. DNA 마이크로어레이는 DNA 칩, 유전자칩, 바이오칩등이라고도부르며, 과거에 한번에유전자하나 만을조사하던것으로부터 동시에모든유전자 를조사할수있게해준비약적인기술발전이라고할수있다. 인간의유전자개수는약 30,000에서 60,000 정도로추정되는데, 현재기술로하나의칩위에 5,000에서 15,000개정도의유전자를심는것은쉬운일이다. 마이크로어레이기술의발전과이에대한관심이증가함에따라관련연구도급속도로활발해지고있는데, microarray 를검색하면 239,000개의웹페이지가검색되고있으며, Medline 에는 1,600 개이상의논문을찾을수있다. DNA 마이크로어레이는유리로만든수cm2정도의좁은칩표면에수천개이상의 probe 라고부르는유전자서열을고정시켜제작되며, cdna 칩과올리고 (oligonucleotide) 칩의두가지종류가있다. cdna 마이크로어레이는스탠포드대학에서개발되었는데, 두가지다른환경에서세포들로부터추출한 mrna를역전사 (reverse transcription) 시킬때두가지의형광물질을띤염기 (dutp) 를집어넣어빨간색 (Cy5) 이나녹색 (Cy3) 을띤 cdna를합성한다음, 합성된두개의 cdna를똑같은양으로섞어서하나의 cdna 마이크로어레이에결합 (hybridization) 시킨다. 결합반응이끝나면 cdna 마이크로어레이는스캐너에의하여읽혀지고그결과화상데이터를얻을수있는데, 이화상데이터는각유전자의형광정 - 8 -

9 도를담고있으므로이를컴퓨터해석소프트웨어를통해분석함으로써유전자의발현 (expression) 정도를수치화할수있다. 이렇게수치화된데이터를데이터마이닝기법을이용해분석함으로써유전자의기능과상호간의연결고리를추론할수있다. 그림 2.1은 cdna 마이크로어레이데이터를얻는과정을보여준다. < 그림 2.1> cdna 마이크로어레이를사용한유전자발현데이터얻기 또다른종류의 DNA 칩인올리고칩은 Affymetrix 사에서개발된것으로, 표본과 probe의결합반응을이용한다는기본원리는같지만 cdna 마이크로어레이와몇가지다른점이있다. 우선, cdna 마이크로어레이에서사용되는 probe는자연상태에서얻어지며길이가최소한 500bp(base pair) 이상인데반해, 올리고칩에서사용되는 probe는길이가 15~25 mer정도로길이가짧고인 - 9 -

10 공적으로제작된다. 좀더정확한진단을위해서는 probe의길이가긴것이유리하지만, 이경우이상결합 (cross-hybridization) 이일어날가능성도높아진다. 올리고칩의경우이상결합을줄이며감도를높이도록제작될수있다. 하지만, 실제유전자는보통몇 kb에이르기때문에이중에서어느부분의 15~25 개염기를선택하느냐가중요한문제가된다. 또, 정상적인염기서열로이루어진 PM(perfect match) probe와더불어, 이와염기서열하나가다른 MM(mismatch) probe가 probe pair를이루고있기때문에, 하나의염기변화에의한다양성 (SNP, single nucleotide polymorphisms) 을연구할수있다. 따라서한염기에생긴돌연변이 (point mutation) 를찾을수있는데, 많은암이나유전병들이특정유전자에생긴작은돌연변이에의해서유발되므로이것을이용하여지금까지밝혀진암관련유전자를가진올리고칩을만든다면한번의실험으로쉽게돌연변이를찾을수있다. 즉, cdna 마이크로어레이의경우에는전반적인유전자발현양상의연구에는쓰일수있지만환자의질병과연관된검사가불가능한반면, 올리고칩은유전적다형성을감지하여유전병을진단하고예측할수있으므로 Affymetrix 뿐만아니라 Corniing, Motorola, Samsung 등여러기업에서올리고칩을상업적으로판매중이거나혹은개발하기위한시도가진행중이다. 그림 2.2는올리고칩의모습을보여준다

11 < 그림 2.2> Affymetrix 사의 GeneChip TM DNA 마이크로어레이 결국, cdna 칩은전반적인유전자발현양상의연구에주로쓰이고환자의질병과연관된검사는어려운반면, 올리고칩은유전적다형성을감지하여유전병을진단하고예측할수있으므로 Affymetrix 이외에여러기업에서상업적으로판매중이거나혹은개발하기위한시도가진행중이다. 2.2 기존마이크로어레이기반암분류연구 현대적인암진단은종양의해부학적발생위치를정확히결정하는데서출발한다. 일반적으로병리학자들은현미경이나유전적, 면역적기법을활용하여발생부위에적합한진단을한다. 하지만이런방법들은여러종양사이의형태학적유사성으로인해후행적인진단이될수있다. 형태적으로동일해보이는암이라도어떤경우는아주빨리발전되어서매우공격적인치료가필요한반

12 면, 진행이매우느려서심지어치료를하지않는것이가장좋은방법인경우도있다. 분자생물학을이용한암분류는이런어려움을해결할수있는잠재력을지니고있다. 여기서문제는, 특정암을식별할수있는유전적인표지 (genetic marker) 를알아내고이를이용해서암을정확히분류하는것이다. DNA 칩을사용한유전자발현분석기술은암분류에응용되기에유망한기술로서, 동일한종류의암은그종류마다의고유한발현양상패턴이있다는가정을전제로한다. 경우에따라서는이를통해서지금까지알려지지않았던새로운종류의종양이발견되기도한다. 마이크로어레이데이터를이용한암분류연구는크게클래스발견 (class discovery) 과클래스예측 (class prediction) 의두가지가있는데, 두방법의차이는표 2.1과같다. 클래스발견 아직까지알려지지않은새로운 종류의암을발견하는것이목 클래스예측 표본을이미알려져있는클래스 로정확히지정하는것이목적 적 계층적클러스터링 (hierarchical clustering) SOM(Self Organizing Map) k-means clustering 사전지식이이용되지않는다 ANN(Artificial neural network) SVM(Support vector machine) Discriminant analysis k-nearest Neighbor 미리정의되어있는클래스에기 초하여표본을분류 < 표 2.1> 클래스발견 vs. 클래스예측

13 계층적클러스터링 (hierarchical clustering)[alon et al., 1999; Alizadeh et al., 2000; Bendor et al., 1999; Hartuv et al., 2000; Ross et al., 2000] 은비슷한양상을보이는유전자혹은표본을묶는것으로초기마이크로어레이데이터분석에서가장많이이용되던방법이다. [Alizadeh et al, 2000] 은림프종데이터의유전자발현연구에계층적클러스터링을사용하였으며, [Ross et al., 2000] 역시계층적클러스터링을사용하여 10 클래스 NCI60 cell line 데이터의유전자발현양상을관찰하였다. [Golub et al., 1999] 은백혈병데이터에대해 SOM 분석과더불어 weighted voting이라는일종의선형 discriminant analysis를수행하였다. [Khan et al., 2001] 은 4-클래스 SRBCT 데이터에대해 PCA(Principal Component Analysis) 을사용하여 dimension reduction을수행한후 3,750개의선형 ANN 모델을구축하여그투표결과를통해 23개의테스트표본을정확히분류할수있음을보였다. 그리고, SVM(Support Vector Machine)[Bendor et al., 2000; Yeang et al., 2001] 은 dimesion reduction 없이도좋은분류성능을보여주고있으나, 기본적으로 2진분류자이므로직접다중클래스분류를할수없다는문제가있다. 이에 [Yeang et al., 2001] 은 SVM, k-nearest Neighbor, Weighted Voting을사용해서 GCM 데이터를분석하면서, 2진클래스분류자를두가지방법으로결합하여 14-클래스데이터를분류하였다. SVM이가장좋은성능을보여주고있으나, 2진클래스문제에비해분류성능이떨어지며 marker gene을선택하지못하는것으로나타나고있다

14 2.3 마이크로어레이데이터의특징 화상데이터를컴퓨터소프트웨어를통해해석하여얻은유전자발현데이터의전형적인모습은표 2.1과같다. sample1 sample2 sample3 sample4 sample < 표 2.2> 행렬로나타낸유전자발현데이터 마이크로어레이표본의유전자발현데이터는 n개의종양표본과 p개의유전자에대해서 n * p 행렬인 X=(x ij ) 로표시할수있다.(x ij 는표본 i에서유전자 j의발현정도 ). 표본이어떤클래스에속하는지이미알고있다면, 표본데이터는유전자발현프로파일 x i =(x i1, x ip ) 과클래스레이블 y i 로이루어진다. 종양클래스가 K 개일때, 클래스레이블 y i 는 1부터 K 사이의정수로정의된다. 이때 x ij 는일반적으로 raw 데이터가아니라이미지분석과정규화, 필터링등의사전처리 (preprocessing) 를거친데이터이다. 이때, 표본의개수인 n은보통 100 미만인데비해, 유전자의개수인 p는수천개에이른다. 이와같이표본의수에비해훨씬많은유전자중에서클래스구별에관련되는유전자를선택하는것은암분류자의성능을높이

15 기위해서뿐만아니라, 그자체로서도큰의미가있다. [Golub et al., 1999] 은백혈병마이크로어레이데이터를분류하면서, marker gene이가져야할두가지기준을가정했다. 첫째로, 유전자가분류에유용하기위해서는어떤클래스에서의발현정도가다른클래스에서의발현정도와크게달라야하며, 두번째로같은클래스내에서는발현정도의변화가적고값이고르게유지되어야한다. 이를그림으로설명하면그림 2.3과같다. < 그림 2.3> 서로다른클래스에서유전자의발현정도예시 그림 2.3은어느유전자가 class 1 표본과 class 2 표본에서갖는발현되는정도를세가지경우로나타낸것이다. 왼쪽의그림을보면, 이유전자는 class 1에서와 class 2에서평균적으로발현정도가거의비슷하다. 따라서 class 1과 class 2를구별하는데유용하다고말할수없다. 오른쪽의그림에서는 class 1과 class 2에서평균적인발현정도가크게차이가난다. 하지만, class 1과 class 2 각각에속하는표본들에서발현정도가들쭉날쭉하며꾸준하지않다. 따라서역시 class1과 class2를구별하는데유용하지않다. 반면에, 가운데그림에서는 class 1과 class 2에서평균적인발현정도가차이가나면서동시에각 class 내에서발현정도가고르게유지되고있다. 결국, 가운데경우와같은발현정도를보이는유전자가 class 1과 class 2를구별하는데유용할것이라고가정할수있다. 이는다시말해서각 class 에서의평균값의차이는크면

16 서동시에표준편차의합은작을수록유리하는뜻이다. [Golub et al, 1999] 은이를 [1] 로나타내고 signal-to-noise 라고명명했다. Signal-to-noise = (µ 1 - µ 2 ) / (σ 1 + σ 2 ) [1] [µ i = class i에서해당유전자의발현정도의평균, σ i = class i에서해당유전자의발현정도의표준편차 ] 하지만이와같이분류에유용한유전자집합을선택하는방법의문제점은암발생의원인을단일유전자단위로만고려한다는점이다. 생물학자들에따르면유전자의발현메커니즘은매우복잡해서, 단독으로는큰의미를갖지못하는유전자라할지라도다른유전자와상호작용을통해함께발현됨으로써암을일으키는중요원인이될수있다. 이와같이둘이상의유전자가한단위로작용하는경우를그림으로나타내면그림 2.4와같다. < 그림 2.4> 두개의유전자가한단위로작용하는경우 그림 2.4에서원과삼각형은서로다른클래스를가리킨다. Gene 1과 Gene 2는단독으로는원클래스에속하는데이터와삼각형클래스에속하는데이터를구별하지못하지만, Gene 1과 Gene

17 를한단위로간주하면구별할수있다. 또, 아직알려지지않은하위클래스가존재할수도있다. 현재까지알려져있는암분류체계는완벽하지않아서, 아직생물학적으로알려지지않은암이존재할수있다. 특히암세포의발전단계에따라특정유전자의발현양상이크게달라지기도한다. 그림 2.5를보자. < 그림 2.5> 하위클래스가존재하는경우 그림 2.5에서원클래스는두개의하위클래스를갖고있다. 이때개별유전자단위로중요도를계산하는통계적방법을사용하여유전자를선택하면, 하위클래스에따라서중요도가크게차이가나서상위클래스전체적으로는중요도가높지않게나타날수있다

18 3 장 암분류를위한유전자집합선정방법 3.1 Genetic Algorithm (GA) 유전알고리즘 (Genetic Algorithm, GA) 은자연세계의진화과정을컴퓨터상에서시뮬레이션함으로써복잡한실세계의문제를해결하고자하는계산모델인진화알고리즘 (evolutionary algorithms) 의한분야이다. 진화알고리즘은염색체를표현하는방법과사용되는유전연산자의종류및특성에따라서여러가지모델로구분되는데, 유전알고리즘과진화전략 (evolution strategy, ES) 에서는고정된길이의이진스트링이나실수의값으로구성된벡터를염색체로사용하는반면, 진화프로그래밍 (evolutionary programming, EP) 과유전프로그래밍 (genetic programming, GP) 에서는그래프와트리로염색체를표현한다. 그리고, EP와 ES는돌연변이 (mutation), GA 와 GP는교차 (crossover) 연산자를주로사용한다. 역사적으로 EP, ES, GA 는 1960 연대와 70년대에개발되었으며 GP 는 90 연대에들어와연구되기시작하였다. GA는 1975년에 John Holland가저서 "Adaptation on Natural and Artificial Systems" 에서처음소개하여이론적기반을다졌으며자연도태의원리를기초로한최적화방법으로서탐색, 최적화및기계학습을위한도구로많이사용한다. 그렇다면진화알고리즘에서이용되는진화와유전의원리는무엇인지간단히논의하자

19 생물은세포로구성되고세포에는핵이있으며그핵에는염색체 (chromosome) 가들어있다. 염색체는주로 DNA로구성되는데, 이 DNA는 4종류의염기라고부르는화학물질이이루는구성방법에따라서로다른정보를담고있다. DNA는 2중나선구조로되어있으며, 이들이복잡하게겹쳐져서염색체를구성하고있다. 유전자 (gene) 란유전정보를담당하는 DNA로서, 특정의유전자는염색체의특정위치에존재한다. 결국유전정보는염색체상에서의위치 ( 유전자위치 ) 와염기의배열에의해표현되는것이다 부모로부터유전자에의해생물로서의정보가다음세대에전달될때, 보다우수한즉, 환경에적응도가높은개체의유전정보가우선적으로전해진다. 반대로적응도가낮은개체는자연도태되어간다. 이러한원리에기초하여세대를거듭해가면차례로환경에적응도가높은개체가많아진다. 이것이유전과진화의기본적인원리이다. GA에서는풀고자하는문제에대한가능한해들을정해진형태의자료구조로표현하는데이를염색체, 혹은개체 (indivisual) 라고부른다. 그리고정해진수의염색체집단을운영하는데이집단을개체군 (population) 이라한다. 염색체상의각인자는유전자라고부른다. 생물학에서는많은수의염기가모여유전자를형성하지만, GA에서는유전자가최소단위가된다. GA에서사용되는기본적인연산자는선택 (selection), 교차 (crossover), 변이 (mutation) 의 3가지이다. 선택은교차를할해를해집단에서선택하는연산자로서이때선택된해를부모해 (parent) 라고한다. 교차는두개의부모해로부터자식해 (offspring) 를만들어내는연산자로서, 부모해에있는우수한속성을자식해에전달하고자하는것이목표이다. 반면에변이는해를임의로변형시키는연산자로서부모해에없는속성을도입하여해의다양성을높이는것이목표이다. [ 문병로, 유전알고리즘, 2001]

20 3.2 k-nearest Neighbor k-nearest Neighbor 분류자는표본의분포상태에영향을받지않는 non-parametric 학습방법의하나로서, 모든표본이 n-차원공간 R n 상의점들로대응된다고가정한다. 표본 x의자질벡터를 <a 1 (x), a 2 (x),, a n (x)> 로표현하면, 두표본 x i 와 xj 사이의거리 d(x i,xj) 는유클리드거리 (Euclidean distance) 일때다음과같이나타낼수있다. d(x i,xj) = n 2 (a r (xi) - a r (x j)) [2] r = 1 이산값 (discreted-value) 을갖는목적함수 (target function) 를 f : R n V, V={v 1, v2,, v n } 라고할때, 분류되어야할질의인스턴 스 x 의클래스 x ) 를다음과같이정한다. q f ( q v V k f ( x ) arg max δ ( v, f ( xi)) [3] q i= 1 ( a = b 이면 δ ( a, b) = 1, 그렇지않으면 δ ( a, b) = 0 ) 즉, n-차원공간에서자신과가장가깝게위치하는 k개의다른표본들의클래스중에서가장많은것으로분류되는것이 k-nearest Neighbor 알고리즘이다

21 3.3 GA/kNN 알고리즘 GA/kNN 유전자선정방법은 GA와 k-nearest Neighbor를이용한유전자선정방법으로서 [Li et al., 2001] 이제안하였으며본논문에서는이를다소단순화하여구현하였다. 본논문에서 GA/kNN 방법을사용하여분류자를구축하는방법은그림 3.1과같다. (1) Initialize 50 chromosomes consisting of d genes (2) For each chromosome, assign its fitness ( fitness = the number of samples correctly classified b (3) select a chromosome randomly (4) mutate one gene in the chromosome randomly (5-2) replecement (5) Is criterion met? no yes (5-1) Save the chromosome 그림 3.1. 근사해집합을얻는과정

22 그림 3.1 의과정을순서대로설명하면다음과같다. (1) d개의유전자로이루어진염색체 50개를임의로생성한다 (d 개의유전자각각에들어가는값은마이크로어레이데이터의유전자인덱스이다 ). (2) 각염색체의적합도를다음과같이계산한다 (a) 훈련데이터에속하는모든표본쌍에대하여, d 차원상에서두표본사이의유클리드거리를계산한다. (b) 각표본에대하여 a) 에서계산한거리에따라 k개의가장가까운이웃표본들을얻는다. 그리고, 이웃표본들의클래스중에서가장수가많은클래스와, 표본의실제클래스가일치하는표본의수가해당염색체의적합도가된다. (3) 위와같이모든염색체에대해적합도를계산한다음, 염색체들가운데하나를임의로선택한다. (4) 선택된염색체내의유전자 1개를염색체내에들어있지않은유전자로변이시킨다 ( 교차연산자는사용되지않는다 ). (5) 변이된염색체에대하여 knn 적합도를계산한다. (5-1) 그값이임계값이상이면분석대상염색체로서저장하고 (1) 로돌아가서다시시작한다. (5-2) 그렇지않으면기존염색체들가운데적합도가가장낮은것과교체하고, 염색체를임의로하나선택하는단계로돌아가서임계값이상인염색체를얻을때까지반복한다. 결국 GA/kNN은 knn을적합도함수 (fitness function) 로사용하는 GA라고볼수있다. (1)-(5) 의과정을반복해서근사해 (near

23 optimal solutions) 들을충분한개수만큼얻은뒤, 각유전자인덱스가나타나는빈도수를계산하여그값이높을수록그유전자를분류에유용한유전자로간주한다. 전체과정을그림으로나타내면그림 2와같다

24 4 장 유전알고리즘을이용한마이크로어레이 데이터분류 4.1 실험 1 급성백혈병데이터 데이터및실험방법 첫번째로사용된마이크로어레이데이터는급성백혈병 (acute leukemia) 데이터이다 [Golub et al.,1999]. 이데이터는 72개의표본으로구성되어있으며이중 25개는 AML(acute myeloid leukemia), 나머지 47개는 ALL(acute lymphoblastic leukemia) 로나누어진다. 전체표본중골수 (bone marrow) 에서추출된 38개의표본 (AML 11개, ALL 27개 ) 은모델학습및유전자선정을위한 training set으로사용되며, 골수와말초혈액 (peripheral blood) 에서추출된나머지 34개의표본 (AML 14개, ALL 20개 ) 은학습된모델및선정된유전자의성능평가를위한 test set으로사용된다. 각표본은올리고칩으로측정된 7,129개유전자의발현도로구성되어있는데, [Li et al., 2002] 과같은방법으로필터링을수행하여전체유전자중 72개샘플의 80% 이상에서발현도 (expression level) 가 50 미만인유전자를제거하여유전자의개수를 5,455개로줄인다음, 발현도를밑이 10인로그값으로변환하여실험을수행하였다

25 4.1.2 실험결과하나의개체군은 50개의염색체로구성하였다. k-nearest neighbor에서 k의값을 3, 5, 7로, d의값은 10, 40, 70, 100로변화시키며실험을하였으며, 각경우에서 6,000 개의근사해 (near-optimal) 염색체집합을얻었다. k = 3, 5, 7인경우의유전자선정결과를비교하기위해 5,455개의유전자각각이선정된빈도수를계산한결과가그림 4.1이다 (d = 40인경우 ). < 그림 4.1> k 값의변화에따른각유전자의선택확률

26 그림 4.1을보면 k = 7인경우에선정된유전자들은 k = 3, 5인경우와상당히다름을알수있다. 이를좀더명확히나타내기위해산포도를그려보면그림 4.2와같다. < 그림4.2> k값에따른각유전자의선정빈도수의비교산포도. 맨위의그래프는 k=3 vs. k=5의비교이며가운데는 k=3 vs. k=7, 맨아래는 k=5 vs. k=7인경우이다

27 그림 4.2를보면, k = 3 vs. k =5인경우는 y = x와유사한모습을보이며이는선정된유전자집합이비슷함을의미한다. 반면에 k = 3 vs. k =5와 k = 5 vs. k = 7의경우는상당히다른그래프형태를보이는것을알수있다. 이는 knn에서 k = 7인경우 k = 3이나 k = 5인경우와는다른유전자들이많이선정되었다는의미이다. 선정된유전자의집합이달라짐에따른분류성능을알아보기위해서, 학습에이용되지않은 34개의테스트집합표본에대한분류성능을비교해보았다. 각인자의설정에따른성능의차이는표 4.1에정리되어있다. 분류는각경우에선정된 50개의우수유전자를이용해서행해졌다. k Con Maj Con Maj Con Maj d < 표 4.1> k 와 d 값에따른테스트데이터에대한분류성능비교

28 표 4.1을보면, majority rule을사용하는경우 d = 10인경우를제외하고모두 33/34의성능을보인다. 이것은 [Li et al.2002] 을비롯하여이실험과동일한백혈병데이터를분석한논문들에서보이는최대성능과동일하다. d = 10에서성능이제대로나오지않은것은, 정확한분류를위해필요한유전자의개수가적어도 10개가넘는다는것을강하게시사한다. consensus rule을사용하는경우는 k = 3일때가장좋고, k = 7일때가장나쁜것을볼수있는데차이가두드러지는것은표본의개수가 34개로서그다지많지않기때문일가능성이높다. 또다른가능성으로는, 앞에서본 k 값에따른유전자선정결과에서 k =7일때상당히다른결과가나온것으로부터 k =7에서선정결과의품질이좋지않았을수도있다. 향후보다크기가큰데이터집합으로실험을수행한다면, 둘중어느요인이더큰영향을미치는지알수있을것이다. consensus rule을사용했을때가장좋은성능은 k = 3, d = 40의 32/34인데, 이는 [Li et al., 2002] 에서선정한유전자집합을사용하여마찬가지로 consensus rule에따라계산할경우의성능 31/34보다더좋은결과라고할수있다 ([Li et al., 2002] 에서는 consensus rule에따른성능을보여주지않고있다 )

29 4.2 실험 2 SRBCT 데이터 데이터및실험방법 SRBCT(Small Round Blue Cell Tumors) 는아이들에게흔한악성종양으로서약 80% 가 20대이하에서발병한다. NB(neuroblasoma), RMS(rhabdomyosarcoma), BL(Burkitt s lymphoma), EWS(Ewing s family of tumors) 의 4 종류가있는데, 현미경을사용해서는정확히분류할수가없다. 최근에 [Khan et al.] 은 PCA(Principal Component Analysis) 와 ANN(Artificial Neural Network) 을이용해서 SRBCT 표본의 cdna 마이크로어레이데이터를분류하였다. 실험 2에서는 [Khan et al.] 이사용한것과같은마이크로어레이데이터에대하여실험 1과유사한방법을사용하여, 분류에유용한유전자집합을선정하고비교해본다. 데이터집합은 에서다운로드했다. 이데이터는 2308개의유전자와 88개의표본으로이루어지는데, 표본들은다시 63개의 training set(23 EWS, 8 BL, 12 NB, 21 RMS) 과 25개의 test set(6 EWS, 3 BL, 6 NB, 5 RMS, 5 non-srbct) 으로나누어진다. SRBCT 데이터는실험 1에서사용된급성백혈병데이터와달리다중클래스 (multi-class) 데이터이므로, EWS, BL, NB, RMS 각각의클래스에대해실험을수행하였다. 즉, GA/kNN 알고리즘을 4 개의클래스각각에대해적용하여, 훈련데이터로부터각클래스의 marker gene을선택하고이를사용해서테스트데이터를예측함으로써선택된유전자의유용성을검증한다. 예를들어, EWS 클

30 래스의 marker gene을얻으려면, EWS vs. non-ews로표본을구분한다음 GA/kNN으로충분한근사해염색체집합을얻고, 이해들로부터유전자의빈도수를계산하여 EWS를위한 marker gene을얻는다. 그리고이와같은실험을각클래스에대해반복해서수행하였다. 각클래스를위한 GA/kNN 실험에서, 염색체의개수는 50개, 각염색체에포함되는유전자의개수는 40개로하였으며, k nearest neighbor의 k는 5로고정하였다. 이값들은모두실험 1에서좋은결과를냈기때문에실험 2에서채용되었다. 그리고염색체를분석대상으로저장하기위한임계값은 62이다. 즉, 전체 63개의훈련데이터중 62개이상정확히분류한염색체는분석대상으로서저장되었으며, 각각 10,000개의염색체를근사해로서얻었다 실험결과 각실험에서얻은근사해로부터빈도수상위유전자를얻은다음, 이상위유전자들을이용하여 25개의테스트표본을정확히분류한수는표 4.2와같다. 분류에사용된상위유전자수 EWS NB BL RMS 표 4.2. SRBCT 테스트표본분류결과

31 표 4.2에서테스트표본을 100% 정확히분류하는데필요한빈도수상위유전자의수는 EWS, NB, BL, RMS에서각각 40, 5, 5, 10 개이다. 이유전자들중에중복되는것을제외하고남는 47개의유전자들을사용해서계층적클러스터링으로 88개의표본전체를묶은결과는그림 4와같다. < 그림 4.3> 표본을대상으로한계층적클러스터링 dendogram. 클래스가표기되지않은표본은 non-srbct 표본. 그림 4를보면 88개의표본이모두클래스별로정확히인접하게위치하는것을볼수있다. 본실험에서선정된 47개의유전자집합중에 [Khan et al.] 이선정한 96개의중요유전자와공통되는 21개의유전자는다음과같다

32 ID 이름 클래스 PTPRF BL FCGRT EWS/RMS FVT1 EWS.RMS CAV1 EWS/RMS PTPN13 EWS TNFAIP6 EWS GYG2 EWS NOE1 EWS TLE2 EWS IGF2 EWS FGFR4 EWS/RMS EST EWS EST EWS REG1A EWS DPYSL2 EWS/RMS IGF2 EWS/RMS MYL4 EWS TNNT2 EWS TNNT1 EWS AF1Q NB MAP1B NB GAS1 NB GAP43 NB MIC2 RMS < 표 4.3> GA/kNN 과 [Khan et al.] 에서공통으로선택된유전자집합

33 5 장 결론및향후연구과제 최근다양한데이터마이닝기법들이마이크로어레이를사용한유전자발현데이터기반의암분류에적용되고있다. 이때, 분류에유용한유전자를미리선택할것인가의여부가중요한문제가된다. 유전자전부를사용해서더나은분류결과를얻는경우도있으나 [Yeang et al., 2001], 모든유전자가특정클래스의분류와관련이있을것이라고생각하기는어렵다. 각클래스를분류하는데유용한유전자집합을알아내는것은그자체로서생물학적의미가있을뿐아니라, 분류성능을높이는데도기여할수있을것으로기대되고있다. 암유전자발현데이터로부터유용한유전자를선택하는데있어서의어려움은암데이터에숨겨진하위클래스가존재할수있다는점이다. 예를들어실험 1에서사용된백혈병데이터의경우 ALL 클래스는실제로는다시 T-Cell ALL과 B-Cell ALL의하위클래스로나누어진다. 어떤유전자가하위클래스에따라서발현정도가크게다르다면, 발현정도에기반한유전자선택방법으로는이유전자를선택할수없을것이다. 본논문에서사용된 GA/kNN은개별적인유전자발현정도에의존하지않으며, 유전자집합이집단적으로발현되는경우를고려한방법이라고할수있다. 실험 1의경우는 knn에서 k값의변화가분류성능에미치는영향을살펴보았다. K가 3이나 5일때에비해서 7인경우는선택되는유전자집합이크게상이한것을볼수있다. 이는훈련표본의개수가 38개에불과하기때문이라고

34 보이는데, 마이크로어레이유전자발현데이터에서표본의개수는전형적으로수십개에불과하므로 k값이크면 noise가들어가기쉬워진다. 표 2에서테스트데이터에 majority rule을사용하는경우 d = 10인경우를제외하고모두 33/34의성능을보이는데, 이것은동일한백혈병데이터를분석한논문들에서보이는최대성능과동일하다. d = 10에서분류정확도가떨어지는것은, 정확한분류를위해필요한유전자의개수가적어도 10개가넘는다는것을강하게시사한다. 테스트데이터분류에있어서 consensus rule 적용시 k가 7일때분류성능이나쁜것은상위유전자집합을얻을때들어간 noise가원인이라고생각된다. 따라서 k의값은 3이나 5정도가적절한것으로판단된다. 실험 2에서다룬 SRBCT 데이터는다중클래스데이터였다. [Khan et al.] 은다중클래스데이터를다루기위해서인공신경망을이용하였으나, 본실험에서는각클래스단위로 GA/kNN을수행해서분류에유용한유전자집합을선택하고빈도수상위유전자들을얻었다. 이렇게얻은각각의 4개의상위유전자집합은해당클래스를다른클래스들과구별하기에유용한유전자들이다. 테스트데이터를 4개의유전자집합각각에적용시킴으로써어느클래스에속하는지분류한결과가표3이다. MIC2 유전자는 EWS 진단에이용되고있지만 RMS에서도발현되기때문에단독으로의존할수는없다고알려져있는유전자인데, [Khan et al.] 에서 EWS로분류된것에반해본실험에서는 RMS 관련유전자로선택되었다. 표 3에서 EWS와 RMS 둘다와관련있는유전자가 6개보이는데, [Khan et al.] 에서는이중에서 FGFR4는 RMS 관련유전자로분류되었고나머지 5개는 EWS에관련된것으로분류되었다. 또, 공통유전자가아닌것들중에서도본실험에서는 EWS로선정된것이 [Khan et al.] 에서는 RMS로선정된것들이다수있다. 이로미루어 EWS와 RMS 클래스가밀접히연관되어있을지모른다는가정을할수있다. 본논문에서는 GA/kNN 방법을사용하여두개의마이크로어레이암데이터에대해서유전자선택을수행하였다. 특히두번째실험에서선택된 47개의유전자집합은 88개의표본전체를 4개의클래스로정확히클러스터링하면서테스트데이터도정확히분류

35 하고있는데, 이는 [Khan et al.] 에서 96개를사용한것보다더적은개수이다. 각클래스의 marger gene의개수가몇개인것이적절한지에대한일반적규칙은존재하지않는다. 적은수의유전자를사용한다고해서반드시저정확한암분류가가능하다고일반화할수는없다. 하지만생물학적으로더의미있을가능성이높은것은사실이며, 생화학적방법으로추가로검증하기위한좋은후보가될수있다. 이런의미에서 GA/kNN을사용한유전자선택방법은효용성이있다고결론내릴수있다

36 참고문헌 [ 문병로, 1991] 문병로, 유전알고리즘. Alizadeh, A.A., Eisen, M.B., Davis, R.E., Ma, C., Lossos, I.S., Rosenwald, A., Boldrick, J.C., Sabet, H., Tran, T., Yu, X., Powell, J.I., Yang, L., Marti, G.E., Moore, T., Hudson, J.Jr, Lu, L., Lewis, D.B., Tibshirani, R., Sherlock, G., Chan, W.C., Greiner, T.C., Weisenburger, D.D., Armitage, J.O., Warnke, R., Levy, R., Wilson, E., Grever, M.R., Byrd, J.C., Botstein, D. Brown, P.O., and Staudt, L.M., Distinct types of diffuse large B-cell lymphoma identified by gene expression profiling, Nature, vol. 403, pp , Alon, U., Barkai, N., Notterman, D.A., Gish, K., Ybarra, S., Mack, D., and Levine, A.J., Broad patterns of gene expression revealed by clustering analysis of tumor and normal colon tissues probed by oligonucleotide arrays, Proceedings of the National Academy of Sciences of the United State of America, vol. 96, p , 1999 Ben-Dor, A., Shamir, R. and Yahkini, Z., Clustering gene expression patterns, J.Comput.Biol., vol. 6, p , Ben-Dor, A., Bruhn, L., Friedman, N., Nachman, I., Schummer, M., and Yakhini, Z., Tissue classification with gene expression profiles, Journal of Computational Biology, vol. 7, no. 3/4, pp , Evertsz, E., Starink, P., Gupta, R., and Watson, D., Technology and applications of gene expression microarrays, Schena, M. (ed.), Microarray Biochip Technology, Eaton Publishing, MA, pp

37 , 2000 Eisen, M.B., Spellman, P.T., Brown, P.O., and Botstein, D., Cluster analysis and display of genome-wide expression patterns, Proceedings of the National Academy of Sciences of the United States of America, vol. 95, no. 25, pp , 1998 Golub, T.R., Slonim, D.K., Tamayo, P., Huard, C., Gaasenbeek, M., Mesirov, J.P., Coller, H., Loh, M.L., Downing, J.R., Caligiuri, M.A., Bloomfield, C.D., and Lander, E.S., Molecular classification of cancer: class discovery and class prediction by gene expression monitoring, Science, vol. 286, no. 5439, pp , 1999 Hartuv, E., Schmitt, A.O., Lange, J., Meier-Ewert, S., Lehrach, H. and Shmir, R., An algorithm for clustering cdna fingerprints, Genomics, vol.66, p , Khan, J., Wei, J.S., Ringnér, M., Saal, L.H., Ladanyi, M., Westermann, F., Berthold, F., Schwab, M., Antonescu, C.R., Peterson, C., and Meltzer, P.S., Classification and diagnostic prediction of cancers using gene expression profiling and artificial neural networks, Nature Medicine, vol. 7, no. 6, pp , 2001 Li, L., Pedersen, L.G., Darden, T.A., and Weinberg, C.R., Computational analysis of leukemia microarray expression data using the GA/KNN method, Lin, S.M. and Johnson, K.F. (eds.), Methods of Microarray Data Analysis (Proceedings of CAMDA 00), Kluwer Academic Publishers, MA, pp ,

38 Ross, D.T., Scerf, U., Eisen, M.B., Perou, C.M., Rees, C., Spellman, P., Iyer, V., Jeffrey, S.S., Van de Rijn, M., Waltham, M., Systematic Variation in Gene Expression Patterns in Human Cancer Cell Lines, Nature Genet, Vol.24, pp , 2000 Spellman, P.T., Sherlock, G., Zhang, M.Q., Iyer, V.R., Anders, K., Eisen, M.B., Brown, P.O., Botstein, D., and Futcher, B., Comprehensive identification of cell cycle-regulated genes of the yeast Saccharomyces cerevisiae by microarray hybridization, Molecular Biology of the Cell, vol. 9, no. 12, pp , Warrington, J.A., Dee, S., and Trulson, M., Large-scale genomic analysis using Affymetrix GeneChip probe arrays, Schena, M. (ed.), Microarray Biochip Technology, Eaton Publishing, MA, pp , Yeang, C., Ramaswamy, S., Tamayo, P., Mukerjee, S., Rifkin R.M., Angelo, M., Reich M., Lander, E.,Mesirov, J., Golub, T.R., Molecular classification of multiple tumor types, Bioinformatics, Vol.1, no.1, 2001 Li, L., Pedersen, L.G., Darden, T.A., and Weinberg, C.R., Computational analysis of leukemia microarray expression data using the GA/KNN method, Lin, S.M. and Johnson, K.F. (eds.), Methods of Microarray Data Analysis (Proceedings of CAMDA 00), Kluwer Academic Publishers, MA, pp ,

39 Abstract DNA Microarray, a recent biotechnology, is expected to contribute to correct classification of cancer types. One difficulty in microarray data analysis is data sparseness, i.e., that the number of samples is small while the number of features (i.e., genes) is large. Existing methods for feature selection usually compute each gene s variation in expression level across samples, but the problem in these methods is that they do not consider the interaction between genes, and that there can be such genes relevant for discrimination jointly with other genes. In this paper, we use genetic algorithm (GA) and k-nearest neighbor (knn) to obtain near-optimal solutions for leukemia and SRBCT microarray data, and then marker genes are deduced by each gene s appearance frequency in the nearoptimal solutions. The results of applying knn in this marker genes dimension show high classification performance. GAbased marker gene selection methods could contribute to the correct classification of cancer types, and could be used as a preprocesser to cluster analysis as well as stand-alone analysis. Keywords : Microarray, Cancer Classification, Genetic Algorithms Student ID :

40 감사의글 석사과정에입학한지어언 5년반, 마침내석사졸업을하게되니감회가새롭습니다. 언제나지나고나면세월의흐름이빠르다고느껴지는법이지만, 한학기를마친후대한민국남자로서피할수없는병역의의무를수행하고다시복학하여석사를마치게된지난 5년반은특히시간이너무나빨리흐른것같습니다. 바이오지능연구실의수많은가족을책임지고계시면서도저에게많은가르침을베풀어주신장병탁교수님께우선감사의말씀을드립니다. 그리고저를자연언어처리연구실의석사생으로받아주셨던김영택교수님께도감사드립니다. 석사초년시절저에게많은조언을주셨던유섭이형과성동이형, 속좁은저에게언제나개방적이고넓은마음으로대해준종우형, 맡은일에언제나성실하고진지하게임하는모범을보이는정호형, 일에엄격하고구분이확실한성배형에게진심으로감사의말을하고싶습니다. 석사선배임에도불구하고같은학부동기로서허물없이수많은도움을준규백이, 장민이가아니었으면결코졸업을할수없었을것입니다. 언제나학자다운풍모를보이시는양박사님, 멋쟁이오박사님, 정말로사람좋은제균이형, 학부의궂은일을맡으며저에게도많은도움을준선이형, 이런저런질문에귀찮아하지않고도와줬던동연이, 수용이, 여러가지컴퓨터제품에풍부한지식으로도와준재홍이, 일과취미모두확실히하는승준이, 이미졸업해서직장생활에바쁜승우, 예쁜여자후배들인인희와호진, 석사동기생인상준이와하영이, 그리고 419호실분위기메이커였던유지선씨, 이모든분들덕분에굴러넘어지지않고오늘까지올수있었다고생각합니다. 그리고, 제가힘들때여러가지조언을아끼지않았던창배형과고등학교동기석훈이에게도고마움의말을빠뜨릴수없습니다. 누구보다도제멋대로고고집이센저를지금까지사랑으로지켜봐주시는아버지, 어머니, 동생, 모두사랑합니다. 학교를졸업하고사회에나가도이모든분들과의추억과받은사랑은앞으로도제인생의든든한버팀목이될것입니다. 마지막으로정말감사합니다