유사성 검색 분자유전체의학 김윤경

계통발생분석 (Phylogenetic Analysis) SA (simulated annealing) 유전자 알고리즘 CONTENTS FASTA 알고리즘 BLAST 알고리즘 통계적 유의성 다중정렬 계통발생분석 (Phylogenetic Analysis) SA (simulated annealing) 유전자 알고리즘

FASTA 알고리즘 유사성 검색에 있어 처음으로 널리 사용된 알고리즘 "words"라는 "서열과일치되는 작은 부분" 을 찾음으로서 최적의 부분정렬을 검색하는 프로그램 휴리스틱 (heuristic) 알고리즘 사용 단백질 서열간의 비교를 위해 제작되었지만 염기 서열간의 비교도 가능  염기 서열 데이터베이스를 6 frame으로 translation하여 입력한 단백질 서열과 비교 하는데 이 기능은 임의의 단백질 서열과 EST 데이터베이스를 검색하는데 좋은 방법

Heuristic 알고리즘 Heuristic : 정보가 완전하지 않은 상황에서 노력을 통해서 시행착오 (trial and error) 를 거쳐, 또는 경험을 통해서 주먹구구식의 규칙 (Rule of Thumb) 으로 지식을 알게되는 과정 Heuristic 알고리즘 이란, 빠른시간안에 답을 찾는건데 이게 불가능할 경우, 문제가 너무 커서 오래 걸린다거나(time complexity) 시간이 해결되도 그걸 저장할수 있는 공간이 부족할 때(space complexity) 하나 또는 둘다 포기하고 풀어내는 알고리즘

FASTA 알고리즘 - 점 행렬(dot matrix)의 특성을 구체화하기 위해서 고안 (1) - 점 행렬(dot matrix)의 특성을 구체화하기 위해서 고안 - 두 서열간의 dot blot을 그림으로서 비교를 시작 - Dot blot에서 일치하는 가진 부분은 대각선으로 표시 하고 그려진 대각선들의 합을 계산 - 후보 일치 부분을 포함하는 대각선을 빠르게 검색한 후 행렬 전체 영역보다는 제한된 영역에서 적용 가능

FASTA 알고리즘 대각선분들의 후보를 최초로 검색할 때 해슁을 이용 해슁(hashing) : 해쉬 테이블로 불리는 특정 검색 테이블 을 사용해서 데이터 아이템을 빠르게 검색하기 위한 구조 -점 행렬 : 수평질의 서열이 수직 데이터베이스 서열과 비교 될 때 nucleotide가 일치되는 위치 -해쉬 테이블 : 질의 서열내에 있는 모든 문자들에 대해서 데이터 베이스내의 문자들을 비교 하는 작업과정에서 전처리를 나타냄 네 가지 뉴클레오티드의 위치를 포함 점 행렬에 점을 추가 하려면 해쉬테이블에 있는 대응 문자 값만을 살피는 것으로 충분

FASTA 알고리즘- hashing 질의 서열과 서열 데이터베이스 양쪽에 들어 있는 짧은 서열(ktup; k개의 문자)을 탐색 (2) 입력한 서열로부터 한개 (ktup=1) 혹은 두개 (ktup=2)의 단백질 서열 (혹은 3개 혹은 6개의 염기서열) 로 이루어진 "단어 (ktup)" 들의 조합을 만듬 그리고 데이터베이스의 임의의 한 서열에서 각 단어들과 일치하는 단어들을 찾아내어 각각의 단어들을 연결하는 대각선을 만든다. 이때 중복된 단어들 제거 (3) 점수가 높은 대각선 부분 10개를 선택해 치환행렬을 이용하여 score들을 다시 계산 이때 가장 큰 값을 가진 부분을 "init1" 이라 정의 (4) gap을 허용하여 몇몇의 high-scoring 대각선 부분들을 합치고 가장 높은 점수를 initn이라고 정의 2개 문자키 (16배), 3개 문자키 (64배) 빠른 검색 가능 문자수의 기본 값  nucleotide 서열 : 6  amino acid 서열 : 2

FASTA 알고리즘 - 특징 FASTA ktup은 BLAST의 워드보다 짧으며 통상적으로 단백질에 대해서는 1 혹은 2, 핵산에 대해서는 4 혹은 6의 값 - 높은 ktup값 적용 - 속도는 빠르나 거짓 양성 결과 양상 가능 - 낮은 ktup값 적용 - 시간이 걸림, 민감한 탐색 가능

FASTA 알고리즘 – Program 의 종류 tfasta : 입력한 단백질 서열과 데이터베이스의 염기서열을 translation 시킨후 유사성 검사 lfasta : 두 단백질 혹은 염기서열의 부분 유사성 검색(compare local similarity)을 수행한 후 부분 서열 배열 (local sequence alignment)의 결과를 보여줌 pfasta : 두 서열의 부분 유사성 검색후 부분 서열 배열의 결과를 그림으로 보여줌 fastx/fasty: DNA 서열을 번역과정을 통해 단백질 서열로 바꾼 후 단백질 서열과 비교 tfastx/tfasty : DNA 데이터베이스를 번역과정을 통해 단백질 데이터베이스로 바꾼 후 단백질 서열과 비교 align: 두 개의 DNA 서열이나 단백질 서열 사이에서 글로벌 정렬 을 수행 lalign : 두 개의 DNA 서열이나 단백질 서열 사이에서 로컬 정렬 을 수행

FASTA 알고리즘 – 웹페이지 FASTA 3.0 : 가장 최근에 나온 FASTA version 서비스 페이지 ( http://www2.ebi.ac.uk/fasta3/ ) 에 가서 서열을 입력하면 검색가능 서열을 입력하면 자동으로 염기 서열인지 단백질 서열인지를 판단 즉 전체 서열 중 ACGT의 서열이 80%이상 차지하면 염기 서열로, 그렇지 않은 경우에는 단백질 서열로 판단

BLAST 알고리즘 - Basic Local Alignment Search Tool (BLAST) - NCBI/GenBank 에서 개발된 유사성 검색 프로그램 - heugoristic 알고리즘 FASTA와 마찬가지로 "Word Based Method"를 이용 별도의 pre-formatted 검색 데이터베이스를 필요로 함 (FASTA와는 달리) - 대부분의 온라인 서열 검색 서버의 중심을 이루는 알고리즘 지역적 유사성(local similarity)이 있는 부분을 찾아 서열의 짝짓기 비교를 수행 - 무작위 서열들에서 국고 정렬 점수에 대한 통계량을 고려하는 수학적 기반 MSP(maximal-scoring segment pair) : 공백을 고려하지 않는 두 서열 사이의 최적의 정렬 MSP점수 분포 : 한계값-extreme value distribution 분포 따름 HSP(high-scoring segment pair)의 신뢰도를 추정하는데 이 통계량이 사용 -길이 n과 m의 두 무작위 서열의 비교에서, 점수 S이상의 값을 가지고 있는 HSP를 관찰한 기대도수 E; E = Knm exp(-λS)  K 와 λ는 Karlin-Altshul 매개변수

BLAST 알고리즘 - 보존된 단어들의 쳬계적인 검색에 기반을 둠 - 단어(word)는 여러 문자로 구성 - 단어의 기본 길이는 아미노산, w=3, 뉴클레오티드, w=11 - 질의 서열은 길이 w인 단어들로 나누어지고 이러한 단어들과 유사한 단어들의 목록이 만들어짐 질의 서열과 정렬을 이루었을 때 경계값(threshold;T) 이상의 점수를 기록하는 모든 짧은 서열(words)의 목록을 구성 만약 T보다 낮은 점수면 목록에서 제거됨 서열 데이터베이스 탐색 - 질의 서열과 데이터베이스로부터의 서열 간의 gap이 없는 로컬 정렬 방식으로 확장. 정렬 점수가 경계값 아래로 떨어질 때까지 확장을 계속. 한 서열 내에서 최고점을 기록한 정렬, 혹은 최고 득점 짝정렬(MSP, maximal-scoring segment pairs)를 로컬 정렬로 결합

BLAST 알고리즘- FSA 모든 단어들의 모든 발생을 검색하기 위해 사용 됨 상태(state), 전이(transition), 입력, 출력의 집합들로 구성된 추상적인 장치 목록에 있는 모든 단어들은 FSA의 상태와 전이로 부호화됨 데이터베이스 서열이 입력으로 주어질 때 FSA는 검색된 결과 전체를 출력으로 만들어 냄 : 패턴들의 발견을 나타내는 출력과 관련 - 예 : ABA, BAA, BAB 검색 Q0 Q4 Q1 Q3 Q2 C B A 패턴 매칭 (pattern matching)에 관한 FSA (finite state automaton)의 한 예

BLAST 알고리즘 1) 검색할 query 서열로 부터 3개의 단백질 혹은 11개의 염기로 이루어진 단어들과 T 이상의 점 수를 가지는 조합을 만든다. 만들어진 조합들을 각각 서열 데이터베이스의 서열들과 비교 2) 만약 각각의 단어 조합들과 같은 서열이 서열 database에서 발견이 되면 BLAST는 옆단어들로 유사성 검색을 확장시켜 나간다. 이때 gap은 허용하지 않음 3) 확장을 마친후 database 서열중 일정 값 이상의 HSP (High-scoring Segment Pairs) 를 가진 서열들을 추출하고 이때 중복되지 않는 각각의 HSP 들은 통계적인 test를 거쳐 연결 이 때 통계적 유의성은 E = Knm exp(-λS) 에 의해 검증 가능 4) BLAST는 quary 서열과 gap 없이 일정 값 이상의 HSP를 기록하지 못하는 서열들을 미리 제거 (FASTA에 비해 훨씬 비교속도가 빠른이유 ) BUT! 두 서열이 특정 부분이 높은 일치성을 가지고 있지는 않지만 대부분의 서열에서 유사성을 가지고 있는 경우에 BLAST는 검색 불가능

BLAST 알고리즘 5) Short repeat sequence 나 특정한 residue들이 많이 존재하는 서열 들을 query 서열로 이용하였을 경우 많은 중요하지 않은 서열들이 결과로 나오게 됨 이런 결과들을 피하기 위하여 BLAST는, filtering하는 기능 을 기본적으로 가짐 . (repeat sequence같은 것들은 검색하기 이전에 제거됨) FASTA와 마찬가지로 BLAST도 단백질 서열을 위해 개발된 프로그램 염기 서열의 검색이 가능하지만 sensitivity가 떨어지므로 염기 서열로 염기 데이터베이스를 검색해 진화적으로 떨어져 있는 서열을 찾고자 한다면 FASTA를 사용하는게 좋다.

BLAST 알고리즘- program의 종류 - BLASTN : 염기 서열간의 비교 - BLASTX : 입력한 염기서열을 6개의 frame으로 변환 후 단백질 서열 database와 비교 - TBLASTN : 염기서열 database를 6 frame으로 변환 후 입력한 단백질 서열과 비교 - TBLASTX : 입력한 염기 서열과 염기서열 database를 모두 6 frame으로 변환후 비교

BLAST 알고리즘 NCBI BLAST와 WU-BLAST - BLAST 알고리즘의 구현 웹 서비스와 다운로드가 가능한 소프트웨어 패키지로 사용할 수 있도록 구현 NCBI BLAST 다중 서열의 프로필을 비교하는 방법의 개발에 초점 WU-BLAST 유전체 서열을 탐색하는 데 유용한 몇 가지 특징을 갭을 처리하는 방식에 있어서 다른 방식을 적용, 개발 TIGR, 스탠포드의 효모 유전체 서버, 버클리의 초파리 유전체 프로젝트 등에서 사용 http://blast.wustl.edu

통계적 유의성 데이터베이스 검색 결과를 해석 할 때.  발견된 유사성이 생물학적으로 의미가 있는지 파악하는 것이 중요  정렬 점수를 통계량으로 사용하여 유의성 평가 가능 ex) BLAST 에서 E값 : 전체 데이터베이스 검색에서 예상 빈도수를 계산하기 위해 확장 가능 Z값  무작위로 추출된 서열들의 점수에 대한 경험적인 분포가 기반이 됨 S - μ ( S : 두 서열의 전영 정렬, 또는 최상의 국소 정렬에 대한 관찰점수 Z = μ : 각 서열의 순서를 무작위로 변화시켜 만든 서열의 최적의 정렬을 만든 과정을 k번 반복하여 얻은 점수들, s1, s2…sk의 평균값 σ : 표준편차 ) σ

다중 정렬 (Multiple alignment) 서열들의 그룹을 동시 비교 기능적/구조적 중요성을 가지는 지역적으로 보존된 영역을 식별할 때 유용 전역 유사성, 서열그룹내의 진화적 관계를 검토하는데 도움을 줌 점진정렬 방법 (progressive alignment method) - 트리를 기반으로 함 - 트리는 서열집합의 계층적 클러스터분석에 의해 구성 단일연결 : 클러스터 내 가장 가까운 점에 따라 거리 측정 완비연결 : 클러스터 내 가장 먼 거리에 따른 거리 측정  클러스터링의 결과 : 트리구조와 비슷한 수형도에 의해 시각화 됨  유사성과 연결성이 계층적으로 표현 (a)  수형도를 따라 두 서열 사이, 서열과 그룹 사이, 두 그룹 사이의 정렬을 결합하여 점진적 다중 정렬 수행 DEHUG3 DEPGG3 DEBYG3 DEZYG3 DEBSGF (a)

다중 정렬 (Multiple alignment) 쌍별 그룹 정렬 (b) - 각 그룹 내에서 미리 결정된 정렬을 변화 시키지 않고 두 그룹의 최적 정렬을 찾아야 함 - 최적화 되는 점수 함수는 두 그룹에 있는 서열에 의해 형성된 쌍들의 합으로 계산 됨 L W R D G R G A L Q L W R G G R G A A Q D W R – G R T A S G L R R – A R T A S A L – R G A R A A A E (b) 트리 기반 점진 정렬 : 트리의 진행 상황이나 정렬 내 위치에 의존하는 유사도 가중치와 공백 벌점을 조정  실제적 구현에 대한 섬세한 조정 가능 : BUT, 일단 정렬 되면,  다음의 그룹 정렬 단계에서 수정 불가능  반복 과정으로 극복 가능 반복 정렬 정렬이 안된 서열이나 일부분만 정렬된 서열들의 집합으로부터 시작해서 임의의 두 개의 그룹으로 나누고, 최적 그룹 정렬을 수행하여 더 좋은 다중 정렬을 만듬 - 임의 분할과 쌍별 그룹 정렬의 단계들은 점수함수가 미리 정한 범위 내로 수렴할 때까지 여러번 반복 - 최상의 해결책 제공

계통발생분석 ( Phylogenetic Analysis) - 위상(topology) : A, B, C 간 유사관계를 나타내 줌 (a) 3개의 서열 존재; AB, AC, BC 4번째 서열 D 추가시,3개 위치 가능 쌍간거리들의 숫자는 6개이지만, 조정가능한 가지는 5개 n개 서열에 대해, n(n-1)/2개의 쌍간 거리 존재 - n 개의 외부 노드, n-2개의 내부 노드를 갖는 트리에서는 2n-3개의 가지만 존재  트리의 재구성 문제= 최적화 문제 A B C D (b) A B A B A B D C C C 계통발생 분석에서 가능한 트리의 위상 3개의 서열 (b) 4개의 서열 공통된 조상 그로부터 분화된 서열

다중 정렬 (Multiple alignment) 사이토우 (saitou)와 네이(Nei)의 이웃-연결(Neighbor-joining)방법 -최적 트리에 대한 근사를 찾기 위한 빠른 방법중 하나 -쌍간의 거리 계산  정렬된 서열들에 대한 거리행렬에 저장  서열들은 특정 서열들과 쌍을 이루는 방법을 통해 연속해서 클러스터링  거리행렬의 크리는 하나씩 줄어듬  만들어지는 트리의 가지들에 대한 길이의 합을 가장 작게 만드는 쌍으로 , 모든 가능한 쌍 중에서 각 단계에서 결집될 쌍이 선택됨. UPGMA(unweighted pair-group method by arithmetic averaging) -거리 행렬에서 가장 짧은 거리가 되는 서열들을 결집 서열들의 전반적인 유사성을 기반으로 함 절약접근방법 문자별 비교를 기반으로 하여 유사성을 분할함 원리 : 최소 진화의 원리  진화 트리는 가능한 최고의 돌연변이 사건을 설명하기 위하여 재구성 됨 - 적어도 4개의 서열 필요

SA (stimulated annealing) x E 개념적 변수공간 x에 대한 최적화 함수 E의 도식적 예시 x : 모든 가능한 정렬을 나타내는 공간 E : 점수값의 부호를 음이되도록 한 함수 - 에너지 함수의 최소화 - 지역적 최소값에 방해 받지 않고 전역적 최대값을 찾기 위한 확률적 방법  다중정렬과 같은 최적화 문제에 응용 가능 - 금속의 제련 (또는 담금질; annealing)과정을 모델링 SA와 메트로폴리스 몬테카를로 방법은 에너지 함수에서 고온에서 커지게 되는 열적 요동 개념을 기반으로 함 ∆E = E(x’n) – E(xn) 1 when ∆E ‹ 0 P = exp(- ∆E/Tn) when ∆E › 0 ㅡ

SA (stimulated annealing) P = exp(- ∆E/Tn) ∆E : 에너지 함수의 증가치, T: 온도 열할을 하는 매개변수 - 열평형 분포의 볼츠만 인자들을 나타냄 몬테 카를로 방법을 이용하여 메트로 폴리스에 의해 처음으로 구현됨 SA에서 몬테카를로 메트로 폴리스방법은 점차적으로 감소하는 온도에서 반복수행 (각 온도에서 실제 열 평형 조건이 만족될 때까지 수행됨  그 뒤 온도가 조금 내려감) - 온도가 낮아지면 나쁜 solution을 선택할 확률이 줄어들게 되기 때문에 전체 알고리즘은 수렴 - 성공 여부 : 초기와 말기의 온도, 온도의 감소치, 몬테카를로 단계의 개수등을 포함한 냉각 계획 (cooling schedule)에 달려있음 미리 정해준 annealing schedule 에 따라 온도를 낮춰줌

유전자 알고리즘 적자생존, 유전자 교차 등의 자연 진화 메카니즘에 기반한 문제해결 알고리즘 현 세대를 구성하는 모집단에서 적합도(fitness)에 따라 염색체들을 선택 유전 연산자를 적용하여 새로운 세대의 모집단을 생성해 나가는 과정 최적화 문제에 대해 다른 종류의 확률적 해법 제공 작은 변화뿐 아니라 급격한 차이도 적극적으로 포함 주어진 환경에 잘 적응하는 유전자만을 선택(selection)하고 교배(crossover)하고 때에 따라서 돌연변이(mutation)도 하며 다음 세대에 우수한 유전 형질이 전달(reproduction) 되게 된다. 따라서 진화(evolution)가 거듭될수록 주어진 환경에 더 적합한 유전자들만 남아있게 될 것이다.

유전자 알고리즘 generation : 세대 population : 세대를 구성하는 모집단 또는 개체군 chromosome : 모집단을 구성하는 염색체 - 유전자의 집합으로 구성되며 유전자 알고리즘에서는 문제의 특성에 맞도록 문자열(string)로 구성한다. gene : 염색체를 구성하는 유전자 genotype : 염색체의 구조를 나타내는 유전형 - 유전자 알고리즘에서는 구조체로 표현 fitness : 적합도 :개체의 우성과 열성을 판별하기 위한 값 genetic operator : 유전 연산자 - reproduction (재생), crossover (교배), mutation (돌연변이) 유전자 알고리즘 교차 (crossover) : 실제 유전과정과 비슷하게 급격한 변화 돌연변이(mutation) : 작은 변화 2개의 개체간에 염색체를 부분적으로 바꿈으로써 새로운 개체 생성 임의의 유전자의 특성치를 변형시킴으로써 유전형질의 다양성을 유지하기 위해 사용되는 연산자

유전자 알고리즘 - 예 f(x) = x2[0 ≤ x ≤ 31] = 환경 x = 환경에 살아가는 개체(유전자) 함수값 = 환경에 잘 적응하는 정도 x = 0이라는 개체보다 x = 4라는 개체가 f(x) = x2[0 ≤ x ≤ 4] 라는 환경에서 더 잘 적응하는 것. 라고 정의한다. 01101 11000 01000 10011 이 4개체가 모여있는 군(집단)에서는 f(x)=x2 라는 환경에서 어떠한 개체가 가장 잘 적응할까?  십진수로 변환 환경 f(x) = x2[0 ≤ x ≤ 31] 개체 0 ≤ x ≤ 31 적합성 f(x) 01000은 살기 어렵고, 11000은 그나마 가장 잘 적응  그러므로 다음 세대에서는 01000은 도태 , 11000은 자손을 생산  이와 같은 과정을 거친 먼 훗날의 개체는 바로 11111이라는 개체가 탄생  주어진 환경을 지배할 것 11111 11111 11111 11111 군(pool)이 위와 같은 개체(gene)로 구성되었을 때 '환경에 적응하였다‘ OR '해를 찾았다'

유전자 알고리즘 유전 알고리즘이 다른 탐색이나 최적화 방법과 다른 점 1. GA는 하나의 개체(변수 등)가 아닌 개체들의 군(pool) 단위로 탐색한다. 2. GA는 적합성 함수(fitness function)를 사용한다. 3. GA는 확률적인 변이 규칙을 사용한다. 위와 같은 이유로, 다른 탐색 또는 최적화 방법 중 하나인 계산에 의존한 방법 (calculus-based method : hill-climbing)에 비하여 전역적(global) 해를 구할 가능성이 높으며 다른 여러탐색 방법에 비하여 효율적