Suboptimal local alignment

Alignment는 두 개의 서열을 나열하여 두 서열의 유사성같은 것들을 알아내는 것이다. Gloabl alignment는 서열의 전체부위를 서로 나열하여 서열의 전체 유사성을 확인하는 반면, Local alignment는 말 그대로 부분적으로 서로 나열하여 부분의 유사성을 확인한다.

https://rosalind.info/problems/subo/

ROSALIND | Suboptimal Local Alignment

 

 이 문제에서는 두 개의 서열 중 공통된 서열 r을 찾는다. 이 r은 32~40bp 정도이고 3의 Hamming distance 정도의 차이를 각 복제마다 가질 수 있다. 이 r이 각 서열에 몇 번이나 있는지 찾는 문제이다.

 원래 이 문제를 풀기 위해서는 EMBOSS의 Lalign을 사용한다. Lalign을 사용하여 공통된 서열을 찾고, 이 공통된 서열이 hamming distance가 3 정도 차이나는 정도에서 각 서열에 몇 번 있는지 확인하는 프로그램을 돌려 찾는게 원래의 의도이다.

 허나 필자는 dotletJS(https://dotlet.vital-it.ch/) 를 이용하여 이 문제를 풀었다. 이 사이트는 웹앱으로 두 뉴클레오타이드/단백질 서열의 얼라이먼트를 dot plot으로 보여준다. 

 필자는 테스트 케이스가 위와 같이 나와 서열 1에 8개의 공통서열 r이, 서열2에는 4개의 공통서열 r이 있다고 답을 내서 맞게 되었다.