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ờ

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:10

Thêm vào BST

Báo xấu

17
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài viết 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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

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ờ

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Ờ Đoàn Duy Bình1, Phạm Minh Tuấn2, Đặng Đức Long3, Nguyễn Hữu Danh2 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 3 Việ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
Đoàn Đ Duy Bình, Phạm Minh T Tuấn, Đặng Đứcc Long, Nguyễn n Hữu Danh 111 trruyền được lạại với logic mờ ờ. Kết quả thử ử nghiệm của chúng tôi cho o thấy rằng vớới thuật toán ddi 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 thhuật toán truyềền thống. Hình 1. M Mô hình mà chúng tôi sử dụng trong t nghiên cứứu này Bài báoo này được chhúng tôi trình bày những vấấn đề sau: giớ ới thiệu về bàii toán dự đoán án cấu trúc bậc c hai RNA được đ thể hiện trong phần II, phần III giớii thiệu về thuậật toán di truy yền, mục IV ggiới thiệu về loogic mờ và giới thiệu sự kết k hợp thuật toán t di truyềnn với logic mờ ờ. Phần V và VI là những kết quả của thhực nghiệm kkhi triển khai thuật toán, đánh đ giá và kếết luận. III. DỰ ĐOÁN N TRÚC BẬC C HAI RNA 2.1. 2 Cấu trúc bậc hai Các phân tử RNA đư m chuỗi của bốn loại ribonnucleotide hooặc là các base ược mô tả đặặc điểm bởi một e: Adenine (A), Cytosine (C), Guaninee (G) và Uraciil (U). Một ch nh các base củủa sợi RNA ttạo thành cấu trúc chính huỗi tuyến tín hoặc h chuỗi. Dư ưới đây mà một số khái niệmm làm sáng tỏ ỏ về chuỗi RNNA và cấu trúc bậc hai RNA A như sau: A có chiều ddài là n ribo a) Mộtt chuỗi RNA onucleotide làà một chuỗi x , , …, , trong g đó ∈ , C, G, U, ∀ ∈ 1, … , n. b) Tronng một cấu trúúc bậc hai củaa RNA, các cặặp base được hình h thành là m một trong ba ccặp như sau: C-G C (G-C), A-U Các cặp base {(A-U), (U-- A), (C-G), (G A (U-A) và G-U (U-G). C G-C)} gọi là ccác cặp Watsoon-Crick hoặc là các cặp base b chính tắcc. Cặp base {((G-U), (U-G)}} được gọi cặp base không bền vững (W Wobble). Sự ổnn định của cá ác cặp base được đ cho bởi mối > A-U ≥ G-U [9], [10]. m quan hệ saau đây: C-G> Hình 2. Các cặp base chíính tắc ứ i và base tại vị trí thứ j, sa c) Vớii , được biiểu diễn cho ccặp base hình thành bởi basse tại vị trí thứ ao cho một tập con của ∈ Y , ,1 gọi là cấu trúc t bậc hai RNA R nếu y thỏỏa mãn các điềều kiện sau:  , llà một cặp basse chính tắc;  Cho , ∈ , , ∈ , nếu thì ;  Nếu , ∈ , thì 3;  Mỗi base b chỉ ghép ccặp với một vàà chỉ một base khác trong cấ ấu trúc. d) Chúúng ta có thể ggọi hai cặp basse , và , , tương thíích nếu:  và (chúúng cùng một cặp base);  ( , trước , ) hoặc;  ^ ^′ ^′ ├ , ┤ bao ggồm , ); e) Cấuu trúc bậc hai RNA không ccó các nút thắtt (pseudoknot free, Hình 3.)) y tương ứngg với chuỗi RN NA x có độ d n là cấu trúúc bậc hai RN dài NA trong đó bbất kỳ hai cặp base , và , , chúngg đều đang lồồng nhau, tức là i
112 1 DỰ ĐOÁN N CẤU TRÚC BẬC HAI RNA A BẰNG SỰ KẾT K HỢP THUẬ ẬT TOÁN DI T TRUYỀN VÀ LOGIC L MỜ j, hoặc làà liên tiếp nhauu, tức là i j . Ở đây chúng ta giả định mà kkhông mất tínnh tổng quát rằng r i j, và i . Hình 3. Cấu trú úc RNA không có nút thắt 2.2. 2 Bài toán dự d đoán cấu ttrúc bậc hai R RNA Bài toánn dự đoán cấuu trúc bậc hai R RNA có thể được đ trình bày như sau:  Cho: một chuỗi RN NA có độ dài , với , , … , , trong đó ∈ , , , , ∀ ∈ 1, … , và v mô hình năng lượng tự do [11].  Mục tiêu: t phát triểnn một thuật toáán , trả ả về một hoặc nhiều n cấu trúcc bậc hai tươ ơng ứng với ch huỗi . Phươngg pháp phổ bbiến để có đưược cấu trúc bậc b hai là tìmm ra cấu trúc có mức nănng lượng tự do cực tiếu (minimum freee energy - MF FE) y của một chuỗi RN NA đã cho và theo mô hì hình năng lượnng . Cách tiếp cận này dựa d trên giả địịnh rằng các pphân tử RNA có khuynh hưướng gấp vào các cấu hình nnăng lượng tự ự do cực tiểu của chúng, được đ thể hiện qua công thứcc sau: ∈ arg g ∈ ∆ , , (1) Trong đó đ biểu thị m h có thể của chuỗi , ∆ llà hàm năng lư một tập tất cả các cấu bậc hai ượng cho phép đo độ ổn định đ của cấu trrúc và arg min n ∈ ∆ bbiể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 RN NA là một cấu u trúc lý thuyếết miêu tả choo các quy tắc vvà các biến tù ùy theo các chuỗi c RNA nàào mà hình thàành nên các ccấu trúc bậc haai tương ứng. Chúng tôi xeem xét một môô hình năng lư ượng tự do RNA R có ba thàành phần chínnh: M tập hợp ccác cấu trúc thhành phần , , … , , tro 1. Một ong đó là sốố cấu trúc thànnh phần của cấ ấu trúc bậc h RNA. Mộột cấu trúc thàành phần là mộ hai ột đoạn cấu trrúc bậc hai RN NA có nhiệt đđộng lực học được đ coi là q quan trọng chho việc tạo thàn ành cấu trúc bậậc hai RNA. 2. Một M tập hợp ccác tham số năăng lượng tự do d , ,…, với tham số năng lượngg tự do tươn ng ứng với c trúc thànhh phần . Thaam số đôi kh cấu hi được ký hiệệu là ∆ . 3. Một M hàm năngg lượng tự do xác định tính ổn định nhiệtt động lực họcc của một chuỗỗi được gấp thành một c trúc bậc hhai cụ thể phhù hợp với . cấu Hầu hếtt các mô hình cho dự đoán cấu trúc bậc hai h giả định rằằng hàm năng lượng tự do ccủa chuỗi và cấu trúc là tuyến tính trrong mô hình năng lượng , có dạng: ∆ , , ≔∑ , , ⊺ (2) Trong đó đ ≔ , ,…, biểuu thị véc tơ củ ủa các giá trị th ham số , , lần xuấtt hiện của cấu trúc thành phần p trong cấu c trúc bậc hhai của chuỗi và , : , ,…, , biểu thị véc tơơ của số lượng g đặc điểm , Các cấuu trúc thành phhần của cấu trrúc bậc hai RN NA bao gồm:
Đoàn Đ Duy Bình, Phạm Minh T Tuấn, Đặng Đứcc Long, Nguyễn n Hữu Danh 113 Hình 4. Cấu trúc t thành phần của RNA Năng lưượng trên cấuu trúc bậc hai của chuỗi chính là năn ng lượng đónng góp của cácc cấu trúc thành phần trrong cấu trúc bậc hai là như ư sau: o Vòng kẹp tóóc (Hairpin Looop): , ; o Xếp chồng ((Stack): , , , ; o Vòng bên trrong (Internal loop): , , ’, ’ ; o Vòng lồi ra (Bulge): , ; o Vòng nhiều nhánh (MultiiLoop): , , , , , ; Năng lư ượng eM đượcc tính như sauu: ’ (3) trrong đó: , , là các trọng số, với: năng lượngg của cặp basee đóng vòng; số lượng xoắn (helices); ’ số lượng baase không ghéép cặp trong vvòng; , năng lượnng tưng ứng với v và ’. III. THUẬT T TOÁ ÁN DI TRUYỀ ỀN TRONG BÀI TOÁN DỰ D ĐOÁN C CẤU TRÚC B BẬC HAI RNA 3.1. 3 Giới thiệu u Thuật toán t di truyền (GA) là kỹ thhuật tìm kiếm ngẫu nhiên to oàn cục với viiệc giả lập cácc quy luật tiến n hóa và di trruyền học để cố gắng tìm rra giải pháp tốối ưu cho bài toán tối ưu hó óa phức tạp. G GA đạt được vvề mặt lý thuy yết và thực nghiệm n đã đượợc chứng minhh nhằm cung cấp cho việc tìm kiếm mạn nh mẽ trong khhông gian phứ ức tạp và chún ng được áp dụng d rộng rãi trong t kỹ thuậtt, kinh doanh vvà khoa học. Thuật toán di truyền được mô tả nhhư sau: Bước 1: Khởi tạo qu uần thể; Bước 2: Đánh giá, nếu n đủ tốt thì kết k 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ơ đồ thhuật toán: Hình 5. Thuật T toán di trruyền
114 1 DỰ ĐOÁN N CẤU TRÚC BẬC HAI RNA A BẰNG SỰ KẾT K HỢP THUẬ ẬT TOÁN DI T TRUYỀN VÀ LOGIC L MỜ 3.2. 3 Các bướcc xây dựng th huật toán di trruyền cho bài toán 1. 1 Bước 1: Cách đơn giản nhất áp dụng thuậtt 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 q thể ta chọọn ngẫu nhiênn các ∈ . S Sau đó tạo cấuu trúc bằng cáách sử dụng cáác cặp ngoặc ““(“ , “)” và dấ ấu “.”, cách tạo như sau: ứnng với cặp “(““ và “)” là liênn kết của các cặp c base chính h tắc (II.A), dấấu chấm biểu thị các base không k được ghép g cặp. Ví dụ: . . . . 2. 2 Bước 2: Đánh giá g các nghiệm m dựa vào năăng lượng đã được đ định ngh hĩa (công thứcc 2); 3. 3 Bước 3: Lựa chọọn các nghiệnn có mực nănng lượng thấp p với tỷ lệ là 70 7 %, còn các nghiệm có mứ ức năng lượng g cao thì bị loại bỏ, sau đóó sẽ được bổ suung các nghiệệm con sau khi lai ghép ở bư ước 4. 4. 4 Bước 4: Quá trìnnh lại ghéo đơơn giản bằng cách sử dụng g lai ghép đồn ng nhất hoặc l ai ghép một đđiểm. Tuy nhiiên việc lại ghép g này gây ra r tình trạng pphá vỡ cấu trúc đã được định nghĩa ở trên n. Ví dụ có thểể sinh ra các nnghiệm con có ó ngoặc mở “(“ “ nhưng khôông có ngoặc đđóng “)” hoặcc ngược lại ho oặc chỉ có các dấu chấm “.””. Vấn đề này nhóm tác giả khắc phục bằng b cách áp dụng d logic mờ ờ, sẽ trình bày ở phần tiếp th heo. 5. 5 Bước 5: Đột biếến, tương tự nhhư lai ghép nóó cũng sinh raa những cấu trú úc không phùù hợp như đã đđịnh nghĩa. Trrong khuôn khổ k bài báo nàày nhóm tác ggiả sẽ chưa trìình bày phươn ng pháp áp dụ ụng logic mờ.. Chúng tôi sẽẽ trình bày tro ong các bài báo b tiếp theo. IV. LOGIC MỜ Ờ 4.1. 4 Giới thiệu u Mô hìnnh hệ thống Fuuzzy Logic (FL) là mô hình h dựa trên tri thức t với các qquy tắc ngôn nngữ. Tập mờ được đ mô tả cho c tất cả các biến đầu vàoo và đầu ra vàà tập luật. Log gic mờ đảm bảảo các phươnng tiện để xử llý kiến thức này n và tính toán các giá trrị đầu ra cho ccác dữ liệu đầầu vào nhất địn nh. Vấn đề ch hính của cách tiếp cận này llà tìm ra một bộ quy tắc ngôn n ngữ phù hợp để xác đđịnh hệ thốngg được mô phỏ ỏng [12]. Hệ thống mờ đượợc biểu diễn theo các quy tắc if-then hoặc h các câu lệnh l có điều kkiện mờ như ttrong biểu thứức của dạng IF F A THEN B,, trong đó A vvà B là nhãn của c các tập mờ. m Tập hợp các c quy tắc nêên được hoànn thành và cun ng cấp một câu u trả lời cho mmọi giá trị đầầu vào. Một số ố đặc điểm quan q trong củaa FL là:  Kết luận rõ ràng có thể được rrút ra từ hệ thố ống phức tạp tạo ra mơ hồ, không rõ rànng, hoặc thông g tin không chínnh xác,  Lý luận l chính xácc được xem nhhư là một trườờng hợp giới hạn h của lý luậnn gần đúng,  Bất kỳ hệ thống llogic nào cũngg có thể được mờ. Một hệ thống suy luậận mờ (FIS), nnhư được thấy y trong sử dụn ng các hàm thàành viên để “llàm mờ” dữ liệu đầu vào và v sau đó áp dụụng một tập hhợp các quy tắắc cho dữ liệu mờ. Hình 6. Sơ đồ cơ bản của logic l mờ Trong nghiên n cứu nàày, nhóm tác ggiả tập trung ứng ứ dụng logic mờ để giải qquyết bài toánn lai ghép như ư đã trình ở trrên. Trong việệc lại ghéo mộột điểm có thểể dẫn đến kết qua không nh hư kỳ vọng vì có hiện tượngg phá vỡ cấu trúc, vì vậy
Đoàn Đ Duy Bình, Phạm Minh T Tuấn, Đặng Đứcc Long, Nguyễn n Hữu Danh 115 việc v trao đổi cấu c trúc có thểể thực hiện bằnng điểm mờ. CóC nghĩa là mặc m dù hoán đỗỗi tại một điểm m nhưng nhữn ng vị trí xa điểm đ lại ghép thì t xác suất táái hiện như lại ghép một điểm một điểm th hông thường. Cách thhể hiện lai ghéép một điểm nnhư sau: Trước T khi lai ghép g Sau khi lai gh hép Các conn được sinh raa trong quá trìnnh lai ghép đư ược thể hiện như sau: 1 , θ((i) < 2 1 ẹ , 2 1 , θ((i) ≥ 2 1 ẹ , 2 Trong đó: đ 1, 1, 1 (4) 0, 1, 1 4 Lai ghép thuật toán dii truyền và loogic mờ 4.2. Lợi ích chính của thuuật toán di truyyền là nó có th hể được sử dụụng để tìm cácc giá trị được ttối ưu hóa từ không k gian tìm kiếm lớn cũng c như làm cho hệ thống có thể học hỏ ỏi. Đồng thời, hạn chế chínhh của thuật toáán di truyền làà nó không có c khả năng lư ưu trữ kiến thhức miền nhưnng GA có thểể được sử dụn ng để tìm giá ttrị tối ưu cho các tham số hàm thành viên, v đặc biệt khi chọn lọc tthủ công các ggiá trị của chúúng trở nên kh hó khăn hoặc mất quá nhiềều thời gian để ể đạt được. Để Đ xử lý thôngg tin được nêuu không chính xác, cách tiếp p cận ra quyết định mờ đã đđược sử dụng. Thực hiiện điểm mờ ttrong lai ghép được thể hiện n như sau: Lai gh hép có điểm mờ m Việc tạo ra y và y n nhiều lần vàà chọn ra các y thực hiiện ngẫu nhiên có mức nnăng lượng thấ ấp nhất. Sờ S đồ thuật toáán di truyền cóó kết hợp với logic mờ.
116 1 DỰ ĐOÁN N CẤU TRÚC BẬC HAI RNA A BẰNG SỰ KẾT K HỢP THUẬ ẬT TOÁN DI T TRUYỀN VÀ LOGIC L MỜ Hình h 6. Thuật toán di truyền kết hợ ợp với logic mờờ V. KẾT QUẢ VÀ ĐÁN NH GIÁ 5.1. 5 Kết quả 1. 1 Các thông số cơ ban củaa thuật toán: static intt AMOUNT\_ _OF\_INDIVIIDUAL = 1000000; stattic List popullation = new; ArrayLiist(); static Double D Pc = 0.7; 0 static Double D Pm = 0.3; 0 sttatic float besstFreeEnergiees = 99999; stattic int position nOfBestFreeE Energies = 0;; 2. 2 Các chuỗi đầu đ vào, kết qquả và so sánhh
Đoàn Đ Duy Bình, Phạm Minh T Tuấn, Đặng Đứcc Long, Nguyễn n Hữu Danh 117 a) a E.Coli 221 Bases  Thôngg tin chuỗi B Bảng 1. Thông g tin chuỗi E.Co oli 221 Bases Tên chuỗi Thông tin Chuỗi E.C Coli 221 ENTIFIERS IDE ACAUG GGGGAUAAGG GGCAGGCGG G B Bases UGAAU UGCCUUGGCU UCUCGGAGG G dbEEST Id: 788664696 CGAAG GAAGGACGUG GAUAAGCUG G ES ST name: CFSW WEC38 AAGCCCGGCG CGAUA GUAGGCGCA GCCGUUAAUA AAUAG ACCGGGGUU U GeenBank Acc: JZ Z515411 UCCGAA AUGGGGCAA ACCCGCCGG GeenBank gi: 5577806034 GAGUA AAUUCCGGCA AUCUCUUGA A LIB BRARY AAGAG GGGAGGCGAA ACGUGGGGA A ACUGA AAACAUCUCA AGUACCUGC Libb Name: LIB BEST_027994 Immune respon nses AGGAA AAAAAAAAAA AAAAAAAAA A of Coptotermees formosanus. Shiraki workerrs A against Escherichia coli Orrganism: Cooptotermes form mosanus Orrgan: wholle body  Kết quuả và so sánh Bảng 2. Kếết quả và so sán nh giữa việc áp dụng d hai thuật ttoán GA Thuật toán di truyềền Thuật to oán di truyền 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 Beest .((((..............................(((((.......... Best free ..................................(((((((((.(((.............. freee .........................(((((((.................... Energy: - ...))).................................... ....((((((((.....) Eneerg ..(((..)))..................)))))))).............. 31.9 y: - .........)))))).......))))........................ ))))..))).)))))))))................... ..............(((((. 23.7 .......................... .( ((((......))))).))))))........................ b) b Bmori 219 Bases  Thôngg tin chuỗi B Bảng 3. Thông g tin chuỗi Bmori 219 Bases Tên n chuỗi Thông tin t Ch huỗi Bm mori 219 ENTIFIERS IDE A ACCACGGCA AUGUGCAAC B Bases dbbEST Id: 455323636 G GGUGACUCC CGGCAGCGC ES ST name: E EST0213 U UCUAGUCCG GCCUGGACC G GCGGCACCC CAGAUCGGA GenBank Acc: E EL928597 A AUCGUGUCG GUGGGGCUU U GenBank gi: 1333905746 C CCCCUGCGC CCCGCGGCGC C LIBRARY U UCCCGAUAU UGUUCGUCC Lib Name: LIB BEST_020979 ARS-CICGRU A ONmgEST O G GAGUCAGCG GCCUUCCAA Orgganism: Ostrrinia nubilalis G GACUGGGUC CGCCCGCCACC U UUCGUUGCU UUGAAUAAA A Straain: bivoltinne Z-pheromon ne strain U UGACUUGAU UAUGAUCGU U Sex: male and ffemale C CAAAAAAAA AAAAAAAAAA Orggan: midguut A AAAAAAAAA AAAAA Devvelop. stage: 4thh and 5th instar larvae Lab host: XL1 Blue Veector: pDNNRLIB
118 1 DỰ ĐOÁN N CẤU TRÚC BẬC HAI RNA A BẰNG SỰ KẾT K HỢP THUẬ ẬT TOÁN DI T TRUYỀN VÀ LOGIC L MỜ  Kết quuả và so sánh Bảng 4. Kếết quả và so sán nh giữa việc áp dụng d hai thuật ttoán GA Thuậật toán di truyyề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 Beest ...........................((((((((...................... Best ................(((((......(((..............)))...)))).(((... freee ..((((((....(((....((((((.(((((.........))))))))) free ............(((((((((((............))))))))))).............. Eneergy ).)))..................................)))))).......... Energy .........((((((..........))).)))..))).. ..................... : -25.8 ...))))))))............................................. : ............................................. ........... -34.6 c) c LSU 98 Baases  Thôngg tin chuỗi Bảng 5. Thôn ng tin chuỗi LSU U 98 Bases Tên n chuỗi Thông tin Chuỗii L LSU IDEN NTIFIERS AAAUACUCCU GACUA UGGGUGACC C GAUAG GCGAAAUAG GUACCGUGAG G 98 dbES ST Id: 402663335 GGAAA AGGUGAAAA AGAACCCCCA A B Bases EST T name: MVE000001399 UCGGG GGAGUGAAA AAAAAAAAAA A AAAAA AAAAAA GenB Bank Acc: EC C731497 GenB Bank gi: 1100045614 Dataabase: TBesstDB LIBR RARY Libb Name: LIIBEST_019927 Mesostigma viiride Regular library 2 R Orgganism: Mesostigma viridee  Kết quuả và so sánh Bảng 6. Kếết quả và so sán nh giữa việc áp dụng d hai thuật ttoán GA Thuậtt toán di truyyền Thuật toán di truyềền kết hợp vớ ới logic mờ N Năng lượng Cấấu trúc Năng g lượng Cấu u trúc Bestt free Energy: .......(((((((.((((................(( Best freee Energy: .......(((((((.(((((................) -16.2 (((..........)))))...........)))).)))) -17.5 )))....(((...((((.......))))))....))) ))))...................... ))))).......................
Đ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.