coursera Computational Molecular Evolution

coursera 의 6주 과정수업으로 이번주에 종강을 하게 되는데 정리를 해보고자 한다.
https://class.coursera.org/molevol-001/class/index

https://spark-public.s3.amazonaws.com/molevol/Downloads/slides_week1.pdf 
... (1~6 까지)

아래 내용은 단순히 위 URL의 vod를 요약한 것으로 추가적인 자료 확인이나 이해를 높이기 위한 노력이 없었으므로 잘못된 해석이 들어가 있을 수 있다.

또한 강의 초반의 classification, evolution, selection, genetic drift, phylogenetic tree teminology 등은 생략한다.  

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를 찾을까? (이 수업에서는 DNA의 multiple alignment에 대해서는 설명하지 않음)
아래와 같은 순서대로 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들이 많이 찾아지게 된다. 이때 어떻게 해야 하는가? 여기서 어떠한 정보를 뽑아 낼 수 있는가?
<consensus 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 를 기준으로 두 그룹으로 나눈다. 이때 두 그룹이 몇번 나왓는가를 오른쪽 table 처럼 정리한다(분홍색 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들이 그러한 특성을 갖은 것이므로 ).

maximum parsimony 이외에 DNA data를 잘 나타내는 phylogenetic 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를 구축하는 것 목표(위의 그림에서 D값과 d 값의 차이가 가장 작게 하는게 목표).

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(NJ) Agorithm
알고리즘은 아래와 같다.

아래 그림은 NJ의 한예이다. 아래 그림의 왼쪽 상단의 table과 같이 distance matrix가 주어졌다고 할때 오른쪽 상단의 table과 같이 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를 구축하는 방법이다.