계통수의 정의 #

계통수는 다양한 생물 종들이 하나의 공동조상에서 기원되었다는 개념을 기반으로, 현존하는 생물군을 가장 바깥쪽의 가지에 위치하며 그들의 공동조상을 뿌리로 하여 나무 형태로 그들의 진화과정을 표현한 그림이다. 기본적으로 하나의 공동조상에서 서로 다른 종이 분화되는 과정을 두 개의 가지가 갈라져서 나오는 형태로 나타낸다. 상동성을 기반으로 하는 최절약 원리 (오컴의 면도날)과 분자적 유전정보 바탕으로 생성된 최우법이 사용된다.

계통수의 해석 #

계통수를 해석하기 위해서는 계통수의 형태와, 각 부분이 의미하는 바를 이해할 수 있어야 한다. 기본적인 계통수는 다음과 같은 형태를 가진다.

위 그림에서 계통수의 뿌리 부분(Root)은 공동조상의 위치를 나타내며, 각 가지 끝 부분(Terminal nodes; tips)은 현존하여 관찰되는 생물군을 의미한다. Root에서 tip 방향으로 가면서 가지(branch)가 갈라지게 되는데, 각 branch는 한 생물군의 계통을 나타낸다. Branch가 나아가다가 서로 다른 가지로 갈라지게 되는 부분을 node라고 하며, 계통의 분화 역사를 나타낸다. 각 node는 여기에서 분화된 branch들의 공동조상이 된다. 가장 최근에 분화가 이루어져 가까운 관계를 나타내는 군을 자매군(sister group)이라고 하며, 서로 자매관계(sister relationship)에 있다고도 할 수 있다. 계통수가 올바른 계통 역사를 담기 위해서는 root가 모두의 공동조상 부분에 위치하여야 하는데, 관찰되는 종들과 먼 유연관계를 갖는 outgroup을 통해 root를 보정할 수 있다.

계통수의 구조를 이해하였다 하더라도, 계통수는 쉽게 잘못 해석되기 쉽다. 정확하게 계통수를 해석하는 가장 좋은 한 가지 방법은, 오직 ‘공동조상의 위치 (서로 간에 가장 최근에 공유한 node 위치)’로 서로 간의 관계를 이해하면 된다. 올바르게 계통수를 이해하기 위해서는 계통수를 일종의 ‘가계도’로 이해하면 쉽게 이해할 수 있다. 다시 말해 ‘촌수’를 따지는 방식으로 이해하면 된다.

위 그림에서 나와 형제는 공동조상을 ‘부모(Parent)’에서 공유한다. 반면 나와 사촌은 공동조상을 ‘조부모(Grandparent)’에서 공유한다. 당연히 부모나 비해서 조부모가 더 오래전의 공동조상이므로, 나는 형제와 더 가까운 관계이고 사촌과는 더 먼 관계가 된다.

서로 간의 관계는 서로 간에 가장 최근에 공유한 node의 위치만 보면 된다고 하였으므로, node와 branch 간의 관계가 바뀌지만 않는다면 계통수는 그 의미가 완전히 같다.

예를 들어 위에서 보여지는 그림을 보면 2번 방향으로 계통수 모양이 바뀌더라도 E , F, G 사이의 관계가 F-G가 더 최근에 node를 공유하므로 이들이 E에 비해 서로 가깝다는 것은 바뀌지 않는다. 즉 계통수는 공동 조상의 위치만 변하면 되지 않기 때문에, node를 중점으로 여기에서 분지된 branch가 단순히 회전하는 것으로는 관계가 바뀌지 않는다.

‘공동조상 찾기’와 ‘계통수의 회전’을 이해할 수만 있다면 계통수의 해석은 쉬워진다.

위 그림에서 a 그림을 보았을 때 A, F, G 간의 관계를 묻는다면 그림 상으로 F가 A보다 G와 가까이에 위치하므로 F와 G가 더 가까운 관계라고 잘못 해석하기 쉽다. 하지만 c 그림을 보면, 이는 a와 완전히 같은 계통수라는 걸 알 수 있다. Tip 간의 공동조상 관계는 완전히 일치하고, 그저 그 안에서 회전이 일어났을 뿐이다. 이 그림에서는 더 이상 F와 G가 가까운 위치에 있지 않다. 즉 그림 상의 위치는 서로 간의 관계에 아무 의미가 없다는 것을 알 수 있다. 제대로 이 계통수를 해석한다면, A와 F가 더 최근에 공동조상을 공유하므로 A와 F가 가까운 관계이고 G가 먼 관계임을 이해할 수 있다.

이미지 출처 및 참고문헌 1)

알고리즘 #

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/Genomics Workbench를 이용한 바이러스의 진단을 위한 계통 분류 및 유연관계 분석 #

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

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

모든 데이터의 준비가 완료되어 sequence alignment를 클릭하여 준비된 데이터를 선택하였다.

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

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

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

위 그림의 하얀색 셀(대각선)을 기준으로 위의 다섯 가지 콘텐츠 중 두 가지씩 비교가 가능하다.

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

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

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

Phylogram, cladogram, circular phylogram, circular cladogram, radial 등의 다양한 layout을 제공하여 여러 형태로 뷰어가 가능하다.

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

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

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

• PAUP : http://paup.csit.fsu.edu/downl.html
• PHYLIP : http://evolution.genetics.washington.edu/phylip.html
• MEGA : http://www.megasoftware.net/
• SplitsTree : http://www.splitstree.org/
• MacClade : http://macclade.org/macclade.html
• Hennig86 : http://www.cladistics.org/education/hennig86.html

참고문헌 #

1. Gregory, T.R., 2008. Understanding evolutionary trees. Evolution: Education and Outreach, 1(2), p.121.

Incoming Links #

Related Data Sciences (DataScience 0) #

• 파이썬/라이브러리/ete toolkit

Related Bioinformaticses (Bioinformatics 1) #

• CAFE
• Jalview
• NemATOL
• PHY
• Pectinase
• Petinase
• Substitution model
• UPGMA
• 유전정보
• 자가불화합성

Suggested Pages #

• 0.526 Neighbor joining
• 0.087 생물정보 데이터 형식
• 0.025 SNP
• 0.025 인공 지능
• 0.025 GenBank
• 0.025 SOAPdenovo
• 0.024 BWA
• 0.023 DNA
• 0.023 Bowtie
• 0.022 Entrez
• More suggestions...