부록 D20: 문자열 알고리즘과 서열 비교
이 장에서 배울 것
이번 장에서는 문자열 알고리즘(string algorithm)과 서열 비교(sequence comparison)를 배웁니다. 문자열은 글자들이 순서대로 이어진 것입니다. DNA 서열 ATGCGT도 문자들이 이어진 문자열로 볼 수 있습니다. 단백질 서열도 아미노산 기호가 이어진 문자열로 볼 수 있습니다.
핵심 용어를 먼저 정리하겠습니다.
- 문자열(string): 문자들이 순서대로 이어진 자료입니다.
- 부분문자열(substring): 긴 문자열 안에 들어 있는 연속된 일부 문자열입니다.
- 표지서열(motif): 생물학적으로 의미가 있을 수 있는 짧은 반복 패턴입니다.
- 정렬(alignment): 두 서열을 서로 대응되도록 맞추는 작업입니다.
- 해밍거리(Hamming distance): 길이가 같은 두 문자열에서 서로 다른 자리의 개수입니다.
- 편집거리(edit distance): 한 문자열을 다른 문자열로 바꾸기 위해 필요한 삽입, 삭제, 치환의 최소 횟수입니다.
- 동적계획법(dynamic programming): 큰 문제를 작은 문제로 쪼개어 표를 채우듯 푸는 방법입니다.
가장 쉬운 비유: 두 문장 비교하기
고양이가 잔다와 고양이가 뛴다를 비교해 봅시다. 앞부분은 비슷하지만 마지막 동사가 다릅니다. DNA 서열 비교도 비슷합니다. 두 서열이 어디가 같고 어디가 다른지 찾아서, 두 생명체나 두 유전자가 얼마나 가까운지 추정합니다.
DNA 서열은 문자열이다
DNA는 A, T, G, C라는 네 종류의 염기로 이루어집니다. 그래서 컴퓨터 입장에서는 DNA를 문자열처럼 다룰 수 있습니다.
ATGCGTAC
이 문자열에서 CGT는 부분문자열입니다. 특정 짧은 패턴이 반복해서 나오면 생물학적으로 중요한 조절 부위일 가능성도 있습니다.
표지서열 찾기
표지서열은 서열 안에서 반복적으로 나타나거나 기능과 관련될 수 있는 짧은 패턴입니다. 예를 들어 ATG가 어떤 서열 안에 몇 번 나오는지 세는 작업은 아주 기본적인 문자열 분석입니다.
서열: ATGAAATGCCATG
표지서열 ATG의 등장 횟수: 3번
실제 연구에서는 더 복잡한 패턴과 확률 모델을 쓰지만, 기본은 “문자열 안에서 의미 있는 패턴을 찾는다”입니다.
해밍거리
해밍거리는 길이가 같은 두 문자열에서 서로 다른 자리의 개수입니다.
서열 1: A T G C
서열 2: A C G T
차이 : * *
2번째 자리와 4번째 자리가 다르므로 해밍거리는 2입니다. 해밍거리는 길이가 같은 서열을 비교할 때 쉽고 빠릅니다.
편집거리
서열 길이가 다를 때는 삽입이나 삭제도 고려해야 합니다. 편집거리는 한 서열을 다른 서열로 바꾸기 위해 필요한 최소 편집 횟수입니다.
가능한 편집은 보통 세 가지입니다.
삽입: 문자를 하나 넣기
삭제: 문자를 하나 지우기
치환: 문자를 다른 문자로 바꾸기
예를 들어 ATG를 ATCG로 바꾸려면 C 하나를 삽입하면 됩니다. 편집거리는 1입니다.
정렬
정렬은 두 서열을 비교하기 좋게 맞추는 작업입니다. 중간에 빠진 부분은 -로 표시할 수 있습니다.
서열 1: A T G - C
서열 2: A T G A C
이렇게 맞추면 두 서열이 대부분 같고, 한 위치에 삽입 또는 삭제가 있었다고 볼 수 있습니다.
동적계획법의 직관
서열 정렬은 가능한 맞춤 방법이 너무 많습니다. 동적계획법은 이 문제를 작은 비교표로 쪼개어 풉니다. 입문 단계에서는 표를 직접 복잡하게 채울 필요는 없습니다. 중요한 것은 “긴 서열 비교를 작은 서열 비교들의 누적으로 해결한다”는 생각입니다.
계산 감각
이 장에서는 다음 계산을 다룹니다.
해밍거리 = 서로 다른 자리의 개수
GC 비율 = (G 개수 + C 개수) / 전체 길이
표지서열 등장 횟수 = 특정 패턴이 나온 횟수
간단한 편집거리 = 필요한 삽입·삭제·치환 횟수
예를 들어 ATGC와 ATCC의 해밍거리는 1입니다. ATGC의 GC 비율은 G 1개와 C 1개이므로 2 / 4 = 0.5, 즉 50%입니다.
생물정보학에서 왜 중요한가
서열 비교는 생물정보학의 오래된 핵심 문제입니다. 유전자 기능 예측, 진화적 관계 추정, 변이 탐지, 유전체 정렬, 단백질 비교가 모두 문자열 비교와 연결됩니다.
보강: 전역정렬과 지역정렬
정렬에는 크게 전역정렬과 지역정렬이 있습니다. 전역정렬은 두 서열 전체를 처음부터 끝까지 맞추려는 방법입니다. 두 서열이 전체적으로 비슷하고 길이도 비슷할 때 적합합니다. 지역정렬은 긴 서열 안에서 특히 비슷한 부분만 찾습니다. 긴 유전체 안에서 보존된 짧은 기능 부위를 찾을 때 유용합니다.
전역정렬: 두 서열 전체를 맞춘다.
지역정렬: 가장 비슷한 일부 구간을 찾는다.
예를 들어 한 단백질 전체를 비교한다면 전역정렬이 어울릴 수 있고, 긴 DNA 안에서 특정 motif와 비슷한 조절 부위를 찾는다면 지역정렬이 더 자연스럽습니다.
점수, mismatch, gap의 의미
정렬은 단순히 같고 다름을 세는 것에서 끝나지 않습니다. 보통 match에는 보상을 주고, mismatch와 gap에는 벌점을 줍니다.
match: 같은 문자가 맞춰짐 → 점수 증가
mismatch: 다른 문자가 맞춰짐 → 점수 감소
gap: 삽입 또는 삭제로 빈칸이 생김 → 점수 감소
예를 들어 match +1, mismatch -1, gap -2라고 합시다. 아래 정렬은 match 3개, mismatch 1개, gap 1개입니다.
A T G - C
A T A G C
점수는 다음과 같습니다.
3×(+1) + 1×(-1) + 1×(-2) = 3 - 1 - 2 = 0
이런 점수 체계는 어떤 차이를 더 심각하게 볼지 정하는 규칙입니다. 단백질 서열에서는 어떤 아미노산 치환은 비슷한 성질이라 덜 나쁘게 보고, 어떤 치환은 더 크게 벌점을 줄 수도 있습니다.
motif는 우연히도 나올 수 있다
짧은 motif는 생물학적으로 중요할 수 있지만, 짧을수록 우연히 나타날 가능성도 큽니다. 예를 들어 4글자 DNA motif는 가능한 조합이 4⁴ = 256개입니다. 긴 유전체에서는 특정 4글자 패턴이 우연히 여러 번 나올 수 있습니다. 그래서 motif 발견은 등장 횟수뿐 아니라 배경 빈도, 보존성, 기능 실험과 함께 해석해야 합니다.
보강 학습: 문자열 알고리즘과 서열 비교
왜 필요한가: DNA/RNA/단백질 서열을 문자열처럼 저장하고 비교하기 위해 필요합니다.
공식 읽기: Hamming distance = 서로 다른 위치의 개수. 길이가 같은 두 문자열에서 각 위치를 비교해 다른 칸을 셉니다.
숫자 예시: ACGT와 ACCT는 세 번째 위치만 달라 Hamming distance가 1입니다.
생물정보학에서 쓰이는 장면: barcode 비교, read 오류 허용, 서열 유사도 탐색, alignment 해석에서 쓰입니다.
흔한 오해와 주의점: 가장 높은 alignment score가 항상 진화적 진실은 아닙니다. scoring rule, gap penalty, 반복서열 영향을 받습니다.
핵심 정리
DNA와 단백질 서열은 컴퓨터에서 문자열로 다룰 수 있습니다. 해밍거리는 같은 길이 서열의 자리 차이를 세고, 편집거리는 삽입·삭제·치환까지 고려합니다. 정렬은 두 서열을 비교하기 좋게 맞추는 작업이고, 동적계획법은 긴 서열 비교를 작은 문제들의 누적으로 푸는 방법입니다.
문제 풀이
문자열 알고리즘과 서열 비교
주관식 답안은 Gemini API로 채점합니다. API 키는 이 브라우저에만 저장됩니다.
-
1. [쉬움] 객관식
문자열의 설명으로 가장 적절한 것은?
-
2. [쉬움] 객관식
DNA 서열을 컴퓨터에서 문자열처럼 볼 수 있는 이유는?
-
3. [쉬움] 객관식
길이가 같은 두 서열에서 서로 다른 자리 수를 세는 거리는?
-
4. [쉬움] 객관식
편집거리가 고려하는 작업이 아닌 것은?
-
5. [계산] 객관식
ATGC와 ATCC의 해밍거리는?
-
6. [계산] 객관식
AAAA와 TTTT의 해밍거리는?
-
7. [계산] 객관식
ATGC의 GC 비율은?
-
8. [계산] 객관식
GGCC의 GC 비율은?
-
9. [계산] 객관식
ATGAAATGCCATG에서 ATG는 몇 번 등장하는가?
-
10. [계산] 객관식
ATG를 ATCG로 바꿀 때 C 하나를 넣으면 된다. 이때 간단한 편집거리는?
-
11. [보통] 객관식
정렬에서 - 기호가 나타낼 수 있는 것은?
-
12. [보통] 객관식
동적계획법의 직관으로 가장 적절한 것은?
-
13. [계산] 객관식
ATGA와 ATTA의 해밍거리는?
-
14. [계산] 객관식
ACGTAC에서 부분문자열 CGT는 몇 번째 자리부터 시작하는가? 첫 자리를 1번으로 센다.
-
15. [계산] 객관식
AATTCC에서 GC 비율은?
-
16. [계산] 객관식
AAAAAA에서 AA는 겹치지 않게 세면 몇 번 등장하는가?
-
17. [계산] 객관식
ACG와 ACG의 해밍거리는?
-
18. [계산] 객관식
ACG를 AG로 바꾸려면 C를 하나 삭제하면 된다. 이때 편집거리는?
-
19. [계산] 객관식
ATATAT에서 AT는 겹치지 않게 세면 몇 번 등장하는가?
-
20. [계산] 객관식
ATGCGA의 길이는?
-
21. [보통] 객관식
서열 비교가 유전자 기능 예측에 도움 되는 이유는?
-
22. [보통] 객관식
길이가 다른 서열을 비교할 때 해밍거리만으로 부족한 이유는?
-
23. [쉬움] 객관식
표지서열을 찾는 작업의 기본 생각은?
-
24. [쉬움] 객관식
서열 정렬의 목적은?
-
25. [계산] 객관식
ATGCTA와 ATGCAA의 해밍거리는?
-
26. [계산] 객관식
서열 ACGCGT의 GC 비율은?
-
27. [계산] 객관식
서열 ATGATGAT에서 motif ATG는 겹치지 않게 몇 번 등장하는가?
-
28. [계산] 객관식
ATG를 ATCG로 바꾸는 최소 편집 횟수는?
-
29. [계산] 객관식
정렬에서 match 5개, mismatch 2개, gap 1개이고 점수가 match +1, mismatch -1, gap -2라면 총점은?
-
30. [개념 구분] 객관식
길이가 다른 두 서열을 비교할 때 해밍거리보다 편집거리가 더 자연스러운 이유는?
-
31. [계산] 객관식
DNA 4글자 motif의 가능한 조합 수는?
-
32. [비교] 객관식
긴 유전체 안에서 보존된 짧은 기능 구간만 찾고 싶을 때 더 자연스러운 정렬은?
-
33. [쉬움] 객관식
ACGT와ACCT의 Hamming distance는? -
34. [보통] 객관식
Hamming distance 적용 조건은?
-
35. [쉬움] 객관식
서열 정렬에서 gap은?
-
36. [어려움] 객관식
alignment score가 달라질 수 있는 이유는?
-
37. [보통] 객관식
반복서열에서 mapping이 어려운 이유는?
-
주관식 38. [보통] 주관식 · Gemini 채점
DNA 서열을 문자열로 볼 수 있다는 말의 의미를 설명하라.
-
주관식 39. [보통] 주관식 · Gemini 채점
해밍거리와 편집거리의 차이를 설명하라.
-
주관식 40. [보통] 주관식 · Gemini 채점
서열 정렬이 생물정보학에서 중요한 이유를 설명하라.
-
주관식 41. [보통] 주관식 · Gemini 채점
동적계획법이 긴 서열 비교에 필요한 이유를 설명하라.
-
주관식 42. [심화] 주관식 · Gemini 채점
짧은 motif가 여러 번 등장한다고 해서 곧바로 기능적 조절 부위라고 단정하면 안 되는 이유를 설명하라.
-
주관식 43. [보통] 주관식 · Gemini 채점
barcode
ATCGGA와ATGGTA의 Hamming distance를 계산하라. -
주관식 44. [보통] 주관식 · Gemini 채점
서열 정렬에서 scoring rule과 gap penalty를 확인해야 하는 이유를 설명하라.