유사성 검색 - 1 유전체 정보 의학 2006, 4.17 Kim Do Kyoon

Outline 서열 분석의 문제 동적 프로그래밍 (Dynamic programming) 전역 정열 (Global alignment) 국소 정열 (Local alignment) 데이터베이스 검색

서열 분석의 문제 서열 분석의 목적 분자생물학의 경험적 지식 사용 두 분자가 유사한 서열을 가지면, 진화적인 관계나 물리 화학적인 제약 때문에 유사한 3차원 구조와 비슷한 생물학적 기능을 갖기 쉽다 뉴클레오티드 또는 아미노산 서열로 쓰여진 고차원의 구조와 기능적인 정보를 밝혀내기 위함 구조적, 기능적 속성으로 확장 될 수 있는 서열 특징을 찾고자 함

서열 분석의 문제 서열 분석 방법 표 3-1 데이터 조직화 방법 서열 분석에 사용되는 계산법 유사성 검색 1차 데이터베이스 (서열 데이터베이스 또는 3차원 구조 데이터베이스)에 저장 된 알려져 있는 데이터들과 비교를 하는 것

서열 분석의 문제 서열 분석 방법 3. 서열 해석에 대한 두 가지 접근법 서열 유사성 검색 또는 상동성 검색 2) 모티브 검색 3. 서열 해석에 대한 두 가지 접근법 서열 유사성 검색 또는 상동성 검색 2) 모티브 검색 모든 형태의 기능 속성에 대한 경험적인 법칙들을 만드는 것이 가능 하지 않음 여전히 가장 선호 되는 접근 방법

서열 분석의 문제 서열 정렬 Certain Criteria required! 서열의 유사성을 찾는 과정 진화론적으로 삽입, 삭제, 치환 과정 거침 두 개의 서열이 비교될 때, 이들 사이의 유사 관계를 잘 나타내는 최적의 정렬을 만드는 것이 필요 Alignment1 Good? Alignment2 Bad? ATTGGCCA | | | | A--GG--A ATTGGCCA | | AGG----A Certain Criteria required!

서열 분석의 문제 서열 정렬 최적의 서열 정렬을 얻는 문제는 전반적인 유사성을 나타내는 점수 함수(Score Function)를 최적화 하는 것 공백은 일치하는 문자 쌍의 수를 최대화하거나, 치환, 그리고 삽입/삭제와 같은 편집 연산의 수를 최소화 하기 위해서 추가 Score Function은 아미노산 또는 뉴클레오티드들 사이의 유사성 측정값과 삽입 및 삭제에 대한 벌점(penalties)을 통해 계산 서열 정렬법 Global 정렬 & Local 정열: 전체 / 부분적인 유사 영역 비교 Pair-wise 정렬 & Multiple 정렬: 두 개 / 세 개 이상의 서열 정렬 3차원 정렬: 두 가지 단백질의 3차원 구조 비교 3차-1차 정렬: 3차원 구조 라이브러리에 대한 아미노산 서열 비교 Pathway alignment: 생화학적 경로 비교

Dynamic Programming Sequence Alignment 예제 서열 상동성 비교 문제: 서열 S1과 서열 S2간의 진화거리는 (insertion, deletion, mutation)라는 편집작업을 통해서 서열 S1을 서열 S2로 변환시키는 최소편집거리 구하는 문제 Ex) S1 = “BLUE”, S2 = “BILE” “BLUE” -> (series of insertion or deletion or mutation) -> “BILE” 진화 거리가 2인 두 해 1) 한 번의 insertion, 한 번의 deletion (편집거리 = 2) B I L – E B - L U E 2) 두 번의 mutation (I와 L, L과 U) (편집거리 = 2) B I L E B L U E

Dynamic Programming 동적 프로그래밍 알고리즘 B I L E 1 2 3 4 U D(i,j) 최적화를 위한 일반적인 알고리즘 서열 정렬의 개념을 이해하기 위한 가장 기본적인 알고리즘 B I L – E B – L UE B I L E B LU E D(i,j) B I L E 1 2 3 4 U

Dynamic Programming 동적 프로그래밍의 장점 서열정렬: 수많은 해결책 중 하나를 찾는 것이기 보다 주어진 조건에 따라서 모든 경우 중 최상의 해결책을 찾는 것 검색 트리: 가지를 칠 수 있는 모든 가능한 길의 점수를 내어 최적의 노드만을 검색 대부분의 가지들을 점수 함수에 따라서 시스템적으로 잘라냄 (점수가 가장 큰 가지만을 남기고 나머지 가지들을 검색 하지 않음) 효율적으로 모든 가능성 계산

Global Alignment 최적 되어야 하는 점수 함수를 이용하여 전체 서열 비교 점수 함수: 정렬의 각각의 위치에서의 가중치 값들의 합 가중치 뉴클레오타이드 일치 또는 불일치에 따라 일정한 값 아미노산 미묘한 서열의 유사성 반영 진화적 분화 정도에 따른 돌연변이 빈도수 반영 (ex. PAM-250)

Global Alignment Ws,t: 문자 s를 문자 t로 또는 그 반대로 치환하기 위한 가중치 d: 하나의 공백 문자에 대한 가중치 => 대각선, 수평, 수직의 3가지 가능성 D[i][j]= max(D[i-1][j-1] + Ws[i],t[j] , D[i-1][j] + d, D[i][j-1] + d) 일정한 공백 벌점과 점수 행렬 D 길이 2의 공백에 대한 벌점은 길이 1의 공백에 대한 벌점의 두 배 길이 2의 공백을 두 개의 사건의 합성으로 봄 D[i][j]= max[D[i-1][j-1] + Ws[i],t[j] , max(D[i-k][j] + dk), max(D[i][j-k] + dk)] dk= 길이 k 인 공백에 대한 벌점 공백 벌점을 길이에 대한 함수로 나타내는 점수 행렬 D 연속적인 문자들의 공백은 두 개의 사건이 아닌 하나의 사건

Global Alignment 공백 벌점: a + bk D[i][j]= max[(D[i-1][j-1] + a , D[i-1][j], D[i][j-1] + a)] + b 공백 벌점: a + bk 길이가 미치는 영향을 초기 부분(공백 개시, gap opening)과 연장 부분(공백 연장, gap extension)으로 단순화 전역 정렬(Global alignment) - 경로 행렬의 왼쪽 위에서 오른쪽 아래까지 확장되는 최적 경로(optimal path)

Local Alignment 경로 행렬 내의 보다 짧은 부분에 국한되는 부분 정렬 x (a) 전역 대 전역 (b) 전역 대 지역 0 0 . . . . . . 0 (a) 수평 서열의 첫 번째 문자와 수직 서열의 첫 번째 문자는 정렬의 출발점 (전역 정렬) (c) 지역 대 지역 (b) 수평 서열 내의 어떤 문자도 아무런 벌점 없이 출발점(수평 서열 내의 여러 부분 영역에서 수직 서열과 유사한 다중 일치를 발견 하는 데 유용 0. 0 0 . . . . . . 0 0 . . . 0 . . . . . . . . . . 0 (c) 지역 대 지역 수평 , 수직 서열 내의 어떤 문자도 아무런 벌점 없이 출발점 최적의 지역 정렬을 찾기 위해 두 경로 행렬의 논리적 곱 => 행렬의 가장 자리에서 0의 값들을 사용 하는 것보다 행렬 내에서 0의 값을 혼합 하는 것이 필요 최적의 국소 정렬 (ex. Smith-waterman) - 점수 값이 음수: 그 때까지의 경로는 최적의 경로에서 제외되면서 적합도가 큰 클러스터가 분리 - 점수 값이 양수: 이미 존재하는 클러스터를 확장하거나 새로 시작

데이터베이스 검색 질의 서열을 데이터베이스내의 서열들과 비교하기 위하여 국소 정렬을 통한 유사 서열 검색 순차적 처리 각 원소는 한 행에서 왼쪽에서 오른쪽 방향으로 계산 각 행은 위에서 아래 방향으로 계산 한 원소를 계산하기 위해서는 앞 원소의 값이 필요 앞의 계산이 완료된 후 다음 원소의 계산이 순차적으로 수행 병렬적 처리 계산 순서가 반대 대각선 방향 모든 원소들이 미리 계산되므로 각 점수 행렬 D의 계산은 동시에 수행 반대 대각선의 길이가 1에서 최대 길이로 변화하므로 효과적이지 못함 특별한 하드웨어를 가지는 컴퓨터에서 구현 됨

동적 프로그래밍의 장단점 시간을 많이 소요 아미노산 서열 분석에서는 미묘한 유사성에 대해서도 아주 민감하게 반응하여 가장 정확한 해결책 뉴클레오티드 서열에서는 두 뉴클레오티드의 유사성보다는 동일성을 판별하므로 별 가치 없음 대중적인, 데이터베이스 검색에 효율적인 알고리즘: FASTA, BLAST - 최적의 정렬을 보장 못하지만 데이터베이스 검색에 있어 효율적이 알고리즘