IQTree #
Find similar titles

Structured data

Category: Software

IQTree
Incoming Links
1. Related Bioinformaticses (Bioinformatics 0)

IQTree #

동기 #

생물의 진화 과정의 유연 관계에 대한 즉, 계통 발생학적 관계를 밝히기 위해서는 근연종과의 뉴클레오타이드 혹은 단백질 서열에 대한 multiple alignment를 기초로 한다. 최근에는 NGS 를 이용하여 대량으로 데이터를 생산할 수 있게 되었을 뿐만 아니라, 다양한 종에서도 대용량의 데이터를 쉽게 얻을 수 있다.

이러한 대용량의 데이터를 계통분류학적으로 분석 하기위해 빠르게 그 관계를 트리형태로 추론할 수 있는 대표적인 방법이 maximum-likelihood(ML) 이다.

이 Maximum likelihood에 의한 방법은 다중 서열 정렬에서 사용한 치환 행렬처럼 아미노산이나 핵산의 치환율에 대한 정보를 바탕으로 TREE를 추론하게 되는데, 여기서 추론한 optical한 tree가 과연 best한 tree인지를 확인하는 것이 어렵다는 NP-hard combinatorial optimization problem에 빠지게 된다는 단점이 있다.

NP : 답을 알려 주면, 그 답이 맞는지를 주어진 시간안에 검산해 볼 수 있는 문제
NP-hard : 답을 알려 주더라도, 그 답이 맞는지를 주어진 시간안에 검산할 수 없는 문제

IQTree #

이러한 이유로, 기존의 ML 트리를 계산하는 프로그램의 속도를 가지고 있으면서도, 다른 검색방법을 이용하여 ML 트리를 추론할 수 있는 방법이 필요하였다.

IQTree는 stochastic(확률론적인) 알고리즘을 이용하여 ML 트리를 추론하는 효과적이고 속도가 빠른 프로그램으로, 다음과 같은 알고리즘 흐름도를 보인다.

그림과 같이 크게 3가지의 단계를 통해 ML 트리를 추론한다.

METHOD #

a. Initial Tree generation

먼저 이치에 맞는 초기 트리들의 대표적인 후보군 트리들을 구성하기 위하여 RAxML과 같은 전략인 stepwise addition tree 방법을 이용하여 100개의 parsimony 트리를 구성한다. 그 중 unique한 topology를 가지는 트리만을 선별하고, 트리를 가로지르는 엣지를 이용하여 ML 값을 계산하고, 상위 20개의 트리를 선택하여 초기 후보군 트리 C를 구성한다.

b. Stochastic NNI

초기 후보군 트리 C 중에서 0.5*(n - 3)번의 랜덤하게 NNI를 수행한다. 여기서 n 은 트리 내부의 가지 개수이다.이를 통해 locally하게 적합한(optimal) tree 를 구성한다.

c. Hill-Climbing NNI

먼저 주어진 트리를 기준으로, 4개의 인접한 가지(branch)들과 트리 내부 가지를 이용하여 분리한 각각의 NNI에 대한 likelihood 값을 계산한다. 현재 트리를 중심으로 likelihood 값이 높은 NNI부터 트리에 붙이게 되는데, 기존에 존재하는 NNI와 충돌이 일어나게 되면, 이 NNI는 제거한다. 이렇게 모든 NNI에 대해 반복하여 Hill-climbing search 알고리즘을 바탕으로 진행하게 된다.

Hill climbing search #

이 검색 방법은 트리에서 깊이 우선탐색(Depth-first search)에 기초한 방법으로, 탐색효율을 높이기 위하여 휴리스틱(heuristic)하게 적용된다. 즉, 각 단계에서 선택한 것이 다른 것보다 더 나은지를 측정하고 계속해서 다른 선택을 한다.

1. root node를 queue Q 에 넣어 첫 번째 요소로 한다. 이후 깊이우선 탐색을 수행한다.
2. Q 가 비어 있든가 목표에 이를 때까지 수행한다. 
Q 에 있는 첫 번째 요소가 목표 (remaining distance 가 0 인 상태) 인지를 결정한다. 만일 목표가 아니라면 Q에서 첫 번째 요소를 제거하고, 그 자식노드들을 잔여거리 (remaining distance) 에 따라 sort하고, sort 된 리스트를 Q 의 앞쪽에 배치한다. 목표가 아닌상태에서 자식노드가 없으면 부모노드로 간다.
3. 만일 목표에 도달하면 성공이며, 그렇지 않으면 실패이다.

NNI #

NNI이란(Nearest neighbor interchange)로 다음과 같이 트리 내부의 가지를 따라서 트리를 2개로 재정렬해주는 기법이다.

사용방법 #

Input file
IQ-TREE 프로그램은 다양한 형식의 파일을 입력값으로 받는다. 예를 들어, 아래 그림과 같은 phylip format은 물론, FASTA, NEXUS, CLUSTALW 포맷도 지원한다.

다음과 같은 INPUT 데이터를 통해 각 종 간의 진화적인 유연관계를 파악할 수 있다.

실행
IQ-TREE 프로그램을 사용하는 방법은 매우 간단하다.

iqtree -s input_data

-s : IQ-TREE를 통해 실행하고자 하는 INPUT 파일의 이름
결과물
IQ-TREE 프로그램의 수행이 완료되면 다음과 같은 3가지의 결과 파일이 출력된다.
1. input_data.iqtree : IQ-TREE 수행결과에 대한 파일로, 각 계산과정에 대한 결과가 정리되어 있다.
2. input_data.treefile : IQ-TREE 계산 결과에 따른 최종 TREE 파일로 Figtree 혹은 MEGA 등으로 TREE를 그려볼 수 있다.
3. input_data.log : IQ-TREE 수행 과정에 대한 로그 파일