Luận văn Cải tiến clustalw cho bài toán sắp hàng đa trình tự

Trang 31 CHƯƠNG 3: CHƯƠNG TRÌNH CMSA 3.1 PHẦN MỀM CLUSTALW 3.1.1 Giới thiệu phần mềm ClustalW Phần mềm này do Thompson viết năm 1994 và phiên bản mới nhất hiện nay là ClustalW 2.0.11 [5]. ClustalW sử dụng giải thuật lũy tiến toàn cục và kỹ thuật gom nhóm Neighbor Joinning để sắp hàng đa trình tự. Đầu tiên các cây không gốc sẽ được tạo thông qua việc tính toán dựa vào khoảng cách của các cặp trình tự, mỗi nút lá đại diện cho một trình tự. Từ các cây không gốc tính toán để xây dựng một nút gốc nối liền các cây này. Các nhánh cây có trọng số khác nhau. Các trọng số này được tính toán và dẫn xuất từ khoảng cách của các cặp trình tự ban đầu. ClustalW 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. Đây cũng là chương trình mà kết quả cho độ chính xác tốt nhất so với các chương trình được hiện thực theo phương pháp lũy tiến toàn cục. Trong luận văn này sử dụng phiên bản ClustalW 1.83 ClustalW có thể nhận file dữ liệu đầu vào gồm 7 định dạng: NBRF/PIR, EMBL/SWISSPROT, Pearson (Fasta), Clustal (*.aln), GCG/MSF (Pileup), GCG9 RSF và GDE. ClustalW có thể xuất ra 7 định dạng file sắp hàng: CLUSTAL, GCG, NBRF/PIR, GDE, NEXUS, FASTA. Ngoài ra, ClustalW còn xuất ra cây hướng dẫn (cũng là cây sinh loài). Có 4 loại cây sinh loài có thể lựa chọn: Clustal, Phylip, ma trận khoảng cách Phylip, Nexus. Ma trận đánh giá được sử dụng trong ClustalW bao gồm nhiều loại. • BLOSUM: gồm Blosum 80, 62, 45 và 30. Trang 32 • PAM: gồm PAM 20, 60, 120, 350 • GONNET: gồm Gonnet 80, 120, 160, 250 và 350. Các bước thực hiện giải thuật của ClustalW như sau ClustalW dùng 96% tổng thời gian chạy cho bước thứ nhất. 4% còn lại dùng cho 2 bước sau. Trong luận văn này sử dụng phần mềm ClustalW 1.83 để so sánh và đánh giá. Các hàm chức năng của ClustalW Sắp hàng từng cặp (PSA) Tính ma trận khoảng cách (distance matrix) Xây dựng cây hướng dẫn (guide tree) và trọng số (weight) của các trình tự. Thuật toán lũy tiến: Sắp hàng theo cây hướng dẫn Hình 3.1: Các bước thực hiện của ClustalW Trang 33 Hình 3.2: Các hàm chức năng của ClustalW Một số giao diện của phần mềm ClustalW . Hình 3.3: Giao diện chính của ClustalW Trang 34 Hình 3.4: Giao diện ClustalW: Sắp hàng đa trình tự Hình 3.5: Giao diện của ClustalW: kết quả sắp hàng Trang 35 3.2.2 Nhận xét clustalW Bắt đầu từ việc nhận xét chương trình ClustalW như sau: • Thứ tự thực hiện (biễu diễn thông qua cây hướng dẫn) ảnh hưởng lớn đến toàn bộ quá trình sắp hàng. Nếu xây dựng cây hướng dẫn không tốt sẽ dẫn đến tình trạng sắp hàng càng về sau càng sai. • Trong ClustalW, các chuỗi có độ khác biệt càng cao thì càng khó sắp hàng. Khi có một hay nhiều trình tự có độ khác biệt càng cao thì khi sinh ra cây hướng dẫn sẽ không hợp lý về mặt sinh học [10]. Hình 3.6: So sánh cây hướng dẫn Chúng ta xem xét 2 hình trên. Trang 36 Dữ liệu đầu vào là các trình tự tương ứng với các đoạn gene biểu diễn các loài có tên như hình đã liệt kê, trong đó đặc biệt chú ý 3 trình tự tương ứng với stafish, moonJelly và yeast. Ba trình tự này có độ khác biệt cao so với tất cả các trình tự còn lại. Hình Tree A là hợp lý vì starfish, moonJelly và yeast có độ khác biệt cao so với các trình tự còn lại nên chúng phải được đặt gần gốc để đảm bảo được sắp sau cùng. Ngược lại, hình Tree B thì không như thế. Trong hình, trình tự moonJelly và yeast được sắp hàng trước. Điều này sẽ dẫn đến sự không hợp lý về mặt sinh học. Từ nhận xét trên, ta thấy rằng ClustalW cần được cải tiến lại để có thể sinh ra cây hướng dẫn phù hợp hơn. Việc cải tiến này cần được tập trung vào các chuỗi trình tự có độ khác biệt lớn so với các chuỗi còn lại. 3.2 CẢI TIẾN CLUSTALW Từ nhận xét cần phải cải tiến ClustalW cho trường hợp tập dữ liệu đầu vào có những trình tự có độ khác biệt cao, đề tài đưa ra ý tưởng cải tiến như sau: Việc cải tiến gồm 2 bước:
Bước 1: tìm ra các trình tự có độ khác biệt cao  Trong quá trình PSA, ClustalW gán các điểm số (score) cho mỗi cặp. Các score này có giá trị từ 0 đến 1  Các score càng nhỏ, độ khác biệt giữa các trình tự càng lớn  Tìm ra các trình tự có độ khác biệt cao (score gần 0)
Bước 2: Sửa cây hướng dẫn để đảm bảo rằng những trình tự này phải được sắp hàng sau cùng  Đảm bảo những trình tự tìm được trong bước 1 phải được xếp gần gốc Trang 37  Nếu không có trình tự nào khác biệt quá lớn, cây hướng dẫn sẽ không thay đổi  Nếu có một trình tự có độ khác biệt lớn, đặt nó gần gốc nhất  Nếu có 2 hay nhiều hơn trình tự có độ khác biệt lớn o Kiểm tra xem giữa các trình tự này có độ khác biệt lớn không o Nếu không, đặt chúng trong cùng 1 nhóm gần gốc (cùng nhánh) o Nếu có, chia thành nhiều nhóm , theo thứ tự độ khác biệt để xác định vị trí đặt gần gốc. 3.3 CHƯƠNG TRÌNH CMSA Chương trình CMSA là chương trình thừa kế và cải tiến từ ClustalW. CMSA sử dụng chương trình ClustalW, giữ nguyên bước 1 và bước 3, chỉ sửa chữa từ bước 2 (sửa cây hướng dẫn). Chương trình CMSA được viết bằng VC++ trên nền IDE Visual Studio 6.0. Chương trình có thể chạy trên hệ điều hành Microsoft Windows XP/ Vista/ Windows 7. Do thừa kế từ phần mềm ClustalW nên cũng có được những ưu điểm của phần mềm được đánh giá là tốt nhất và nhanh nhất này. Chương trình có khả năng nhận dữ liệu đầu vào là các trình tự sinh học thuộc nhiều định dạng khác nhau, sau đó tiến hành sắp hàng. Đầu ra của chương trình gồm 2 loại tập tin: tập tin chứa các trình tự đã được sắp xếp và tập tin chứa cây hướng dẫn. • Dữ liệu đầu vào là các file có thể thuộc một trong 7 định dạng sau: NBRF/PIR, EMBL/SwissProt, Pearson (Fasta), GDE, Clustal, GCG/MSF, RSF. Trang 38 Chương trình CMSA chủ yếu sử dụng định dạng FASTA. Định dạng này lưu trữ các trình tự theo cấu trúc: tên, mô tả và nội dung của trình tự. Mỗi ký tự “>” đại diện cho sự khai báo một trình tự trong file. Nội dung của trình tự không chứa khoảng trắng. Định dạng Hình 3.7: Định dạng file FASTA • Dữ liệu đầu ra: File biểu diễn cây hướng dẫn có phần mở rộng là dnd. File này có thể xem bằng nhiều phần mềm khác nhau như TreeView, PHYLIP,… >Tên trình tự Mô tả Nội dung >Tên trình tự Mô tả Nội dung … >Chuoi1 monkey ACGCTWDKLTCCCDAA PVVQSK >Chuoi2 human TGDCCAGUKVVMPDD QWWWSDCCCGTTTM RR … Trang 39 Hình 3.8: Đầu ra là cây hướng dẫn File biểu diễn kết quả sắp hàng có thể được xuất ra theo nhiều định dạng: Fasta, Clustal, NCBR/PIR, GCG/MSF, PHYLIP, NEXUS, GDE. Chương trình CMSA chủ yếu xuất ra theo định dạng GCG/MSF để tiện cho việc đối chiếu kết quả bằng chương trình Bali_score. Định dạng MSF có dạng như sau: Trang 40 Hình 3.9: Định dạng file MSF Pile Up MSF: 1 (chiều dài MSA) Type: P hay N (cho biết là trình tự đang xét là protein hay DNA) Name: Tên trình tự oo Len: chiều dài trình tự trong MSA …. Name: Tên trình tự oo Len: chiều dài trình tự trong MSA // (2 ký tự này cho biết kết thúc phần header của file) Tên trình tự Nội dung trình tự (Các ký hiệu “-“ được thay bằng “,”) Tên trình tự Nội dung trình tự Trang 41 Hình 3.10: Ví dụ định dạng file MSF PileUp MSF:21793 Type: N Check: 361 .. Name: Snake oo Len:21793 Check: 2781 Weight: 1.0 Name: Iguana oo Len:21793 Check: 8601 Weight: 18.0 Name: Lizard oo Len:21793 Check: 7448 Weight: 19.0 Name: Whale oo Len:21793 Check: 2018 Weight: 10.0 Name: Cattle oo Len:21793 Check: 6069 Weight: 10.0 Name: Monkey oo Len:21793 Check: 1499 Weight: 6.0 Name: Human oo Len:21793 Check: 7075 Weight: 6.0 Name: Bird oo Len:21793 Check: 7732 Weight: 6.0 Name: Fish oo Len:21793 Check: 8182 Weight: 12.0 Name: Crocodile oo Len:21793 Check: 662 Weight: 7.0 Name: Yeast oo Len:21793 Check: 8294 Weight: 19.0 // Snake .......... .......... .......GTT ATTGTAGCTT ACATTAC..T Iguana .......... .......... .......GTT ATTGTAGCTT AATTTAT..C Lizard .......... .......... .......GTC ATTGTAGCTT ATTTT.T..A Whale .......... .......... .......GTT AATGTAGCTT AAACACTCAC Cattle ATATATAAAC GCAGGCCCCC CCCCCCCGTT GATGTAGCTT AACC.....C Monkey .......... .......... .......GTT AATGTAGCTT AA.TACT..C Human AACCAAACCC CAAAGACACC CCCCACAGTT TATGTAGCTT ACCTCCT..C Bird .......... .......... .......GTC CCCGTAGCTT ACAGCC...C Fish .......... .......... .......GCT AGCGTAGCTT Trang 42 Ví dụ có đầu vào gồm 9 trình tự như sau: Hình 3.11: Ví dụ dữ liệu đầu vào Hình 3.12: Xác định các trình tự có độ khác biệt cao điểm càng nhỏ, các trình tự khác biệt càng lớn. Trang 43 Bước cải tiến thứ nhất trong chương trình CMSA là tìm ra tất cả các trình tự có độ khác biệt cao (các trình tự có score nhỏ). Trong hình trên, có thể thấy rằng trình tự số 7 (ứng với tên là Yeast) là trình tự có độ khác biệt cao nhất so với tất cả các trình tự còn lại. Trình tự này sẽ được đánh dấu lại để chắc chắn rằng nó phải được đặt gần gốc, nghĩa là sẽ được sắp hàng sau cùng. Hình 3.13: Cây hướng dẫn sau khi sửa chữa Dùng clustal Dùng CMAS