22. global alignment [10 2주차]

22. Global Alignment [10-2주차]

2024년 1월 14일 일요일

오전 2:58

<Global Alignment>

문자열의 유사도를 구하는 다른 방법. 다음 세 단계로 진행된다.

 

두 개의 문자열 acbcdb와 cadbd의 유사도를 측정.

1.     유사도 함수 𝜎를 정의한다. 𝜎(a, b)는 문자 'a'와 문자 'b'의 유사도를 반환한다.

유사도 함수는 위와 같은 테이블을 통해 정의할 수 있다.

위 테이블에서, 𝜎(a, c) = -2 이다.

두 문자가 같으면 5, 둘다 빈 문자이면 0 임을 알 수 있다.

2.     각각의 문자열에 "-"(빈칸임을 의미)를 적절한 위치에 삽입하여 두 문자열의 길이가 같아지도록 한다.

이를 두 문자열을 확장한다고 한다.

적절한 위치에 삽입한다는 것은, 유사도가 가장 높게 나오도록 삽입한다는 뜻이다.

3.     전체 유사도를 구한다.

𝜎(𝑎,−)+ 𝜎(𝑐,𝑐)+𝜎(𝑏,−)+𝜎(𝑐,𝑎)+𝜎(𝑑,𝑑)+𝜎(𝑏,𝑏)+𝜎(−,𝑑)

 

 

<Global alignment의 점화식>

문자열 x[1..m], y[1..n]의 global alignment를 V(m, n)이라 하자.

유사도가 가장 높게 나오도록 두 문자열을 확장하는 방법을 이해하기 위해, V(i, j)의 점화식을 구해 보자.

 

V(i, j)는 다음 세 가지 방법 중 하나로 구해진다.

1.     "-"를 추가하지 않음

2.     y에 "-"를 추가

3.     x에 "-"를 추가

 

위 세 가지 중 V(i, j)를 가장 크게 하는 것을 선택하므로, 점화식은 다음과 같이 정리된다.

 

 

 

<Global Alignment - Tabular Computation>

위와 같이 유사도 함수가 주어졌을 때, GTTCAT 와 ATTAGCG 의 global alignment를 구해 보자.

 

다음은 V(i, j)의 기저조건이다.

• 𝑉(0,0)=0
• 𝑉(𝑖,0)=𝑉(𝑖−1,0)+𝜎(x[𝑖], −)
• 𝑉(0,𝑗)=𝑉(0,𝑗−1)+𝜎(−, y[𝑗])

이를 이용해, 아래의 테이블을 채울 수 있다.

 

위 테이블의 (i, j)칸은 V(i, j)를 의미한다. (i-1, j), (i, j-1), (i-1, j-1) 칸이 채워져 있으면 위에서 구한 점화식을 통해 (i, j)칸을 채울 수 있다.