3 1 Defining Minimum Edit Distance
https://youtu.be/-XRJL2R0SCg

image
image
image

문자열을 alignment할때 있는 그대로 해야만 하는 것은 아니다. 위 그림과 같이 중간에 빈칸을 넣을수도 있다.

image

edit distance를 이용 두 문장간의 유사성을 파악할수도 있다.

image
image

3 2 Computing Minimum Edit Distance
https://youtu.be/fN3Js7H72HE

image
image

edit distance 알고리즘을 이해하는데 도움이 되는 영상

https://youtu.be/We3YDTzNXEk

3 3 Backtrace for Computing Alignments
https://youtu.be/MnE10oJ2jX4

edit distace를 하는 과정에 back tracking (tracing) 작업을 추가로 함으로써 어는 부분에서 insertion이 되었는지 나중에 알수 있으며 이를 통해 alignment가 가능하게 된다.

image
image

위 그림에서 화살표가 세가지 있는경우 어느 방향으로 부터 현재값이 기인하는지 상관없다는 것을 의미한다. 맨윗줄 3의경우는 옆이나 밑에서 오기보다 대각선 하단에서 기인하는 것이 효율적인 경로이므로 이경우는 대각선방향만 선택한다. 이런 계산 과정을 하다보면 특정방향으로 부터만 기인하는 것이 효율적이 있는데 이런 경우 insertion, deletion, substitution 중 하나의 작업만 효율적이란 이야기다. 

image
image

3 4 Weighted Minimum Edit Distance

https://youtu.be/9G-EwniAaPA

image
image

위 그림은 각 알파벳 별로 잘못 오인되는 경우의 수를 보여주고 있다. 특정 알파벳이 특정 알파벳으로 오인되는 경우가 많은 것을 알수 있다. 그래서 weighted min edit distance를 사용 알고리즘 성능을 높일수 있다.

image

3 5 Minimum Edit Distance in Computational Biology
https://youtu.be/96pL6xTP3W8

위의 needleman – wunsch algorithm은 global sequence alignment에 많이 사용되는 알고리즘중의 하나이다. -i * d , -j * d부분은 시작으로 부터 얼마나 떨어져서 맷칭이 시작되는지를 보고 감점하는 부분이다. 

local sequence alignment의 경우 시작이나 마지막 부분에 있는 빈공간은 신경쓰지 않는다.

smith waterman algorithm의 iteration부분을 보면 음수의 값이 있는 경우 0으로 대체되게 된다. 즉 최소값이 0이 되게 된다. 

위 두 그림은 같은 데이터라도 맷칭부분을 다양하게 할수 있는 것을 보여준다.

Comments are closed.

Post Navigation