09 J2_ _R[정인선].hwp

Size: px

Start display at page:

Download "09 J2_200800097_R[정인선].hwp"

나리 탁
8 years ago
Views:

1 일배체형 재조합을 위한 MCIH 모델과 WMLF/GI 모델의 정확도 비교 57 DOI: /KIPSTB B..57 일배체형 재조합을 위한 MCIH 모델과 WMLF/GI 모델의 정확도 비교 정 인 선 강 승 호 임 형 석 요 약 일배체형 조합 문제를 해결하기 위해 제시된 MLF(Mmum Letter Fps) 모델이나 WMLF(Weghted Mmum Letter Fps) 모델은 유전 자형 정보를 도입함으로써 오류와 손실이 많을 때에도 높은 정확도를 얻을 수 있다. 그리고 MLF 모델에 비해 가중치 버전인 WMLF모델의 정 확도가 높다는 사실도 밝혀졌다. 본 논문에서는 유전자형 정보상의 동형(homozygous)의 분포 비율과 유전자 서열판독기계의 성능에 따른 신뢰 도의 차이를 매개변수로 하여 두 모델을 구체적으로 비교, 분석한다. 두 모델의 성능 비교를 위해 신경망과 유전자 알고리즘을 사용한다. 실험 결과 동형의 비율이 크고 판독기계의 성능이 좋으면 특히 손실율과 오류율이 높은 경우에 WMLF/GI 모델의 정확도가 더 우수함을 보인다. 키워드 : 일배체형 조합문제, 유전자형, SNP, 신경망 The Correctess Comparso of MCIH Mode ad WMLF/GI Mode for the Idvdua Hapotypg Recostructo I-Seo Jeog Seug-Ho Kag Hyeog-Seok Lm ABSTRACT Mmum Letter Fps(MLF) ad Weghted Mmum Letter Fps(WMLF) ca perform the hapotype recostructo more accuratey from SNP fragmets whe they have may errors ad gaps by troducg the reated geotype formato. Ad t s kow that WMLF s more accurate hapotype recostructo tha those based o the MLF. I the paper, we aayze two modes uder the codtos that the dfferet rates of homozygous ste the geotype formato ad the dfferet cofdece eves accordg to the sequecg quaty. We compare the performace of the two modes usg eura etwork ad geetc agorthm. If the rate of homozygous ste s hgh ad sequecg quaty s good, the resuts of expermets dcate that WMLF/GI has hgher accuracy of hapotype recostructo tha that of the MCIH especay whe the error rate ad gap rate of SNP fragmets are hgh. Keywords : Hapotype Assemby Probem, Geotype, SNP, Neura Network. 서 론 ) 사람의 유전체(geome) 서열이 전부 밝혀짐에 따라 유전 적 차이에 대한 연구가 유전학에서 중요한 주제가 되었다 [0]. 모든 사람은 개인 간에 약 99.9% 동일한 유전적 염기 서열을 지니고 있고 약 0.%의 염기서열만이 개인 간의 차 이를 보인다. 단지 0.%의 염기서열 차이가 개인간 유전적 차이의 원인으로 추정되고 있다[8]. 인간 유전체에서 유전적 변이를 가장 풍부하게 보여주는 유전 마커(geetc marker) 이 논문은 007년도 정부재원(교육인적자원부 학술연구조성사업비)으로 한 국학술진흥재단의 지원을 받아 연구되었음(KRF D00644). 준 회 원 : 전남대학교 전산학과 박사과정 정 회 원 : 전남대학교 전자컴퓨터공학부 교수 논문접수 : 009년 월 5일 수 정 일:차 009년 월 4일 심사완료 : 009년 월 5일 로 SNP이 대표적이며, 이의 이해가 인간의 질병 치료와 약 품 설계 그리고 새로운 의료 기구 생산에 대한 능력을 증가 시킬 것으로 예측하고 있다. SNP이란 DNA 염기서열에서 하나의 염기서열 차이를 보 이는 유전적 변화 또는 변이를 말한다. 변이의 범위는 제한 되어 있고 각 변이를 대립유전자(aee)라 한다. SNP은 일 반적으로 대립유전자의 빈도에 의해 원형(wd type)과 돌연 변이형(mutat type)으로 구분한다. 그리고 특정 염색체의 SNP 서열을 일배체형이라 한다. 인간과 같은 이배체 (dpod) 생물은 유전체가 한 쌍의 염색체로 구성되어 있기 때문에 두 개의 일배체형이 존재한다. 유전자형(geotype)이 란 상동염색체에 대한 두 일배체형의 조합(cofato)을 말 한다. SNP에 대해 두 대립유전자형이 동일하면 이 SNP 위 치(ste)를 동형이라 하고, 서로 다르면 이형(heterozygous)

그리고 MLF 모델에 비해 가중치 버전인 WMLF모델의 정 확도가 높다는 사실도 밝혀졌다. 본 논문에서는 유전자형 정보상의 동형(homozygous)의 분포 비율과 유전자 서열판독기계의 성능에 따른 신뢰 도의 차이를 매개변수로 하여 두 모델을 구체적으로 비교, 분석한다. 두 모델의 성능 비교를 위해 신경망과 유전자 알고리즘을 사용한다.

2 58 정보처리학회논문지 B 제6-B권 제호(009.4) SNP SNP SNP 3 Chrom. c, patera g c g g T a a g a c g G c t a g g a t C a g t Chrom, c, matera g c g g A a a g a c g G c t a g g a t G a g t 일배체형 T G C 일배체형 A G G 유전자형 T/A G/G C/G (그림 ) 한 쌍의 일배체형과 유전자형 예 이라 한다. (그림 )은 3개의 SNP 위치를 갖는 염색체의 예 이다. 일배체형들은 {TGC}와 {AGG}이며, 이형은 SNP 위치 과 3, 동형은 SNP 위치 에서 나타난다. 일배체형의 차이는 개별 개체들의 발현 형질의 차이와 직 접적인 관련이 있는 것으로 밝혀져 있다. 특히 유전과 관련 이 있는 질병연구에서 중요한 의미를 갖고 있다. 이들의 차 이를 유형화 하고 특정 질병과의 연관성을 분석하면 개인들 의 질병 발생 가능성을 사전에 알 수 있다. 또한 특정 약물 이나 치료 방법에 반응하는 개인의 양상도 각자 다르게 나 타나는데 이러한 약물이나 치료 방법과 일배체형 유형의 관 계를 규명하게 되면 맞춤의학의 실현 또한 가능할 것으로 판단된다. 이처럼 일배체형은 생물학, 의학, 약학 등 여러 분 야에서 중요한 의미를 갖는 유전마커이다[7]. 개별 SNP이나 유전자형을 생물학적 실험을 통해 얻어내 기는 상대적으로 쉬운 작업에 속하지만 일배체형을 바로 얻 어내는 것은 기술적 제약이 많으며 비싼 비용을 지불해야 한다. 또한 현재의 SNP 판독 기술은 SNP의 위치와 대립유 전자형을 알아낼 수 있을 뿐 대립유전자가 두 염색체 중 어 떤 염색체의 것인지를 판별하기에 한계가 있다. 따라서 일 배체형을 결정하는 문제가 유전자형을 결정하는 문제보다 훨씬 어렵다. 이러한 어려움을 극복하기 위해 전산학적 관 점에서 두 부류의 문제가 정의 되었다. 일배체형 추론문제 (hapotype ferece probem)는 특정 집단의 유전자형 정 보로부터 일배체형 집합을 추론하는 문제이다. 다른 하나는 일배체형 조합문제(hapotype assemby probem)로 개인의 판독된 염기 서열들로부터 하나의 일배체형 쌍을 조합해내 는 문제이다. 본 논문은 일배체형 조합문제를 다룬다. 일배 체형 조합문제는 손실(mssg or gap)과 오류(error)가 존 재하는 SNP 단편들을 두 부분으로 나누고 이로부터 한 쌍 의 일배체형을 결정하는 것이다. 일배체형 조합문제에는 여러 가지 모델이 제시되어 있는 데 각각 다른 실험상의 조건들을 가정하고 있다[]. 이중 MLF 모델과 이 모델의 가중치 버전인 WMLF 모델은 하나 의 생물 개체로부터 모든 단편들이 얻어지고 단편들의 SNP 판독에 손실과 오류가 있다고 가정한다. 여기서 손실이란 SNP을 판독하지 못한 경우를 말하고 오류란 잘못 판독한 경우를 말한다. WMLF 모델은 이러한 가정에 염기를 판독 하는 기계가 자신이 판독한 개별 염기에 대해 신뢰도를 부 여한다는 사실에 기반하고 있다. 이 가중치는 SNP 판독 기 계가 판독된 염기에 대해 가지는 정확성을 나타낸다. 두 모 델이 제시한 문제들은 단편들에 손실이 없는 경우에도 NP-hard임이 증명되었으며[,3], 개의 손실이 있는 경우엔 MLF 모델은 APX-hard임[]이 밝혀졌다. APX-hard란 좋은 근사 알고리즘의 존재가 알려지지 않은 경우를 말한다. 그 리고 Zhao 등[3]은 WMLF 모델이 MLF 모델 보다 일배체 형을 조합하는데 높은 정확성을 가짐을 보여주었다. 그러나 두 모델은 SNP 판독상의 손실률과 오류율이 낮은 경우에 효과적이다. MLF 모델의 정확성을 향상시키기 위해 상대적 으로 얻기 쉬운 유전자형 정보의 도입을 모델화 한 MCIH 모델[]이 제시되었다. MCIH 모델은 MLF/GI 모델[0]로 불린다. 이후 유전자형 정보를 MLF 모델에 도입한 여러 방 법들이 제시되었다[9,0,]. [4]에서는 WMLF 모델에 유전 자형을 도입한 WMLF/GI 모델을 제시하고 일배체형 결정 의 정확도와 수렴속도를 향상시켰다. 그러나 유전자형을 도 입한 두 모델 WMLF/GI와 MCIH 사이의 유전자형 정보에 따른 다양한 비교는 되어있지 않고 유전자형에 분포하는 동 형의 비율과 서열판독기계의 성능에 따른 두 모델간의 성능 비교를 후속 연구로 제시하고 있다. 본 논문은 이러한 사실 을 바탕으로 [4]에서 제시한 두 가지 조건을 사용하여 두 모델의 성능상의 차이를 종합적으로 보인다. 특히 이 두 가 지 조건이 어떻게 두 모델간의 일배체형 조합의 정확도에 기여하는지를 보인다. 이를 위해 새로이 신경망을 설계하고 기존에 제시된 유전자 알고리즘 두 가지를 이용하여 두 모 델의 성능상의 차이를 보다 구체적으로 비교, 분석한다. 논문의 구성은 다음과 같다. 장에서는 문제에 대한 정의 를 보이고, 3장에서는 제시된 문제를 해결하기 위한 알고리 즘을 설계한다. 마지막으로 4장과 5장에서 실험결과에 대해 분석하고 결론을 맺는다.. 문제 정의 실험을 통해 한 쌍의 염색체로부터 길이가 인 m 개의 SNP 단편들을 얻었다고 하자. 각 SNP는 원형이거나 돌연 변이형 혹은 손실일 수 있으며, 각각, - 그리고 0으로 표 기한다. 이러한 단편들은 {, -, 0}로 구성된 m 행렬 M 로 표현되는데, 이를 SNP 행렬이라 부른다. 행렬의 각 행은 SNP 단편 f 에 해당하고 각 열은 단편들의 SNP 위

(그림 )은 3개의 SNP 위치를 갖는 염색체의 예 이다. 일배체형들은 {TGC}와 {AGG}이며, 이형은 SNP 위치 과 3, 동형은 SNP 위치 에서 나타난다. 일배체형의 차이는 개별 개체들의 발현 형질의 차이와 직 접적인 관련이 있는 것으로 밝혀져 있다. 특히 유전과 관련 이 있는 질병연구에서 중요한 의미를 갖고 있다.

3 일배체형 재조합을 위한 MCIH 모델과 WMLF/GI 모델의 정확도 비교 59 치에 해당한다. SNP 판독기계는 이러한 단편들의 SNP 값 에 신뢰도를 부여하는데 이는 SNP 값이 올바로 판독 되었 는지에 따라 0과 사이의 확률 값으로 나타낸다. SNP 값에 대한 신뢰도는 m 의 가중치 행렬 W 로 표현되고 행렬 의 원소 wj 는 행렬 M 의 원소인 SNP 위치 fj 의 값에 대한 신뢰도를 나타낸다. fj 가 손실이면 신뢰도를 0으로 한다. 서로 다른 값을 가진 SNP 위치는 가중치가 낮은 값 을 다른 값으로 바꾸면 적은 비용으로 일치시킬 수 있으므 로 두 단편 f 와 f j 의 SNP 위치 사이의 거리는 그들의 가중치를 사용하여 다음과 같이 정의한다. d( f k, f jk m( wk, w ) = 0 jk ),, f f 0, f k otherwse jk 0, ad f k f 만약 한쪽이 SNP 단편이 아니고 일배체형인 경우엔 SNP 단편의 가중치를 사용한다. 즉, d ( fk, h jk ) = wk 이다. SNP 단편 f = ( f,..., f ) 과 f j = ( f j,..., f j ) 사이 의 거리는 두 단편의 SNP 전체를 일치시키는데 드는 최소 가중치의 합으로 정의 한다. D( f, f ) d( f, f ) j k jk k = jk () = () 만약 D( f, f j) > 0 이면, 두 단편 f 과 f j 가 다른 염 색체에서 복제되었거나 SNP 판독에 오류가 있었음을 의미 하고 이런 경우를 충돌한다(cofct)라고 한다. 그렇지 않으 면 모든 SNP 단편들이 서로소인 두 집합으로 분리되고 집 합내의 모든 단편들 간에 충돌이 없음을 의미하는데 이때 SNP 행렬이 타당하다(feasbe)라고 한다. 일배체형 h 와 SNP 단편 f j 사이의 거리는 아래와 같이 정의한다. D( h, f ) d( h, f ) = (3) j k jk k = 그리고 (그림 )처럼 유전자형 g = ( g, g,..., g ) 에 대해 번째 SNP 위치가 모두 원형의 대립유전자를 가지면 를 g 에 부여하고 돌연변이형의 대립유전자를 가지면 -를 부 여한다. 만약 SNP 위치가 이형이면 0을 부여한다. 그리고 한 쌍의 일배체형 h 과 h 가 각 SNP 위치에 대해서 아래 의 조건을 만족하면 이 일배체형 쌍은 유전자형과 양립한다 (compatbe)라고 한다. f f f g g g =, =, = 0, h h h = h = h = h = = = or h = h = (4) MCIH 문제는 유전자형 정보를 갖는 SNP 행렬이 주어졌 을 때 행렬의 원소 값들을 최소 개수로 변경하여 두 집합이 타당하도록 분할하고 유전자형과 양립하는 두 일배체형을 결정한다. WMLF/GI 문제는 MCIH 문제에 서열판독기계의 성능에 따른 신뢰도를 추가하여 두 일배체형을 결정한다. 이에 대한 WMLF/GI 문제는 다음과 같이 정의한다[5]. 정의. WMLF/GI 문제 SNP 행렬 M 과 가중치 행렬 W 그리고 유전자형 g 가 주어지면, 가중치의 합이 최소 이면서 변경 후의 SNP 행렬이 타당 하고 유전자형과 양 립 하도록 SNP 행렬의 원소 값들을 에서 -로 혹은 그 반대로 변경하라. 즉, SNP 단편들을 최소의 가중치로 개별 원소들을 변경하여 집합내의 단편들끼리 상호 충돌이 없는 서로 소인 두 집합으로 분리하고 유전자형과 양립하도록 한 쌍의 일배체형을 결정하라. 3. WMLF/GI문제를 해결하기 위한 알고리즘 설계 3. 신경망을 이용한 일배체형 조합 문제 WMLF/GI 문제는 분류 문제와 유사하다. 즉 SNP 단편 들이 주어졌을 때 각 SNP 단편을 집합 내의 단편들끼리 상 호 충돌이 최소가 되도록 두 집합으로 분리하고 이 두 집합 으로부터 한 쌍의 일배체형을 결정한다. 신경망은 잡음이 많은 데이터와 훈련 받지 않은 데이터에 대해 분류 능력이 우수하다고 알려져 있으며 생물정보학 분야를 포함한 여러 분야에서 성공적으로 사용되고 있다. 신경망은 (그림 )처럼 3개의 계층(ayer)으로 구성된다. 입력계층에서 각 노드는 길이가 인 m 개의 SNP 단편들 로써 {, -, 0} 값으로 구성된 -차원의 벡터이다. 은닉계 층은 두 개의 노드를 가지며 각 노드는 한 쌍의 일배체형에 대응되는 단편들의 두 부분집합을 나타낸다. 출력계층은 하 나의 노드로 유전자형을 나타낸다. 신경망의 중요한 특징은 다음의 목적을 성취하기 위해 설계되었다. 목적. 최소화 여기서 = f C D( h, f ) (5) =,,..., m 이다. f = ( f, f,..., f m ) 의 분할 P = C, C ) 와 한 쌍의 일배체형, ) 에 속한 ( f 와 목적. 만족 또는 최소화 ( h h 에 대해 C h 사이의 전체 가중치의 합을 최소화 한다. z g, =,..., = (6) ( z g ), =,..., (7) =

서로 다른 값을 가진 SNP 위치는 가중치가 낮은 값 을 다른 값으로 바꾸면 적은 비용으로 일치시킬 수 있으므 로 두 단편 f 와 f j 의 SNP 위치 사이의 거리는 그들의 가중치를 사용하여 다음과 같이 정의한다.

4 60 정보처리학회논문지 B 제6-B권 제호(009.4) 3..3 오류 역전파 알고리즘을 통한 연결 가중치 갱신 모든 SNP 단편들을 전방향 처리를 통해 얻어진 h 과 h 사이의 거리에 의해 두 집합 P = ( C, C ) 으로 분류한 다. 만약 D(h, f ) < D(h,f ) 라면, f 는 C 에 분류되 며 그렇지 않으면 C 로 분류된다. 일배체형 h 과 SNP 단 편 f 사이의 거리는 다음과 같이 정의한다. (그림 ) 3계층의 신경망 실험을 통해 얻은 유전자형 Z = ( z, z,..., z ) 와 실제 유전자형 g = ( g, g,..., g ) 이 동일하거나 그 차를 최소 화 한다. 3.. 연결 가중치의 초기화 입력계층에서 은닉계층의 연결 가중치 W = ( wj ) 는 0 또는 의 임의의 값을 갖는다. 여기서 =, 이고 j,,..., m = 이다. 3.. 일배체형 생성을 위한 전방향 처리 전방향 처리는 은닉계층과 출력계층에 있는 각 노드의 입 력값과 출력값들의 계산에 의해 한쌍의 일배체형과 유전자 형을 생성하며 처리과정은 다음과 같다. ) 은닉계층의 입력값은 h, h 각각에 대해 X = ( x, x,..., x ) 와 X = ( x, x,..., x ) 이다. 각 노드의 입력을 계산하기 위해서 이 노드에 연결된 입력 을 해당 가중치와 곱한 후에 합한다. m xk = fk w, =,, k =,...,. = ) 은닉계층의 출력값은 한 쌍의 일배체형 h = ( h, h,..., h ) 과 h = ( h, h,..., h ) 이다. 은 닉계층은 입력값을 받아서 활성화 함수를 적용한다. 활성화 함수는 입력값의 범위를 -과 사이의 값으로 대응시키며 다음과 같다. F( xk ) =. + e (8) hk = λ x (9) D( h, f ) = k= +, s( x) =, d( s( h k x 0 x < 0. ), f k ), () 여기서 =, 이고 k =,..., 이다. 거리 d 는 식 ()에 의해 정의되었으며, 한쪽이 SNP 단편이 아니고 일배 체형이므로 둘 사이의 거리는 SNP 단편의 가중치를 사용한 다. 즉 d ( s( hk ), fk ) = wk 이다. 식 ()는 단편들의 부분집합 C 에 속하는 SNP 단편들과 일배체형 h 사이의 오류이며, 식 (3)은 실험을 통해 얻은 유전자형 Z = ( z, z,..., z ) 와 실제 유전자형 g = ( g, g,..., g ) 사이의 오류이다. 이들 오류를 최소화하기 위해 은닉계층과 출력계층 사이의 연결가중치를 갱신한다. Err _ h = ( h 연결가중치 W (t) f C k= k f =,, =,,... m () Err _ g = w ( t + ) = w ( t) ρ ( L k= k ) ( z k g k ) 의 갱신은 다음 식에 의해 계산한다. _ h + L. f k _ g ),, (3) (4) 3) 출력계층은 h 과 h 을 입력으로 받아 아래 식에 의 해 유전자형 Z = ( z, z,..., z ) 을 출력한다. w ( t + ) = w ( t) ρ ( L _ h + L _ g ), (5) z = h + h. (0) k k k 연결가중치 T = ( w, w,..., wm 에 대한 Err _ h w )

여기서 =, 이고 j,,..., m = 이다. 3.. 일배체형 생성을 위한 전방향 처리 전방향 처리는 은닉계층과 출력계층에 있는 각 노드의 입 력값과 출력값들의 계산에 의해 한쌍의 일배체형과 유전자 형을 생성하며 처리과정은 다음과 같다. ) 은닉계층의 입력값은 h, h 각각에 대해 X = ( x, x,..., x ) 와 X = ( x, x,.

5 일배체형 재조합을 위한 MCIH 모델과 WMLF/GI 모델의 정확도 비교 6 와 Err _ g _ h 는 = k 0 _ g = k 0 = = λ / [ h λ / [ z k k f g k k ] [ h ] [ h k k ] f k ] f, f, f k, f, f f C f C f C f C (6) (7) 3.0 GHz 와 GB RAM)에서 실험하였다. 정확도 R r (Recostructo rate)를 모델과 알고리즘의 성 능 평가치로 사용한다. 이 정확도는 다른 논문들[9,0,,3] 에서도 사용된 것으로 다른 모델이나 알고리즘과의 성능 비 교를 위하여 그대로 사용한다. 정확도는 다음과 같이 정의 한다. h = ( h, h ) 를 염색체에 대한 실제 일배체형이라 하고 h ˆ = ( hˆ, ˆ h ) 를 알고리즘에 의해 결정된 일배체형이라 하면 이다. 여기서, =,, =,,... m, ρ 는 학습률이며 나머 지는 신경망을 학습하기 위한 매개변수들이다. 3. 유전자 알고리즘 유전자 서열판독기계의 성능에 따른 신뢰도와 유전자형 내의 동형 분포율에 의해 한 쌍의 일배체형을 결정하는 문 제를 실험하기 위해 이전에 제안된 유전자 알고리즘을 간략 하게 제시한다[5]. 알고리즘 GAforHapotypeAssemby 입력: SNP 단편 행렬 M, 가중치 행렬 W, 유전자형 g 세대 크기 PS, 교배율 CR, 돌연변이율 MR, 최대 세대 생성 수 GN 출력: 한 쌍의 일배체형 h, h Beg 임의의 초기 세대 P0 생성, k = 0; 유전자형 g에 의해 초기 세대 수정 whe ( k < GN) do 세대 Pk 내의 각 개체들의 적응도 계산 ; 토너멘트 선택 연산자를 이용하여 Pk 세대에서 만큼의 개체들을 선택하여 P k + 세대에 편입; 룰렛휠 선택 연산자와 교배연산자를 사용하여 CR PS 만큼의 후손을 생성하여 P k + 에 추가; 새로 생성된 세대의 MR PS 개체에 대해 돌연 k = k+ ; ed do retur 적응도가 가장 큰 개체로 부터 결정한 한 ed 4. 실험 결과 및 분석 (그림 3) 유전자 알고리즘 개요 일배체형 조합을 위한 WMLF/GI 모델의 성능을 평가하 기 위해 실제 데이터와 임의 데이터를 사용하였다. 제안한 알고리즘은 C 언어로 구현하고 3비트 시스템(Petum 4, 정확도 Rr 는 m{ r + r, r R r ( h, hˆ) = + r ) (8) 이다. 여기서 r ˆ j= D( h, h j ), = j =, 로써 두 일 배체형 간의 해밍 거리를 말한다. 4. 임의 자료에 대한 실험 모델들의 성능을 비교하기 위해 길이가 =50인 0쌍의 종자(seed) 일배체형을 임의로 만들었다. 한 실험 개체의 SNP 행렬은 m =50개의 단편들로 구성했는데 이들은 한 쌍 의 종자 일배체형을 임의로 복사하여 만들었다. 모든 SNP 단편들에는 손실률( R m =0.3)에 의해 임의로 손실을 발생시 켰다. SNP 오류는 오류율( R e =0., 0., 0.5, 0.3, 0.35)에 따 라 SNP 단편들의 임의 위치에 -은 로, 은 -로 수정하 여 만들었다. 설계한 신경망 알고리즘의 매개변수들은 ρ = 0.03, λ = 0., L =0., L =0.8로 하였다. 앞에서 언급 한데로 일배체형 조합문제에 대해 오류율과 손실률이 높을수록 WMLF 모델이 MLF 모델 보다 정확성 이 높다. 유전형 정보를 추가한 MCIH 모델과 WMLF/GI 모델의 성능을 비교하기 위해 필요한 가정과 매개변수를 추 가하였다. WMLF 또는 WMLF/GI 모델은 유전자의 서열을 판독하는 기계가 판독에 대해 신뢰도를 부여한다는 사실을 전제하고 있다. 이때 판독 기계의 성능이 우수하다면 오류 가 있는 판독은 신뢰도를 낮게 부여하고, 오류가 없는 경우 에 대해서는 높은 신뢰도를 부여할 가능성이 크다. 따라서 기계의 성능에 따라 판독에 대한 신뢰도의 차이는 현실적인 가정을 해치지 않는다. 한편 유전자형 정보의 도입은 유전 자형이 가지고 있는 동형의 분포율에 따라 일배체형 조합의 정확성에 매우 큰 영향을 미친다. 본 논문에서는 판독에 있어 신뢰도의 차이로 대변되는 판 독기계의 성능이라는 가정과 유전자형 내의 동형의 분포율 이라는 매개변수를 이용하여 MCIH 모델과 WMLF/GI 모델 의 성능을 비교하였다. WMLF/GI 모델에서 판독기계의 성 능에 따라 신뢰도(0.9, 0.), 신뢰도(0.9, 0.5), 신뢰도(0.9, 0.8) 세가지로 실험하였다. 첫 번째 숫자는 판독이 정확한 경우

h = ( h, h ) 를 염색체에 대한 실제 일배체형이라 하고 h ˆ = ( hˆ, ˆ h ) 를 알고리즘에 의해 결정된 일배체형이라 하면 이다. 여기서, =,, =,,... m, ρ 는 학습률이며 나머 지는 신경망을 학습하기 위한 매개변수들이다. 3.

6 6 정보처리학회논문지 B 제6-B권 제호(009.4) 에 부여한 신뢰도의 평균이며, 두 번째 숫자는 그 반대의 신뢰도의 평균이다. (그림 4)와 (그림 5)는 신경망과 유전자 알고리즘[5]을 이 용하여 얻은 두 모델의 정확도로써 실험 개체들을 각각의 매개변수들에 따라 실험한 후에 정확도를 평균한 값이다. 신뢰도를 사용한 WMLF/GI 모델이 MCIH 모델 보다 높은 정확도를 가짐을 알 수 있다. 신뢰도(0.9,0.)이고 오류율이 0.3이내인 경우 신경망은 97%이상 그리고 유전자 알고리즘 (그림 4) 신경망을 이용한 동형 비율과 판독 기계의 성능에 따 른 정확도 비교 (동형 비율: 0%, 0%, 30%, 60%, 70%) (그림 5) 유전자 알고리즘을 이용한 동형 비율과 판독 기계의 성능에 따른 정확도 비교 (동형 비율: 0%, 0%, 30%, 60%, 70%)

신뢰도를 사용한 WMLF/GI 모델이 MCIH 모델 보다 높은 정확도를 가짐을 알 수 있다. 신뢰도(0.9,0.)이고 오류율이 0.

7 일배체형 재조합을 위한 MCIH 모델과 WMLF/GI 모델의 정확도 비교 63 (a) 신경망 (b) 유전자 알고리즘 (그림 6) MCIH모델과 WMLF/GI모델의 정확도 비교 은 99%이상의 정확도를 보였다. 오류율이 0.35인 경우 신경 망은 신뢰도를 사용하지 않은 MCIH 보다 5~0% 정도의 정 확도를 향상 시켰으며, 유전자 알고리즘은 동형의 비율이 0%일 때 MCIH 보다 5%이상의 높은 정확도를 보였다. 신 뢰도의 차이가 큰 경우, 즉 서열판독기계의 정확성이 높을 때 일배체형 결정의 정확도가 높음을 알 수 있다. 그리고 유전자형 정보가 정확도에 미치는 영향은 동형의 비율에 크게 좌우되며, 동형의 비율이 낮으면 상대적으로 서열판독기계의 성능이 일배체형 결정에 영향이 커진다는 사실을 알 수 있다. 특히 유전자 알고리즘을 이용한 실험에 서는 동형의 비율이 낮을수록 상대적으로 기계 성능의 영향 력이 커지고 오류율이 높을수록 일배체형 결정의 정확도의 차가 커짐을 알 수 있다. 하지만 신경망의 경우는 유전자형 내의 동형에 보다 민감하게 반응하는 반면 판독기계의 성능 에는 크게 반응하지는 않는 것으로 나타났다. 4. 염색체 5q3에 대한 실험 Day등[]이 공개한 자료를 실험 자료로 사용하였다. 공 개한 원자료는 부-모-자식 염색체 5q3의 03개 SNP 위치 에 대한 유전자형들로 구성되어 있다. 부모의 유전자형과 가계도 정보로부터 총 58쌍의 일배체형을 도출하였고 양 대립유전자를 정확히 결정할 수 없는 경우에는 손실로 처리 하였다. 58쌍의 일배체형 중 손실율이 0%를 넘는 것들은 제거하고 나머지 47쌍의 일배체형을 실험 자료로 삼았다. 실험 개체를 생성하는 데는 m =50개의 SNP 단편들로 SNP 행렬을 구성하였다. 생성한 자료에 대한 MCIH 모델과 WMLF/GI 모델의 정 확도를 (그림 6)에서 비교 하였다. 실제 염색체 5q3에 대한 일배체형 58쌍의 동형 비율은 평균 76.5% 정도였다. SNP 판독 기계 성능에 따른 신뢰도 및 매개변수들은 임의 자료 와 동일하게 실험하였다. 실제 데이터에서도 임의 데이터와 마찬가지로 WMLF/GI 모델이 전체적인 우위를 보였다. 오 류율이 0. 이내로 낮은 경우 두 모델의 정확도는 비슷하나, 오류율이 큰 경우 SNP 단편들에 신뢰도를 부여하는 것이 정확도를 개선하는데 더 효과적임을 알 수 있다. 5. 결 론 일배체형 조합 문제는 생물정보학 분야에서 중요한 문제 중 하나이다. 본 논문에서는 일배체형 조합 문제를 보다 효 율적으로 해결하기 위해 WMLF 모델에 유전자형 정보를 도입한 WMLF/GI 모델과 MCIH 모델을 비교, 분석하였다. 현재 유전자형을 도입한 두 모델 사이의 성능에 대한 종합 적인 비교가 이루어져 있지 않다. 따라서 본 논문에서는 두 모델의 성능 비교를 위해 유전자형 내의 동형의 분포율이라 는 매개변수와 신뢰도의 차이로 대변되는 유전자 서열판독 기계의 성능이라는 가정을 이용하였다. 이러한 두 가지 조 건하에 새로 설계한 신경망과 기존에 제시된 유전자 알고리 즘을 이용하여 일배체형 조합문제의 정확도를 비교, 분석하 였다. MCIH 모델 보다 신뢰도를 사용한 WMLF/GI 모델이 일배체형 조합문제에서 전체적으로 높은 정확도를 보였다. 유전자형 정보가 일배체형 조합의 정확도에 미치는 영향은 동형의 비율에 크게 좌우되며, 동형의 비율이 낮으면 상대 적으로 신뢰도의 영향력이 커지므로 서열판독기계의 성능이 일배체형 결정에 큰 영향을 미쳤다. 일배체형 조합 문제는 복잡도면에서 어려운 문제로서 앞 으로도 이를 해결할 여러 접근 방법에 대한 연구가 요구된 다. 또한 실제 현장에서 제기되는 문제들을 반영한 새로운 모델과 문제의 개발도 필요하다. 참 고 문 헌 [] R. Cbras, L. V. Ierse, S. Kek, ad J. Tromp, O the compexty of Severa Hapotypg Probem, 5th Workshop o Agorthms Boformatcs(WABI), LNBI 369, pp. 8-39, 005. [] M. J. Day, J. D. Roux, S. F. Schaffer, T. J. Hudso, ad E. S. Lader, Hgh-resouto hapotype structure the huma geome, Nature Geetcs 9, pp.9-3, 00. [3] H. J. Greeberg, W. E. Hart, ad G. Laca, Opportutes

그리고 유전자형 정보가 정확도에 미치는 영향은 동형의 비율에 크게 좌우되며, 동형의 비율이 낮으면 상대적으로 서열판독기계의 성능이 일배체형 결정에 영향이 커진다는 사실을 알 수 있다.

8 64 정보처리학회논문지 B 제6-B권 제호(009.4) for Combatora Optmzato Computatoa Boogy, INFORMS Joura o Computg Vo.6, No.3, pp.- 3, 004. [4] D. E. Godberg, Geetc Agorthms serarch, Optmzato ad Mache Learg, Addso-Wesey, 989. [5] S. H. Kag, I. S. Jeog, M. H. Cho, ad H. S. Lm, Hapotype Assemby from Weghted SNP Fragmets ad Reated Geotype Iformato, Froters Agorthmcs Workshop(FAW) 008, LNCS 5059, pp.45-54, 008. [6] R. Rzz, V. Bafa, S. Istra, ad G. Laca, Practca Agorthms ad Fxed-Parameter Tractabty for the Sge Idvdua SNP Hapotypg Probem, d Workshop o Agorthms Boformatcs(WABI), LNCS 45, pp.9-43, 00. [7] J. C. Stephes, et a, Hapotype varato ad kage dsequbrum 33 huma gees, Scece, Vo.93, pp , 00. [8] J. D Terwger ad K. M Wess, Lkage dsequbrum mappg of compex dsease: fatasy or reaty?, Curret Opo Botechoogy, Vo.9, No.6, pp , 998. [9] Y. Wag, E. Feg, R. Wag, ad D. Zhag, The hapotype assemby mode wth geotype formato ad teratve oca-exhaustve search agorthm, Computatoa Boogy ad Chemstry, Vo.3, pp.88-93, 007. [0] R. S. Wag, L. Y. Wu, Z. P. L, ad X. S. Zhag, Hapotype recostructo from SNP fragmets by mmum error correcto, Boformatcs, Vo., No.0, pp , 005. [] X. S. Zhag, R. S. Wag, L. Y. Wu, ad L. Che, Modes ad Agorthms for Hapotypg Probem, Curret Boformatcs, Vo., pp.05-4, 006. [] X. S. Zhag, R. S. Wag, L. Y. Wu, ad W. Zhag, Mmum Cofct Idvdua Hapotypg from SNP Fragmets ad Reated Geotype, Evoutoary Boformatcs Oe, Vo., pp.7-80, 006. [3] Y. Y. Zhao, L. Y. Wu, J. H. Zhag, R. S. Wag, ad X. S. Zhag, Hapotype assemby from aged weghted SNP fragmets, Computatoa Boogy ad Chemstry, Vo.9, pp.8-87, 005. [4] 강승호, 정인선, 최문호, 임형석, 신뢰도를 가진 SNP 단편 들과 유전자형으로부터 일배체형 조합, 정보과학회논문지, 제35권 제호, pp , 008. 정 인 선 e-ma:sjug0@hotma.com 00년 여수대학교 전산학과(학사) 006년 전남대학교 전산학과(석사) 006년~현 재 전남대학교 전산학과 박사 과정 관심분야:생물정보학, 알고리즘, 인공지 능 등 강 승 호 e-ma:ksto@gma.com 994년 전남대학교 전산학과(학사) 003년 전남대학교 전산학과(석사) 003년~현 재 전남대학교 전산학과 박사 과정 관심분야:생물정보학, 알고리즘, 인공지 능 등 임 형 석 e-ma:hsm@choam.ac.kr 983년 서울대학교 컴퓨터공학과(학사) 985년 한국과학기술원 전산학과(석사) 993년 한국과학기술원 전산학과(박사) 996년~997년 미국 Purdue대학 방문교수 987년~현 재 전남대학교 전자컴퓨터공 학부 교수 관심분야:알고리즘, 그래프이론, 생물정보학 등

H. Kag, I. S. Jeog, M. H. Cho, ad H. S. Lm, Hapotype Assemby from Weghted SNP Fragmets ad Reated Geotype Iformato, Froters Agorthmcs Workshop(FAW) 008, LNCS 5059, pp.45-54, 008. [6] R. Rzz, V.

회원번호 대표자 공동자 KR000****1 권 * 영 KR000****1 박 * 순 KR000****1 박 * 애 이 * 홍 KR000****2 김 * 근 하 * 희 KR000****2 박 * 순 KR000****3 최 * 정 KR000****4 박 * 희 조 * 제

회원번호 대표자 공동자 KR000****1 권 * 영 KR000****1 박 * 순 KR000****1 박 * 애 이 * 홍 KR000****2 김 * 근 하 * 희 KR000****2 박 * 순 KR000****3 최 * 정 KR000****4 박 * 희 조 * 제 KR000****4 설 * 환 KR000****4 송 * 애 김 * 수 KR000****4