💻 bioinformatics

Scaling Quantum Optimisation Beyond Hardware Limits for Real-World Scientific Workloads: Genome Assembly on Current Quantum Hardware

이 연구는 해밀토니안 자동 분해 최적화 프레임워크(HADOF)가 현재의 NISQ 하드웨어 한계를 극복하여 실제 양자 하드웨어 상에서 710만 염기쌍의 슈도모나스 에루기노사(Pseudomonas aeruginosa) 게놈을 99.348%의 게놈 분율로 성공적으로 조립할 수 있음을 입증하며, 대규모 과학적 워크로드를 위한 확장 가능한 양자 최적화의 생존 가능성을 증명한다.

원저자: G Sankar, N., Miliotis, G., Caton, S.

게시일 2026-09-09

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: G Sankar, N., Miliotis, G., Caton, S.

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

모든 생명체는 A, C, G, T라는 네 가지 화학적 문자로 쓰인 자신만의 고유한 설명서를 지니고 있습니다. 유기체가 어떻게 기능하는지, 어떻게 질병을 일으키는지, 또는 어떻게 약물에 저항할 수 있는지를 이해하기 위해 과학자들은 먼저 이 설명서 전체를 읽어야 합니다. 하지만 현대의 기계들은 한 번에 책 전체를 읽을 수 없습니다. 대신, 그들은 DNA를 수백만 개의 작고 중첩되는 조각들로 잘게 나누는데, 이는 마치 소설을 수천 개의 작은 조각으로 갈갈이 찢어 놓는 것과 같습니다. 게놈 조립의 과제는 이 흩어진 조각들을 가져와서 올바르고 완전한 서열로 다시 조립하는 것입니다. 이것은 조각들이 단순히 뒤섞여 있을 뿐만 아니라, 종종 오류와 혼란스러운 반복 구간을 포함하고 있어 어떤 조각이 어디에 속하는지 알기 어렵게 만드는 거대한 퍼즐입니다. 이를 정확하게 수행하는 것은 감염병을 추적하고, 암을 이해하며, 박테리아가 항생제에 살아남기 위해 어떻게 진화하는지 모니터링하는 데 매우 중요합니다.

수십 년 동안 과학자들은 이 퍼즐을 풀기 위해 조각들의 최적의 순서를 추측하는 영리한 지름길을 사용하여 고전 컴퓨터에 의존해 왔습니다. 그러나 게놈이 더 커지고 복잡해짐에 따라 이러한 지름길은 때때로 실패하여 공백을 남기거나 잘못된 연결을 만들어내기도 합니다. 새로운 연구 분야는 양자 컴퓨터가—아원자 세계를 지배하는 기이한 물리 법칙에 따라 작동하는—이 퍼즐을 더 효과적으로 해결할 수 있을지 질문을 던집니다. 기대되는 바는 이 기계들이 수백만 가지의 가능한 배열을 동시에 탐색하여 데이터 속에서 단 하나의 최적의 경로를 찾아내는 것입니다. 그러나 현재의 양자 컴퓨터는 아직 초기 단계에 머물러 있습니다. 그것들은 작고 취약하며 오류를 범하기 쉬워, 실제 생물학에 필요한 방대한 데이터 세트를 아직 처리할 수 없습니다.

최근 한 연구에서 연구진은 실제 양자 컴퓨터를 사용하여 심각한 감염을 일으킬 수 있는 흔한 박테리아인 녹농균(Pseudomonas aeruginosa)의 게놈을 조립하려고 시도하며 바로 이 문제에 도전했습니다. 연구팀은 컴퓨터의 제한된 크기 때문에 불가능했을 전체 퍼즐을 기계에 한꺼번에 강제로 떠넘기려 하지 않았습니다. 대신, 그들은 문제를 수천 개의 작고 관리 가능한 조각들로 나누었습니다. 그들은 '해밀토니안 자동 분해 최적화 프레임워크(Hamiltonian Auto Decomposition Optimisation Framework, HADOF)'라고 불리는 새로운 방법을 사용했는데, 이는 조정자 역할을 합니다. 이 프레임워크는 거대한 조립 작업을 양자 칩에 적합한 작은 하위 문제들로 나누고, 이들을 하나씩 해결한 다음 결과를 다시 하나로 엮어냅니다. 연구진은 710만 염기쌍 크기의 게놈을 가진 박테리아의 실제 DNA 시퀀싱 데이터를 사용하여 133개의 양자 비트, 즉 큐비트로 구성된 실제 양자 프로세서로 이 접근 방식을 테스트했습니다.

결과는 양자 컴퓨터가 완벽하지는 않지만, 여전히 생물학적으로 유용한 답을 낼 수 있음을 보여주었습니다. 양자 보조 방식은 박테리아 게놈의 99.348%를 재구성해 냈는데, 이는 최고의 고전 컴퓨터가 달성할 수 있는 수준에 놀라울 정도로 근접한 결과입니다. 재구성된 서열은 원래의 복사본에 거의 완벽했으며, 중복되거나 누락된 섹션이 거의 없었습니다. 이러한 성공은 양자 최적화가 아주 작은 연습용 예제를 넘어 훨씬 더 큰 규모, 즉 실제 임상적으로 유의미한 유기체 규모에서도 작동할 수 있음을 입증했다는 점에서 의미가 큽니다. 연구진은 양자 컴퓨터가 계산상의 수학적으로 '최선'인 점수를 단순히 찾아낸 것이 아님을 발견했습니다. 때로는 수학적으로 완벽한 점수가 오히려 깨지거나 잘못된 게놈으로 이어지기도 했습니다. 대신, 성공의 열쇠는 솔루션의 구조, 구체적으로는 최종 경로에 유지된 조각의 개수를 살펴보는 것이었으며, 이를 통해 광범위한 가능성 중에서 올바른 조립을 식별해 냈습니다.

이 연구는 또한 기술의 현재 한계를 강조했습니다. 연구진이 동일한 문제를 완벽하고 노이즈가 없는 양자 컴퓨터 시뮬레이션에서 실행했을 때, 결과는 실제 기계에서보다 약간 더 좋았습니다. 실제 하드웨어는 오류를 유발하여 원시 수학적 점수를 더 나쁘게 만들고 솔루션을 더 파편화되게 만들었습니다. 그러나 연구진은 이러한 오류가 있음에도 불구하고, 근본적인 방법론이 고품질의 게놈을 복구할 만큼 견고하다는 것을 보여주었습니다. 그들은 최종 조립에 유지된 조각의 수가 성공의 강력한 지표라는 것을 발견했습니다. 즉, 컴퓨터가 부여한 원시 점수와 상관없이 일정 최소한의 조각 수를 유지하는 솔루션은 거의 항상 완전한 게놈을 만들어냈습니다. 이는 향후 과학자들이 완벽한 양자 컴퓨터를 기다리지 않고도, 데이터를 해석하는 올바른 방법만 있다면 현재의 불완전한 기계들을 사용하여 유용한 결과를 얻을 수 있음을 시사합니다.

이 작업은 이론적 약속과 실제 응용 사이의 가교 역할을 합니다. 이는 양자 컴퓨팅과 영리한 고전적 전략을 결합함으로써, 과학자들이 이전에 도달할 수 없었던 생물학적 문제를 해결하기 시작할 수 있음을 보여줍니다. 연구진은 자신들의 코드와 데이터를 대중에게 공개하여 다른 이들이 다양한 유기체와 다양한 기계로 이 방법들을 테스트할 수 있도록 했습니다. 이것이 아직 병원과 실험실에서 사용하는 표준 도구들을 대체하는 것은 아니지만, 양자 최적화가 실제 세계의 생물학적 복잡성을 다룰 수 있다는 명확한 증거입니다. 앞으로의 과제는 이러한 방법들을 더 큰 게놈을 다루도록 정교화하고, 현재의 하드웨어가 필연적으로 만들어내는 오류들을 더 잘 걸러내는 것입니다. 현재로서는, 이 연구는 양자 컴퓨터가 한 번에 한 조각씩 가장 복잡한 생명의 지침을 해독하는 데 도움을 줄 미래를 향한 구체적인 발걸음으로 남아 있습니다.

기술 요약: 하드웨어 한계를 넘어 실제 과학적 워크로드를 위한 양자 최적화 확장

문제 정의
게놈 조립, 특히 롱 리드(long-read) 시퀀싱 데이터의 de novo 조립은 감염병 감시 및 암 유전체학에서 중요한 응용 분야를 가진 게놈학의 근본적인 과제입니다. 이 작업은 파편화된 리드로부터 완전한 게놈을 재구성하는 과정을 포함하며, 이는 종종 오버랩 그래프(overlap graph) 상의 대규모 조합 최적화 문제로 모델링됩니다. 기존의 고전적 알고리즘(예: Unicycler)은 휴리스틱 그래프 단순화에 의존하지만, 복잡하고 반복적이며 노이즈가 많은 데이터셋에 대해서는 확장성과 전역적 최적성 측면에서 한계에 직면합니다.

양자 컴퓨팅은 양자 근사 최적화 알고리즘(QAOA) 및 양자 어닐링(Quantum Annealing)과 같은 알고리즘을 통해 이러한 복잡한 탐색 공간을 탐색하는 데 잠재적인 이점을 제공할 수 있습니다. 그러나 실제 배포는 다음과 같은 잡음이 있는 중간 규모 양자(NISQ) 하드웨어의 제약으로 인해 심각하게 제한됩니다:

큐비트 수: 실제 조립 그래프는 수천 개의 변수를 필요로 하는 경우가 많으며, 이는 현재 장치(예: IBM의 ibm_torino, 133 큐비트)의 큐비트 수를 훨씬 초과합니다.
연결성 및 노이즈: 높은 오류율과 제한된 큐비트 연결성은 많은 2-큐비트 게이트를 포함하는 깊은 회로를 필요로 하며, 이는 상당한 오류 누적과 차선적인 솔루션으로 이어집니다.
정식화 확장성: 조립 문제를 이차 무제약 이진 최적화(QUBO) 형식으로 인코딩하면 이진 변수의 수가 급격히 폭발하여 직접적인 임베딩이 불가능해집니다.
제약 조건 처리: 유효한 경로, 분기 없음과 같은 엄격한 생물학적 제약 조건을 무제약 QUBO 정식화 내에서 무거운 페널티 항 없이 완벽하게 강제하기는 어렵습니다. 이는 유효하지 않거나 생물학적으로 타당하지 않은 조립 결과를 초래할 수 있습니다.

방법론
저자들은 **해밀토니안 자동 분해 최적화 프레임워크(HADOF)**와 QUBO 기반의 조립 문제 정식화를 결합한 양자 보조 게놈 조립 파이프라인을 제안합니다. 이 워크플로우는 클래식 Unicycler 어셈블러의 그래프 레이아웃 최적화 단계를 양자 접근 방식으로 대체합니다.

데이터 및 전처리: 본 연구는 Pseudomonas aeruginosa 게놈(약 7.1 Mbp)에 대한 실제 Oxford Nanopore Technology(ONT) 롱 리드 시퀀싱 데이터를 활용합니다. 원시 리드는 Minimap을 사용하여 오버랩을 식별하고, Miniasm을 사용하여 스트링 그래프(string graph)를 구축하는 방식으로 처리됩니다. 524개의 노드와 2,313개의 유향 에지를 포함하는 이 그래프가 입력값이 됩니다.
QUBO 정식화: 순열 행렬(permutation-matrix) 정식화(변수 $N^2$ $N^{2}$ 개 필요) 대신, 저자들은 에지 기반 QUBO 정식화를 채택합니다. 이는 변수의 수를 에지의 수( $M = |E|$ $M = ∣ E ∣$ )로 줄여줍니다. 목적 함수는 다음을 포함합니다:
- 에지 포함을 보상하는 음의 선형 항.
- 단일 정점에서의 분기(다중 유입 또는 유출 에지)를 억제하는 이차 페널티 항.
  이 정식화는 엄격한 해밀토니안 경로 인코딩이라기보다 완화된 연결성 모델이며, 이를 통해 노이즈가 있는 하드웨어에서 더 높은 유연성을 허용합니다.
HADOF 구현: 하드웨어 한계를 극적으로 극복하기 위해, HADOF를 사용하여 전역 QUBO를 작은 서브 문제(5개 변수 집합)로 분해합니다.
- 프레임워크는 이전 반복에서 얻은 주변 확률( $P(x_i)$ )의 전역 "신념(belief)" 벡터를 유지하며, 이를 통해 후속 서브 문제에서 비활성 변수에 대한 맥락을 제공하면서, 양자 하드웨어(또는 시뮬레이터)를 사용하여 이러한 서브 문제들을 QAOA(구체적으로는 트로터화된 변형인 QAOA-t)를 통해 반복적으로 해결합니다.
- 이 연합 방식(federated approach)을 통해 133-큐비트 장치에서 2,313개의 변수를 가진 문제를 462개의 5-큐비트 회로와 1개의 3-큐비트 회로를 실행함으로써 해결할 수 있습니다.
후처리: 양자 솔버는 결정론적인 단일 출력 대신 확률적 분포를 생성하므로, 클래식 후처리 단계가 필요합니다. 샘플링된 그래프 솔루션에서 위반 사항(예: 차수가 1보다 큰 노드)을 해결하고, 가장 긴 선형 경로를 추출하며, 원형화(circularization)를 수행하기 위해 깊이 우선 탐색(DFS) 알고즘이 적용됩니다. 추출된 시퀀스는 Racon을 통해 정제(polish)되며, QUAST를 사용하여 Unicycler 베이스라인과 비교 평가됩니다.

주요 기여

확장 가능한 양자 조립: 본 연구는 저자들이 아는 바에 따르면, 실제 양자 하드웨어에서 연구된 가장 큰 게놈 조립 그래프(7.1 Mbp)를 입증하였으며, 이는 합성 또는 바이러스 게놈(<5 kbp)에 국한되었던 이전의 개념 증명 연구들을 능가합니다.
HADOF 통합: 대규모 QUBO 문제를 작은 서브 문제로 분할하여 큐비트 및 연결성 제약에도 불구하고 현재의 NISQ 장치에서 실행할 수 있도록 HADOF를 성공적으로 통합했습니다.
경험적 벤치마킹: 본 연구는 양자 접근 방식(HADOF-QAOA), 클래식 시뮬레이티드 어닐링(SA), 그리고 최첨단 클래식 어셈블러인 Unicycler 간의 엄격한 비교를 제공합니다.
지표 분석: 추상적인 QUBO 최적화 지표(목적 점수)와 생물학적 조립 품질(게놈 분율, 중복 비율) 사이의 관계를 평가하는 프레임워크를 구축하였으며, QUBO 점수를 최소화하는 것만으로는 생물학적으로 유효한 조립을 보장할 수 없음을 강조합니다.

결과
연구는 세 가지 솔버(SA, 이상적인 노이즈 없는 시뮬레이터에서의 HADOF-QAOA, 실제 ibm_torino QPU에서의 HADOF-QAOA)를 사용하여 P. aeruginosa 게놈 조립을 평가했습니다.

조립 품질:
- Unicycler (베이스라인): 100% 게놈 분율과 1.0의 중복 비율을 가진 7,139,404 bp의 원형 조립을 달성했습니다.
- SA: 100% 게놈 분율과 1.0의 중복 비율을 가진 조립을 생성하여 Unicycler 베이스라인과 밀접하게 일치했습니다.
- HADOF-QAOA (이상적): 100% 게놈 분율과 1.0의 중복 비율을 달성했으나, Unicycler에 비해 최종 경로에서 더 적은 노드를 사용했습니다.
- HADOF-QAOA (실제 하드웨어): 상당한 노이즈와 더 높은 QUBO 목적 점수(SA의 -992 대비 평균 -370)에도 불구하고, 최상의 샘플링 솔루션은 99.348%의 게놈 분율과 1.0의 중복 비율을 달성했습니다.
최적화 vs. 생물학적 품질:
- 원시 QUBO 목적 점수와 생물학적 조립 품질 사이에는 **디커플링(decoupling, 탈동기화)**이 관찰되었습니다. 낮은 QUBO 점수가 반드시 높은 게놈 분율을 보장하지는 않았으며, 유사한 점수를 가진 솔루션들이 15%에서 100%에 이르는 전체 스펙트럼을 포괄했습니다.
- 노드 보유량: DFS 후처리 후 보유된 노드 수와 게놈 분율 사이에 강한 선형 상관관계가 관찰되었습니다. 200개 이상의 노드를 보유한 솔루션은 일관되게 100%에 근접한 게놈 분율을 달성했습니다.
- 길이로서의 대리 지표: 총 조립된 게놈 길이는 게놈 분율과 선형 관계를 보였으며, 참조 크기(7.1 Mbp)에서 정체되었습니다. 이 길이를 초과하는 조립은 중복 비율이 증가함을 나타내며, 이는 반복 서열로 인한 과잉 조립(over-assembly)을 의미합니다.
솔버 성능: SA는 최적의 참조값 근처에서 가장 조밀한 솔루션 분포를 보였습니다. 실제 하드웨어 결과는 더 파편화되어 있었으나, 분해 전략을 통해 노이즈가 있는 분포로부터 적어도 하나의 고품질 솔루션(99.35% 분율)을 추출할 수 있었습니다.

의의 및 주장
본 논문은 하이브리드 분해 프레임워크가 이론적 양자 최적화와 현재의 하드웨어 제약 사이의 간극을 메울 수 있음을 입증함으로써, 실질적인 양자 생물정보학을 향한 중요한 진전임을 주장합니다.

개념 증명: 실제 하드웨어에서 7.1 Mbp 게놈을 성공적으로 조립한 것은, 분해 및 후처리 전략이 사용된다면 NISQ의 한계에도 불구하고 생물학적으로 타당한 재구성이 가능하다는 것을 증명합니다.
방법론적 통찰: 본 연구는 게놈 조립의 경우, "최선의" 수학적 솔루션(가장 낮은 QUBO 에너지)이 반드시 가장 생물학적으로 정확한 것은 아니라는 점을 강조합니다. 대신, 솔루션 분포의 구조적 패턴(노드 보유 수 및 경로 길이 등)이 조립 품질의 더 나은 지표 역할을 합니다.
미래 방향: 저자들은 현재 하드웨어가 제한적이지만, HADOF 구현과 벤치마킹 파이프라인의 오픈 소스 공개가 향후 연구를 위한 토대를 제공한다고 강조합니다. 향-후 개선 사항으로는 관찰된 구조적 패턴에 기반한 참조 없는 후보 필터링, 로컬 토폴로지를 포함하도록 QUBO 페널티 재정식화, 그리고 게놈 조립 그래프에 특화된 집계 정책 개발 등을 제시합니다.

결론적으로, 속도나 절대적 최적성 측면에서 양자 우위가 아직 실현되지는 않았지만, 하이브리드 프레임워크를 사용하여 실제 하드웨어에서 고품질의 생물학적으로 타당한 조립을 생성할 수 있는 능력은 복잡한 과학적 워크로드를 위한 양자 보조 방법론의 잠재력을 입증합니다.

기술 요약: 하드웨어 한계를 넘어 실제 과학적 워크로드를 위한 양자 최적화 확장

유사한 논문