Dữ Liệu Với Số Lượng Chuỗi Lớn (

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

Có thể bạn quan tâm!

Xem toàn bộ 50 trang tài liệu này.

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

300 – 350

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.

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

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]

Ở đâ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.

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

Sequence Input

sequence

>= 2000 aa

Số Sequences

> 4000

Có Không

MAFFT-NS1

MAFFT-NS2

Có

Không

Số Sequences

>= 4000

MAFFT-NS1

Có

Không

Số Sequences

>= 400

MAFFT-NS2

Có

Không

Số Sequences

>= 200

MUSCLE

Có

Không

Tổng số aa

>= 7000

MAFFT-LINSI

Có

Không

Là DNA

MAFFT-LINSI

Có

Không

PROBCONS

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

Sequence Input

sequence

> 2000 aa

Số Sequences

> 4000

Có Không

MAFFT-NS1

MAFFT-NS2

Có

Không

Số Sequences

> 4000

MAFFT-NS1

Có

Không

Số Sequences

> 400

MAFFT-NS2

Có

Không

Số Sequences

> 200

MUSCLE

Có

Không

Độ tương tự

> 35%

MAFFT-LINSI

Có

Không

Tổng số aa

> 9000

MAFFT-LINSI

Có

Không

Là DNA

MAFFT-LINSI

Có

Không

PROBCONS

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.