💻 bioinformatics

Quantifying the Rearrangement Complexity of Pangenomes

이 논문은 복잡한 팬게놈 데이터에 적용될 때 발생하는 기존 재배열 모델의 이론적 및 실질적 한계를 극복함으로써 비교 유전체학과 팬게노믹스 사이의 간극을 메우기 위한 범-조상 재구성(Complete Ancestral Reconstruction for Pangenomes, CARP) 문제를 소개한다.

원저자: Bohnenkaemper, L., Stoye, J.

게시일 2026-09-22

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Bohnenkaemper, L., Stoye, J.

원본 논문은 CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ⚕️ 이것은 동료 심사를 거치지 않은 프리프린트의 AI 생성 설명입니다. 의학적 조언이 아닙니다. 이 내용을 바탕으로 건강 관련 결정을 내리지 마세요. 전체 면책 조항 읽기

생명은 네 글자의 코드로 쓰여 있지만, 종이 어떻게 변화하는지에 대한 이야기는 종종 그 네 글자가 어떻게 뒤섞이고, 잘리고, 다시 붙여지는지에 의해 설명되곤 합니다. 수십 년 동안 과학자들은 이러한 뒤섞임(shuffle)을 두 가지 다른 방식으로 연구해 왔습니다. 한 그룹은 생명의 거대한 역사를 들여다보며, 마치 새로운 가지가 돋아나는 가계도처럼 한 종이 수백만 년에 걸쳐 두 종으로 갈라지는 과정을 추적합니다. 또 다른 그룹은 훨씬 더 가까이서, 오늘날 인류의 다양한 게놈이나 박테리아의 서로 다른 균주처럼 단일 종 내부의 변이를 연구합니다. 두 그룹 모두 동일한 생물학적 사건을 연구하지만, 그들은 좀처럼 같은 언어를 사용하지 않았습니다. 첫 번째 그룹은 직계 혈통을 가정하는 단순한 나무 형태의 모델을 사용하는 반면, 두 번째 그룹은 유전자가 개체 사이를 뛰어넘을 수 있는 인구 집단의 무질서한 현실을 포착하는 복잡한 그물망 형태의 지도를 사용합니다. 이러한 단절은 관련 게놈 집단의 진정한 구조적 복잡성을 단일하고 통일된 방식으로 측정하는 것을 어렵게 만들었습니다.

레오나르드 보넨켐퍼(Leonard Bohnenkämper)와 옌스 스토리(Jens Stoye)는 이 간극을 메울 새로운 방법을 제안했습니다. 그들은 유전자를 해체하는 데 필요한 특정 이동 횟수를 세어 게놈 집단이 얼마나 "복잡한지" 정량화하는 방법을 도입했습니다. 게놈 집단을 나타내는 엉클어진 실타래를 상상해 보십시오. 연구자들은 그 엉킨 뭉치를 하나의 단순하고 곧은 가닥으로 만드는 데 정확히 몇 번의 자르기와 다시 잇기가 필요할지 알고 싶어 했습니다. 그들은 이를 '판게놈을 위한 완전 조상 재구성(Complete Ancestral Reconstruction for Pangenomes)' 문제라고 부릅니다. 그들의 접근 방식은 게놈의 집합을 정적인 목록이 아니라, 유전자가 이동하거나 복제되거나 위치를 바꿀 수 있는 동적인 시스템으로 취급합니다. 연구진은 모든 유전 물질이 가지의 혼란 없이 오직 하나의 다른 조각에만 연결되는 상태를 "단순한" 상태로 정의함으로써, 판게놈의 무질서한 현실과 저 단순함의 이상 사이의 거리를 측정하는 자를 만들었습니다.

연구진은 이 퍼즐을 풀기 위해 수학적 프레임워크를 개발했으며, 먼저 '단일 절단 또는 결합(single cut or join)'이라는 특정 유형의 유전적 이동에 집중했습니다. 이 모델에서 절단은 염색체를 분리하고, 결합은 두 끝을 연결합니다. 연구팀은 어떤 복잡한 게놈 집단이라도 이를 단순화하는 데 필요한 최소한의 절단 및 결합 횟수는 유전 지도 내의 '경합하는 연결(contested connections)'의 수와 정확히 일치한다는 것을 증명했습니다. 경합하는 연결이란 DNA 조각이 동시에 둘 이상의 이웃에게 연결되려고 시도하여 그래프에 분기점을 만드는 지점을 말합니다. 게놈 지도가 이러한 분기점을 많이 가지고 있다면 매우 복잡하며, 이를 곧게 펴기 위해 많은 작업이 필요합니다. 반대로 분기가 적다면 구조적으로 단순합니다. 이 발견은 이전에 대규모 집단에 대해서는 계산적으로 불가능하다고 여겨졌던 문제를 수천 개의 게놈에 대해서도 거의 즉각적으로 해결할 수 있는 과제로 바꾸어 놓았다는 점에서 매우 중요합니다.

아이디어를 테스트하기 위해 연구팀은 단순한 게놈에서 시작하여 무작위적인 뒤섞임, 복제, 손실을 도입해 점점 더 복잡한 게놈 가족을 만들어내는 시뮬레이션을 실행했습니다. 그들은 자신들의 새로운 측정치가 실제 시뮬레이션된 작업 횟수와 매우 높은 상관관계(0.89에서 0.91)를 보이며, 시뮬레이션된 뒤섞임의 수를 매우 잘 추적한다는 것을 발견했습니다. 시뮬레이션된 게놈이 약간만 변했을 때는 측정치가 낮았고, 연구진이 재배열을 더 많이 추가할수록 측정치는 꾸준히 상승하며 증가하는 구조적 혼돈을 정확하게 반영했습니다. 또한 그들은 이 방법이 원래의 단순한 조상을 얼마나 잘 재구성하는지도 확인했습니다. 이 방법은 어떤 연결이 확실히 보존되었는지 식별하는 데는 매우 뛰어났지만(높은 정밀도), 게놈이 더 많이 뒤섞어질수록 더 보수적으로 변하여, 불확실한 연결을 추측하기보다는 재구성된 조상을 더 작은 조각들로 나누는 경향을 보였습니다. 이러한 보수적인 접근 방식은 결과가 항상 완벽하지는 않더라도 신뢰할 수 있도록 보장합니다.

연구진은 이후 실제 생물학적 데이터에 이 방법을 적용하여 박테리아, 효모, 초파리, 인간을 포함한 8가지 종의 완전한 게놈을 다운로드했습니다. 그들은 이 종들의 유전적 변이 지도를 구축하고 각 종의 복잡도 점수를 계산했습니다. 결과에 따르면, 이 방법은 초기 지도를 구축하는 데 사용된 특정 소프트웨어와 관계없이 종들을 구조적 복잡도에 따라 일관되게 순위를 매길 수 있었습니다. 예를 들어, 연구진은 Yersinia pestis와 Escherichia coli 박테리아가 상대적으로 낮은 복잡도 점수를 가진 반면, 인간 게놈은 우리 종 내에서 발견되는 방대한 구조적 변이를 반영하여 훨씬 높은 점수를 보인다는 것을 발견했습니다. 또한 이 방법은 서로 다른 소프트웨어 도구가 유전 지도를 구축하는 방식의 미묘한 차이를 드러냈습니다. 세 가지 방법으로 구축된 인간 게놈 그래프를 분석했을 때, 연구진은 지도들의 크기는 비슷해 보였지만, 한 가지 방법이 다른 방법들보다 구조적으로 훨씬 더 복합적인 그래프를 생성한다는 것을 발견했습니다. 이는 해당 방법이 다른 종류의 유전적 변이를 포착하고 있음을 시사합니다.

이 연구는 단순히 새로운 숫자를 계산하는 법을 제공하는 것이 아니라, 생명의 역사를 바라보는 새로운 렌즈를 제공합니다. 판게놈의 복잡성이 단순화하는 데 필요한 절단 횟수로 측정될 수 있음을 보여줌으로써, 연구진은 종의 깊은 역사와 그 내부의 즉각적인 변이 모두에 적용할 수 있는 도구를 만들었습니다. 이 방법은 현대의 시퀀싱 기술이 생성하는 방대한 데이터셋을 처리할 수 있을 만큼 빠르며, 인간 규모의 게놈 집단을 분석하는 데 단 몇 분밖에 걸리지 않습니다. 현재 버전은 단순한 유전적 이동 모델을 사용하지만, 이 프레임워크는 확장 가능하도록 설계되었습니다. 과학자들이 더 복잡한 유형의 유전적 재배열에 대한 해결책을 개발함에 따라, 이와 동일한 접근 방식을 사용하여 종의 상세한 프로필을 작성하고, 어떤 유형의 뒤섞임이 그 종의 진화 경로를 정의하는지 보여줄 수 있을 것입니다. 현재로서는, 이 방법은 추상적인 게놈 복잡성이라는 개념을 구체적이고 셀 수 있는 현실로 바꾸어 놓으며, 살아있는 세계의 엉클어진 아름다움을 측정하는 명확하고 실용적인 방법으로 자리 잡고 있습니다.

기술 요약: 팬게놈의 재배열 복잡도 정량화

문제 정의
본 논문은 두 가지 확립된 분야, 즉 비교 유전체학(종 간의 게놈 재배열에 초점)과 팬게노믹스(종 내의 구조적 변이에 초점) 사이의 단절 문제를 다룹니다. 두 분야 모두 유사한 데이터 구조(예: 브레이크포인트 그래프 및 팬게놈 그래프)를 활용하지만, 서로 다른 시간 척도와 데이터 유형으로 인해 역사적으로 별개로 연구되어 왔습니다. 역전(reversal) 문제와 같은 고전적인 재배열 문제는 종종 NP-난해(NP-hard)이며 계통수(phylogenetic tree)를 전제로 하는데, 이는 수평적 유전자 전달(HGT)이나 성적 재조합과 같이 계통 간 상호작용이 빈번하고 복잡한 팬게놈에는 적합하지 않습니다. 또한, 기존의 팬게놈 지표(예: 개방성, 핵심 비율)는 완전한 염색체로부터 유도된 팬게놈 그래프의 '구조적 복잡성'을 충분히 정량화하지 못합니다. 저자들은 팬게놈 그래프를 단순화하는 데 필요한 재배열 연산이 얼마나 "복잡한가"를 정량화하기 위한 통합된 프레임워크의 필요성을 식별했습니다.

방법론
저자들은 팬게놈을 위한 완전한 조상 재구성(Complete Ancestral Reconstruction for Pangenomes, CARP) 문제를 제안합니다. 이 프레임워크는 팬게놈의 구조적 복잡도를 주어진 팬게놈을 "단순한" 팬게놈(그래프 표현에서 분기 경로가 없는 것)으로 변환하는 데 필요한 최소한의 **그래프 변경 연산(Graph Altering Operations, GAO)**으로 정의하며, 이때 무제한의 **경로 변경 연산(Path Altering Operations, PAO)**을 허용합니다.

정의:
- 마커 및 인접성(Markers and Adjacencies): 팬게놈은 마커의 끝단을 나타내는 노드와 마커 간의 연결(마커 엣지) 또는 마커 간의 인접성(인접성 엣지)을 나타내는 엣지로 구성된 **다중 브레이크포인트 그래프(Multiple Breakpoint Graph, MBG)**로 표현됩니다.
- 단순 팬게놈(Simple Pangenome): 팬게놈이 "단순하다"는 것은 모든 마커 끝단이 최대 하나의 인접성 엣지에 연결되어 결과적으로 분기 노드가 없는 그래프를 형성함을 의미합니다.
- 연산:
  - GAO: 그래프 구조를 변경하는 연산(예: 역전, 절단, 결합). CARP 문제에서 최소화하고자 하는 "비용이 드는" 연산입니다.
  - PAO: MBG 구조를 변경하지 않고 염색체 경로를 변경하는 연산(예: 융합, 분기, 염색체 전이, 상동 재조합). 저자들은 동일한 MBG를 가진 임의의 두 팬게놈을 서로 변환할 수 있는 "완전한" PAO 집합을 정의합니다.
CARP 문제: 주어진 팬게놈 $P$ , 완전한 PAO 집합 $N$ , 그리고 GAO 집합 $A$ 가 주어졌을 때, $N$ 에 속한 임의의 수의 PAO를 사용하여 $P$ 를 단순한 팬게로 변환하는 최단 경로의 GAO 시퀀스를 찾는 것입니다.
SCJ 모델 하에서의 해법: 저자들은 단일 절단 또는 결합(Single-Cut-or-Join, SCJ) 모델에 대한 구체적인 해법을 제공합니다. 그들은 SCJ 하에서의 CARP 측도가 MBG에서의 논쟁적 인접성(contested adjacencies) 수와 직접적으로 대응함을 증명합니다. 논쟁적 인접성은 분기 노드(인접성 부그래프에서 차수가 2보다 큰 노드)에 연결된 엣지로 정의됩니다.
- 정리: 필요한 최소 SCJ 연산의 수는 정확히 논쟁적 인접성의 수( $|E_{cnt}|$ )와 같습니다.
- 알고리즘: 저자들은 논쟁적 엣지를 식리고, 감소하는 사이클(diminishing cycles, PAO를 통해)을 사용하여 각 논쟁적 엣지의 다중도가 1이 될 때까지 줄여서 해당 엣지를 절단할 수 있도록 하는 선형 시간 알고리즘(Algorithm 2)을 제시합니다.

주요 기여

CARP 공식화: 그래프 변경 이벤트(구조적 복잡도)와 경로 변경 이벤트(계통 상호작용)를 명시적으로 분리함으로써, 고전적 재배열 이론과 팬게노믹스를 통합하는 새로운 재배열 문제를 도입했습니다.
이론적 프레임워크: 복잡도 지표에 비용을 발생시키지 않으면서도 복잡한 팬게놈 상호작용을 모델링할 수 있도록 (염색체 전이 및 상동 재조합을 포함한) "완전한" PAO 집합을 정의했습니다.
선형 시간 해법: SCJ 모델 하에서 CARP 문제가 단순히 MBG의 논쟁적 인접성 개수와 같다는, 놀라울 정도로 간단한 선형 시간 해법을 도출했습니다.
구현: SCJ-CARP 측도를 계산하고 다양한 규모의 팬게놈 그래프를 분석할 수 있는 carp 및 carp-scan 도구를 개발했습니다.

결과
저자들은 시뮬레이션 및 실제 데이터를 사용하여 SCJ-CARP 측도를 평가했습니다.

시뮬레이션 데이터: ZOMBI를 사용하여 다양한 재배열 비율을 가진 계통수를 시뮬레이션했을 때, SCJ-CARP 측도는 시뮬레이션된 재배열 이벤트의 수와 강한 상관관계(Pearson 0.89, Spearman 0.91)를 보였으며, 특히 낮은 비율에서 그러했습니다. 그러나 재배열 비율이 높아짐에 따라 조상 인접성 재구성은 높은 정밀도(precision)를 보였으나 낮은 재현율(recall)을 보였는데, 이는 SCJ 단순화의 보수적인 특성과 일치합니다.
교차 분류군 비교: 이 방법은 서로 다른 블록 탐지 방법(Minigraph-Cactus 및 SibeliaZ)을 사용한 8개 분류군(Yersinia pestis, Escherichia coli, Homo sapiens 포함)의 팬게놈에 적용되었습니다. SCJ-CARP 측도는 블록 정의에 따른 절대값의 차이에도 불구하고, 이들 팬게놈의 상대적 구조적 복잡도 순위를 일관되게 산출했습니다.
인간 팬게놈 그래프 분석: 저자들은 Minigraph, Minigraph-Cactus, PGGB로 구축된 그래프를 비교했습니다. 분석 결과, Minigraph-Cactus와 PGGB는 유사한 노드 수를 가졌지만, 작은 노드를 필터링할 때 구조적 복잡성이 크게 갈라지는 것으로 나타났습니다. PGGB의 그래프는 필터링 시 복잡도가 증가하는 경향을 보였는데, 이는 중복을 고도로 연결된 작은 노드로 압축하는 정렬 기반 패러다임을 반영합니다. 반면 Minigraph과 Minigraph-Cactus는 더 유사한 구조적 행동을 보였습니다.

의의 및 주장
본 논문은 CARP가 "공동 모델링(joint modeling)"을 향한 첫 걸음이라고 주장합니다. 이 연구의 의의는 다음과 같습니다.

단순한 노드/엣지 수를 넘어 팬게놈 그래프의 구조적 복잡도를 정량화하기 위해 재배열 기반의 공식적인 지표를 제공합니다.
SCJ와 같은 단순한 모델 하에서도, 이 지표가 (사용된 방법론에 대한 사전 지식 없이도) 팬게놈 구축 방법론 간의 구조적 차이를 구별할 수 있는 유용한 통찰을 제공함을 입증했습니다.
더 복잡한 재배열 모델(예: DCJ, 역전)에 CARP를 적용할 수 있는 토대를 마련하여, 어떤 생물학적 모델이 복잡성을 가장 잘 설명하는지 나타내는 벡터 기반의 팬게놈 특성화를 가능하게 합니다.

저자들은 현재의 범위에 대해 겸허한 태도를 유지하며, SCJ 솔루션이 시작점일 뿐이며 절대적인 측정값은 입력 게놈 크기와 블록 정의에 따라 달라질 수 있음을 언급하며 향후 정규화 노력의 필요성을 시사했습니다. 또한 현재의 PAO 집합이 반드시 가장 짧거나 생물학적으로 가장 현실적인 것은 아니지만, 이론적 경계를 정의하기에는 충분하다고 밝혔습니다.

유사한 논문