부록 D19: 그래프 이론

4 분 소요

이 장에서 배울 것

이번 장에서는 그래프 이론(graph theory)을 배웁니다. 여기서 그래프는 막대그래프나 꺾은선그래프가 아니라, 대상들 사이의 관계를 점과 선으로 그린 지도입니다. 계산생물학에서는 유전자와 유전자, 단백질과 단백질, 세포와 세포, 질병과 유전자 사이의 관계를 자주 다룹니다. 이런 관계를 정리하는 기본 언어가 그래프입니다.

핵심 용어를 먼저 정리하겠습니다.

점(node): 관계망에서 하나의 대상을 나타냅니다. 유전자 하나, 단백질 하나, 사람 하나가 점이 될 수 있습니다.
선(edge): 두 점 사이의 관계를 나타냅니다. 두 단백질이 서로 붙는 관계, 한 유전자가 다른 유전자를 조절하는 관계가 선이 될 수 있습니다.
방향그래프(directed graph): 선에 방향이 있는 그래프입니다. 예를 들어 A → B는 A가 B에 영향을 준다는 뜻입니다.
가중그래프(weighted graph): 선마다 관계의 강도가 숫자로 붙은 그래프입니다.
차수(degree): 한 점에 연결된 선의 개수입니다.
경로(path): 한 점에서 다른 점까지 선을 따라 이동하는 길입니다.
중심성(centrality): 관계망에서 어떤 점이 얼마나 중요한 위치에 있는지 나타내는 생각입니다.
군집(community): 서로 촘촘하게 연결된 점들의 묶음입니다.

그래프 이론의 기본 구조

가장 쉬운 비유: 친구 관계 지도

반 친구들의 친분 관계를 생각해 봅시다. 사람 한 명을 점으로 그리고, 서로 친하면 선으로 연결합니다. 친구가 많은 학생은 선이 많이 붙어 있습니다. 어떤 학생은 여러 무리를 이어 주는 다리 역할을 할 수도 있습니다. 그래프 이론은 이런 관계를 숫자와 그림으로 분석하는 방법입니다.

생물학에서도 비슷합니다. 단백질 하나를 점으로 놓고, 서로 결합하는 단백질끼리 선으로 연결하면 단백질 상호작용망이 됩니다. 유전자를 점으로 놓고, 한 유전자가 다른 유전자의 발현을 조절하면 방향이 있는 선을 그릴 수 있습니다.

점과 선

그래프의 가장 기본 구성요소는 점과 선입니다.

점: 유전자 A, 유전자 B, 단백질 C
선: A와 B가 함께 작동한다, B가 C를 조절한다

그래프는 복잡한 관계를 한눈에 보게 해 줍니다. 표로 보면 관계가 흩어져 보이지만, 그래프로 그리면 어떤 대상이 중심에 있는지, 어떤 대상들이 묶여 있는지 더 쉽게 볼 수 있습니다.

방향그래프와 가중그래프

모든 관계가 같은 것은 아닙니다. 어떤 관계는 방향이 있습니다. 예를 들어 전사인자라는 단백질이 어떤 유전자의 발현을 조절한다면, 보통 전사인자 → 유전자처럼 방향을 생각합니다. 이것이 방향그래프입니다.

어떤 관계는 강도가 있습니다. 단백질 A와 B가 매우 강하게 결합하면 선의 가중치가 클 수 있고, 약하게 결합하면 작을 수 있습니다. 이것이 가중그래프입니다.

차수: 연결이 얼마나 많은가

차수는 한 점에 붙은 선의 개수입니다. 어떤 유전자에 연결된 다른 유전자가 많다면, 그 유전자는 관계망에서 중요한 위치에 있을 가능성이 있습니다.

예를 들어 점 A가 B, C, D와 연결되어 있다면 A의 차수는 3입니다. 차수는 가장 간단한 중심성 지표입니다. 단, 차수가 높다고 항상 생물학적으로 가장 중요하다고 단정하면 안 됩니다. 데이터의 품질과 관계의 의미도 함께 봐야 합니다.

경로와 최단경로

경로는 한 점에서 다른 점으로 가는 길입니다.

A → B → C

이 경우 A에서 C로 가는 경로의 길이는 선 2개입니다. 여러 경로가 있을 때 가장 짧은 길을 최단경로라고 합니다. 생물학 네트워크에서는 한 유전자의 변화가 다른 유전자에 얼마나 가까운 경로로 영향을 줄 수 있는지 생각할 때 이런 개념이 쓰입니다.

군집: 촘촘한 묶음

그래프 안에는 서로 많이 연결된 작은 묶음이 생길 수 있습니다. 친구 관계에서 친한 무리가 생기는 것처럼, 단백질 관계망에서도 같은 기능을 수행하는 단백질들이 서로 촘촘하게 연결될 수 있습니다. 이런 묶음을 군집이라고 합니다.

군집을 찾으면 복잡한 네트워크를 기능 단위로 나눠 볼 수 있습니다.

계산 감각

그래프 이론에서는 아주 간단한 계산만으로도 관계망의 성질을 볼 수 있습니다.

차수 = 한 점에 연결된 선의 개수
무방향 그래프의 가능한 최대 선 개수 = n(n - 1) / 2
평균 차수 = 2 × 선 개수 / 점 개수
밀도 = 실제 선 개수 / 가능한 최대 선 개수

예를 들어 점이 5개인 무방향 그래프에서 가능한 최대 선 개수는 5 × 4 / 2 = 10개입니다. 실제 선이 4개라면 밀도는 4 / 10 = 0.4입니다.

평균 차수도 자주 씁니다. 점이 5개이고 선이 4개이면 평균 차수는 2 × 4 / 5 = 1.6입니다. 선 하나는 두 점에 붙어 있으므로 2를 곱합니다.

생물정보학에서 왜 중요한가

유전자 조절망, 단백질 상호작용망, 대사망, 세포 간 통신망은 모두 그래프로 표현할 수 있습니다. 그래프를 알면 “어떤 유전자가 중심에 있는가”, “어떤 단백질들이 기능 묶음을 이루는가”, “질병 유전자들이 같은 네트워크 근처에 모이는가” 같은 질문을 던질 수 있습니다.

보강: 중심성은 한 종류가 아니다

차수는 가장 쉬운 중심성입니다. 연결이 많은 점은 차수가 높습니다. 하지만 네트워크에서 중요한 위치는 연결 수만으로 결정되지 않습니다. 어떤 점은 연결 수가 많지는 않아도 두 큰 묶음을 이어 주는 다리 역할을 할 수 있습니다. 이런 경우에는 매개중심성(betweenness centrality)이 중요할 수 있습니다.

차수 중심성: 직접 연결이 얼마나 많은가
매개중심성: 다른 점들 사이의 길목 역할을 얼마나 하는가
근접중심성: 다른 점들까지 얼마나 가깝게 갈 수 있는가

단백질 상호작용망에서 차수가 높은 단백질은 허브처럼 보일 수 있습니다. 하지만 실험 데이터가 많이 연구된 단백질에 편향되어 있으면 차수가 높게 보일 수도 있습니다. 그래서 중심성 계산 결과는 생물학적 검증과 함께 읽어야 합니다.

연결요소와 모듈

그래프에서 서로 길로 연결된 점들의 묶음을 연결요소라고 합니다. 한 그래프 안에 서로 떨어진 여러 연결요소가 있을 수 있습니다. 단백질 네트워크에서는 특정 기능과 관련된 단백질들이 한 모듈로 촘촘히 연결되기도 합니다.

예를 들어 점 6개와 선이 다음과 같다고 합시다.

A-B, A-C, B-C, D-E

A, B, C는 서로 연결된 묶음이고, D와 E도 묶음입니다. F가 아무 선도 없다면 F는 혼자 떨어진 연결요소입니다. 이런 구조를 보면 네트워크가 하나의 큰 시스템인지, 여러 작은 시스템으로 나뉘는지 알 수 있습니다.

방향성과 가중치의 생물학적 의미

유전자 조절망에서 A → B는 A가 B에 영향을 준다는 뜻일 수 있습니다. 하지만 단백질 상호작용망에서 A-B는 보통 방향이 없는 관계입니다. 또한 선의 가중치가 상관계수인지, 결합 강도인지, 실험 신뢰도인지에 따라 해석이 완전히 달라집니다.

따라서 그래프를 볼 때는 먼저 “점은 무엇인가?”, “선은 무엇을 뜻하는가?”, “방향과 가중치는 어떤 의미인가?”를 확인해야 합니다. 그래프 계산은 그다음입니다.

보강 학습: 그래프 이론

왜 필요한가: 단백질 상호작용, 유전자 조절, 대사 경로처럼 관계 데이터를 노드와 엣지로 읽기 위해 필요합니다.

공식 읽기: degree(v)=노드 v에 연결된 엣지 수. v는 노드입니다. degree는 한 노드가 몇 개 관계를 갖는지 나타냅니다.

숫자 예시: A가 B,C,D와 연결되어 있으면 A의 degree는 3입니다.

생물정보학에서 쓰이는 장면: 네트워크 분석, pathway, 단백질 상호작용, 세포 간 신호 네트워크에서 쓰입니다.

흔한 오해와 주의점: 엣지는 항상 직접 원인 관계가 아닙니다. 물리적 결합, 상관, 문헌 기반 관계가 섞일 수 있습니다.

핵심 정리

그래프는 관계를 점과 선으로 나타내는 도구입니다. 점은 대상, 선은 관계입니다. 방향그래프는 관계의 방향을, 가중그래프는 관계의 강도를 나타냅니다. 차수, 평균 차수, 밀도, 최단경로 같은 간단한 계산은 생물학 네트워크를 읽는 기본 눈을 만들어 줍니다.

Gemini AI 채점

주관식 답안은 Gemini API로 채점합니다. API 키는 이 브라우저에만 저장됩니다.

API KEY 미등록

1. [쉬움] 객관식

그래프 이론에서 점(node)이 뜻하는 것은?

선택지 관계망에서 하나의 대상을 나타낸다. 항상 숫자 평균만 뜻한다. 그래프의 제목만 뜻한다. p-value의 다른 이름이다.
2. [쉬움] 객관식

선(edge)의 설명으로 가장 적절한 것은?

선택지 데이터의 결측값만 뜻한다. 두 점 사이의 관계를 나타낸다. 유전자 서열의 길이만 뜻한다. 표의 행 번호만 뜻한다.
3. [쉬움] 객관식

A가 B를 조절한다는 관계를 표현하기에 가장 적절한 그래프는?

선택지 막대그래프 원그래프 방향그래프 무조건 무방향 그래프
4. [쉬움] 객관식

가중그래프에서 가중치가 나타낼 수 있는 것은?

선택지 염색체의 색깔 파일 확장자 항상 표본 수 관계의 강도
5. [계산] 객관식

점 A가 B, C, D와 연결되어 있다. A의 차수는?

선택지 3 1 2 4
6. [계산] 객관식

점이 4개인 무방향 그래프의 가능한 최대 선 개수는?

선택지 4 6 8 12
7. [계산] 객관식

점 5개, 선 4개인 무방향 그래프의 평균 차수는?

선택지 0.8 4 1.6 2.5
8. [계산] 객관식

가능한 최대 선이 10개이고 실제 선이 5개이면 밀도는?

선택지 2 5 10 0.5
9. [계산] 객관식

A-B-C 경로에서 A에서 C까지 지나가는 선의 개수는?

선택지 2 1 3 4
10. [쉬움] 객관식

서로 촘촘하게 연결된 점들의 묶음은?

선택지 편향 군집 전사 삽입
11. [보통] 객관식

차수가 높은 점을 해석할 때 가장 조심해야 할 점은?

선택지 무조건 질병 원인이라고 봐야 한다. 항상 데이터 오류라고 봐야 한다. 차수가 높다고 항상 생물학적으로 가장 중요하다고 단정하면 안 된다. 계산이 불가능하다고 봐야 한다.
12. [쉬움] 객관식

단백질 상호작용망에서 점으로 가장 자연스러운 것은?

선택지 pH 값 하나 시험 날짜 그래프 배경색 단백질 하나
13. [계산] 객관식

점 6개인 무방향 그래프의 가능한 최대 선 개수는?

선택지 15 6 12 30
14. [계산] 객관식

점 8개, 선 12개인 무방향 그래프의 평균 차수는?

선택지 1.5 3 6 12
15. [계산] 객관식

가능한 최대 선이 15개이고 실제 선이 3개이면 밀도는?

선택지 0.5 3 0.2 5
16. [계산] 객관식

점 A에 선이 0개 붙어 있다. A의 차수는?

선택지 1 2 계산할 수 없음 0
17. [계산] 객관식

점 10개, 선 20개인 그래프의 평균 차수는?

선택지 4 2 10 20
18. [계산] 객관식

가능한 최대 선이 6개이고 실제 선이 6개이면 밀도는?

선택지 0 1 0.5 6
19. [계산] 객관식

A-B-C-D 경로에서 A에서 D까지 경로 길이는?

선택지 1 2 3 4
20. [계산] 객관식

점이 3개인 무방향 그래프의 가능한 최대 선 개수는?

선택지 2 6 9 3
21. [보통] 객관식

유전자 조절 관계처럼 원인 방향이 중요한 경우 필요한 것은?

선택지 방향 정보 항상 원형 배치 항상 같은 차수 항상 pH 계산
22. [보통] 객관식

평균 차수 공식에서 선 개수에 2를 곱하는 이유는?

선택지 점 하나가 항상 네 번 세어지기 때문이다. 선 하나가 두 점에 붙어 있기 때문이다. 밀도 공식과 같게 만들기 위해서다. 방향그래프에서는 점이 없기 때문이다.
23. [보통] 객관식

그래프가 생물정보학에서 유용한 가장 큰 이유는?

선택지 모든 실험을 없앨 수 있기 때문이다. DNA를 자동으로 단백질로 바꾸기 때문이다. 복잡한 생물학적 관계를 점과 선의 구조로 볼 수 있기 때문이다. p-value를 항상 0으로 만들기 때문이다.
24. [보통] 객관식

네트워크에서 여러 기능 단위가 따로 뭉쳐 있을 때 확인하고 싶은 것은?

선택지 파일 압축률 염기쌍 색깔 현미경 배율 군집 구조
25. [계산] 객관식

무방향 그래프에서 점이 6개일 때 가능한 최대 선 개수는?

선택지 15 12 30 6
26. [계산] 객관식

점 8개, 선 12개인 무방향 그래프의 평균 차수는?

선택지 1.5 3 12 24
27. [계산] 객관식

점 5개, 실제 선 4개인 무방향 그래프의 밀도는?

선택지 0.2 0.3 0.4 0.8
28. [계산] 객관식

선 목록이 A-B, A-C, A-D, B-C일 때 A의 차수는?

선택지 1 2 4 3
29. [계산] 객관식

방향 선이 A→B, C→B, B→D일 때 B의 들어오는 차수는?

선택지 2 1 3 0
30. [사례 판단] 객관식

두 기능 모듈을 이어 주는 다리 역할의 노드를 평가할 때 특히 관련 있는 중심성은?

선택지 GC 비율 매개중심성 표준오차 p값
31. [계산] 객관식

점 4개인 완전 무방향 그래프의 선 개수는?

선택지 4 8 6 12
32. [데이터 해석] 객관식

단백질 상호작용망에서 차수가 높은 단백질을 해석할 때 가장 적절한 태도는?

선택지 무조건 질병 원인 단백질이라고 단정한다 p값으로 바꿔야만 의미가 있다 서열 정렬 점수로만 판단한다 허브 후보로 보되 데이터 편향과 생물학적 검증을 함께 확인한다
33. [쉬움] 객관식

그래프에서 node와 edge는?

선택지 p-value와 표준편차 샘플 수 대상과 관계 항상 원인 관계
34. [쉬움] 객관식

A가 B,C,D와 연결되면 A의 degree는?

선택지 1 2 4 3
35. [보통] 객관식

인접행렬은?

선택지 노드 사이 연결을 행렬로 표현한다. 유전자를 삭제한다. p-value를 0으로 만든다. 표본수를 정한다.
36. [어려움] 객관식

hub 단백질에 대한 올바른 해석은?

선택지 항상 독성이 없다. 중요할 수 있지만 항상 안전한 약물 표적은 아니다. 원인 증명이다. 반드시 제거한다.
37. [보통] 객관식

엣지 해석에서 확인할 것은?

선택지 배경색만 파일명만 물리적 결합인지 상관인지 문헌 기반인지 글자 수만
주관식 38. [보통] 주관식 · Gemini 채점

그래프에서 점과 선이 각각 무엇을 뜻하는지 생물학 예시와 함께 설명하라.
주관식 39. [보통] 주관식 · Gemini 채점

차수가 높은 점을 생물학적으로 해석할 때 왜 조심해야 하는지 설명하라.
주관식 40. [보통] 주관식 · Gemini 채점

평균 차수와 밀도가 관계망을 이해하는 데 어떤 도움을 주는지 설명하라.
주관식 41. [보통] 주관식 · Gemini 채점

유전자 조절망을 방향그래프로 표현해야 하는 이유를 설명하라.
주관식 42. [심화] 주관식 · Gemini 채점

단백질 상호작용망에서 차수가 높은 단백질을 발견했을 때 바로 질병 원인이라고 단정하면 안 되는 이유를 설명하라.
주관식 43. [보통] 주관식 · Gemini 채점

엣지가 A-B, A-C, B-D일 때 각 노드 A,B,C,D의 degree를 구하라.
주관식 44. [보통] 주관식 · Gemini 채점

네트워크 hub를 바로 약물 표적으로 단정하면 안 되는 이유를 설명하라.