DBPIA-NURIMEDIA

Size: px

Start display at page:

Download "DBPIA-NURIMEDIA"

시영 아
6 years ago
Views:

1 46 정보과학회논문지 : 데이타베이스제 34 권제 1 호 (2007.2) 2 단계접근법을통한통합마이크로어레이데이타의분류기생성 (Building a Classifier for Integrated Microarray Datasets through Two-Stage Approach) 윤영미 이종찬 박상현 (Youngmi Yoon) (Jongchan Lee) (Sanghyun Park) 요약마이크로어레이데이타는동시에수만개유전자의발현값을포함하고있기때문에질병의발현형질분류에매우유용하게쓰인다. 그러나동일한생물학적주제라할지라도여러독립된연구집단에서생성된마이크로어레이의분석결과는서로다르게나타날수있다. 이에대한주된이유는하나의마이크로어레이실험에참여한샘플의수가제한적이기때문이다. 따라서개별적으로수행된마이크로어레이데이타를통합하여샘플의수를늘리는것은, 보다정확한분석을하는데있어매우중요하다. 본연구에서는이에대한해결방안으로두단계접근방법을제안한다. 제 1 단계에서는개별적으로생성된동일주제의마이크로어레이데이타를통합한후인포머티브 (Informative) 유전자를추출하고제 2 단계에서는인포머티브유전자만을이용하여클래스분류 (Classification) 과정후분류자를추출한다. 이분류자를다른테스트샘플데이타에적용한실험결과를보면마이크로어레이데이타를통합하여샘플의수를증가시킬수록, 비교방법에비해정확도가최대 24.19% 높은분류자를만들어내는것을알수있다. 키워드 : 바이오인포마틱스, 마이크로어레이데이타분석, 마이크로어레이데이타통합, 클래스분류자찾기, 인포머티브유전자추출 Abstract Since microarray data acquire tens of thousands of gene expression values simultaneously, they could be very useful in identifying the phenotypes of diseases. However, the results of analyzing several microarray datasets which were independently carried out with the same biological objectives, could turn out to be different. One of the main reasons is attributable to the limited number of samples involved in one microarry experiment. In order to increase the classification accuracy, it is desirable to augment the sample size by integrating and maximizing the use of independently-conducted microarray datasets. In this paper, we propose a novel two-stage approach which firstly integrates individual microarray datasets to overcome the problem caused by limited number of samples, and identifies informative genes, secondly builds a classifier using only the informative genes. The classifier from large samples by integrating independent microarray datasets achieves high accuracy up to 24.19% increase as against other comparison methods, sensitivity, and specificity on independent test sample dataset. Key words : Bioinformatics, Microarray data analysis, Microarray data Integration, Microarray classification, Informative gene selection 1. 서론 본연구는과학기술부과학재단목적기초연구 (R ) 로수행되었음 정회원 : 연세대학교컴퓨터과학과 amyyoon@cs.yonsei.ac.kr 학생회원 : 연세대학교컴퓨터과학과 jclee@cs.yonsei.ac.kr 종신회원 : 연세대학교컴퓨터과학과교수 sanghyun@cs.yonsei.ac.kr 논문접수 : 2006년 6월 15일심사완료 : 2006년 11월 12일 암세포가가지고있는분자적특성을암의진단및분류에적용하기위하여암세포특이적유전자발현패턴을연구하고자하는흐름이있어왔고, 마이크로어레이는소수의실험만으로많은수의유전자발현정도를밝힐수있다는점에서암진단분야에획기적진전을가져올것으로기대되고있다. 하나의실험에서얻어진마이크로어레이데이타는그림 1과같이각열은하나

2 2 단계접근법을통한통합마이크로어레이데이타의분류기생성 47 의샘플을, 각행은하나의유전자를의미하며각셀의값은특정유전자가특정샘플에서발현된정도를나타내는수치이다. 또한각샘플은암, 정상등과같은클래스레이블 (label) 을갖는다. 마이크로어레이실험자료는소수의유전자만을대상으로하는분자생물학실험과달리, 수천내지수만개의프로브 (probes) 를대상으로발현수치를얻게되므로이의분석및해석과정에있어서필연적으로통계기법의적용이필요하다. 그림 1 하나의마이크로어레이데이타실험결과 (Si는샘플, G i 는유전자, C 1 과 C 2 는클래스레이블 ) 이러한분석에통계기법이적용되기때문에실험에사용된샘플의수가많으면많을수록결과에대한신빙성이높아질수있다. 특히암과관련된연구의경우충분한수의샘플을대상으로분석하는것이신뢰할수있는결과를도출하는데필수적이다. 최근들어각연구자들에의해독립적으로얻어진마이크로어레이데이타중동일한종류의세포나조직이사용된데이타세트를통합하여분석함으로써각각의독립적분석보다더유의한결과를얻을수있을것이라는가능성이제기되고있다 [1]. 그러나현재까지는동일주제에대해실험한마이크로어레이데이타를대상으로한다하더라도사용된플랫폼 (platform), 유전자세트, 각실험실마다적용된프로토콜 (protocol) 이다를경우이를직접통합하는솔루션이완전하지않은상태이기때문에, 이를통합하여분석하는데많은한계점을가지고있다. 또한독립적으로수행된마이크로어레이의유전자발현값은직접적인비교가불가능하기때문에, 서로상이한환경에서실험된다른마이크로어레이데이타를통합한다는것은매우어려운문제이다. 따라서본논문에서는두단계접근을통하여독립적인마이크로어레이데이타를통합하여신뢰도가높은분류자를찾는방법을제안한다. 제 1 단계에서는독립적으로생성된동일주제의마이크로어레이데이타를복잡한정규화과정없이효율적으로통합하는새로운방법을제안한다. 또한, 통합 마이크로어레이데이타로부터발현형질 (phenotype) 과관련이있는, 인포머티브유전자만을효과적으로추출하는방법을제안한다. 본논문에서제안하는인포머티브유전자추출방법은샘플내순위기반접근 (Rank Based Approach) 을통해간단한정규화과정을거친통합마이크로어레이데이타에효과적으로적용할수있다. 제 2 단계인클래스분류단계에서는제 1 단계에서생성된인포머티브유전자만을사용하여생물학적으로해석이용이한간단한클래스분류규칙을생성한다. 기존의 TSP(Top Scoring Pair) 방법 [2] 은분류규칙에참여하는유전자의개수를중복을허용하지않는 2개로한정하였으며규칙의개수도 1개로제한하였다. 그러나이러한제약조건은생물학적인근거가미흡할뿐만아니라규칙에참여하는유전자가테스트샘플에존재하지않을가능성도배제할수없다. 따라서본논문에서는규칙에참여하는유전자의개수를일반화하고규칙의개수도확장하여좀더신뢰성있고정확한규칙을찾는방법을제안한다. 본논문의분류자는 K( 5) 개의규칙으로이루어져있으며, 한개의규칙은세개유전자간의관계식과클래스레이블로이루어져있다. 이방법은제 1 단계에서클래스분류와연관이있는유전자만을추출한후에적용하기때문에클래스분류의정확도를높일수있을뿐만아니라제 2 단계의계산량을줄일수있다는장점이있다. 제 1단계에서통합에사용된학습데이타 (training dataset) 의샘플수가커질수록테스트데이타의분류정확도가더높아지는것을기존의알고리즘과의비교실험을통해알수있었다. 본논문의순차적두단계접근방법은기존의실험 [19-21] 으로얻어진마이크로어레이데이타의활용성을획기적으로향상하고, 마이크로어레이통합분야에새로운가치를창출하는패러다임으로볼수있다. 2. 관련연구 2.1 마이크로어레이데이타통합최근까지마이크로어레이데이타통합을위하여사용된방법으로는마이닝기법의하나인메타마이닝이있다. 이방법은개별적으로얻어진마이크로어레이실험의결과를통합하여분석하는방식이다 [3]. 그러나각개별연구의샘플의수가일반적으로적기때문에개별연구결과자체가좋지않은경우가많고이런결과의통합은더좋지못한분석을낳을수도있다. 또다른통합의방법으로는개별연구로얻어진데이타값을공통의스케일을갖는값으로정규화하여결합시키는방법이있다 [4]. 가장대표적인예는 Z-Score로변형시켜결합하는경우이다. 그러나복잡한정규화과정을거쳐

48 정보과학회논문지 : 데이타베이스제 34 권제 1 호 (2007.2) 야하는이러한방법은전처리 (preprocessing) 단계에많은비용을지불하게된다. 이밖에데이타통합의모델을제시한연구로는이질마이크로어레이데이타통합에상관서명 (Correlation Signature) 을사용한방법이있다 [5]. 2.

3 48 정보과학회논문지 : 데이타베이스제 34 권제 1 호 (2007.2) 야하는이러한방법은전처리 (preprocessing) 단계에많은비용을지불하게된다. 이밖에데이타통합의모델을제시한연구로는이질마이크로어레이데이타통합에상관서명 (Correlation Signature) 을사용한방법이있다 [5]. 2.2 인포머티브유전자식별마이크로어레이데이타를분석하는데있어가장큰제약조건은실험에참여하는샘플의수에비해유전자의수가너무많다는점이다 [6]. 그러나실질적으로클래스결정에영향을미치는관련 (relevant) 유전자의수는매우한정적이고대부분의유전자들은클래스판별에영향을미치지않는잡음 (noise) 유전자이다. 인포머티브유전자는아래그림 2의두번째와같이클래스 A 에서는모두높은발현값을나타내고클래스 B에서는모두낮은발현값을나타내는유전자로정의할수있다. 반면에그림 2의세번째와같이특정클래스에대해일관성있는발현값을제공하지못하는유전자는연관성이없는잡음유전자로판단할수있다 [7]. 따라서특정질병에관여하는의미있는유전자만을추출한후이를대상으로분류방법을적용하는것이합리적이다. 중모수적 (parametric) 방법은 t-statistics나 Golub [10] 의방법같이데이타를대표하는통계적인모델을가정하여그모델을대표할수있는모수 ( 예 : 평균과분산 ) 를저장하게된다. 이방법은수만개의유전자의발현값을매우적은수의모수로치환하기때문에정보의손실을발생시킬수있다는문제점이있다. 반면비모수적 (non-parametric) 방법은하나의유전자에대한모든샘플값을정렬하여그유전자가두개의클래스그룹에서다르게발현된정도에대한점수 ( 완벽한분리를방해하는정도 ) 를계산한다 [8,11]. 유전자를특징으로보았을때특징추출방법중에서가장일반적으로많이쓰이는방법은순위기반방법이다. 순위기반특징추출방법은각특징이다른특징보다더유의한지의정도를통계적수치로측정한후정렬하여상위의특징을선택하는것이다. 대표적인인포머티브유전자추출방법으로는인포메이션게인 (Information Gain)[12], 릴리프-에프 (Relief- F)[13], 켄달의상관계수 (Kendall's Correlation Coefficient)[14] 를응용한 Park방법 [11] 이있다. 인포메이션게인방법은무질서한정도의척도인엔트로피를활용하는알고리즘이다. 우선 X를유전자로, Y를클래스레이블 ( 정상 (Normal), 암 (Tumor)) 로정하여각각의엔트로피를계산한다. 엔트로피의계산식은아래와같이정의된다. 그림 2 발현값의유형으로본인포머티브유전자발현형질에관여하지않는유전자를제거하고인포머티브유전자만식별해내는작업을특징추출 (Feature Selection) 이라하는데이는마이크로어레이데이타분석에매우중요하다 [8]. 현재이러한인포머티브유전자를정확하고효과적으로추출하기위한여러방법들이제시되고있다. 특징추출의대표적방법으로 PCA(Principal Component Analysis)[9] 와같은방법이있다. 그러나 PCA방법은아이겐벡터로마이크로어레이데이타의차원을줄이기는하지만클래스분류와연관성이있는유전자를개별적으로찾아주지는못한다. 순위방법 그리고아래정의한인포메이션게인 (IG) 수식에의해 IG값을구하여이값이큰유전자를추출하는방법이다. 릴리프-에프는각샘플에대해가장가까운 f개의동일클래스의샘플 (hit sample) 과다른클래스의샘플 (miss sample) 을찾아모든유전자에대해해당샘플과의발현값차이를구한다. 그리고해당샘플과동일클래스의샘플사이의차이는가중치를감소시키고해당샘플과다른클래스의샘플사이의차이는가중치를증가시킨다. 이러한계산을모든샘플에대해모두누적하여각유전자의가중치를계산한후이값이큰순서대로유전자를추출하는방법이다. Park[11] 은켄달의상관계수를이용하여두클래스그룹에서그유전자가다르게발현된정도를측정하는점수함수를정의하였다. 그러나이방법은각유전자의발현값을그대로사용하기때문에서로상이한환경에서실험된다른마이크로어레이데이타에는적용할수

4 2 단계접근법을통한통합마이크로어레이데이타의분류기생성 49 없다. 위에언급한세개의방법들은모두유전자발현값을그대로사용하였으며마이크로어레이데이타의통합또는정규화에대한고려가전혀없다. 2.3 클래스분류많은클래스분류방법중에대표적인것으로는 SVM[15,16], k-nearest Neighbor[17] 의방법이있다. SVM은기계학습알고리즘에바탕을둔것으로하이퍼플레인 (Hyper plane) 으로대표되는선형결정규칙 (Linear Decision Rules) 을학습해나아가는것이다. SVM은마이크로어레이의클래스분류뿐만아니라회귀분석, 밀도예측같은다양한분야에도사용된다. 그러나마이크어레이데이타에적용하기위해서는실험적으로여러가지종류의파라미터조정을필요로하기때문에다소복잡하다는단점이있다. k-nearest Neighbor(k-NN) 는새로운샘플에대하여학습데이타개체중에서유사한것들을선택하여샘플의클래스를분류하는알고리즘이다. 그러나 k-nn 알고리즘은모든유전자에동일한가중치를부여하였을경우좋은성능을제공하지못한다는단점을가지고있다. 또다른클래스분류방법중파라미터를사용하지않고데이타에따라처리되는기계학습방법으로 Xu가제안한 TSP[2] 와 Tan이제안한 k-tsp[18] 방법이있다. TSP는가장높은점수를갖는유전자의쌍을찾는알고리즘이다. 모든유전자쌍 (X i, X j) 에대하여, X i < X j 관계가두클래스에서나타나는상대빈도를각각구하여그차이를계산하여점수함수로사용한다. 이점수가높을수록그유전자쌍은두클래스를잘구별한다고말할수있으며점수가가장큰한쌍의유전자가 TSP 분류자로사용된다. k-tsp는 TSP 방법을확장한것으로 k개의상위점수를얻은유전자쌍을분류자로사용하는방법이다. TSP의경우단지두개의유전자가분류자가되기때문에생물학적해석의용이함은있으나학습데이타를약간만변동시켜도 TSP 분류자자체가변할수있다. 또한분류규칙에참여하는유전자가테스트샘플에존재하지않을가능성도배제할수없다. TSP와 k-tsp 연구에서는인포머티브유전자를먼저추출하는단계없이바로클래스분류자를찾는작업을수행하며전체유전자가분류규칙생성에관여하게되므로, 데이타를통합함에따라계산량의증가를초래한다. 3. 연구방법본장에서는시스템의전체적인개요를먼저기술하고두단계알고리즘을기술한다. 3.2절에서는마이크로 어레이데이타통합의과정과인포머티브유전자를효과적으로추출할수있는방법을기술하고, 3.3절에서는추출된인포머티브유전자를이용하여두클래스를잘구분짓는유전자집합및대소관계를알아낼수있는 k-tst(k-top Scoring Triple) 분류방법에대해설명한다. 3.1 시스템개요본논문에서제안하는시스템의전체적인개요는그림 3과같다. 본논문에서제안하는시스템은두단계로구성되는데제 1단계에서는개별적으로생성된마이크로어레이데이타의통합과인포머티브유전자의추출이이루어진다. 개별적으로시행된마이크로어레이실험의경우, 각실험의발현값의척도가다르며유전자세트의종류도다르다. 따라서이를통합하기위해서우선모든마이크로어레이데이타에서공통적으로사용된유전자만을추출한다. 그리고각실험에서의샘플의발현값을각샘플내에서의순위값으로치환하여통합한다. 일단발현값을순위값으로치환하면각기다른실험에서유래한샘플들도유전자순서가같다면통합이가능하다. 이후각각의유전자에대하여두클래스그룹에서그유전자가다르게발현된정도를측정하는점수를켄달의상관계수를이용하여계산한다. 이때점수값이아주작거나혹은아주큰값을가진유전자가인포머티브유전자가될수있다. 제 2단계에서는 1단계에서추출한인포머티브유전자만을이용하여클래스분류규칙을만들어낸다. 임의의 3개의유전자를 X i, X j, X k 이라하자. 모든 3개의유전자 X i, X j, X k 에대하여, 값의대소관계를생성하면총 6가지의분류규칙을만들어낼수있다. 모든샘플은두개의클래스 C 1, C 2 중의하나에속한다. 클래스 C 1 을레이블로갖는샘플중에서각각의관계를만족하는샘플의수를 C 1 전체샘플수로나누어 C 1 클래스에서해당관계가나타날확률을구한다. 그리고클래스 C 2 를레이블로갖는샘플중에서각각의관계를만족하는샘플의수를 C 2 전체샘플수로나누어 C 2 클래스에서해당관계가나타날확률을구한다. 그리고각각의분류규칙에대하여이두확률값의차이를계산한다. 이값의차이가큰 k개의분류규칙이두클래스를잘구분할수있는분류자의역할을한다. 분류규칙의최적개수 k는학습데이타에 LOOCV 1) (Leave One Out Cross Validation) 를적용하여얻는다. 각분류규칙은 (3개의유전자로이루어진집합, 유전자간의크기를비교한관계식, 이관계식의클래스레이블 ) 로이루어져있다. 새로 1) LOOCV 방법은하나의마이크로어레이데이타내에서하나의샘플을제외한나머지샘플들을이용하여규칙을생성하고이를제외한하나의샘플에적용하여규칙의정확도를측정하는방법이다.

운테스트샘플이주어지면이분류자를적용하여다수의판정을얻은클래스레이블을계산하여그샘플의실질적인클래스레이블과비교하여정확도를측정한다. 3.

5와같이공통적으로사용된유전자집합 (G 3, G 4, G 5, G 6) 만을추출해야한다.

5 50 정보과학회논문지 : 데이타베이스제 34 권제 1 호 (2007.2) (a) 클래스분류규칙을얻기위한 2 단계접근방법 (b) 테스트샘플의클래스레이블판정그림 3 시스템의전체적인개요 운테스트샘플이주어지면이분류자를적용하여다수의판정을얻은클래스레이블을계산하여그샘플의실질적인클래스레이블과비교하여정확도를측정한다. 3.2 마이크로어레이데이타통합과인포머티브유전자추출동일한주제에대한마이크로어레이실험이라할지라도실험에사용된프로브 (Probe, 탐침유전자 ) 세트및유전자의종류는다를수있다. 그렇기때문에개별적으로수행된마이크로어레이실험을통합하기위해서는그림 4와같이먼저독립적으로수행된동일주제의마 이크로어레이데이타들중에서그림 5와같이공통적으로사용된유전자집합 (G 3, G 4, G 5, G 6) 만을추출해야한다. 또한공통적으로사용되는유전자집합이동일순서를가졌다할지라도서로다른실험조건 ( 프로토콜 ) 으로인해마이크로어레이데이타들의발현값의스케일은다를수있기때문에정규화과정없이직접적인통합은불가능하다. 따라서본논문에서는그림 6에서와같이실제발현값이아닌각샘플내에서의해당유전자의발현값의순위를이용하여통합을가능케하였다. 그림 4 독립적으로수행된마이크로어레이데이타 그림 5 마이크로어레이데이타간공통유전자만추출

2 단계접근법을통한통합마이크로어레이데이타의분류기생성 51 그림 6 각샘플내순위로표현된마이크로어레이데이타 순위로치환된값을각유전자에대해크기순으로정렬한후 ( 클래스레이블도함께정렬된다.) 모든샘플에대해클래스레이블을 0 또는 1의값으로치환한다. 예를들어정상클래스샘플을 0, 암클래스샘플을 1로치환한다.

6 2 단계접근법을통한통합마이크로어레이데이타의분류기생성 51 그림 6 각샘플내순위로표현된마이크로어레이데이타 순위로치환된값을각유전자에대해크기순으로정렬한후 ( 클래스레이블도함께정렬된다.) 모든샘플에대해클래스레이블을 0 또는 1의값으로치환한다. 예를들어정상클래스샘플을 0, 암클래스샘플을 1로치환한다. 그리고이렇게얻어진이진문자열과초기의이진문자열 ( 정렬하기이전에클래스레이블을이진문자열로치환한것 ) 과의거리를, 점수함수를이용하여구한다. 점수함수는해당유전자가인포머티브유전자가될가능성에대한척도로서, 정렬후이진문자열이정렬하기이전의이진문자열로변환되기위해필요한연속된 0과 1의교환횟수로정의된다. 표 1은초기의이진문자열 과정렬후얻어진이진문자열 과의점수를예로보인것으로여기서점수는 4로계산된다. 점수함수를통해얻어진값이아주크거나아주작은유전자가인포머티브유전자로선택될수있다. 표 2는인포머티브유전자추출을위한알고리즘을나타낸다. 알고리즘의이해를돕기위해아래표 3과같은마이크로어레이데이타가있다고가정해보자. 이를 점수 (score) 표 1 점수함수의예 이진문자열 (binary sequence) 교환위치 (positions swapped) 과 와 와 과 4 각샘플내에서의순위를기반으로변환한것 ( 알고리즘 단계 2) 이표 4이다. 그리고각유전자별로크기순으로 정렬한것이표 5이고클래스레이블을이진문자열로 변환한것 ( 알고리즘단계 4) 이표 6이다. 알고리즘단계 1을수행하게되면초기의이진문자 열 S를 로얻을수있다. 이를연속된 0과 1의 교환횟수로정의한함수를이용하여표 6의각유전자 표 3 발현값으로표현된데이타 정상 정상 정상 암 암 암 G G G G 표 4 순위로표현된데이타 정상 정상 정상 암 암 암 G G G G 표 5 정렬된데이타와클래스레이블 정상 / 암 정상 / 암 정상 / 암 정상 / 암 정상 / 암 정상 / 암 G 1 2 ( 정상 ) 2 ( 정상 ) 3 ( 암 ) 3 ( 암 ) 4 ( 정상 ) 4 ( 암 ) G 2 1 ( 암 ) 1 ( 암 ) 1 ( 암 ) 2 ( 정상 ) 3 ( 정상 ) 4 ( 정상 ) G 3 1 ( 정상 ) 1 ( 정상 ) 2 ( 암 ) 3 ( 정상 ) 4 ( 암 ) 4 ( 암 ) G 4 1 ( 정상 ) 2 ( 암 ) 2 ( 암 ) 3 ( 정상 ) 3 ( 암 ) 4 ( 정상 ) 표 2 인포머티브유전자추출알고리즘 Input: NI ( 인포머티브유전자의개수 ), V[][] ( 발현값 ) Output: IG[][] ( 인포머티브유전자정보 ) 1: 정상샘플은 0으로암샘플은 1로치환한이진문자열 S를생성한다. 2: 모든 i,j에대하여발현값으로표현된 V[G i][s j] 를각샘플내에서발현값으로정렬하였을때의순위인 R[G i][s j] 로대 체한다. 3: 선택되지않은유전자중임의의한유전자 G i 를선택한다. 4: 모든 j에대해 R[G i][s j] 을오름차순으로정렬한후정상샘플은 0으로암샘플은 1로치환한이진문자열 T를생성한다. 5: 연속된 0과 1의교환횟수로정의된점수함수를이용하여 S와 T의점수를계산한후우선순위큐에삽입한다. 6: 모든유전자가선택될때까지단계 3으로돌아가계속수행한다. 7: 우선순위큐에서상위 NI/2개, 하위 NI/2개의인포머티브유전자를추출한다.

7 52 정보과학회논문지 : 데이타베이스제 34 권제 1 호 (2007.2) 표 6 이진문자열로표현된데이타 G G G G 의이진문자열에대하여계산해보면 0과 1의교환의횟수가가장적은유전자는 G 3 로총 1회이고가장많은유전자는 G 2 로 9회이다. 이는 G 2 와 G 3 가 G 1 이나 G 4 보다인포머티브유전자가될가능성이높다는것을의미한다. 점수가낮은 G 3 유전자는해당질병에대해긍정적인상관관계 (positive correlation), 즉암세포에대해발현을많이하는유전자로설명될수있으며점수가큰 G 2 유전자는부정적인상관관계 (negative correlation), 즉정상세포에대해발현을많이하는유전자로설명될수있다. 모든발현값을샘플내에서의순위로치환을하였기때문에이를정렬하는데있어같은순위값이발생할수있다. 만일동일한클래스를가진샘플사이에같은순위값이발생하였을경우에는점수에영향을미치지않는다. 그러나서로다른클래스를가진샘플사이에같은순위값이발생하였을경우에는어떤클래스를우선순위에두느냐에따라점수가다를수있다. 위의예제의경우초기의이진문자열 S가 이기때문에암샘플을정상샘플보다우선시한다면그렇지않을경우보다점수가더크게나오게된다. 본논문에서는정상샘플에암샘플보다더높은우선순위를주었다. 그러나우선순위에따른이러한점수의차이가인포머티브유전자를구별하는데에는크게영향을미치지않는다. 왜냐하면서로다른클래스를가진샘플들사이에동일한순위값이발생하였다면이는해당유전자가인포머티브유전자가될가능성이적은유전자임을의미하기때문이다. 3.3 k-tst (k-top Scoring Triple) 분류방법본연구에서는암과정상샘플을구분하는분류자의신뢰성을높이기위하여규칙에참여하는유전자의수를일반화하는것이목표이다. 이러한목표의첫단계로서기존의 k-tsp 방식을확장한 k-tst를제안한다. k-tst에서는분류규칙에참여하는유전자의수를세개로한정한다. 세개의유전자의순위값의크기를비교하여아래의표 9와같이 R 1... R 6 의 6개의관계식을확립하고, 각관계식에대하여발생한빈도수를계산한다. 점수는하나의관계식이클래스 1에서일어난확률과클래스 2에서일어난확률의차로계산된다. 이확률의차가가장큰관계식의세개의유전자조합이클래스를가장잘분류다고할수있다. 각관계식의우세한클래스레이블은두확률값을비교하여큰쪽의클래스로정의된다. 본논문은모든세개의유전자조합을대상으로한다. 각조합에대하여 6개의관계식모두에대하여위의점수를계산하여, 우선순위큐에정렬한다. 이중에서 k개의상위관계식이본논문의분류자가된다. 따라서분류자는 k개의분류규칙으로이루어져있으며각각의분류규칙은 1) 세개의유전자집합, 2) 세개유전자간의크기를비교한관계식, 3) 그관계식의우세한클래스레이블로이루어져있다. k-tst에대한알고리즘은표 7과같다. 그리고표 7의단계 3에서사용한점수함수 (scoring function) 의정의는표 8과같다. 예를들어표 9와같은데이타가있다고가정해보자. C 1 과 C 2 는각각정상또는암클래스를의미하고 X는유전자를, R i 는세개의유전자조합의대소관계를의미한다. 여기서해당되는모든의값을구해보면 R 3 표 8 점수함수정의 Class 1 에서 X i <X j <X k 인관계가나타날확률 (X i, X j, X k 는각샘플내에서의순위값을나타냄 ) 표 9 TST 예제 R 1 R 2 R 3 R 4 R 5 R 6 Total C C (R 의정의 ) R 1: X i < X j < X k R2: X i < X k < X j R3: X j < X i < X k R4: X j < X k < X i R5: X k < X i < X j R6: X k < X j < X i 표 7 k-tst 분류방법알고리즘 Input: K ( 원하는규칙의개수 ), IS[][] ( 인포머티브유전자 ) Output: K개의분류규칙집합 1: 인포머티브유전자중이전에선택되지않은세개의유전자조합을선택한다. 2: 모든샘플에대해세유전자의발현값간의대소관계를판별한다. 3: 정의된점수함수를이용하여각분류규칙의점수를계산한다. 4: 계산된점수와대소관계, 유전자조합, 우세한클래스레이블로이루어진규칙을크기 K인우선순위큐에삽입한다. 5: 가능한세개의유전자조합이남아있다면단계 1로돌아가다시수행한다. 6: 우선순위큐에서상위 K개의규칙을추출한다.

8 2 단계접근법을통한통합마이크로어레이데이타의분류기생성 53 (X j < X i < X k) 관계일경우에, 가가장큰점수를가지는것을알수있다. 이는유전자 X i, X j, X k 에대해서 X j < X i < X k 의규칙이나올가능성이가장높다는것을의미한다. k-tst 알고리즘은모든인포머티브유전자 X i, X j, X k 조합에대하여 를구하여이값이큰 K개의규칙을반환한다. 위의예제의경우규칙은 ( 점수 : 0.66, 대소관계 : X j < X i < X k, 유전자조합 : X i, X j, X k, 우세한클래스레이블 : C 1 ) 로표현될수있다. 만일테스트샘플의클래스레이블을판별하고자할때, 위의규칙에기반한다면 X i, X j, X k 유전자의값을확인하여 X j < X i < X k 의관계를만족시킨다면테스트샘플의클래스를 C 1 으로판별하게된다. 실제로는이러한규칙의개수가 k개이기때문에과반수투표 (majority voting) 에따라테스트샘플의클래스를판별한다. 과반수투표의과정은아래수식과같다. r i k is NC = is the 1 V ( ri ) = 0 i th rule the number of L( r ) = Class i L( ri ) P ri( S) = L( ri ) k i= 1 V ( r ) Label of i ri rules Otherwise S is a test sample NC is the number of normal count the r ( L( r ) = { normal, tu i if S satisfies the Otherwise if P ( S) is a Normal Sample i 위수식에서 는규칙의우세한클래스레이블을의미하고 는테스트샘플 S가규칙를만족할경우에는규칙의우세한클래스레이블로, 그렇지않을경우에는규칙의우세한클래스레이블과반대의클래스레이블로정의된다. 는 normal과 tumor만을원소로가지고있기때문에테스트샘플의클래스는규칙의우세한클래스레이블이 normal이고테스트샘플 S가규칙을만족한다면 normal로, 만족 r i 하지않을경우 tumor 로정의되게된다. 그리고 는규칙의판정결과가정상샘플일경우에는 1로, 암샘플일경우에는 0으로정의된다. 는최종적인판정을하기위해정상샘플이라고판정한횟수를모두 누적하게된다. 만일 의값이 보다크면테스트 샘플의클래스를정상으로판정하게되고그렇지않을경우에는암으로판정하게된다. 규칙의개수 k를홀수로고정하였기때문에동점이발생하지않고항상테스트샘플의클래스를판정할수있다. 4. 실험결과 본장에서는논문이제안하는두단계마이크로어레이분석기법의정확도와효율성을검증하기위한실험을기술한다. 본실험에서는논문을통하여공개된데이타가비교적많은전립선암 (Prostate Cancer) 마이크로어레이데이타를사용하였다. 실험에사용된마이크로어레이플랫폼은 Affymetrix사의 HG_95AV2이다. 아래실험에서사용된데이타는각실험자의이름인 Singh [19], Welsh[20], Latulippe[21] 로표기한다. 4.1 LOOCV 를통한최적규칙의개수 (K) 결정본절에서는 LOOCV를이용해규칙의개수인 K를변경해가며정확도가가장높은최적의 K의값을얻는실험에대해기술한다. 보통인포머티브유전자의개수는 50에서 200개로선택하는것이일반적이므로 [10,22], 본실험에서는총유전자의개수인 12600개의 1% 인 126개를선택하였다. 아래그림 7에서그림 12까지는 K 의최대값을 10으로설정하였을때 K를변경시켜가며각마이크로어레이데이타에대한 LOOCV를실험한그래프이고표 11은실험결과얻은최적의 K의값들이다. 여기서비교척도로서정확도 (Accuracy) 와민감도 (Sensitivity) 그리고특이성 (Specificity) 을사용하였다. 이를수식으로나타내면아래와같다. 표 10 전립선암 (prostate cancer) 마이크로어레이데이타 데이타 프로브세트 ( 유전자개수 ) 정상샘플의수 암샘플의수 총샘플의수 Singh Welsh LaTulippe

9 54 정보과학회논문지 : 데이타베이스제 34 권제 1 호 (2007.2) 그림 7 Singh 데이타로 LOOCV 그림 10 Singh 과 Welsh 의통합데이타로 LOOCV 그림 8 Latulippe 데이타로 LOOCV 그림 11 Singh 과 Latulipple 의통합데이타로 LOOCV 그림 9 Welsh 데이타로 LOOCV 그림 12 Welsh 와 Latulippe 의통합데이타로 LOOCV 표 11 LOOCV를통해얻어진최적 K Traing Data 최적 K Singh 9 Latulippe 5 Welsh 5 Singh + Welsh 9 Singh + Latulippe 7 Welsh + Latulippe 5 본실험에서는규칙의개수를최소 5개이상으로한 정하였다. 왜냐하면규칙의개수가너무적을경우분류 자의신뢰성을보장하기어렵기때문에실제다른환경 에서얻어진독립적인데이타를테스트데이타로하여실험하였을경우정확도가떨어질수있기때문이다. 4.2 인포머티브유전자추출방법의정확도비교본절에서는논문에서제안한인포머티브유전자의추출방법에대한정확도를비교분석한다. 비교대상으로는대표적인인포머티브유전자추출방법인인포메이션게인 (Information Gain) 과릴리프에프 (Relief-F) 를사용하였다. 이때두방법모두통합된데이타에그대로적용하는것이불가능하기때문에가장일반적인정규화방법인 Z-score를사용하여통합하였다. 그리고두번째단계인클래스분류방법의비교대상으로는

2 단계접근법을통한통합마이크로어레이데이타의분류기생성 55 그림 13 Singh 데이타에대한 LOOCV 결과 그림 16 Singh 과 Welsh 통합데이타에대한 LOOCV 결과 그림 14 Welsh 데이타에대한 LOOCV 결과

현재패턴인식분야에서가장좋은정확도를나타내고있는 SVM(Support Vector Machine) 을사용하였다. 그림 13에서그림 18은각데이타세트에대한 LOOCV 의정확도를나타내는그래프이다.

Singh과 Welsh의단일데이타에대한 LOOCV의정확도 ( 그림 13,14) 는인포메이션게인을사용한경우와동일하게나왔으며 Latulippe 데이타 ( 그림 15) 에대해서는더좋은성능을나타내었다.

10 2 단계접근법을통한통합마이크로어레이데이타의분류기생성 55 그림 13 Singh 데이타에대한 LOOCV 결과 그림 16 Singh 과 Welsh 통합데이타에대한 LOOCV 결과 그림 14 Welsh 데이타에대한 LOOCV 결과 그림 17 Singh 과 Latulippe 통합데이타에대한 LOOCV 결과 그림 15 Latulippe 데이타에대한 LOOCV 결과 그림 18 Welsh 와 Latulippe 통합데이타에대한 LOOCV 결과 현재패턴인식분야에서가장좋은정확도를나타내고있는 SVM(Support Vector Machine) 을사용하였다. 그림 13에서그림 18은각데이타세트에대한 LOOCV 의정확도를나타내는그래프이다. 위의그래프들을보면논문에서제안한인포머티브추출방법이다른방법에비해동일하거나더좋게나옴을알수있다. Singh과 Welsh의단일데이타에대한 LOOCV의정확도 ( 그림 13,14) 는인포메이션게인을사용한경우와동일하게나왔으며 Latulippe 데이타 ( 그림 15) 에대해서는더좋은성능을나타내었다. 그리고 릴리프에프보다는대부분좋은정확도를보임을알수있다. 특히 Singh과 Latulippe의통합데이타 ( 그림 17) 에대한 LOOCV의정확도는다른방법들에비해 10% 이상의높은정확도를나타내고있다. 이러한결과로비추어볼때, 본논문에서제안하는인포머티브유전자추출방법이다른추출방법들에필적하거나좀더좋은성능을보인다는것을알수있다. 아래그림 19에서그림 21은세개의데이타중하나를테스트데이타로사용하고나머지데이타의조합을학습데이타로사용하여정확도를실험한그래프이다. 예

11 56 정보과학회논문지 : 데이타베이스제 34 권제 1 호 (2007.2) 를들어 Singh을테스트데이타로사용할경우, 학습데이타세트는 Welsh, Latulippe, Welsh+Latullipe가된다. 본알고리즘은각학습데이타로부터분류자를얻어서 Singh데이타에적용하여정확도를측정, 비교하였다. 그리고 Singh에대하여분류자를찾는세가지방법 1) 본논문에서제안한인포머티브유전자추출방법 + SVM, 2) 릴리프에프 + SVM, 3) 인포메이션게인 + SVM의정확도를비교하였다. 독립적인데이타로테스트를수행한위의그래프들을보면, LOOCV 실험에서와마찬가지로논문에서제안한인포머티브유전자추출방법이인포메이션게인과동그림 19 Singh을테스트데이타로사용 일한성능을보이거나조금더좋은성능을보였다. 인포메이션게인방법이통합데이타에대해항상더좋은정확도를보이지않는반면 ( 그림 19), 본논문에서제안한방법은데이타를통합하여샘플의수를증가시킬수록정확도가좋아지는것을알수있다. 4.3 클래스분류방법의정확도비교본절에서는 4.1절에서구한각학습마이크로어레이데이타에대한최적의 K개의규칙을이용하여독립적인데이타에적용하였을때제안하는두단계접근시스템의정확도를기존의 k-tsp 방법과 4.2절에서비교실험한기존의방법중더좋은성능을보인인포메이션게인을적용한후 SVM을적용하는방법과비교실험한다. 그림 22에서그림 24는 Singh, Welsh, Latulippe 를각각독립적인테스트데이타로이용하고그이외의마이크로어레이데이타의조합으로학습하여규칙을만들어테스트한정확도그래프이다. 표 12는실험에사용된 K의값을나타낸다. 위의세그래프를보면알수있듯이단일마이크로어레이데이타에대한테스트결과는 k-tst가다른방법들에비해항상좋은결과를내지는못한다. 그러나단일마이크로어레이데이타는학습데이타로사용하기에샘플의수가충분치않다. 특히 Welsh, Latulippe 에서는샘플의수가약 30개내외이고정상샘플과암 그림 20 Welsh 를테스트데이타로사용 그림 22 Singh 을테스트데이타로사용 그림 21 Latulippe 를테스트데이타로사용 그림 23 Welsh 를테스트데이타로사용

12 2 단계접근법을통한통합마이크로어레이데이타의분류기생성 57 그림 24 Latulippe를테스트데이타로사용표 12 실험에사용된규칙의개수 (K) Test data Training data k-tsp k-tst Welsh 3 5 Singh Latulippe 3 5 Welsh + Latulippe 1 5 Singh 1 9 Welsh Latulippe 3 5 Singh + Latulippe 5 7 Singh 1 9 Latulippe Welsh 3 5 Singh + Welsh 9 9 샘플수의분포가비대칭적이기때문에이를학습데이타로쓰는것은신뢰할만한규칙을만들어내지못할가능성이있다. 그러나학습데이타의샘플의수가늘어날수록, 즉단일마이크로어레이데이타를통합할수록, k-tst의정확도가 k-tsp나 SVM에비해 15% 에서최대 24.19% 좋아짐 ( 그림 22, 23) 을알수있다. 위의실험들을근거로하였을때본논문에서제안한두단계접근법이단일마이크로어레이데이타를통합하면할수록, 신뢰도높은규칙을만들어내는것을알수있다. 5. 결론및향후연구본논문에서는독립적으로생성된마이크로어레이데이타를통합하고인포머티브유전자를찾은후, 클래스분류규칙을생성하는두단계접근방법을소개하였다. 본논문의주공헌은다음과같다. 마이크로어레이데이타의양이폭발적으로늘고있는상황에서동일한생물학적주제로다른연구기관에서독립적으로시행된데이타를통합할수있는새로운방법을제 1 단계에적용하였다. 데이타의통합으로학습데이타의샘플수가증가되었기때문에높은정확도를보이는분류자를찾을수있었다. 또한두단계접근을취함으로서제 2 단계에서는 1단계에서추출된인포머 티브유전자만을사용함으로써계산량을획기적으로줄일수있었다. 그리고본논문에서제시한클래스분류방법은관련유전자의개수가비교적적고해석이용이하기때문에실질적으로암진단키트에사용될경우진단비용을크게낮출수있다. 왜냐하면수만개의유전자를이용하는마이크로어레이실험을매진단에사용하는것을비용면에서비효율적이기때문이다. 본논문에서제시한알고리즘에대한시스템구현이완성되어진행된실험결과를보면, 본논문의인포머티브유전자추출방법이다른방법에비해우수하거나필적함을알수있고, 독립마이크로어레이데이타를통합하여학습데이타의샘플수가늘어날수록, 본논문의분류자의정확도가다른방법에비해월등히좋아짐을알수있었다. 위의실험들을근거로하였을때본논문에서제안한두단계접근법이단일마이크로어레이데이타를통합하면할수록, 신뢰도높은규칙을만들어내는것을알수있었다. 현재향후연구로 1) Affymetrix사의플랫폼뿐만아니라다른기준으로발현값을표현하는 cdna 플랫폼과연동하는방법 2) 상관관계분석또는클러스터링기법을활용하여, 관련유전자들간의존재하는중복 (redundancy) 을없애는방법 3) 클래스분류규칙의개수, 각규칙에참여하는유전자의개수를좀더일반화하는방법등이있다. 참고문헌 [1] S. Mukherjee, P. Tamayo, S. Rogers, R. Rifkin, A. Engle, C. Campbell, T. Golub and J. Mesirov, "Estimating dataset size requirements for classifying DNA microarray data", Journal of Computational Biology, vol. 10, pp , [2] L. Xu, A. Tan, D. Naiman, D. Geman and R. Winslow, "Robust prostate cancer marker genes emerge from direct integration of inter-study microarray data", Bioinformatics, vol. 21, pp , [3] J. K. Choi, U. Yu, S. Kim and O. J. Yoo, "Combining multiple microarray studies and modeling interstudy variation", Bioinformatics, vol. 19, pp , [4] H. Jiang, Y. Deng, H.S. Chen, L. Tao, Q. Sha and J. Chen, "Joint analysis of two microarray geneexpression data sets to select lung adenocarcinoma marker genes," BMC Bioinformatics, vol. 5, pp , [5] J. Kang, J. Yang, W. Xu, and P. Chopra, "Integrating heterogeneous microarray data sources using correlation signatures," In International Workshop on Data Integration in the Life Sciences (DILS), 2005.

58 정보과학회논문지 : 데이타베이스제 34 권제 1 호 (2007.2) [6] S. Dudoit and J. Fridlyand, "Classication in microarray experiments," Statistical Analysis of Gene Expression Microarray Data, Chapman and Hall, 2003.

Friedman, I. Nachman, M. Schummer and Z. Yakhini, "Tissue classification with gene expression profiles," Journal of Computational Biology, vol. 7, pp. 559-583, 2000. [9] C.

R. Downing and M. A. Caligiuri, "Molecular classification of cancer: class discovery and class prediction by gene expression monitoring," Science, vol. 286, pp. 531-537, 1999. [11] P. J. Park, M.

13 58 정보과학회논문지 : 데이타베이스제 34 권제 1 호 (2007.2) [6] S. Dudoit and J. Fridlyand, "Classication in microarray experiments," Statistical Analysis of Gene Expression Microarray Data, Chapman and Hall, [7] C. Tang, A. Zhang and J. Pei, "Mining Phenotypes and Informative Genes from Gene Expression Data," ACM SIGKDD, pp , Washington, DC, USA, August [8] A. Ben-Dor, L. Bruhn, N. Friedman, I. Nachman, M. Schummer and Z. Yakhini, "Tissue classification with gene expression profiles," Journal of Computational Biology, vol. 7, pp , [9] C. Bishop, "Neural networks for pattern recognition," Oxford University Press, New York, [10] T. R. Golub, D. K. Slonim, P. Tamayo, C. Huard, M. Gaasenbeek, J. P. Mesirov, H. Collier, M. L. Loh, J. R. Downing and M. A. Caligiuri, "Molecular classification of cancer: class discovery and class prediction by gene expression monitoring," Science, vol. 286, pp , [11] P. J. Park, M. Pagano and M. Bonetti, "A nonparametric scoring algorithm for identifying informative genes from microarray data," Pacific Symposium on Biocomputing, pp , [12] I. H. Witten, and E. Frank, "Data mining: practical machine learning tools and techniques with Java implementations," Morgan Kaufmann, [13] M. Robnik-Sikonja, and I. Kononenko, "Theoretical and empirical analysis of ReliefF and RReliefF," Machine Learning, vol. 53, pp.23-69, [14] N. Bailey, "Statistical methods in biology," Cambridge university press, [15] C. C. Chang and C. J. Lin, "LIBSVM: a library for support vector machine," 2001, csie.ntu.edu.tw/~cjlin/libsvm. [16] V. Vapnik, "Statistical Learning Theory," John Wiley & Sons, New York, [17] B. Dasarathy, "Nearest Neighbor Norms: NN Pattern Classification Techniques," IEEE Computer Society Press, Los Alamitos, CA, USA [18] A. Tan, D. Naiman, L. Xu, R. Winslow and D. Geman. "Simple decision rules for classifying human cancers from gene expression profiles," Bioinformatics, vol. 21, pp , [19] D. Singh, P. G. Febbo, K. Ross,D. G. Jackson, J. Manola and C. Ladd, "Gene expression correlates of clinical prostate cancer behavior," Cancer Cell, vol. 1, pp , [20] J. B. Welsh, L. M. Sapinoso, A. I. Su, S. G. Kern, J. Wang-Rodriguez and C. A. Moskaluk, "Analysis of gene expression identifies candidate markers and pharmacological targets in prostate cancer", Cancer Res., vol. 61, pp , [21] E. LaTulippe, J. Satagopan, A. Smith, H. Scher, P. Scardino and V. Reuter, "Comprehensive gene expression analysis of prostate cancer reveals distinct transcriptional programs associated with metastatic disease," Cancer Res, vol. 62, pp , [22] L. Li, W. Leping, C. R. Weinberg, T. A. Darden and L. G. Pedersen, "Gene Selection for Sample Classification Based on Gene Expression Data: Study of Sensitivity to Choice of Parameters of the ga/knn Method," Bioinformatics, vol. 17, pp , 윤영미 1981 년 2 월서울대학교자연과학대학졸업 ( 학사 ) 년 6 월 ~1983 년 6 월오하이오주립대학수학과 ( 학사수료 ) 년 3 월스탠포드대학교컴퓨터과학과졸업 ( 석사 ) 년 5 월 ~1993 년 5 월 Intelli- Genetics Inc., Mountainview, California, Software Engineer 년 2 월 ~ 현재가천의과학대학교부교수 년 3 월 ~ 현재연세대학교컴퓨터과학과박사과정. 관심분야는데이타베이스시스템, 데이타마이닝, 바이오인포매틱스 이종찬 2004년 8월연세대학교컴퓨터과학과졸업 ( 학사 ). 2006년 8월연세대학교컴퓨터과학과대학원졸업 ( 석사 ). 관심분야는위치기반서비스, ITS, 데이타베이스시스템, 데이타마이닝, 바이오인포메틱스 박상현 1989년 2월서울대학교컴퓨터공학과졸업 ( 학사 ). 1991년 2월서울대학교컴퓨터공학과졸업 ( 석사 ). 2001년 2월 UCLA대학교전산학과졸업 ( 박사 ). 1991년 3월~ 1996년 8월대우통신연구원. 2001년 2 월~2002년 6월 IBM T. J Watson Research Center Post-Doctoral Fellow. 2002년 8월~ 2003년 8월포항공과대학교컴퓨터공학과조교수. 2003년 9 월~2006년 8월연세대학교컴퓨터과학과조교수. 2006년 9 월~현재연세대학교컴퓨터과학과부교수. 관심분야는데이타베이스보안, 데이타마이닝, 바이오인포매틱스, XML 등

<313120C0AFC0FCC0DA5FBECBB0EDB8AEC1F2C0BB5FC0CCBFEBC7D15FB1E8C0BAC5C25FBCF6C1A42E687770>

<313120C0AFC0FCC0DA5FBECBB0EDB8AEC1F2C0BB5FC0CCBFEBC7D15FB1E8C0BAC5C25FBCF6C1A42E687770> 한국지능시스템학회 논문지 2010, Vol. 20, No. 3, pp. 375-379 유전자 알고리즘을 이용한 강인한 Support vector machine 설계 Design of Robust Support Vector Machine Using Genetic Algorithm 이희성 홍성준 이병윤 김은태 * Heesung Lee, Sungjun Hong,