GraphHDBSCAN*: Graph-based Hierarchical Clustering on High Dimensional Single-cell RNA Sequencing Data

이 논문은 고차원 단일 세포 RNA 시퀀싱 데이터에서 생물학적으로 의미 있는 계층적 구조와 평면 분할을 모두 효과적으로 복원하는 그래프 기반 계층적 군집화 알고리즘인 GraphHDBSCAN*을 제안하고 그 유효성을 검증합니다.

핵심

1. 배경: 거대한 '세포 도시'와 혼란스러운 지도

상상해 보세요. 우리 몸에는 수백만 개의 세포가 있습니다. 각 세포는 고유한 역할을 하는 '시민'입니다. 최근 기술 덕분에 우리는 이 수백만 명의 시민 한 명 한 명을 모두 조사할 수 있게 되었습니다. 이를 **'단일 세포 RNA 시퀀싱'**이라고 합니다.

하지만 문제는 데이터가 너무 방대하고 복잡하다는 것입니다. 마치 수백만 명의 시민이 모여 있는 거대한 도시를 한 번에 보는데, 지도가 너무 복잡해서 누가 누구의 가족인지, 어떤 직업군에 속하는지 구별하기 힘든 상황입니다.

• 기존의 문제점:
  • 평면적인 분류 (Louvain, Leiden 등): 기존 프로그램들은 이 도시를 단순히 "A 구역, B 구역"으로 나눕니다. 하지만 세포는 단순하지 않습니다. '혈액 세포'라는 큰 가족 안에 '단핵구', 'T 세포'라는 하위 가족이 있고, 다시 그 안에도 더 작은 하위 집단이 있습니다. 기존 프로그램은 이 **가계도 (계층 구조)**를 무시하고 그냥 평평하게 나눕니다.
  • 잡음 (Noise) 처리: 데이터에는 오류나 이상한 세포들이 섞여 있습니다. 기존 프로그램들은 이들을 그냥 **'쓰레기통 (Noise)'**으로 버려버립니다. 하지만 그 쓰레기통 속에 진짜 중요한 희귀 세포가 숨어 있을 수도 있습니다.

2. 해결책: GraphHDBSCAN* (그래프 기반 계층적 클러스터링)

이 논문이 제안한 GraphHDBSCAN*은 이 문제를 해결하기 위해 등장한 **'스마트한 도시 계획가'**입니다.

비유 1: "친구 관계도"로 도시를 재구성하다 (그래프 기반)

기존 방법들은 세포 간의 거리를 계산할 때, 모든 세포를 3 차원 공간에 뿌려놓고 거리를 재는 방식 (직접적인 거리 측정) 을 썼습니다. 하지만 세포 데이터는 너무 많고 복잡해서 (고차원), 이 방식은 거리가 왜곡되어 정확한 관계를 파악하지 못했습니다.

GraphHDBSCAN*은 대신 **'친구 관계도 (그래프)'**를 먼저 그립니다.

• "누가 누구와 가장 친한 친구인가?"를 먼저 파악합니다.
• 그리고 그 친구 관계의 강도 (가중치) 를 이용해 세포들을 그룹화합니다.
• 효과: 복잡한 3 차원 공간 대신, 친밀도라는 명확한 기준을 통해 세포들의 진짜 관계를 찾아냅니다.

비유 2: "나무 가지"처럼 성장하는 계층 구조 (Hierarchical)

기존 프로그램은 "이 도시를 5 개의 구로 나누자"라고 정해놓고 딱 잘라냅니다. 하지만 GraphHDBSCAN*은 나무처럼 자랍니다.

• 뿌리: 모든 세포가 하나로 합쳐진 상태.
• 가지: 세포들이 조금씩 분리되기 시작합니다. (예: "혈액 세포" vs "신경 세포")
• 잎사귀: 더 세분화됩니다. (예: "단핵구" vs "T 세포" vs "B 세포")
• 장점: 연구자는 이 나무 구조를 보고, "어, 이 가지가 더 잘게 나뉘는군!" 하며 원하는 수준의 세분화를 직접 선택할 수 있습니다. 마치 나무를 위에서 아래로 내려다보며 원하는 가지만 잘라내는 것과 같습니다.

비유 3: 버려진 '쓰레기통'을 다시 살리다 (Label Propagation)

기존 프로그램이 "이 세포는 이상하니까 쓰레기통에 버려라"라고 한 세포들이 있습니다. GraphHDBSCAN*은 이렇게 말합니다.

"잠깐! 이 세포가 쓰레기일 수도 있지만, 혹시 이웃한 세포들과 너무 비슷해서 분류가 안 된 건 아닐까?"

이 프로그램은 **라벨 전파 (Label Propagation)**라는 기술을 사용합니다.

• "이웃한 세포들이 모두 'T 세포'인데, 이 세포만 '쓰레기'라면, 아마 이 세포도 'T 세포'일 확률이 높아. 다시 T 세포로 분류해 줄게."
• 효과: 버려지던 중요한 세포들을 다시 찾아내고, 그 세포가 어떤 그룹에 속하는지 정확하게 알려줍니다.

3. 이 프로그램이 가져온 변화 (결과)

이 프로그램을 실행해 보니 놀라운 일이 일어났습니다.

1. 숨겨진 가족 찾기: 기존에는 발견하지 못했던 단핵구의 새로운 하위 유형을 찾아냈습니다. 마치 "오래된 가계도에서 알던 친척 외에, 전혀 몰랐던 사촌이 있었다"는 것을 발견한 것과 같습니다.
2. 더 정확한 분류: 기존에 널리 쓰이던 프로그램 (Louvain, Leiden) 보다 세포들을 더 정확하게 그룹화했습니다.
3. 유연한 분석: 연구자가 "너무 세분화하지 말고 큰 그룹만 보여줘"라고 하거나, "정말 자세히 봐줘"라고 하더라도, 한 번의 분석으로 모든 계층 구조를 보여줍니다.

4. 요약: 왜 이것이 중요한가요?

GraphHDBSCAN*은 단순히 세포를 묶는 것을 넘어, 세포들의 복잡한 가족 관계 (계층 구조) 를 이해하고, 버려지던 중요한 세포들을 다시 구출해 주는 혁신적인 도구입니다.

• 기존: "이것은 A 그룹, 저것은 B 그룹이야. 나머지는 쓰레기야." (단순하고 평면적)
• GraphHDBSCAN:* "이것은 A 그룹의 큰 가족이고, 그 안에 B, C, D라는 작은 가족들이 있어. 그리고 저 쓰레기통에 있던 녀석도 사실은 B 가족의 일원이었어!" (정교하고 계층적)

이 기술은 암 연구, 면역학 연구 등 복잡한 질병의 원인을 세포 수준에서 파악하는 데 큰 도움을 줄 것으로 기대됩니다. 마치 혼란스러운 도시 지도를 정리하여, 시민들의 진짜 관계와 역할을 명확하게 보여주는 나침반과 같은 역할을 하는 것입니다.

기술 요약

1. 문제 정의 (Problem)

단일 세포 RNA 시퀀싱 (scRNA-seq) 기술은 수천에서 수백만 개의 세포에 대한 유전자 발현을 분석하여 세포 이질성을 규명하는 데 혁신을 가져왔습니다. 그러나 이러한 고차원적이고 희소하며 노이즈가 많은 데이터를 클러스터링할 때 다음과 같은 주요 도전 과제가 존재합니다.

• 계층적 구조의 무시: 기존 상태의 최첨단 (SOTA) 방법들 (Louvain, Leiden 등) 은 주로 평면적인 (flat) 분할에 초점을 맞추고 있어, 세포 유형이 더 구체적인 아형으로 분화되는 자연스러운 계층적 구조 (hierarchical organization) 를 포착하지 못합니다.
• 고차원 데이터의 한계: 기존 밀도 기반 계층적 클러스터링 알고리즘 (HDBSCAN*) 은 거리 기반 유사성에 의존하는데, 고차원 공간에서는 '차원의 저주'로 인해 거리가 덜 유용해져 클러스터 형성의 견고성이 떨어지고 많은 세포가 노이즈로 잘못 분류되는 문제가 발생합니다.
• 하이퍼파라미터 민감성: Louvain 및 Leiden 알고리즘은 해상도 (resolution) 파라미터와 같은 하이퍼파라미터에 민감하며, 확률적 성격을 띠어 결과가 불안정할 수 있습니다.
• 노이즈 처리의 한계: 기존 방법은 노이즈로 분류된 세포를 단순히 제거하거나 무시하는 경향이 있어, 희귀한 세포 유형이나 과도기적 상태를 놓칠 수 있습니다.

2. 방법론 (Methodology)

저자들은 GraphHDBSCAN* 을 제안했습니다. 이는 그래프 기반 밀도 계층적 클러스터링을 수행하며, 고차원 scRNA-seq 데이터에 최적화된 HDBSCAN* 의 확장 버전입니다.

핵심 구성 요소:

1. 가중 구조 유사성 (Weighted Structural Similarity, WSS) 그래프 구축:

   • 원시 데이터 (유전자 발현 행렬) 에서 직접 $k$-NN 그래프를 구축합니다.
   • 기존 공유 최근접 이웃 (SNN) 개념을 확장하여, 노드 간의 연결 강도를 나타내는 가중치를 포함하는 WSS 그래프를 생성합니다.
   • 이를 통해 PCA, t-SNE, UMAP 과 같은 차원 축소 단계를 거치지 않고도 고차원 데이터에서 안정적인 클러스터링이 가능해집니다.

2. CORE-SG (Core-based Spanning Graph) 활용:

   • 다양한 밀도 설정 ($minPts$ 값) 에 대한 계층 구조를 효율적으로 탐색하기 위해 CORE-SG 기술을 사용합니다.
   • 이 방법은 하나의 초기 실행 ($k_{max}$) 으로 여러 $minPts$ 값에 대한 최소 신장 트리 (MST) 를 유도할 수 있게 하여, 계산 비용을 크게 줄이고 실제 사용 시 하이퍼파라미터가 필요 없는 (hyperparameter-free) 알고리즘으로 만듭니다.

3. 계층적 클러스터링 및 평면 분할 추출:

   • WSS 그래프를 기반으로 HDBSCAN* 프레임워크를 적용하여 밀도 기반 계층 구조 (Condensed Tree) 를 생성합니다.
   • FOSC (Framework for Optimal Selection of Clusters) 와 EOM (Excess of Mass) 기준을 사용하여 계층 구조에서 가장 안정적이고 의미 있는 평면 분할 (flat partition) 을 자동으로 추출합니다.

4. 레이블 전파 (Label Propagation) 를 통한 노이즈 처리:

   • HDBSCAN* 은 기본적으로 노이즈로 분류된 점들을 식별합니다. scRNA-seq 데이터에서는 이러한 점들이 기술적 오류일 수도 있지만, 희귀 세포일 수도 있으므로 완전히 제거하기보다는 재할당하는 것이 유용합니다.
   • 저자들은 HDBSCAN(cd,–)* 기반의 반지도 학습 (semi-supervised) 레이블 전파 전략을 도입하여, 노이즈로 분류된 세포들을 밀도 연결성을 기반으로 가장 적합한 클러스터에 재할당합니다. 이 과정은 MST 를 활용하므로 추가적인 계산 복잡도를 크게 증가시키지 않습니다.

3. 주요 기여 (Key Contributions)

• 새로운 알고리즘 제안: 고차원 단일 세포 데이터에 특화된 그래프 기반 계층적 클러스터링 알고리즘인 GraphHDBSCAN* 을 최초로 제안했습니다.
• 계층적 구조의 복원: 기존 평면 분할 방법들이 놓치던 세포 유형 간의 계층적 관계 (예: 단핵구 $\rightarrow$ 비정형/중간/전형적 단핵구) 를 자동으로 발견하고 시각화할 수 있습니다.
• 노이즈의 의미 있는 활용: 노이즈로 간주된 세포들을 단순히 버리는 것이 아니라, 밀도 기반 원리를 적용하여 적절한 세포 유형으로 재할당함으로써 데이터의 완전성을 높였습니다.
• 차원 축소 불필요: 고차원 데이터의 거리 문제를 해결하기 위해 PCA 등 차원 축소를 거치지 않고, 그래프 구조와 WSS 변환을 통해 직접 클러스터링을 수행합니다.

4. 실험 결과 (Results)

저자들은 여러 scRNA-seq 데이터셋 (PBMC, Zheng, CITE-seq 등) 을 사용하여 GraphHDBSCAN* 을 평가했습니다.

• 생물학적 통찰력 확보:
  • 단핵구 (Monocyte) 하위 집단 발견: CITE-seq 데이터에서 기존 연구에서는 설명되지 않았던 두 가지 단핵구 하위 집단 (Leaf Node 3, 4) 을 발견했습니다. CD36, CD11c 마커를 통해 이를 생물학적으로 검증했습니다.
  • Zheng 데이터셋: 자연살해세포 (NK) 와 T 세포, B 세포, 조혈모세포 간의 계층적 분리를 정확히 재현했으며, 이전에 기술되지 않은 CD34+ 세포의 두 가지 하위 집단을 발견했습니다.
• 성능 벤치마킹:
  • 평면 분할 성능: 조정 랜덤 지수 (ARI) 와 조정 상호 정보 (AMI) 기준으로 Louvain, Leiden, 기존 HDBSCAN* 과 비교했습니다.
  • GraphHDBSCAN* 은 기본 설정 (Default) 과 최적 하이퍼파라미터 (Best) 설정 모두에서 Louvain 및 Leiden 보다 일관되게 우수한 또는 동등한 성능을 보였습니다. 특히 기존 HDBSCAN* 보다 훨씬 높은 성능을 기록하여 고차원 데이터에서의 거리 기반 한계를 극복했음을 입증했습니다.
  • 다양한 데이터셋에서 안정적이고 낮은 변동성을 보였습니다.
• 계산 효율성:
  • 데이터 크기가 증가함에 따라 매끄럽고 예측 가능한 확장성 (scaling) 을 보였습니다. 계층 구조를 생성하는 추가 비용이 있더라도 Louvain/Leiden 과 비교해 계산 오버헤드가 크지 않으며, 실용적인 수준입니다.

5. 의의 및 결론 (Significance)

GraphHDBSCAN* 은 단일 세포 분석 분야에서 다음과 같은 중요한 의의를 가집니다:

1. 생물학적 계층 구조의 자동 발견: 연구자가 사전에 지시하지 않아도 데이터의 밀도 기반 계층 구조를 자동으로 발견하여, 세포 분화 경로와 하위 집단 간의 관계를 직관적으로 이해할 수 있게 합니다.
2. 하이퍼파라미터 의존성 감소: CORE-SG 를 통해 다양한 밀도 스케일을 한 번의 실행으로 탐색할 수 있어, 사용자가 복잡한 파라미터 튜닝에 시간을 낭비하지 않아도 됩니다.
3. 데이터의 완전성 유지: 노이즈로 분류된 세포들을 재할당함으로써, 희귀 세포나 과도기적 상태를 놓치지 않고 전체 데이터셋을 포괄적으로 분석할 수 있는 프레임워크를 제공합니다.
4. 차원 축소 불필요: 고차원 데이터의 본질적인 구조를 보존하면서 클러스터링을 수행하므로, 차원 축소 과정에서 발생할 수 있는 정보 손실이나 인위적 구조 왜곡을 방지합니다.

결론적으로, GraphHDBSCAN* 은 고차원 단일 세포 데이터의 복잡한 이질성과 계층적 관계를 해결하기 위한 강력하고 견고한 도구로, 기존 커뮤니티 탐지 방법들의 한계를 극복하고 생물학적 통찰력을 극대화할 수 있는 새로운 표준이 될 가능성이 높습니다.