Skip to content

계통수 #
Find similar titles

Structured data

Category
Analysis

계통수의 정의 #

계통수는 생물의 진화의 결과 여러 종이나 분류군 사이에서 나타나는 유사성과 차이점을 "나무"형식으로 보이는 그림이다. 상동성을 기반으로 하는 최절약 원리 (오컴의 면도날)과 분자적 유전정보 바탕으로 생성된 최우법이 사용된다.

알고리즘 #

molecular data, 즉 DNA sequence로 부터 어떻게 Phylogenetic tree를 구축하는지 알아본다.

Maximum Parsimony #

simplest possible hypothesis를 선택하는 것이 maximum parsimony 방식. 곧 shortest tree(데이터를 나타내는데 필요한 mutation 갯수가 가작 적은 tree) 를 선택하는 방식.

테이블(4개 샘플 A,B,C,D의 sequence를 3bp로 구성)를 multiple alignment 한 결과)를 예를 들어 보면 1번 bp를 기준으로 보면 왼쪽의 두개의 phylogenetic tree 중 위의 tree가 단 하나의 mutation 만 필요하므로 데이터를 잘 나타내는 tree 라고 판단하는 것이다.

위의 tree는 3개의 bp를 모두 고려 했을때의 tree length를 나타낸 것으로 위의 maximum parsimony의 방식으로는 tree가 적당한 tree로 판단된다.

다르게 표현하면 maximum parsimony는 homoplasy가 가장 적게 나타나는 tree를 선택하는 것이다.

homoplasy는 위의 그림에서 보듯이 공통의 조상으로 부터 얻은 형질이 아니라 각기 따로 얻은 형질이 비슷한 것을 의미하는 것. shortest tree를 선택하게 되어 있는 maximum parsimony는 mutation 갯수를 줄이는 방향으로 tree를 선택하므로 동일한 서열은 공통의 조상으로 부터 오게끔 샘플을 배치하기 때문에 homoplasy가 적은 tree를 선택하게 되는 것.

그러면 DNA 데이터로 부터 어떻게 maximum parsimony tree를 찾을까? 아래와 같은 순서대로 parsiminious tree를 찾는다.

  1. Construct list of all possible trees for data set
  2. For each tree: determine length, add to list of lengths
  3. When finished: select tree from list
  4. If several trees have the same length, then they are equally good (equally parsimonious)

tree를 construction 하는 방법은 아래와 같다(이 같은 방식을 exhaustive search 라고 함, 모든 tree를 다 찾는 방식).

먼저 radom 하게 3개의 샘플을 뽑고 tree를 구성(3개 샘플에서는 unroot tree 일때 딱 하나의 tree밖에 나올수 없다). 그 뒤 모든 가능한 branch 에다가 새로운 샘플을 끼어 넣음.

tree가 구축되었으면 그 다음 tree length를 구하는 방법이 필요. 그것이 fitch algorithm.

The Fitch Algorithm #

  1. Root the tree at an arbitrary internal node (or internal branch)
  2. Visit an internal node x for which no state set has been defined, but where the state sets of x's immediate descentdants (y,z) have been defined
  3. If the state sets of y,z have common states, then union of y,z to x, and increase tree length by one
  4. Repeat until all internal nodes have been visited. Note length of current tree.

위 그림이 tree length 를 구하는 예. 각 leaf는 샘플의 DNA 서열을 나타냄. unrooted tree 에서 internal branch를 끌어서 rooted tree를 생성. 그뒤 leaf 에부터 internal node를 정하면서 length 를 결정.

모든 tree를 다 구축해보는 것은 현실적으로 불가능하다. 이에 대한 방안을 알아본다.

Searching Tree Space #

exhaustive search는 엄청나게 많은 tree를 생성하게 된다(위의 exhaustive search의 그림과 아래 table 참고).

그 대안으로 나온것이 Branch and bound 방식. 랜덤하게 tree 하나를 뽑아서 그것의 length를 구하고 그것을 기준으로 삼는것. 그래서 tree construction 할때 그 기준보다 넘어가버리면 아예 그것과 관련된 tree는 더이상 계산하지 않는 것이다.

위 그림의 오른쪽 상단의 것을 기준으로 삼으면 tree를 construction 할때 두번째 layer의 오른쪽과 왼쪽의 tree는 이미 기준의 tree보다 length가 길기 때문에 더이상 샘플을 adding 하지 않는다. 하지만 branch and bound 역시 샘플 수가 많으면 효과적인 방법이 아님. 그래서 나온방식이 Heuristic search.

  1. Construct initial tree (e.g.,sequential addition); determine length
  2. Construct set of "neighboring trees" by making small rearrangements of initial tree; determine lengths
  3. If any of the neighboring trees are better than the initial tree, then select it/them and use as starting point for new round of rearrangements (possibly several neighbors are equally good)
  4. Repeat steps 2+3 until you have found a tree that is better than all of its neighbors
  5. This tree is a "local optimum" (not necessarily a global optimum)

랜덤하게 tree 하나 뽑아서 length 구하고 이 tree의 rearrangement 해서 length를 구하고 이 새로운 tree가 기존의 tree 보다 length가 짧아지면 이 tree로 갈아타서 또 rearrange 하고.. 이를 반복해서 local optimum을 찾는것. 곧 경험적으로 해봐서 더이사 좋아지지 않는다 싶으면 멈추는 것을 의미.

tree의 rearrangement는 아래와 같이 3가지 방식이 있다. TBR > SPR > NNI

maximum parsimony 같은 방법을 이용하면 equally parsimonious 한 tree들이 많이 찾아지게 된다. 이때 어떻게 해야 하는가? 여기서 어떠한 정보를 뽑아 낼 수 있는가?

설령 수많은 equally parsimonious trees 가 찾아졌다 하더라도 실상 tree들의 전체 적인 형태는 비슷하며 단지 약간의 차이가 있을 뿐이다. 그렇기 때문에 consensus tree를 구축함으로써 tree set으로부터 정보를 뽑아 낼수 있다.

위와 같이 strict consensus tree는 모호한 부분은 polytomy를 이용하여 나타내는 방법 (첫번째와 두번째 tree는 동일한데, 어떻게 동일한 tree가 두번 나올수 있냐에 대해서는 저 tree들이 더 큰 tree의 subtree라고 가정해보면 됨).

두번째 방법으로는 majority rule consensus tree. 다수의 tree를 따르는 것.

majority consensus tree를 구축하는 방법

  1. tree set의 tree 하나씩 모든 internal branch를 기준으로 bipartition으로 해서 나타나는 separation을 table로 정리한다.
  2. 정리되 table을 count를 frequency로 바꾼뒤 ordering 해서 50이상의 값을 갖는 separation을 찾는다.

6개의 equally parsimonious trees 가 있을 때 tree 하나씩 모든 internal node 를 기준으로 두 그룹으로 나눈다. 이때 두 그룹이 몇번 나왓는지를 정리한다.(분홍색 branch를 기준으로 A,E 와 C,B,D,F 가 나뉘는데 갯수가 적은 group을 *로 표시하고 많은 group은 -으로 표시한다).

최종적으로 모든 tree의 internal branch로 bipartition을 하면 count table를 구할 수 있다. 그리고 이 count를 전체 tree의 갯수로 나눈 뒤 ordering을 한다. 이 후 50% 가 넘는 record를 가지고 majority consensus tree를 만든다.

50 이상의 record를 가지고 tree를 구축하였으므로 반드시 50 이상의 record들은 comparable 하게 표현이 된다(절반 이상의 tree들이 그러한 특성을 갖은 것이므로).

Distance Matrix Method #

DNA를 multiple alignment 하고 나서 distance matrix(숫자는 different base의 갯수)를 만든 다음 이 matrix를 만족시키는 tree를 구축하는 방법이 distance matrix method.

distance matrix method 는 DNA alignment를 해 놓고 DNA different count인 observed distance의 값을 가장 잘 나타내는 phylogenetic tree를 구축하는 것 목표이다.

observed distance(D)와 phylogenetics tree의 distance(d)의 차이는 sum of squares(Q)로 표현 가능하다. 이때 일반적으로 distance가 멀수록 error가 더 들어 가기 때문에 D의 n차로 나누어 보정한다.

sum of square(Q)를 계산한 식을 각 branch의 길이의 이차 함수로 표현이 되고 이차 함수는 아래로 볼록한 형태를 갖고 있으며 최소값은 미분했을때 0인 값이므로 각 branch의 길이가 결정된다.

이 때 이 Q값이 가장 작은 tree를 선택하게 되면 이는 Least Squares Optimality Criterion에 의한 것이고 branch의 합이 가장 작은 tree를 선택하는 것이 Minimum Evolution Optimality Criterion 에 의한 것이다(두 방식다 tree의 branch를 결정할때는 sum of square를 이용하고 최종적으로 가장 적절한 tree가 뭔가를 선택할때 기준이 달라진다).

distance matrix method 역시 parsimony와 같이 tree를 만들어 놓고 평가하는 방식이다. 그렇기 때문에 tree가 많아지면 exhaustive method 방식보다는 heuristic algorithm을 이용하여 효율을 높일 수 있다. distance matrix method의 경우 이 외에도 clustering algorithm 을 이용할 수 있는데 그 한 방법인 neighbor joining 방법을 알아본다.

Neighbor Joining Agorithm #

distance matrix가 주어졌다고 할때 u 값을 계산한다. 그 뒤 새로운 distance matrix를 생성하고 이 값중 제일 작은 값을 갖는 pair를 찾는다(-39가 가장 작은 값으로 A,B 와 C,D가 있는데 여기서는 C,D를 선택). 그뒤 새로운 노드 X와 C,D의 거리를 구한다.

C와 D가 clustering 되어 새로운 노드 X를 생성한 뒤 아래 그림과 같이 새로운 X 노드와 나머지 노드 간의 거리를 구해야 한다.

C,D의 record는 삭제한 뒤 A,B,X 만 가지고 위 과정을 반복한다.


정리를 하자면 tree를 구축하는 방식은 exhaustive, branch and bound, 그리고 heuristic 방식이 있는 것. 그리고 그 tree를 평가 하는 방식으로 maximum parsimony, distance matrix method가 있는 것. maximum parsimony의 경우 fitch algorithm으로 계산 가능하고, distance matrix의 경우 tree 선택 기준에 least squares 와 minimum evolution 방식으로 나눌 수 있다. 추가적으로 matrix distance method의 경우에는 clustering 방식으로 optimal tree를 결정할 수 있는데 NJ(neighbor joining algorithm)이 그 한 방법이다. NJ 방법은 distance matrix에서 가장 짧은 노드를 합치는 식으로 step-by-step으로 phylogenetic tree를 구축하는 방법이다.

분석 방법 및 사례 #

CLC Main Workbench를 이용한 바이러스의 진단을 위한 계통 분류 및 유연관계 분석 #

AI가 빈번하게 발생하고 있는 요즈음 확보된 influenza virus가 어디서부터 유래한 것인지 확인하는 과정이 필요하여 CLC bio사의 CLC Main Workbench라는 상용화 소프트웨어를 활용하였다.

Workflow

소프트웨어를 통해 진행할 수 있는 workflow는 위와 같다.
먼저 확보된 sequence data를 CLC Main Workbench를 import하여 분석하고자 하는 데이터로 이용하였다.
그리고 계통 분류 및 유연관계 분석을 위한 influenza virus의 data가 별도로 존재하지 않아 NCBI database 접속을 통해 데이터를 다운로드 받았다.

NCBI에서 data 다운로드하기
모든 데이터의 준비가 완료되어 sequence alignment를 클릭하여 준비된 데이터를 선택하였다.

Sequence alignment 수행하기

Alignment 결과

그래픽한 Alignment 결과를 얻었지만 조금 더 깔끔한 뷰어를 보기 위하여 뷰어 옵션을 변경할 수 있는 side panel을 통해 염기서열의 색을 변경하였다. Alignment 결과 염기서열 하나하나 보면서 어떻게 정렬이 되었는지 확인이 가능하지만 전체적인 뷰어도 확인할 수 있다.

이렇게 만들어진 alignment 데이터를 이용하여 두 서열간의 차이를 pairwise 분석을 통해 비교하였다.

Pairwise comparison 분석

비교 컨텐츠
* Gap : 두 서열의 동일한 위치에서 한 서열에는 gap이 있고, 다른 서열에는 gap이 없는 경우의 수를 산출
* Differences : 두 서열의 동일한 위치가 서로 다른 경우의 수
* Distance : 두 서열의 유전적 거리를 산출
* Percent Identity : Alignment상의 동일한 위치에 두 서열이 중복되는 경우의 수를 백분율로 표시
* Identity : Alignment상의 동일한 위치에 두 서열이 중복되는 경우의 수를 산출

위 그림의 빨간 대각선을 기준으로 위의 다섯 가지 컨텐츠 중 두 가지씩 비교가 가능하다.

Pairwise 분석 외에 tree를 그려 분석하고자 하는 influenza virus가 어디서부터 유래했는지 분석하고자 한다.

기본적으로 tree를 그리기 위한 알고리즘은 두 가지가 있다.
* Neighbor Joining
* UPGMA

이 두 가지의 알고리즘은 거리에 기반하여 tree를 그려준다.

Tree parameter

Tree 결과

이전 버전과 달리 tree를 뷰어할 수 있는 layout이 추가되었다.

또한 metadata의 import를 통해 각 서열의 host가 무엇이고, 어느 나라에서 유래된 것이며, 언제 연구된 서열인지 비교하여 내가 분석하고자 하는 서열이 어느 서열과 유연관계가 가까운지 확인할 수 있다.

Metadata import 결과 뷰어

계통수를 그리기 위한 다양한 프로그램 #

현재 웹에서도 tree를 그리기 위한 다양한 프로그램들을 제공하고 있다. 이 중 가장 잘 알려진 것이 PAUP(phylogenetic analysis using parsimony)이다.

Incoming Links #

Related Data Sciences #

Related Articles #

Related Bioinformaticses #

Suggested Pages #

0.0.1_20140628_0