TRƯỜNG ………………….
KHOA……………………….

[\[\

Báo cáo tốt nghiệp
Đề tài:

SẮP HÀNG ĐA CHUỖI












Lời cảm ơn


Tôi xin bày tỏ lòng biết ơn sâu sắc nhất tới Tiến sỹ Lê Sỹ Vinh. Thầy là
người trực tiếp giao đề tài và tận tình hướng dẫn cũng như giúp đỡ tôi trong quá
trình thực hiện luận văn này.
Đồng thời tôi xin chân thành cảm ơn thầy Từ Minh Phương, hiện đang
công tác tại SUlab công ty FPT. Thầy đã tạo điều kiện và đưa ra những lời
khuyên bổ ích cho tôi trong thời gian cuối thực hiện khóa lu

ận.




Hà Nội tháng 05 năm 2010
Sinh viên
Nguyễn Hà Anh Tuấn
Tóm tắt nội dung


Sắp hàng đa chuỗi là một bài toán tin sinh học phổ biến trên thế giới hiện nay,
mặc dù đã có rất nhiều phương pháp tiếp cận cũng như thuật toán được đưa ra để giải
quyết bài toán này tuy nhiên chưa thuật toán nào cho kết quả tới khả năng tối ưu.
Trong nội dung của khóa luận, tôi xin được khái quát tổng quan bài toán sắp hàng đa
chuỗi cũng như một số thuật toán tiêu biểu trên th
ế giới hiện nay. Đồng thời tôi cũng
xin đưa ra một số ý kiến của mình cũng như giải pháp nhằm tăng tính ổn định và tin
cậy của các thuật toán này.

Mục lục
Chương 1: Giới thiệu chung 1
Chương 2: Các phương pháp phổ biến hiện nay 6
1.MUSCLE 6
2.MAFFT 8
3. ProbCons 10
Chương 3: EM-Coffee (Extended M-Coffee) 12
1.Đặt trọng số khi kết hợp các thuật toán 12
2.MUMSA 13
3.T-Coffee, M-Coffee 14

3.1. T-Coffee 14
3.2. M-Coffee 20
4.EM-Coffee 21
Chương 4: Kết quả thực nghiệm 23
1. Bộ dữ liệu BAliBASE 23
Chương 5: Kết luận 31
Tài liệu tham khảo 32


Page | 1

Chương 1: Giới thiệu chung

Phần giới thiệu về sắp hàng đa chuỗi( multiple sequence alignment) dưới đây
được viết một phần dựa trên luận văn tiến sĩ của thầy Lê Sỹ Vinh[31] và quyển sách
Inferring Phylogenies của giáo sư Joseph Felsenstein[30].
Theo học thuyết tiến hóa của Darwin[1], tất cả các sinh vật trên trái đất đều có
cùng một tổ tiên chung. Theo thời gian và quá trình tiến hóa của các sinh vật, các
ADN của chúng dần đổi khác biệt với tổ tiên. Các ADN biến đổi t
ừ cùng một nguồn
gốc được gọi chung là các ADN tương đồng(homology). Và tổng quát hơn nữa, một
chuỗi ADN tiến hóa từ cùng một tổ tiên là chuỗi tương đồng. Những sự biến đổi của
các chuỗi ADN có thể nhiều hay ít, có thể xảy ra đồng thời hay phân tán tuy nhiên
chúng vẫn giữ lại một số thông tin có trong chuỗi ADN của tổ tiên. Theo nhận định
của các nhà khoa học, việc biến
đổi ADN của các sinh vật đều thông qua 3 phép biến
đổi sau:
− Phép chèn, đưa thêm một ADN vào chuỗi.
− Phép xóa, xóa đi 1 ADN trong chuỗi.
− Phép thay thế, thay thế ADN này bằng một ADN khác.

Trong khi các phép thay thế chỉ làm thay đổi những vị trí nhất định của một chuỗi
ADN chứ không làm thay đổi độ dài của chuỗi ADN đó, một phép chèn hay một phép
xóa lại làm cho số lượng ADN của chuỗi nhiều hơn một ADN hoặc ít đi mộ
t ADN.
Tuy nhiên, chúng ta không thể xác định được sự khác biệt giữa phép chèn và phép xóa
nên 2 phép này được gộp lại thành một phép biến đổi và gọi tên chung cho chúng là
phép chèn/xóa.
Bảng 1 là ví dụ về các phép biến đổi giữa 2 chuỗi ADN s1 và s2. Trong ví dụ này
ta có thể thấy tại vị trí thứ 2 và vị trí thứ 3 có thực hiện phép biến đổi thay thế ( C – A
và A – G) đồng thời tại vị trí thứ 7 xác định được một phép chèn/xóa. Tại các vị trí còn
lại ta có thể thấy s
ự tương đồng giữa 2 chuỗi s1 và s2, chẳng hạn tại vị trí 1 cả 2 chuỗi
s1 và s2 đều là A hay tại vị trí 4 là G.

Page | 2

Bảng 1: Ví dụ về các phép biến đổi
1 2 3 4 5 6 7 8 9
s1 A
C A
G C T
G
G T
s2 A
A G
G C T - G T

Thông thường đặc điểm của sinh vật dựa vào cấu chúc chuỗi ADN của chúng,
như vậy khi xuất hiện một phép biến đổi bên trong chuỗi ADN thì đặc điểm của sinh
vật sẽ bị biến đổi. Sự thay đổi này có thể là những dấu hiệu bên ngoài giúp chúng ta có

thể xác định điểm khác biệt hoặc chỉ là sự biến đổi bên trong sinh vật và cần tập trung
nghiên cứu mớ
i nhận ra sự biến đổi này. Khi sự biến đổi là quá lớn, rất có thể một loài
sinh vật hoàn toàn mới sẽ xuất hiện. Chính vì vậy sự xuất hiện của các chương trình
sắp hàng đa chuỗi hay bắt cặp đa chuỗi (multiple sequence alignment) là rất quan
trọng trong lĩnh vực sinh học nói chung và sinh học phân tử nói riêng (molecular
biology). Dựa vào kết quả của các chương trình này các nhà khoa học có thể đi tới
những kết luậ
n đối với các chuỗi ADN và axit amin tương ứng như sau:
− Xác định và chẩn đoán được chức năng mà đoạn ADN/axit amin
này thực hiện trong cơ thể sinh vật.
− Xác định các vị trí biến đổi liên quan tới các bệnh di truyền để từ đó
tìm kiếm phương pháp phát hiện và cứu chữa
− Phân tích các 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 và chẩ
n đoán các cấu trúc bậc cao cho ADN/axit amin mới
giải mã được.
Các phép biến đổi thường làm cho chuỗi ADN(có thể là protein) tương đồng bị
biến đổi cả về kích thước lẫn nội dung của nó. Khi đó ta có thể định nghĩa một cách
đơn giản của việ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
một phép chèn/xóa trong quá trình tiến hóa) vào các chuỗi sao cho tất cả các ADN(axit

Page | 3

amin) ở cùng một vị trí thì tương đồng với nhau. Tuy dữ liệu đầu vào của một chương
trình sắp hàng đa chuỗi thường là có độ dài các chuỗi khác nhau, nhưng kết quả của
chúng luôn cho ra những chuỗi ADN(protein) có độ dài bằng nhau, kết quả này còn
được gọi là “đa chuỗi thẳng hàng”.
Chẳng hạn ta có 4 chuỗi cần được thực hiện sắp hàng đa chuỗi như sau

Bảng 2: Ví dụ của sắ
p hàng đa chuỗi
s1
= GCTGATATAG C
s2
= G G G T G A T T A G C
s3
= G C T A T C G C
Input
s4
= AGCGGAACAC C
s1’
= –
G
CTG
A
TATA G
C
s2’
= G
G
GTG
A
T– TA G
C
s3’
= –
G
CT–
A

T– –C G
C
Kết quả
s4’
= A
G
CGG
A
– A C A C
C
Như chúng ta nhận thấy độ dài của các chuỗi s1, s2 và s4 là khác so với độ dài
của chuỗi s3. Tuy nhiên kết quả thu được thì độ dài của cả 4 chuỗi là tương đương
nhau. Ngoài ra chúng ta cũng có thể dễ dàng phát hiện được những phép biến đổi được
thực hiện khi nhìn vào kết quả của chương trình sắp hàng đa chuỗi. Chẳng hạn có một
phép chèn/xóa tại vị trí thứ nhất của s1’ và s3’ hay một phép thay thế C bởi G t
ại s2’.
Tương tự như vậy là các phép chèn xóa hay các phép thay thế còn lại.
Một điều có thể nhận ra trong sắp hàng đa chuỗi đó chính là tồn tại nhiều cách
chèn dấu cách khác nhau và khi đó ta có thể tạo ra nhiều kết quả khác nhau. Việc tồn
tại nhiều phép biến đổi khác nhau này có thể được cải thiện bằng cách sử dụng mắt
thường và dựa trên kinh nghiệm để bắt cặp. Tuy nhiên, cách thức này chỉ có th
ể áp
dụng được với những chuỗi ADN ngắn vào số lượng chuỗi bắt cặp nhỏ. Đối với những

Page | 4

trường hợp bắt cặp hàng trăm chuỗi và độ dài mỗi chuỗi lớn thì việc làm thủ công trên
trờ nên không khả thi và mất tính hiệu quả ban đầu của nó. Để giải quyết bài toán này
người ta đã đưa ra rất nhiều phương pháp tính toán và nghiên cứu nhằm mục đích tối
ưu hóa bắt cặp đa chỗi. Các phương pháp này thường tiến hành sao cho nó tiến tới sấp

xỉ một hàm mục tiêu cho trước. Hàm mụ
c tiêu đơn giản nhất được đưa ra là cực tiểu
hóa các phép biến đổi tồn tại giữa các cặp chuỗi sau khi sau khi đã bắt cặp xong.
Tuy nhiên vẫn còn một vấn đề khá nan giải đó là việc rất khó để bắt cặp những
chuỗi có sự liên hệ lẫn nhau thấp một cách chính xác mà không cần sự chỉnh sửa bằng
tay dựa trên kinh nghiệm của các nhà khoa học. Đề giải quyết vấn
đề này có rất nhiều
phương án đã được đưa ra trong vòng 4 tới 5 thập kỉ qua. Năm 1970 Needleman và
Wunsch[2] đã đưa ra một thuật toán để so sánh chuỗi ADN dựa trên quy hoạch động,
thuật toán này giúp ta có khả năng bắt cặp 2 chuỗi ADN (pairwise alignment) và thu
được một kết quả khá tốt. Mặc dù vậy việc mở rộng bài toán này lên thành sắp hàng đa
chuỗi (multiple sequence alignment) lại là một câu chuyện hoàn toàn khác bởi độ phức
tạp của thuật toán là N
k
(trong đó k là số lượng chuỗi dùng để bắt cặp và N là độ dài
của chuỗi). Sau đó một số phương pháp mới cũng được đưa ra, trong đó có phương
pháp progessive[3] hay phương pháp chuẩn hóa lặp (iterative refinement)[4-5]. Các
phương pháp này đều dựa trên các biến thể của quy hoạch động 2 chiều (two-
dimentional dynamic programing) và giảm được độ phức tạp của bài toán xuống còn
N
2
. Việc giảm được độ phức tạp của bài toán xuống còn N
2
là một thành tựu rất lớn
nhưng độ chính xác của sắp hàng đa chuỗi còn dựa trên chính hệ thống tính điểm của
mỗi chương trình, hệ thống tính điểm càng chính xác thì độ chính xác của kết quả nó
đưa ra càng cao. Nói tới hệ thống tính điểm này ta không thể không nhắc tới ClustalW,
một phương pháp được phát triển bởi Thompson và các đồng nghiệp năm 1994[6].
ClustalW sử dụng cách tính toán hệ thống đi
ểm phạt (điểm phạt cho các phép biến đổi)

và hàm mục tiêu của ClustalW là làm nhỏ nhất có thể điểm phạt này. Đây chính là một
trong những phương pháp đi tiên phong cho hệ thống điểm phạt ngày nay.
Hiện tại, các phương pháp được phát triển nhằm mục đích giải quyết bài toán sắp
hàng đa chuỗi ngày càng xuất hiện nhiều hơn. Mỗi thuật toán đều có khả năng chính
xác và tính tin cậy khác nhau. Nh
ững phương pháp nổi bật nổi bật bởi độ chính xác
của chúng có thể kể đến như: T-Coffee[7], MAFFT[8,14], PROBCONS[9], và
MUSCLE[10]. Trong MAFFT nổi lên như một chương trình rất được ưa chuộng hiện

Page | 5

nay nhờ vào tốc độ thực thi và độ tin cậy của thuật toán. Việc đánh giá độ tin cậy của
một phương pháp hay thuật toán cần phải dựa trên một bộ dữ liệu chuẩn chứa đồng
thời các chuỗi chưa được sắp hàng và dữ liệu chuẩn để đối sánh. Những bộ dữ liệu này
thường là những bộ dữ liệu được trích chọn trong quá trình nghiên cứu củ
a các nhà
khoa học hoặc được các nhà khoa học sử dụng kinh nghiệm của mình để xác định.
Kết luận: Mặc dù việc sắp hàng đa chuỗi đã được nghiên cứu và phát triển từ rất
lâu nhưng nó vẫn là một bài toán cần được nghiên cứu và tiếp tục phát triển để giải
quyết được các nhu cầu hiện tại cũng như trong tương lai gần. Mỗi phương pháp sắp
hàng đa chu
ỗi đều có những ưu và nhược điểm riêng của nó và quan trọng hơn nữa là
mỗi chỉ phù hợp với những kiểu dữ liệu nhất định. Chính vì vậy việc tập trung nghiên
cứu nhằm mục đích cải thiện độ chính xác của các phương pháp này là điều rất cần
thiết.

Page | 6

Chương 2: Các phương pháp phổ biến hiện nay


Sau đây, tôi xin trình bày tổng quan một số chương trình sắp hàng đa chuỗi tiêu
biểu hiện nay trên thế giới. Các chương trình này đều đã khẳng định được khả năng
của mình và được áp dụng khá nhiều trong lĩnh vực sinh học nói chung và sinh học
phân tử nói riêng.
1.MUSCLE
MUSCLE là chương trình sắp hàng đa chuỗi được phát triển bởi David Edgar
năm 2004. Hiện tại MUSCLE đang được sử dụng khá rộng rãi bởi độ chính xác khá
cao và tốc độ của chương trình có thể hỗ trợ người sử dụng với bộ dữ liệu lớn tới hàng
ngàn chuỗi. Về mặt thuật toán, ta có thể chia thuật toán của MUSCLE ra làm ba bước
chính đó là bước bắt cặp nháp, cải tiến, và bước chu
ẩn hóa lại. Ngoài ra tác giả đưa ra
hai hệ thống tính điểm khác nhau đó là khoảng cách K-mers[11] cho bộ chuỗi chưa
được bắt cặp với nhau và ma trận KIMURA[12] cho các chuỗi đã bắt cặp rồi.

Hình 1: khoảng cách K-mers[10]
K-mer được định nghĩa là một chuỗi các amino axit đứng liền kề nhau có độ dài
bằng K. Đối với những sequence có liên hệ với nhau thì số lượng K-mer sẽ nhiều hơn
các cặp sequence bình thường. Khoảng cách K-mers được định nghĩa dựa trên định
nghĩa của K-mer khi ta sử dụng nó trong chuỗi kí tự. Phương pháp sử dụng K-mer này
không đòi hỏi các chuỗi đã được align hay chưa và thu được kết qu
ả với tốc độ khá

Page | 7

cao. Hình 2 là một ví dụ cho khoảng cách K-mers, với K = 3 ta thu được tại phần trên
K-mer là 6 và phần dưới K-mer là 13. Tương tự như vậy với K=4 tại phần trên K-mer
là 4 và dưới là 9.
Khoảng cách KIMURA[12] được định nghĩa là khoảng cách giữa 2 chuỗi đã được
bắt cặp và được tính theo công thức:
2

111
ln(1 2 ) ln( )
242
Kp
DPQQ=− − − −
Trong đó, P là số lượng transition đếm được giữa 2 chuỗi và Q là số lượng
transversion đếm được giữa 2 chuỗi. Transition là dạng thay thế A – G hay C – T hoặc
ngược lại. Trong khi đó Transversion là dạng thay thế A – C, T hay các trường hợp
tương tự như vậy.
Ngoài ra, còn một điểm đáng lưu ý ở MUSCLE đó là bắt cặp profiles (profile
alignment). Đây là một dạng bắt cặp tương tự như b
ắp cặp sóng đôi (pairwise
alignment) nhưng mỗi profile không còn là một chuỗi như bắt cặp sóng đôi mà là
nhiều chuỗi được ghép vào.

Hình 2: Các bước chạy của MUSCLE[10]
Ở các bước một và hai của MUSCLE lần lượt sử dụng 2 hệ thống điểm là khoảng
cách K-mers và ma trận KIMURA để dựng cây nhị phân dựa trên thuật toán

Page | 8

UPGMA[13]. Mỗi nút trên cây được ghép lại bởi 2 profile và tạo ra một profile mới
cho. Cứ làm như vậy cho tới gốc cuối cùng thì ta sẽ đạt được một alignment. Và đến
đây coi như chúng ta đã hoàn thành việc sắp hàng đa chuỗi nếu người sử dụng không
muốn chạy bước chuẩn hóa.
Bước cuối cùng của MUSCLE là bước chuẩn hóa (refinement). Dựa trên cây
được dựng sau hai bước trên bước này sẽ cắt bỏ một cạnh từ
cây đó sau đó bắt cặp lại
2 profiles và sử dụng điểm sum of pair để tính toán nếu có cải thiện với điểm của kết
quả trên thì giữ lại, nếu không thì bỏ đi. Điểm sum-of-pair là điểm để xác định khả

năng bắt cặp giữa 2 chuỗi sẽ được nói tới sau trong phần kết quả thực nghiệm sử dụng
BAliBASE.
Về độ
phức tạp của thuật toán, nếu ta chỉ chạy 2 bước đầu thì độ phức tạp thuật
toán sẽ là O(N
2
+ NL + L
2
). Nếu có thêm bước chuẩn hóa lại thì độ phức tạp thuật toán
là O(N
3
L). trong đó N là số chuỗi cần bắt cặp, L là độ dài của chuỗi.
Dựa theo kết quả thực nghiệm sẽ nêu ở phần sau của tài liệu này, MUSCLE có
tốc độ chạy rất tốt và có thể chạy được với bộ dữ liệu lớn, cỡ từ 1 tới vài nghìn cuỗi.
2.MAFFT
MAFFT là viết tắt của Multiple Alignment using Fast Fourier Transform được
đưa ra năm 2002 bởi một nhóm các tác giả người Nhật. Tại thời điểm hiện tại, MAFFT
được đánh giá rất cao nhờ vào độ chính xác gần như là cao nhất trên những chuỗi full-
length của bộ dữ liệu chuẩn BAliBASE đồng thời MAFFT cũng yêu cầu một thời gian
để chạy tương đối dễ chịu với người sử dụng.
Khác vớ
i các phương pháp khác, các tác giả của MAFFT sử dụng giả thuyết tần
suất sự thay thế các amino axit phụ thộc lớn vào các thuộc tính lý hóa của nó, đặc biệt
là 2 thuộc tính khối lượng(volume) và độ phân cực(polarity) [13]. Dựa trên 2 thuộc
tính này người ta dựng nên 2 giá trị chuẩn hóa v(a) và p(a) tượng trưng lần lượt cho
khối lượng và độ phân cực. Tiếp theo mối quan hệ giữa 2 chuỗi amino axit sẽ được
tính toán b
ằng cách sử dụng biến đổi Fourier. Ý nghĩa chính của biến đổi Fourier ở
bước này chính là giúp giảm độ phức tạp của thuật toán. Sau bước này ta sẽ thu được
các giá trị c(k)[14] – tượng trưng cho mối quan hệ giữa 2 chuỗi, ở đây k là độ trễ của

chuỗi 2 so với chuỗi 1 như hình 3.

Page | 9


Hình 3: độ trễ k và tìm kiếm đoạn tương đồng[14]
Từ hình vẽ ta có thể thấy nếu k bằng 2 thì chuỗi 1 sẽ đi trước chuỗi 2 khi bắt cặp
với nhau để tìm đoạn tương đồng. Mặt khác bằng thực nghiệm cho thấy, c(k) càng lớn
thì khả năng tìm được những đoạn tương đồng khi sắp xếp 2 chuỗi theo độ trễ k càng
lớ
n. Và từ những đoạn tương đồng tìm được người ta xây dựng một ma trận tương
đồng để từ đó có thể bắt cặp 2 chuỗi amino axit này lại với nhau (cách xác định đoạn
tương đồng và xây dựng ma trận tương đồng có thể đọc thêm ở tài liệu tham khảo số
14). Hình 4 biểu diễn một ma trận tương đồng

Hình 4, ma trận tương đồng[14]
Trong trường hợp này, đường bắt cặp được sử dụng là S(5,5) -> S(4,4) -> S(2,3)
-> S(1,1) vì giá trị của S(2,3) lớn hơn giá trị của S(3,2).

Page | 10

Cũng giống như MUSCLE, để mở rộng bài toán từ bắt cặp sóng đôi lên sắp hàng
đa chuỗi, MAFFT sử dụng bắt cặp profile – profile. Bằng cách tính toán lại c(k) cho
mỗi cặp profile và xác định đoạn tương đồng cũng như ma trận tương đồng ta có thể
hoàn thành các bước sắp hàng đa chuỗi của option đơn giản nhất MAFFT là FFT-Ns1.
Các option còn lại của MAFFT hầu hết đều sử dụng kết quả
của FFT-Ns1 và sử dụng
các bước chuẩn hóa để thu được kết quả tốt hơn FFT-Ns1.
Theo phiên bản mới nhất của MAFFT, chúng ta có thể có nhiều option để chọn
lựa như FFT-Ns2, FFT-Nsi, Li-Nsi, Ei-Nsi, …. Mỗi option có thể đáp ứng cho người

dùng những yêu cầu nhất định. Chẳng hạn đối với option FFT-Ns2 tốc độ bắt cặp là rất
cao, nhanh hơn cả MUSCLE tuy nhiên lại thu được kết quả không tốt lắm. Để
thu
được kết quả tốt hơn, ta có thể sử dụng option Li-nsi của MAFFT. Option này tuy
chạy chậm hơn MUSCLE nhưng lại có kết quả đáng tin cậy hơn.
3. ProbCons
ProbCons có tên đầy đủ là Probabilistic consistency-based multiple sequence
alignment. Đây là phần mềm sắp hàng đa chuỗi được tác giả gốc Việt Nam là Chương
Đỗ, và các đồng nghiệp phát triển và lần đầu được công bố năm 2005. Cũng như
MUSCLE và MAFFT, ProbCons cũng là một chương trình rất thông dụng và được sử
dụng rộng rãi hiện nay. ProbCons có khả năng trả về một kết quả chính xác cao tuy
nhiên về mặt tốc độ ProbCons không thể được như
MAFFT và MUSCLE.
Về mặt thuật toán, ProbCons đưa mô hình Markov ẩn vào thuật toán progressive.
Điểm khác biệt chính giữa ProbCons và các phương án tiếp cận khác đó chính là việc
sử dụng ước lượng cực đại về độ chuẩn xác chứ không phải là cách sử dụng mô hình
Viterbi[15], mặt khác ProbCons còn sử dụng ước lượng các phép biến đổi để bảo toàn
thông tin của các chuỗi trong khi bắt cặp. Ngoài ra ProbCons sử dụng ma trận chuyển
đổi chuẩn BLOSUM62[16] và đi
ểm phạt phát sinh khi thêm dấu cách trong việc bắt
cặp cũng được huấn luyện bởi ước lượng cực đại. Để thực hiện sắp hàng đa chuỗi,
ProbCons cần phải thực hiện qua ít nhất là 5 bước(thuật toán chi tiết có thể đọc thêm ở
tài liệu tham khảo số 9). Các bước này sẽ được trình bày một cách tổng quát nhất như
sau:


Page | 11

− Bước 1: Xây dựng ma trận xác suất P
xy

(i,j) trong đó x,y là 2 chuỗi bất kì
cần phải bắt cặp, i và j lần lượt là vị trí của kí tự trong 2 chuỗi x,y.
− Bước 2: Tính toán kì vọng của độ chính xác khi bắt cặp 2 chuỗi x, y. Với
mỗi cặp chuỗi x, y xác định một kết quả bắt cặp 2 chuỗi này sao cho kì
vọng của cách bắt cặp này là cao nhất.
− Bước 3: Ước l
ượng tính vững chắc của các bước chuyển đổi. Ở bước
này, ma trận xây dựng ở bước 1 sẽ được tính toán và chuẩn hóa lại.
− Bước 4: Xây dựng cây cho các chuỗi cần bắt cặp bằng thuật toán phân
cụm, trọng số sẽ được tính toán dựa trên giá trị tính ở bước 2.
− Bước 5: Dựa vào cây đã dựng ở bước 4, ta tiến hành bắt cặp cho cả bộ
d
ữ liệu.
Ngoài ra còn có thể có thêm bước chuẩn hóa lại kết quả, bước chuẩn hóa này sẽ
cắt kết quả làm 2 phần và tiến hành bắt cặp lại. Số lần bước chuẩn hóa thực hiện là
không xác định trước.
Kết quả của Proncons là rất đáng tin cậy, nó sẽ được thể hiện trong phần thực
nghiệm sẽ được trình bày ở phần sau bản báo cáo này. Tuy nhiên, về mặt tốc
độ
ProbCons không thể so sánh với 2 thuật toán trên và có lẽ chỉ nên chạy ProbCons với
những dữ liệu không vượt quá 50 chuỗi và có độ dài tối đa của chuỗi nằm trong
khoảng 500 axit amin.

Page | 12

Chương 3: EM-Coffee (Extended M-Coffee)


1.Đặt trọng số khi kết hợp các thuật toán
Ba thuật toán đã được nêu ra trong chương 2 chính là ba phương pháp được sử

dụng phổ biến nhất cho việc sắp hàng đa chuỗi hiện nay trên thế giới. Mỗi phương
pháp đều có những ưu điểm và nhược điểm riêng của nó. Tuy nhiên, điều cần quan
tâm nhất đó chính là mỗi phương pháp đưa ra kết quả tốt nhất với những bộ dữ liệu
nhất định. Chúng không cho v
ề kết quả ổn định và đáng tin cậy trong mọi trường hợp
có thể xảy ra trong bộ dữ liệu.
Việc đánh giá ba thuật toán sẽ được tóm tắt lại trong bảng sau:
Bảng 3: nhận định về các thuật toán.
Thuật toán Ưu điểm Nhược điểm
Muscle

Tốc độ cao, có thể chạy với bộ dữ
liệu lớn
Độ chính xác của muscle với
các bộ dữ liệu chuẩn so với
các thuật toán khác là không
cao
ProbCons
Độ chính xác và tính tin cậy của
ProbCons là lớn
Tốc độ chậm, chỉ có thể chạy
với những bộ dữ liệu nhỏ
MAFFT
Có độ chính xác khá cao, nhiều
option ứng với những bộ dữ liệu
riêng đồng thời tốc độ chấp nhận
được
Với những option có độ chính
xác cao thì tốc độ không tốt,
và ngược lại.

Chính vì việc mỗi thuật toán đều có độ chính xác trên những bộ dữ liệu nhất định
trong khi những dữ liệu cần phải được bắt cặp là rất đa dạng. Ta cần tìm cách kết hợp
kết quả các thuật toán trên với nhau để đưa ra một kết quả mới với hi vọng kết quả này
có được độ tin cậy trên càng nhiều bộ dữ liệu càng tốt.

Page | 13

Vậy bài toán của chúng ta hiện nay chính là tìm cách sử dụng ba thuật toán trên
cũng như kết quả của nó trong mỗi lần sắp hàng đa chuỗi để tạo ra một kết quả mới có
độ chính xác với kì vọng là cao hơn và có khả năng ổn định trên nhiều bộ dữ liệu chứ
không còn như từng thuật toán chỉ chạy tốt với một số bộ dữ liệu. Tất nhiên mỗi thu
ật
toán đều có độ chính xác của riêng nó và không thể coi kết quả của mỗi thuật toán
trước khi đưa vào sử dụng làm thư viện là như nhau, mỗi thuật toán cần có trọng số
nhất định. Trọng số này không thể dùng mắt thường hoặc kinh nghiệm để đánh giá do
số lượng chuỗi và độ dài mỗi chuỗi trong sắp hàng đa chuỗi không phải là nhỏ.
2.MUMSA
Vào năm 2005, trên thế giới xuất hiện rất nhiều chương trình sắp hàng đa chuỗi,
điều này làm cho người sử dụng không thể xác định chính xác nên chọn chương trình
nào phù hợp cho bộ dữ liệu của mình. Việc nhận định độ tin cậy của một chương trình
sắp hàng đa chuỗi trở thành vấn đề cấp bách. Trong bối cảnh đó Timo Lassmann và
Erik Sonnhammer đã cho ra đời MUMSA[17], chương trình hỗ trợ ngườ
i dùng xác
định được tính tin cậy của một đa chuỗi thẳng hàng mà không cần đến bộ dữ liệu tham
khảo.
Thuật toán của MUMSA dựa trên việc so sánh các đa chuỗi thẳng hàng. Họ đưa
ra một khái niệm đó là cặp amino axit được bắt cặp tương ứng(pair-of-aligned
residues). Chẳng hạn ta có một đa chuỗi thẳng hàng, trong đó amino axit thứ 3 trong
chuỗi 1 được bắt cặp tương ứng vớ
i amino axit thứ 5 trong chuỗi 7 thì 2 amino axit

này được gọi là một cặp amino axit được bắt cặp tương ứng. Như vậy, từ đa chuỗi
thẳng hàng là input đầu vào của chương trình ta có thể tạo ra rất nhiều cặp trên. Chú ý
rằng chúng ta cần chia nhỏ đa chuỗi đầu vào thành các phần nhỏ nhất có thể nhưng
vẫn giữ đủ thông tin của đa chuỗi đó để giảm thiểu số lượng các c
ặp amino axit được
bắt cặp tương ứng.
Để so sánh độ tin cậy của một đa chỗi thẳng hàng trong nhiều đa chuỗi khác,
thuật toán của MUMSA tiến hành tính điểm cho mỗi cặp amino axit được bắt cặp
tương ứng để biểu diễn số lần xuất hiện của chúng trong những đa chuỗi thẳng hàng.
Xét một cặp α bất kì, ta gọi n(α) là số
lần xuất hiện của α trong (m – 1) đa chuỗi thẳng
hàng còn lại đang được so sánh. Một cặp xuất hiện trong tất cả mọi đa chuỗi sẽ cho ta
giá trị n(α) = (m – 1) điều này đồng nghĩa với xác suất cặp α xảy ra trên thực tế là lớn,

Page | 14

và ngược lại một cặp không xuất hiện trong các chuỗi còn lại cho ta kết quả n(α) = 0
hay xác suất cặp α xảy ra trên thực tế là rất nhỏ.
Như vậy với một đa chuỗi A ban đầu, ta có thể dùng giá trị trên cho tất cả các cặp
amino axit được bắt cặp tương ứng của nó để tính toán độ tin cậy của một đa chuỗi
thẳng hàng. Độ tin c
ậy của một đa chuỗi thẳng hàng được tính theo công thức:
MOS(A) =
{
}
()
()|
1
nA
Am

αα
∈
−
∑

(|A| số lượng cặp amino axit tương ứng trong A)
MOS là viết tắt của multiple overlap score và có giá trị biến thiên trong đoạn
[0,1]. Khi MOS(A) = 1 tức là mọi cặp amino axit tương ứng xảy ra trong A đều xảy ra
trong (m – 1) đa chuỗi khác và ngược lại khi MOS(A) = 0 là khi không có cặp amino
axit nào xuất hiện trong A lại xuất hiện trong các đa chuỗi được so sánh với A. Bằng
những kết quả thực nghiệm củ
a mình, các tác giả của MUMSA đã chỉ ra rằng những
đa chuỗi thẳng hàng có điểm MOS cao từ 0.8 trở lên là những đa chuỗi đáng tin cậy và
có thể sử dụng chúng cho những công việc khác. Ngoài ra, những đa chuỗi chỉ có điểm
MOS thấp hơn 0.5 thì có thể có nhiều phần được bắt cặp không chính xác và cần được
chỉnh sửa lại. Chẳng hạn với bộ dữ li
ệu BAliBASE, nếu như kết quả của các chương
trình sắp hàng đa chuỗi có điểm MOS nhỏ hơn 0.5 thì những đa chuỗi mà thuật toán
của nó không thể nhận biết được những đoạn tương đồng đã được bắt cặp một cách
thủ công của bộ dữ liệu này.
Như vậy, mục đích chính của MUMSA là tính toán độ chính xác hay tính tin cậy
của những
đa chuỗi thẳng hàng khi mang chúng so sánh với nhau. Từ kết quả của
MUMSA nếu áp dụng vào giả thuyết sử dụng thư viện từ MAFFT, MUSCLE, và
ProbCons ở trên ta sẽ thu được độ tin cậy của từng thuật toán. Đồng thời từ đó ta cũng
có thể xác định được trọng số của các thuật toán trên dựa vào kết quả của MUMSA
3.T-Coffee, M-Coffee
3.1. T-Coffee
T-Coffee – Tree-based Consistency Objective Function for alignment Evaluation
là phần mềm được công bố và phát triển và năm 2000. Vào thời điểm được công bố,


Page | 15

T-Coffee chính là phần mềm có độ chính xác cao nhất trong các chương trình sắp hàng
đa chuỗi đồng thời tốc độ chạy của T-Coffee là chấp nhận được.
T-Coffee có 2 tính năng chính. Tính năng thứ nhất là nó sử dụng hệ thống dữ liệu
thư viện được sinh ra từ bắt cặp sóng đôi các cặp chuỗi để tạo ra đa chuỗi thẳng hàng
cuối cùng. Tính năng thứ 2 là tối ưu hóa, tính năng này có nhiệm vụ
chọn đa chuỗi
thẳng hàng phù hợp nhất với bộ dữ liệu được đưa vào. Như vậy nhìn chung, T-Coffee
sử dụng thuật toán progressive cùng với khả năng cập nhật thư viện dữ liệu của mình
thông qua mỗi bước thực hiện của nó. Điều này cho phép T-Coffee lấy được sự đơn
giản và tốc độ của thuật toán progressive đồng thời giảm thiểu lỗi x
ảy ra trong quá
trình bắt cặp. Hình 5 ở bên dưới là một lỗi thường xảy ra trong quá trình bắt cặp sử
dụng thuật toán progressive thông thường, trong hình ta có thể thấy sự bắt cặp lỗi của
từ CAT ở chuỗi B.

Hình 5: lỗi xảy ra trong bắt cặp sử dụng thuật toán progressive thông thường[7]
Về mặt thuật toán, T-Coffee có 5 bước chính như hình 6 đó là tạo thư viện chính,
đặt trọng số cho thư viện chính, kết hợp thư viện, mở rộng thư viện, bắt cặp sử dụng
thuật toán progressive. Chúng ta sẽ đi vào từng bước của thuật toán này.


Page | 16


Hình 6: các bước thuật toán của T – Coffee[7]

Page | 17


3.1.1. Tạo thư viện chính
Thư viện chính của T-Coffee là tập hợp các cặp chuỗi thu được nhờ vào quá trình
bắt cặp sóng đôi giữa các chuỗi nằm trong đầu vào. Như vậy với đầu vào có N chuỗi ta
sẽ có N(N – 1)/2 cặp trong thư viện. Trong thư viện mỗi cặp có thể có liên kết với nhau
và một điều cần chú ý đó là mỗi cặp đều có tính quan trọng khác nhau bởi một số có
thể đưa ra những s
ự bắt cặp chính xác cho kết quả sau này. Việc xác định cặp nào
quan trọng, cặp nào không sẽ được tính toán ở bước 2.
Có 2 cách được sử dụng để tạo thư viện chính của T-Coffee. Cách thứ nhất là sử
dụng thuật toán ClustalW[6] để bắt cặp 2 chuỗi tổng quát, có độ dài mặc định. Và cách
thứ hai là sử dụng Lalign để bắt cặp khi 2 chuỗi được chia thành các đoạn nhỏ, có độ
tương
đồng cao (Lalign là chương trình nằm trong bộ chương trình FASTA và xây
dựng dựa theo thuật toán Sim được đưa ra bởi Huang và Miller năm 1991 [18]).
3.1.2. Đặt trọng số cho thư viện chính
Trọng số sẽ được gán cho tất cả các cặp có trong bộ thư viện chính. Ý nghĩa
chính của trọng số này chính là biểu diễn cho sự giống nhau của các cặp. Thuật toán sử
dụng tính đồng nhất (identity) của chuỗi, tính đồng nhất của chuỗi được đưa ra bởi
Sander và Schneider năm 1991[19] và đã được chứng minh khi bắt cặp những chuỗi
có tính đồng nhất lớn hơn 30%. Đồng th
ời trọng số này cũng thể hiện được tính đúng
đắn của mình trong một bài viết trước đó của nhóm tác giả[20]. Như vậy Mỗi cặp
chuỗi được bắt cặp trong thư viện chính sẽ nhận được trọng số bằng chính độ tương
đồng giữa 2 chuỗi trong nó.Chẳng hạn với ví dụ của hình 5, ta sẽ có bộ thư viện như
hình 7.

Hình 7: Thư viện chính cùng với trọng số[7]



Page | 18

3.1.3. Kết hợp thư viện
Mục tiêu của thuật toán là kết hợp bộ thư viện được tạo thành bởi cả ClustalW và
Lalign về với nhau. Điều này có thể thực hiện dựa trên một ý tưởng đơn giản, nếu một
cặp trong thư viện này mà được lặp lại ở thư viện kia thì có thể ghép chúng làm một
với trọng số bằng tổng trọng số của cặp này trong cả 2 thư việ
n. Nếu không có thì chỉ
cần tạo một phần tử mới cho thư viện là chính cặp đang xét.
Sau khi đã ghép xong, bộ thư viện mới này chúng ta có thể đưa sang việc sắp
hàng đa chuỗi bằng cách tìm kiếm đa chuỗi thẳng hàng nào thích hợp nhất với trọng số
của các cặp có trong thư viện. Tuy nhiên, thuật toán lại tiếp tục cải tiến độ chuẩn xác
của thông tin trong mỗi cặ
p bằng cách mở rộng bộ thư viện. việc mở rộng bộ thư viện
này chính là bước thứ tư của thuật toán
3.1.4. Mở rộng thư viện

Hình 8: Mở rộng thư viện[7]
Bài toán xây dựng đa chuỗi thẳng hàng từ một bộ dữ liệu có gán trọng số là một
bài toán khá nổi tiếng được đưa ra bởi Kececioglu với cái tên “maximum weight
trace”[21]. Trước thời điểm T-Coffee được công bố đã có 2 thuật toán được đưa ra
bởi Notredame[22] và Reinert[23], thuật toán của Notredame dựa trên giải thuật gen di
truyền trong khi đó thuật toán thứ 2 của Reinert dựa trên đồ thị
. Mặc dù vậy cả 2 thuật
toán này đều không đáp ứng được yêu cầu. Thuật toán của Notredame là khá thực tế
tuy nhiên lại đòi hỏi thời gian thực hiện quá lớn. Trong khi đó thuật toán của Reinert
lại quá phức tạp và có thể xảy ra những sai sót trong quá trình tính toán.

Page | 19


Cuối cùng, vấn đề trên đã được giải quyết bằng cách sử dụng thuật toán heuristic
bên trong phần mở rộng thư viện của T-Coffee. Ý tưởng chung của thuật toán này là
trọng số cho mỗi cặp amino axit được bắt cặp với nhau có thể biểu diễn một phần
thông tin cho cả bộ dữ liệu. Để làm được việc này một cách tiếp cận mới được đưa ra
như hình 8, đây là cách m
ở rộng thư viện từ thư viện chuẩn ví dụ của hình 7. Thuật
toán dựa trên việc sự dụng mỗi cặp amino axit được bắt cặp với nhau trong thư viện và
kiểm tra xem sự xuất hiện của nó trong các cặp chuỗi đã được bắt cặp khác trong thư
viện chính còn lại. Với ví dụ trong hình 8, ta giả thiết rằng có 4 chuỗi cần được bắt cặp
là A, B, C, và D
. Chúng ta gọi A(G) là kí tự G trong GARFIELD ở chuỗi A, tương tự
như vậy với B(G). Đồng thời gọi W(A(G), B(G)) là trọng số đặc trưng cho cặp này ở
trong thư viện chính. Trên thực tế A(G) và B(G) được bắt cặp với nhau trong thư viện
chính và ta có thể thấy trọng số của cặp này là 88 (dựa trên trọng số của cặp chuỗi A –
B). Nếu bây gi
ờ ta đưa thêm chuỗi C vào để so sánh, ta có thể thấy A(G) và C(G) được
bắt cặp với nhau, đồng thời đó là C(G) và B(G). Như vậy ta có thể nói là có một sự bắt
cặp giữa A(G) và B(G) thông qua C. Ta xét 2 giá trị mới đó là W
1
= W(A(G), C(G))
=77 và W
2
= W(B(G), C(G)) = 100. Ta đặt trọng số mà A(G) được bắt cặp với B(G)
thông qua C là giá trị nhỏ nhất giữa W
1
và W
2
, ở đây do W
1
= 77 và W

2
= 100 nên ta
đặt lại giá trị trong thư viện là 77. Khi đưa vào trong thư viện mở rộng cặp A(G) và
B(G) sẽ có trọng số là giá trị 88 ban đầu cộng với giá trị 77 mới thu được kết quả mới
là 165.
Việc mở rộng thư viện đòi hỏi phải xét tới tất cả các bộ ba chuỗi trong thư viện
chính ban đầu. Chẳng hạn việc bắt cặp A và
B thông qua D không tồn tại thông tin liên
quan tới A(G) và B(G) như vậy bộ ba chuỗi này được xem là không liên quan tới việc
bắt cặp A(G) và B(G), đồng thời chúng cũng không làm ảnh hưởng tới trọng số khi bắt
cặp 2 amino axit này với nhau. Như vậy trọng số để bắt cặp giữa 2 amino axit sẽ là
tổng tất cả các trọng số được tính theo thuật toán trên. Một khi hoàn thành tất cả các
c
ặp amino axit trên A và B thì mỗi cặp sẽ chứa thêm thông tin từ các chuỗi C và D.
Độ phức tạp lý thuyết của thuật toán này là O(N
3
L
2
), trong đó N là số chuỗi và L
là độ dài trung bình của các chuỗi. Tuy nhiên điều này chỉ xảy ra với thư viện có các
cặp chuỗi không liên quan gì tới nhau, trên thực nghiệm độ phức tạp thuật toán lớn
nhất cũng chỉ là O(N
3
L).

Page | 20

Trọng số sẽ là 0 nếu cặp amino axit tương ứng không xuất hiện trên thư viện,
điều này sẽ xảy ra trong phần lớn các cặp amino axit trong quá trình thực hiện thuật
toán. Ngược lại, nếu trọng số lớn hơn 0, nó sẽ biểu diễn tính tương đồng giữa 2 chuỗi

trong một cặp ở thư viện chính. Điểm này có thể được dùng để bắt cặp 2 chuỗi bất kì
từ bộ dữ liệu của chương trình sử dụng quy hoạch động[24].
3.1.5. Bắt cặp sử dụng thật toán progressive
Trong bắt cặp progressive, đầu tiên 2 chuỗi sẽ được bắt cặp với nhau để tạo ma
trận khoảng cách giữa tất cả các chuỗi, ma trận này được sử dụng để xây dựng cây và
từ cây đó áp dụng thuật toán neighbor-joining[25] để nhóm các chuỗi có độ tương
đồng với nhau nhất thành một nhóm. 2 chuỗi có khoảng cách gần nhất sẽ được bắt cặp
trước sử dụng thuật toán quy hoạ
ch động. Chú ý rằng thuật toán quy hoạch động này
sử dụng trọng số được sinh ra trong bước mở rộng thư viện. Trong quá trình bắt cặp
sóng đôi này, gap sẽ được tạo ra và những gap này sẽ được cố định và không thể thay
đổi về sau này (gap chính là dấu cách được thêm vào, biểu thị cho một phép chèn/xóa).
Việc bắt cặp các nhóm có khoảng cách gần nhau nhất sẽ được thực hiện cho tới khi đạt
tới gốc c
ủa cây. Chú ý rằng, để bắt cặp hai nhóm, điểm vẫn sẽ được lấy từ thư viện mở
rộng tuy nhiên sẽ là điểm trung bình của toàn bộ cột trong trong các cặp đó.
Một điều đáng lưu ý nữa ở đây đó là trong bước sử dụng quy hoạch động, các
điểm phạt hay bất kì tham số nào sẽ không được sử dụng, lý do ở đây chính là khi tạ
o
ra thư viện mở rộng các điểm phạt đó đã được tính rồi.
3.2. M-Coffee
M-Coffee[26] là một dạng mở rộng của T-Coffee, mục tiêu của M-Coffee là kết
hợp các đa chuỗi thẳng hàng từ các chương trình và thuật toán khác trên thế giới để tạo
thành đa chuỗi thẳng hàng mới với hi vọng kết quả này tốt hơn các kết quả được sinh
ra từ các thuật toán đó.
Dự
a trên lý thuyết của T-Coffee ta có thể thấy nếu ta thay các bước tạo thư viện
chính bởi ClustalW và Lalign thành các chương trình bắt cặp trên thì ta có thể chạy T-
Coffee dựa trên bộ thư viện là các cặp chuỗi được bắt cặp bởi các thuật toán khác.
Chính điều này làm cho M-Coffee thu nhận được thông tin từ các thuật toán khác và


Page | 21

cho ra kết quả là đa chuỗi thẳng hàng mang thông tin phù hợp với tất cả các thuật toán
đó.
Một điều đáng nói ở M-Coffee là thuật toán này luôn cố gắng chạy tất cả các
chương trình có cài đặt trong máy tính người sử dụng. Những chương trình đó có thể
là những chương trình đã xuất hiện từ rất lâu, thuật toán có thể đã lỗi thời và kết quả
của nó dường như là không t
ốt. Việc sử dụng thư viện dựa trên các kết quả này dẫn tới
có thể có những đánh giá sai sót về những thông tin lưu trữ và thời gian chạy chương
trình bị kéo dài. Điều này dẫn tới khả năng về mặt tốc độ của M-Coffee là hạn chế.
Tuy nhiên, T-Coffee đã đưa ra một phiên bản mở rộng của mình với tư tưởng khá
giống với M-Coffee. T-Coffee sẽ nhậ
n chuỗi đầu vào cùng với các bộ dữ liệu được
đưa làm thư viện nhưng các bộ dữ liệu này sẽ được coi như ngang bằng nhau – các
trọng số của các đa chuỗi tham khảo đều là 1.
4.EM-Coffee
Như vậy khi đi tới bước này chúng ta đã phần nào tìm ra được hướng giải quyết
chính cho vấn để được đưa ra ở phần 1 chương 3. Trọng số biểu diễn độ tin cậy của
một đa chuỗi thẳng hàng được giải quyết bằng MUMSA và sau đó dùng T-Coffee để
sắp hàng đa chuỗi sử dụng bộ thư viện đã được gán trọng số trên. Nhìn chung thuật
toán c
ủa EM-Coffee có thể được biểu diễn như hình 9.
Dựa trên các kết quả thực nghiệm của các thuật toán hiện nay, 5 phương án cho
kết quả tốt nhất được lựa chọn đó là MUSCLE, ProbCons, MAFFT FFT-nsi, MAFFT
Li-nsi, MAFFT Ei-nsi. Bộ thư viện của T-Coffee sẽ chính là những dữ liệu kết quả từ
các thuật toán này.
Về mặt trọng số, ta cần chuẩn hóa các giá trị thu được từ MUMSA. Giả sử Ta có
các giá trị MOS thu đượ

c từ các đa chuỗi thẳng hàng sinh ra bởi các thuật toán lần lượt
như sau: MOS(muscle), MOS(ProbCons), MOS(fftnsi), MOS(linsi), MOS(einsi). Bước
chuẩn hóa đầu tiên, ta sẽ tính điểm trung bình các giá trị MOS này
OS( )
5
pi P
M
pi
M
∈
=
∑

(pi tương ứng với các thuật toán)