CÁC PHƯƠNG PHÁP SẮP HÀNG ĐA CHUỖI NHANH

- Sắp hàng đa chuỗi là một vấn đề quan trọng trong lĩnh vực tin sinh học.
- 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..
- 31.2 Các chương trình sắp hàng đa chuỗi (multiple sequences alignment ) thông dụng hiện nay.
- Các phương pháp bắt cặp đa chuỗi.
- 52.1.1 Tính toán ma trận khoảng cách giữa mọi cặp chuỗi.
- 183.2.1 Dữ liệu với số lượng chuỗi lớn.
- 193.2.2 Dữ liệu với số lượng sequence nhỏ, tổng số amino axit nhỏ.
- 203.2.3 Dữ liệu với độ dài của chuỗi quá lớn.
- 19Bả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.
- 29Bảng 7: Kết quả các phương pháp với BAliBASE 2.
- 30Bảng 8: Kết quả các phương pháp với BAliBASE 3 – homologous.
- 31Bảng 9: Kết quả các phương pháp với BAliBASE 3 – ful llength.
- 13Hình 4: Ví dụ về việc tạo ma trận tương đồng [4].
- 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.
- 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.
- Qua đó ta có thể thấy được tầm quan trọng của sắp hàng đa chuỗi.
- Đố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.
- 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.
- 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..
- Đạt độ chính xác khá cao và tốc độ nhanh với kích thước dữ liệu vừa phải..
- Đối với những tập dữ liệu lớn (>1000 chuỗi), nên chạy với cấu hình tiết kiệm thời gian và bộ nhớ PROBCONS[5].
- Cho độ chính xác cao khi kiểm tra với một vài bộ dữ liệu chuẩn..
- Hạn chế về tốc độ và bộ nhớ, không có khả năng thực hiện với những bộ dữ liệu lớn (>100 chuỗi) MAFFT[4].
- 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.
- 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.
- Tính toán ma trận khoảng cách giữa mọi cặp chuỗi..
- 2.1.1 Tính toán ma trận khoảng cách giữa mọi 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.
- Từ bước 1, ta có ma trận khoảng cách giữa mọi cặp chuỗi.
- 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)..
- 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 đó..
- Đầu vào của UPGMA[13] là một ma trận khoảng cách.
- 2.2.3 Thuật toán.
- Tạo ra ma trận khoảng cách D1..
- 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.
- 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..
- Hình 4: Ví dụ về việc tạo ma trận tương đồng [4].
- Ma trận điểm cho thuật toán được định nghĩa theo công thức.
- 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.
- 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).
- 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.
- 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.
- Dữ liệu đầu vào có chuỗi có độ dài lớn.
- Đố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.
- 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..
- 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..
- 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]..
- Dữ liệu với số lượng chuỗi lớn.
- 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.
- 3.2.1 Dữ liệu với số lượng chuỗi lớn.
- 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).
- 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.
- 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.
- 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:.
- Tổng số amino acid của dữ liệu.
- 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.
- Đố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).
- 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ế..
- Do, với dữ liệu đầu vào có mức độ tương đồng cao