단백질 보존 지역간의 연관성 탐사

이도헌, 김정자

전남대학교  컴퓨터 정보학부

Exploring Association Rules among Conservative Regions of Proteins

Doheon Lee, Jungja Kim

School of Computer and Information, Chonnam National University

서론

바이오정보학(bioinformatics)은 생물학, 특히 유전체 연구 분야에서 발생하는 데이터를 처리하기 위한 제반 컴퓨터 기술을 의미한다 [1,2,3,4,5,6]. 다양한 기능 유전체학의 접근 방법 중, 단백질 수준에서 유전체를 바라보는 연구는 신진대사 기능과 암호 체계들이 DNA나 RNA 수준보다는 명확하기 때문에 최근 가장 주목받는 분야의 하나이다 [3,6].

본 논문에서는 데이터 마이닝에서 연구된 연관 규칙 탐사 기법을 이용하여 단백질 서열의 집합에서 잘 보존된 단백질 영역을 찾고 이들간에 존재하는 연관성을 탐사하기 위한 방법을 제안한다. 예를 들어 그림 1과 같이 하나의 단백질 서     열에서 ADDE 와 PQSRS 부서열 이     나타나면 대부분 FGKLL 부서열도     함께 나타나는 것을 발견할 수      있으며 이는 {adde, pqsrs} □      {fgkll}라는 서열 연관규칙의 형

그림 1. 단백질 보존 지역 간의 연관성             태로 표현할 수 있다.  생물학적                                               으로 이와 같은 영역을 모티프 (motif)라 하며 잘 보존된(Conservative) 단백질 영역으로서 그 지역들로 인하여 단백질의 2차, 3차 구조에 대한 유용한 단서를 제공하고 이를 통해 단백질의 기능예측을 가능하게 한다. 이러한 관찰에 근거하여 부서열 ADDE, PQSRS와 부서열 FGKLL 간에 상호작용과 해당 기능과의 연관성에 대한 정교한 생물학적 가설을 세우고, 실험을 통해 검증할 수 있게 된다. 이처럼 발견된 서열 연관 규칙은 실험 대상으로 적합한 가설을 선정하는데 유용할 뿐 아니라, 과거에는 전혀 고려하지도 않았던 새로운 발상의 전환을 가능케 할 수 있다.

서열 연관규칙

1. 서열 연관 규칙  (Sequence Association Rule)

서열 연관 규칙은 임의의 길이를 가진 서열간의 연관성을 나타내는 규칙이다.

정의 1. 서열 연관 규칙(sequence association rule)

주어진 기호의 집합 □의 원소로 구성된 모든 가능한 서열(sequence)의 집합을 □라고 할 때, 서열 연관 규칙(sequence association rule)은 다음과 같이 정의된다.

{s1, s2, ... , sm-1} => sm

단, 1 □ i □ m인 모든 i에 대하여, si ∈ □. 이 때, si를 해당 서열 연관 규칙의 항목 서열(item sequence)이라고 부른다. □

다음은 탐사된 규칙들이 어느 정도 유용한가의 타당성을 평가하기 위한 척도로서 지지도(Support)와 신뢰도(Confidence)를 정의한다.

정의 2. 서열간의 중첩관계

서열 s의 길이와 i번째 원소를 각각 len(s), s[i]라고 표시하자. 서열 s1와 s2에 대해,

s1[1] = s2[k+1] ∧ s1[2] = s2[k+2] ∧ ... ∧ s1[len(s1)] = s2[k+len(s1)]

를 만족하는 k가 하나 이상 존재하면, s1은 s2에 포함된다고 하고, s1 ⊆ s2라고 표시한다.

이 때, s2 상에서 s1이 나타나는 위치를 표시하기 위하여 다음과 같은 오프셋 집합(Offset Set)을 정의한다.

Offset(s1 | s2) = {(begin, end) | s1[1] = s2[k+1] ∧ s1[2] = s2[k+2] ∧ ... ∧ s1[len(s1)] = s2[k+len(s1)] ∧ begin = k+1 ∧ end = k + len(s1)}

s1 ⊆ p, s2 ⊆ p를 만족하는 세 개의 서열 s1, s2, p가 있을 때,

～(begin1, end1) ∈ Offset(s1 | p), ～(begin2, end2) ∈ Offset(s2 | p) (end1 < begin2 or end2 < begin1)

을 만족하면, s1과 s2는 p에 대하여 중첩되지 않는다고 정의한다. □

정의 3. 서열 연관 규칙의 지지도(support)

주어진 서열의 집합 P 에 대한, 서열 연관 규칙 {s1, s2, ... , sm-1} => sm 의 지지도는 다음과 같이 정의된다.

Support({s1, s2, ... , sm-1} => sm | P) = |{p | p ∈ P ∧ {s1, s2, ... , sm} ∠ p}| / |P|

단, 1 □ i □ m인 모든 i에 대하여, si ⊆ p이고, {s1, s2, ... , sm}에 속하는 모든 서열쌍이 p에 대하여 중첩하지 않으면, {s1, s2, ... , sm} ∠ p 가 성립한다. □

정의 4. 서열 연관 규칙의 신뢰도(Confidence)

주어진 서열의 집합 P 에 대한, 서열 연관 규칙 {s1, s2, ... , sm-1} => sm 의 신뢰도는 다음과 같이 정의된다

confidence({s1, s2, ... , sm-1} => sm | P) =

|{p | p ∈ P ∧ {s1, s2, ... , sm} ∠ p}|  /  |{p | p ∈ P ∧ {s1, s2, ... , sm-1} ∠ p}|

단, 1 □ i □ m인 모든 i에 대하여, si ⊆ p이고, {s1, s2, ... , sm}에 속하는 모든 서열쌍이 p에 대하여 중첩하지 않으면, {s1, s2, ... , sm} ∠ p 가 성립한다.□

2. 서열 연관 규칙 탐사 단계

서열 연관 규칙에 적용하는 입력 데이터는 특정 종들의 단백질 서열 데이터를 대상으로 한다. 단백질은 20종류의 아미노산으로 구성되므로, 특정 단백질은 20가지 알파벳의 문자 스트링의 조합으로 해석한다. 서열 연관 규칙의 탐사과정은 다음과 같다. 단계1에서 빈발 서열 집합을 찾는다. 단계2에서는 규칙을 구성하기 위한 빈발 부 서열 항목 조합을 구한다. 각 후보 서열 항목 생성 전에 부분집합과 중첩문제를 해결하여 선택된 빈발 서열 항목으로만 구성된 규칙조합을 추출한다. 단계3에서 일정 지지도와 신뢰도 이상의 규칙만을 생성하고, 마지막으로 단계4에서는 규칙들간에 포함관계에 있는 규칙들은 제거하여 요약된 규칙을 보인다. 그림 2의 단백질 데이터를 받아들여 서열 지지도 30%일 때 생성된 빈발 부서열 집합들은 그림 2와 같고 그림 3은 최종적으로 발견된 규칙의 예이다.

[[[  1 's Frequence Set]]]

A(   9),C(   3),D(   9),E(   9),F(   8),G(   6),H(   8),I(  10),K(   9),L(  10),M(   7),N(   9),P(   9),

Q(   6),R(   9),S(  10),T(   9),V(   9),W(   6),Y(   6),

[[[  2 's Frequence Set]]]

AE(   3),AL(   3),AP(   6),DI(   5),EL(   3),FK(   3),FS(   3),HS(   3),HT(   5),IL(   5),KA(   4),KL(   4),

KY(   3),LA(   5),LK(   7),LN(   4),LS(   4),LT(   3),MD(   5),MM(   5),NR(   4),NT(   3),PH(   5),QL(   3),

RL(   3),RS(   5),SD(   4),SL(   3),SR(   3),SS(   3),TN(   3),

[[[  3 's Frequence Set]]]

APH(   5),DIL(   5),LKA(   3),LSR(  3),MDI(   5),MMD(   5),MMM(   5),PHT(   5),SRS(   3),

[[[  4 's Frequence Set]]]

APHT(   5),LSRS(   3),MDIL(   5),MMDI(   ,MMMD(   5),

[[[  5 's Frequence Set]]]

MMDIL(   5),MMMDI(   5),

[[[  6 's Frequence Set]]]

MMMDIL(   5),

그림 2. 빈발 부서열 집합

.

MMMDIL <- A D H I K L R S T AP HT (100.00 50.00)

RS <- A E H I K L M N P R S T (100.00 50.00).

APHT <- A D H I K L M R S T IL MD MM (100.00 50.00)

M <- A D H I K L R S T AP HT IL MD MM (71.43 50.00)

AP <- A D H I K L M R S T HT IL MD MM (83.33 50.00).

그림 3.  발견 규칙 예

실험

본 절에서는 제안한 알고리즘의 실험 결과를 제시한다. 알고리즘은 C 언어로 구현하였으며 실험 환경은 RAM 512M, HDD 40G, Pentium 933 프로세서를 탑재한 Linux server 에서 실험하였다. 데이터는 가장 많은 서열 정보를 보유하고 있는 SWISS-PROT 데이터 베이스로부터 추출한 단백질 서열 데이터를 가지고 지지도와 신뢰도를 변화하면서 실험을 수행하였다. 그림 4는 지지도의 변화에 따르는 발생 규칙 수의 분포이다. 일반적으로 10% 미만을 지지도 임계값으로 부여하는 트랜잭션 연관 규칙의 경우와는 달리 서열 연관 규칙의 경우에는 주어진 단백질 집단에 속하는 상당히 많은 수의 단백질에서 공통성이 나타나야만 생물학적으로 유의할 만한 패턴이라고 간주할 수 있다. 따라서 본 실험에서는 최소 지지도 임계값을 50% 이상으로 설정한다. 알고리즘의 수행에 있어서 매개변수의 역할은 여러 관점으로 해석할 수 있다. 지지도에 따르는 발생 규칙수 의 변이들은 낮은 지지도일수록 많은 후보 항목의 생성으로 인해 생성된 규칙은 많지만 더 많은 경우의 서열의 연관성을 보인다. 서열문제의 경우 완전한 매칭이 되지 않더라도 같은 실험 결과를 보인다면 동일 종이나 같은 기능을 수행할 것이라 예측한다. 높은 지지도와 신뢰도에 의해 생성된 규칙 조합은 타당성이 있는 의미있는 규칙임을 의미한다. 그림 5는 지지도별 신뢰도에 따르는 수행시간의 분포이다. 지지도 60%이하에서는 큰 편차를 보이며 70%□90%의 변이는 거의 유사한 분포를 보인다.

그림 4. 신뢰도에 따르는 지지도별 발생규칙수

그림 5. 지지도별 (신뢰도|수행시간)

결과 및 토론

본 논문에서는 단백질 서열 분석을 통하여 그들 부 서열간에 존재하는 관련성을 탐사하는 서열 연관 규칙 알고리즘(SARA)을 제안하였다. 특정 단백질 서열에 거의 항상 함께 나타나는 부서열의 조합은 단백질 기능 분석의 중요한 단서가 된다. 즉 단백질 부 서열간의 동시출현(co-occurrence)은 특정 단백질의 2, 3차원 구조, 특정 핵산 서열과의 바인딩(binding), 특정 단백질과의 상호 작용 등의 기능을 밝히는 출발점으로 생각 할 수 있다. 기존 Apriori 알고리즘은 단일 원자 항목 단위의 트랜잭션 데이터를 대상으로 그들 간의 연관성을 탐사하였다. 그러나 제안하는 서열 연관 규칙 알고리즘에서는 단일 항목에 대응하는 한 문자 이상의 조합으로 구성된 서열 데이터이기 때문에 서열의 중복을 인정하여야 한다. 이외에도 규칙을 구성하는 부 서열 항목들간의 중첩 문제를 각 단계별 후보 항목 생성 단계 전에 걸러냄으로써 생물학 연구에 필요한 정확한 규칙 생성을 유도하였다. 마지막 단계에서는 최종 탐사된 규칙들에 대해서 규칙간에 포함되어지는 부 규칙들은 제거함으로써 의미있는 규칙들로 집약하였다.

참고 문헌

[1] R. Hofestaedt, "Computer science and biology," BioSystems 43, pp.69-71, 1997.

[2] Rebhan M, Chalifa-Caspi V, Prilusky J, Lancet D, "GeneCards:a novel functional genomics compendium with automated data mining and query reformulation support," Bioinformatics, 14(8), August, pp.656-664, 1998.

[3] Setubal  J,  Meidanis  J,   Introduction  to Computational Molecular Biology, Boston, MA:PWS Publishing Company, July 1997.

[4] Alvis Brazma, Inge Jonassen, Ingvar Eidhammer, David Gilbert, Approaches to the automatic discovery of pattern biosequences, Journal of Computational Biology, November 5, 1997.

[5] Luke   Alphey,  DNA  SEQUENCING  from experimental methods to bioinformatics, School of Biological Sciences, The University of Manchester, Manchester, UK, BIOS Scientific Publishers, 1997.

[6] Steven  L. Salzberg,  David B  Searls and Simon Kasif, Computational Methods in Molecular Biology, Elsevier Science B.V., 1998.