ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
Nguyễn Hoàng Dũng
CÁC PHƯƠNG PHÁP SẮP HÀNG ĐA CHUỖI
NHANH
KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY

Ngành: Công Nghệ Thông Tin
Cán bộ hướng dẫn: Tiến sĩ. Lê Sỹ Vinh
HÀ NỘI - 2010
LỜI CẢM ƠN
Đầu tiên, tôi xin gửi lời cảm ơn tới gia đình, nơi đã động viên và tạo mọi điều kiện
giúp tôi học hành tốt nhất trong suốt những năm qua.
Tôi xin chân thành cảm ơn các thầy cô giáo trong trường Đại học Công nghệ - Đại
học Quốc gia Hà Nội đã tận tình giúp đỡ và truyền đạt kiến thức cho tôi trong suốt 4
năm học qua để tôi có đủ kiến thức hoàn thành khóa luận này.
Đặc biệt, tôi xin gửi lời cảm ơn sâu sắc tới thầy Lê Sỹ Vinh – người đã nhiệt tình
giúp đỡ, định hướng cũng như động viên tôi trong quá trình nghiên cứu và hoàn thành
khóa luận.
Tôi xin gửi lời cảm ơn chân thành tới thầy Từ Minh Phương trường đại học Bưu
Chính Viễn Thông, người đã truyền dạy cho tôi những kiến thức quan trọng liên quan
trực tiếp đến đề tài của khóa luận.
Tôi cũng xin cảm ơn các bạn trong nhóm Tin sinh. Các bạn đã giúp đỡ tôi rất
nhiều trong việc hoàn thành khóa luận.
Mặc dù đã rất cố gắng hoàn thành khóa luận này, xong khóa luận sẽ khó tránh khỏi
những thiếu sót, kính mong quý thầy cô tận tình chỉ bảo giúp tôi. Một lần nữa tôi xin
cảm ơn tất cả mọi người.
Hà Nội, tháng 5 năm 2010
Sinh viên
Nguyễn Hoàng Dũng
Tóm tắt

3.1 Cách giải quyết của Chuong B. Do và Kazutaka Katoh.....................................................................17
3.2 Vấn đề tốc độ...................................................................................................................................18
3.2.1 Dữ liệu với số lượng chuỗi lớn ( > 200 chuỗi)..........................................................................18
3.2.2 Dữ liệu với số lượng sequence nhỏ, tổng số amino axit nhỏ...................................................19
3.2.3 Dữ liệu với độ dài của chuỗi quá lớn ( > 2000 amino acids)....................................................20
3.3 Vấn đề điểm chuẩn (benchmark)....................................................................................................21
3.3.1 Với các chuỗi có độ tương đồng cao........................................................................................21
3.3.2 Với các chuỗi có độ tương đồng thấp......................................................................................21
3.4 Cây quyết định.................................................................................................................................22
3.4.1 Cây quyết định cho yêu cầu tốc độ xử lý cao...........................................................................23
3.4.2 Cây quyết định cho yêu cầu tốc điểm chuẩn cao.....................................................................24
Chương 4: Kết quả thực nghiệm và bình luận...........................................................................................26
4.1 Giới thiệu về BAliBASE.....................................................................................................................26
4.1.1 BAliBASE 2.................................................................................................................................26
4.1.2 BAliBASE 3.................................................................................................................................26
4.1.3 Cách đánh giá của BAliBASE......................................................................................................26
4.2 Kết quả thực nghiệm........................................................................................................................28
Chương 5: Kết Luận....................................................................................................................................34
Tài Liệu Tham Khảo....................................................................................................................................35
Mục Lục Bảng:
Bảng 1: Bắt cặp đa chuỗi ADN của Người, Mèo, Khỉ, Chó, Ngựa, Gà và Vịt với các phép thay thế ở vị trí
số 2, 3, 11, 13 và phép chén / xóa ở vị trí số 7 và số 10..............................................................................2
Bảng 2: Các chương trình bắt cặp đa chuỗi phổ biến nhất hiện nay..........................................................3
Bảng 3: Kiểm tra các MUSCLE, FFT-NS2, FFT-NS1 với các test có số lượng chuỗi từ 200 đến 500 chuỗi. 18
Bảng 4: Kiểm tra FFT-NS2 với các dữ liệu có số lượng chuỗi lớn hơn 400................................................19
Bảng 5: Thời gian chạy của PROBCONS theo tống số amino acid.............................................................19
Bảng 6: Tính toán SP(mi)............................................................................................................................27
Bảng 7: Kết quả các phương pháp với BAliBASE 2.....................................................................................29
Bảng 8: Kết quả các phương pháp với BAliBASE 3 – homologous.............................................................30
Bảng 9: Kết quả các phương pháp với BAliBASE 3 – ful llength................................................................31

hợp giữa công nghệ thông tin và sinh học nhằm phục vụ nhiều mục đích khác nhau.
Trong số đó, việc nghiên cứu phân tích trình tự (chuỗi AND và protein) đóng một vai
trò vô cùng quan trọng. Để đơn giản cho việc nghiên cứu, các trình tự DNA, protein
được tuần tự hóa và nghiên cứu dưới dạng chuỗi các kí tự. Khi một gen mới được phát
hiện, một trong những yêu cầu quan trọng là làm sao tìm được chức năng, tác dụng của
gen này, yêu cầu tương tự cũng được đặt ra với các amino acid mới. Một phương pháp
đơn giản để xử lý yêu cầu này là so sánh, đánh giá sự giống nhau (tương đồng) của các
chuỗi mới tìm ra với các chuỗi đã biết, từ đó ta có thể đưa ra dự đoán về các chức năng
của những chuỗi mới phát hiện này. Do đó, sắp hàng đa chuỗi (multiple sequence
alignment) các đoạn ADN / protein là một trong những bài toán phổ biến và quan trọng
nhất trong sinh học phân tử và các lĩnh vực liên quan. Sắp hàng đa chuỗi giúp chúng ta
giải quyết một số vấn đề sau:
- Tìm kiếm và chẩn đoán chức năng cho các chuỗi ADN / protein mới giải mã
1
- Tìm kiếm và chẩn đoán cấu trúc bậc cao cho chuỗi ADN / protein mới giải mã
- Phân tích phép biến đổi để xây dựng quá trình tiến hóa giữa các loài sinh vật.
- Xác định các vị trí biến đổi dẫn đến các bệnh liên quan đến di truyền, để từ đó
tìm ra phương pháp phát hiện và cứu chữa.
Trong quá trình tiến hóa, có 3 phép biến đổi phổ biến trên một trình tự: (1) thay
thế, (2) chèn, (3) xóa. Các phép biến đổi này làm cho các chuỗi tương đồng bị biến đổi
cả về nội dung cũng như kích thước. Sắp hàng đa chuỗi là quá trình chèn thêm các dấu
cách (biểu diễn cho nhưng amino acid bị xóa khỏi chuỗi trong quá trình tiến hóa) vào
các chuỗi sao cho tất cả các amino acid ở cùng một ví trí thì tương đồng. Sau khi sắp
hàng, tất cả các chuỗi đều có độ dài bằng nhau. Kết quả, ta sẽ thu được một tập các
chuỗi gọi là một ‘đa chuỗi thẳng hàng’ ( sequences alignment ). Ví dụ dưới đây thể
hiện một đa chuỗi thẳng hàng của 7 đoạn ADN của 7 loài sinh vật là Người, Mèo, Khỉ,
Chó, Ngựa, Gà và Vịt. Phân tích cho thấy ở vị trí thứ 2 tồn tại phép biến đổi giữa ‘C’
của nhóm động vật ( Người, Mèo, Khỉ, Chó ) và ‘G’ của nhóm động vật ( Ngựa, Gà, Vịt
). Tương tự như vậy ta thấy tồn tại các phép biến đổi ở các vị trí 3, 4, 11 và 13. Ở vị trí 7
và số 10, ta quan sát thấy phép biến đổi chèn / xóa ‘G’ và ‘C’ tương ứng.

thẳng hàng hoàn chỉnh. Tiếp theo CLUSTALW[3], nhiều phương pháp khác đã được đề
xuất. Những phương pháp cho kết quả tốt nhất hiện nay là:MAFFT[4], PROBCONS[5],
và MUSCLE[6]. Trong đó MAFFT[4] là phương pháp mới được phát triển bao gồm
khá nhiều chương trình con cho các yêu cầu khác nhau.
Bảng 2: Các chương trình bắt cặp đa chuỗi phổ biến nhất hiện nay.
Chương trình Ưu điểm Nhược điểm
CLUSTALW[3]
Tiết kiệm bộ nhớ, có khả
năng chạy các test có chuỗi
có độ dài lớn.
Kém hơn về độ chính xác và tốc
độ so với một số chương trình
mới
MUSCLE[6]
Đạt độ chính xác khá cao và
tốc độ nhanh với kích thước
dữ liệu vừa phải.
Đối với những tập dữ liệu lớn
(>1000 chuỗi), nên chạy với cấu
hình tiết kiệm thời gian và bộ
nhớ
PROBCONS[5]
Cho độ chính xác cao khi
kiểm tra với một vài bộ dữ
liệu chuẩn.
Hạn chế về tốc độ và bộ nhớ,
không có khả năng thực hiện với
những bộ dữ liệu lớn (>100
chuỗi)
MAFFT[4] Phát triển với nhiều tùy Hạn chế về tốc độ với những yêu

- Tạo cây hướng dẫn (guide tree).
- Progressive alignment.
2.1.1 Tính toán ma trận khoảng cách giữa mọi cặp chuỗi
Tại bước này, mọi cặp chuỗi được bắt cặp với nhau, sau đó tính khoảng cách giữa
từng cặp chuỗi. Việc này được thực hiện bằng cách sử dụng phương pháp tính toán xấp
xỉ nhanh[7]. Phương pháp này cho phép một số lượng lớn các chuỗi được sắp hàng. Còn
điểm khoách cách được tính bằng cách: tính số lượng k-tuple khớp với nhau (các đoạn
giống hệt nhau, thường có độ dài 1 hoặc 2 cho protein và 2 hoặc 4 cho chuỗi nucleotide)
trong kết quả tốt nhất của 2 chuỗi sắp hàng và trừ đi điểm phạt cho việc chèn gap.
2.1.2 Tạo cây hướng dẫn (guide tree)
Từ bước 1, ta có ma trận khoảng cách giữa mọi cặp chuỗi. Cây hướng dẫn (guide
tree) cho bước tiếp theo được tạo ra nhờ phương pháp Neighbour-Joining[8]. Đây là một
thuật toán lặp. Mỗi lần lặp thuật toán chạy qua các bước sau:
- Căn cứ vào ma trận khoảng cách hiện tại (ở đây là ma trận có ở bước 1) ta tính
toán ma trận khoảng cách Q (được định nghĩa dưới đây).
- Tìm các cặp phần tử mà có giá trị khoảng cách Q nhỏ nhất. Tạo nên một nút
trên cây và kết hợp 2 phần tử này thành một nút. 2 phần tử này được gọi là
“hàng xóm”.
- Tính toán khoảng cách của 2 “hàng xóm” với nút mới.
- Tính toán khoảng cách của các nút bên ngoài với nút mới này.
5
- Quay lại bước 1 với ma trận khoảng cách được tính từ bước trước.
Thuật toán dừng lại khi chỉ còn lại một nút duy nhất, và nút này trở thành gốc của
cây hướng dẫn (guide tree).
Ở đây, ta định nghĩa:
Ma trận khoảng cách ban đầu có r phần tử. d(i, j) là khoảng cách giữa i và j trong
ma trận đó.
Khi đó khoảng cách Q giữa i và j được tính:
1 1
( , ) ( 2) ( , ) ( , ) ( , )

hàng các chuỗi từ nút lá cho đến gốc của cây. Mỗi bước sẽ là quá trình sắp hàng 2 nhóm
chuỗi đã được sắp hàng trước đó sử dụng thuật toán quy hoạch động [9] [10]. Gap ở
những nhóm chuỗi này được giữ nguyên trong kết quả tạo thành. Việc này lặp đi lặp lại
cho đến khi gặp gốc của cây hướng dẫn. Đó là kết quả cuối cùng.
6
2.2. MUSCLE
2.2.1 Các loại khoảng cách và các cách xây dựng cây hướng dẫn
MUSCLE[6] sử dụng hai cách để xác định khoảng cách giữa các chuỗi đó là
khoảng cách K-mer[11] cho những cặp chuỗi chưa được sắp hàng và khoảng cách
Kimura[12] cho những cặp đã được sắp hàng (có độ dài bằng nhau).
K-mer[11] được định nghĩa là một chuỗi có độ dài bằng K của các amino acid
đứng liền kề nhau. Thuật toán sử dụng K-mer không đòi hỏi cặp chuỗi cần phải sắp
hàng mà ưu điểm lớn của nó là kết quả thu được với tốc độ khá cao (độ phức tạp thuật
toán là O(L) với L là độ dài của chuỗi) [11].
Hình 1: Ví dụ về k-mer [6]
Hình 1 thể hiện một ví dụ của K-mer, với K = 3, ở các chuỗi trên dễ dàng nhận
thấy K-mer là 6 và tại các chuỗi ở phần dưới K-mer là 13. Tương tự như vậy với K = 4
các chuỗi bên trên K-mer là 4 và các chuỗi dưới K-mer là 9.
Khoảng cách Kimura[12] giữa 2 chuỗi đã được sắp hàng (có độ dài bằng nhau)
được tính theo công thức sau:
D
K2p
= -1/2 ln(1-2P-Q) – ¼ ln(1/2Q)
Ở đây, P là số lượng transition và Q là số lượng transversion trong hai chuỗi.
Transition là một phép thay thế khi thay A bởi G, C bởi T hoặc ngược lại. Trong khi đó
Transversion là phép thay thế A bởi C hoặc T hay các trường hợp tương tự.
7
Sau khi xây dựng xong ma trận khoảng cách, MUSCLE[6] sử dụng thuật toán
UPGMA[13] để nhóm các chuỗi lại với nhau. UPGMA[13] là một thuật toán xây dựng
cây hướng dẫn cho việc sắp hàng từng profile. Đầu vào của UPGMA[13] là một ma trận

xy
= (1 - f
x
G
)(1- f
y
G
) log ∑
i
∑
j
f
x
i
f
y
i
p
ij
/p
i
p
j
MUSCLE[6] sử dụng các tham số p
i
và p
ij
là các tham số của ma trận 240 PAM
VTML [14].
2.2.3 Thuật toán