Dự đoán cấu trúc bậc hai rna bằng sự kết hợp thuật toán di truyền và logic mờ

Nội dung text: Dự đoán cấu trúc bậc hai rna bằng sự kết hợp thuật toán di truyền và logic mờ

1. Kỷ yếu Hội nghị KHCN Quốc gia lần thứ XI về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR); Hà Nội, ngày 09-10/8/2018 DOI: 10.15625/vap.2018.00015 DỰ ĐOÁN CẤU TRÚC BẬC HAI RNA BẰNG SỰ KẾT HỢP THUẬT TOÁN DI TRUYỀN VÀ LOGIC MỜ 1 2 3 2 Đoàn Duy Bình , Phạm Minh Tuấn , Đặng Đức Long , Nguyễn Hữu Danh 1 Khoa Tin học, Trường Đại học Sư phạm, Đại học Đà Nẵng 2 Khoa Công nghệ thông tin, Trường Đại học Bách khoa, Đại học Đà Nẵng 3Viện Nghiên cứu và Giáo dục Việt Anh, Đại học Đà Nẵng doanduybinh@gmail.com, pmtuan@dut.udn.vn, long.dang@vnuk.edu.vn, danh.nghuu@gmail.com TÓM TẮT: Trong bài báo này, chúng tôi giới thiệu sự kết hợp giữa thuật toán GA với logic mờ (Fuzzy Logic). Từ thuật toán kết hợp này chúng tôi áp dụng cho bài toán dự đoán cấu trúc bậc hai của các phân tử RNA (Ribonucleic Acid). Bài toán dự đoán cấu trúc bậc hai mà chúng tôi đề cập dựa trên phương pháp nhiệt động lực học, với việc tìm cấu trúc bậc hai có năng lượng cực tiếu. Với kết quả của các cấu trúc tìm được bằng thuật toán kết hợp mà chúng tôi giới thiệu, chúng tôi hy vọng sẽ đóng góp vào kho dữ liệu của sinh học phân từ, phục vụ cho các nghiên cứu trong ngành sinh học phân tử. Đồng thời cũng giới thiệu được một cách tiếp cận mới về thuật toán di truyền. Từ khóa: RNA; Thuật toán di truyền; Logic mờ; Cấu trúc bậc hai; Dự đoán; I. GIỚI THIỆU RNA là một chuỗi nucleotide đơn bao gồm adenine (A), guanine (G), cytosine (C) và uracil (U) và nó có thể tự gấp lại để tạo thành cấu trúc bậc hai với các cặp base như A ≡ U, G = C, và G - U. Có nhiều dạng RNA khác nhau được tìm thấy: RNA nhân không đồng nhất (hnRNA), RNA thông tin (mRNA), RNA vận chuyển (tRNA), RNA ribosome (rRNA) và RNA nhân nhỏ. Về mặt cấu trúc, hnRNA và mRNA là cả hai đều là sợi đơn, trong khi rRNA và tRNA hình thành cấu hình phân tử ba chiều. Mỗi loại RNA có một vai trò khác nhau trong các quá trình tế bào khác nhau như mang thông tin di truyền (mRNA), dịch mã (rRNA) và chuyển mã di truyền (tRNA). Mỗi chuỗi RNA, có thể gấp lại để hình thành một số cấu trúc bậc hai bậc hai có thể xảy ra. Xác định một cấu trúc bậc hai chính xác được gọi là bài toán dự đoán cấu trúc bậc hai [1]. Các phương pháp vật lý để xác định cấu trúc RNA, chẳng hạn như tia X, tinh thể và quang phổ cộng hưởng từ hạt nhân (Nuclear Magnetic Resonance - NMR) là khó khăn, dễ bị lỗi, tốn thời gian, tốn kém chi phí và trong một số trường hợp là không khả thi [2]. Do đó, các phương pháp tính toán là các phương án thay thế thích hợp để dự đoán cấu trúc bậc hai của một phân tử RNA. Hiên nay, phương pháp dự đoán cấu trúc RNA tính toán chủ yếu tập trung vào dự đoán cấu trúc bậc hai RNA - tập hợp các cặp base hình thành khi các phân tử RNA gấp lại. Cấu trúc ba chiều của ARN, được xác định bởi các tọa độ của các nguyên tử, được gọi là cấu trúc bậc ba. Mặc dù rất khó khăn, nhưng vẫn có những cách tiếp cận để dự đoán cấu trúc bậc ba RNA [3], [4]. Dự đoán cấu trúc bậc hai của RNA dễ hơn cấu trúc bậc ba và cấu trúc bậc hai của RNA làm sáng tỏ cấu trúc bậc ba của RNA. Hai phương pháp tính toán khác nhau tồn tại cho dự đoán cấu trúc bậc RNA đó là: Phương pháp so sánh và Tối ưu hóa nhiệt động lực học. Kể từ khi RNA gấp lại là tùy thuộc vào luật nhiệt động lực học, có một giả định rằng cấu trúc chính xác là một cấu trúc năng lượng thấp. Sự ổn định của cấu trúc bậc hai phụ thuộc vào lượng năng lượng tự do được giải phóng để tạo thành các cặp base. Do đó, năng lượng tự do của cấu trúc càng tiêu cực, thì một chuỗi đặc biệt ổn định hơn được hình thành. Cấu trúc này được gọi là cấu trúc bậc hai năng lượng tự do tối thiểu (MFE) [5]. Trong trường hợp chỉ có chuỗi của một phân tử RNA đã biết, phương pháp ab initio được sử dụng để thực hiện dự đoán cấu trúc bậc hai RNA như là một bài toán cực hiểu hóa năng lượng thông qua việc sử dụng các mô hình nhiệt động lực học. Những phương pháp này là một trong hai quy hoạch động hoặc metaheuristics. Thuật toán áp dung cho Mfold và RNAfold là thuật toán quy hoạch động cho dự đoán cấu trúc bậc hai RNA dựa trên việc tìm năng lượng tự do tối thiểu. Thuật toán quy hoạch động như kỹ thuật toán học có thể đạt tối ưu toàn cục trong các bài toán nhỏ. Nhưng trong các bài toán thực tế, có một số nhược điểm. Ví dụ, khi số lượng các biến tăng lên, số lượng các đánh giá của hàm đệ quy cũng sẽ tăng theo cấp số nhân. Đối với bài toán dự đoán cấu trúc bậc hai RNA, số lượng lớn các phương án cấu trúc làm cho khó xác định cái nào chính xác hơn. Ngoài ra, các thuật toán này chỉ dự đoán cấu trúc năng lượng tự do tối thiểu, trong khi cấu trúc tự nhiên thường có năng lượng tự do khoảng 5-10 % từ năng lượng tự do tối thiểu của chuỗi. Mặt khác, nhiều thuật metaheuristics đã được đề xuất như thuật toán di truyền; RnaPredict [6] -Mô phỏng luyện kim; SARNA-Predict - Tối ưu hóa bầy đàn; HelixPSO [7] và thuật toán tìm kiếm Harmony; HSRNAFold [8]. Các thuật toán này tạo ra một vector cấu trúc thay vì chỉ cấu trúc năng lượng tự do tối thiểu. Đối với dự đoán cấu trúc bậc hai, một thuật toán di truyền là thực tế hơn vì nó có thể giải quyết vấn đề kích thước lớn. Trong bài báo này, chúng tôi sẽ giải quyết bài toán dự đoán cấu trúc bậc hai RNA sử dụng thuật toán di
2. Đoàn Duy Bình, Phạm Minh Tuấn, Đặng Đức Long, Nguyễn Hữu Danh 111 truyền được lại với logic mờ. Kết quả thử nghiệm của chúng tôi cho thấy rằng với thuật toán di truyền mới của chúng tôi có được một cải tiến lớn đối với lên thuật toán truyền thống. Hình 1. Mô hình mà chúng tôi sử dụng trong nghiên cứu này Bài báo này được chúng tôi trình bày những vấn đề sau: giới thiệu về bài toán dự đoáán cấu trúc bậc hai RNA được thể hiện trong phần II, phần III giới thiệu về thuật toán di truyền, mục IV giới thiệu về logic mờ và giới thiệu sự kết hợp thuật toán di truyền với logic mờ. Phần V và VI là những kết quả của thực nghiệm khi triển khai thuật toán, đánh giá và kết luận. II. DỰ ĐOÁN TRÚC BẬC HAI RNA 2.1. Cấu trúc bậc hai Các phân tử RNA được mô tả đặc điểm bởi một chuỗi của bốn loại ribonucleotide hooặc là các base: Adenine (A), Cytosine (C), Guanine (G) và Uraciil (U). Một chuỗi tuyến tính các base của sợi RNA tạo thành cấu trúc chính hoặc chuỗi. Dưới đây mà một số khái niệm làm sáng tỏ về chuỗi RNA và cấu trúc bậc hai RNA như sau: a) Một chuỗi RNA có chiều dài là n ribonucleotide là một chuỗi x , , , , trong đó ∈ ,C,G,U,∀ ∈ 1, , n. b) Trong một cấu trúc bậc hai của RNA, các cặp base được hình thành là một trong ba cặp như sau: C-G (G-C), A-U (U-A) và G-U (U-G). Các cặp base {(A-U), (U- A), (C-G), (G-C)} gọi là các cặp Watson-Crick hoặc là các cặp base chính tắc. Cặp base {(G-U), (U-G)} được gọi cặp base không bền vững (Wobble). Sự ổn định của các cặp base được cho bởi mối quan hệ saau đây: C-G>> A-U ≥ G-U [9], [10]. Hình 2. Các cặp base chính tắc c) Với , được biểu diễn cho cặp base hình thành bởi base tại vị trí thứ i và base tại vị trí thứ j, sao cho một tập con của ∈Y, , 1 gọi là cấu trúc bậc hai RNA nếu y thỏa mãn các điều kiện sau: ,  là một cặp base chính tắc; Cho , ∈,, ∈, nếu thì ; Nếu , ∈, thì 3; Mỗi base chỉ ghép cặp với một và chỉ một base khác trong cấu trúc. d) Chúng ta có thể gọi hai cặp base , và ,,, tương thích nếu:  và  (chúng cùng một cặp base); (, trước ,) hoặc; ^′^′ ├, ┤ bao gồm ,); e) Cấu trúc bậc hai RNA không có các nút thắt (pseudoknot free, Hình 3.) y tương ứng với chuỗi RNA x có độ dài n là cấu trúc bậc hai RNA trong đó bất kỳ hai cặp base , và ,, chúng đều đang lồng nhau, tức là i
3. 112 DỰ ĐOÁN CẤU TRÚC BẬC HAI RNA BẰNG SỰ KẾT HỢP THUẬT TOÁN DI TRUYỀN VÀ LOGIC MỜ j, hoặc là liên tiếp nhau, tức là ij . Ở đây chúng ta giả định mà kkhông mất tính tổng quát rrằng i j, và i. Hình 3. Cấu trúc RNA không có nút thắt 2.2. Bài toán dự đoán cấu ttrúc bậc hai RNA Bài toán dự đoán cấu trúc bậc hai RNA có thể được trình bày như sau: Cho: một chuỗi RNA có độ dài , với , , , , trong đó ∈,,,,∀∈1, , và mô hình năng lượng tự do [11]. Mục tiêu: phát triển một thuật toán , trả về một hoặc nhiều cấu trúc bậc hai tương ứng với chuỗi . Phương pháp phổ biến để có được cấu trúc bậc hai là tìm ra cấu trúc có mức năng lượng tự do cực tiếu (minimum free energy - MFE) y của một chuỗi RNA đã cho và theo mô hìình năng lượng . Cách tiếp cận này dựa trên giả định rằng các phân tử RNA có khuynh hướng gấp vào các cấu hình năng lượng tự do cực tiểu của chúng, được thể hiện qua công thức sau: ∈ arg ∈ ∆, , (1) Trong đó biểu thị một tập tất cả các cấu bậc hai có thể của chuỗi , ∆ là hàm năng lượng cho phép đo độ ổn định của cấu trúc và arg min ∈ ∆ biểu thị cho năng lượng của mà ∆ llà cực tiểu. Một mô hình năng lượng tự do RNA là một cấu trúc lý thuyết miêu tả cho các quy tắc vvà các biến tùy theo các chuỗi RNA nào mà hình thành nên các cấu trúc bậc hai tương ứng. Chúng tôi xeem xét một mô hình năng lượng tự do RNA có ba thành phần chínnh: 1. Một tập hợp các cấu trúc thành phần , , ,, trong đó là số cấu trúc thành phần của cấu trúc bậc hai RNA. Một cấu trúc thành phần là một đoạn cấu trúc bậc hai RNA có nhiệt động lực học được coi là quan trọng cho việc tạo thàànnh cấu trúc bậc hai RNA. 2. Một tập hợp các tham số năng lượng tự do ,, , với tham số năng lượng tự do tương ứng với cấu trúc thành phần . Tham số đôi khi được ký hiệu là ∆. 3. Một hàm năng lượng tự do xác định tính ổn định nhiệt động lực học của một chuỗi được gấp thành một cấu trúc bậc hai cụ thể phhù hợp với . Hầu hết các mô hình cho dự đoán cấu trúc bậc hai giả định rằng hàm năng lượng tự do của chuỗi và cấu trúc là tuyến tính trong mô hình năng lượng , có dạng: ∆, , ≔ ∑ , , ⊺ (2) Trong đó ≔ , , , biểu thị véc tơ của các giá trị tham số , , lần xuất hiện của cấu trúc thành phần trong cấu trúc bậc hai của chuỗi và , :, , ,, biểu thị véc tơ của số lượng đặc điểm , Các cấu trúc thành phần của cấu trúc bậc hai RNA bao gồm:
4. Đoàn Duy Bình, Phạm Minh Tuấn, Đặng Đức Long, Nguyễn Hữu Danh 113 Hình 4. Cấu trúc thành phần của RNA Năng lượng trên cấu trúc bậc hai của chuỗi chính là năng lượng đónng góp của các cấu trúc thành phần trong cấu trúc bậc hai là như sau: o Vòng kẹp tóc (Hairpin Loop): , ; o Xếp chồng (Stack): , , , ; o Vòng bên trong (Internal loop): , ,’, ’; o Vòng lồi ra (Bulge): , ; o Vòng nhiều nhánh (MultiLoop): ,,,,, ; Năng lượng eM được tính như sau: ’ (3) trong đó: , , là các trọng số, với: năng lượng của cặp base đóng vòng; số lượng xoắn (helices); ’ số lượng base không ghép cặp trong vòng; , năng lượng tưng ứng với và ’. III. THUẬT TOÁN DI TRUYỀN TRONG BÀI TOÁN DỰ ĐOÁN CẤU TRÚC BẬC HAI RNA 3.1. Giới thiệu Thuật toán di truyền (GA) là kỹ thuật tìm kiếm ngẫu nhiên toàn cục với việc giả lập các quy luật tiến hóa và di truyền học để cố gắng tìm ra giải pháp tối ưu cho bài toán tối ưu hóa phức tạp. GA đạt được về mặt lý thuyết và thực nghiệm đã được chứng minh nhằm cung cấp cho việc tìm kiếm mạnh mẽ trong không gian phức tạp và chúng được áp dụng rộng rãi trong kỹ thuật, kinh doanh và khoa học. Thuật toán di truyền được mô tả như sau: Bước 1: Khởi tạo quần thể; Bước 2: Đánh giá, nếu đủ tốt thì kết thúc; Bước 3: Chọn lọc; Bước 4: Lai ghép; Bước 5: Đột biến; Bước 6: Quay lại bước 2; Sơ đồ thuật toán: Hình 5. Thuật toán di truyền
5. 114 DỰ ĐOÁN CẤU TRÚC BẬC HAI RNA BẰNG SỰ KẾT HỢP THUẬT TOÁN DI TRUYỀN VÀ LOGIC MỜ 3.2. Các bước xây dựng thuật toán di truyền cho bài toán 1. Bước 1: Cách đơn giản nhất áp dụng thuật toán di truyền đơn cho bài toán dự đoáán cấu trúc bậc hai tại bước khởi tạo quần thể ta chọn ngẫu nhiên các ∈ . Sau đó tạo cấu trúc bằng cách sử dụng các cặp ngoặc “(“ , “)” và dấu “.”, cách tạo như sau: ứng với cặp “(“ và “)” là liên kết của các cặp base chính tắc (II.A), dấu chấm biểu thị các base không được ghép cặp. Ví dụ: 2. Bước 2: Đánh giá các nghiệm dựa vào năng lượng đã được định nghĩa (công thức 2); 3. Bước 3: Lựa chọn các nghiện có mực năng lượng thấp với tỷ lệ là 70 %, còn các nghiệm có mức năng lượng cao thì bị loại bỏ, sau đó sẽ được bổ sung các nghiệm con sau khi lai ghép ở bước 4. 4. Bước 4: Quá trình lại ghéo đơn giản bằng cách sử dụng lai ghép đồng nhất hoặc lai ghép một điểm. Tuy nhiiên việc lại ghép này gây ra tình trạng phá vỡ cấu trúc đã được định nghĩa ở trên. Ví dụ có thể sinh ra các nghiệm con có ngoặc mở “(“ nhưng không có ngoặc đóng “)” hoặc ngược lại hoặc chỉ có các dấu chấm “.”. Vấn đề này nhóm tác giả khắc phục bằng cách áp dụng logic mờ, sẽ trình bày ở phần tiếp theo. 5. Bước 5: Đột biến, tương tự như lai ghép nó cũng sinh ra những cấu trúc không phù hợp như đã định nghĩa. Trrong khuôn khổ bài báo này nhóm tác giả sẽ chưa trình bày phương pháp áp dụng logic mờ. Chúng tôi sẽ trình bày trong các bài báo tiếp theo. IV. LOGIC MỜ 4.1. Giới thiệu Mô hình hệ thống Fuzzy Logic (FL) là mô hình dựa trên tri thức với các quy tắc ngôn ngữ. Tập mờ được mô tả cho tất cả các biến đầu vào và đầu ra và tập luật. Logic mờ đảm bảo các phương tiện để xử lý kiến thức này và tính toán các giá trị đầu ra cho các dữ liệu đầu vào nhất định. Vấn đề chính của cách tiếp cận này là tìm ra một bộ quy tắc ngôn ngữ phù hợp để xác định hệ thống được mô phỏng [12]. Hệ thống mờ được biểu diễn theo các quy tắc if-then hoặc các câu lệnh có điều kiện mờ như trong biểu thức của dạng IF A THEN B,, trong đó A và B là nhãn của các tập mờ. Tập hợp các quy tắc nên được hoànn thành và cung cấp một câu trả lời cho mọi giá trị đầu vào. Một số đặc điểm quan trong của FL là: Kết luận rõ ràng có thể được rút ra từ hệ thống phức tạp tạo ra mơ hồ, không rõ ràng, hoặc thông tin không chính xác, Lý luận chính xác được xem như là một trường hợp giới hạn của lý luận gần đúng, Bất kỳ hệ thống logic nào cũng có thể được mờ. Một hệ thống suy luận mờ (FIS), như được thấy trong sử dụng các hàm thành viên để “làm mờ” dữ liệu đầu vào và sau đó áp dụng một tập hợp các quy tắc cho dữ liệu mờ. Hình 6. Sơ đồ cơ bản của logic mờ Trong nghiên cứu này, nhóm tác giả tập trung ứng dụng logic mờ để giải quyết bài toán lai ghép như đã trình ở trên. Trong việc lại ghéo một điểm có thể dẫn đến kết qua không như kỳ vọng vì có hiện tượng phá vỡ cấu trúc, vì vậy
6. Đoàn Duy Bình, Phạm Minh Tuấn, Đặng Đức Long, Nguyễn Hữu Danh 115 việc trao đổi cấu trúc có thể thực hiện bằng điểm mờ. Có nghĩa là mặc dù hoán đỗi tại một điểm nhưng những vị trí xa điểm lại ghép thì xác suất tái hiện như lại ghép một điểm một điểm thông thường. Cách thể hiện lai ghép một điểm như sau: Trước khi lai ghép Sau khi lai ghép Các con được sinh ra trong quá trình lai ghép được thể hiện như sau: 1 , θ(i) < 2 1 , ẹ 2 1 , θ(i) ≥ 2 1 , ẹ 2 Trong đó: 1, 1, (4) 0, 1, 4.2. Lai ghép thuật toán di truyền và loogic mờ Lợi ích chính của thuật toán di truyền là nó có thể được sử dụng để tìm các giá trị được tối ưu hóa từ không gian tìm kiếm lớn cũng như làm cho hệ thống có thể học hỏi. Đồng thời, hạn chế chính của thuật toán di truyền là nó không có khả năng lưu trữ kiến thức miền nhưng GA có thể được sử dụng để tìm giá ttrị tối ưu cho các tham số hàm thành viên, đặc biệt khi chọn lọc thủ công các giá trị của chúng trở nên khó khăn hoặc mất quá nhiều thời gian để đạt được. Để xử lý thông tin được nêu không chính xác, cách tiếp cận ra quyết định mờ đã được sử dụng. Thực hiện điểm mờ trong lai ghép được thể hiện như sau: Lai ghép có điểm mờ Việc tạo ra y và y thực hiện ngẫu nhiên nhiều lần và chọn ra các ycó mức năng lượng thấp nhất. Sờ đồ thuật toán di truyền có kết hợp với logic mờ.
7. 116 DỰ ĐOÁN CẤU TRÚC BẬC HAI RNA BẰNG SỰ KẾT HỢP THUẬT TOÁN DI TRUYỀN VÀ LOGIC MỜ Hình 6. Thuật toán di truyền kết hợp với logic mờ V. KẾT QUẢ VÀ ĐÁNH GIÁ 5.1. Kết quả 1. Các thông số cơ ban của thuật toán: static int AMOUNT\_OF\_INDIVIDUAL = 100000; static List population = new; ArrayList (); static Double Pc = 0.7; static Double Pm = 0.3; static float bestFreeEnergies = 99999; static int positionOfBestFreeEnergies = 0;; 2. Các chuỗi đầu vào, kết quả và so sánh
8. Đoàn Duy Bình, Phạm Minh Tuấn, Đặng Đức Long, Nguyễn Hữu Danh 117 a) E.Coli 221 Bases Thông tin chuỗi Bảng 1. Thông tin chuỗi E.Coli 221 Bases Tên chuỗi Thông tin Chuỗi E.Coli 221 IDENTIFIERS ACAUGGGGGAUAAGGGCAGGCGG Bases UGAAUGCCUUGGCUCUCGGAGG dbEST Id: 78864696 CGAAGGAAGGACGUGAUAAGCUG EST name: CFSWEC38 CGAUAAAGCCCGGCGUAGGCGCA AAUAGCCGUUAAUACCGGGGUU GenBank Acc: JZ515411 UCCGAAAUGGGGCAACCCGCCGG GenBank gi: 5577806034 GAGUAAUUCCGGCAUCUCUUGA LIBRARY AAGAGGGAGGCGAACGUGGGGA ACUGAAAACAUCUCAGUACCUGC Lib Name: LIBEST_027994 Immune responses AGGAAAAAAAAAAAAAAAAAAA of Coptotermes formosanus. Shiraki workers A against Escherichia coli Organism: Coptotermes formosanus Organ: wholle body Kết quả và so sánh Bảng 2. Kết quả và so sánh giữa việc áp dụng hai thuật toán GA Thuật toán di truyền Thuật toán di truyền kết hợp với logic mờ Năng Năng Cấu trúc Cấu trúc lượng lượng Best .(((( ((((( Best free ((((((((.((( free ((((((( Energy: - ))) (((((((( ) Energ ((( ))) ))))))) 31.9 y: - ))))) )))) )))) ))).)))))))) (((((. 23.7 .( (((( ))))).))))) b) Bmori 219 Bases Thông tin chuỗi Bảng 3. Thông tin chuỗi Bmori 219 Bases Tên chuỗi Thông tin Chuỗi Bmori 219 IDENTIFIERS AACCACGGCAUGUGCAAC Bases dbEST Id: 45323636 GGGUGACUCCGGCAGCGC EST name: EST0213 UUCUAGUCCGCCUGGACC GGCGGCACCCAGAUCGGA GenBank Acc: EL928597 AAUCGUGUCGUGGGGCUU GenBank gi: 133905746 CCCCCUGCGCCCGCGGCGC LIBRARY UUCCCGAUAUGUUCGUCC Lib Name: LIBEST_020979 ARS-CICGRU ONmgEST GGAGUCAGCGCCUUCCAA Orgganism: Ostrinia nubilalis GGACUGGGUCGCCCGCCAC UUUCGUUGCUUGAAUAAA Strain: bivoltinne Z-pheromone strain UUGACUUGAUAUGAUCGU Sex: male and female CCAAAAAAAAAAAAAAAA Orggan: midgut AAAAAAAAAAAAAA Develop. stage: 4th and 5th instar larvae Lab host: XL1 Blue Vector: pDNRLIB
9. 118 DỰ ĐOÁN CẤU TRÚC BẬC HAI RNA BẰNG SỰ KẾT HỢP THUẬT TOÁN DI TRUYỀN VÀ LOGIC MỜ Kết quả và so sánh Bảng 4. Kết quả và so sánh giữa việc áp dụng hai thuật toán GA Thuật toán di truyền Thuật toán di truyền kết hợp với logic mờ Năng Năng Cấu trúc Cấu trúc lượng lượng Best ((((((( Best ((((( ((( ))) )))).((( free (((((( ((( ((((((.(((( ))))))))) free ((((((((((( ))))))))))) Energy ).))) )))))) Energy (((((( ))).))) ))) : -25.8 ))))))) : -34.6 c) LSU 98 Bases Thông tin chuỗi Bảng 5. Thông tin chuỗi LSU 98 Bases Tên chuỗi Thông tin Chuỗi LSU IDENTIFIERS GACUAAAUACUCCUGGGUGACC GAUAGCGAAAUAGUACCGUGAG 98 dbEST Id: 40263335 GGAAAGGUGAAAAGAACCCCCA Bases EST name: MVE00001399 UCGGGGAGUGAAAAAAAAAAAA AAAAAAAAAA GenBank Acc: EC731497 GenBank gi: 110045614 Database: TBestDB LIBRARY Lib Name: LIBEST_019927 Mesostigma viride Regular library 2 Organism: Mesostigma viride Kết quả và so sánh Bảng 6. Kết quả và so sánh giữa việc áp dụng hai thuật toán GA Thuật toán di truyền Thuật toán di truyền kết hợp với logic mờ Năng lượng Cấu trúc Năng lượng Cấu trúc Best free Energy: (((((((.(((( ( Best free Energy: (((((((.(((( ) -16.2 ((( )))) )))).))) -17.5 ))) ((( ((( )))))) ))) )))) )))))
10. Đoàn Duy Bình, Phạm Minh Tuấn, Đặng Đức Long, Nguyễn Hữu Danh 119 VI. KẾT LUẬN Với những kết quả thực nghiệm trên đây cho thấy rằng thuật toán di truyền kết hợp với logic mờ cho ra những cấu trúc tốt hơn so với thuật toán di truyền thuần túy. Tuy nhiên vẫn chưa đạt đến mức độ tối ưu cho một cấu trúc bậc hai RNA như kỳ vọng. Khi ghép thuật toán di truyền với logic mờ cho phép áp dụng dự đoán những cấu trúc bậc hai RNA cho những kết quả tốt hơn. Trong mô hình nhiệt động học đơn giản thì thuật toán di truyền tính toán năng lượng tự do của cấu trúc được thực hiện tốt hơn khi áp dụng DPA với mô hình nhiệt động học phức tạp. Đặc biệt với việc sử dụng thuật toán di truyền ghép với logic mờ thì việc tìm được cấu trúc bậc hai tối ưu là tốt hơn. Chúng tôi sẽ xây dựng các hàm mờ và tập mờ khi ghép với thuật toán di truyền để áp dụng cho bài toán dự đoán cấu trúc bậc hai RNA đạt được cấu trúc tối ưu. VII. TÀI LIỆU THAM KHẢO [1] M. Zuker and D. Sankoff. Rna secondary structures and their prediction. Bulletin of Mathematical Biology, 46(4):591-621, 1984. [2] B. Felden. Rna structure: experimental analysis. Current Opinion in Microbiology, 10(3):286-291, 2007. [3] S. Cao, S. J. Chen. Physics-based de novo prediction of rna 3d structures. Journal of Molecular Biology, 115(14):4216-4226, 2011. [4] M. Parisien, F. Major. The mc-fold and mc-sym pipeline infers rna structure from sequence data. Nature, 452(7183):51-55, 2008. [5] D. M. Layton, R. Bundschuh. A statistical analysis of rna folding algorithms through thermodynamic parameter perturbation. Nucleic Acids Research, 33(2):519-524, 2005. [6] K. C. Wiese, A. A. Deschenes, A. G. Hendriks. Rnapredict_an evolutionary algorithm for rna secondary structure prediction. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 5(1):24-41, 2007. [7] M. Geis, M. Middendorf. A particle swarm optimizer for finding minimum free energy rna secondary structures. Swarm Intelligence Symposium, 2007. SIS 2007. IEEE, pages 1-8, 2007. [8] A. M. Mohsen, A. T. Khader, D. Ramachandram. Hsrnafold: A harmony search algorithm for rna secondary structure prediction based on minimum free energy. Innovations in Information Technology, 2008. IIT 2008, pages 11-15, 2008. [9] M. Zuker and P. Stiegler. Optimal Computer Folding of Large RNA Sequences Using Thermodynamics and Auxiliary Information. Nucleic Acids Research, 9:133-148, 1981. [10] M. Zuker. On Finding All Suboptimal Foldings of an RNA Molecule. Science, 244(4900):48-52, 1989. [11] Ingo Müller. A History of Thermodynamics - the Doctrine of Energy and Entropy. Springer, 2007. [12] Seref Inal Sakir Tasdemir, Abdullah Urkmez. Determination of body measurements on the holstein cows using digital image analysis and estimation of live weight with regression analysis. Computers and Electronics in Agriculture, 76(2):189-197, 2011. RNA SECONDARY STRUCTURE PREDICTION BY A COMBINATION OF GENETIC ALGORITHM WITH FUZZY LOGIC Doan Duy Binh, Pham Minh Tuan, Dang Duc Long, Nguyen Huu Danh ABSTRACT: In this pape we introduce a hybrid Algorithm Genetic with Fuzzy Logic. From this hybrid algorithm we apply the problem of predicting the second-ary structure of Ribonucleic Acid. Problem predicted secondary structure that we mentioned methods based on thermodynamics, to find secondary structure with minimum energy. With the results of the algorithms found by the hybrid algorithm we introduce, we hope to contribute to the molecular biology data warehouse for molecular biology research. It also introduces a new approach to genetic algorithms.