💻 bioinformatics

RosaSeed: Faster and Accurate Short Read Alignment Using a Configurable Seeding Strategy

RosaSeed는 BWA-MEM2, Minimap2, ERT와 같은 최신 도구들과 비교하여 정확도는 대등하거나 더 우수하면서도 유연한 메모리-성능 트레이드오프를 제공하며, 시딩(seeding) 과정과 전체 정렬 처리량을 크게 가속화하는 설정 가능한 숏 리드 정렬 알고리즘입니다.

원저자: Gandhi, S. M., Cockburn, B. F.

게시일 2026-09-26

📖 5 분 읽기🧠 심층 분석

CC BY 4.0

원저자: Gandhi, S. M., Cockburn, B. F.

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

인간의 게놈은 A, C, G, T라는 단 네 가지 문자로 쓰인 화학적 코드인 방대한 지시서 라이브러리입니다. 이 코드가 어떻게 작동하는지 이해하거나, 질병을 유발하는 미세한 오타를 찾아내기 위해서, 과학자들은 먼저 사람의 세포로부터 DNA를 읽어내야 합니다. 현대의 기계들은 긴 DNA 가닥을 수백만 개의 아주 작은 조각으로 잘게 쪼개고, 각 조각에 담긴 문자의 서열을 읽은 다음, 이 조각들이 거대한 원래의 게놈 책 중 어디에 속하는지를 알아내려 노력합니다. 이 조각들을 다시 맞추는 과정은 정렬(alignment)이라고 불립니다. 이는 현대 의학과 생물학의 근본적인 단계이지만, 동시에 거대한 계산적 도전이기도 합니다. 이 작업을 수행하는 컴퓨터는 30억 개의 문자로 이루어진 참조 도서와 수십억 개의 짧은 서열을 비교해야 하며, 이는 표준 장비로는 몇 시간 또는 며칠이 걸릴 수 있는 작업입니다. 병목 현상은 종 데이서 컴퓨터가 어디를 살펴보기 시작할지 알려주는 초기 일치 항목, 즉 '씨앗(seeds)'을 찾는 바로 첫 번째 단계에서 자주 발생합니다.

앨버타 대학교의 연구진은 정확도를 잃지 않으면서 이 초기 검색 속도를 높이는 RosaSeed라는 새로운 방법을 개발했습니다. 그들의 연구는 이 분야의 오래된 트레이드오프(절충 관계)를 해결합니다. 기존 방식들은 빠르지만 엄청난 양의 컴퓨터 메모리를 필요로 하거나, 혹은 정확하지만 느렸습니다. 연구진은 컴퓨터가 참조 도서를 읽는 방식을 바꿈으로써, 기존의 가장 빠른 고성능 도구들보다 메모리를 적게 사용하면서도 검색을 훨씬 더 빠르게 만드는 방법을 찾아냈습니다. 그들은 단순히 DNA 문자를 하나씩 확인하는 대신, 문자를 쌍이나 삼중조로 그룹화하여 컴퓨터가 앞서 건너뛰며 각 단계에서 더 많은 정보를 처리할 수 있도록 했습니다. 또한, 이미 커버된 영역을 확인하는 데 시간을 낭비하는 대신, 초기 검색에서 일치 항목을 놓친 DNA 부분에만 추가적인 노력을 집중하는 스마트한 전략을 도입했습니다.

그들 혁신의 핵심은 다양한 유형의 컴퓨터에 맞춰 조정할 수 있는 구성 가능한 프레임워크입니다. 표준 싱글 코어 프로세서에서 그들이 권장하는 설정은 정확도의 골드 스탠다드로 여겨지는 널리 사용되는 BWA-MEM2 소프트웨어보다 초기 검색 단계에서 거의 4배 더 빠른 것으로 나타났습니다. 원시 데이터에서 최종 정렬 보고서에 이르기까지의 총 시간을 측정했을 때도, 이 새로운 방법은 여전히 거의 4배 더 빨랐습니다. 결정적으로, 이러한 속도는 메모리 사용량의 손실 없이 이루어졌습니다. 이 새로운 시스템은 거대한 사전 계산 트리(pre-computed trees)에 의존하는 다른 빠른 방법들보다 약 25% 적은 메모리를 요구했습니다. 연구진은 시뮬레이션된 데이터(정답을 알고 있는 데이터)와 실제 인간 DNA 샘로 모두 소프트웨어를 테스트했습니다. 이 테스트에서 새로운 방법은 기존의 최고 도구들과 거의 동일한 정확도 수준을 유지하며, DNA 조각들을 올바른 위치에 배치하고 정확한 유전적 변이를 식별해 냈습니다.

왜 이것이 중요한지 이해하려면 현재 검색이 어떻게 이루어지는지를 보아야 합니다. 전통적인 소프트웨어는 참조 게놈을 거대한 인덱스처럼 취급하여, DNA 조각의 모든 문자를 인덱스와 대조하여 일치 여부를 확인합니다. 이 과정이 느린 이유는 컴퓨터가 데이터가 도착하기를 기다리며 메모리 안을 끊임없이 돌아다녀야 하기 때문입니다. 새로운 방법인 RosaSeed는 게임의 규칙을 바꿉니다. 그것은 DNA 문자를 더 큰 블록으로 인코딩하여, 컴퓨터가 인덱스를 통해 더 큰 발걸음을 내디딜 수 있게 합니다. 마치 사람이 사전에서 특정 단어를 찾는 것과 같습니다. 기존 방식은 단어의 모든 글자를 하나하나 사전과 대조하는 것이라면, 새로운 방식은 두 개 또는 세 개의 글자를 한 번에 확인하여 사전의 넓은 구역을 훨씬 더 빠르게 건너뛰는 것입니다. 데이터를 그룹화하는 방식의 이 간단한 변화는 컴퓨터가 수행해야 하는 단계의 수를 줄여, 필요한 시간을 획기적으로 단축합니다.

하지만 더 큰 발걸음을 떼는 것은 시작점이 약간 어긋날 경우 컴퓨터가 일치 항목을 놓치는 결과를 초래할 수 있습니다. 이를 해결하기 위해 연구진은 두 번째 지능형 계층을 추가했습니다. 만약 초기 빠른 검색이 빈틈(DNA 조각 중 매칭되지 않은 부분)을 남긴다면, 그들은 목표를 정밀하게 타격하는 접근법을 사용합니다. 그들은 전체 조각을 다시 확인하는 대신, 빈 공간에 특정 체크포인트를 배치하고 그곳에서 일치 항목을 찾습니다. 이는 빠른 단계의 속도가 중요한 정보를 놓치는 비용으로 이어지지 않도록 보장합니다. 이 시스템은 유연합니다. 메모리가 많은 강력한 컴퓨터에서 최대 속도를 내기 위해 더 큰 글자 블록을 사용하도록 조정할 수도 있고, 구형 기기를 위해 메모리 사용량을 줄이도록 튜닝할 수도 있으며, 이 모든 과정에서 최종 결과의 정확성을 유지합니다.

연구진은 minibwa와 Strobealign이라는 도구를 포함한 최근의 정렬 속도 향상 시도들과도 이 방법을 테스트했습니다. 24코어를 갖춘 현대적인 워크스테이션에서 그들의 최적화된 버전인 miniRosaSeed는 단일 프로세싱 스레드를 사용할 때 minibwa보다 2배 이상 빨랐으며, Strobealign보다는 현저히 빨랐습니다. 아마도 더 중요한 점은, 이 방법이 두 도구보다 더 정확하여 DNA 조각의 올바른 위치를 더 자주 찾아냈다는 것입니다. 게놈 분석의 세계에서 속도는 가치 있는 것이지만, 정확도는 타협할 수 없는 필수 조건입니다. 실수를 저지르는 빠른 도구는 잘못된 의학적 진단이나 결함이 있는 과학적 결론으로 이어질 수 있습니다. 이 새로운 방법은 과거에는 달성하기 어려웠던 조합인, 빠르면서도 정밀한 성능을 동시에 구현해 냈습니다.

이 연구의 영향은 단순히 시간을 절약하는 것을 넘어 확장됩니다. 연구진은 테스트 중에 컴퓨터가 소비한 에너지를 측정했으며, 새로운 방법이 기존의 느린 도구들보다 훨씬 적은 전기를 사용한다는 것을 발견했습니다. 컴퓨터가 작업을 훨씬 더 빨리 끝내기 때문에, 풀 파워로 실행되는 시간이 줄어들기 때문입니다. 게놈 연구가 수천 개가 아닌 수백만 개의 게놈을 분석하는 방향으로 나아감에 따라, 이러한 에너지 사용량의 감소는 비용과 환경적 영향 측면에서 매우 중요한 요소가 됩니다. 이 소프트웨어는 기존 도구들의 '드롭인 교체(drop-in replacement)'가 가능하도록 설계되었습니다. 즉, 과학자들이 이미 신뢰하고 있는 기존의 다운스트림 분석 파이프라인과 함께 그대로 사용할 수 있다는 뜻입니다. 이러한 호환성은 연구 워크플로우를 완전히 개편할 필요 없이 속도 향상의 이점을 즉시 채택할 수 있도록 보장합니다.

연구는 또한 기술의 한계를 탐구했습니다. 연구진은 이 방법이 표준 DNA 조각에 가장 잘 작동하며, 현재는 일부 시퀀싱 데이터에서 흔히 나타나는 모호한 문자(ambiguous letters)를 포함하는 조각들을 제거한다고 언급했습니다. 그들은 향에 업데이트를 통해 이를 해결할 계획입니다. 또한, 읽기 어려운 반복 영역이 포함된 완전하고 고품질인 인간 게놈 참조 모델에서도 소프트웨어를 테스트했습니다. 이 어려운 영역에서도 새로운 방법은 우수한 성능을 보여주었으며, 이는 가장 까다로운 응용 분야에도 견고하게 대응할 수 있음을 시사합니다. 소프트웨어의 소스 코드는 공개되어 있어, 다른 과학자들이 결과를 검증하고 이 연구를 바탕으로 발전시킬 수 있습니다.

결국, 이 작업은 게놈 분석을 더욱 효율적으로 만드는 데 있어 중요한 진전을 의미합니다. 일치 항목을 찾는 방식을 재고하고 빈틈을 메우는 스마트하고 적응적인 계층을 추가함으로써, 연구진은 기존의 최고 도구들만큼 정확하면서도 더 빠르고 에너지 효율적인 도구를 만들어 냈습니다. 이를 통해 과학자들은 더 많은 데이터를 더 짧은 시간에 처리할 수 있으며, 이는 개인 맞춤형 의료와 인간 생물학에 대한 이해를 가속화할 잠재력을 가집니다. 이 프로젝트의 성공은 성숙하고 확고하게 자리 잡은 알고리즘 분야에서도, 결과의 품질을 희생하지 않으면서 성능을 극적으로 개선할 수 있는 혁신의 여지가 여전히 존재함을 보여줍니다.

기술 요약: RosaSeed: 구성 가능한 시딩 전략을 이용한 빠르고 정확한 숏 리드 정렬

문제 정의
BWA-MEM2와 같이 널리 사용되는 기존의 숏 리드 DNA 정렬 알고리즘은 실행 시간의 상당 부분(약 40%)을 시드 생성(seed generation)에 할애합니다. 이 단계는 일반적으로 FM 인덱스 기반의 역방향 탐색(backward search)에 의존하며, 이는 참조 유전체를 염기 단위로 순차적으로 탐색해야 합니다. 이 과정은 불규칙한 메모리 액세스 패턴을 생성하여 현대의 고밀도 메모리 시스템에서도 캐시 지역성(cache locality)을 저해하고 심각한 지연 시간 병목 현상을 초래합니다. 기존의 시딩 가속 시도들은 트레이드오프를 수반합니다. 예를 들어, FM 인덱스를 대신하여 대규모 사전 계산 구조(예: Enumerated Radix Tree/ERT)를 사용하는 방식은 메모리 점유율을 크게 증가시키며, 서브샘플링 전략(예: Minimap2, Strobealign)은 메모리는 줄일 수 있으나 유익한 매치를 놓칠 수 있어 정확도를 낮출 수 있습니다. 또한, 최근의 지연 시간 은닉(latency-hiding) 접근 방식(예: minibwa)은 속도는 개선하지만 정렬 정확도나 다운스트림 일관성을 희생할 수 있습니다. 따라서 높은 메모리 비용을 발생시키지 않으면서도 FM 인덱스 탐색을 실질적으로 가속화하고, 정렬 품질 및 기존 파이프라인과의 호환성을 유지할 수 있는 정렬 방법이 필요합니다.

방법론
RosaSeed는 BWA-MEM2의 시딩 커널을 대체하면서, 그 검증된 체이닝(chaining) 및 밴디드 스미스-워터맨(Banded Smith–Waterman, BSW) 확장 파이프라인으로 후보 시드를 직접 전달하도록 설계된 구성 가능한 시딩 프레임워크입니다. 본 방법론은 다음과 같은 몇 가지 핵심 혁신을 포함합니다:

s-Base FM 인덱스 및 파생 참조: RosaSeed는 각 심볼이 $s \ge 1$ 개의 연속된 DNA 염기를 인코딩하는 radix- $4^s$ 알파벳에서 작동합니다 ( $s=1, 2, \text{ 또는 } 3$ ). 모든 가능한 시드 경계를 커버하기 위해, 참조 유전체는 정방향 및 역상보(reverse-complement) 가닥 모두에서 파생된 $s$ 개의 위상 변이(phase-shifted) 심볼 시퀀스를 결합하여 구축됩니다. 이를 통해 역방향 탐색 확장 단계를 $s$ 배만큼 줄입니다.
점프 테이블(Jump Table, JT) 가속: 사전 계산된 점프 테이블은 가능한 모든 $k$ -mer 접두사(prefix)에 대한 접미사 배열(suffix array, SA) 구간을 저장합니다. RosaSeed는 $k$ 번의 FM 인덱스 단계를 수행하는 대신 단 한 번의 JT 조회를 통해 시드 생성을 시작하여, 발생 배열(occurrence array) 액세스 횟수를 크게 줄입니다. 고유 히트(unique hits)는 SA 압축 해제 없이 즉시 해결됩니다.
다단계 시딩 전략:
- Phase A (주요 단계): 오른쪽에서 왼쪽으로 진행되는 가닥 인식형(strand-aware) 불연속 피벗 스윕(disjoint pivot sweep)을 수행합니다. JT와 $s$ -base 역방향 확장을 사용하여 가능한 가장 긴 시드를 찾습니다. 체이닝에 유익하지 않을 가능성이 높은 과다하게 빈번한 시드를 억제하기 위해 선택적 SA 구간 캡( $T$ )을 사용합니다.
- Phase B (고정 피벗 보완 단계): 추가적인 시드를 찾기 위해 균일하게 배치된 소수의 고정 피벗을 평가하며, SA 구간 너비에 기반한 조기 종료 기준을 사용합니다.
- Phase C (적응형 간극 지향 보완 단계): Phase A에서 남겨진 정렬되지 않은 간극(gap)을 식별하고, 누락된 시드를 복구하기 위해 해당 간극 내에 적응적으로 피벗을 배치합니다. 이 전략은 고정 피벗보다 계산 효율이 높으며, 커버되지 않은 영역만을 타겟팅합니다.
프리페치 스케줄링(Prefetch Scheduling): FM 인덱스의 캐시 미스 지연 시간을 숨기기 위해, RosaSeed는 여러 리드(read)의 확장 단계를 인터리빙(interleaving)하는 코루틴 기반 스케줄러를 채택합니다. 이는 minibwa의 지연 시간 은닉 전략을 모방하되 RosaSeed의 다단계 구조에 맞게 조정된 것으로, 다음 리드로 넘어가기 전에 다음 발생 배열 블록에 대한 소프트웨어 프리페치를 발행합니다.
사전 체인 필터링(Pre-Chain Filtering): 선택적 휴리스틱을 통해 체이닝 단계에 진입하기 전 낮은 가치의 싱글톤 시드(짧거나 매우 빈번한 시드)를 억제함으로써, 정확도에 큰 영향을 주지 않으면서 다운스트림 계산 부하를 줄입니다.
구성 가능한 메모리-성능 트레이드오프: 본 프레임워크는 가변적인 $s$ -base 인코딩, 다양한 SA 압축 계수, 선택 가능한 보완 시딩 전략(Phase B 또는 C)을 지원하여, 사용자가 메모리 제한적이거나 고처리량이 요구되는 환경에 맞춰 알고리즘을 튜닝할 수 있도록 합니다.

주요 기여

s-Base FM 인덱스: 표준 FM 인덱스 역방향 탐색 로직과의 호환성을 유지하면서 다중 염기 조회를 가능하게 하는, 위상 변이된 참조 유전체로부터 파생된 일반화된 $s$ -base 인덱스를 도입했습니다.
구성 가능한 시딩 프레임워크: 점프 테이블, 다단계 시딩(주요 스윕 및 적응형 간극 지향 또는 고정 피벗 보완 전략), 그리고 사전 체인 필터링을 통합한 새로운 파이프라인을 제시했습니다.
드롭인 교체(Drop-in Replacement): RosaSeed는 기존 BWA-MEM2의 체이닝 및 정렬 확장 모듈과 원활하게 통합되어, 다운스트림 파이프라인의 수정 없이 사용할 수 있습니다.
성능 최적화: 메모리 지연 시간을 숨기기 위한 코루틴 기반 프리페치 스케줄링과 실행 시간-메모리 트레이드오프를 최적화하기 위한 구성 가능한 파라미터를 구현했습니다.
포괄적 평가: 시뮬레이션 및 실제 데이터셋(T2T-CHM13v2.0 참조 유전체 포함)을 사용하여 BWA-MEM2, ERT, ERT2, Minimap2, Bowtie2, minibwa, Strobealign을 대상으로 광범위한 벤치마킹을 수행했습니다.

결과
ERR 데이터셋에 대해 BWA-MEM2(압축되지 않은 접미사 배열 사용)를 대상으로 한 단일 스레드 실행 평가 결과는 다음과 같습니다:

속도: 권장되는 RosaSeed 설정은 시드 처리에서 13.06배의 속도 향상을, 전체 fastq-to-SAM 시간에서 3.85배의 속도 향상을 달 나타냈습니다.
메모리: RosaSeed는 피크 메모리로 49.61 GB를 사용하였으며, 이는 ERT 및 ERT2보다 약 25% 적은 수준이면서도 대등한 정확도를 유지했습니다.
정확도: RosaSeed는 **98.52%**의 표준 정확도, **99.97%**의 구조적 정확도, **99.87%**의 서열 일관성 정확도를 유지하여 BWA-MEM2와 매우 유사한 성능을 보였습니다.
최신 기술(State-of-the-Art)과의 비교:
- ERT 대비: 시드 처리에서 3.96배, 전체 시간에서 2.48배 더 빠름.
- ERT2 대비: 시드 처리에서 1.2배, 전체 시간에서 1.44배 더 빠름.
- Minimap2 대비: 시드 처리에서 4.82배, 전체 시간에서 3.31배 더 빠름.
- Bowtie2 대비: 시드 처리에서 33.24배, 전체 시간에서 10.83배 더 빠름.
- minibwa 대비 (24코어 Zen 3 워크스테이션 기준): 속도 최적화된 miniRosaSeed 설정은 단일 스레드 실행 시 minibwa 대비 fastq-to-SAM 속도가 2.12배 빨랐으며, 2.58% 더 높은 표준 정확도와 4.2배 적은 오정렬(misalignment)을 기록했습니다. miniRosaSeed는 26 스레드까지 minibwa보다 빠르고 정확했습니다.
- Strobealign 대비: miniRosaSeed는 2.18배 더 빠르며 3.1% 더 높은 표준 정확도를 보였습니다.
다운스트림 일관성: HG002 데이터를 사용한 DeepVariant 기반 변이 호출 분석 결과, RosaSeed는 BWA-MEM2/ERT와 매우 일치하는 결과를 생성했습니다 (SNP 및 Indel F1 점수 각각 0.0003 및 0.00015 이내). RosaSeed는 BWA-MEM2/ERT에 비해 보조 정렬(supplementary alignments)을 28.6% 감소시켰습니다.
에너지 효율: 단일 스레드 실행 시 RosaSeed는 BWA-MEM2보다 샘플당 약 3.5배 적은 에너지를 소비했습니다.

의의
본 논문은 다운스트림의 체이닝이나 로컬 정렬 단계를 수정하지 않고도, 시딩 최적화만으로 상당한 숏 리드 정렬 가속화를 달성할 수 있음을 입증합니다. 메모리 효율, 속도, 정확도의 균형을 맞추는 구성 가능한 프레임워크를 도입함으로써, RosaSeed는 BWA-MEM2의 시딩 단계에 대한 "드롭인" 대안을 제공합니다. 이는 기존 접근 방식들이 직면했던 속도, 메모리 점유율, 정확도 사이의 근본적인 갈등을 해결하며, 다양한 컴퓨팅 환경에 적합한 다수의 운영 지점(operating points)을 제공합니다. 본 연구 결과는 제안된 구성 가능한 시딩 전략이 지연 시간 은닉 프리페칭과 결합될 때, 기존의 빠른 정렬 도구들(minibwa 및 Strobealign 포함)보다 정확도-속도 트레이드오프 측면에서 우수한 성능을 보이면서도, 확립된 BWA-MEM2의 높은 정확도와 파이프라인 호환성을 유지할 수 있음을 시사합니다.

유사한 논문