Chương 1 GIỚI THIỆU ĐỀ TÀI 1.1 Tổng quan vấn đề Ngày nay, đứng trước nguy cơ đối mặt với những vấn đề sức khỏe nghiêm trọng, con người ngày càng đẩy mạnh nghiên cứu đối với các vấn đề liên quan đến sinh học và công nghệ gen nhằm tìm ra những giải pháp cho các vấn đề trên. Trong những năm qua, với sự trợ giúp của những ngành khoa học khác, ngành sinh học và công nghệ gen đã gặt hái được nhiều thành tựu đáng kể, đặc biệt là sự chuyển dịch từ cấu trúc của các đa phân tử sinh học sang phân tích trình tự sinh học. Theo dữ liệu về các trình tự sinh học có tại National Center for Biotechnology Information (NCBI) của Mỹ, đã có tới 120GB chứa khoảng 9 Gbase (Gbase hay còn gọi là Giga base pairs là một cặp bazơ gồm 2 nucleotid đối ngược nhau trong chuỗi xoắn kép) [1]. Việc phân tích, tìm kiếm, so sánh,.
trong dữ liệu gen lớn như vậy đòi hỏi nhiều thời gian cũng như tính chính xác trong quá trình thực thi, do đó việc phát triển các giải thuật so sánh tuần tự trong lĩnh vực sinh học là khá quan trọng. Qua đó ta thấy lĩnh vực máy tính cũng góp phần không nhỏ đối với lĩnh vực sinh học. Bằng việc sử dụng các công cụ hỗ trợ từ tin học, công việc nghiên cứu trở nên dễ dàng và đảm bảo được sự chính xác cao, từ đó giúp cho công tác nghiên cứu về sinh học đặc biệt là công nghệ gen.2 Động lực nghiên cứu Sắp xếp trình tự gen mang đến nhiều lợi ích: • Phát hiện được bệnh tế bào máu hình lưỡi liềm [2]. • Thiết kế các peptide kháng thể [3].
• Xét nghiệm di truyền [4]. • Xác định quan hệ tiến hóa loài [4]. Trong đề tài này, chúng tôi chọn GPU (thay vì chọn nền tảng FPGA, Multi- core, .) để tăng tốc thuật toán xếp trình tự gen bởi GPU có nhiều core nên phù hợp để thử nghiệm. Mặt khác, quá trình thiết lập môi trường thử nghiệm dễ dàng và ngôn ngữ được sử dụng để lập trình GPU (cụ thể là dùng CUDA) là C/C++.
Tuy nhiên, việc sử dụng ngôn ngữ C/C++ lập trình cho GPU không hề đơn giản so với lập trình tuần tự đơn thuần. Nói cách khác, việc tiếp cận và hiện thực song song hóa một chương trình là cả một thử thách mới đối với chúng tôi khi tiếp cận vấn đề này. Hiện nay có nhiều giải thuật xếp trình tự gen như BWA-MEM [5], Bowtie2 [6], Cushaw2 [7], GEM [8], AGILE [9], STELLR [10],. và mỗi giải thuật đều có những ưu điểm và nhược điểm riêng.
Tuy nhiên trong đề tài này, chúng tôi quyết định chọn giải thuật BWA- MEM, vì đó là một giải thuật so trùng và sắp hàng một cách chính xác, nhanh chóng trong trình tự sinh học với độ dài genome lớn, cân bằng tốt (scale well) đối với vộ genome lớn và đặc biệt là mã nguồn mở (điều này dễ dàng trong việc tìm hiểu và hiện thực giải thuật trên nền tảng GPU).3 Đóng góp của đề tài Đề tài có các đóng góp sau. Phân tích cấu trúc chương trình BWA-MEM. Tăng tốc chương trình BWA-MEM trên nền tảng GPU.4 Cấu trúc của luận văn Luận văn được chia thành 8 chương theo cấu trúc như sau: 1. Giới thiệu tổng quan các vấn đề trong Sinh-Tin học, động lực nghiên cứu, đóng góp của đề tài và trình bày cấu trúc luận văn.
Các kiến thức nền tảng được trình bày trong giải thuật BWA-MEM như: Burrows-Wheeler Transform (BWT), Full-text index Minute-space (FM- index), giải thuật Smith-Waterman (SW) và kiến thức nền tảng GPU, CUDA. Phân tích cấu trúc chương trình BWA-MEM. Tìm hiểu các công trình liên quan đến đề tài, quan sát và nhận định. Trình bày ý tưởng và cách thức hiện thực chương trình trên GPU, 6.
Trình bày kết quả thực nghiệm, đánh giá và phân tích kết quả. Trình bày về kết luận vấn đề các giới hạn và công việc tiếp theo của đề tài trong tương lai. Tài liệu tham khảo. 3 Chương 2 KIẾN THỨC NỀN TẢNG Chương 2 trình bày tổng quan các kiến thức về kỹ thuật Burrows-Wheeler Transform (BWT), Full-text Minute-space (FM-index), giải thuật Smith-Waterman (SW) và GPU (Graphics Processing Unit).
Đồng thời cũng cấp kiến thức về Burrows-Wheeler Aligner (BWA-MEM) - một trong những giải thuật so trùng và sắp hàng chuỗi với độ dài lớn từ 70bp đến vài megabases. Những kiến thức này đặc biệt quan trọng bởi nó giúp chúng ta biết được cách thức hoạt động của giải thuật BWA-MEM để từ đó thực hiện giải thuật BWA-MEM trên GPU nhằm tăng tốc cho giải thuật BWA-MEM.1 Kiến Thức Nền Tảng Được Sử Dụng Trong BWA-MEM 2.1 Burrows-Wheeler Transform (BWT) Giải thuật được sử dụng trong kỹ thuật nén dữ liệu theo ý tưởng sắp xếp lại các ký tự trong một chuỗi để tạo ra một chuỗi có nhiều các ký tự giống nhau dồn lại với nhau hơn chuỗi ban đầu và có thể chuyển đổi từ chuỗi này lại chuỗi ban đầu. Thuật toán tạo ra chuỗi BWT có thể mô tả như sau với chuỗi abaaba. Ta kí hiệu chuỗi abaaba là T.
Bước 1: Viết thêm vào cuối T một kí tự là $ (đại diện cho con trỏ EOF), xét n+1 hoán vị vòng quanh, ta được: 4 abaaba$ baaba$a aaba$ab aba$aba ba$abaa a$abaab $abaaba Bước 2: Sắp xếp n+1 hoán vị vòng quanh đó theo thứ tự từ điển tạo thành ma trận BWT. $abaaba a$abaab aaba$ab aba$aba abaaba$ ba$abaa baaba$a Bước 3: Viết ra các ký tự cuối của các hoán vị vòng quanh theo đúng thứ tự sau khi đã sắp xếp tạo thành từ mã BWT của T: abba$aa Dưới đây Hình 2.1 sẽ mô tả tổng quan quá trình xây dựng chuỗi BWT.1: Tổng quan xây dựng chuỗi BWT [11] 5 2.2 Chuyển đổi về chuỗi gốc ban đầu: BWT-reversing Xét ma trận BWT (MT ) cột đầu và cột cuối ký hiệu là F và L, đánh thứ tự cho các ký tự ở 2 cột này. T bwt là chuỗi BWT được tạo ra từ MT. MT có tính chất "Last-to-First column mapping" (LF-mapping) nghĩa là sự xuất hiện thứ i của ký tự ở cột cuối cùng (L) tương ứng với sự xuất hiện thứ i của ký tự đó ở cột đầu tiên (F).
Theo [12], LF-mapping có: • C(·) biểu thị mảng chiều dài |Σ| sao cho C[c] chứa tổng số lần xuất hiện của các ký tự trong dữ liệu text có thứ tự từ điển nhỏ hơn ký tự c. LF(·) đại diện cho Last-to-First column mapping bởi vì ký tự T bwt [i] ở cột cuối L của ma trận MT sẽ nằm ở cột đầu F tại vị trí LF(i) và LF(·) cũng cho phép dò ngược chuỗi T. Cụ thể, nếu T[k] = T bwt [i] thì T[k-1] = T bwt [LF(i)]. Dựa vào Hình 2.1 ta có T bwt = "abba$aa".1: Thứ tự của các ký tự trong T bwt 1 2 3 4 5 6 7 T bwt a b b a $ a a • Xây dựng C[c] của T bwt Bảng 2.3: Occ(c,q) của T bwt a b b a $ a a 1 2 3 4 5 6 7 $ 0 0 0 0 1 1 1 a 1 1 1 2 2 3 4 b 0 1 2 2 2 2 2 LF(6) = C(a) + Occ(a,6) = 1 + 3 = 4 => L(6) = F(4) = a2 LF(4) = C(a) + Occ(a,4) = 1 + 2 = 3 => L(4) = F(3) = a1 LF(3) = C(b) + Occ(b,3) = 5 + 2 = 7 => L(3) = F(7) = b1 LF(7) = C(a) + Occ(a,7) = 1 + 4 = 5 => L(7) = F(5) = a3 LF(5) = C($) + Occ($,5) = 0 + 1 = 1 => L(5) = F(1) = $ Ta được chuỗi T = a3 b1 a1 a2 b0 a0 (Hình 2.2: LF-mapping [11] 7 Để chuyển về chuỗi gốc ban đầu, ta đảo ngược chuỗi bắt đầu từ phía phải của chuỗi gốc dò ngược về phía trái.
Cách thực hiện đảo ngược được trình bày như Hình 2. Kết quả thu được như sau: a3 b1 a1 a2 b0 a0 $ = T.3: BWT Reversing [11] Hình 2.4: Minh họa BWT Reversing trực quan [11] 2.3 FM-Index (Full-text index in Minute space) FM-index [13] cho phép tìm kiếm chuỗi con trùng một cách hiệu quả bên trong dữ liệu text. FM-index kết hợp kỹ thuật BWT với một vài cấu trúc dữ liệu phụ trợ để nhằm giảm bộ nhớ thực thi và thực hiện nhanh hơn. 8 Thành phần chính của FM-index bao gồm F (có thể được trình bày rất đơn giản 1 số nguyên cho 1 ký tự) và L (có thể nén được) từ ma trận BWT (Hình 2.
FM-index có khả năng tiết kiệm không gian cần để lưu trữ.5: Thành phần chính của FM-index [11] Truy vấn với FM-Index: việc truy vấn bằng cách sử dụng LF-mapping được mô tả như sau. • Ví dụ cần truy vấn chuỗi P = aba. Ta truy vấn như Hình 2. • Đã tìm được chuỗi P là có trong T và truy vấn này có cùng kết quả với mảng hậu tố (Hình 2.
Thuật toán cho FM-index [12]: xét chuỗi con trùng P[1,p] trong dữ liệu text T[1,n]. Giá trị occ là số lượng của những lần xuất hiện của chuỗi con trùng P[1,n] trong dữ liệu text nén T bwt. Hai thủ tục chính để vận hành FM- index: 1. Xác định số lượng của những lần xuất hiện của chuỗi con trùng P[1,p] trong dữ liệu nén T bwt sử dụng thuật toán get_row (Algorithm 1).
Tham số First trỏ đến hàng đầu tiên của ma trận BWT (MT ) chứa tiền tố P[i, p] và tham số Last trỏ đến hàng cuối của MT chứa tiền tố P[i, p]. Thuật toán trả về giá trị occ = Last - First + 1. Xác định những vị trí của của chuỗi con trùng P[1,n] ở trong dữ liệu text T sử dụng thuật toán get_position (Algorithm 2) trả về occ giá trị nguyên khác nhau trong khoảng [1,n].6: Các bước thực hiện truy vấn với FM-index [11] Hình 2.7: Vị trí trùng lắp trong BWT [11] 10 Algorithm 1 Thuật toán get_rows để tìm những hàng chứa tiền tố P[1,n] [12] Function GET_ROWS(P [1, p]) begin i ← p, c ← P ]p F irst ← C[c] + 1, Last ← C[c + 1]; while ((F irst ≤ Last) and (i ≥ 2)) do c ← P [i − 1]; F irst ← C[c] + Occ(c, F irst − 1) + 1; Last ← C[c] + Occ(c, Last); i ← i − 1; end if Last < F irst then return no rows pref ixed by P [1, p]; end else return (First,Last); end end Algorithm 2 Thuật toán get_position cho việc tính toán Pos(i) [12] Function GET_POSITION(i) begin i0 ← i, t ← 0; while row i’ is not marked do i0 ← LF [i0 ]; t ← t + 1; end return Pos(i’) + t; end Ví dụ: Truy vấn chuỗi P = aba trong dữ liệu text T = aabaaba. Dựa vào Hình 2.1 ta có T bwt = abba$aa.
Áp dụng tiến trình của FM-index.