Tài liệu Khóa luận Các phương pháp sắp hàng đa chuỗi nhanh: ĐẠ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à...
43 trang |
Chia sẻ: haohao | Lượt xem: 1189 | Lượt tải: 0
Bạn đang xem trước 20 trang mẫu tài liệu Khóa luận Các phương pháp sắp hàng đa chuỗi nhanh, để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên
ĐẠ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
Tin Sinh học (bioinformatics) là một lĩnh vực khoa học sử dụng các công nghệ
của các ngành tin học, toán học ứng dụng, thống kê, khoa học máy tính, trí tuệ nhân
tạo, hóa học và hóa sinh để giải quyết các vấn đề sinh học. Sắp hàng đa chuỗi là một
vấn đề quan trọng trong lĩnh vực tin sinh học. Trong những năm gần đây, chất lượng
của các chương trình sắp hàng đa chuỗi đã được cải thiện rất nhiều bởi rất nhiều thuật
toán mới. Mặc dù vậy, lĩnh vực vẫn là một nhiệm vụ khó khăn cho các nhà khoa học.
Mỗi một thuật toán, một chương trình sắp hàng đa chuỗi đều có những ưu điểm và
nhược điểm riêng của mình. Vì thế cần tìm cách tối ưu từng ưu điểm của từng phương
pháp, và hạn chế nhược điểm của chúng.
Khóa luận sẽ trình bày về các phương pháp sắp hàng đa chuỗi được ứng dụng
rộng rãi hiện nay đồng thời phân tích và đưa ra một giải pháp nhằm phát huy tối đa ưu
điểm cũng như hạn chế tối thiểu nhược điểm của từng phương pháp.
Mục Lục:
Chương 1. Giới thiệu .......................................................................................................1
1.1 Multiple alignment .................................................................................................1
1.2 Các chương trình sắp hàng đa chuỗi (multiple sequences alignment ) thông dụng
hiện nay ........................................................................................................................3
Chương 2. Các phương pháp bắt cặp đa chuỗi ................................................................5
2.1 CLUSTALW ..........................................................................................................5
2.1.1 Tính toán ma trận khoảng cách giữa mọi cặp chuỗi ........................................5
2.1.2 Tạo cây hướng dẫn (guide tree) .......................................................................5
2.1.3 Progressive alignment ......................................................................................6
2.2. MUSCLE...............................................................................................................7
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 ...........................7
2.2.2 Profile alignment..............................................................................................8
2.2.3 Thuật toán ........................................................................................................8
2.3 MAFFT.................................................................................................................10
2.3.1 Bắt cặp nhóm sử dụng FFT............................................................................10
2.3.2 Hệ thống tính điểm.........................................................................................13
2.4 PROBCONS.........................................................................................................15
Chương 3. Cây quyết định .............................................................................................17
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 .......................................................................27
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..............................20
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
Mục Lục Hình:
Hình 1: Ví dụ về k-mer [6] ..............................................................................................7
Hình 2: Các bước thực hiện của MUSCLE [6] ...............................................................9
Hình 3: Ví dụ về độ trễ [4] ............................................................................................12
Hình 4: Ví dụ về việc tạo ma trận tương đồng [4] ........................................................13
Hình 5: Ví dụ về global homology [4] ...........................................................................21
Hình 6: Ví dụ về local homology [4] .............................................................................22
Hình 7: Ví dụ về các đoạn gap nội khối [4] ..................................................................22
Hình 8: Cây quyết định với yêu cầu xử lý tốc độ cao....................................................23
Hình 9: Cây quyết định với yêu cầu xử lý với điểm chuẩn cao .....................................24
1
Chương 1. Giới thiệu
1.1 Multiple alignment
Trình bày tổng quan dưới đây được tham khảo từ luận văn tiến sỹ của thầy Lê Sỹ
Vinh[1] và cuốn Inferring Phylogenies[2] của giáo sư Felsenstein.
Với sự phát triển như vũ bão của khoa học kỹ thuật, trong vài thập kỷ qua, sinh
học phân tử đã có nhiều bước tiến mạnh mẽ. Kèm theo đó là sự ra đời của hàng loạt
loại công cụ phục vụ cho sinh học, qua đó góp phần thúc đẩy mạnh mẽ quá trình giải
mã một số lượng lớn trình tự gen ở nhiều loài sinh vật. Cho đến nay, nhiều bộ gen của
nhiều loài vi khuẩn và sinh vật bậc cao đã được giải mã gần như hoàn toàn. Trong đó,
một khám phá đặc biệt là việc giải mã bộ gen người. Dự án Bản đồ gen người là một
dự án nghiên cứu khoa học mang tầm quốc tế. Dự án khởi đầu vào năm 1990 với
người đứng đầu là tiến sĩ James D. Watson. Bản phác thảo đầu tiên của bộ gen đã được
cho ra đời vào năm 2000 và hoàn thiện vào năm 2003. Một dự án song song cũng được
thực hiện bởi một công ty tư nhân tên là Celera Genomics. Tuy nhiên, hầu hết trình tự
chuỗi được xác định là tại các trường đại học và các viện nghiên cứu từ các nước Mỹ
Cannada và Anh. Việc xác định toàn bộ bộ gen người là một bước tiến quan trọng
trong việc phát triển thuốc và các khía cạnh chăm sóc sức khỏe khác. Qua những phát
kiến này, lượng thông tin sinh học ngày càng phong phú và đa dạng. Để có thể xử lý
và ứng dụng khối lượng thông tin đồ sộ như vậy, ngành Tin Sinh học (Bioinformatics)
ra đời, đó là sự kết 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ã
2
- 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.
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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14
Người A C A A C T G G T C C G T T
Mèo A C G A C T G G T C C G T T
Khỉ A C G G C T G G T C C G T T
Chó A C G G C T G - T C C G G T
Ngựa A G G A C T G G T - C G G T
Gà A G T G C T - G T C G G G T
Vịt A G T A C T - G T - G G G T
Dễ dàng nhận thấy, chúng ta có thể sử dụng nhiều cách chèn dấu cách vào các vị
trí khác nhau để tạo ra các phương án bắt cặp đa chuỗi khác nhau. Trước đây, các nhà
sinh vật học có thể tiến hành bắt cặp đa chuỗi bằng mắt và kinh nghiệm. Không cần
phải nói cũng có thể hiểu được đó là một công việc vô cùng vất vả và khô khan. Mà
kết quả đạt được là rất hạn chế về chất lượng. Qua đó ta có thể thấy được tầm quan
3
trọng của sắp hàng đa chuỗi. Để nâng cao độ chính xác, các phép biến đổi có thể được
gắn các trọng số khác nhau sao cho các phép biến đổi ít khi xảy ra có trọng số lớn hơn
các phép biến đổi thường xuyên xảy ra. Đối với dữ liệu protein, người ta thường sử
dụng ma trận thay thế axit amin làm trọng số cho các phép thay thế giữa các cặp axit
amin ( ma trận thay thế axit amin phản ánh tốc độ thay thế giữa các axit amin ).
1.2 Các chương trình sắp hàng đa chuỗi (multiple sequences
alignment ) thông dụng hiện nay
Bài toán sắp hàng đa chuỗi là một trong những bài toán được quan tâm và nghiên
cứu nhiều nhất trong hai thập kỉ qua. Một trong các phương pháp nổi bật và thông
dụng trước đây là phương pháp CLUSTALW[3] được phát triển bởi Thompson và
đồng nghiệp từ những năm 1994. Phương pháp CLUSTALW[3] tiến hành sắp hàng
các chuỗi sao cho tổng số điểm phạt (điểm phạt cho phép thay thế, điểm phạt cho phép
chèn / xóa…) là nhỏ nhất. Để làm được việc đó, CLUSTALW[3] từng bước tiến hành
sắp hàng hai chuỗi (hay hai nhóm chuỗi đã được sắp hàng) để cuối cùng thu được một
đa chuỗi 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
4
chuỗi)
MAFFT[4]
Phát triển với nhiều tùy
chọn, cho phép thực hiện
nhiều yêu cầu từ tốc độ
nhanh đến độ chính xác rất
cao
Hạn chế về tốc độ với những
yêu cầu chạy chính xác, và cũng
không phải là phương pháp cho
kết quả cao nhất trên tất cả các
bộ dữ liệu chuẩn
Mặc dù việc sắp hàng đa chuỗi và tìm kiếm thành phần lặp có một lịch sử nghiên
cứu và phát triển khá lâu, nhưng nó vẫn là một bài toán quan trọng cần phải tiếp tục
tập trung nghiên cứu và phát triển để giải quyết các đòi hỏi ngày một cao của lĩnh vực
sinh học.
Hàng chục phương pháp sắp hàng đa chuỗi mới được đề xuất hàng năm. Mỗi
phương pháp đưa ra đều có ưu điểm và nhược điểm về độ chính xác và thời gian thực
hiện. Quan trọng hơn chúng thường chỉ phù hợp cho một số kiểu dữ liệu, và dẫn đến
khó khăn lớn cho người dùng trong việc lựa chọn phương pháp phù hợp nhất cho một
bộ dữ liệu cụ thể đang nghiên cứu. Ví dụ, đối với các bộ dữ liệu có chứa thành phần
lặp, chúng ta phải sử dụng phương pháp tiên tiến nhất cho phép bắt cặp đa chuỗi kết
hợp với tìm thành phần lặp. Vì vậy khóa luận sẽ tập trung giải quyết vấn đề trên bằng
cách xây dựng một chương trình sắp hàng đa chuỗi kết hợp các phương pháp tốt nhất
hiện nay thông qua việc sử dụng cây quyết định.
5
Chương 2. Các phương pháp bắt cặp đa chuỗi
2.1 CLUSTALW
CLUSTALW[3] là một chương trình được biết đến và sử dụng nhiều nhất trong
các chương trình giải quyết bài toán MSA (Multiple sequences alignment). Nó được
phát triển bởi Julie D. Thompson, Desmond G. Higgins và Toby J. Gibson.
CLUSTALW[3] được thực hiện thông qua 3 bước chính:
- Tính toán ma trận khoảng cách giữa mọi cặp chuỗi.
- 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.
6
- 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.
- 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) ( , ) ( , ) ( , )
r r
k k
Q i j r d i j d i k d j k
= =
= − − −∑ ∑
Với mỗi “hàng xóm” khi được nối tạo thành một nút mới, chúng ta sử dụng công
thức sau để tính khoảng cách giữa từng “hàng xóm” với nút mới. Ở đây: f, g là 2 hàng
xóm và u là nút mới được tạo thành:
1 1
1 1( , ) ( , ) [ ( , ) ( , )]
2 2( 2)
r r
k k
d f u d f g d f k d g k
r = =
= + −− ∑ ∑
Khi một nút mới được tạo thành ta dùng công thức sau để tính khoảng cách của
nó với các nút cũ:
1 1( , ) [ ( , ) ( , )] [ ( , ) ( , )]
2 2
d u k d f k d f u d g k d g u= − + −
Ở đây, u là nút mới, k là nút cũ, f và g là 2 phần tử tạo nên nút mới u.
2.1.3 Progressive alignment
Dựa vào cây hướng dẫn (guide tree) được tạo ra từ bước 2, chúng ta sử dụng sắp
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.
7
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:
DK2p= -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ự.
8
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 khoảng cách. Ở mỗi bước 2 nút gần nhất được nhóm lại với nhau tạo thành một
nút mới và ma trận khoảng cách được tính lại theo công thức sau:
1 ( , )
| | * | | x A x B
d x y
A B ∈ ∈
∑ ∑
Ở đây, chúng ta tính khoảng cách giữa 2 nút A và B; x và y lần lượt là các nút ban
đầu trong A và B; d(x, y) là khoảng cách giữa 2 nút x và y.
2.2.2 Profile alignment
Để áp dụng bắt cặp sóng đôi vào các profiles, điều cần thiết là xác định một hàm
tính điểm cho một cách sắp hàng.
Ta coi i, j là 2 amino acid, pi là xác xuất i xuất hiện, pij là xác xuất i và j được
align với nhau, fxi là xác suất của i xuất hiện tại cột x của profile thứ nhất, fxG là xác
suất xuất hiện một gap tại cột x trong các profile. Khi đó MUSCLE[6] đưa ra hàm tính
Log-Expectation theo công thức sau:
LExy = (1 - fxG)(1- fyG) log ∑i∑j fxi fyi pij/pipj
MUSCLE[6] sử dụng các tham số pi và pij là các tham số của ma trận 240 PAM
VTML [14].
2.2.3 Thuật toán
Thuật toán MUSCLE[6] là một loạt các bước sử dụng các khái niệm đã trình bày
ở trên. Tuy nhiên tổng quát lại nó bao gồm 3 phần chính là:
Phần 1: draft progessive.
Phần 2: improved progessive.
Phần 3: Refinement.
Mỗi phần làm một nhiệm vụ riêng biệt, nhưng kết nối chặt chẽ với nhau bởi đầu
ra của phần này là đầu vào của phần tiếp theo.
9
Hình 2: Các bước thực hiện của MUSCLE [6]
Phần 1: draft progessive. Mục tiêu chính của phần này là tạo ra một đa chuỗi
thẳng hàng mà vấn đề chính là tốc độ chứ không phải là sự chính xác.
- Sử dụng khoảng cách K-mer[8] để xác định khoảng cách giữa mỗi cặp của
chuỗi dầu vào. Tạo ra ma trận khoảng cách D1.
- Sử dụng thuật toán UPGMA[13] để xây dựng cây hướng dẫn TREE1.
- Ở mỗi lá của cây Tree1, một profile được tạo ra từ một chuỗi đầu vào. Các
nút trong cây được thăm theo thứ tự tiền tố (nghĩa là các nút con được thăm trước cha
mẹ). Ở mỗi nút trong (internal node) phương pháp một bắt cặp sóng đôi (pairwise
alignment - một đa chuỗi thẳng hàng nhưng chỉ có được xây dựng từ 2 profile) được
xây dựng từ 2 nút con. Việc này lặp đi lặp lại cho đến khi gặp gốc của cây. Đó chính là
đa chuỗi thẳng hàng – mục tiêu của bước này.
Phần 2: improved progessive. Hầu hết các lỗi trong phần một đều do việc sử
dụng khoảng cách K-mer[11], phần 2 sẽ tạo lại cây bằng cách sử dụng khoảng cách
Kimura[12]. Phương pháp này cho kết quả tốt hơn nhưng đòi hỏi các chuỗi phải được
sắp hàng (có độ dài bằng nhau).
- Với mỗi cặp chuỗi trong MSA1, chúng ta tính khoảng cách cho chúng sử
dụng khoảng cách Kimura[12]. Kết quả ta có ma trận khoảng cách D2.
- Từ ma trận khoảng cách D2, sử dụng phương pháp UPGMA[13] ta tạo nên
cây Tree2.
10
- Làm tương tự bước 1.3 với cây Tree2 ta được đa chuỗi thẳng hàng MSA2.
Phần 3: Refinement. Tìm phương án tốt nhất.
- Bước 3.1 Một cạnh được chọn từ Tree2 (cạnh được chọn bằng cách giảm dần
khoảng cách tới gốc)
- Bước 3.2 Chia cây Tree2 thành 2 phần bằng cách bỏ cạnh vừa chọn, sau đó
tính lại các profile trên mỗi phần đó.
- Bước 3.3 Tạo ra một đa chuỗi thẳng hàng (sequences alignment) mới bằng
cách sắp hàng một lần nữa 2 profile vừa được tạo ra.
- Bước 3.4 Nếu điểm SP (sum of pair)[23] được cải thiện thì cách sắp hàng
mới được giữ lại, ngược lại ta bỏ đi.
- Lặp lại các bước 3.1-3.4 cho tới khi hội tụ hoặc đi tới giới hạn do người sử
dụng định nghĩa[15].
2.3 MAFFT
2.3.1 Bắt cặp nhóm sử dụng FFT
Biểu diễn một amino acid dưới dạng một vector
Tần suất của sự thay thế các amino acid phụ thuộc mạnh mẽ vào các thuộc tính lí
hóa của chúng, đặc biệt là các thuộc tính khối lượng (volume) và độ phân cực
(polarity)[16]. Do đó để biểu diễn một amino acid a dưới dạng vector thì ta cần một
vector trong đó các thành phần của vector này là v(a) – thể hiện thuộc tính khối lượng
và p(a) – thể hiện thuộc tính độ phân cực[17]. Ở đây, MAFFT[4] đã sử dụng các giá
trị v(a) và p(a) đã được chuẩn hóa để thuận lợi cho việc tính toán sau này. Công thức
xác định các giá trị chuẩn hóa đó là:
[ ](ˆ ) ( ) / vv a v a v σ= −
[ ](ˆ ) ( ) / pp a p a p σ= −
Trong dó các giá trị v và p là các giá trị trung bình, các giá trị ,v pσ σ là độ lệch
tiêu chuẩn.
Khi đó một chuỗi amino acid sẽ được chuyển thành một chuỗi các vector.
11
Tính toán mối quan hệ giữa hai chuỗi amino acid
Mối tương quan về mặt khối lượng giữa 2 chuỗi amino acid được tính theo công
thức sau
1 2
1 ,1
ˆ ˆ( ) ( ) ( )v
n N n k M
c k v n v n k
≤ ≤ ≤ + ≤
= +∑
Trong đó N và M là độ dài của 2 amino acid. 1 2ˆ ˆ( ), ( )v n v n là giá trị của thuộc tính
khối lượng của 2 amino acid tại vị trí thứ n. k là độ trễ trong phép tính. Việc định nghĩa
k sẽ được nêu ở phần sau.
Bằng một cách hoàn toàn tương tự ta sẽ tính được giá trị ( )pc k . Khi đó hàm quan
hệ giữa 2 chuỗi amino acid này được định nghĩa theo công thức
c(k) = cv(k) + cp(k).
Nếu ta coi N = M trong trường hợp trên, khi đó độ phức tạp của thuật toán để tính
mối quan hệ này là O(N2). Tuy nhiên, dựa vào biến đổi Fourier ta có thể tối ưu bước
này và giảm độ phức tạp thuật toán xuống còn O(N logN) [18]. Xét với trường hợp tính
toán cv(k), ta coi V1(m) và V2(m) là dạng biến đổi của v1(n) và v2(n) ta sẽ có
1 1ˆ( ) ( )v n V m⇔
2 2ˆ( ) ( )v n V m⇔
Ta coi dấu ⇔ dùng để biểu diễn các cặp khi sử dụng Fourier và dấu * thể hiện sự
chuyển vị ma trận. Khi đó giá trị của hàm phụ thuộc sẽ được tính theo công thức
*
1 2( ) ( ) ( )vc k V m V m⇔
Tìm kiếm đoạn tương đồng
Độ trễ k giữa hai chuỗi là độ chậm của chuỗi thứ nhất với chuỗi thứ 2. Ở phần B
hình dưới đây biểu diễn độ trễ k giữa 2 chuỗi 1 và 2
12
Hình 3: Ví dụ về độ trễ [4]
Bằng thực nghiệm ta thấy, với các giá trị c(k) lớn, đồng nghĩa với việc tại độ trễ
đó có thể xuất hiện các chuỗi tương đồng (như trên hình vẽ). Khi đó thuật toán sử dụng
một bảng trượt với độ lớn của bảng là 30 amino acid (trong hình ví dụ thì độ lớn của
bảng là 4). Sau đó lấy 20 giá trị độ trễ k có c(k) lớn nhất. Sử dụng bảng trượt trên hai
chuỗi này, nếu tỉ lệ tương đồng vượt quá giới hạn (giá trị giới hạn mặc định là 0.7) thì
coi như ta đã tìm được một vùng tương đồng, nếu có nhiều vùng tương đồng liên tiếp
với nhau thì nối chúng lại với nhau. Tuy nhiên độ lớn của vùng tương đồng này không
vượt quá 150 amino acid, nếu lớn hơn 150 thì phải tách chúng ra làm 2 đoạn tương
đồng.
Tạo ma trận tương đồng
Sau khi đã tìm ra được các cặp đoạn tương đồng giữa 2 chuỗi. Khi đó ta định
nghĩa một ma trận hai chiều là ma trận tương đồng như sau:
Ma trận S(i,j) (i, j = 1 … n) – n là số đoạn tương đồng giữa h chuỗi.
Tại S(i, j) nếu đoạn i của chuỗi một tương đồng với đoạn j của chuỗi hai thì điểm
S(i,j) sẽ là điểm được tính như trên. Trường hợp còn lại S(i,j) = 0.
13
Hình 4: Ví dụ về việc tạo ma trận tương đồng [4]
Hình trên là một ví dụ của việc tạo ma trận tương đồng với 5 đoạn tương đồng
giữa chuỗi 1 và chuỗi 2. Việc chọn đường đi tối ưu phụ thuộc vào S(2,3) và S(3,2).
Nếu S(2,3) có giá trị lớn hơn thì đường đi sẽ theo đường in đậm như hình vẽ.
Mở rộng từ bắt cặp giữa 2 sequence thành bắt cặp nhóm
Ta có thể dễ dàng mở rộng tính toán bắt cặp giữa 2 chuỗi thành bắt cặp giữa 2
nhóm bằng cách thay công thức tính cv(k) và cp(k) với vi(n) và pi(n) bằng:
1
1
ˆ ˆ( ) . ( )group i i
i group
v n w v n
∈
= ∑
1
1
ˆ ˆ( ) . ( )group i i
i group
p n w p n
∈
= ∑
Trong đó wi là trọng số của chuỗi i trong group1
Đặc biệt, trong trường hợp sử dụng cho các nucleotide chúng ta có thể áp dụng
công thức sau để tính toán hàm quan hệ:
c(k) = cA(k) + ct(k) + cc(k) + cg(k).
2.3.2 Hệ thống tính điểm
Ma trận điểm:
Để nâng cao hiệu năng của việc bắt cặp, một hệ thống tính điểm (ma trận tương
đồng và điểm phạt gap) đã được sửa đổi [19]. Ma trận điểm cho thuật toán được định
nghĩa theo công thức :
14
( ) ( )ˆ 2 / 1 2 aab abM M average average average S⎡ ⎤= − − +⎣ ⎦
Trong đó:
a, b là hai amino acid
các giá trị average được tính
1 a a a aa vera ge f M= Σ
,2 a b a b a ba vera ge f f M= Σ
Mab là ma trận ban đầu, mặc định ở đây là ma trận PAM 200 [15].
fa là tần số xuất hiện của amino acid a [15].
Sa là tham số thêm vào.
Đối với các acid nucleic ta có các giá trị fa = 0.25 và Sa = 0.06
Điểm phạt
Công thức tính điểm phạt được định nghĩa theo công thức:
{ }( , ) 1 ( ) ( ) / 2op start endG i j S g j g i⎡ ⎤= − +⎣ ⎦
Trong đó:
Sop là điểm phạt khi tạo ra một gap
gstart(j) là số gap xuất hiện bắt đầu từ vị trí thứ j
gend(i) là số gap xuất hiện từ vị trí bắt đầu cho tới i
( ) ( ) ( 1)start m m m
m group
g j w a j z j
∈
= +∑
d ( ) ( ) ( 1)en m m m
m group
g i w a i z i
∈
= −∑
zm(i) = 1 và am(i) = 0 nếu tại vị trí thứ i của chuỗi có gap ngược lại zm(i)= 0 và
am(i) = 1.
15
2.4 PROBCONS
PROBCONS[5] sử dụng mô hình Markov ẩn [20] cho thuật toán progressive.
Điểm khác biệt chính giữa PROBCONS[5] và các phương án tiếp cận khác đó chính là
việc sử dụng ước lượng chuẩn xác cực đại (maximum expected accuracy) chứ không
phải là cách sử dụng mô hình Viterbi[21], ngoài ra PROBCONS[5] 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. Mặt
khác PROBCONS[5] còn sử dụng ma trận chuyển đổi chuẩn BLOSUM62[22] 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.
Các bước thực hiện của thuật toán PROBCONS[5] như sau:
Cho m chuỗi, S = {S(1) ,… , S(m)}
- Bước 1: Tính các ma trận xác suất:
Với mỗi cặp chuỗi x và y của S, và với mỗi {1,...,| | }i x∈ và {1,...,| | }j y∈ . Ta tính
ma trận Pxy (i, j) = P(xi ~ yj ∈ a*| x, y). Đây là xác suất ký tự xi và yj được bắt cặp với
nhau trong a* - pairwise alignment được sinh ra từ mô hình HMM.
- Bước 2: Tính toán kỳ vọng của độ chính xác.
Định nghĩa kỳ vọng của độ chính xác của một bắt cặp sóng đôi (pairwise
alignment) a được tạo bởi hai chuỗi x và y được tính bằng số lượng liên kết chính xác
của các ký tự chia cho chiều dài của chuỗi ngắn hơn.
Ea* (accuracy(a, a*)|x, y) =
~yj
1 ( ~ * | , )
min{| |,| | } xi a
P xi yj a x y
x y ∈
∈∑
Với mỗi cặp chuỗi x và y ta tính toán cực đại của kỳ vọng của độ chính xác bằng
phương pháp quy hoạch động và đặt E(x, y) = Ea* (accuracy(a, a*)|x, y)
- 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 ta ước lượng lại P(xi ~ yj ∈ a*| x, y) ở bước trên.
Ở dạng ma trận chuyển đổi ta có công thức:
P’xy
1
| | z S
PxzPzy
S ∈
← ∑
16
- Bước 4: Xây dựng cây hướng dẫn (guide tree).
Xác định ma trận tương đồng giữa 2 chuỗi x và y bằng giá trị E(x, y) được tính ở
bước 2. Từ đó ta xây dựng cây hướng dẫn.
- Bước 5: Progressive alignment
Dựa vào cây hướng dẫn được dựng từ bước 4, ta tiến hành bắt cặp.
Qua các thực nghiệm với các bộ dữ liệu chuẩn, kết quả của PROBCONS[5] là rất
cao (cao nhất với rất nhiều bộ dữ liệu chuẩn). Tuy nhiên, một hạn chế cực lớn của
PROBCONS[5] là tốc độ, về mặt này PROBCONS[5] không thể so sánh với các thuật
toán trên.
17
Chương 3. Cây quyết định
3.1 Cách giải quyết của Chuong B. Do và Kazutaka Katoh
Như đã trình bày ở trên, hiện nay có khá nhiều phương pháp sắp hàng đa chuỗi,
nhưng mỗi phương pháp lại có một đặc điểm riêng kèm theo đó là những ưu khuyết
điểm riêng. Đôi khi một phương pháp cho kết quả tốt với bộ dữ liệu này, lại không phù
hợp với bộ dữ liệu khác. Một phương pháp cho kết quả rất cao nhưng tốc độ lại quá
chậm, hoặc không thể xử lý những dữ liệu quá lớn. Qua đó có thể thấy việc xây dựng
cây quyết định để giải quyết vấn đề chọn phương pháp tối ưu nhất cho mỗi loại dữ liệu
đầu vào là vô cùng quan trọng. Hai nhà khoa học Chuong B. Do và Kazutaka Katoh đã
đề ra một giải pháp[26] là nghiên cứu về từng phương pháp và từng loại dữ liệu, qua
đó có thể đưa ra được những phương pháp phù hợp với từng bộ dữ liệu cả về mặt điểm
chuẩn lẫn thời gian xử lý.
Hai tác giả đã chia các loại dữ liệu ra thành 3 phần riêng biệt cần phải xem xét là:
- Dữ liệu yêu cầu tìm thành phần lặp.
- Dữ liệu đầu vào có số lượng chuỗi lớn ( > 200 chuỗi ).
- Dữ liệu đầu vào có chuỗi có độ dài lớn ( > 2000 amino acid).
Đối với loại dữ liệu thứ nhất, chúng ta không xem xét nó trong phạm vi của khóa
luận này.
Đối với dữ liệu đầu vào có số lượng chuỗi lớn ( > 200 chuỗi ). Hai tác giả đã chỉ
ra độ phức tạp thuật toán trong việc tính toán ma trận khoảng cách là nhân tố chủ yếu
trong việc dẫn đến thời gian thực hiện quá lâu của các phương pháp. Cho nên những
phương pháp có cách xây dựng ma trận khoảng cách với độ phức tạp thấp sẽ được
chọn. Ở đây, 2 phương pháp MUSCLE và FFT-NS-2 đã được chọn.
Với dữ liệu có chuỗi có độ dài lớn ( > 2000 amino acid), thì độ phức tạp không
gian của thuật toán là nguyên nhân chính dẫn đến việc thuật toán có xử lý được loại dữ
liệu này không. Hầu hết các phương pháp có độ phức tạp không gian là O(L2) với L là
độ dài trung bình của các chuỗi. Đối với loại dữ liệu này, những phương pháp có độ
phức tạp không gian tuyến tính ( CLUSTALW, FFT-NS-1 và FFT-NS-2 ) được sử
dụng.
18
Tuy nhiên cách chia của Katoh và Chuong B Do còn chưa được rõ ràng, chưa chỉ
rõ đối với từng khoảng nhỏ dữ liệu. Do đó tôi sẽ phát triển tiếp phương pháp của 2 tác
giả Chuong B Do và Kazukata Katoh trong khóa luận này.
Trong khóa luận này, ta tập trung nghiên cứu về 4 chương trình sắp hàng đa
chuỗi tốt nhất hiện nay là: CLUSTALW, MUSCLE, PROBCONS, MAFFT (bao gồm
L-INS-i, E-INS-i, G-INS-i, FFT-NS-1, FFT-NS-2). Ở đây, chúng ta tập trung vào 2
vấn đề tốc độ và điểm chuẩn (benchmark) để đưa ra 2 cây quyết định cho 2 yêu cầu về
tốc độ và benchmark.
3.2 Vấn đề tốc độ
Với các phương pháp kể trên, chúng đều có một giới hạn về dữ liệu đầu vào khác
nhau. Vấn đề ở đây, là kiểm tra giới hạn của từng phương pháp. Để kiểm tra, chúng ta
sử dụng 3 bộ dữ liệu là BAliBASE2[23], BAliBASE3[24] và Pfam-A[25].
Chúng ta chia thành 3 tình huống riêng biệt:
- Dữ liệu với số lượng chuỗi lớn ( > 200 chuỗi).
- Dữ liệu với số lượng chuỗi nhỏ, tổng số amino acid nhỏ.
- Dữ liệu với độ dài của chuỗi quá lớn ( > 2000 amini acid).
3.2.1 Dữ liệu với số lượng chuỗi lớn ( > 200 chuỗi)
Trong trường hợp này, tốc độ đóng một vai trò vô cùng quan trọng. Trong trường
hợp này ta có các phương pháp có thể chạy được là: MUSCLE, FFT-NS-1, FFT-NS-2.
Những phương pháp này cho kết quả tương đối thấp, nhưng có tốc độ chạy khá cao.
Do đó ta sẽ kiểm tra giới hạn của 3 phương pháp này, các test được trích từ bộ dữ liệu
Pfam-A ( là bộ dữ liệu chỉ là một tập hợp các chuỗi protein). Với các test có số lượng
chuỗi từ 200 đến 500 chuỗi.
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.
Số lượng chuỗi MUSCLE FFT-NS-2 FFT-NS-1
200 – 250 28 / 128 / 68.8 5 / 12 / 9.4 3 / 11 / 8
250 - 300 63 / 284 / 113.8 9 / 17 / 12.6 9 / 18 / 11.8
19
300 – 350 47 / 183 / 136.8 8 / 19 / 13.2 7 / 20 / 12.4
350 – 400 74 / 339 / 167.6 12 / 31 / 18 8 / 21 / 12.8
400 – 450 102 / 604 / 257.4 15 / 56 / 26.2 13 / 48 / 22.8
450 – 500 145 / 738 / 372.2 18 / 60 / 34 16 / 49 / 27.6
Kết quả chỉ ra thời gian chạy nhanh nhất, lâu nhất của một test, và thời gian trung
bình của các test đó. Từ những số liệu trên ta có thể thấy. MUSCLE chỉ nên chạy với
các test dưới 400 chuỗi. Tiếp tục với các phương pháp FFT-NS2 và FFT-NS1, ta có:
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
Số lượng chuỗi FFT-NS-2
500 – 1000 20 / 306 / 90.4167
1000 – 2000 97 / 454 / 219.455
2000 – 3000 250 / 535 / 397.727
3000 – 4000 350 / 631 / 486
4000 – 5000 497 / 824 / 651.4
Dựa vào các số liệu trên, ta có thể thấy FFT-NS-2 chỉ nên giới hạn chạy với các
dữ liệu dưới 4000 chuỗi. Trong 2 phương pháp FFT-NS-2 và FFT-NS-1 thì FFT-NS-2
có bước xử lý thô là FFT-NS-1. Do đó FFT-NS-2 có tốc độ chậm hơn nhưng cho kết
quả cao hơn FFT-NS-1. Trong các phương pháp được xét, FFT-NS-1 là phương pháp
có tốc độ cao nhất, nhưng cho kết quả tồi nhất. Đây là phương pháp chỉ nên sử dụng
khi các phương pháp khác đã không thể chạy được.
3.2.2 Dữ liệu với số lượng sequence nhỏ, tổng số amino axit nhỏ
Với trường hợp này, hầu hết các phương pháp đều có thể chạy được, khi đó các
điểm đánh giá phải được đặt nên hàng đầu. Chúng ta nên xử dụng các phương pháp có
độ chính xác cao như: PROBCONS, L-INS-i, G-INS-i, E-INS-i.
20
Với PROBCONS, kiểm tra với 2 bộ dữ liệu BAliBASE2[23] và BAliBASE3[24],
ta có các thông số như sau:
Bảng 5: Thời gian chạy của PROBCONS theo tống số amino acid
Tổng số amino acid của dữ liệu Thời gian chạy
0 – 1000 2.3
1000 – 2000 8
2000 – 3000 18.1
3000 – 4000 43.3
4000 – 5000 71.5
5000 – 6000 103.5
6000 – 7000 140.6
7000 – 8000 190.8
8000 – 9000 250.25
9000 – 10000 301
Từ những số liệu trên có thể thấy, PROBCONS chỉ nên dùng với những bộ dữ
liệu nhỏ (có tổng số amino acid nhỏ). Một cách chính xác, khi cần chạy nhanh và chạy
chính xác nên giới hạn tổng số amino acid của dữ liệu lần lượt là 7000 và 9000.
Đối với 3 phương pháp L-INS-i, G-INS-i, E-INS-i, nên giới hạn dữ liệu đầu vào
ở mức 200 sequences (Theo Katoh [26]).
3.2.3 Dữ liệu với độ dài của chuỗi quá lớn ( > 2000 amino acids)
Đối với các dữ liệu loại này, thì độ phức tạp không gian là một vấn đề quan trọng
cần phải xtôi xét đầu tiên trong việc lựa chọn các phương pháp sắp hàng đa chuỗi.
Hiện nay, hầu hết các phương pháp sắp hàng đa chuỗi đều hướng đến việc sử dụng
thuật toán quy hoạch động với việc sử dụng độ phức tạp không gian là O(L2) (Ở đây, L
21
là độ dài trung bình của các chuỗi). Đối với các chuỗi đặc biệt dài (> 2000 amino
acids) các phương pháp có độ phức tạp không gian tuyến tính O(L) là sự lựa chọn tối
ưu để giải quyết vấn đề này. Với các phương pháp đang được xem xét thì
CLUSTALW, FFT-NS-2 và FFT-NS-1 là những phương pháp như thế.
3.3 Vấn đề điểm chuẩn (benchmark)
3.3.1 Với các chuỗi có độ tương đồng cao
Độ tương tự (identity), là thuật ngữ chỉ việc mức độ giống nhau của các chuỗi
đầu vào. Theo Katoh và Chuong B. Do, với dữ liệu đầu vào có mức độ tương đồng cao
( > 35 % ), thì việc chạy bất cứ chương trình nào cũng không ảnh hưởng quá lớn đến
kết quả cuối cùng [26]. Còn việc kiểm tra mức độ tương tự, tôi đã sử dụng một chương
trình sắp hàng đa chuỗi có tốc độ cao (cụ thể ở khóa luận này là FFT-NS-1) để tạo ra
các chuỗi sắp hàng (có độ dài bằng nhau), sau đó kiểm tra mức độ tương tự với độ
phức tạp tuyến tính (O(L) với L là độ dài của chuỗi sau khi sắp hàng).
3.3.2 Với các chuỗi có độ tương đồng thấp
Với các chuỗi có mức độ tương tự thấp (<= 35 % ), các hệ thống tính điểm chuẩn
khác nhau đã thống nhất xác định PROBCONS và L-INS-i là các phương pháp cho kết
quả cao nhất hiện nay.
Tuy nhiên phương pháp PROBCONS khi chạy với dữ liệu là các chuỗi DNA
luôn rất chậm. Do đó, với các dữ liệu là chuỗi DNA ta không nên sử dụng phương
pháp PROBCONS.
Nói chung, sắp hàng các chuỗi có độ tương tự thấp được hiểu là 1 trong 3 trường
hợp sau:
Trường hợp 1: global homology – tương đồng (homology) trên toàn chiều dài
của chuỗi protein
Hình 5: Ví dụ về global homology [4]
22
Ở đây, X chỉ ra phần có thể được align, o là các phần không được align và – là
gap. Theo hình trên ta có thể thấy, toàn chiều dài các chuỗi là các phần có thể được
align. Đây là trường hợp đơn giản nhất và phương pháp PROBCONS và G-INS-i là 2
phương pháp cho kết quả tốt nhất trong các phương pháp đang xét.
Trường hợp 2: local homology – tương đồng (homology) được bao quanh bởi
các miền không tương đồng
Hình 6: Ví dụ về local homology [4]
Hình trên chỉ ra một tập các chuỗi có chứa trong nó một miền có thể align và
xung quanh nó là các phần không tương đồng. Khi đó, L-INS-i là phương pháp tối ưu.
Trường hợp 3: Các đoạn gap nội khối dài - các khoảng tương đồng (homology)
ngắn chia tách bởi các đoạn gap nội khối
Hình 7: Ví dụ về các đoạn gap nội khối [4]
Trong trường hợp này, có nhiều vùng có thể align, nhưng hầu hết chúng khá rời
rạc và được tách bởi những đoạn gap rất dài. Khi đó E-INS-i là phương pháp cho kết
quả tốt nhất trong các phương pháp kể trên.
Tuy nhiên, trong hầu hết các hệ thống tính điểm chuẩn, PROBCONS và L-INS-i
là hai phương pháp cho kết quả tốt nhất.
3.4 Cây quyết định
Có hai yêu cầu cần phải giải quyết là: tốc độ và benchmark, cho nên ta sẽ tạo hai
cây quyết định dựa trên những lý thuyết đã trình bày ở trên.
23
3.4.1 Cây quyết định cho yêu cầu tốc độ xử lý cao
Hình 8: Cây quyết định với yêu cầu xử lý tốc độ cao
24
3.4.2 Cây quyết định cho yêu cầu tốc điểm chuẩn cao
Hình 9: Cây quyết định với yêu cầu xử lý với điểm chuẩn cao
25
Trong phương pháp được đề xuất ở đây, tôi chưa xử lý việc tìm cách phát hiện
kiểu của các dữ liệu đầu vào có độ tương đồng thấp.
Ở đây ta mặc định với các chuỗi có độ tương tự nhỏ (<= 35 %), chúng ta chỉ sử
dụng 2 phương pháp L-INS-i và PROBCONS (là 2 phương án cho kết quả tốt nhất
hiện nay). Tuy nhiên kết quả cuối cùng khi chưa xử lý vấn đề này cũng rất khả quan.
26
Chương 4: Kết quả thực nghiệm và bình luận
Một đánh giá toàn diện và so sánh được các chương trình sắp hàng đa chuỗi đòi
hỏi một số lượng lớn các sự dữ liệu được sắp xếp chính xác mà có thể được sử dụng
như các bộ kiểm thử. Các bộ dữ liệu này có thể chỉ ra được hiệu suất của các chương
trình sắp hàng đa chuỗi phụ thuộc vào số lượng các chuỗi, mức độ giống nhau giữa các
chuỗi và số lượng các phép chèn thêm vào liên kết này. Các yếu tố khác cũng có thể
ảnh hưởng đến chất lượng liên kết chẳng hạn như độ dài của chuỗi, … BAliBASE là
bộ dữ liệu đáp ứng được đầy đủ các yêu cầu như thế. Do đó trong khóa luận này tôi sẽ
sử dụng BAliBASE để kiểm tra hiệu năng của hai phương pháp sử dụng cây quyết
định (cả về tốc độ lần điểm chuẩn) và so sánh nó với các chương trình sắp hàng đa
chuỗi khác.
4.1 Giới thiệu về BAliBASE
BAliBASE - Benchmark Alignment dataBASE là một bộ dữ liệu được xây dựng
bởi các nhà khoa học Julie D. Thompson, Olovier Poch và một số nhà khoa học khác.
Việc xây dựng bộ dữ liệu BAliBASE hoàn toàn dựa trên những kết quả đã được kiểm
chứng trước đó đồng thời bắt cặp dựa trên kinh nghiệm của chính những nhà khoa học
này. BAliBASE là một bộ dữ liệu mở, được thiết kế để phục vụ cho mục đích đánh giá
các chương trình sắp hàng đa chuỗi. Nó đặt ra tất cả các trường hợp gặp phải trong quá
trình sắp hàng. Cơ sở dữ liệu của BAliBASE được làm một cách thủ công với các chú
thích chi tiết.
4.1.1 BAliBASE 2
BAliBASE 2 có tất cả 8 reference, nhưng chỉ thường sử dụng 5 reference đầu
tiên. Các file dữ liệu được cung cấp dưới định dạng RSF hoặc MSF.
4.1.2 BAliBASE 3
BAliBASE 3 bao gồm 5 reference. Mỗi reference bao gồm một số lượng file. Các
file có tên là BBnnnnn bao gồm các chuỗi full-length, trong khi các file có tên là
BBSnnnnn là các chuỗi chỉ chứa các vùng tương đồng (homologous).
27
4.1.3 Cách đánh giá của BAliBASE
BAliBASE sử dụng hai hệ số điểm là sum of pair (SP) và total colum (TC) để
kiểm tra tính chính xác của một đa chuỗi thẳng hàng so với kết quả mà các nhà khoa
học bắt cặp một cách thủ công.
Điểm SP được tính theo thuật toán sau:
- Đặt s(x, y). Ở đây x và y là hai amino axit, s(x, y) là điểm khi bắt cặp x với y
trong đa chuỗi thẳng hàng. khi đó ta sẽ có giá trị của s(x, y) tương ứng là:
s(x, y) = 1 nếu x và y đều là một amino axit.
s(x, y) = -1 nếu x và y là hai amino acid khác nhau.
s(x, y) = -2 nếu x là gap, y khác gap và ngược lại.
s(x, y) = 0 nếu x và y đều là gap.
- Giả sử SP(mi) là giá trị của điểm “sum of pair” ở cột thứ i của đa chuỗi thẳng
hàng mà ta cần tính điểm ( phân biệt với đa chuỗi thẳng hàng mà các nhà khoa học đã
sắp hàng bằng tay để làm kết quả so sánh ), giá trị SP(mi) được tính bằng cách lấy tổng
của các s(x, y) trong đó x và y là các amino axit được lấy từ cột thứ i của đa chuỗi
thẳng hàng. Sau đó điểm SP của cả đa chuỗi sẽ được tính bằng cách lấy tổng tất cả các
điểm SP(mi) của tất cả các cột trong đa chuỗi.
Một ví dụ đơn giản cho việc tính toán SP(mi) như sau:
Bảng 6: Tính toán SP(mi)
m1 m2 m3 m4 m5 m6 m7 m8 m9
seq1 G T T C C T G - T
seq2 - T G C - T G - T
seq3 G T G C - T T - T
Score -3 3 -1 3 -4 3 -1 0 3
Ví dụ trên thể hiện một đa chuỗi thẳng hàng với 3 chuỗi và độ dài mỗi chuỗi là 9.
Ở đây với cột thứ 1. Ta có:
SP(m1) = s(G, -) + s (G, G) + s (-, G) = -2 + 1 + -2 = -3.
Tương tự với các điểm SP của các cột từ m2 cho đến m9.
Như vậy, điểm SP(m) của đa chuỗi thẳng hàng trên sẽ là: SP(m) = 3.
28
- Sau đó điểm SP(m) với đa chuỗi thẳng hàng cần tính điểm sẽ được so sánh với
kết quả SP(R) mà các nhà khoa học đã làm một cách thủ công có sẵn trong BAliBASE
và điểm SP cuối cùng của đa chuỗi thẳng hàng mà phương pháp đưa ra sẽ được tính
theo công thức: SP(m) / SP(R) * 100. Đây chính là cách tính điểm sum of pair (SP) của
BAliBASE.
Hệ số điểm thứ hai của BAliBASE là total column (TC). Điểm TC chính là tỉ lệ
số cột mà đa chuỗi thẳng hàng cần tính điểm chứa các amino axit giống hệt với cột
của đa chuỗi thằng hàng mà các nhà khoa học đã làm thủ công trong BAliBASE.
Qua hai hệ số điểm SP và TC chúng ta có thể xác định được phần nào độ chính
xác của kết quả của phương pháp sắp hàng đa chuỗi cần kiểm tra.
4.2 Kết quả thực nghiệm
Kết quả dưới đây, là kết quả của 2 bộ dữ liệu BAliBASE 2 và 3 với các phương
pháp:
- CLUSTALW version 2.0.12
- MUSCLE version 3.6
- PROBCONS version 1.12
- MAFFT version 6.617
29
BAliBASE 2
Ref11(27) Ref12(27) Ref13(28) Ref20(23) Ref30(12) Ref40(12) Ref50(12) Average
Programs
SP TC SP TC SP TC SP TC SP TC SP TC SP TC SP TC
Time(s)
CLUSTALW 87.21 80.15 83.87 76.26 86.38 78.75 93.26 59.26 72.33 48.08 85.55 69.76 85.78 63.42 83.74 68.26 1383
MUSCLE 84.96 77.11 88.78 81.96 88.76 91.46 93.56 59.61 78.33 53.92 88.13 75.33 97.25 90.08 86.37 73.04 281
PROBCONS 89.48 84.26 90.46 84.89 91.95 94.85 94.01 61.04 81.68 63.08 92.25 77.91 98.58 94.00 91.24 81.18 4733
LINSI 84.91 78.59 78.59 82.12 89.84 84.28 84.28 57.30 57.30 51.17 51.17 51.17 94.02 83.67 83.67 74.67 371
Automatic-FAST 89.48 84.26 90.46 84.89 90.95 91.11 93.88 60.17 81.58 61.83 92.25 77.91 98.49 93.08 91.02 80.16 2280
Automatic-ACCURACY 89.48 84.26 90.46 84.89 90.95 91.11 93.88 60.17 81.59 61.92 92.25 77.91 98.58 94.00 91.02 80.20 2716
Bảng 7: Kết quả các phương pháp với BAliBASE 2
30
BAliBASE 3 Homologous
RV11(38) RV12(44) RV20(41) RV30(30) RV40(49) RV50(15) Average
Programs
SP TC SP TC SP TC SP TC SP TC SP TC SP TC
Time(s)
CLUSTALW 66.25 41.76 90.30 78.95 92.35 45.00 81.77 48.30 N/A N/A 79.76 41.73 82.90 53.46 7020
MUSCLE 74.84 54.92 92.89 82.30 95.55 55.02 86.47 53.83 N/A N/A 87.25 51.13 87.81 61.58 450
PROBCONS 80.72 62.92 95.06 87.20 95.68 59.93 90.69 64.97 N/A N/A 90.91 60.53 90.82 68.70 13030
LINSI 69.57 48.60 92.57 80.73 93.93 49.76 87.55 59.30 N/A N/A 88.38 51.47 86.43 59.47 1100
EINSI 69.46 48.46 92.55 80.68 93.82 50.05 87.58 59.66 N/A N/A 89.86 59.62 86.51 60.28 1300
Automatic-FAST 80.57 62.58 94.98 86.93 95.24 57.90 90.12 63.17 N/A N/A 88.91 56.40 90.37 67.37 3340
Automatic-ACCURACY 80.72 62.92 94.86 86.70 95.36 58.44 90.44 63.60 N/A N/A 89.85 53.73 90.55 67.36 3850
Bảng 8: Kết quả các phương pháp với BAliBASE 3 – homologous
31
BAliBASE 3 full-length
RV11(38) RV12(44) RV20(41) RV30(30) RV40(49) RV50(16) Average
Programs
SP TC SP TC SP TC SP TC SP TC SP TC SP TC
Time(s)
CLUSTALW 50.02 22.74 86.50 71.30 85.16 21.98 72.56 27.30 78.93 39.55 74.25 30.75 75.37 37.39 17015
MUSCLE 59.39 35.56 91.82 80.70 89.07 34.32 80.38 38.43 86.82 46.76 85.46 48.00 82.48 48.26 1905
PROBCONS 66.80 41.48 94.17 85.55 91.69 40.66 84.6 54.3 90.24 52.86 89.17 56.69 86.37 55.66 32012
LINSI 66.31 43.81 93.56 83.49 92.72 45.21 86.6 59.31 92.69 61.53 90.15 59.26 87.25 59.33 3445
EINSI 66.11 43.6 93.48 83.19 92.51 44.6 86.81 59.53 92.37 61.13 89.76 59.55 87.09 59.08 3781
Automatic-FAST 66.65 41.18 93.75 84.30 91.31 41.90 84.77 52.13 91.59 57.08 88.45 54.69 86.46 56.09 7200
Automatic-ACCURACY 66.73 41.26 93.53 83.82 91.10 42.17 85.37 53.03 89.55 52.86 87.26 52.19 85.92 55.05 7530
Bảng 9: Kết quả các phương pháp với BAliBASE 3 – ful llength
32
Nhận xét
Bảng 7 chỉ ra kết quả của các phương pháp với bộ dữ liệu BAliBASE 2. Với mỗi
phương pháp và 1 reference tương ứng, bảng 7 đưa ra 2 chỉ số lần lượt là điểm SP, TC
của phương pháp đó với reference tương ứng. Cột cuối cùng thể hiện tổng số điểm SP,
TC của từng phương pháp với bộ dữ liệu BAliBASE 2, cũng như tổng thời gian xử lý
của từng phương pháp với bộ dữ liệu BAliBASE 2.
Từ bảng 7, ta có thể thấy, PROBCONS với bộ dữ liệu BAliBASE 2 cho kết quả
tốt nhất, nhưng thời gian xử lý của nó quá lâu (lên đến 4733 s). Mặc dù BAliBASE 2
phần lớn gồm toàn những bộ dữ liệu nhỏ (chỉ khoảng vài đến vài chục chuỗi). Các
phương pháp còn lại cho kết quả không tốt bằng mặc dù tốc độ xử lý cao hơn hẳn. Còn
2 phương án sử dụng cây quyết định cho kết quả tốt gần tương đương trên từng
reference (đôi khi các phương án này cho kết quả tốt nhất). Mặc dù kết quả trung bình
trên bộ dữ liệu BAliBASE 2, PROBCONS cao hơn 2 phương pháp sử dụng cây quyết
định, nhưng không đáng kể (SP: 91.24 so với 91.02 và TC: 81.18 so với 80.20 và
80.16), tuy nhiên thời gian xử lý của phương pháp PROBCONS cao hơn gấp đôi so với
2 phương pháp sử dụng cây quyết định (4733 s so với 2280 s và 2716 s).
Bảng 8 chỉ ra kết quả với bộ dữ liệu BAliBASE 3 – homologous. Qua đó ta có
thể thấy, PROBCONS cho kết quả tốt nhất với bộ dữ liệu này, tuy nhiên thời gian xử
lý của nó quá lớn (13030 s). Còn các phương pháp khác lại cho kết quả tồi hơn hẳn
mặc dù thời gian xử lý thấp hơn. Còn 2 phương pháp sử dụng cây quyết định, thì
phương pháp Automatic – ACCURACY cho kết quả tốt nhất trên RV11 và bằng với
PROBCONS. Còn kết quả cuối cùng chỉ kém phương án PROBCONS một ít. Điểm
SP: PROBCONS là 90.82 so với 90.55 và 90.37 lần lượt của Automatic –
ACCURACY và Automatic – FAST. Điểm TC: PROBCONS: 68.70 so với 67.36 và
67.37. Mặc dù 2 phương án này cho kết quả thấp hơn một chút, nhưng bù lại thời gian
xử lý của chúng lại nhanh hơn rất nhiều ( 3850 và 3340 so với 13030
Bảng 9 chỉ ra kết quả của các phương pháp với bộ dữ liệu BAliBASE 3 – full
length. Ở đây, MAFFT-L-INS-i và MAFFT-E-INS-i cho kết quả cao nhất với hầu hết
các reference. PROBCONS cho kết quả thấp hơn một chút. 2 phương pháp sử dụng
cây quyết định ở bộ dữ liệu này cho kết quả không thật sự khả quan. Nó không cho kết
quả cao nhất ở bộ dữ liệu nào. Tuy nhiên kết quả cuối cùng nó cũng chỉ thấp hơn 2
phương pháp của MAFFT và cao hơn các phương pháp còn lại và thời gian xử lý thì
hoàn toàn có thể chấp nhận được.
33
Qua những kết quả trên, ta có thể thấy rằng: Mặc dù 2 phương pháp sử dụng cây
quyết định không cho kết quả tốt nhất trên từng bộ dữ liệu riêng biệt nhưng kết quả của
chúng luôn đứng lần lượt là thứ 2 và thứ 3 trên từng bộ, chỉ kém kết qua tốt nhất một tỉ
lệ rất nhỏ và hơn hẳn những phương pháp khác. Trong khi những phương pháp
PROBCONS, MAFFT có thể tốt nhất trên 1 vài bộ dữ liệu, nhưng chúng vẫn mang
những nhược điểm nhất định trên những bộ dữ liệu khác nhau.
Do 2 bộ dữ liệu chuẩn ở trên, chỉ bao gồm những dữ liệu nhỏ (chỉ khoảng vài
chục đến trên một trăm chuỗi) không đủ để thể hiện hết những ưu điểm của hai phương
pháp sử dụng cây quyết định này (do không thể thể hiện ưu điểm về mặt tốc độ khi xử
lý các bộ test lớn, và không thể hiện được khả năng xử lý những bộ test ngoại cỡ - số
lượng chuỗi cực lớn, độ dài chuỗi cực lớn).
Qua đó có thể nhận thấy ưu điểm của 2 phương án sử dụng cây quyết định mà tôi
đưa ra.
34
Chương 5: Kết Luận
Mặc dù có một lịch sử lâu dài, nhưng việc nghiên cứu trong lĩnh vực sắp hàng đa
chuỗi vẫn tiếp tục phát triển mạnh mẽ. Mỗi năm, hàng chục bài báo mô tả các phương
pháp mới cho việc sắp hàng đa chuỗi được công bố. Mặc dù nhiều phương pháp trong
các phương pháp đó đều tiếp cận dựa trên các nguyên tắc cơ bản giống nhau, nhưng
các chi tiết của việc triển khai có thể có tác động đáng kể đến hiệu suất, cả về tính
chính xác và tốc độ. Lý do chính cho việc vấn đề này vẫn được tiếp tục quan tâm trong
lĩnh vực tin sinh học là sắp hàng đa chuỗi vẫn là trung tâm của phân tích so sánh trình
tự trong sinh học tính toán hiện đại: sự sắp hàng chính xác tạo thành cơ sở của nhiều
nghiên cứu trong lĩnh vực tin sinh học, và những tiến bộ trong các phương pháp sắp
hàng đa chuỗi có thể tạo ra những lợi ích sâu rộng trong nhiều lĩnh vực ứng dụng khác
nhau.
Trong những năm gần đây, xu hướng trong việc sắp hàng đa chuỗi có bao gồm
việc phát triển các công cụ thích hợp cho xử lý hiệu quả cao trên máy tính (MUSCLE,
MAFFT, POA, KAlign), ứng dụng kỹ thuật học máy (PROBCONS, CONTRAlign,
MUMMALS), và khai thác các cơ sở dữ liệu được công bố công khai để cải thiện tính
chính xác của việc sắp hàng đa chuỗi (PRALINE, MAFFT, PROMALS). Tuy nhiên
mỗi một phương pháp đều có một ưu nhược điểm của riêng mình. Do đó một số nhà
khoa học đã nhận ra một vấn đề quan trọng là tích hợp nhiều phương pháp vào cùng
một công cụ, và sử dụng cây hướng dẫn để có thể giúp đỡ cho các nhà khoa học khác
có thể ứng dụng dễ dàng.
Nội dung của khóa luận này cũng mang ý nghĩa tương tự. Phần mềm được thiết
kế được tích hợp các phương pháp hiện đại và tôi đã đưa ra một phương án tiếp cận
trong việc chọn lựa, sử dụng các phương pháp đó một cách hiệu quả. Hai phương pháp
sử dụng cây quyết định cho kết quả trên từng bộ dữ liệu chuẩn riêng lẻ luôn cho kết
quả khá tốt (xấp xỉ với kết quả của phương án tốt nhất trên bộ dữ liệu đó). Đặc biệt là
điều này vẫn đúng với nhiều bộ dữ liệu chuẩn khác nhau, điều mà các phương pháp
khác không thực hiện được. Ngoài ra, một ưu điểm nổi trội của hai phương pháp này
là, nó có thể thực hiện được nhiều kiểu dữ liệu khác nhau và cố gắng cho kết quả tốt
nhất trong khoảng thời gian cho phép. Đây là một ưu điểm lớn của phương pháp này,
do những phương pháp khác hầu như chỉ thực hiện tốt với một kiểu dữ liệu. Qua đó có
thể thấy được sự hiệu quả của phương án mà tôi đề xuất trong khóa luận này.
35
Tài Liệu Tham Khảo
[1] Lê Sỹ Vinh. PhD in 2005 (Heinrich-Heine-University Duesseldorf,
Germany). Topic : Phylogenetic tree reconstruction.
[2] Felsenstein, J. (2004). Inferring Phylogenies. Sinauer Associates,
Sunderland, Mass.
[3] Chenna R, Sugawara H, Koike T, Lopez R, Gibson TJ, Higgins DG,
Thompson JD (2003). "Multiple sequence alignment with the Clustal series of
programs"
[4] Kazutaka Katoh, Kazuharu Misawa1, Kei-ichi Kuma andTakashi Miyata
(2002). MAFFT: a novel method for rapid multiple sequence alignment based on
fast Fourier transform
[5] B. Do, Mahathi SP. Mahabhashyam, Michael Brudno, and Serafim
Batzoglou (2005). PROBCONS: Probabilistic consistency – based multiple
sequence alignment.
[6] Robert C. Edgar (2004). MUSCLE: multiple sequence alignment with
high accuracy and high throughput
[7] Wilbur, W.J. and Lipman, D.J. (1983). Proc. Natl. Acad. Sci. USA, 80,
726- 730
[8] Saitou, N. and Nei, M. (1987). Mol. Biol. Evol. 4, 406-425.
[9] Myers, E.W. and Miller, W. (1988). CABIOS, 4, 11-17.
[10] Thompson, J.D. (1994). CABIOS, (Submitted).
[11] Edgar R.C. (2004) Local homology recognition and distance measures in
linear time using compressed amino acid alphabets. Nucleic Acids Res., 32, 380 –
385.
[12] Kimura M. (1983) The Neutral Theory of Molecular Evolution.
Cambridge University Press
[13] Sneath & Sokal (1973). Numerical Taxonomy. W.H. Freeman and
Company, San Francisco, pp 230-234 Unweighted Pair Group Method with
Arithmetic Mean.
[14] Muller T., Spang,R. and Vingron,M. (2002) Estimating amino acid
substitution models: a comparison of Dayhoff’s estimator, the resolvent approach
and a maximum likelihood method. Mol. Biol. Evol., 19, 8–13.
36
[15] Hirosawa M., Totoki,Y., Hoshida,M. and Ishikawa,M. (1995)
Comprehensive study on iterative algorithms of multiple sequence
alignment. CABIOS, 11, 13–18.
[16] Miyata,T., Miyazawa,S. and Yasunaga,T. (1979) Two types of amino
acid substitutions in protein evolution. J. Mol. Evol., 12, 219–236.
[17] Grantham,R. (1974) Amino acid difference formula to help explain
protein evolution. Science, 185, 862–864.
[18] Press,W.H., Teukolsky,S.A., Vetterling,W.T. and Flannery, B.P(1995)
Numerical Recipes in C: The Art of Scientific Computing, 2nd Edn. Cambridge
University Press, Cambridge, UK.
[19] Vogt,G., Etzold,T. and Argos,P. (1995) An assessment of amino acid
exchange matrices in aligning protein sequences: the twilight zone revisited. J. Mol.
Biol., 249, 816–831.
[20] Eddy, S.R. (1995). Multiple alignment using hidden Markov models. In.
[21] Viterbi, A.J. (1967). Error bounds for convolutional codes and an
asymptotically optimal decoding algorithm. IEEE Trans. Inf. Theory IT-13: 260-
269.
[22] Henikoff, S. and Henikoff, J.G. (1992). Amino acid substitution matrices
from protein blocks. Proc. Nat. Acad. Sci. 89: 10915-10919.
[23] Thompson, J.D., Plewniak, F., and Poch, O. (1999). BAliBASE: A
benchmark alignment database for the evaluation of multiple alignment
programs.Bioinformatics 15: 87-88.
[24] Julie Thompson, Frédéric Plewniak and Olivier Poch (1999)
Bioinformatics, 15,87-88. BAliBASE: A benchmark alignments database for the
evaluation of multiple sequence alignment programs
[25] Sonnhammer EL, Eddy SR, Durbin R (1997). Sanger Centre, Wellcome
Trust Genome Campus, Hinxton, Cambridge, United Kingdom. Pfam: a
comprehensive database of protein domain families based on seed alignments.
[26] Chuong B. Do, Kazutaka Katoh (2008) ,Protein Multiple Sequence
Alignment, Methods in Molecular Biology vol. 484: Functional Proteomics.
Các file đính kèm theo tài liệu này:
- LUẬN VĂN-CÁC PHƯƠNG PHÁP SẮP HÀNG ĐA CHUỖI NHANH.pdf