1

MỞ ĐẦU
Công nghệ thông tin là một trong những ngành khoa học kỹ thuật có
tính phổ dụng rộng rãi, được áp dụng trong nhiều lĩnh vực khác nhau.
Trong đó, không thể không kể đến việc ứng dụng công nghệ thông tin
trong công nghệ sinh học. Và chính sự hội tụ của hai nền khoa học lớn
này đã hình thành một ngành khoa học đã và đang phát triển khá mạnh mẽ
đó chính là ngành Tin sinh học (Bioinformatics). Từ khi Tin sinh học ra
đời, nó đã trở thành một công cụ hỗ trợ đắc lực trong việc nghiên cứu và
ứng dụng các sáng chế, phát minh của ngành công nghệ sinh học vào thực
tiễn.
Trong những năm gần đây, các nhà khoa học trong lĩnh vực sinh học
đã phát hiện ra những cấu trúc sinh học phân tử mới và xây dựng thành
một hệ thống cơ sở dữ liệu sinh học phân tử khá lớn tập trung thành các
ngân hàng dữ liệu (GenBank, EMBL, DDBJ). Tháng 08 năm 2015,
GenBank đã công bố có 199.823.644.287 bases, từ 187.066.846
sequences trong hệ thống ngân hàng dữ liệu của đơn vị này.
Tuy nhiên, Với dữ liệu lớn thì việc tìm kiếm dữ liệu hoặc tìm kiếm
sự tương đồng trong database sẽ tốn rất nhiều chi phí về mặt thời gian, đặc
biệt là bài toán bắt cặp trình tự sinh học. Có nhiều thuật toán được xây
dựng để giải quyết bài toán bắt cặp trình tự sinh học, và mỗi thuật toán lại
có tính ưu việt khác nhau về mặt thời gian hoặc hiệu quả thực hiện. Thuật
toán Smith-Waterman thường được áp dụng để giải quyết bài toán bắt cặp
trình tự sinh học vì thuật toán này cho kết quả có độ chính xác cao, tuy
nhiên giải thuật này lại mất khá nhiều thời gian thực hiện. Để nâng cao
tính hiệu quả của giải thuật Smith-Waterman và góp phần cải thiện thời


2

gian thực hiện của thuật toán này, luận văn sẽ tập trung vào việc đẩy mạnh
thời gian thực hiện của giải thuật dựa trên nền tảng các GPU. Luận văn
được đề xuất với tên như sau: “Giải pháp tăng tốc độ xử lý thuật toán
Smith-Waterman”.

CHƯƠNG 1- CƠ SỞ LÝ THUYẾT
1.1. Tổng quan về GPU:
Trong kiến trúc của máy tính, bộ vi xử lý trung tâm (CPU) là một bộ
phận quan trọng để vận hành máy tính, là khối điều khiển, xử lý các
chương trình và dữ kiện. Tuy nhiên đối với những ứng dụng đòi hỏi tốc
độ xử lý cao thì CPU có thể không thể đáp ứng, đặc biệt là trong lĩnh vực
đồ họa, game 3D. Vì vậy, để tăng tốc độ xử lý và thực thi chương trình,
người ta bổ sung GPU vào hệ thống máy tính, vậy GPU là gì và phương
thức tăng tốc độ xử lý của nó trong hệ thống máy tính như thế nào, những
điều này sẽ được trình bày cụ thể dưới đây.
1.1.1. GPU là gì:
GPU (Graphics Processing Unit) là bộ vi xử lý chuyên dụng có nhiệm
vụ tăng tốc, xử lý đồ họa cho bộ vi xử lý trung tâm CPU nhằm tăng tốc
các ứng dụng đồ họa, ứng dụng khoa học, kỹ thuật và phân tích dữ liệu
lớn. GPU có thể đẩy nhanh tốc độ xử lý ở nhiều môi trường khác nhau:
máy tính (máy tính cá nhân, máy trạm, máy chơi game chuyên dụng), điện
thoại di động, máy tính bảng, robot, …
1.1.2.

Lịch sử phát triển của GPU:

Và trong khoảng 17 năm gần đây, GPU đã phát triển rất mạnh mẽ với
nhiều cải tiến, bổ sung, đặc biệt là những linh kiện phần cứng nhằm tăng



3

tốc độ xử lý của trình điều khiển VGA (Video Graphic Array). Khi GPU
mới xuất hiện thì chưa có khả năng lập trình mở rộng, sau thời gian phát
triển và cải tiến thì việc lập trình mở rộng trở nên khá dễ dàng.
1.1.3. Cấu trúc của GPU và cơ chế song song ứng dụng:
1.2. Tổng quan về OPENCL
1.2.1. Giới thiệu về OPENCL:
OpenCL (Open Computing Language) là một chuẩn lập trình mã
nguồn mở miễn phí sử dụng ngôn ngữ OPENCL-C dựa trên những tiêu
chuẩn của C99 và IEEE-754 (chuẩn dấu chấm động cho số học), do đó,
cấu trúc lệnh của OPENCL hoàn toàn giống với ngôn ngữ lập trình C.
1.2.2. Cấu trúc của OPENCL:
Sự vận hành của OpenCL được mô tả bởi cụm các model có mối liên
hệ với nhau, bao gồm Platform Model (mô hình nền tảng), Execution
Model (mô hình thực thi), Memory Model (mô hình bộ nhớ), và
Programming Model (mô hình lập trình).
a) Platform Model:
b) Execution Model:
c) Memory Model:
d) Programming Model:
1.2.3. Quy trình phát triển một chương trình OPENCL:
1.3. Bài toán bắt cặp trình tự:
Bắt cặp trình tự hay so sánh trình tự nhằm tìm đến sự tương đồng
giữa các trình tự bằng cách đo lường sự giống nhau của các chuỗi trình tự.
Các chuỗi trình tự ở đây chính là các chuỗi trình tự ADN, RNA hoặc các
trình tự amino acid (protein). Và việc bắt cặp trình tự được thực hiện bằng


4


cách thêm “gap” vào những vị trí sao cho các cột tương đồng nhau.
Ví dụ: cho trình tự a: AGTGACT, trình tự b: ATGCT, kết quả của quá
trình bắt cặp trình tự là:
AGTGACT
|

||

||

A– TG– CT
Để đánh giá được mức độ tương đồng của các trình tự, áp dụng công thức
sau:
𝒏𝒂 𝒙 𝒎𝒂𝒕𝒄𝒉 + 𝒏𝒊 𝒙 𝒎𝒊𝒔𝒎𝒂𝒕𝒄𝒉 + 𝒏𝒈 𝒙 𝒈𝒂𝒑

(1.1)

Trong đó: na, ni, ng lần lượt là số các phần tử giống nhau, không giống
nhau và số các gap được thêm vào; match, mismatch và gap lần lượt là
các chỉ số tính toán để tìm ra mức độ tương đồng (match >0).
1.4. Các thuật toán giải quyết bài toán bắt cặp trình tự sinh học:
Có nhiều thuật toán được xây dựng đẻ giải quyết bài toán bắt cặp
trình tự: thuật toán Needleman-Wunsch, Smith-Waterman, Blast, ….
Thuật toán Needleman-Wunsch và Smith-Waterman đều dựa trên cơ chế
quy hoạch động, tuy nhiên mỗi giải thuật lại có một phương pháp xử lý
và tìm kiếm khác nhau.
CHƯƠNG 2 - NGUYÊN LÝ ĐẨY NHANH THUẬT TOÁN
SMITH-WATERMAN TRONG MÔI TRƯỜNG CPU-GPU
2.1. Thuật toán Smith-waterman nguyên thủy:

2.1.1. Giới thiệu:
Thuật toán Smith-Waterman là giải thuật giải quyết bài toán bắt cặp
trình tự cục bộ, nhằm tìm ra những đoạn có điểm tương đồng về cấu trúc


5

hoặc chức năng giữa các trình tự sinh học, nucleotide hoặc các chuỗi
protein.
Thuật toán này được F. Smith và Michael S. Waterman đề xuất vào
năm 1981 dựa trên một thuật toán trước đó được xây dựng bởi Needleman
và Wunsch, được biết đến với tên gọi: thuật toán Needleman-Wunsch.
2.1.2. Nguyên lý hoạt động:
Thuật toán Smith-Waterman là thuật toán sử dụng phương pháp quy
hoạch động để định lượng các điểm số cho quá trình bắt cặp trình tự.
Do áp dụng phương pháp quy hoạch động nên trong quá trình tính
toán, giải thuật sử dụng ma trận để ghi nhận điểm số và áp dụng công thức
sau:
Hi0=0 với ∀𝑖 = 0, 𝑛, H0j=0 với ∀𝑗 = 0, 𝑚
(2.1)
Hij=max(0, 𝐻𝑖−1,𝑗−1 + 𝜎𝑖𝑗 , 𝐻𝑖−1,𝑗 + 𝑑, 𝐻𝑖,𝑗−1 + 𝑑) , ∀𝑖 = 0, 𝑛, ∀𝑗 =
0, 𝑚 (2.2)
𝑚𝑎𝑡𝑐ℎ
và d=gap
𝑚𝑖𝑠𝑚𝑎𝑡𝑐ℎ

𝜎𝑖𝑗 = {
Trong đó:

- n là độ dài của trình tự Sa,

- m là độ dài trình tự Sb,
- Hij là ma trận điểm số
- d là giá trị của gap
- match và mismatch lần lượt là điểm số trùng khớp và không trùng
khớp của Sai và Sbj, giả sử rằng điểm số match luôn dương (match ≥
0).


6

Để giải quyết bài toán bắt cặp trình tự cục bộ, giải thuật trãi qua các
bước sau:
Bước 1: Khởi tạo ma trận, áp dụng công thức (2.1).
Bước 2: Tính toán điểm số và điền ma trận, áp dụng công thức (2.2).
Bước 3: Tìm điểm số max trong ma trận Hi,j
Bước 4: Tìm dấu vết dựa trên ma trận vừa tính ở trên.
Bước 5: Kết quả bắt cặp trình tự
Để minh họa cho các bước của giải thuật, tìm hiểu ví dụ sau (ví dụ
1): cho trình tự A: CGTGAATTCAT, trình tự B: GACTTAC, cho các giá
trị match = 2, mismatch=-1, gap = -1; n, m: lần lượt là độ dài của chuỗi
trình tự A, B.
2.1.3. Thuật toán và Đánh giá:
Thuật toán Smith-Waterman thực hiện theo trình tự 5 bước:
Bước 1: Khởi tạo ma trận:
H[i][0]=0, 0<=i<=n, n là chiều dài chuỗi trình tự A
H[0][j]=0, 0<=j<=m, m là chiều dài chuỗi trình tự B.
Bước 2: Điền ma trận:
If (a[i]==b[j])
Delta= match
Else

Delta = mismatch
Hij=max(0, Hi-1,j-1 + delta, hi-1,j+d, Hi,j-1+d)
Bước 3: Tìm Hnmax,mmax:
If(max_H

7

max_H = Hij
imax = i
jmax = j
Bước 4: Tìm dấu vết:
Xuất phát từ Hnmax,mmax,
nếu:
– Hij = Hi-1,j-1 + σij thì vết (i,j) → (i-1,j-1) theo đường chéo
– Hij = Hi,j-1 + d thì vết (i,j) → (i,j-1) đi lui
– Hij = Hi-1,j + d thì vết (i,j) → (i-1,j) đi lên
Bước 5: Kết quả:
Nếu:
– (i,j) →(i-1,j-1): theo đường chéo Ui và Vj được ghi vào
– (i,j) →(i-1,j): đi lên “-” và Vj được ghi vào
– (i,j) →(i,j-1): đi lui Ui và “-” được ghi vào
Thuật toán này giải quyết rất hiệu quả bài toán bắt cặp trình tự cục
bộ với độ chính xác tương đối cao, tuy nhiên thời gian thực hiện thuật toán
thì tốn khá nhiều thời gian, thời gian thuật toán thực thi là O(nm).
2.2. Phương pháp cải tiến thuật toán Smith-Waterman:
Dựa trên thuật toán Smith-Waterman nguyên thủy, phương pháp được
trình bày trong luận văn sẽ cải tiến tốc độ xử lý của thuật toán trong giai
đoạn điền ma trận.
Gọi x, y là đại diện cho điểm bắt đầu và điểm kết thúc của hai đoạn

tương đồng của hai trình tự. Lưu ý, đoạn tương đồng được xác định dựa
trên trình tự ban đầu của chúng. Giả sử rằng [x, y] là phân đoạn tương
đồng trong chuỗi SA, 1 ≤ 𝑥 ≤ 𝑦 ≤ 𝑛, với n là độ dài của chuỗi SA, tương


8

tự [z,w] là phân đoạn tương đồng của trình tự SB, 1 ≤ 𝑧 ≤ 𝑤 ≤ 𝑚, với m
là độ dài của chuỗi trình tự SB.
Ví dụ trên ta có như sau:
Trình tự Sa: C G T G A A T T C A T
Trình tự Sb: G A C T TA CT
Match = 2, mismatch = -1, gap = -1
Bắt cặp trình tự cục bộ giữa hai trình tự và đoạn tương đồng như sau:

Hình 2.1: Ví dụ đoạn tương đồng của hai trình tự
Ta có đoạn tương đồng là [4,9] cho trình tự SA.
2.2.1. Phương pháp cắt tỉa:
Để giải quyết bài toán bắt cặp trình tự cho cặp trình tự r=<b,c> cần
phải có kết quả của liên kết cho các trình tự 𝑝 =< 𝑎, 𝑏 >∈ 𝑃, trong đó
[xp, yp] là đoạn tương đồng giữa hai chuỗi trình tự, fp là số mismatch giữa
hai trình tự, gp là số gap được thêm vào. Tương tự, kết quả của liên kết


9

cho các trình tự 𝑞 =< 𝑎, 𝑐 >∈ 𝑃, trong đó [xq, yq] là đoạn tương đồng
giữa hai chuỗi trình tự, fq là số mismatch và gq là số gap.
Từ kết quả trên, phương pháp cắt tỉa được trình bày trong luận văn này
nhằm tăng tốc liên kết của thuật toán Smith – Waterman cho cặp

r=<b, c> ∈ P và phương pháp cắt tỉa được áp dụng trong giai đoạn điền
ma trận.

Hình 2.2: Mô hình tổng quát biểu diễn trình tự tương đồng (Nguồn
[5])
Trong hình 2.2: (a) bắt cặp trình tự giữa sa và sb, (b) bắt cặp trình tự
giữa sa và sc, (c) phần chung giữa chúng trên chuỗi sa.
Giả sử rằng: p=<a,b> và q=<a,c> có ađồng giữa các trình tự khi và chỉ khi 𝑥𝑞 ≤ 𝑦𝑝 𝑣à 𝑥𝑝 ≤ 𝑦𝑞 . Từ đó, suy ra
đoạn tương đồng giữa các trình tự được xác định bằng công thức sau đây:
[Max(𝑥𝑝 , 𝑥𝑞 ) , min(𝑦𝑝 , 𝑦𝑞 )]

(2.3)

Điều kiện để phương pháp cải tiến được thực hiện: khi tồn tại đoạn
tương một đồng giữa các cặp trình tự p và q.
Ví dụ 2: Cho 3 trình tự:


10

Sa: CGTGAATTCAT
Sb: GACTTAC
Sc: GACTTAAATAGGGGC
Match =2, mismatch = -1 và gap = -1;
Kết quả bắt cặp trình tự của các cặp như sau:
 Kết quả bắt cặp trình tự của Sa và Sb:
G A A T T
|

|

|

- C

|

|

G A C T T A C

Trong đó ta có đoạn tương đồng của trình tự p=< Sa,Sb> = [4,9] trên trình
tự Sa, fp=1 và gp=1;
 Kết quả bắt cặp trình tự của Sa và Sc:
G A A T T C A
|

|

|

|

|

- T
|

G A C T T A A A T

Trong đó ta có đoạn tương đồng của trình tự p=< Sa,Sc> = [4,11] trên trình
tự Sa, fq=2 và gp=1;
Áp dụng công thức (2.3) để kiểm tra có tồn tại điểm tương đồng giữa các
đoạn trình tự trên:
[Max(𝑥𝑝 , 𝑥𝑞 ) , min(𝑦𝑝 , 𝑦𝑞 )] = [𝑀𝑎𝑥(4,4), 𝑀𝑖𝑛(9,11)] = [4,9]
Vậy tồn tại đoạn tương đồng giữa các cặp trình tự => phương pháp cắt
tỉa được áp dụng trên các đoạn trình tự trên. Và đoạn tương đồng được
biểu diễn như sau:


11

7

8

Sa C G T G A A T

1

2

3

T

Sb

4

5

6

9

10

11

- C A T

G A C T T A C
1

2

3

1

2

3

4

5

6

7

4

5

6

7

8

9

10

11

T C A

- T

Sa C G T G A A T

Sc

G A C T T A A A T A G G G G C
1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

Sa C G T G A A T T C A T

1

2

3

4

5

6

7

8

9

10

11

Hình 2.3: Biểu diễn bắt cặp trình tự của ba chuỗi Sa, Sb, Sc trên
chuỗi Sa
2.2.2. Ràng buộc dưới cho tất cả các cặp trong quá trình so sánh:
Ý tưởng của phương pháp này đó chính là sử dụng giới hạn thấp hơn
L1 cho tất cả các điểm số liên kết trong đoạn tương đồng
[max(𝑥𝑝 , 𝑥𝑞 ) , min(𝑦𝑝 , 𝑦𝑞 )] và là giới hạn dưới L cho các điểm liên kết
cho tất cả các cặp r =<b,c>. Do đó, một giới hạn thấp hơn L1 cho đoạn
tương đồng trong chuỗi sa được sử dụng như là một ràng buộc thấp hơn

cho những liên kết của những chuỗi con. Vì mỗi dãy làm một phần của
chuỗi sb và sc, điểm số liên kết cho cặp r=<b,c> ít nhất là L2 hay L2 có thể
được sử dụng như là một giới hạn dưới L cho tất cả cặp r=<b,c>.


12

Hình 2.4: Sự trùng khớp và không trùng khớp của ba trình tự
(Nguồn [5])
Hình 2.5 cho thấy sự trùng khớp và không trùng khớp của ba trình tự
sa, sb, sc khi sắp xếp. Như thể hiện trong hình, giới hạn dưới L2 cho điểm
số liên kết của cặp r có thể tính được bằng cách đến số lượng các biểu
tượng phù hợp mà thường xuất hiện trong ba chuỗi trình tự sa, sb, sc.
Hàm tính giá trị giới hạn dưới cho tất cả các điểm số liên kết trong
đoạn tương đồng được xác định bởi:
𝐿 = 𝑀𝑎𝑥(0, 𝑚𝑎𝑐𝑡𝑐ℎ × 𝑀 − 𝐹 − 𝐺)

(2.4)

Trong đó M là số match của các ký tự tương đồng trong đoạn tương
đồng giữa các trình tự, M được tính bằng cách lấy chiều dài của đoạn
tương đồng trừ đi số mismatch của chúng, được biểu diễn bởi công thức
sau:
𝑀 = min(𝑦𝑝 , 𝑦𝑞 ) − max(𝑥𝑝 , 𝑥𝑞 ) + 1 − (𝑓𝑝 + 𝑓𝑞 )
Công thức tính F: 𝐹 = 𝑚𝑖𝑠𝑚𝑎𝑡𝑐ℎ 𝑥 (𝑓𝑝 + 𝑓𝑞 )
(2.6)

(2.5)

13

Công thức tính G: 𝐺 = 𝑔𝑎𝑝 𝑥 (𝑔𝑝 + 𝑔𝑞 )
(2.7)
Vì đoạn tương đồng được xác định trên các trình tự ban đầu của Sa,
không bao gồm các ký tự GAP, do đó L được xác định bởi công thức (2.3)
là một giới hạn thấp hơn về điểm số của đoạn tương đồng.
Giả định rằng điểm số liên kết của đoạn tương đồng trên trình tự Sa
là L’, giả sử L’ < L, các điểm không phù hợp, GAP nằm trong đoạn tương
đồng và tất cả các biểu tượng còn lại đều phù hợp. Tổng điểm số của các
ký hiệu còn lại như vậy phải có một điểm số tiêu cực để đáp ứng cho L’ <
L, điều này mâu thuẫn với giả định điểm số 𝑚𝑎𝑡𝑐ℎ ≥ 0. Vậy kết luận rằng
L’>L.
Trong quá trình bắt cặp trình tự cục bộ cho ra điểm số liên kết tối đa,
vị trí bắt đầu và kết thúc của đoạn tương đồng là tùy ý, một ràng buộc thấp
hơn về điểm số của đoạn tương đồng là một ràng buộc địa phương về điểm
số cho toàn bộ khu vực.
2.2.3. Tế bào kích hoạt
Giả sử ta có L là một giới hạn thấp hơn trên tất cả các điểm liên kết,
một tế bào kích hoạt là một tế bào trong ma trận (i,j) thỏa mãn điều kiện
sau:
𝐻𝑖,𝑗 + 𝛼 × max(𝑚 − 𝑖, 𝑛 − 𝑘 ) < 𝐿
Phương pháp này sử dụng điểm số cao nhất đã được tính toán trước
đó nhằm tính toán điểm số trong ma trận Hi,j.
Vì vậy, tính toán giá trị của một ô trong ma trận H(i,j) có thể được
cắt tỉa trong giai đoạn điền ma trận nếu tất cả tế bào (i-1,j), (i,j-1), (i-1,j1) được kích hoạt hoặc đã được cắt tỉa.


14

2.2.4. Lý thuyết song song thuật toán Smith- Waterman:
2.3. Thuật toán cải tiến
2.3.1. Thuật toán Smith-Waterman với phương pháp cắt tỉa:
Thuật toán Smith-Waterman sử dụng phương pháp cắt tỉa sẽ giảm
được quá trình tính toán trong giai đoạn điền ma trận. Và thuật toán được
xây dựng như sau:
Bước 1: Khởi tạo ma trận:
H[i][0]=0, 0<=i<=n, n là chiều dài chuỗi trình tự A
H[0][j]=0, 0<=j<=m, m là chiều dài chuỗi trình tự B.
Bước 2: Xác định giá trị giới hạn dưới:
M =min(yp,yq) – max(xp,xq) +1 – (fp+fq)
F = mismatch x (fp +fq)
G = gap x (gp +gq)
Bound = Max(0, match x M – F – G)
Bước 3: Điền ma trận
Vì giá trị của ma trận luôn lớn dương, do đó, để đánh dấu các tế bào
kích hoạt hoặc tế bào được cắt tỉa chọn các giá trị âm, trong luận văn này,
tác giả chọn giá trị là -1.
If (Hi-1,j-1==-1 && Hi-1,j ==-1 && Hi, j-1 == -1)
Hij=-1
Else
If (a[i]==b[j])
Delta= match
Else
Delta = mismatch


15

Hij=max(0, Hi-1,j-1 + delta, Hi-1,j+d, Hi,j-1+d)

If (Hij + match * max(n-i,m-k) < bound)
Hij=-1
Bước 4: Tìm Hnmax,mmax:
If(max_H max_H = Hij
imax = i
jmax = j
Bước 5: Tìm dấu vết:
Xuất phát từ Hnmax,mmax,
nếu:
– Hij = Hi-1,j-1 + σij thì vết (i,j) → (i-1,j-1) theo đường chéo
– Hij = Hi,j-1 + d thì vết (i,j) → (i,j-1) đi lui
– Hij = Hi-1,j + d thì vết (i,j) → (i-1,j) đi lên
Bước 6: Kết quả:
Nếu:
– (i,j) →(i-1,j-1): theo đường chéo Ai và Bj được ghi vào
– (i,j) →(i-1,j): đi lên “-” và Bj được ghi vào
– (i,j) →(i,j-1): đi lui Ai và “-” được ghi vào
Thuật toán Smith-Waterman sử dụng phương pháp cắt tỉa giải quyết
bài toán bắt cặp trình tự cục bộ rất hiệu quả với độ chính xác tương đối
cao. Trong giai đoạn điền ma trận, việc bỏ qua tính toán giá trị của từng
tế bào trong ma trận sẽ giúp tăng tốc độ xử lý của thuật toán.


16

2.3.2. Thuật toán kết hợp giữa cắt tỉa và xử lý song song
Việc tính toán song song phụ thuộc vào việc xác định số đường chéo
trong ma trận, có nghĩa là tính được số lần tính toán song song của bài
toán. Gọi L là số đường chéo trong ma trận, công thức tính L được tổng

quát như sau:
𝑛

𝑚

𝑘

𝑘

𝐿= +

−1=

(𝑛+𝑚)
𝑘

-1

(2.9) (Nguồn [3])

Trong đó:
- n là chiều dài của chuỗi trình tự Sa, m là chiều dài của chuỗi trình tự
Sb.
- k là kích thước ma trận con, là ước số chung của chiều dài của hai
chuỗi trình tự n và m, với điều kiện kSau khi tính toán được số đường chéo trong ma trận thì cần phải xác
định được số ma trận cần tính toán trên mỗi đường chéo. Gọi Nmatrix là số
ma trận trên mỗi đường chéo Li và được xác định theo công thức sau:
𝑛

𝑚

𝑚

𝑘

𝑘

𝑘

𝑁𝑚𝑎𝑡𝑟𝑖𝑥 = 𝑚𝑖𝑛 (𝐿, ( − max (0, 𝐿 − )) , ) , 1 ≤ 𝑖 ≤ 𝐿 (2.10)
(Nguồn [3])

Ví dụ: Cho trình tự Sa: ACTACTTAGT (n=10), Sb: ATGCTCTTAG
(m=10), match = 2, mismatch = -1 và gap =-1;
Với n=10 và m=10 => k =2, áp dụng công thức (2.9) ta có L=9.


17

A
A
T
A
C
T
C
A
G
T

0
0
0
0
0
0
0
0
0
0
0

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

T
0
1
1

4
3
2
3
2
1
1
3

G
0
0
0
3
3
2
2
2
1
3
2

C
0
0
0
2
2
5
4

4
3
2
2

T
0
0
0
2
1
4
7
6
5
4
4

C
0
0
0
1
1
3
6
9
8
7
6

T
0
0
0
2
1
2
5
8
8
7
9

T
0
0
0
2
1
1
4
7
7
7
9

A
0
2

2
1
4
3
3
6
9
8
8

G
0
1
1
1
3
3
2
5
8
11
10

Hình 2.5: Cách song song thuật toán SW trong giai đoạn điền ma
trận
Trong hình 2.7, ta có 9 đường chéo, theo cơ chế song song là lần lượt
tính giá trị cho từng đường chéo từ 1 đến 9. Đồng thời, trên mỗi đường
chéo có số ma trận cần phải tính theo kích thước k; việc tính toán cho từng
điểm số trong ma trận con cũng được thực hiện theo mô hình được miêu
tả trong hình 2.1.

Trước tiên, tính toán cho đường chéo số 1 (các tế bào ma trận màu
vàng): áp dụng công thức 2.10 ta tính được số ma trận là 1.
Tương tự, đường chéo số 2, số ma trận là 2.
Lặp lại quá trình tính toán cho đến khi hoàn tất việc tính toán điểm số
của các tế bào ma trận trên đường chéo số 9 của ma trận.
Từ mô hình trên, song song giải thuật Smith-Waterman được thực hiện
thông qua các bước sau:


18

Bước 1: Khởi tạo giá trị ban đầu cho ma trận
Hi0=0 với ∀𝑖 = 0, 𝑛, H0j=0 với ∀𝑗 = 0, 𝑚
Bước 2: Xác định kích thước k của ma trận con
Bước 3: Tính toán số đường chéo cần phải song song theo công thức:
𝑛

𝑚

𝑘

𝑘

𝐿= +

−1=

(𝑛+𝑚)
𝑘

-1

Bước 4: Tính toán số ma trận con trên đường chéo thứ I, ta thực hiện
song song các ma trận con theo hướng đường chéo:
𝑛

𝑚

𝑚

𝑘

𝑘

𝑘

𝑁𝑚𝑎𝑡𝑟𝑖𝑥 = 𝑚𝑖𝑛 (𝐿, ( − max (0, 𝐿 − )) , ) , 1 ≤ 𝑖 ≤ 𝐿

(2.10)

Bước 5: Tìm giá trị max trong ma trận
Bước 6: Tìm vết dựa theo kết quả tính toán ở bước điền ma trận
Bước 7: In kết quả.
2.4. Thuật toán cải tiến
2.4.1. Phương pháp kết hợp giữa cắt tỉa và xử lý song song
Việc kết hợp phương pháp cắt tỉa và xử lý song song thuật toán
Smith-Waterman không chỉ cải thiện về mặt thời gian của việc cắt tỉa
những tế bào không tính toán mà còn đẩy nhanh xử lý song song những
giá trị từng tế bào trong từng ma trận trên mỗi đường chéo của ma trận.
Giải thuật kết hợp giữa phương pháp cắt tỉa và xử lý song song thuật toán

Smith-Waterman được trình bày qua các bước như sau:
Bước 1: Khởi tạo ma trận:
H[i][0]=0, 0<=i<=n, n là chiều dài chuỗi trình tự A
H[0][j]=0, 0<=j<=m, m là chiều dài chuỗi trình tự B.
Bước 2: Xác định giá trị giới hạn dưới:


19

M =min(yp,yq) – max(xp,xq) +1 – (fp+fq)
F = mismatch x (fp +fq)
G = gap x (gp +gq)
Bound = Max(0, match x M – F – G)
Bước 3: Xác định kích thước ma trận con và L
- k là ước số chung của n và m
- Tính số đường chéo của ma trận:
𝑛

𝑚

𝑘

𝑘

𝐿= +

−1=

(𝑛+𝑚)
𝑘

-1

Bước 4: Điền ma trận
For I = 0 to L
𝑛

𝑚

𝑚

𝑘

𝑘

𝑘

𝑁𝑚𝑎𝑡𝑟𝑖𝑥 = 𝑚𝑖𝑛 (𝐿, ( − max (0, 𝐿 − )) , ) , 1 ≤ 𝑖 ≤ 𝐿
Mỗi ma trận con ta tính như sau:
If (Hi-1,j-1==-1 && Hi-1,j ==-1 && Hi, j-1 == -1)
Hij=-1
Else
If (a[i]==b[j])
Delta= match
Else
Delta = mismatch
Hij=max(0, Hi-1,j-1 + delta, Hi-1,j+d, Hi,j-1+d)
If (Hij + match * max(n-i,m-k) < bound)
Hij=-1
Bước 5: Tìm Hnmax,mmax:

If(max_H

20

max_H = Hij
imax = i
jmax = j
Bước 6: Tìm dấu vết:
Xuất phát từ Hnmax,mmax,
nếu:
– Hij = Hi-1,j-1 + σij thì vết (i,j) → (i-1,j-1) theo đường chéo
– Hij = Hi,j-1 + d thì vết (i,j) → (i,j-1) đi lui
– Hij = Hi-1,j + d thì vết (i,j) → (i-1,j) đi lên
Bước 7: Kết quả:
Nếu:
– (i,j) →(i-1,j-1): theo đường chéo Ai và Bj được ghi vào
– (i,j) →(i-1,j): đi lên “-” và Bj được ghi vào
– (i,j) →(i,j-1): đi lui Ai và “-” được ghi vào
Phương pháp cắt tỉa kết hợp với xử lý song song thuật toán SmithWaterman đã làm tăng quá trình tính toán của giải thuật Smith-Waterman
trong bài toán bắt cặp trình tự cục bộ.
TIỂU KẾT CHƯƠNG 2
Chương hai đã giới thiệu tổng quan về giải thuật Smith-Waterman
từ lý thuyết cho đến các bước thực hiện giải thuật. Mặc dù, giải thuật
Smith-Waterman giải quyết bài toán bắt cặp trình tự cục bộ với độ chính
xác tương đối cao nhưng thời gian thực hiện giải thuật lại khá tốn nhiều
thời gian. Để tăng tốc thời gian xử lý của giải thuật, trong chương hai cũng
nêu rõ cơ chế tăng tốc bằng việc ứng dụng cắt tỉa các tế bào thỏa mãn một

21

điều kiện nhất định được gọi là tế bào kích hoạt. Đồng thời, ứng dụng việc
cắt tỉa vào quá trình song song trong giai đoạn điền ma trận. Trong chương
hai cũng thể hiện rõ các bước của giải thuật và đánh giá sơ bộ của thuật
toán.
CHƯƠNG 3- KẾT QUẢ THỰC NGHIỆM

3.1. Chương trình thực nghiệm
3.1.1. Chương trình:
Chương trình được xây dựng trên nền tảng C++ trong Visual Studio
Ultimate 2013 và thư viện OPENCL 2.0, kết hợp Intel® SDK for
OPENCL™ 2016. Với việc sử dụng thư viện của OPENCL 2.0 nên trong
chương trình thực thi cần phải khai báo như sau:
#define CL_HPP_TARGET_OPENCL_VERSION 200
Việc khai báo này rất cần thiết cho quá trình phát triển chương trình,
bởi việc sử dụng các hàm thư viện <CL/cl2.hpp> trong version 2.0 của
OPENCL. Và sau đây là một số hàm được xây dựng trong chương trình:
3.1.1.1.

Hàm quét tìm Platforms:

Hàm được xây dựng nhằm tìm kiếm các Platforms được cài đặt trong
hệ thống và lựa chọn Platforms mặc định. Thông thường, mỗi máy tính
chỉ sử dụng một GPU, tuy nhiên đối với những cấu trúc máy tính mới hoặc
mạnh mẽ thì có thể sử dụng dual-GPU, vì vậy hàm được xây dựng nhằm
tìm kiếm tất cả các platforms có trong hệ thống, ví dụ: Intel® OPENCL,
AMD ® OPENCL, … Đồng thời, hàm sẽ lựa chọn Platform mặc định để
thực thi.

22

void TimPlatforms()
{
cl::Platform::get(&all_platforms);
if (all_platforms.size() == 0){
std::cout << " Khong tim thay platform.!\n";
exit(1);
}
default_platform = all_platforms[0];
std::cout << "Platform su dung: " <<
default_platform.getInfo<CL_PLATFORM_NAME>() <<
"\t Version: " <<
default_platform.getInfo<CL_PLATFORM_VERSION>()
<< "\n\n";
}
3.1.1.2.

Hàm quét tìm thiết bị:

Cũng giống như hàm tìm kiếm Platform, hàm tìm kiếm thiết bị có mục
đích là sẽ tìm tất cả các GPU được gắn vào hệ thống máy tính, hàm không
chỉ thực thi trên hệ thống dual-GPU mà còn được sử dụng trong hệ thống
chỉ có một GPU duy nhất.
void TimDevices()
{
default_platform.getDevices(CL_DEVICE_TYPE_ALL,
&all_devices);
if (all_devices.size() == 0){

std::cout << " Khong tim thay thiet bi
nao!\n";
exit(1);
}
default_device = all_devices[0];
std::cout << "Device su dung: " <<
default_device.getInfo<CL_DEVICE_NAME>() << "\n\n";
}


23

Đối với cấu hình của máy mà tác giả thực nghiệm, trường hợp sử dụng
CPU là thiết bị device của OPENCL giá trị trong mảng all_devices[] là 1
(all_devices[1]), và GPU giá trị là 0 (all_devices[0]).
3.1.1.3.

Hàm tính toán giới hạn thấp hơn:

Hàm xây dựng nhằm tìm ra giới hạn thấp hơn giữa hai chuỗi trình tự,
input đầu vào của hàm là kết quả của liên kết các cặp trước đó p=<a,b>,
q= <a,c>. Kết quả của hàm sẽ là giá trị giới hạn thấp hơn. Input của hàm
được khai báo dạng typedef struct có dạng như sau:
typedef struct Reinput
{
string strname1;
string strinfo1;
string strname2;
string strinfo2;
long int so_mismatch, so_gaps, start, end;

}Re_input;
Trong đó: Các biến số trong struct là kết quả của quá trình bắt cặp
trình tự của hai chuỗi trình tự.

Và hàm tìm giá trị thấp hơn được xây dựng như sau:


24

int calculateBound(Reinput str1, Reinput str2,
Score score)
{
int bound = 0;
if ((str1.end < str2.start) || (str2.end <
str1.start))
{
bound = 0;
}
else
{
bound = max(0, ((min(str1.end, str2.end) max(str1.start, str2.start) - (str1.so_mismatch +
str2.so_mismatch)) - (str1.so_mismatch +
str2.so_mismatch) * score.mismatch (str1.so_gaps + str2.so_gaps) * score.gap));
}
return bound;
}
3.1.1.4.

Kernel file của phương pháp cắt tỉa kết hợp song song:

Như đã giới thiệu trong chương 1, kernel được thực hiện trên các thiết
bị của OPENCL (CPU đa lõi, GPU, …), device được chọn để thực thi
kernel còn phụ thuộc vào cấu hình máy tính, môi trường thực thi và ý
muốn của người lập trình. Và việc thực thi các kernel cần phải xác định
được id của từng work-item, do đó kernel của phương pháp cắt tỉa kết hợp
song song thuật toán Smith-Waterman được xây dựng như sau:
- Lấy id của work-item:
int x = get_global_id(0);


25

- Lấy giá trị của i và j:
int startI = subIndexes[2*x+0];
int startJ = subIndexes[2*x+1];
-

Nếu i thỏa mãn điều kiện (i >= n / 2) hoặc (i >= m – j) thì kiểm tra

Hi-1,j-1; Hi-1,j; Hi,j-1 có phải là các tế bào kích hoạt hay không, nếu là tế
bào kích hoạt thì bỏ qua tính toán giá trị Hij và ngược lại:
if ((ii >= (n / 2)) ||( ii >= m - jj))
{
if(H[(j-1)*(i-1)*dim]==-1 && H[j+(i-1)*dim]==-1
&& H[(j-1)+i*dim]==-1)
{
H[index]=-1;
T[index]=-1;
}
else

{
if(s1[ii]==s2[jj])
tam = H[(j-1)+(i-1)*dim] + match;
else
tam = H[(j-1)+(i-1)*dim] +
mismatch;
tam1 = H[j+(i-1)*dim] + gap;
tam2 = H[(j-1)+i*dim] + gap;
H[index] = max(max(max(0, tam),
tam1),tam2);
if ((H[index] + match*max(n - ii, m - jj))
< bound)
{
H[index] = -1;
T[index] = 0;