logo

서열정렬이란? 📂알고리즘

서열정렬이란?

정의

염기서열 간의 유사도를 근거로 나열하는 것을 서열정렬sequence Alignment이라 한다.

assembly.png 1

설명

생명정보공학에서 유전체의 길이는 무척 길기 때문에 이를 데이터화하는 것부터가 엄청난 일이다. 상상하기에는 우리도 중합효소처럼 DNA상류부터 하류까지 순서대로 읽으면서 저장하면 좋을 것 같지만, 현실적으로는 그렇게 할 수가 없기 때문에 조각으로 나눠진 짧은 염기서열인 리드(Reads) 를 많이 얻어서 그걸 이어붙여야한다. 그러면 이들의 양끝에서 어떤 부분이 겹치는지(Overlapping) 확인하게 되는데, 그 과정에서 서열정렬 을 하게 된다.

언뜻 이 과정은 의구심이 들지만 생각보다 무척 정확하다. 가령 다음과 같이 두 리드의 양 끝 4개 ${\color{red}AATC}$가 일치한다고 상상해보자: $$ ATCGCC {\color{red}AATC} \\ {\color{red}AATC} TATTC $$ 아주 단순하게 생각해서 네 염기가 우연히 일치하는 경우의 수는 $4^{4} = 256$ 가지 중 단 하나뿐이고, 확률분포가 있으니 가설검정을 통해 이것이 얼마나 확실한지도 확인할 수 있다. 4개만으로도 이정도니 실제 정렬은 꽤 믿을만하다고 주장할 수 있을 것이다. 물론 이런 방법으로는 틀리는 경우도 있기 때문에 가능한 한 많은 양의 리드를 읽어서 보완하게 되는데, 그렇게 만들어진 긴 서열을 **합의서열(Consensus Sequence)**이라 부른다. 실제로 NGS(Next Generation Sequence) 데이터는 각 위치의 염기와 그 염기가 정확할 확률을 병기하는 식으로 제공된다. 합의서열이 만들어지고 나면 다른 개체와의 비교가 수월하기 때문에 서열정렬의 맥락에선 **레퍼런스 서열(Reference Sequence)**이라도 불리며, 참조서열과 비교되는 서열을 **쿼리 서열(Query Sequence)**이라 한다.

염기서열은 크게 두 염기서열을 비교해 유사도를 구하는 **쌍서열정렬(Pairwise Sequence Alignment)**과 여러 염기서열을 비교하는 다중서열정렬(Multiple Sequence Alignment) 로 나눌 수 있으며, 쌍서열정렬은 다시 다음과 같이 나뉜다:

  • 전역정렬(Global Alignment): 두 서열의 공통 부분이 가장 많아지는 정렬을 찾는다.
  • 반전역정렬(Semi-global Alignment): 레퍼런스 서열에서 쿼리 서열과 가장 비슷한 부분을 찾는다.
  • 국소정렬(Local Alignment): 두 염기서열에서 가장 비슷한 부분들을 찾는다.나이브하게 생각했을 때 서열정렬에는 아주, 아주아주 많은 계산이 필요하기 때문에 동적 프로그래밍을 응용한 알고리즘이 개발되었다. 전역정렬과 국소정렬의 대표적인 알고리즘으로는 각각 **니들맨-분쉬 정렬(Needleman-Wunsch Alignment)**과 스미스-워터맨 정렬(Smith-Waterman Alignment) 이 있다.