서열정렬이란?
정의
염기서열 간의 유사도를 근거로 나열하는 것을 서열정렬sequence Alignment이라 한다.
설명
생명정보공학에서 유전체의 길이는 무척 길기 때문에 이를 데이터화하는 것부터가 엄청난 일이다. 상상하기에는 우리도 중합효소처럼 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) 이 있다.