Lossless Reductions and Hybrid Sampling for Phylogeny Using the Maximum Compatibility Criterion
이 논문은 손실 없는 그래프 축소와 하이브리드 양자-고전 샘플링 기술을 도입하여 모든 최적의 형질 집합을 효율적으로 열거함으로써 최대 호환성 계통 재구성을 향상시키며, 노이즈가 있는 양자 장치에서 기존 라그랑주 승수법의 한계를 해결하는 동시에 SARS-CoV-2 데이터에 대한 효과를 입증한다.
원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. 이것은 동료 심사를 거치지 않은 프리프린트의 AI 생성 설명입니다. 의학적 조언이 아닙니다. 이 내용을 바탕으로 건강 관련 결정을 내리지 마세요. 전체 면책 조항 읽기
지구상의 생명은 모든 생명체의 유전 암호에 기록된 하나의 이야기이며, 수백만 년에 걸쳐 인구 집단이 어떻게 분리되고, 이동하고, 변화해 왔는지에 대한 역사이다. 이 역사를 읽기 위해 과학자들은 서로 다른 유기체 사이의 관계를 지도화하는 계통수라고 불리는 가계도를 구축한다. 이러한 나무는 단순히 학술적인 호기별 대상이 아니다. 그것들은 연구자들이 단일 체내에서 암이 어떻게 진화하는지 이해하고, 특정 병원체를 표적으로 하는 약물을 설계하며, SARS-CoV-2와 같은 새로운 바이러스 변이의 확산을 추적하는 데 도움을 준다. 그러나 이러한 나무를 재구성하는 것은 어려운데, 왜냐하면 우리는 오늘날 살아있는 유기체들의 유전적 스냅샷만을 가지고 있을 뿐, 과거의 전체 기록을 가지고 있지 않기 때문이다. 과학자들은 가진 데이터를 바탕으로 진화의 가장 가능성 높은 경로를 추론해야 하며, 형질이 어떻게 전해지거나 변화했는지를 시사하는 패턴을 찾아야 한다.
이를 수행하는 강력한 방법 중 하나는 단 하나의 나무에서도 모순 없이 완벽하게 들어맞는 가장 큰 유전적 형질 그룹을 찾는 것이다. 대부분의 조각은 쉽게 잘 맞지만, 몇몇 조각은 뒤틀려 있거나 수렴 진화(서로 관련 없는 종들이 독립적으로 유사한 형질을 발달시키는 것)에 의해 모양이 변한 퍼즐을 상상해 보라. 목표는 패턴을 깨뜨리는 조각들은 무시하면서, 일관된 그림을 형성하는 가장 큰 조각 세트를 찾는 것이다. 이것은 최대 호환성 문제(maximum compatibility problem)로 알려져 있다. 단 하나의 좋은 해결책을 찾는 것도 어렵지만, 가능한 모든 최적의 해결책을 모두 찾는 것은 훨씬 더 어려우며, 이는 완전하고 정확한 가계도를 구축하는 데 매우 중요하다. 만약 과학자들이 단 하나의 해결책만을 찾는다면, 데이터가 뒷받침하는 중요한 대안적 역사들을 놓칠 수도 있다.
한 연구팀은 고전적인 컴퓨터 기술과 신흥 양자 방법을 결합하여 단 하나가 아닌 모든 최적의 진화 나무를 찾아내는 이 어려운 퍼즐을 해결하는 새로운 접근 방식을 개발했다. 그들의 작업은 컴퓨터가 수백만 개의 가능성을 샅샅이 뒤져 가장 큰 호환되는 형질 그룹을 찾아내야 하는 특정 단계에 집중되어 있다. 연구진은 기존 방식이 단일 정답을 찾는 데는 뛰어나지만, 동등하게 좋은 해결책들의 전체 다양성을 포착하는 데는 종종 어려움을 겪는다는 것을 발견했다. 이를 해결하기 위해 그들은 두 단계 전략을 도입했다. 첫째, 거대한 퍼즐을 가능한 모든 답을 잃지 않으면서도 다룰 수 있는 크기로 축소하는 규칙 세트를 만들었다. 둘째, 양자 컴퓨터를 마법 같은 해결사가 아니라, 클래식 컴퓨터에 의해 정제되고 검증될 수 있는 다양한 후보군을 생성하는 도구로 사용하여 이 후보들을 샘플링하는 새로운 방법을 테스트했다.
연구진은 현재 기술의 한계를 시험할 수 있을 만큼 충분히 큰 데이터셋인 수십만 개의 SARS-CoV-2 바이러스 서열 데이터를 조사하는 것으로 시작했다. 그들은 양자 컴퓨터를 사용하여 이 문제를 해결하는 표준적인 방식이 최적이 아니라는 것을 발견했다. 일반적으로 양자 알고리즘은 규칙을 엄격하게 강제하여 모든 후보 해결책이 퍼즐의 법칙을 완벽하게 따르도록 조정된다. 그러나 연구팀은 노이즈가 있는 실제 환경의 양자 장치에서는 이러한 엄격함이 오히려 방해가 된다는 것을 발견했다. 대신, 그들은 양자 컴퓨터가 몇 가지 규칙을 어길 수도 있는 "엉성한" 후보들을 생성하도록 허용하고, 그 후 빠른 클래식 컴퓨터 프로그램을 사용하여 이를 수정하는 것이 더 낫다는 것을 발견했다. 이 복구 과정은 마치 숙련된 편집자가 초안을 가져와 최종적인 완벽한 버전으로 다듬는 것과 같다. 양자 기계가 더 넓은 범위의 가능성을 탐색하게 하고 그 결과를 정제함으로써, 그들은 양자 기계에게 처음부터 완벽함을 강요할 때보다 더 많은 구별된 해결책들을 찾아낼 수 있었다.
이 과정을 현재의 기술로 효율적으로 만들기 위해, 팀은 양자 컴퓨터로 문제를 보내기 전에 문제를 압축하는 방법을 개발했다. 그들은 유전 데이터의 많은 부분이 매우 예측 가능하여, 나중에 어떻게 다시 결합할지에 대한 기록만 유지한다면 계산에서 완전히 제외할 수 있다는 점을 깨달았다. 이는 그림의 프레임을 제거하여 캔버스를 보는 것과 같으며, 나중에 어떻게 다시 부착할지 정확히 알고 있는 상태를 의미한다. 이러한 손실 없는 축소 규칙을 적용함으로써, 그들은 수백 개의 노드를 가진 유전 데이터를 나타내는 복잡한 그래프를 단 몇 개의 노드로 줄일 수 있었다. 350개의 바이러스 샘플을 포함한 특정 테스트 케이스에서, 그들의 방법은 64개의 점을 가진 그래프를 단 5개의 점을 가진 작고 단순한 그래프로 줄였다. 이는 마지막 단계의 답을 찾는 과정을 사소하게 만들었으며, 이를 통해 완전한 최적 진화 나무 세트를 확실하게 복구할 수 있게 했다.
실험 결과는 하나의 답을 찾는 것과 모든 답을 찾는 것 사이의 명확한 차이를 보여주었다. 표준적인 클래식 도구를 사용하여 최적의 해결책을 찾을 때, 그들은 단일 최고 결과를 찾는 데는 종종 성공했다. 그러나 데이터가 배치될 수 있는 모든 다른 방법들을 찾으려고 할 때, 동일한 도구들은 수천 번을 실행하더라도 유효한 해결책 중 상당수를 놓치는 경우가 많았다. 그들의 하이브리드 접근 방식은 그래프 압축과 수정된 양자 샘플링 방법을 결합하여, 이러한 숨겨진 다양성을 밝혀내는 데 훨씬 더 뛰어난 성능을 보였다. 64개의 점을 가진 테스트 그래프에서, 그들의 수정된 양자 방법은 무작위 추측 방법보다 더 많은 구별되고 검증된 해결책을 모든 시행에서 찾아냈다. 이것이 아직 양자 컴퓨터가 이 작업에서 클래식 컴퓨터보다 우월하다는 것을 입증한 것은 아니지만, 스마트한 데이터 축소와 양자 샘플링의 결합이 이전에는 완전히 해결하기에 너무 크거나 복잡했던 문제들을 다루는 강력한 방법임을 입증했다.
궁극적으로 이 연구는 진화 생물학을 위한 새로운 길을 제시한다. 데이터를 먼저 단순화하고, 샘 샘플링한 다음, 마지막으로 재구성하는 모듈형 시스템으로 취급함으로써, 과학자들은 이제 이전보다 훨씬 더 큰 데이터셋을 다룰 수 있게 되었다. 연구진은 거대한 바이러스 서序列 세트를 가져와 예측 가능한 부분을 제거하고, 남은 복잡한 핵심 부분을 탐색하기 위해 양자 장치를 사용한 다음, 완벽한 정확도로 전체 그림을 재구성할 수 있음을 보여주었다. 이 접근 방식은 양자 컴퓨터가 완벽하거나 오류가 없어야 한다는 것에 의존하지 않는다. 대신, 이를 다양한 아이디어의 원천으로 사용하고 클래식 논리로 정제한다. 양자 기술이 계속 발전함에 따라, 클래식과 양자 컴퓨팅의 강점을 결합하는 이 방법은 과학자들이 이전에는 도달할 수 없었던 수준의 상세함과 완전함으로 생명의 역사를 재구성할 수 있게 해줄 것이다.
연구 분야의 논문에 파묻히고 계신가요?
연구 키워드에 맞는 최신 논문의 일일 다이제스트를 받아보세요 — 기술 요약 포함, 당신의 언어로.