A Block Decomposed QUBO Workflow for Chromosome-Y Phylogeny Reconstruction

모든 생명체는 DNA에 기록된 역사를 지니고 있으며, 이는 수천 년 동안 인구 집단이 어떻게 이동하고, 혼합되고, 분리되었는지를 보여주는 분자적 기록입니다. 과학자들에게 이 역사를 재구성하는 것은 유전적 변이라는 조각들을 모아 종의 가계도라는 그림을 완성하려는 거대하고 파편화된 퍼즐을 맞추는 것과 같습니다. 인간의 조상을 추적하는 가장 신뢰할 수 있는 방법 중 하나는 Y 염색체를 살펴보는 것인데, 이는 아버지로부터 아들에게 거의 변하지 않은 채 전달되는 작은 DNA 조각입니다. Y 염색체는 어머니의 DNA와 섞이지 않기 때문에 명확하고 끊기지 않는 계보 역할을 하며, 연구자들이 인류 가계도의 깊은 가지를 그려낼 수 있게 해줍니다. 그러나 유전 데이터의 양이 증가함에 따라, 올바른 트리 구조를 찾는 작업은 매우 어려워지고 있습니다. 심지어 적은 수의 사람들을 가계도로 배열하는 방법의 가짓수조차 너무 방대하여, 표준 컴퓨터가 모든 가능성을 하나씩 확인하는 능력을 초과합니다. 이러한 조합 폭발(combinatorial explosion)로 인해 과학자들은 최선의 답을 빠르게 추측하지만 그것이 반드시 정답임을 보장하지는 않는 휴리스틱(heuristics), 즉 지름길에 의존할 수밖에 없었습니다.

사르데냐의 CRS4에 있는 연구팀은 두 가지 서로 다른 전략을 결사하여 문제를 해결하는 새로운 계산 워크플로우를 개발했습니다. 바로 거대한 문제를 관리 가능한 작은 조각으로 나누는 것과, 특수한 유형의 양자 영감 알고리즘을 사용하여 그 조각들을 해결하는 것입니다. 그들의 연구는 인간의 Y 염색체 데이터, 구체적으로는 단일 염기 다형성(SNP)이라고 알려진 유전 코드의 단일 문자 변화에 초점을 맞추고 있습니다. 연구진은 150개의 샘플에서 유래한 유전 정보를 포함하는 데이터셋으로 시작했으며, 필요한 유전적 변이가 부족한 72개의 정보가 없는 샘ks를 제거하여 분석을 위한 78개의 남성 집단을 남겼습니다. 그런 다음 그들은 새로운 방법을 사용하여 진화 트리를 재구성했습니다. 현재의 기술로는 너무 복잡하여 전체 트리를 한 번에 해결하는 대신, 과업을 두 가지 주요 결정으로 나누었습니다. 첫째, 어떤 집단들이 트리 상에서 함께 클러스터링되어야 하는지를 결정했습니다. 둘째, 시간의 방향을 보여주기 위해 트리의 맨 시작점인 뿌리(root)를 어디에 배치해야 할지를 파악했습니다.

이러한 결정을 내리기 위해, 연구진은 생물학적 문제를 이차 비제약 이진 최적화(quadratic unconstrained binary optimization)라고 알려진 수학적 형식으로 변환했습니다. 쉽게 말해, 이것은 최적의 트리를 찾는 과정을 복잡한 언덕과 골짜기로 이루어진 풍경 속에서 가장 낮은 지점을 찾는 게임으로 바꾸는 것입니다. 여기서 가장 낮은 지점은 가장 가능성 높은 가족사를 나타냅니다. 문제는 이 풍경이 너무 거대하여 한꺼번에 탐색하기 어렵다는 점입니다. 연구팀의 해결책은 ADMM 분해(ADMM decomposition)라는 기술을 사용하는 것이었는데, 이는 거대한 풍경을 겹쳐진 작은 구역들로 나누는 방식입니다. 각 구역은 독립적으로 해결되며, 그 후 결과물들을 하나로 묶어 일관된 전체를 형성합니다. 이를 통해 시스템은 단일 컴퓨터가 처리하기 불가능했을 법한 규모의 문제를 다룰 수 있게 됩니다.

이 작은 구역들을 해결하기 위해, 팀은 디지털 카운터-다이아베틱 양자 최적화(digitized counter-diabatic quantum optimization)라고 불리는 방법을 채택했습니다. 이 접근법은 양자 역학의 원리를 사용하여 풍경의 가장 낮은 지점을 매우 빠르게 찾아냅니다. 반복적인 시행착오를 거치는 다른 양자 방법들과 달리, 이 기술은 단 한 번의 직접적인 통과(direct pass)로 해결책으로 가는 경로를 계산합니다. 연구진은 양자 프로세서의 동작을 모방한 노이즈가 없는 컴퓨터 시뮬레이션에서 워크플로우를 테스트했습니다. 그들은 이 방법이 78개 집단의 가계도를 성공적으로 재구성했다는 것을 발견했습니다. 결과 트리는 아프리카 혈통 깊숙한 곳에 뿌리를 두었으며, 이는 인류 기원에 대한 확립된 과학적 이해와 일치하는 결과입니다. 또한, 새로운 방법이 식별한 모든 그룹이 이웃 결합(Neighbor-Joining)이라는 표준적이고 널리 받아들여지는 트리 구축 기술과 일치했지만, 새로운 방법은 이웃 결합 참조 트리에서 발견된 그룹의 40%만을 회복했는데, 이는 그들의 접근 방식이 정밀하기는 하지만 표준 방식보다 더 적은 총 클러스터를 식별했음을 나타냅니다.

이 연구는 거대한 문제를 나누는 것과 효율적인 양자 스타일의 솔버를 결합하는 이 하이브리드 접근 방식이 인구 유전학의 실행 가능한 경로임을 입증합니다. 이는 현재의 대규모 양자 컴퓨터가 필요로 하는 거대하고 오류가 많은 하드웨어를 요구하지 않으면서도, 전통적인 지름길의 추측을 넘어설 수 있는 방법을 제공합니다. 시뮬레이션된 양자 장치에서 이러한 어려운 트리 재구성 문제를 해결할 수 있음을 증м함으로써, 연구진은 이 기술이 향후 더 큰 데이터셋에도 적용될 준비가 되었음을 보여주었습니다. 그들의 연구는 가공되지 않은 유전 데이터를 각 가지를 정의하는 특정 유전 마커가 포함된, 뿌리가 있고 주석이 달린 가계도로 바꾸는 명확하고 단계적인 파이프라인을 제공합니다. 이 성과는 해당 분야가 근사치에 대한 의존도를 줄이면서도 인류 진화 역사의 전체 복잡성을 더 높은 정밀도로 지도화할 수 있는 미래로 나아가고 있음을 시사합니다.