BỘ GIÁO DỤC ĐÀO TẠO
TRƯỜNG ĐẠI HỌC LẠC HỒNG
*** PHẠM ĐÔNG PHONG
KHAI THÁC KIẾN TRÚC PHÂN TÁN
VÀ CHIA SẺ TÌM SỰ TƯƠNG ĐỒNG
CỦA CÁC TRÌNH TỰ SINH HỌC LUẬN VĂN THẠC SỸ CÔNG NGHỆ THÔNG TIN Đồng Nai – Năm 2013

BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC LẠC HỒNG
* * *
PHẠM ĐÔNG PHONG KHAI THÁC KIẾN TRÚC PHÂN TÁN
VÀ CHIA SẺ TÌM SỰ TƯƠNG ĐỒNG
CỦA CÁC TRÌNH TỰ SINH HỌC

Biên Hòa, ngày 25 tháng 05 
Hc viên
Ph

iii
TÓM TẮT
Bắt cặp các trình tự (Sequence Alignment) sinh học DNA, Protein là một bài
toán cơ bản và đòi hỏi nhiều thời gian xử lý trong lĩnh vữc sinh tin học
(Bioinfomatics). Trong đó, Smith-Waterman là một thuật toán bắt cặp cục bộ nhằm
giải quyết bài toán này. Trên cơ sở bài toán bắt cặp này, có thể ứng dụng cho nhiều
bài toán khác. Đặc biệt đó là bài toán tìm sự tƣơng đồng của các trình tự.(Sequence
Similarity Searching)
Tuy nhiên, hiện nay số lƣợng các trình tự trong các cơ sở dữ liệu sinh học lớn
trên thế giới nhƣ NCBI, EMBL, DDBJ đang gia tăng nhanh chóng dẫn đến việc các
thuật toán xử lý trên khối lƣợng lớn dữ liệu trở nên kém hiệu quả. Luận văn này
trình bày một phƣơng pháp triển khai thuật toán Smith-Waterman trên môi trƣờng
phân tán MPI kết hợp với kiến trúc chia sẻ GPU-CPU nhằm tăng tốc thuật toán.
Môi trƣờng phân tán MPI với các thuật toán xử lý song song phù hợp cho phân
hoạch dữ liệu giúp cải thiện hiệu suất tìm kiếm và kiến trúc chia sẻ sử dụng CUDA
cho phép song song hóa bài toán bắt cặp trình tự.
Từ khoá: Sinh tin hc, bt cp trình t, CUDA, GPU, MPI.

iv
MỤC LỤC
LỜI CẢM ƠN i
LỜI CAM ĐOAN ii
TÓM TẮT iii
DANH MỤC CÁC KÝ HIỆU, CHỮ VIẾT TẮT vi
DANH MỤC HÌNH vii
DANH MỤC BẢNG ix

3.3.1. Lịch sử MPI 44
3.3.2. Đặc điểm của MPI 45
v
3.3.3. Cấu trúc chƣơng trình MPI 45
3.3.4. Cách lập trình MPI 45
CHƢƠNG 4. GIẢI THUẬT VÀ PHƢƠNG PHÁP HIỆN THỰC HÓA GIẢI
THUẬT TRÊN MÔI TRƢỜNG MPI KẾT HỢP CÔNG NGHỆ CUDA. 47
4.1. Thuật toán Smith-Waterman 47
4.2. Xây dựng giải thuật song song và cài đặt trên môi trƣờng CUDA. 51
Xây dựng giải thuật 51
4.3. Song song hoá xử lý dữ liệu dựa trên mô hình truyền thông điệp MPI 54
4.3.1. Lý do chọn mô hình truyền thông điệp MPI 54
4.3.2. Mô tả bài toán 54
4.3.3. Mô tả thuật toán 54
CHƢƠNG 5. KẾT QUẢ THỰC NGHIỆM 58
5.1. So sánh thời gian chạy chƣơng trình. 59
5.2. So sánh độ chính xác. 62
KẾT LUẬN 64
TÀI LIỆU THAM KHẢO viii
Hình 4.6. Sơ đồ biểu diễn Server gửi chuỗi DNA về Client 55
Hình 4.7. Sơ đồ biểu diễn Server gửi vị trí các trình tự DNA trong ngân hàng về
Client 56
Hình 4.8. Sơ đồ biểu diễn Client bắt cặp từng trình tự DNA trong ngân hàng với
chuỗi truy vấn DNA muốn tìm 57
Hình 5.1. Kết quả chạy chƣơng trình với file cơ sở dữ liệu db1b 59
Hình 5.2. File lƣu trữ kết quả sắp hàng đa trình tự 59


− Đánh giá kết quả theo yêu cầu của luận văn.
3
Phƣơng pháp thực hiện
− Sử dụng hệ điều hành Windows và MPI để chuyển thông điệp cấp thập trên
hệ thống phân tán.
− Sử dụng ngôn ngữ lập trình cấp cao nhƣ C/ C++ trên Visual Studio để lập
trình.
− Sử dụng kiến trúc tính toán song song với CUDA (Compute Unified Device
Architecture) do NVIDIA phát triển. CUDA là động cơ tính toán trong các
GPU (Graphics Processing Unit) của NVIDIA, để cài đặt các thuật toán chạy
trên GPU thông qua ngôn ngữ C++.
− Sử dụng thuật toán Smith - Waterman để thực hiện trên một số trình tự cần
so sánh. Thuật toán này bắt cặp cục bộ để tìm vùng tƣơng đồng giữa hai trình
tự nucleotide hay protein, thuật toán tìm các đoạn hay các miền có độ tƣơng
đồng cao từ đó đánh giá mức độ tƣơng đồng của hai trình tự.
Dự kiến kết quả đạt đƣợc
− Về lý thuyết: Tài liệu về vấn đề khai thác kiến trúc phân tán và chia sẻ tìm
sự tƣơng đồng của các trình tự sinh học.
− Về sản phẩm: Module chƣơng trình về sự tƣơng đồng của các trình tự sinh
học.
Dự kiến tên công trình công bố trên tạp chí hoặc hội thảo khoa học:
Khai thác kiến trúc phân tán và chia sẻ để tìm sự tƣơng đồng của các trình tự
sinh học.
Bố cục luận văn
Luận văn bao gồm 5 chƣơng. Chƣơng thứ nhất giới thiệu vấn đề cần giải
quyết, trình bày một số khái niệm tổng quan về sinh tin học, bài toán sắp hàng trình
tự, xử lý dữ liệu song song trên môi trƣờng phân tán dùng MPI, công nghệ CUDA
của nVidia, mục tiêu cũng nhƣ cấu trúc luận văn. Chƣơng thứ hai trình bày chi tiết
các phƣơng pháp sắp hàng trình tự. Chƣơng thứ ba trình bày công nghệ CUDA của
nVidia và ứng dụng, lập trình song song trên môi trƣờng phân tán sử dụng mô hình

6
cặp toàn cục đòi hỏi sắp xếp và so sánh về trình tự một cách toàn bộ. Trong loại
này, trình tự đầu vào thƣờng tƣơng tự và có độ dài xấp xỉ bằng nhau. Bắt cặp cục bộ
tập trung vào tính tƣơng đồng của các bộ phận cục bộ. Các thuật toán liên kết cục
bộ thƣờng cố gắng sắp hàng các trình tự để có đƣợc phần giống nhau dài nhất. Liên
kết cục bộ phù hợp với trình tự có độ dài khác nhau
Đối với bắt cặp toàn cục, thuật toán đƣợc phát triển nhất là Needleman-
Wunsch [7]. Đây là một phƣơng pháp sắp xếp dựa vào quy hoạch động, để tính
điểm cho quá trình liên kết. Mặt khác, các thuật toán BLAST [8] cho phép tìm kiếm
trình tự con (subsequences) giống nhƣ trình tự truy vấn. BLAST sử dụng phƣơng
pháp heuristic vì vậy tốc độ đặc biệt nhanh khi thực hiện trên các ngân hàng gen
lớn. Điều này đã làm BLAST trở thành công cụ phổ biến. Mặc dù với tốc độ thấp
hơn thuật toán BLAST, nhƣng với một độ chính xác cao hơn, nên thuật toán Smith-
Waterman [9] đƣợc xem là một trong những thuật toán phổ biến nhất của việc giải
quyết các vấn đề về sắp hàng trình tự cục bộ. Việc cài đặt thuật toán Smith-
Waterman đòi hỏi một lƣợng lớn các tính toánnên không thể chấp nhận cho hệ
thống máy tính thông thƣờng.
Đã có nhiều giải pháp đƣa ra để giải quyết bài toán, trong đó việc xử lý song
song trên môi trƣờng phân tán với kỹ thuật truyền thông điệp MPI hoặc sử dụng
công nghệ CUDA (Compute Unified Device Architecture) trên GPU đa nhân là
hƣớng tiếp cận đƣợc nhiều tác giả quan tâm. Nhóm tác giả Fa Zhang, Xiang-Zhen
Qiao, Zhi-Yong Liu trong [10] trình bày phƣơng pháp song song hoá dữ liệu với kỹ
thuật chia để trị, nhóm tác giả M.Noorian, H.Pooshfam, Z.Noorian, R.Abdullah
trong [11] đề xuất một thuật toán lai dựa trên các hệ thống phân tán MPI và
OpenMP triển khai trên cụm máy chủ SMP. Hƣớng tiếp cận hiện nay là dựa trên
kiến trúc chia sẻ đa nhân đồ hoạ GPU có khá nhiều công trình nghiên cứu, điển hình
là các công trình đƣợc nêu trong các tài liệu [12], [13], đây có thể xem là hƣớng tiếp
cận có nhiều triển vọng do công nghệ đồ hoạ đa nhân đang phát triển mạnh mẽ. Tuy
nhiên việc tập trung xử lý trên môi trƣờng chia sẻ bộ nhớ của một máy tính với
công nghệ CUDA, OpenCL hoặc các công nghệ dựa trên đa nhân đồ hoạ khác chƣa

 Tìm kiếm các trình tự, các đoạn lặp (motif), các enzyme trong cơ sở dữ
liệu.
Ở Việt Nam, lĩnh vực này cũng chỉ xuất hiện ở các viện nghiên cứu, trong một
vài trƣờng đại học lớn, và cũng chỉ dừng lại ở trong giới nghiên cứu về Công nghệ
sinh học. Hoạt động của khoa Công nghệ sinh học, trƣờng đại học Khoa Học Tự
Nhiên TP. Hồ Chí Minh; Viện Công nghệ sinh học, Viện Khoa học và Công nghệ
Việt Nam; Trƣờng đại học Y Dƣợc TP. Hồ Chí Minh là những minh chứng.
Phân viện Công nghệ thông tin tại TP. Hồ Chí Minh, từ năm 2004 đã hợp tác
với một số nhà nghiên cứu của Viện Công nghệ Sinh học; của NCBI/NLM/NIH và
NIAID/NIH đã xây dựng phần mềm HiBio [4] phục vụ việc nghiên cứu Công nghệ
Sinh học với các chức năng:
– Thiết kế mồi để hiển thị cặp mồi tốt nhất, các đoạn mồi xuôi, các đoạn
mồi ngƣợc, hoặc sắp xếp theo các tính chất.
– Thiết kế bản đồ plasmid với các tính năng cần thiết ở các dạng khác
nhau, trong đó có cả việc đề xuất những enzym cắt.
– Có thể sử dụng để dự đoán cấu trúc protein bậc 2, xem cấu trúc bậc 3
của một protein nào đó.
– Sử dụng để vẽ cây sinh loài theo hai dạng có gốc và không gốc.
– Vấn đề tìm kiếm motif cũng đƣợc đặt ra trong HiBio.
….
Ngoài phần mềm trên, Sở Khoa học và Công nghệ Tp. Hồ Chí Minh cũng
quản lý dự án về Xây dựng mô hình và công cụ tin học để xử lý thông tin về gene,
16
máy tính là một nhiệm vụ cấp bách và cần thiết. Để giải quyết khó khăn này, ngƣời
ta đã nghiên cứu tăng tốc độ tính toán bằng hai phƣơng pháp hoặc kết hợp cả hai:
 Phƣơng pháp 1: Cải tiến công nghệ, tăng tốc độ xử lý của máy tính.
Công việc này đòi hỏi nhiều thời gian, công sức và tiền của, nhƣng tốc
độ cũng chỉ đạt đƣợc đến một giới hạn nào đó.
 Phƣơng pháp 2: Chia bài toán ra thành những công việc nhỏ để có thể
chạy song song trên nhiều bộ xử lý.

những bài toán song song dữ liệu trong đó cùng một đoạn mã chƣơng trình đƣợc
thực thi song song cho nhiều bộ dữ liệu khác nhau.
Bên cạnh việc phát triển các bộ xử lý đồ họa có năng lực tính toán lớn, các
hãng sản xuất cũng quan tâm tới môi trƣờng phát triển ứng dụng cho các bộ xử lý
đồ họa này. CUDA là môi trƣờng phát triển ứng dụng trên các GPU của nVidia, bao
gồm ngôn ngữ lập trình song song, dữ liệu cùng với các công cụ biên dịch, gỡ rối và
giám sát thực thi cho các ứng dụng hoạt động dựa vào công nghệ này. Một số đặc
điểm chính của công nghệ CUDA:
 CUDA dựa trên nền tảng ngôn ngữ C, do đó nó quen thuộc với đa số
nhà phát triển ứng dụng.
 Mã CUDA chia làm 2 phần: phần thực thi trên CPU và phần thực thi
trên GPU. Phần thực thi trên GPU, còn gọi là kernel, khi đƣợc gọi có
18
thể thực thi song song trên hàng ngàn tiến trình riêng biệt. Mỗi tiến
trình có một định danh riêng để xác định nhiệm vụ của tiến trình đó.
 Để tránh sự phụ thuộc vào phần cứng, CUDA cho phép ngƣời lập trình
tùy ý xác định số lƣợng tiến trình song song, tuy nhiên các tiến trình
này cần đƣợc phân theo từng block với số lƣợng tối đa là 512. Cách
chia block giúp ngƣời lập trình không cần quan tâm tới năng lực phần
cứng, đồng thời giúp việc thực thi đƣợc hiệu quả ngay cả trên nhiều
loại GPU khác nhau.
Bộ nhớ đƣợc tổ chức phân cấp theo các lớp sau:
 Bộ nhớ chính: vùng bộ nhớ dành cho phần mã CPU. Chỉ có phần mã
này có thể truy cập và chỉnh sửa thông tin trên đó
 Bộ nhớ toàn cục GPU: vùng bộ nhớ mà tất cả các tiến trình của GPU có
thể truy cập. Có thể chuyển dữ liệu từ bộ nhớ chính sang bộ nhớ này
thông qua một số hàm thƣ viện của CUDA. Bộ nhớ này thông thƣờng
đƣợc dùng để lƣu trữ các dữ liệu đầu vào và đầu ra cho các tiến trình
song song trên GPU.
 Bộ nhớ chia sẻ: vùng bộ nhớ mà chỉ các tiến trình trong cùng một block

 Trong đó,
– na, ni, ng: tƣơng ứng là số phần tử bắt cặp đƣợc, số đột biến và số gap.
– match, mismatch, gap: tƣơng ứng là giá trị bắt cặp, đột biến và gap.
Ví dụ minh họa về điểm đánh giá với match = 2, mismatch = -1, gap = 1:
GAATTCAGTTA
| || | | |
GGAT-C-G—-A
 Giá trị: 6 x (+2) + 4 x (-2) + 1 x (-1) = 3
AC GCTG
| | |
-CATG-T-
 Giá trị: 3 x (+2) + 5 x (-2) + 0 x (-1) = -4
ACGCTG-
| ||
-C-ATGT
 Giá trị: 3 x (+2) + 3 x (-2) + 1 x (-1) = -1
tcctctgcctctgccatcat caaccc
|||| ||| ||||| ||||| ||||||
tcctgtgcatctgcaatcatgggcaaccc
 Giá trị: 23 x (+2) + 3 x (-2) + 3 x (-1) = 37
25
1}22,23,11{}2,2,{
3}21,21,21{}2,2,{
1}21,21,10{}2,2,{
1}20,20,12{}2,2,{
0}22,20,10{}2,2,{
2534352435
2433342334
2332332233
2231322132


MaxMMMMaxM
MaxMMMMaxM
MaxMMMMaxM
MaxMMMMaxM
MaxMMMMaxM





3}22,20,21{}2,2,{
0}21,22,10{}2,2,{
2}20,21,20{}2,2,{
1}20,20,12{}2,2,{
0}22,20,10{}2,2,{
4554554455
4453544354
4352534253
4251524152
4150514051





MaxMMMMaxM
MaxMMMMaxM
MaxMMMMaxM
MaxMMMMaxM



Viết lại ma trận M và σ
Bng 2.1. Ma trn M và  C
A
T
G
T
C
A
T
G
T

0
0
0
0
0
0 0
0

-1
-1
-1
-1
G
0
0
1
-1
3
1

G
0
-1
-1
-1
2
-1
C
0
2
0
0
1
2

C
0
2

-1
-1
2
-1

26
Tạo vết
 Xuất phát từ M
nm
, nếu:
– M
ij
= M
i-1,j-1
+ σ
ij
thì vết (i,j) → (i-1,j-1) đi theo đƣờng chéo
– M
ij
= M
i,j-1
+ d thì vết (i,j) → (i,j-1) đi lui
– M
ij
= M
i-1,j
+ d thì vết (i,j) → (i-1,j) đi lên
Bng 2.2. To vt t ma trn M
nm


0
0
A
0
-1
2
0
-1
-1

A
0
-1
2
-1
-1
-1
C
0
2
0
1
-1
-2

C
0
2
-1
-1

-1
-1
T
0
0
1
2
0
3

T
0
-1
-1
2
-1
2
G
0
-1
-1
0
4
2

G
0
-1
-1
-1




HHHH
HHHH
HHHH



1}11,12,11,0max{ }1,1,,0max{
1}12,11,12,0max{}1,1,,0max{
1}10,12,10,0max{ }1,1,,0max{
2213231223
2112221122
2011211021



HHHH
HHHH
HHHH



2}13,11,11,0max{}1,1,,0max{
3}10,11,21,0max{}1,1,,0max{
0}10,11,10,0max{}1,1,,0max{
3223332233
3122322132
3021312031

A
C
A

0
0
0
0
A
0
2
1
2
G
0
1
1
1
C
0
0
3
2
A
0
2
2
5
Tạo vết
• Xuất phát từ H


A
C
A

0
0
0
0
A
0
2
1
2
G
0
1
1
1
C
0
0
3
2
A
0
2
2
5
Tìm kết quả

 Single Instruction, Multiple Data (SIMD) là loại máy tính song song.
– Single Instruction, tất cả các đơn vị xử lý thi hành cùng câu lệnh ở chu
kỳ đồng hồ trƣớc.
– Multiple Data, mỗi đơn vị xử lý có thể thực hiện thao tác trên phần tử
dữ liệu khác nhau
– Máy tính SIMD có một đơn vị điều khiển để điều khiển nhiều đơn vị xử
lý thực hiện theo một luồng các câu lệnh. CPU phát sinh tín hiệu điều
khiển tới tất cả các phần xử lý, những bộ xử lý này cùng thực hiện một
phép toán trên cấc mục dữ liệu khác nhau, nghĩa là mỗi bộ xử lý có
luồng dữ liệu riêng. Kiến trúc máy SIMD có mô hình hoạt động theo
Hình 3.3

Hình 3.3. kin trúc máy SIMD
– Đây là loại tốt nhất phú hợp cho bài toán chuyên môn đòi hỏi tốc độ xử
lý cao nhƣ xử lý đồ thị, hình ảnh. Thi hành đồng bộ và tất định.
– Có hai biến thể loại SIMD. Biến thể Proccesor Arrays:
• Connection Machine CM‐2, MasPar MP‐1 & MP2, ILLIACIV
• Biến thể vector Pipelines: IBM 9000, Cray X-MP, Y-MP & C90,
Fujitsu VP, NEC SX-2, Hitachi S820, ETA10.
33
– Hầu hết các máy tính hiện đại, đặc biệt là các Graphics Processor Units
(GPUs) sử dụng chỉ thị SIMD.
 Multiple Instruction, Single Data (MISD), là loại máy tính song song.
– Miltiple Instruction, mỗi đơn vị xử lý hoạt động trên dữ liệu độc lập
thông qua dòng cấu trúc riêng biệt.
– Single Data, mỗi dòng dữ liệu duy nhất đƣợc đƣa vào nhiều đơn vị xử
lý.
– Kiến trúc máy MISD có mô hình hoạt động theo Hình 3.4

Hình 3.4. Kin trúc máy MISD