# 궤적 분석 고르기: PAGA·MST·Diffusion Pseudotime > 세포가 연속적으로 변하는 과정을 군집 연결 지도, 트리 뼈대, 세포별 순서로 요약하는 세 방법이 각각 무엇을 입력받아 무엇을 출력하고, 데이터 특성에 따라 어느 것을 골라야 하는지 비교한다. 궤적 분석은 **세포들이 끊어진 집단이 아니라 연속된 과정 위에 놓여 있을 때, 그 과정의 모양과 순서를 데이터에서 추정하는 방법**입니다. 줄기세포가 중간 단계를 거쳐 성숙 세포가 되는 분화, 자극을 받은 면역세포가 활성화되는 과정이 대표적입니다. 이 문서는 세 가지 접근을 같은 틀로 비교합니다. 셋은 답하는 질문의 **해상도**가 다릅니다. | 방법 | 답하는 질문 | 입력 | 출력 | | --- | --- | --- | --- | | PAGA | 어느 군집이 어느 군집과 이어져 있는가 | [kNN 그래프](/reference/knn-graph/) + 군집 라벨 | 군집×군집 연결 강도 행렬 | | MST (Slingshot 등) | 군집들을 잇는 분기 트리는 무엇이고 각 가지의 세포 순서는 어떤가 | 군집 중심점 좌표 + 시작 군집 | 트리 edge 목록, 가지별 세포 순서 | | Diffusion Pseudotime (DPT) | 시작 세포에서 각 세포까지 얼마나 진행했는가 | kNN 그래프 + 시작 세포 | 세포별 0~1 pseudotime | 세 방법 모두 **방향을 데이터에서 알아내지 못합니다.** 어느 쪽이 시작인지는 사람이 생물학 지식으로 지정하거나 RNA velocity 같은 별도 분석으로 정합니다. ## 세 방법이 공통으로 푸는 문제 [군집화](/reference/clustering-methods/)는 세포를 끊어진 그룹으로 나눕니다. 그러나 분화 중인 세포는 `cluster 2`와 `cluster 5` 사이의 경계에 수백 개씩 걸쳐 있고, 이 세포들을 어느 한쪽에 배정하면 "중간 단계"라는 정보가 사라집니다. 궤적 분석은 이 연속성을 세 수준으로 복원합니다. - **위상**(topology): 과정이 한 줄인가, 갈라지는가, 합쳐지는가. 군집 수준에서 답합니다. - **뼈대**(skeleton): 갈라지는 지점과 가지의 경로. 군집 중심점을 잇는 트리로 답합니다. - **순서**(pseudotime): 각 세포가 시작점에서 얼마나 떨어져 있는가. 세포 수준의 숫자로 답합니다. pseudotime은 실제 시간이 아닙니다. 한 시점에 채취한 세포들이 서로 다른 진행 단계에 있다고 가정하고, 발현 변화량을 순서로 바꾼 값입니다. ## PAGA: 군집 사이의 edge를 세어 연결 지도를 만든다 **PAGA**(partition-based graph abstraction)는 **kNN 그래프를 군집 단위로 뭉쳐, 군집 사이에 edge가 우연보다 얼마나 많은지를 연결 강도로 요약하는 방법**입니다. ### 어떤 문제를 풀 때 쓰는가 Leiden 군집이 20개 나왔을 때, 그중 어느 쌍이 실제로 세포 연속체로 이어져 있고 어느 쌍이 완전히 떨어져 있는지 알고 싶을 때 씁니다. UMAP 그림에서 두 섬이 붙어 보이는 것은 배치의 우연일 수 있지만, PAGA는 그래프에서 직접 셉니다. 또 하나의 쓰임은 **UMAP 초기 배치**입니다. UMAP을 PAGA 지도의 군집 위치에서 시작하면 전체 구조가 군집 연결을 더 잘 반영합니다. ### 입력 [kNN 그래프](/reference/knn-graph/)와 세포별 군집 번호입니다. 군집 해상도가 바뀌면 PAGA 지도도 바뀝니다. ### 어떻게 동작하는가 군집 A와 B 사이에 실제로 있는 edge 수를 세고, 두 군집의 크기와 node들의 edge 수를 고려했을 때 edge가 무작위로 이어졌다면 기대되는 수와 비교합니다. 실제 수가 기대 수보다 훨씬 많으면 연결 강도가 1에 가깝고, 비슷하거나 적으면 0에 가깝습니다. 가상 데이터로 군집 세 개를 보면 다음과 같습니다. | 군집 쌍 | 실제 edge 수 | 기대 edge 수 | 연결 강도 | | --- | ---: | ---: | ---: | | A - B | 850 | 120 | 0.92 | | B - C | 310 | 95 | 0.71 | | A - C | 12 | 110 | 0.03 | A와 B, B와 C는 이어져 있고 A와 C는 B를 거쳐야만 연결된다고 읽습니다. 위젯의 세포들은 A에서 B를 거쳐 C로 이어지고, D는 C 쪽에 놓인 세포 하나로만 가늘게 이어져 있습니다. 표의 실제 edge 수는 왼쪽 그림의 흰 선을 군집 쌍별로 센 것입니다. 기준값을 0.3까지 올리면 C - D의 약한 연결이 지도에서 사라지고, A - B - C의 연결만 남습니다. "우연으로 기대되는 수"와 비교한다는 생각은 [군집화의 modularity](/reference/clustering-methods/#어떻게-동작하는가)와 같습니다. ### 출력 군집×군집 연결 강도 행렬입니다. 그림에서는 node가 군집, node 크기가 세포 수, edge 굵기가 연결 강도입니다. 연결 강도가 기준보다 약한 edge는 숨기고 그리는 것이 보통입니다. PAGA는 **트리를 강제하지 않습니다.** 세포 주기처럼 고리 모양의 과정이면 edge가 고리를 이루고, 서로 무관한 두 세포 종류면 edge가 아예 없습니다. 이 점이 아래 MST와의 가장 큰 차이입니다. ## MST: 군집 중심점을 최소 비용 트리로 잇는다 **MST**(minimum spanning tree, 최소 신장 트리)는 **모든 node를 연결하되 edge 가중치의 합이 가장 작고 고리가 없는 트리를 찾는 고전 그래프 알고리즘**입니다. Kruskal이나 Prim 알고리즘으로 구합니다. 싱글셀에서는 **Slingshot**, TSCAN, 초기 Monocle이 군집 중심점을 잇는 궤적 뼈대로 MST를 씁니다. ### 어떤 문제를 풀 때 쓰는가 분화처럼 **한 뿌리에서 갈라져 나가는 트리 모양**이 생물학적으로 기대될 때, 가지의 경로를 명시적으로 얻고 가지마다 세포 순서를 매기고 싶을 때 씁니다. PAGA가 "A-B와 B-C가 이어져 있다"로 끝나는 반면, MST 기반 방법은 "뿌리 A에서 B를 거쳐 C로 가는 lineage 1, D로 가는 lineage 2"처럼 경로를 줍니다. ### 입력 군집마다 하나씩 계산한 **중심점 좌표**(PCA 공간에서 군집에 속한 세포의 평균)와 **시작 군집**입니다. 중심점 사이의 Euclidean 거리가 edge 가중치가 됩니다. ### 어떻게 동작하는가 가상 데이터로 군집 다섯 개의 중심점 거리를 보면 Kruskal 알고리즘은 가장 짧은 edge부터 고리를 만들지 않는 한 차례로 채택합니다. | 순서 | edge | 거리 | 채택 | | ---: | --- | ---: | --- | | 1 | A - B | 2.1 | 채택 | | 2 | B - C | 2.4 | 채택 | | 3 | B - D | 2.9 | 채택 | | 4 | C - D | 3.0 | 거부 (B를 통해 이미 연결, 고리 생성) | | 5 | D - E | 3.3 | 채택 | 군집 5개를 edge 4개로 잇는 트리가 나옵니다. 시작을 A로 지정하면 뿌리에서 잎까지의 경로가 lineage입니다: `A → B → C`와 `A → B → D → E`. Slingshot은 여기에 각 lineage를 따라 세포 구름의 가운데를 지나는 부드러운 곡선(principal curve)을 맞추고, 각 세포를 곡선 위에 투영한 위치를 pseudotime으로 씁니다. ### 출력 | 출력 | 내용 | | --- | --- | | 트리 edge 목록 | 군집 쌍 (군집 수 - 1개) | | lineage 목록 | 뿌리에서 각 잎까지의 군집 경로 | | lineage별 pseudotime | 그 lineage에 속한 세포마다 하나의 값 (여러 가지에 걸친 세포는 값이 여러 개) | 트리 뼈대는 군집 중심점 사이의 거리 행렬만 있으면 구할 수 있습니다. principal curve와 pseudotime까지 얻으려면 Slingshot 같은 전용 도구를 씁니다. MST는 **반드시 트리를 만듭니다.** 서로 무관한 두 세포 종류도 어딘가 edge로 이어지고, 고리 모양의 과정은 한 곳이 끊겨 선처럼 보입니다. 또 중심점 하나가 doublet이나 batch 때문에 조금만 움직여도 edge 선택이 바뀔 수 있어 군집 수와 품질에 민감합니다. ## Diffusion Pseudotime: 그래프 위 확산 거리로 세포마다 순서를 매긴다 **DPT**(diffusion pseudotime)는 **[Diffusion Map](/reference/dimension-reduction-methods/#diffusion-map-그래프-위를-걷는-random-walk로-좌표를-만든다)의 확산 거리를 써서 시작 세포에서 각 세포까지의 진행 정도를 계산하는 방법**입니다. ### 어떤 문제를 풀 때 쓰는가 군집 단위가 아니라 **세포 하나하나에 순서**를 붙이고 싶을 때, 그리고 과정이 한 줄이거나 분기가 한두 번뿐일 때 씁니다. pseudotime을 얻으면 "어떤 유전자가 과정의 앞쪽에서 켜지고 뒤쪽에서 꺼지는가"를 pseudotime에 대한 발현 곡선으로 볼 수 있습니다. ### 입력 kNN 그래프와 **시작 세포 하나**입니다. 시작 세포는 보통 가장 미분화된 군집에서 Diffusion Map의 한쪽 끝에 있는 세포를 고릅니다. ### 어떻게 동작하는가 kNN 그래프의 edge 가중치를 "한 걸음에 이웃으로 갈 확률"로 바꾼 전이 행렬 위에서, 두 세포가 random walk로 서로 얼마나 쉽게 도달하는지를 **확산 거리**로 정의합니다. 수많은 경로를 평균하는 거리라서 edge 하나의 잡음에 둔감합니다. 시작 세포에서 각 세포까지의 확산 거리를 0~1로 정규화한 값이 pseudotime입니다. 줄기의 왼쪽 끝을 시작 세포로 고르면 색이 줄기를 따라 밝아지다가 두 가지로 나뉘어 올라갑니다. 가지 끝을 시작 세포로 고르면 순서가 뒤집혀, 방향은 사람이 정해야 한다는 것을 볼 수 있습니다. 줄기에서 시작했을 때 두 가지 끝의 값이 거의 같다는 점도 눈여겨보세요. pseudotime 숫자만으로는 세포가 어느 가지에 있는지 알 수 없습니다. ### 출력 세포마다 pseudotime 값이 하나씩 붙은 열입니다. 시작 세포가 0, 가장 먼 세포가 1입니다. 시작 세포와 그래프로 연결되지 않은 세포는 값을 정할 수 없어 무한대를 받습니다. DPT는 **분기를 명시적으로 알려 주지 않습니다.** 갈라진 두 가지의 세포가 비슷한 pseudotime 값을 받을 수 있으므로, 분기 구조는 PAGA나 Diffusion Map 그림으로 먼저 확인하고 가지별로 따로 계산하는 편이 안전합니다. ## 데이터 특성에 따라 고르기 | 데이터·질문의 특성 | 맞는 방법 | 이유 | | --- | --- | --- | | 군집 20개 중 어느 것이 이어졌는지만 알고 싶음 | PAGA | 군집 수준 연결 강도를 직접 계산 | | 서로 무관한 세포 종류가 섞여 있음 | PAGA | 연결이 없으면 edge를 두지 않음, MST는 강제로 이음 | | 세포 주기처럼 고리 모양 과정 | PAGA | 트리를 강제하지 않음 | | 한 뿌리에서 갈라지는 분화 트리가 기대됨 | MST (Slingshot) | lineage 경로와 가지별 pseudotime을 명시적으로 줌 | | 가지마다 유전자 발현 곡선을 비교하고 싶음 | MST (Slingshot) 또는 PAGA + DPT 조합 | lineage별 pseudotime이 필요 | | 한 줄짜리 연속 과정, 세포별 순서가 필요 | DPT | 잡음에 둔감한 세포 단위 순서 | | 세포 수십만 개 | PAGA, DPT | 군집 수준 또는 희소 그래프 연산, Slingshot은 느려짐 | | 군집 품질이 불확실함 | PAGA | 연결 강도라는 수치로 불확실성을 남김, MST는 edge를 단정 | | UMAP의 전체 배치를 믿을 만하게 만들고 싶음 | PAGA | 군집 연결을 반영한 초기 배치 | 실무에서는 **PAGA로 위상을 확인하고, 분화 트리가 보이면 그 세포들만 떼어 DPT나 Slingshot으로 pseudotime을 계산**하는 순서가 흔합니다. ## 흔한 함정 - **방향이 있다고 믿는다.** 세 방법 모두 무방향입니다. 시작 군집을 바꾸면 pseudotime이 뒤집힙니다. 시작점은 알려진 marker(줄기세포 marker 등)나 RNA velocity로 정합니다. - **끊어진 세포 종류에 pseudotime을 매긴다.** T세포와 상피세포 사이에는 과정이 없습니다. 궤적은 생물학적으로 연속이 기대되는 세포 집단에만 적용하고, 그 집단만 따로 떼어 그래프를 다시 만듭니다. - **UMAP에서 보이는 다리를 궤적으로 읽는다.** doublet이나 batch 때문에 생긴 가느다란 연결이 궤적처럼 보일 수 있습니다. PAGA 연결 강도와 QC 지표로 확인합니다. - **군집 해상도를 바꾸지 않고 한 번만 본다.** PAGA와 MST는 군집이 입력입니다. resolution을 바꿔도 유지되는 연결만 믿습니다. - **pseudotime을 시간 단위로 해석한다.** 0.3과 0.6의 차이가 "두 배 오래 걸렸다"는 뜻이 아닙니다. 순서만 의미가 있습니다. - **batch가 궤적을 만든다.** donor A의 세포가 모두 앞쪽, donor B가 모두 뒤쪽이면 분화가 아니라 batch입니다. pseudotime을 sample로 색칠해 확인합니다. ### 공식 자료 - [PAGA 논문: Wolf et al., *Genome Biology* (2019)](https://genomebiology.biomedcentral.com/articles/10.1186/s13059-019-1663-x) - [Scanpy `sc.tl.paga` API](https://scanpy.readthedocs.io/en/stable/api/generated/scanpy.tl.paga.html) - [Slingshot 논문: Street et al., *BMC Genomics* (2018)](https://bmcgenomics.biomedcentral.com/articles/10.1186/s12864-018-4772-0) - [Slingshot Bioconductor 문서](https://bioconductor.org/packages/release/bioc/html/slingshot.html) - [Diffusion pseudotime 논문: Haghverdi et al., *Nature Methods* (2016)](https://www.nature.com/articles/nmeth.3971) - [Scanpy `sc.tl.dpt` API](https://scanpy.readthedocs.io/en/stable/api/generated/scanpy.tl.dpt.html) - [궤적 분석 방법 비교: Saelens et al., *Nature Biotechnology* (2019)](https://www.nature.com/articles/s41587-019-0071-9)