suffix tree 2

Genome-scale 서열 분석

Suffix tree는 생물학 서열 분석에 있어서 기본적인 데이터 구조 중 하나이다. 이전 블로그에서도 잠깐 언급했듯이 GPU를 이용해서 서열 매칭 작업을 병렬화 한다는 내용을 잠깐 언급한적이 있는데,,,, 이게 좀,,, Fast Exact String Matching on the GPU와 High-throughput sequence alignment using Graphics Processing Units(MUMmerGPU)는 모두 Michael C. Schatz가 저자로써, 모두 생물학 서열에 있어서 GPU를 이용한(GPU를 사용하지 않는 MUMmer(Maximal Unique Matching)) Suffix tree 알고리즘을 병렬화하는 내용이다. 간단하게 보면, 우선 기준이 되는 Reference..

Bioblogs 2008.07.22

생물정보학에서의 서열 유사성 검색 - GPU와 Suffix Tree를 이용한 병렬처리

생물정보학에서의 서열 유사성 검색의 중요성은 굳이 설명하지 않아도 다들 이해하시리라 믿는다. 여기서는 String Match라는 관점에서 서열 데이터(text)로 부터 주어진 서열 찾는 Suffix Tree 알고리즘과 이 알고리즘을 GPU를 통해서 구현하는 방법에 대해서 알아보고자 한다. GPU(Graphics Processing Unit)는 무엇인가? 간단하게 말하면 컴퓨터에 있는 그래픽 카드의 CPU라고 생각하면 될것이다. 요즘 게임들은 3D와 실사와 정말 유사한 화면을 제공하는데, 이러한 것들을 CPU가 아닌 그래픽 카드의 GPU에서 처리하게 함으로써 좀 더 빠르게 게임을 할 수 있는 환경을 제공하는 것이다. 그런데 이 GPU의 아키텍처의 특성상 이것만 하기에는 너무 아깝기 때문에 범용적인 수치연산..

Bioblogs 2008.03.26