POTTR: Identifying Recurrent Trajectories in Evolutionary and Developmental Processes using Posets

이 논문은 종양 계통수 내의 불확실성을 고려하여 부분 순서 집합 (poset) 프레임워크를 기반으로 재발성 돌연변이 궤적을 식별하는 NP-난제 문제를 해결하는 새로운 알고리즘 'POTTR'을 제안하고, 이를 다양한 암 및 발생 생물학 데이터에 적용하여 통계적으로 유의미한 새로운 궤적과 분화 경로를 발견했습니다.

핵심

🕵️‍♂️ 1. 문제 상황: "혼란스러운 사건 기록들"

생각해 보세요. 암이 생기거나 배아가 자라는 과정은 마치 거대한 사건 기록과 같습니다.

• 환자 A의 암은: 유전자 X 가 먼저 변하고, 그다음 Y, 그다음 Z 순서로 변했습니다.
• 환자 B의 암은: Y 가 먼저 변하고, 그다음 X, Z 순서로 변했습니다.
• 환자 C의 암은: X 와 Y 가 동시에 변한 것 같고, 그다음 Z 가 변했습니다.

여기서 문제는 두 가지입니다.

1. 순서가 불분명함: 어떤 환자는 두 사건이 동시에 일어났는지, 아니면 순서가 뭘지 정확히 알 수 없습니다 (이를 **'클러스터'**라고 부릅니다).
2. 기록이 여러 개임: 같은 환자라도 분석 방법에 따라 서로 다른 순서 기록 (나무 모양의 도표) 이 여러 개 나올 수 있습니다.

기존의 방법들은 이 복잡한 기록들을 정리할 때, "순서가 불분명하면 그냥 무시해 버리거나" 혹은 "하나의 정답만 고집해서" 중요한 패턴을 놓치는 경우가 많았습니다.

🧩 2. POTTR 의 해결책: "완벽하지 않은 퍼즐 맞추기"

저자들은 이 문제를 해결하기 위해 POTTR이라는 새로운 방법을 개발했습니다. 이걸 세 가지 비유로 설명해 볼게요.

비유 1: "불완전한 지도 (Poset)"

기존 방법들은 모든 지점이 명확하게 연결된 '완벽한 지도'만 다뤘습니다. 하지만 실제 데이터는 지점 사이의 연결선이 끊기거나, "A 와 B 중 누가 먼저인지 모르겠다"는 표시가 있는 불완전한 지도들입니다.
POTTR 은 이 불완전한 지도들을 그대로 받아들입니다. "어디가 연결되었는지 모르겠다"는 부분도 무시하지 않고, "아마도 이런 순서일 수도 있겠다"는 가능성을 열어두고 분석합니다.

비유 2: "갈등 없는 팀 만들기 (Conflict Graph)"

여러 환자의 기록을 비교할 때, "A 가 B 보다 먼저"라고 말하는 기록과 "B 가 A 보다 먼저"라고 말하는 기록이 충돌할 수 있습니다.
POTTR 은 이 충돌들을 **갈등 그래프 (Conflict Graph)**라는 그물망으로 표현합니다.

• 갈등이 있는 두 사건은 그물망으로 묶여 서로 만날 수 없습니다.
• 갈등이 없는 사건들은 그물망에서 자유롭게 연결될 수 있습니다.

이제 POTTR 은 이 그물망에서 **가장 많은 사건들을 포함하면서도 서로 충돌하지 않는 그룹 (독립 집합)**을 찾습니다. 마치 가장 많은 친구들을 초대하되, 서로 싸우는 친구들은 함께 부르지 않는 파티를 기획하는 것과 같습니다.

비유 3: "모호한 조각을 맞춰서 완성하기"

가장 중요한 점은 POTTR 이 **모호한 부분 (클러스터)**을 해결한다는 것입니다.

• 기존 방법: "A 와 B 가 동시에 변했다? 알 수 없으니 이 둘을 하나로 묶어서 분석하자." → 순서 정보가 사라짐.
• POTTR 방법: "A 와 B 가 동시에 변한 것처럼 보이지만, 다른 환자 기록을 보면 A 가 B 보다 먼저일 수도 있겠다. 그럼 이 모호한 부분을 **해결 (Resolution)**해서 A → B 순서로 만들어 보자."
  이렇게 모호한 조각을 다른 기록들의 힌트를 통해 맞춰주면, 훨씬 더 명확하고 의미 있는 **반복되는 패턴 (Recurrent Trajectory)**이 드러납니다.

---

🏥 3. 실제 성과: "숨겨진 진실을 찾아내다"

저자들은 이 POTTR 을 실제 데이터에 적용했습니다.

1. 폐암 (NSCLC) 데이터:

   • 기존 방법으로는 발견하지 못했던 새로운 암 진화 경로를 찾아냈습니다.
   • 예를 들어, 특정 유전자들이 무작정 동시에 변한 것처럼 보였는데, POTTR 로 분석하니 어떤 유전자가 먼저 변하고 그다음 다른 유전자가 변하는지 순서를 밝혀냈습니다. 이는 약물에 대한 반응이나 환자의 생존율과 깊은 연관이 있습니다.

2. 백혈병 (AML) 데이터:

   • 기존 방법보다 훨씬 더 많은 통계적으로 의미 있는 패턴을 찾아냈습니다. 기존 방법은 잡음 (noise) 에 가려진 진짜 패턴을 놓쳤는데, POTTR 은 이를 걸러냈습니다.

3. 배아 발달 (TLS) 데이터:

   • 실험실에서 배아를 키우는 과정에서, 화학 물질을 넣었을 때 세포가 어떻게 다른 길로 갈라지는지 추적했습니다.
   • 정상적인 상황에서는 세포가 A 길로 가는데, 약물을 넣으니 B 길로 가는 새로운 발달 경로를 찾아냈습니다. 이는 마치 길거리 지도에서 새로운 우회로를 발견한 것과 같습니다.

---

💡 4. 요약: 왜 이 연구가 중요한가?

• 불완전한 데이터도 잘 다룸: 암이나 발달 과정은 복잡하고 불완전한 데이터가 많습니다. POTTR 은 이 불완전함을 인정하고, 오히려 그 불완전함을 해결하며 진실을 찾아냅니다.
• 새로운 발견: 기존에 "알 수 없다"고 치부했던 부분에서, 의미 있는 규칙을 찾아냅니다.
• 유연함: 단순히 나무 (Tree) 모양의 데이터뿐만 아니라, 더 복잡한 방향성 그래프 (DAG) 형태의 데이터도 분석할 수 있어 다양한 생물학적 문제에 적용 가능합니다.

한 줄 요약:

POTTR 은 "혼란스럽고 불완전한 생물학적 기록들" 속에서, 서로 충돌하지 않는 가장 큰 '반복되는 사건 순서'를 찾아내는 똑똑한 탐정입니다.

기술 요약

1. 문제 정의 (Problem Definition)

• 배경: 암 진화나 생물체 발달과 같은 많은 생물학적 과정은 시간적 순서를 가진 유전적 사건 (돌연변이 등) 의 연속으로 설명됩니다. 각 환자나 개체마다 진화 경로는 독립적이지만, 특정 돌연변이들의 순서가 여러 개체에서 반복적으로 관찰되는 '재발성 궤적 (Recurrent Trajectories)'이 존재하며, 이는 질병의 형태, 약물 반응, 치료 결과와 밀접한 연관이 있습니다.

• 주요 난제:

  1. 이질성 (Heterogeneity): 종양 내 (Intra-tumor) 및 종양 간 (Inter-tumor) 이질성이 매우 높습니다.
  2. 불확실성 (Uncertainty): 시퀀싱 깊이 부족이나 세포 샘플링의 한계로 인해 특정 환자 내에서 돌연변이들의 상대적 순서가 명확하지 않아 '돌연변이 클러스터 (Mutation Clusters)'로 묶여 표현되는 경우가 많습니다.
  3. 다중 트리 (Multiple Trees): 하나의 환자로부터 추론된 계통수 (Phylogenetic trees) 가 여러 개일 수 있으며, 기존 방법들은 이를 효과적으로 통합하지 못합니다.
  4. 기존 방법의 한계: 기존 알고리즘들은 대부분 계통수 (Tree) 에만 국한되거나, 클러스터 해결에 한계가 있으며, 모든 가능한 트리를 나열하는 방식은 대규모 데이터에 비효율적입니다.

• 목표: 여러 입력 계통수 (또는 부분 순서 집합) 에서 공통으로 관찰되는 가장 큰 재발성 사건 순서 (궤적) 를 식별하는 문제.

2. 방법론 (Methodology)

저자들은 문제를 해결하기 위해 불완전 부분 순서 집합 (Incomplete Posets) 프레임워크와 POTTR 알고리즘을 제안했습니다.

가. 불완전 부분 순서 집합 (Incomplete Posets) 모델링

• 개념: 기존 계통수 (Tree) 를 일반화하여 **부분 순서 집합 (Poset, Partially Ordered Set)**으로 표현합니다.
• 불완전성 (Incomplete): 특정 돌연변이들의 순서가 불확실한 경우 (클러스터), 이를 '숨겨진 순서 (Hidden Order, $\sim$)'로 정의합니다. 이는 요소들이 동등하게 묶여 순서가 미해결 상태임을 의미합니다.
• 해결 (Resolution): 불완전 Poset 에서 숨겨진 순서를 해결하여 (클러스터를 분해하여) 완전한 Poset 으로 만드는 과정을 포함합니다.

나. 최대 k-공통 유도 불완전 부분 순서 집합 문제 (MkCIIS)

• 정의: $n$개의 불완전 Poset 집합이 주어졌을 때, 적어도 $k$개의 입력 Poset (또는 그 해결 버전) 에서 공통으로 유도되는 (Induced) 가장 큰 부분 Poset 을 찾는 문제입니다.
• 복잡도: 이 문제는 NP-hard임을 증명했습니다.

다. POTTR 알고리즘 (Combinatorial Algorithm)

• 충돌 그래프 (Conflict Graph) 구축:
  • 입력된 모든 불완전 Poset 쌍 간의 충돌 (순서 모순, 비교 불가능성 등) 을 노드와 간선으로 표현하는 다중 그래프를 생성합니다.
  • 핵심 아이디어: 공통 유도 불완전 부분 Poset (CIIS) 은 충돌 그래프에서의 **독립 집합 (Independent Set)**과 일대일 대응됩니다.
• 정수 선형 계획법 (ILP) 활용:
  • 최대 독립 집합 (MIS) 문제를 ILP 로 변환하여 해결합니다.
  • 동시 선택: $k$개 이상의 입력 Poset 을 선택하고, 해당 선택된 Poset 들 간의 충돌이 없는 최대 크기의 노드 집합 (궤적) 을 찾습니다.
  • 클러스터 해결: 충돌 그래프에서 숨겨진 순서 (클러스터) 가 다른 Poset 에서 명확한 순서로 관찰되면, 이를 해결하여 궤적에 포함시킵니다.

3. 주요 기여 (Key Contributions)

1. 새로운 수학적 프레임워크: 계통수 기반의 재발성 궤적 탐지 문제를 **불완전 부분 순서 집합 (Incomplete Posets)**으로 공식화하여, 계통수뿐만 아니라 일반적인 DAG(방향성 비순환 그래프) 형태의 발달 과정에도 적용 가능하게 확장했습니다.
2. 불확실성 처리: 돌연변이 클러스터와 다중 계통수 추론 불확실성을 명시적으로 모델링하고, 이를 재발성 궤적 탐색 과정에서 자동으로 해결 (Resolve) 하는 방법을 제시했습니다.
3. NP-hard 문제 해결 알고리즘: 충돌 그래프와 ILP 를 결합한 POTTR 알고리즘을 개발하여, 기존 휴리스틱 방법보다 정확하고 엄밀하게 최대 재발성 궤적을 찾습니다.
4. 범용성: 암 진화 (종양 계통수) 와 생물체 발달 (세포 계보 추적) 두 가지 다른 생물학적 맥락 모두에 적용 가능함을 입증했습니다.

4. 실험 결과 (Results)

저자들은 POTTR 을 세 가지 데이터셋에 적용하여 성능을 검증했습니다.

• 비교 분석 (NSCLC 및 AML 데이터):

  • 기존 방법인 MASTRO와 비교했습니다.
  • NSCLC (비소세포폐암): POTTR 은 MASTRO 가 놓친 2 개의 통계적으로 유의미한 재발성 궤적을 발견했습니다. 이는 COL5A2 및 NFE2L2 유전자의 클러스터 순서를 해결함으로써 가능했습니다. 예를 들어, $PIK3CA$증폭 후$COL5A2$돌연변이가 발생하거나,$NFE2L2$가 다른 3 개 유전자 ($PIK3CA, TP53, SOX2$) 이후에 발생한다는 순서를 규명했습니다.
  • AML (급성 골수성 백혈병): 34 개의 최대 재발성 궤적 중 33 개가 통계적으로 유의미 ($p < 0.05$) 였으며, MASTRO 가 보고한 많은 궤적은 통계적 유의성이 없었습니다.

• TRACERx 데이터 (대규모 NSCLC 코호트):

  • 401 명의 환자 (469 개의 계통수) 에 적용했습니다.
  • POTTR 은 클러스터 해결을 통해 $TP53, CDKN2A, PIK3CA$등의 돌연변이 순서를 규명했습니다. 특히$TP53$과$PIK3CA$의 순서가 질병 무진행 생존 기간과 관련된다는 기존 연구 결과를 지지하고 확장했습니다.
  • MASTRO 는 같은 환자 내의 여러 계통수를 선택할 수 없어 비교 대상에서 제외되었습니다.

• 발생 생물학 (TLS 모델):

  • 생쥐 배아 모델 (Trunk-Like Structures) 의 세포 계보 추적 데이터를 분석했습니다.
  • 화학적 자극 (WNT 활성화, BMP 억제) 전후의 분화 경로를 비교했습니다.
  • 결과: 정상 조건에서는 척추 (Somite) 가 내피 세포 (Endothelial) 와 공통 조상에서 분화되는 대체 경로가 존재했으나, 화학적 자극 하에서는 이 경로가 억제되고 신경 - 중배엽 전구체에서 척추가 분화되는 고전적 경로로만 유지됨을 발견했습니다. 이는 기존 트리 기반 방법으로는 분석 불가능한 DAG 형태의 데이터에서 POTTR 의 우수성을 보여줍니다.

5. 의의 및 결론 (Significance)

• 정밀한 진화 경로 규명: 돌연변이 클러스터와 계통수 추론의 불확실성을 해결함으로써, 기존에 발견되지 않았거나 모호했던 중요한 생물학적 순서 (예: 약물 내성 메커니즘, 발달 경로) 를 통계적으로 유의미하게 규명할 수 있습니다.
• 확장성: 트리 구조에 국한되지 않고 일반적인 부분 순서 (DAG) 를 처리할 수 있어, 복잡한 세포 분화 네트워크 분석에 필수적인 도구가 됩니다.
• 한계 및 향후 과제: 현재 데이터셋에서 클러스터 해결을 지지하는 샘플 수가 적고, NP-hard 문제 특성상 대규모 데이터에 대한 휴리스틱 개선이 필요하며, 무한 사이트 가정 (Infinite Sites Assumption) 을 완화하는 등의 추가 연구가 필요합니다.

요약하자면, POTTR 은 불완전성과 불확실성이 내재된 생물학적 진화 및 발달 데이터에서 재발성 패턴을 찾아내기 위한 강력한 계산 생물학적 도구로, 부분 순서 이론과 조합 최적화를 결합하여 기존 방법들의 한계를 극복했습니다.