우리는 모두 같은 사람이더라도 다른 생김새를 가지고 있습니다. 무엇이 이러한 차이를 만들까요? 바로 유전체 서열입니다. 당, 인산, 염기로 이루어진 핵산이 단위체로써 중합해 유전체를 만들고, 각 단위체의 서로 다른 염기, A, T, G, C의 순서에 따라 정보를 결정할 수 있게 됩니다. 이렇게 저장된 정보는 그 사람을 이루는 모든 생물학적 요소를 나타나게 됩니다. 따라서, 만약 어떤 사람의 서열을 알 수 있다면, 이는 그 사람이 가지고 있는 모든 생물학적 특성을 분석할 수 있다는 의미이며, 이는 현 인류에게 매우 중요한 과제입니다. 하지만, 현재 기술로 한 번에 파악할 수 있는 서열의 길이는 약 250bp (bp ; base pair의 약자로, 서열의 길이를 염기쌍 개수로 나타내는 단위)이며 인간의 전체 유전체 길이는 30억bp입니다. 따라서, 우리에게는 짧은 서열 조각(250bp.)을 모아 큰 서열(30억 bp.)을 만들어 내야 하는 과제가 주어집니다.
생물학에서는 이러한 과정을 assembly라고 합니다. ‘모아 조립한다’라는 본래의 뜻과 비슷하게, 짧은 조각을 모아 긴 서열을 만들어낸다는 의미입니다. 결국, 비유해 보자면, 우리에게는 퍼즐 조각이 주어져 있고, 이를 바탕으로 완성된 그림을 만들어야 하는 것입니다. 하지만 실제 퍼즐 맞추기에서는 전체 사진이 주어져 있어 이를 바탕으로 퍼즐을 맞추지만, 인간의 유전체 분석은 전체 서열이 주어져 있지 않습니다. 이처럼, 전체 서열을 모르는 상태에서 짧은 조각을 모으는 assembly를 de novo assembly(de novo ; ‘바로 그 자리에서’)라고 합니다. 이번 월간 글립 6월호에서는 de novo assembly에 대한 알고리즘을 분석할 것입니다. 그리고, 이 알고리즘을 수행하는 과정에서 맞닥뜨리게 되는 여러 가지 현실적 문제를 해결하는 방법에 대해 알아볼 것입니다.
De novo assembly의 핵심은 우리가 가지고 있는 짧은 서열의 겹침으로써 긴 서열을 만드는 것입니다. 다시 말해, 아래 그림 1처럼, 1, 2번 서열을 가지고있다면, 겹치는 부분인 붉은 부분을 기준으로 더 긴 조각을 얻을 수 있게 되는 것입니다.
그림1. De novo assembly의 예시
긴 전체 서열을 얻기 위해 위 과정을 반복해야 하므로 사람이 직접 진행하는 것보다 컴퓨터를 이용하는 것이 효율적입니다. 컴퓨터는 이 과정을 de bruijn graph를 이용한 알고리즘으로 진행합니다. 이 방식은 우리가 알고 있는 짧은 서열을 길이 k의 더 짧은 서열로 나누어 중복 및 겹침을 찾는 과정으로 진행됩니다. 길이가 k 인 각각의 서열을 따로 나타내고, 중복된다면 하나로 표현합니다. 이때, 전체 긴 서열에서 바로 옆에 존재한다고 생각되는 길이 k 의 조각은 화살표로 연결하여 하나의 그래프를 구성합니다.
이해를 돕기 위해 [ACGA, ACGT, ATAC, CGAC, CGTA, GACG, GTAT, TACG]의 서열이 나열된 예시를 생각해봅시다. 이제 이 서열들을 k=3의 작은 조각으로 나눠보면, ACGA는 ACG와 CGA가 됩니다. 그리고 이들은 인접하기 때문에 그림 2(왼)처럼 화살표로 연결할 수 있습니다. 또한, 두 번째 서열인 ACGT를 나누어 보면 ACG와 CGT가 됩니다. 이때 ACG는 ACGA 와 ACGT에서 중복되기 때문에 하나의 서열로 나타냅니다. 이러한 과정을 통해 전체 서열을 연결해보면, 그림 2(우)같은 그래프를 얻게 되고, 붉은색 화살표가 가리키는 순서에 따라 읽어보면 전체 서열인 ATACGACGTAT를 찾을 수 있습니다.
그림 2. De bruijn graph의 적용
하지만, 이 방법은 큰 문제가 있는데, 바로 반복 서열의 문제입니다. 사람 유전체 서열의 55% 정도는 반복 서열입니다 [1]. 다시 말해 같은 서열이 계속해서 나타난다는 의미입니다. 이때, 반복 서열은 앞서 구한 그래프의 경로를 하나로 고정하지 않고 여러 개의 경우의 수를 만들어냅니다. 그렇기 때문에 아무리 그래프를 잘 그린다고 하더라도 하나로 고정되지 않은 결과를 얻게 되고, 이는 우리의 본래 목적과 부합하지 않습니다. 이해를 돕기 위해 아래 그림 3에서, 서열 R이 반복되어 ARBRCRD, ARCRBRD의 두 가지 경우가 가능한 상황을 봅시다. 그러면 앞서 언급했던 반복 서열의 문제가 발생하게 됩니다. 이를 어떻게 해결할 수 있을까요?
그림 3. 반복 서열의 문제
의외로 이러한 문제에 대한 접근법은 많은 알고리즘 연구자들의 관심을 불러일으켰고, 이 문제 상황을 TSP(Traveling Salesman Problem)라고 합니다. TSP는 다음 질문으로부터 출발합니다.
“어떤 세일즈맨이 1에서 4의 도시를 돌아다니며 영업활동을 한다. 이때 각 도시를 이동하는 교통비는 각각 다르다. 만약 1에서 출발하여 다시 1로 돌아오고자 할 때 최소한의 교통비를 가지고 이동하려면 어떻게 해야 할까? 그리고, 어느 도시에서 출발하는 것이 좋을까?”
그림 4. TSP 문제[2]
다시 말해서, 그림 4와 같은 상황에서 교통비를 가장 적게 지불하려면 어떤 경로를 선택해야 하는지의 문제라고 할 수 있습니다. 또한, 도시의 총 개수와 도시 간의 비용 차이로 결정되는 모든 문제들은 TSP의 일종이라고 생각할 수 있습니다. 즉, 우리의 문제도 de bruijn graph에서 가능한 서열의 종류를 경로로 모두 구하고, 그 중에서 가장 최적의 경우를 찾는 것이기 때문에 TSP에 해당합니다.
이에 대한 본질적인 해결 방법은 간단합니다. 처음과 끝을 도시 ①로 고정하고, 나머지 도시들의 순서를 순열로 구성하여 각 경우에서 발생하는 총 교통비를 구하는 것입니다. 그리고, 고정한 도시의 종류를 ②, ③, ④로 바꾸며 전체에서 최소인 경우를 찾으면 됩니다. 그림 4의 경우에는 총 24가지의 경우가 있겠습니다. 하지만 이는 매우 비효율적인 방식입니다. 개의 도시를 분석하기 위해 번의 분석을 해야 하는데, 이는 의 값이 커짐에 따라 매우 급격하게 증가하기 때문입니다. (부록 1. 참고)
따라서 사람들은 최소 비용인 하나의 경로를 찾기보단 최소 비용일 수 있는 여러 가지의 후보를 먼저 찾고, 이들을 이용한 분석을 진행하는 방식으로 돌파구를 찾았습니다. 결국, 최적화된 해결책이 아닌, 일종의 절충안인 것입니다. 이 해결책은 MST(Minimal Spanning Tree)와 pre-order traveling의 두 가지의 개념으로 이루어집니다.
MST란 모든 꼭짓점을 연결하는 tree형태의 경로 중 최소 비용인 경우를 의미합니다. 이를 구성하는 알고리즘을 Prim’s Algorithm이라고 하는데, 그래프에서 비용이 가장 작은 변을 하나 고르고, 그 변의 꼭짓점들에 연결된 다른 변들 중 가장 비용이 작은 변을 다시 골라 새로운 그래프를 형성하는 과정을 반복하는 것입니다. 그림 4에서 예시를 들어보자면, 변 (1, 2)를 먼저 고르고, (1, 3), (1, 4)를 골라 MST를 다음과 같은 그림 6처럼 표현할 수 있습니다.
그림 5. 새로 만들어진 MST
그림 5처럼, tree구조는 필연적으로 중심의 역할을 하는 root와 그 나머지 leaf로 구성됩니다. 이 경우, ①이 root이고, 나머지가 leaf라고 할 수 있습니다. 이제 경로를 생각할 것인데, 그 경로를 pre-order traveling으로 구성할 것입니다. 이는 경로상에서 root의 위치가 leaf에 대하여 어디에 있는지를 설명하는 방식입니다. 만약 root가 leaf보다 먼저 등장하면, 우리는 이를 pre-order라고 합니다. 그렇기 때문에 root인 ①을 먼저 방문하고, 나머지 leaf는 순서대로 ②, ④, ③을 방문한다고 생각할 수 있습니다. 결국, 우리는 ①, ②, ④, ③ 순서의 경로를 얻습니다. (부록 2. 참고)
이 경우, Prim’s Algorithm은 개의 도시에 대해 의 데이터를 분석하게 하고, pre-order traveling을 찾는 과정은 번의 분석만 하면 되므로, 최종적으로 ) 번의 분석을 하면 됩니다. 이전의 과 비교해보면 아주 효율적인 과정입니다. (부록 1. 참고)
이를 다시 서열의 문제에 적용해본다면, 위 방식으로 구해진 서열은 정확한 정답은 아니지만 정답에 매우 근접합니다. 그렇기 때문에 우리는 이 서열과 비슷한 서열들에 대해서만 분석하면 될 것이고, 이는 필요한 계산의 양을 많이 줄여준다는 점에서 효율적인 분석법이라고 할 수 있습니다. 물론, 이렇게 얻어진 서열과 비슷한 서열을 얻어내는 과정에서 얼마나 비슷한 걸 선택할지에 따라 답이 큰 영향을 받겠으나, 현재 생명과학의 여러 분야에서 신뢰할만한 데이터를 바탕으로 기준을 수립해 나가고 있습니다.
생명과학은 얼핏 보면 생명체만을 다루고 공학이나 데이터과학과는 관련성이 없어 보이지만, 이번 글에서 생명과학 문제에 적용했던 알고리즘은 오히려 컴퓨터공학의 주 관심사 중 하나입니다. 이와 같이 생명과학에서 알고리즘을 이용하는 방법론은 요즘 가장 촉망받는 분야인 정보생물학과 큰 관련이 있습니다. 여러 분야를 융합하는 최근의 연구 트렌드가 이끌어낼 미래가 더욱 더 기대됩니다!
[부록 1. 알고리즘의 효율성 분석]
이제 알고리즘의 효율성을 어떻게 파악할 수 있는지 알아봅시다. 알고리즘의 효율성이라고 하면, 가장 먼저 어떠한 과제를 수행하는데 소요되는 시간을 비교하는 예시를 떠올릴 수 있습니다. 하지만 이는 컴퓨터의 자체적인 능력에 크게 의존합니다. 아무리 효율적인 알고리즘이더라도 아주 오래된 컴퓨터에서 작동시키면 오래 걸릴 것이고, 아주 비효율적인 알고리즘이어도 슈퍼 컴퓨터에서 작동시키면 아주 빠를 것입니다. 그렇기 때문에 시간을 비교하는 것은 정확하지 않습니다.
그렇기 때문에 사람들은 complexity function, 을 정의했습니다. 이는 N개의 data가 주어졌을 때 몇 번의 계산을 시행했을 때 우리가 원하는 결과에 도달하는지에 대한 함수입니다. 다시 말해 알고리즘의 효율성을 시간이 아닌 횟수의 항으로 계산하고자 하는 것입니다. 예를 들어, 개의 data로 번의계산을 하는 알고리즘은 = 입니다. 특히 이 경우에서, 이 매우 커지면 complexity function의 값에 큰 영향을 주는 것은 이 아니라 이며, 이항이 알고리즘의 효율성에 큰 영향을 줍니다. 이는 asymptotic upper bound O로 분석할 수 있고, 아래 부록 그림 1과 같이 정의됩니다.
부록 그림 1. O의 정의
따라서 여러 종류의 알고리즘을 asymptotic upper bound O로 분석하게 되면 같은 수준의 complexity를 가지는 알고리즘을 묶어 생각할 수 있고, 이를 complexity class라고 합니다. 다시 본문의 내용으로 돌아가보자면, TSP의 경우는 O(!), 타협한 해결책의 경우는 입니다. 하지만, 문제의 실질적인 해결을 위해 O() 이상의 경우를 생각하지 않습니다. N의 값이 커짐에 따라 해야 하는 계산의 양이 지나치게 켜져 유용하지 않기 때문입니다.
[부록 2. Tree]
Tree는 꼭짓점과 변으로 구성되어 있는 그래프의 한 종류입니다. 위 아래의 계층적인 체계를 가지고 있는 모든 그래프를 tree라고 합니다. Tree의 계층 중 가장 위에 존재하는 원소를 가장 위에 두고, 순서대로 아래를 향해 그려 나가면 가장 중심에 있는 원소가 나타납니다. 이를 root node라고 하고, 가장 말단의 원소를 leaf node라 합니다.
Tree의 가장 대표적인 성질은 acyclic하다는 것입니다. 이는 곧, 하나의 꼭짓점에서 출발하여 다시 그 꼭짓점으로 돌아 오는 경로가 존재하지 않다는 것입니다. 그렇기 때문에 MST는 기존의 TSP와 달리 출발한 도시로 다시 되돌아 오지 않습니다.
[참고 문헌]
Criscione, Steven W., et al. "Transcriptional landscape of repetitive elements in normal and cancer human cells." BMC genomics 15.1 (2014): 1-17.
[그림 출처]
https://www.cdn.geeksforgeeks.org/wp-content/uploads/Euler12.png
Written by GLEAP 10기 구자영
Edited by GLEAP 학술팀·홍보팀
Comments