Xem mẫu
- 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.
nguon tai.lieu . vn
