[논문]그래프 기반 분산 시스템을 이용한 염기 서열 정렬

이준수; 안재균; 여윤구; 노홍찬; 박상현

[국내논문] 그래프 기반 분산 시스템을 이용한 염기 서열 정렬
DNA Sequence Alignment Using a Graph-based Distributed System 원문보기

이준수 (연세대학교 컴퓨터과학과) , 안재균 (연세대학교 컴퓨터과학과) , 여윤구 (연세대학교 컴퓨터과학과) , 노홍찬 (연세대학교 컴퓨터과학과) , 박상현 (연세대학교 컴퓨터과학과)

서열 정렬(sequence alignment)은 유전학(genomic)에서 널리 사용되는 도구 중 하나이다. 최근에는 차세대 시퀀싱 기술(NGS)이 발달함에 따라 데이터의 생산량이 크게 증가했고, 이에 따라 높은 처리량(throughput)을 가진 서열 정렬 알고리즘의 필요성이 증가하였다. 본 논문에서 제안하는 염기 서열 정렬 알고리즘은 시퀀스(sequence)데이터를 그래프 형태로 변형시킨 다음, 마이크로소프트사의 그래프 기반인 메모리(in-memory) 분산시스템(distributed system) 트리니티(Trinity)를 이용해 서열 정렬을 수행한다. 본 논문의 알고리즘은 트리니티 시스템에서 시뮬레이션 염기 데이터를 성공적으로 정렬하였으며, 슬레이브의 개수가 늘어날수록 빠른 속도를 나타내어 확장성(scalability)을 입증했다.

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

(그림 8)슬레이브의 개수가 많을수록 각 슬레이브 에서 처리하는 양이 줄어들기 때문에 정렬 속도가 빨라지는 것을 볼 수 있다. 이는 본 논문의 알고리즘의 확장성을 검증했다. (그림 9)k-mer의 값이 늘어날수록 리드의 조각이 커지기 때문에 변이를 허용한 최적의 리드를 찾을 수 없어, sensitivity는 낮아지고, 반면 정렬속도는 빨라지는 것을 알 수 있다.

제안 방법

중복(duplication)으로 인해 최적의 정렬 결과를 찾기 위해서는 많은 계산량이 필요하였다. 이 때문에 기존의 알고리즘들은 최적의 정렬 결과를 찾는 대신, 고유의 휴리스틱을 적용하여 높은 처리량을 획득하였다. 그러나 이러한 접근 방법은 필연적으로 정확도와의 트레이드오프 (trade-off)를 갖게 되며, 분산 처리 기술의 발전 등 컴퓨팅파워가 계속 발전함에 따라 이러한 접근 방법을 반드시 따를 필요도 없게 되었다.
다음으로 참조 시퀀스에 정렬된 쿼리의 정렬 위치를 조합·연결하여 각 트림마다 참조 시퀀스에 연속적으로 매칭된 쿼리의 총 길이를 비교한다.
쿼리 중 첫 번째 노드의 정렬 위치를 탐색할 때에는 노드 아이디(Cell ID)(그림 3)를 기반으로 구축된 해시 인덱스를 이용하며, 이때의 탐색 속도는 O(1) 이다. 첫 번째 노드의 탐색이 성공하면 해당 노드에 저장되어 있는 이웃 정보와 다음 k-mer의 시퀀스와 비교한다. 이와 같은 방법(그림 6)으로 한 개의 쿼리에 해당하는 3개의 k-mer가 모두 매칭되면 중첩되지 않게 다음 쿼리를 준비하고, 매칭되지 않을 경우에는 일부 시퀀스의 중첩을 허용하며 다음 쿼리를 준비한다.
실험을 위한 염기 서열 데이터는 Samtool[7]로 생성된 시뮬레이션 리드를 이용했다. 분산 처리 시스템의 성능을 활용하기 위해 필수적인 알고리즘의 확장성(scalability)과 ppv, sensitivity를 검증하기 위해 각각 슬레이브 개수와 k-mer의 수를 조절했다.
대용량의 NGS리드가 범용화 됨에 따라, 최적의 정렬 결과를 찾기 위해서는 많은 계산량이 필요하게되었다. 본 논문에서는 기존 시퀀스 데이터를 일정 길이로 분할한 뒤, 분할된 염기 서열을 정점으로, 정점 간의 from-to 정보를 간선으로 갖는 그래프 형태로 변환하였으며, 이를 Microsoft사에서 개발한 그래프 분산처리 시스템인 트리니티에 적용하여 염기서열 정렬 문제를 다뤘다. 트리니티는 그래프 형태의 데이터를 디스크에 기록하는 과정 없이 메모리 수준에서 해석하기 때문에 높은 처리 속도를 제공할 수 있다.

대상 데이터

실험을 위한 염기 서열 데이터는 Samtool[7]로 생성된 시뮬레이션 리드를 이용했다. 분산 처리 시스템의 성능을 활용하기 위해 필수적인 알고리즘의 확장성(scalability)과 ppv, sensitivity를 검증하기 위해 각각 슬레이브 개수와 k-mer의 수를 조절했다.

이론/모형

본 논문에서는 Microsoft사에서 개발한 그래프 분산처리 시스템인 트리니티[4,5]를 이용하여 염기서열 정렬 문제를 다룬다. 트리니티는 메모리 기반의 분산처리 시스템으로서, 그래프 형태의 데이터를 디스크에 기록하는 과정 없이 메모리 수준에서 해석하기 때문에 높은 처리 속도를 제공한다.
다음으로 참조 시퀀스에 정렬된 쿼리의 정렬 위치를 조합·연결하여 각 트림마다 참조 시퀀스에 연속적으로 매칭된 쿼리의 총 길이를 비교한다. 그 중 정렬된 염기 서열이 가장 긴 매칭을 최적의 위치로 선정하고 Smith-Waterman Algorithm[6]을 이용해 점수를 계산했다. 이렇게 각 슬레이브의 최적의 위치를 프록시에서 통합해 최종결과를 클라이언트로 전송하고 클라이언트에서는 SAM[7] 형태로 최종 결과를 확인 할 수 있다.

성능/효과

트리니티는 그래프 형태의 데이터를 디스크에 기록하는 과정 없이 메모리 수준에서 해석하기 때문에 높은 처리 속도를 제공할 수 있다. 시뮬레이션 리드를 이용하여 확장성을 검증하였으며, k-mer가 커질수록 더 빠른 결과를 얻을 수 있는 대신 확장성sensitivity가 낮아지는 것을 알 수 있다.

후속연구

본 논문은 시퀀스 데이터를 그래프 형태로 변환해 그래프 기반 인 메모리 분산시스템에 접목하였으나, 아직 많은 부분에서 추후 연구가 필요하다. 참조 시퀀스에 전처리를 진행해 정렬비용을 줄이고, 정렬 시의 치환, 삽입, 결손.

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증

[국내논문] 그래프 기반 분산 시스템을 이용한 염기 서열 정렬
DNA Sequence Alignment Using a Graph-based Distributed System 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper

문제 정의

제안 방법

대상 데이터

이론/모형

성능/효과

후속연구

이 논문을 인용한 문헌

관련 콘텐츠

원문 보기

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

연합인증

[국내논문] 그래프 기반 분산 시스템을 이용한 염기 서열 정렬 DNA Sequence Alignment Using a Graph-based Distributed System 원문보기

초록 용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

AI 본문요약 엑셀 다운로드 AI-Helper

문제 정의

제안 방법

대상 데이터

이론/모형

성능/효과

후속연구

이 논문을 인용한 문헌

관련 콘텐츠

원문 보기

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

[국내논문] 그래프 기반 분산 시스템을 이용한 염기 서열 정렬
DNA Sequence Alignment Using a Graph-based Distributed System 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper