Multiple Sequence Alignment 중 Progressive Alignment 기법

 

Multiple Sequence Alignment 중 Progressive Alignment 기법

 

Multiple Sequence Aligment (MSA) 기법 중 가장 많이 사용되는 것이 progrssive alignment method (hierarchical or tree method)로 heuristic search를 기반으로 한다.

이 방법은 모든 서열들을 pairwise로 비교하여 가장 비숫한 pair 부터 가장 멀리 관계된 pair까지 순차적으로 비교하여  MSA를 수행한다. 모든 Progrssive Alignment Methods는 두 가지 단계를 필요로 한다.

 

1. 서열들의 관계를 나타내는 tree를 만든다. (Guide tree)

2. Guide tree에 의한 순서대로 서열 또는 MSA에 서열(또는 MSA)을 추가하며 MSA를 완성한다.

 

초기의 Guide tree는 neigbor-joining 또는 UPGMA와 같은 효율적인 clustering method로 결정하고, dynammic programming alignment 보다는 distance를 바탕으로한 방법으로 aligment를 한다.

 

Progressive alignment method는 전체적인 최선의 결과를 보장 할 수 없다. 문제는 MSA가 더해 나가는 중 에러가 있으면, 그 에러가 마지막 결과 까지 증식이 된다. 또한 세트 안의 서열들이 멀리 관계되어 있으면 그 성과가 많이 떨어진다. 최신의 progressive alignment methods는 sequence weighening scheme을 사용하여 세트안의 서열들에게 이들의 계통학적 거리를 반영한 점수를 준다. 이것은 alignment program에 주어진 서열들의 non-random selection을 보정한다.