Luận văn Các kỹ thuật toán học cho bài toán so sánh đa trình tự

ư sau: Sắp xếp quần thể theo thứ tự độ tốt giảm dần. Loại bỏ các cá thể cuối dãy để chỉ giữ lại p cá thể tốt nhất, ở đây ta giả sử quần thể có kích thước cố định p. Một thuật giải di truyền gồm các thành phần sau: Một cấu trúc dữ liệu I biểu diễn không gian lời giải của bài toán. Phương pháp khởi tạo quần thể ban đầu P(0). Hàm định nghĩa độ thích nghi (fitness function) đóng vai trò môi trường. Các phép toán di truyền như đã mô phỏng ở trên. Và các tham số thuật giải di truyền sử dụng (kích thước quần thể, xác suất lai, đột biến v.v...) parent 1 : 1 1 0 | 0 0 1 parent 2 : 0 1 0 | 1 1 1 offspring 1 : 1 1 0 1 1 1 offspring 2 : 0 1 0 0 0 1 Các kỹ thuật toán học cho bài toán so sánh đa trình tự Phạm Mạnh Hùng Trang 59 4.3.2. Cấu trúc thuật giải di truyền tổng quát Bắt đầu t=0; Khởi tạo quần thể P(t); Tính độ thích nghi cho các cá thể thuộc P(t); while (điều kiện dừng chưa thoả) { t = t+1; Tái sinh P’(t) từ P(t-1); Lai Q(t) từ P’(t); Đột biến R(t) từ P’(t); Chọn lọc P(t) từ ( 1) ( ) ( ) ( )− ∪ ∪ ∪P t Q t R t P' t ; } Kết thúc. Ý tưởng của việc sử dụng giải thuật GA cho bài toán TSP: Chúng ta xây dựng một quần thể các lời giải của bài toán TSP. Quần thể có m cá thể với m là tham số do người dùng điều chỉnh. Mỗi nhiễm sắc thể sẽ có k gene, mỗi gene đại diện cho 1 đỉnh. Hàm fitness chính là chiều dài của quãng đường ứng với nhiễm sắc thể. Quãng đường ứng với nhiễm sắc thể càng ngắn hàm thích nghi càng tốt. Chúng ta sẽ xây dựng các hàm lai ghép, đột biến, và chọn lọc cho giải thuật. Ví dụ: Phép lai ghép sử dụng phép lai ghép theo giải thuật PMX(Partially-Mapped Crossover). Nội dung phép lai ghép này như sau: Sử dụng 2 điểm cắt trên nhiễm sắc thể của cả cha-mẹ. Để tạo một nhiễm sắc thể mới(con), phần chuỗi nằm giữa 2 điểm cắt của nhiễm sắc thể thứ nhất cha(mẹ) sẽ được thay thế cho phần chuỗi nằm giữa 2 điểm cắt của nhiễm sắc thể còn lại. So sánh sự thay đổi gene trong phần giữa 2 điểm cắt của nhiễm sắc thể thứ hai với nhiễm sắc thể mới tạo, thực hiện sự thay đổi các phần tử bên ngoài vùng giữa 2 điểm cắt của nhiễm sắc thể con, dựa trên sự thay đổi này. Điều này đảm bảo cho không có sự lặp lại của các gene trong nhiễm sắc thể mới. Tương tự đổi vai trò của nhiễm sắc thể cha mẹ với nhau ta sẽ tạo được thêm 1 con mới. Xét ví dụ 2 nhiễm sắc thể cha 1 2 5 6 4 3 8 7 và mẹ 1 4 2 3 6 5 7 8 . Xét 2 điểm cắt tại vị trí 3,6. Quá trình tạo ra 1 nhiễm sắc thể mới(con) như sau. Thay thế chuỗi nằm giữa 2 điểm cắt của mẹ là 2 3 6 bằng chuỗi nằm giữa 2 điểm cắt của cha 5 6 4 lúc Nhiễm sắc thể cho bài toán TSP 9 đỉnh [9 3 4 0 1 2 5 7 6 8] Các kỹ thuật toán học cho bài toán so sánh đa trình tự Phạm Mạnh Hùng Trang 60 này nhiễm sắc thể con là 1 4 5 6 4 5 7 8. Như vậy 5, 4 xuất hiện 2 lần trong nhiễm sắc thể con. So sánh phần nằm giữa 2 điểm cắt của nhiễm sắc thể con và nhiễm sắc thể mẹ ta thấy gene 5 được thay bằng 2, gene 4 được thay bằng 6, nhưng vì 6 có trong phần giữa 2 điểm cắt nên 4 được thay bằng 3. Thực hiện sự thay đổi này với phần nằm ngoài 2 điểm cắt ta được nhiễm sắc thể con mới: 1 3 5 6 4 2 7 8 . Chúng ta có một ví dụ minh họa cho phép Crossover của giải thuật. Phép đột biến: phép đột biến được thực hiện bằng cách đổi chỗ một cách ngẫu nhiên 2 gene bất kỳ trong 1 nhiễm sắc thể, sao cho nhiễm sắc thể mới thu được có chiều dài của con đường tương ứng ngắn hơn so với nhiễm sắc thể ban đầu. Ví dụ minh họa cho phép đột biến của giải thuật: Phép chọn lọc: Chọn lọc các cá thể có hàm thích nghi tốt nhất. 4.4. Phần hiện thực giải thuật và chương trình: Chương trình tính MSA(MSAPR) được viết bằng VC++8(2005) trên nền IDE Visual Studio 2005. Chương trình chạy trên nền hệ điều hành Microsoft Windows XP, cung cấp giao diện đồ hoạ cho phép người dùng tương tác một cách dễ dàng. Chương trình tính MSA hiện thực cả 2 giải thuật 1A, 1B. Người sử dụng có thể lựa chọn 1 trong 2 giải thuật này. Dựa trên các ý tưởng đã được phân tích trong phần giải thuật. Cấu trúc chương trình chương trình hiện thực bài toán MSA gồm có 3 phần: ƒ Module giải quyết bài toán PSA ƒ Module giải quyết bài toán TSP Trước [0 1 2 3 4 5 6] Sau phép đột biến [0 1 3 2 4 5 6] parent 1 : 1 2 | 5 6 4 | 3 8 7 parent 2 : 1 4 | 2 3 6 | 5 7 8 ________________________________ offspring (step 1) : 1 4 5 6 4 5 7 8 (step 2) : 1 3 5 6 4 2 7 8 Các kỹ thuật toán học cho bài toán so sánh đa trình tự Phạm Mạnh Hùng Trang 61 ƒ Module hiện thực giải thuật 1B. Hình 4.8 Cấu trúc chương trình hiện thực PSA Module: hiện thực giải thuật “Chia để trị” kết hợp với việc sử dụng 3 ma trận BLOSUM để giải quyết bài toán PSA. Hình 4.9 Module PSA MSA Module :Hiện thực giải thuật tính MSA. Bao gồm các khối chức năng: ƒ Khối chức năng tính toán ma trận khoảng cách dựa trên việc sử dụng module PSA. ƒ Khối chức năng tìm thứ tự align các sequence dựa trên ma trận khoảng cách và Module TSP. ƒ Khối chức năng thực hiện giải thuật Feng-Doolittle, align 2 nhóm sequence. Input MSA Module PSA Module TSP Module Output PSA Module Kết quả hàm đánh giá 2 sequence Kết quả alignment 2 sequence Sequence 1 Sequence 2 Đầu raĐầu vào Giải thuật Chia để trị kết hợp quy hoạch động Các ma trận BLOSUM Các kỹ thuật toán học cho bài toán so sánh đa trình tự Phạm Mạnh Hùng Trang 62 ƒ Khối chức năng thực hiện giải thuật align bao gồm việc gom nhóm, thực hiện giải thuật align theo thứ tự từ lời giải bài toán TSP, lưu trữ các nhóm sequence đã được align. Hình 4.10 Sơ đồ các khối chức năng của Module MSA. TSP Module: Module hiện thực giải thuật giải quyết bài toán TSP. Trên cơ sở thư viện hàm GALib[12] được phát triển bởi MIT(Massachusetts Institute of Technology), chương trình tích hợp và thừa kế thư viện GALib đồng thời hiện thực một giải thuật di truyền cho bài toán TSP. GALib là một thư viện hàm mở, được viết bằng C++, cung cấp các phương thức hỗ trợ người dùng xây dựng một giải thuật di truyền(GA) để phát triển các ứng dụng . Mặc dù là bài toán NP, tuy nhiên hiện tại bài toán TSP đã được giải quyết rất tốt với số đỉnh nhỏ hơn 10000.Về phương pháp giải quyết bài toán TSP, có khá nhiều phương pháp, phương pháp tiếp cận theo nhánh và cận(branch and bound) kết hợp một số kỹ thuật heuristic được sử dụng phổ biến nhất và cho kết quả nhanh nhất. Sử dụng giải thuật GA cho bài toán TSP là một giải pháp không thật sự tối ưu, tuy nhiên giải thuật là chấp nhận được về mặt thời gian cũng như không gian nhớ khi số đỉnh nhỏ hơn 500. Do phạm vi của luận văn nên phần giải quyết bài toán TSP chỉ giới hạn trong việc áp dụng giải thuật GA. Input (k sequence) Ma trận khoảng cách Lời giải TSP Feng-Doolittle Algorithm Module PSA Module TSP Module Module gom nhóm, align Kết quả MSA Các kỹ thuật toán học cho bài toán so sánh đa trình tự Phạm Mạnh Hùng Trang 63 Hình 4.11 Sơ đồ các khối chức năng của module TSP. Ngoài 3 module chính còn 2 module nhập xuất thực hiện việc xử lý dữ liệu đầu vào cũng như xuất kết quả của giải thuật. Input/Output. Dữ liệu đầu vào của chương trình tuân theo chuẩn định dạng FASTA(NCBI)[21]. Chuẩn định dạng FASTA được sử dụng phổ biến trong hầu hết các chương trình tìm MSA. Chuẩn định dạng này lưu trữ các sequence theo cấu trúc: tên, mô tả và nội dung của sequence. Mỗi ký tự “>” biểu hiện cho sự khai báo một sequence trong file. Nội dung của sequence không chứa ký tự khoảng trắng. Định dạng: Bảng 4.1 Định dạng của file dữ liệu đầu vào Dữ liệu đầu ra của chương trình được biểu diễn theo từng phần của toàn bộ MSA. Định dạng của file kết quả có dạng như sau. Giải thuật GA cho TSP Chu trình qua các đỉnh Ma trận khoảng cách Số đỉnh GALib >Tênsequence Mô tả Nội dung >Tênsequence Mô tả Nội dung . . . . >Sequence1 cbfx_mouse VLGTVKWFNVRNGYGFINRNDT KEDVFVHQTAIKKNNPRKYLRSV GDGETVEFDVVEGEKGAEAANV TGP >Sequence2 grp2_nicsy KGTVKWFSDQKGFGFITPDDGGE DLFVHQSGIRSEGFRSLAEGETVE FEVESGGDGRTKAVDVTGP Các kỹ thuật toán học cho bài toán so sánh đa trình tự Phạm Mạnh Hùng Trang 64 Bảng 4.2 Định dạng của file dữ liệu đầu ra. Ngoài ra chương trình còn cho phép lưu trữ kết quả theo chuẩn định dạng MSF, để phục vụ cho quá trình so sánh thống kê kết quả khi kiểm thử trên tập BAliBASE benchmark, phần này sẽ được đề cập chi tiết trong Chương 5. Chuẩn định dạng MSF có dạng như sau: Bảng 4.3 Định dạng file dữ liệu đầu ra theo chuẩn MSF Result MSA: Tên sequence Nội dung của sequence trong MSA Tên sequence Nội dung của sequence trong MSA … Tên sequence Nội dung của sequence trong MSA Result MSA: grp2_nicsy -----KGTVKWFSDQKGFGFITPDDGGEDLFVHQSGIRSEG----FRSLA cbfx_mouse ----VLGTVKWFNVRNGYGFINRNDTKEDVFVHQTAIKKNNPRKYLRSVG ************************************************************* grp2_nicsy EGETVEFEVESGGDGRTKAVDVTGP- cbfx_mouse DGETVEFDVVEGEKG-AEAANVTGP- PileUp MSF: l (chiều dài MSA) Type: P hay N (cho biết là các sequence đang xét là protein hay nucleotide) Name: Tên của sequence oo Len: chiều dài sequence trong MSA … Name: Tên của sequence oo Len: chiều dài sequence trong MSA // (2 ký tự này cho biết kết thúc phần header của file) Tên sequence Nội dung của sequence trong MSA(Các ký hiệu ‘-‘ được thay bằng ‘.’) Tên sequence Nội dung của sequence trong MSA PileUp MSF: 82 Type: P Name: hmgl_trybr oo Len: 82 Name: hmgt_mouse oo Len: 82 Name: hmgb_chite oo Len: 82 // hmgl_trybr .KKDSNAPKR AMTSFMFFSS ....DFRSKH SDLSI.VEMS KAAGAAWKEL hmgt_mouse ......KPKR PRSAYNIYVS ESFQEAKDDS AQGKL..... KLVNEAWKNL hmgb_chite ....ADKPKR PLSAYMLWLN SARESIKREN PDFKV.TEVA KKGGELWRGL hmgl_trybr GPEERKVYEE MAEKDKERYK REM....... .. hmgt_mouse SPEEKQAYIQ LAKDDRIRYD NEMKSWEEQM AE hmgb_chite ..KDKSEWEA KAATAKQNYI RALQEYERNG G. Các kỹ thuật toán học cho bài toán so sánh đa trình tự Phạm Mạnh Hùng Trang 65 Bảng tóm tắt các lớp được xây dựng của chương trình: Lớp Chức năng MultipleAlignmentAlgorithm Hiện thực chức năng module MSA: Feng- Doolittle, tạo ma trận khoảng cách, thực hiện giải thuật align MSA LinearSapceAlgorithm Hiện thực giải thuật PSA theo kỹ thuật chia để trị sử dụng 3 ma trận BLOSUM Sequence Lưu trữ Sequence GATSP Hiện thực giải thuật di truyền cho bài toán TSP dựa trên thư viện hàm GALib AlignSequenceProfile Lưu trữ các nhóm sequence đã được align InitValue Khởi tạo các thông số cho giải thuật PSA MatrixPenalty Đối tượng lưu trữ ma trận đánh giá, các tham số về gap StoreOPDBPF Lưu trữ thông tin cho phép tìm lại con đuờng của giải thuật PSA TSPResultObject Lưu trữ kết quả lời giải TSP Bảng 4.4 Bảng tóm tắt các lớp của chương trình. Ngoài ra chương trình còn 1 số lớp phụ khác phục vụ cho quá trình xây dựng giao diện, hỗ trợ cấu trúc dữ liệu cho việc thực thi các thuật giải… Các kỹ thuật toán học cho bài toán so sánh đa trình tự Phạm Mạnh Hùng Trang 66 Chương 5. KẾT QUẢ NHẬN XÉT Chương này giới thiệu một số kết quả của chương trình. Thực hiện việc kiểm thử chương trình trên BAliBASE benchmark, so sánh kết quả với một số chương trình đang được sử dụng phổ biến trên thế giới. Các kết quả của MSAPR trong phần này thu được khi chạy trên máy PC cấu hình 512MB RAM, CPU Intel 4 2.4 GHz, sử dụng hệ điều hành Microsoft Windows XP. 5.1. Một số kết quả chạy chương trình. Ví dụ kiểm thử kết quả chương trình trên tập TAT protein của HIV1(Human Immunodeficiency Virus 1): Bảng 5.1 TAT Protein HIV1 >1 MDPVDPNLESWNHPGSQPRTACNKCHCKKCCYHC >2 MDPVDPNLEPWNHPGSQPRTPCNKCHCKKCCYHC >9 MEPVDPRLEPWKHPGSQPKTACNNCYCKKCCYHC >16 MEPVDPRLEPWKHPGSQPKTASNNCYCKRCCLHC >20 MEPVDPRLEPWKHPGSQPKTACTNCYCKKCCFHC >22 MEPVDPRLEPWKHPGSQPKTACTTCYCKKCCFHC >21 MDPVDPRLEPWKHPGSQPKAACTSCYCKKCCFHC >23 MEPVDPSLEPWKHPGSQPKTACTNCYCKKCCLHC >18 MEPVDPNLEPWKHPGSQPRTACNNCYCKKCCFHC >19 MEPVDPNLEPWKHPGSQPRTACNNCYCKKCCFHC >8 MEPVDPNLEPWKHPGSQPRTACTNCYCKKCCFHC >15 MEPVDPRLEPWKHPGSQPKTACTNCYCKKCCFHC >14 MEPVDPRLEPWKHPGSQPKTACTNCYCKKCCFHC >13 MEPVDPRLEPWKHPGSQPKTACTNCYCKKCCFHC >12 MEPVDPRLEPWKHPGSQPKTACTNCYCKKCCFHC >11 MEPVDPRLEPWKHPGSQPKTACTNCYCKKCCFHC >10 MEPVDPRLEPWKHPGSQPKTACTTCYCKKCCFHC >17 METHLKAPESSLESYNEPSSCTSEQGVTAQELAKQGEELLSQLHRPLEACTNSCYCKQCSFHC >7 MEPVDPNLEPWKHPGSQPTTACSNCYCKVCCWHC >6 MDPIDPDLEPWKHPGSQPRTVCNNCYCKACCYHC >24 MDPVDPNIEPWNHPGSQPKTACNRCHCKKCCYHC >5 MDPVDPNIEPWNHPGSQPKTACNRCHCKKCCYHC >4 MDPVDPNLEPWNHPGSQPKTACNRCHCKKCCYHC >3 MDPVDPNLEPWNHPGSQPRTPCNKCYCKKCCYHC Các kỹ thuật toán học cho bài toán so sánh đa trình tự Phạm Mạnh Hùng Trang 67 Trong đó: 1,..,24 lần lượt là 24 protein của TAT : 1 -> P18804 2 -> P04611 3 -> P04613 4 -> P04609 5 -> P12506 6 -> P17285 7 -> P24738 8 -> P19552 9 -> P05908 10 -> P04610 11 -> P04607 12 -> P04606 13 -> P04326 14 -> P04608 15 -> P05907 16 -> P20893 17 -> P18044 18 -> P35965 19 -> P04614 20 -> P19553 21 -> P05906 22 -> P05905 23 -> P20879 24 -> PDB1tiv Bảng 5.2 Kết quả Alignment của MSAPR và CLUSTALW với TAT HIV1 Result of MSA: 6 MDP----IDPDLEPWKHPGS------------------------QPRTVCNN-CYCKACCYHC 3 MDP----VDPNLEPWNHPGS------------------------QPRTPCNK-CYCKKCCYHC 2 MDP----VDPNLEPWNHPGS------------------------QPRTPCNK-CHCKKCCYHC 1 MDP----VDPNLESWNHPGS------------------------QPRTACNK-CHCKKCCYHC 24 MDP----VDPNIEPWNHPGS------------------------QPKTACNR-CHCKKCCYHC 5 MDP----VDPNIEPWNHPGS------------------------QPKTACNR-CHCKKCCYHC 4 MDP----VDPNLEPWNHPGS------------------------QPKTACNR-CHCKKCCYHC 19 MEP----VDPNLEPWKHPGS------------------------QPRTACNN-CYCKKCCFHC 18 MEP----VDPNLEPWKHPGS------------------------QPRTACNN-CYCKKCCFHC 8 MEP----VDPNLEPWKHPGS------------------------QPRTACTN-CYCKKCCFHC 7 MEP----VDPNLEPWKHPGS------------------------QPTTACSN-CYCKVCCWHC 23 MEP----VDPSLEPWKHPGS------------------------QPKTACTN-CYCKKCCLHC 16 MEP----VDPRLEPWKHPGS------------------------QPKTASNN-CYCKRCCLHC 9 MEP----VDPRLEPWKHPGS------------------------QPKTACNN-CYCKKCCYHC 12 MEP----VDPRLEPWKHPGS------------------------QPKTACTN-CYCKKCCFHC 14 MEP----VDPRLEPWKHPGS------------------------QPKTACTN-CYCKKCCFHC 20 MEP----VDPRLEPWKHPGS------------------------QPKTACTN-CYCKKCCFHC 11 MEP----VDPRLEPWKHPGS------------------------QPKTACTN-CYCKKCCFHC 15 MEP----VDPRLEPWKHPGS------------------------QPKTACTN-CYCKKCCFHC 13 MEP----VDPRLEPWKHPGS------------------------QPKTACTN-CYCKKCCFHC 10 MEP----VDPRLEPWKHPGS------------------------QPKTACTT-CYCKKCCFHC 22 MEP----VDPRLEPWKHPGS------------------------QPKTACTT-CYCKKCCFHC 21 MDP----VDPRLEPWKHPGS------------------------QPKAACTS-CYCKKCCFHC 17 METHLKAPESSLESYNEPSSCTSEQGVTAQELAKQGEELLSQLHRPLEACTNSCYCKQCSFHC 1 ----MDPVDPNLESWNHP-----------------GS-------QPRTACNK-CHCKKCCYHC 2 ----MDPVDPNLEPWNHP-----------------GS-------QPRTPCNK-CHCKKCCYHC 9 ----MEPVDPRLEPWKHP-----------------GS-------QPKTACNN-CYCKKCCYHC 16 ----MEPVDPRLEPWKHP-----------------GS-------QPKTASNN-CYCKRCCLHC 20 ----MEPVDPRLEPWKHP-----------------GS-------QPKTACTN-CYCKKCCFHC 22 ----MEPVDPRLEPWKHP-----------------GS-------QPKTACTT-CYCKKCCFHC 21 ----MDPVDPRLEPWKHP-----------------GS-------QPKAACTS-CYCKKCCFHC 23 ----MEPVDPSLEPWKHP-----------------GS-------QPKTACTN-CYCKKCCLHC 18 ----MEPVDPNLEPWKHP-----------------GS-------QPRTACNN-CYCKKCCFHC 19 ----MEPVDPNLEPWKHP-----------------GS-------QPRTACNN-CYCKKCCFHC 8 ----MEPVDPNLEPWKHP-----------------GS-------QPRTACTN-CYCKKCCFHC 15 ----MEPVDPRLEPWKHP-----------------GS-------QPKTACTN-CYCKKCCFHC 14 ----MEPVDPRLEPWKHP-----------------GS-------QPKTACTN-CYCKKCCFHC 13 ----MEPVDPRLEPWKHP-----------------GS-------QPKTACTN-CYCKKCCFHC 12 ----MEPVDPRLEPWKHP-----------------GS-------QPKTACTN-CYCKKCCFHC 11 ----MEPVDPRLEPWKHP-----------------GS-------QPKTACTN-CYCKKCCFHC 10 ----MEPVDPRLEPWKHP-----------------GS-------QPKTACTT-CYCKKCCFHC 17 METHLKAPESSLESYNEPSSCTSEQGVTAQELAKQGEELLSQLHRPLEACTNSCYCKQCSFHC 7 ----MEPVDPNLEPWKHP-----------------GS-------QPTTACSN-CYCKVCCWHC 6 ----MDPIDPDLEPWKHP-----------------GS-------QPRTVCNN-CYCKACCYHC 24 ----MDPVDPNIEPWNHP-----------------GS-------QPKTACNR-CHCKKCCYHC 5 ----MDPVDPNIEPWNHP-----------------GS-------QPKTACNR-CHCKKCCYHC 4 ----MDPVDPNLEPWNHP-----------------GS-------QPKTACNR-CHCKKCCYHC 3 ----MDPVDPNLEPWNHP-----------------GS-------QPRTPCNK-CYCKKCCYHC Kết quả MSA với tập HIV1 của MSAPR Kết quả MSA với tập HIV1 của CLUSTALW Các kỹ thuật toán học cho bài toán so sánh đa trình tự Phạm Mạnh Hùng Trang 68 Thời gian chạy đối với việc tìm MSA của TAT HIV1 là 15s, của CLUSTALW là 12s. Thử nghiệm trên một số tập protein thực khác, và so sánh với kết quả của CLUSTALW, chương trình cho kết quả chạy tốt. Khi số sequence lớn và chiều dài trung bình của các sequence lớn hơn 500, thời gian chạy của chương trình cao hơn so với CLUSTALW. Vấn đề so sánh thời gian chạy và không gian bộ nhớ sử dụng sẽ được đề cập chi tiết trong phần sau. Phần tiếp theo sẽ thực hiện việc so sánh kết quả của MSAPR với một số chương trình, trên cùng một tập dữ liệu đầu vào BAliBASE. 5.2. BAliBASE (Benchmark Alignment Database) BAliBASE[3] là một tập dữ liệu các MSA của các protein được giới thiệu bởi Thompson(1999). Các MSA trong BAliBASE được xây dựng dựa trên cấu trúc bậc 3 (cấu trúc của các protein trong không gian 3 chiều) quan sát được của các protein. Từ cấu trúc bậc 3, các protein được chuyển đổi về cấu trúc bậc 2, từ đó tạo nên các MSA trong BAliBASE. Đây là một benchmark chuẩn, thường được dùng để kiểm thử các chương trình tìm lời giải của bài toán MSA. Phiên bản được sử dụng trong đề tài BAliBASE 2.01. BAliBASE 2.01 bao gồm 220 MSA, với khoảng 1000 sequence. Các protein trong MSA là các protein thật sự trong thực tế. Các MSA trong BAliBASE chia làm 8 nhóm. Mỗi nhóm này giới thiệu một số các trường hợp MSA thường gặp trong thực tế. Nhóm 1 là các MSA của các sequence có độ dài tương đương nhau, và có nhiều mức độ tương đồng giữa các sequence. Nhóm 2 bao gồm các MSA của 1 tập khoảng 15 sequence, có độ giống nhau quan sát được trong cấu trúc bậc 3 nhỏ hơn 25%. Nhóm 3 bao gồm 4 nhóm con, các nhóm con này có độ giống nhau ở các vị trí của các sequence giữa các nhóm nhỏ hơn 25%. Nhóm 4 và nhóm 5 chứa các alignment có từ 20 sequence trở lên bao gồm các N/C terminal extension và các insertions. Nhóm 6 gồm các MSA được hình thành từ các sequence có sự lặp lại của các đoạn con. Nhóm 7 gồm các MSA được hình thành từ các transmembrane protein sequence. Các kỹ thuật toán học cho bài toán so sánh đa trình tự Phạm Mạnh Hùng Trang 69 Nhóm 8 bao gồm các MSA được hình thành từ các protein có sự đột biến theo dạng vòng(Đột biến vòng được định nghĩa: Xét 1 protein ABCDEFGH, đột biến vòng có thể có dạng như sau ABCDEFGH, BCDEFGHA, CDEFGHAB ,DEFGHABC, EFGHABCD). BAliBASE sử dụng 2 định dạng file để cho phép người dùng có thể kiểm nghiệm kết quả của các chương trình trên tập dữ liệu này. Các file .tfa lưu trữ các sequence(tạo nên mỗi MSA tương ứng trong BAliBASE) theo chuẩn FASTA. Các file .msf lưu trữ các MSA theo chuẩn MSF. Việc so sánh kết quả MSA của BAliBASE với các kết quả MSA khác(được tạo ra bởi cùng 1 tập sequence đầu vào) sẽ được thực hiện thông qua chương trình bali_score (Thompson) [4]. Chương trình này sẽ cho biết MSA được đưa vào sẽ có độ chính xác bao nhiêu so với MSA của BAliBASE. Gọi độ chính xác là Δ . Tiêu chí đánh giá độ chính xác của MSA thường căn cứ vào Δ . Một số tính chất của Δ : ƒ [0,1]Δ∈ . ƒ 1Δ = có sự giống nhau hoàn toàn giữa 2 MSA. ƒ 0Δ = , 2 MSA có sự khác biệt hoàn toàn. ƒ 1Δ→ độ chính xác cao. ƒ 0Δ→ độ khác biệt cao. Chương trình MSAPR cho kết quả chạy khá tốt trên BAliBASE benchmark. 5.3. So sánh kết quả Để kiểm định kết quả của MSAPR, đề tài sử dụng các file .tfa của BAliBASE, thực hiện việc tính toán đồng thời kết quả của cả MSAPR và CLUSTALW. Ngoài ra để cung cấp một cái nhìn toàn diện hơn, chương trình có sử dụng lại các kết quả tính toán của Thompson [29] với 7 chương trình khác để thực hiện việc so sánh. Các chương trình này bao gồm: SAGA, DIALIGN, SB_PIMA, ML_PIMA, MULTALIGN, PILEUP 8, MULTAL, HMMT. Chi tiết về các chương trình và các kết quả này có thể tham khảo tại trang web Bioinformatics Platform of Strasbourg [5]. Các kỹ thuật toán học cho bài toán so sánh đa trình tự Phạm Mạnh Hùng Trang 70 5.3.1. Giới thiệu về các chương trình được sử dụng CLUSTALW: là một chương trình mã nguồn mở được phát triển bởi Gibson T. (European Molecular Biology Laboratory-EMBL), Thompson J. (National Scientific Research Centre- CNRS (France)), Higgins D. (University College Dublin(UCD) - National University of Ireland, Dublin). CLUSTALW hiện thực bằng C và sử dụng Progressive Algorithm. Đây là chương trình cho kết quả ổn định và tốt nhất trong các chương trình phát triển theo hướng Progressive Algorithm. Phiên bản được sử dụng tính toán trong đề tài là CLUSTALW 1.83. CLUSTALX: là một phiên bản giao diện đồ họa của CLUSTALW. Phiên bản được sử dụng trong đề tài là CLUSTALX 1.83. SAGA được phát triển bởi Cédric Notredame* and Desmond G. Higgins (European Bioinformatics Institute ) sử dụng giải thuật di truyền để tìm lời giải MSA. DIALIGN được phát triển bởi Burkhard Morgenstern(University of Göttingen), DIALIGN sử dụng Progressive Algorithm.(không áp dụng gap penalty). ML_PIMA, SB_PIMA được phát triển bởi Smith, R.F và Smith,T.F. Sử dụng Progressive Algorithm. MULTALIGN: được phát triển bởi Barton G.J. và Sternberg(Laboratory of Molecular Biology Department of Crystallography Birkbeck College, London). MULTALIGN sử dụng mô hình Progressive Algorithm để tìm lời giải MSA. PILEUP 8 được phát triển bởi Genetic Computer Group(GCG) áp dụng Progressive Algorithm để tìm lời giải MSA. MULTAL được phát triển bởi Taylor, sử dụng Progressive Algorithm để hiện thực. HMMT được phát triển bởi Sean R. Eddy(Washington University School, MRC- Laboratory of Molecular Biology in Cambridge), sử dụng mô hình Markov ẩn để tìm lời giải MSA. 5.3.2. So sánh độ chính xác của kết quả Trong phần này sẽ trình bày các kết quả thu được khi chạy MSAPR, và CLUSTALW trên tập 5 nhóm dữ liệu của BAliBASE, và liệt kê thêm các kết quả khác của 7 chương trình nêu ở trên dựa trên một nghiên cứu của Thompson. Chúng ta sẽ xét kết quả của các chương trình khi sử dụng từng nhóm dữ liệu MSA của BAliBASE. Các kỹ thuật toán học cho bài toán so sánh đa trình tự Phạm Mạnh Hùng Trang 71 Nhóm 1. Dựa vào chiều dài của các MSA, BAliBASE chia Nhóm 1 làm 3 tập con: ƒ Tập MSA có chiều dài nhỏ(từ 50-200 phần tử) ƒ Tập MSA có chiều dài trung bình (từ 200-400 phần tử) ƒ Tập MSA có chiều dài lớn( từ 500 phần tử trở lên) Căn cứ vào độ giống nhau I của các sequence tạo nên các MSA, trong mỗi tập con lại chia thành 3 hình thức, Các MSA thỏa mãn I 0.25< . Các MSA có I thỏa 0.2 I 0.4≤ ≤ và các MSA có I thỏa I 0.35≤ . Ba bảng 5.3, 5.4, 5.5 liệt kê độ chính xác của các chương trình khi sử dụng dữ liệu nhóm 1, (có độ giống nhau của các sequence I thỏa mãn I 0.25< ). Cột đầu tiên là tên của các sequence thuộc nhóm 1(I<0.25). Các cột tiếp theo lần lượt là độ chính xác của các chương trình so với kết quả MSA của BAliBASE. Kết quả chạy chương trình với tập MSA có chiều dài nhỏ(gồm 7 tập sequence). Tên MSA PR CLUST ALW SAGA DIALIG N SB_ PIMA ML_ PIMA MULTA LIGN PILE UP 8 MULT AL HMMT 1aboA 0.581 0.688 0.529 0.359 0.312 0.312 0.703 0.521 0.526 0.181 1idy 0.604 0.548 0.342 0.018 0.145 0.062 0.566 0.080 0.080 0.138 1r69 0.382 0.436 0.550 0.406 0.681 0.366 0.325 0.562 0.225 0.100 1tvxA 0.319 0.216 0.278 0.306 0.344 0.344 0.228 0.344 0.244 0.108 1ubi 0.477 0.595 0.452 0.000 0.370 0.493 0.488 0.428 0.428 0.140 1wit 0.666 0.693 0.899 0.851 0.963 0.444 0.842 0.773 0.763 0.549 2trx 0.548 0.690 0.801 0.728 0.451 0.496 0.500 0.453 0.235 0.292 Bảng 5.3 Kết quả chạy chương trình với Nhóm 1 có chiều dài nhỏ Kết quả chạy chương trình với tập MSA có chiều dài trung bình(8 tập sequence). MSA PR CLUSTA LW SAGA DIALIG N SB_ PIMA ML_PI MA MULTA LIGN PILEU P8 MUL TAL HMMT 1bbt3 0.188 0.315 0.652 0.450 0.260 0.260 0.582 0.430 0.160 0.128 1sbp 0.425 0.467 0.543 0.453 0.540 0.456 0.580 0.547 0.537 0.144 1havA 0.260 0.227 0.411 0.130 0.300 0.466 0.419 0.536 0.040 0.133 1uky 0.407 0.517 0.672 0.566 0.684 0.684 0.685 0.571 0.460 0.084 2hsdA 0.529 0.537 0.771 0.679 0.470 0.470 0.470 0.646 0.463 0.117 2pia 0.565 0.601 0.690 0.660 0.740 0.740 0.760 0.850 0.560 0.057 3grs 0.293 0.310 0.689 0.327 0.416 0.416 0.380 0.446 0.347 0.056 kinase 0.615 0.655 0.862 0.764 0.733 0.703 0.643 0.730 0.650 0.277 Bảng 5.4 Kết quả chạy chương trình với Nhóm 1 có chiều dài trung bình Các kỹ thuật toán học cho bài toán so sánh đa trình tự Phạm Mạnh Hùng Trang 72 Kết quả chạy chương trình với tập MSA có chiều dài lớn(8 tập sequence). Bảng 5.5 Kết quả chạy chương trình với Nhóm 1 có chiều dài lớn 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 Testcase(Nhóm 1)(I<0.25) Đ ộ ch ín h xá c MSA PR CLUSTALW MULTAL Độ dài nhỏ Độ dài trung bình Độ dài lớn Hình 5.1 Đồ thị tương quan về độ chính xác của MSAPR, CLUSTALW và MULTAL MSA PR CLUST ALW SAGA DIALI GN SB_PI MA ML_PI MA MULT ALIGN PILEU P8 MULT AL HMMT 1ajsA 0.434 0.371 0.531 0.142 0.486 0.471 0.424 0.556 0.364 0.105 1cpt 0.647 0.696 0.780 0.829 0.792 0.792 0.835 0.865 0.777 0.156 1lvl 0.460 0.394 0.619 0.699 0.559 0.559 0.570 0.587 0.572 0.064 1pamA 0.389 0.433 0.596 0.694 0.513 0.549 0.596 0.641 0.204 0.034 1ped 0.732 0.748 0.748 0.743 0.756 0.756 0.727 0.723 0.730 0.032 2myr 0.448 0.394 0.285 0.284 0.670 0.613 0.422 0.621 0.547 0.050 4enl 0.547 0.562 0.414 0.529 0.701 0.701 0.754 0.669 0.787 0.044 gal4 0.360 0.518 0.500 0.581 0.445 0.445 0.368 0.543 0.406 0.055 Các kỹ thuật toán học cho bài toán so sánh đa trình tự Phạm Mạnh Hùng Trang 73 Nhóm 2: Bảng 5.6 liệt kê độ chính xác của các chương trình khi thực hiện việc tính toán MSA với toàn bộ dữ liệu của nhóm 2. MAS PR CLUST ALW SAGA DIALI GN HMMT SB_PI MA ML_PI MA MULT ALIGN PILE UP8 1aboA 0.759 0.850 0.489 0.384 0.724 0.391 0.220 0.528 0.000 1idy 0.899 0.949 0.548 0.000 0.353 0.000 0.000 0.401 0.000 1csy 0.626 0.804 0.154 0.000 0.000 0.000 0.000 0.154 0.114 1r69 0.887 0.916 0.475 0.675 0.000 0.675 0.675 0.675 0.450 1tvxA 0.867 0.942 0.448 0.000 0.276 0.241 0.241 0.138 0.345 1tgxA 0.737 0.786 0.773 0.630 0.622 0.678 0.543 0.696 0.318 1ubi 0.756 0.826 0.492 0.000 0.053 0.129 0.129 0.000 0.000 1wit 0.648 0.800 0.694 0.724 0.641 0.469 0.463 0.500 0.476 2trx 0.933 0.950 0.870 0.734 0.739 0.850 0.702 0.870 0.870 1sbp 0.721 0.808 0.374 0.043 0.214 0.043 0.054 0.186 0.177 1havA 0.763 0.839 0.448 0.000 0.194 0.259 0.238 0.500 0.493 1uky 0.815 0.855 0.476 0.216 0.395 0.256 0.306 0.585 0.562 2hsdA 0.796 0.836 0.498 0.262 0.423 0.390 0.561 0.593 0.278 2pia 0.803 0.821 0.763 0.612 0.647 0.730 0.695 0.765 0.766 3grs 0.737 0.803 0.282 0.350 0.141 0.183 0.211 0.192 0.159 kinase 0.827 0.914 0.867 0.692 0.749 0.755 0.651 0.830 0.799 1ajsA 0.870 0.876 0.311 0.000 0.242 0.000 0.000 0.311 0.227 1cpt 0.814 0.847 0.776 0.425 0.388 0.184 0.277 0.777 0.688 1lvl 0.799 0.836 0.726 0.783 0.539 0.620 0.688 0.614 0.678 1pamA 0.798 0.812 0.623 0.576 0.530 0.393 0.386 0.566 0.702 1ped 0.878 0.895 0.835 0.773 0.696 0.651 0.647 0.741 0.749 2myr 0.822 0.895 0.825 0.840 0.443 0.727 0.750 0.894 0.786 4enl 0.844 0.869 0.739 0.122 0.213 0.096 0.092 0.384 0.224 Bảng 5.6 Kết quả chạy của các chương trình với các sequence của nhóm 2. Các kỹ thuật toán học cho bài toán so sánh đa trình tự Phạm Mạnh Hùng Trang 74 0 0.2 0.4 0.6 0.8 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 Testcase (Nhóm 2) Đ ộ ch ín h xá c MASPR CLUSTALW HMMT Hình 5.2 Đồ thị tương quan về độ chính xác của MSAPR, CLUSTALW và HMMT Nhóm 3: Bảng 5.7 liệt kê độ chính xác của các chương trình khi thực hiện việc tính toán MSA với toàn bộ dữ liệu nhóm 3 MSAPR CLUS TALW SAGA DIALI GN HMMT SB_PI MA ML_PI MA MULTA LIGN PILEU P8 1idy 0.506 0.591 0.364 0.000 0.227 0.000 0.000 0.045 0.000 1r69 0.342 0.555 0.524 0.524 0.000 0.000 0.905 0.000 0.000 1ubi 0.345 0.582 0.585 0.000 0.366 0.000 0.000 0.000 0.268 1wit 0.602 0.833 0.484 0.500 0.323 0.645 0.323 0.242 0.210 1uky 0.455 0.527 0.269 0.139 0.037 0.083 0.148 0.241 0.083 kinase 0.679 0.762 0.758 0.650 0.478 0.541 0.682 0.688 0.599 1ajsA 0.336 0.405 0.186 0.000 0.006 0.000 0.000 0.000 0.110 1 pamA 0.764 0.783 0.579 0.683 0.169 0.546 0.590 0.546 0.754 1ped 0.721 0.808 0.646 0.641 0.172 0.450 0.507 0.665 0.722 2myr 0.440 0.636 0.494 0.272 0.101 0.278 0.494 0.253 0.310 4enl 0.762 0.799 0.672 0.050 0.050 0.393 0.438 0.652 0.498 Bảng 5.7 Kết quả chạy của các chương trình với các sequence của nhóm 3. Các kỹ thuật toán học cho bài toán so sánh đa trình tự Phạm Mạnh Hùng Trang 75 0 0.2 0.4 0.6 0.8 1 1 2 3 4 5 6 7 8 9 10 11 Testcase(Nhóm 3) Đ ộ ch ín h xá c MSAPR CLUSTALW HMMT Hình 5.3 Đồ thị tương quan về độ chính xác của MSAPR, CLUSTALW và HMMT Nhóm 4: Bảng 5.8 liệt kê độ chính xác của các chương trình khi thực hiện việc tính toán MSA với toàn bộ dữ liệu nhóm 4. MSAPR CLUSTALW SAGA DIALI GN SB_PI MA ML_PI MA MULTA LIGN PILEU P8 1dynA 0.313 0.566 0.000 0.600 0.600 0.600 0.000 0.000 1pysA 0.482 0.558 0.250 0.750 1.000 1.000 0.000 0.750 1ckaA 0.436 0.823 0.375 1.000 1.000 0.000 0.000 1.000 1csp 0.358 0.498 0.000 0.889 0.000 0.000 0.000 0.000 1lkl 0.707 0.718 0.000 1.000 1.000 1.000 0.000 1.000 1mfa 0.580 0.500 0.385 1.000 0.846 1.000 0.385 1.000 1ycc 0.783 0.785 0.485 0.727 0.970 0.818 0.485 0.455 2abk 0.470 0.469 0.000 1.000 0.471 0.471 0.000 0.471 kinase1 0.807 0.873 0.000 1.000 1.000 1.000 0.000 1.000 Bảng 5.8 Kết quả chạy của các chương trình với các sequence của nhóm 4 0 0.2 0.4 0.6 0.8 1 1 2 3 4 5 6 7 8 9 Testcase(Nhóm 4) Đ ộ ch ín h xá c MSAPR CLUSTALW SAGA Hình 5.4 Đồ thị tương quan về độ chính xác của MSAPR, CLUSTALW, SAGA. Các kỹ thuật toán học cho bài toán so sánh đa trình tự Phạm Mạnh Hùng Trang 76 Nhóm 5 Bảng 5.9 liệt kê độ chính xác của các chương trình khi thực hiện việc tính toán MSA với toàn bộ dữ liệu nhóm 5. MSAPR CLUSTALW SAGA DIALI GN SB_PIM A ML_PI MA MULTA LIGN PILEU P8 1pysA 0.590 0.580 0.429 0.762 0.190 0.762 0.429 0.190 1eft 0.236 0.459 0.000 0.579 0.000 0.000 0.000 0.211 1ivy 0.785 0.818 0.735 1.000 1.000 0.882 0.735 1.000 1qpg 0.839 0.903 0.521 1.000 1.000 1.000 1.000 1.000 1thm1 0.714 0.706 0.765 0.765 0.765 0.412 0.412 0.765 1thm2 0.755 0.852 0.774 1.000 0.194 0.194 0.774 0.645 2cba 0.744 0.769 0.767 1.000 0.533 0.767 0.550 0.600 S51 0.627 0.796 0.831 0.646 0.338 0.631 0.646 0.646 S52 0.857 0.902 1.000 1.000 0.515 0.515 1.000 0.515 kinase1 0.807 0.817 0.484 0.806 0.677 0.677 1.000 0.677 kinase2 0.698 0.812 0.667 0.667 0.556 0.444 0.333 0.689 kinase3 0.609 0.777 0.729 0.812 0.333 0.583 0.646 0.729 Bảng 5.9 Kết quả chạy của các chương trình với các sequence của nhóm 5 0 0.2 0.4 0.6 0.8 1 1.2 1 2 3 4 5 6 7 8 9 10 11 12 Testcase(Nhóm 5) Đ ộ ch ín h xá c MSAPR CLUSTALW SAGA Hình 5.5 Đồ thị tương quan về độ chính xác của MSAPR, CLUSTALW, SAGA Như vậy thông qua kết quả kiểm thử các chương trình trên 5 nhóm dữ liệu của BAliBASE, MSAPR cho kết quả chạy ổn định, sự chênh lệch về độ chính xác(với MSA của BAliBASE) so với CLUSTALW là chấp nhận được. So với các chương trình còn lại MSAPR cũng cho những kết quả đánh giá khá tốt và khả quan. Chương trình chạy tốt cho cả tập dữ liệu có độ dài các sequence nhỏ, cũng như với các tập dữ liệu có độ dài trung bình và lớn. Các kỹ thuật toán học cho bài toán so sánh đa trình tự Phạm Mạnh Hùng Trang 77 Phần tiếp theo chúng ta sẽ xem xét về thời gian chạy cũng như vấn đề sử dụng bộ nhớ. 5.3.3. So sánh về mặt thời gian chạy, bộ nhớ Như đã trình bày ở phần thuật toán, chương trình MSAPR nhắm đến việc tăng độ chính xác của chương trình, cũng như giảm thiểu bộ nhớ sử dụng nên so sánh về mặt thời gian MSAPR có thời gian chạy lâu hơn so với CLUSTALW. Khi các sequence có chiều dài nhỏ(50-100 phần tử), thời gian chạy của CLUSTALW và MSAPR là tương đương, khi các sequence có chiều dài trung bình thì thời gian chạy giữa MSAPR và CLUSTALW chênh nhau khoảng 1,5 lần. Khi các sequence có chiều dài lớn, thời gian chạy có thể chênh lệch từ 3-4 lần. Hầu hết các MSA trong BAliBASE có ít hơn 50 sequence, do đó thời gian chạy thường dao động từ 10 giây đến 10 phút, tùy theo chiều dài của các sequence. Khi xét tập sequence lớn từ 100 đến 500 sequence, thời gian chạy của chương trình dao động trong khoảng từ 3 giờ đến 15 giờ. 0 1 0 0 2 0 0 3 0 0 4 0 0 5 0 0 1 0 0 2 0 0 3 0 0 4 0 0 5 0 0 S ố s e q u e n c e Th ờ i g ia n (p hú t) M S A P R C L U S T A L W Hình 5.6 So sánh thời gian thực thi của MSAPR và CLUSTALW Xét về bộ nhớ sử dụng, như đã đề cập trong phần thiết kế giải thuật, chương trình hạn chế tối đa việc cấp phát bộ nhớ. Xét trên tập kết quả từ 5 nhóm dữ liệu của BAliBASE, MSAPR chiếm dụng từ 3.5MB đến 10MB bộ nhớ. Đây là một kết quả khá tốt về mặt quản lý bộ nhớ. Các kỹ thuật toán học cho bài toán so sánh đa trình tự Phạm Mạnh Hùng Trang 78 Chương 6. KẾT LUẬN Sinh tin học(Bioinformatics) đang có những bước phát triển đột phá, và từng bước trở thành một ngành khoa học có vai trò vô cùng quan trọng trong sự phát triển của nhân loại. Được đánh giá là một trong 10 bài toán lớn của Bioinformatics, từ khi được đặt ra cho đến hiện nay, bài toán MSA đã và vẫn đang được nghiên cứu. Nhiều giải pháp được đưa ra để giải quyết bài toán này, tuy nhiên cho đến hiện nay(2007), bài toán MSA vẫn là một bài toán mở, chưa có một lời giải nào có thể giải quyết bài toán trọn vẹn. Đứng trên góc độ của một công trình nghiên cứu, luận văn cố gắng đưa ra một giải pháp nhằm cung cấp thêm một cách thức để giải quyết bài toán này. Tiếp cận theo hướng kết hợp phương pháp Progressive Algorithm và một số kỹ thuật heuristic, luận văn đã tối ưu hóa bài toán PSA về độ chính xác, cũng như không gian nhớ sử dụng cho chương trình, thông qua việc sử dụng giải thuật chia để trị kết hợp với việc sử dụng đồng thời 3 ma trận BLOSUM và các tham số về khả năng sinh gap, để phục vụ cho việc tính toán. Cùng với việc cải thiện chất lượng bài toán PSA, luận văn cũng đã sử dụng kết quả của bài toán TSP để mô tả quá trình phân hoạch cũng như gom nhóm, để thực hiện phép toán align cho bài toán MSA. Với việc kết hợp những kỹ thuật này, chương trình hiện thực cho giải thuật được đề xuất đã cho kết quả khá tốt. Kiểm thử chương trình trên tập dữ liệu mẫu BAliBASE và so sánh kết quả của chương trình với một số phần mềm được đánh giá rất tốt trong việc giải quyết bài toán MSA: CLUSTALW, SAGA, MULTALIGN,…. Về cơ bản chương trình cho lời giải có độ ổn định cao, chính xác không thua kém CLUSTALW(phần mềm được đánh giá là cho kết quả tốt và ổn định nhất), mặc dù thời gian chạy dài hơn so với CLUSTALW tuy nhiên xét về bộ nhớ sử dụng chương trình cho kết quả sử dụng bộ nhớ khá tốt. Đây cũng là mục tiêu hướng tới của luận văn: cung cấp một giải pháp, cho phép giải bài toán MSA có độ chính xác cao, thời gian chạy chấp nhận được và tiết kiệm về mặt bộ nhớ. Thông qua một số thử nghiệm trên một số tập dữ liệu mẫu khác, kết quả thu được của luận văn hoàn toàn có thể cung cấp cho các nhà sinh học một công cụ để giải các bài toán MSA. Các kỹ thuật toán học cho bài toán so sánh đa trình tự Phạm Mạnh Hùng Trang 79 Kết quả đạt được có thể được mở rộng thêm để cải thiện tốc độ chạy của chương trình. Hạn chế về mặt thời gian chạy của chương trình có thể được giải quyết bằng việc: ƒ Đề xuất một phương pháp song song hóa giải thuật được nêu, và triển khai bài toán trên một hệ thống tính toán song song như Cluster hoặc triển khai trên hệ thống tính toán lưới Grid. ƒ Thiết kế một giải thuật nhánh và cận nhằm tối ưu về thời gian chạy cũng như độ chính xác cho bài toán TSP khi số đỉnh của bài toán lớn. Với những sự mở rộng này chúng ta có thể xây dựng một hệ thống tính toán để giải quyết bài toán MSA một cách hữu hiệu. Đây chính là hướng phát triển của luận văn. Các kỹ thuật toán học cho bài toán so sánh đa trình tự Phạm Mạnh Hùng Trang 80 TÀI LIỆU THAM KHẢO 1. Akutsu, T., Arimura, H., and Shimozono, S., “On Approximation Algorithms for Local Multiple Alignment”, Proceedings of the fourth annual international conference on Computational molecular biology, Tokyo, Japan, 2000. 2. Attwood, T.K., Parry D.J., “Introduction to Bioinformatics”, Prentice Hall, 1999. 3. BAliBASE HomePage, 4. Bali_Score Program HomePage, 5. Bioinformatics Platform of Strasbourg, 6. Bonizzoni, P., Vedova, G.D “The complexity of multiple sequence alignment with SP-score that is a metric”, Theoretical Computer Science 2001, 259:63-79. 7. Cormen, T.H., Leiserson, C.E., Rivest, R.L. and Clifford, S., “Introduction to Algorithm”. Chapter 16, Dynamic Programming, MIT, 2001. 8. Eddy, S.R., “Multiple Alignment using Hidden Markov Model”. Proc. Int. Conf. Intell. Syst. Mol. Biol. 1995;3:114-20. 9. European Bioinformatics Institute, “CLUSTALW, CLUSTALX”, European Bioinformatics Institute HomPage, 10. Feng, D. and Doolittle, R., “Progressive alignment of amino acid sequences and construction of phylogenetic trees from them”, Method Enzymol. , 266:368-382 11. Feng, D. and Doolittle, R., “Progressive sequence alignment as a prerequisite to correct phylogenetic trees”, J. Mol. Evol , 25:351-360 12. GALib HomePage 13. Gotoh, O., “Significant improvement in accuracy of multiple protein sequence alignments by iterative refinement as assessed by reference to structural alignments”, J. Mol. Biol. 264:823-838 14. Henikoff, S. and Henikoff, J.G., “Amino acid substitution matrices from protein block”. Proc. Nat. Acd. Sci. USA. 90:10915-10919. Các kỹ thuật toán học cho bài toán so sánh đa trình tự Phạm Mạnh Hùng Trang 81 15. Hirschberg D.S., “A linear Space Algorithm for Computing Maximal Common Subsequences”, Communication of the ACM, Volumn 18, Number 6, 1975 16. Huang, X., and Chao, K.-M,”A generalized global alignment algorithm”, Bioinformatics, Oxford University Press, Vol. 19, no. 2, 2003 pp 228–233. 17. Korostensky, C. and Gonnet,G.H. , ”Near Optimal Multiple Sequence Alignments using a Traveling Salesman Problem approach”. Proceedings of the String Processing and Information Retrieval Symposium & International Workshop on Groupware Page, 1999, pp 105. 18. Korostensky, C. and Gonnet, G.H. , ”Using traveling salesman problem algorithms for evolutionary tree construction”. Bioinformatics, 16:619-927, 2000. 19. Lipman, D. and Pearson, W. ,” Rapid and sensitive protein similarity searches”. Science,227:1435–1441, 1985. 20. Myers, E.W., Miller W., “Optimal alignments in linear space”.Comput Appl Biosci 1988, 4:11-17. 21. NCBI HomePage, 22. Needleman, S. B. and Wunsch, C. D. , “A general method applicable to the search for similarities in the amino acid sequence of two proteins”. Journal of Molecular Biology, 48:443–453, 1970. 23. Nicholas, H.B.Jr, Ropelewski, A.J. and Deerfield, D.W., “Strategies for multiple sequence alignment”, Biotechniques, 32:572-578. 24. Notredame, C., and Higgins, D. G., “SAGA: sequence alignment by genetic algorithm”, Nucleic Acids Research, vol. 24, no. 8, 1996, pp. 1515-1524. 25. Pearson, W.R, Miller, W. , “Dynamic programming algorithms for biological sequence comparison”. Meth. Enzymol. 210:575-601, 1992. 26. Shyu, C., “Multiple Sequence Alignment with Evolutionary Computation“ ,Genetic Programming and Evolvable Machines, Vol 5, Number 2. 2005, pp 121-144. 27. Smith, T. F. and Waterman, .M. S., “Identification of common molecular subsequences”, Journal of Molecular Biology, 147(1):195–197, Mar. 1981. Các kỹ thuật toán học cho bài toán so sánh đa trình tự Phạm Mạnh Hùng Trang 82 28. Thompson , S.M., ”Multiple Sequence Alignment & Analysis”, Florida State University School of Computational Science and Information Technology (CSIT), 2007. 29. Thompson, J.D., Plewniak, F. and Poch, O.”A comprehensive comparision of multiple sequence alignment”, Nucleic Acids Res., 27:2682-2690. 30. Tompa, M. ”Alignment by Dynamic Programming”, 31. TSPBIB HomePage, 32. Wang, L. and Jiang, T., “On the complexity of multiple sequence alignment”. Journal of Computationa Biology, 1994, pp 337–348. 33. Wallace I.M., Blackshields G., Higgins D.G., “Multiple sequence alignments” Curr Opin Struct Biol 2005, 15:261-266. 34. Wayama, W., Takahashi, K., and Shimizu, T., “An approach to amino acid sequence alignment using a genetic algorithm”. Genome Informatics, vol. 6, 1995, pp. 122-123. 35. Yang, Y., “Comparative analysis of methods for multiple sequence alignment”, Stanford University, 2001. 36. Zhong, W., “Using Traveling Salesman Problem Algorithms to Determine Multiple Sequence Alignment Orders”. Các kỹ thuật toán học cho bài toán so sánh đa trình tự Phạm Mạnh Hùng Trang 83 Phụ lục 1. Bảng đối chiếu Thuật ngữ Anh - Việt Các thuật ngữ trong Sinh học: Thuật ngữ Tiếng Anh Thuật ngữ Tiếng Việt Amino Acid Acid amin, là đơn vị cấu trúc cơ bản của protein Biology Sinh học Block Khối Chromosome Nhiễm sắc thể DNA(Deoxyribonucleic Acid) Là một phân tử nucleic acid mang thông tin di truyền mã hóa cho hoạt động sinh trưởng và phát triển của các dạng sống. DNA chứa các gene cấu trúc.(còn gọi là ADN) Evolution Tree Cây tiến hoá Genomic Công nghệ gene Gene Là một đoạn DNA mang một chức năng nhất định trong quá trình truyền thông tin di truyền Identity Giống nhau Molecular Biology Sinh học phân tử Nucleotide Nu, là các đơn phân cấu thành DNA. Gồm 4 loại A,C,G,T Parent Thế hệ cha mẹ Phylogenetic Tree Cây sinh loài Protein Hợp chất đại phân tử được tạo thành từ rất nhiều các đơn phân là các acid amin. Protein Family Họ các protein có liên quan với nhau RNA(Ribonucleic Acid) Là cơ sở di truyền ở cấp độ phân tử(còn gọi là ARN) Sequence Chuỗi trình tự Secondary Structure of Proteins Cấu trúc bậc 2 của Protein Similarity Tương đồng Transmembrane protein Loại Protein nối liền các lớp màng nhầy. Các kỹ thuật toán học cho bài toán so sánh đa trình tự Phạm Mạnh Hùng Trang 84 Tertiary Structure of Proteins Cấu trúc bậc 3 của Protein Các thuật ngữ trong chuyên ngành(Sinh tin học): Thuật ngữ Tiếng Anh Thuật ngữ Tiếng Việt Align Thực hiện so sánh(gióng hàng, gióng cột) 2 hay nhiều trình tự. BAliBASE benchmark Dữ liệu kiểm thử BAliBASE BAliScore Độ chính xác của MSA so với MSA mẫu của BAliBASE Bioinformatics Sinh tin học BLOSUM Matrix Ma trận BLOSUM Center Star Algorithm Giải thuật chọn phần tử trung tâm Circular Tour Chu trình, lời giải bài toán TSP Crossover Phép lai ghép Deletion Sự mất đi các phần tử Deletion gap Các gap được sinh ra bằng cách xóa đi các phần tử của sequence. Divide and Conquer Algorithm Giải thuật chia để trị Distance Matrix Ma trận khoảng cách Dynamic Programming Quy hoạch động Execution Time Thời gian thực thi FASTA Chuẩn định dạng FASTA lưu trữ các sequence Fitness Function Hàm thích nghi Feng-Doolittle Algorithm Giải thuật của Feng-Doolittle GALib Thư viện hàm cho phép thiết kế, hỗ trợ lập trình các ứng dụng về thuật giải di truyền Gap Phần tử sinh ra trong quá trình so sánh các trình tự Gap Open Penalty Khả năng mở gap Gap Extension Penalty Khả năng mở rộng của gap Genetic Algorithm-GA Giải thuật di truyền Các kỹ thuật toán học cho bài toán so sánh đa trình tự Phạm Mạnh Hùng Trang 85 Gene Finding Problem Bài toán tìm gene Global Sequence Alignment Phép so sánh trình tự theo hướng toàn cục Guide Tree Cây mô tả quá trình so sánh của các sequence Heuristic Các kỹ thuật trong Trí tuệ nhân tạo, giúp giải quyết các bài toán 1 cách tự nhiên. Insertion Sự thêm vào các phần tử Insertion gap Các gap được sinh ra do sự thêm các phần tử vào sequence Iterative Algorithm Giải thuật tìm MSA bằng cách sinh ra 1 MSA có chất lượng thấp và cải tiến dần theo các bước lặp Local Sequence Alignment Phép so sánh trình tự theo hướng cục bộ Match Sự tương ứng, phù hợp giữa 2 thành phần của 2 sequence MSF Chuẩn định dạng MSF lưu trữ các MSA Multiple Sequence Alignment-MSA So sánh đa trình tự Mutation Phép đột biến NCBI Trung tâm quốc gia về Thông tin Công nghệ sinh học của Hoa Kỳ, cung cấp ngân hàng gene, Cơ sở dữ liệu Protein, các chương trình phục vụ cho mục đích sinh học… Near Optimal MSA MSA gần tối ưu Nondeterministic Polynomial-NP Bài toán NP, không thể tính với độ phức tạp đa thức Optimal MSA Phép so sánh đa trình tự tối ưu(tốt nhất) Order for Alignment Thứ tự so sánh của các sequence Pairwise Distance Khoảng cách của các cặp sequence Pairwise Sequence Alignment-PSA So sánh 2 trình tự Progressive Algorithm Giải thuật tìm MSA thông qua việc sử dụng bài toán PSA nhiều lần PMX(Partially Mapped Crossover) Kỹ thuật lai ghép từng phần Population Quần thể Scoring Function Hàm đánh giá Các kỹ thuật toán học cho bài toán so sánh đa trình tự Phạm Mạnh Hùng Trang 86 Scoring Matrix Ma trận đánh giá Scoring Method Phương pháp đánh giá Selection Phép chọn lọc Sequence Trình tự Sequence Alignment So sánh trình tự Subtitution Sự thay thế Sum of Pair Phương pháp đánh giá theo tổng các cặp trình tự Traceback Quá trình tìm alignment từ các vết Traveling Salesman Problem-TSP Bài toán người bán hàng Các kỹ thuật toán học cho bài toán so sánh đa trình tự Phạm Mạnh Hùng Trang 87 Phụ lục 2. Từ viết tắt Tên viết tắt Tên đầy đủ BLOSUM Block Substitution Matrix BAliBASE Benchmark Alignment DataBase CSDL Cơ sở dữ liệu DNA Deoxyribonucleic Acid GA Genetic Algorithm FASTA Fast Alignment Search Tool HMM Hidden Markov Model MSA Multiple Sequence Alignment NCBI National Center for Biotechnology Information NP Nondeterministic Polynomial NST Nhiễm Sắc Thể PSA Pairwise Sequence Alignment RNA Ribonucleic Acid SP Sum of Pair TSP Traveling Salesman Problem Các kỹ thuật toán học cho bài toán so sánh đa trình tự Phạm Mạnh Hùng Trang 88 Tham khảo Chỉ mục A amino acid, 6, 9, 10, 12, 13, 14, 16, 17, 20, 21, 25, 38 Average Information Content, 17 B BAliBase, 3 BaliScore, 69 Bioinformatics, iii, 1, 70, 78 block, 13 C Center Star Alignment, 33, 37 Circular Tour, 51, 52, 53, 54, 55, 56 CLUSTALW, 19, 40, 41, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78 Crossover, 57 Chromosome, 1, 57, 58, 59, 60 D DIALIGN, 19, 69, 70, 71, 72, 73, 74, 75, 76 Distance Matrix, 51, 53, 61, 65 Divide and Conquer Algorithm, 5, 43, 65 DNA, 1, 2, 6, 7, 10, 19 Dynamic Programming, 2, 18, 19, 24 E Entropy, 17 Execution Time, v, 43, 68, 77, 78, 79 F FASTA, 19, 63, 69 Feng-Doolittle Algorithm 4, 38, 39, 40 fitness function, 58 G Gap, 11, 14, 15 deletion, 11, 27, 28 insertion, 11, 27, 28 Gap Extension Penalty, 15 Gap Open Penalty, 15 gene, 1, 2, 6, 7, 10, 19, 57, 59, 60 Gene Finding Problem, 6 Genetic Algorithm, 5, 21, 57 Genomic, 1 Giải thuật 1A, 51 Giải thuật 1B, 55, 57 Giải thuật cải tiến không gian nhớ, 29 Gotoh Algorithm, 28 Guide Tree, 40, 54 H heuristic, 2, 3, 4, 18, 20, 23, 24, 33, 40, 62, 78 Hidden Markov Model, 19, 21 HMMT, 22, 69, 70, 71, 72, 73, 74, 75 I Identity, 6, 68, 71 Iterative Algorithm, 18, 19 M ML_PIMA, 69, 70, 71, 72, 73, 74, 75, 76 MSAPR, 60, 66, 67, 68, 69, 70, 72, 74, 75, 76, 77 MSF, 64, 69 MULTAL, 19, 69, 70, 71, 72 MULTALIGN, 19, 40, 69, 70, 71, 72, 73, 74, 75, 76, 78 Mutation, 58 N NCBI, 3, 63 Near Optimal Alignment, 3, 18 NP, 2, 18, 23, 51, 62 nucleotide, 9, 10, 12, 17, 21, 25 O Oder for Alignment, 5, 50, 51, 52, 54, 58, 61, 62 Optimal Alignment, 11, 24, 25, 26, 33, 36, 43, 44, 47 P Pairwise Distance, 40, 49 Parent, 57 Phylogenetic Tree, 1 PILEUP, 19, 40 PMX(Partially-Mapped Crossover), 59 Population, 21, 57, 58, 59 Progressive Algorithm 2, 3, 4, 18, 19, 23, 24, 37, 39, 40, 41, 49, 50, 52, 70, 78 protein, 1, 2, 6, 7, 9, 10, 13, 14, 19, 66, 67, 68, 69 protein family, 9 R RNA, 1, 6, 7, 83 S SAGA, 21, 69, 70, 71, 72, 73, 74, 75, 76, 78 SB_PIMA, 69, 70, 72, 73, 74, 75, 76 Scoring function, 5, 7, 12, 13, 14, 15, 16, 17, 20, 22, 25, 32, 34, 36, 38, 39, 40, 44, 48 Scoring Matrix BLOSUM, 3, 5, 13, 14, 47, 48, 61, 65, 78 Chemical Similarity Matrix, 13 Genetic Code Matrix, 13 Identity Matrix, 13 Các kỹ thuật toán học cho bài toán so sánh đa trình tự Phạm Mạnh Hùng Trang 89 Subtitution Matrix, 13 Scoring Method, 15 Sum-of-Pair, 16, 18, 32, 40, 50 Selection, 58 Sequence Alignment Global, 7 Local, 7 Multiple, 2, 3, 4, 5, 9, 10, 13, 16, 17, 18, 19, 20, 21, 22, 23, 24, 32, 33, 34, 37, 39, 41, 42, 49, 50, 60, 61, 62, 63, 65, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79 Pairwise, 2, 3, 4, 5, 7, 8, 15, 18, 23, 24, 25, 26, 33, 34, 35, 37, 38, 42, 43, 44, 48, 49, 51, 53, 57, 60, 61, 65, 78 Similarity, 7, 12, 13, 14, 16, 17, 39, 40, 51, 68 Substitution, 10, 14 T Tertiary Structure of Protein, 6, 9, 68 Traceback, 20, 26, 27, 45 transmembrane protein, 68 Traveling Salesmans Problem(TSP), 3, 5, 50, 51, 52, 53, 55, 57, 59, 60, 62, 65, 78, 79