ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ

NGUYỄN THU TRANG

BÀI TOÁN TÌM KIẾM MOTIF VÀ
PHƢƠNG PHÁP TỐI ƢU ĐÀN KIẾN

LUẬN VĂN THẠC SĨ NGÀNH CÔNG NGHỆ THÔNG TIN

Hà Nội, năm 2016


ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ

NGUYỄN THU TRANG

BÀI TOÁN TÌM KIẾM MOTIF VÀ
PHƢƠNG PHÁP TỐI ƢU ĐÀN KIẾN

Ngành
Chuyên ngành
Mã số

: Công nghệ thông tin
: Hệ thống thông tin
: 60480104

LUẬN VĂN THẠC SĨ NGÀNH CÔNG NGHỆ THÔNG TIN




2

LỜI CAM ĐOAN
Tôi xin cam đoan rằng đây là công trình nghiên cứu của cá nhân tôi dƣới
sự hƣớng dẫn giúp đỡ của PGS.TS. Hoàng Xuân Huấn. Các kết quả đƣợc viết
chung với các tác giả khác đều đƣợc sự đồng ý của tác giả trƣớc khi đƣa vào
luận văn. Trong toàn bộ nội dung nghiên cứu của luận văn, các vấn đề đƣợc
trình bày đều là những tìm hiểu và nghiên cứu của chính cá nhân tôi hoặc là
đƣợc trích dẫn từ các nguồn tài liệu có ghi tham khảo rõ ràng, hợp pháp.
Trong luận văn, tôi có tham khảo đến một số tài liệu của một số tác giả
đƣợc liệt kê tại mục tài liệu tham khảo
Hà nội, tháng 10 năm 2016

Nguyễn Thu Trang


3

MỤC LỤC
LỜI CẢM ƠN .................................................................................................................. 1
LỜI CAM ĐOAN ............................................................................................................ 2
DANH MỤC KÝ HIỆU VÀ TỪ VIẾT TẮT .................................................................. 5
DANH MỤC CÁC BẢNG .............................................................................................. 6
DANH SÁCH CÁC HÌNH VẼ ....................................................................................... 7
MỞ ĐẦU ......................................................................................................................... 8
Chƣơng 1: TIN SINH HỌC VÀ BÀI TOÁN TÌM KIẾM (l,d) MOTIF ....................... 10
1.1. Tin sinh học ........................................................................................................10
1.1.1 Giới thiệu về tin sinh học .............................................................................10

2.3.4 Quy tắc cập nhật vết mùi ..............................................................................33
2.3.4.1 Thuật toán AS ..........................................................................................33
2.3.4.2 Thuật toán ACS .......................................................................................34
2.3.4.3 Thuật toán Max-Min ...............................................................................34
2.3.4.4 Thuật toán Max- Min trơn .......................................................................35
2.3.5 ACO kết hợp với tìm kiếm địa phƣơng ........................................................35
2.3.6 Số lƣợng kiến ................................................................................................35
2.3.7 Tham số bay hơi ...........................................................................................36
Chƣơng 3: THUẬT TOÁN ĐỀ XUẤT ......................................................................... 37
3.1 Thuật toán tối ƣu đàn kiến ...................................................................................37
3.2. Xây dựng đồ thị cấu trúc ....................................................................................38
3.3. Thông tin heuristic ..............................................................................................38
3.4. Xây dựng lời giải tuần tự ....................................................................................38
3.5. Quy tắc cập nhật mùi (pheromone update rule) .................................................39
3.6. Tìm kiếm địa phƣơng (local search) ...................................................................40
Chƣơng 4: KẾT QUẢ THỰC NGHIỆM, SO SÁNH VÀ ĐÁNH GIÁ KẾT QUẢ ..... 42
4.1 Bộ dữ liệu chuẩn ..................................................................................................42
4.2 Tiến hành chạy thực nghiệm trên hệ điều hành ubuntu.......................................42
4. 3 Kết quả chạy thực nghiệm và đánh giá ..............................................................43
4.3.1 Kết quả thực nghiệm ....................................................................................43
4.3.2 So sánh và đánh giá ......................................................................................45
4.3.2.1 So sánh với MEME .................................................................................45
4.3.2.2 Kết quả so sánh F-ACOMotif với Pairmotif+ và MEME trên tập dữ liệu
thực ......................................................................................................................47
KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN .................................................................... 49
TÀI LIỆU THAM KHẢO ............................................................................................. 50


5


Ant Colony System
(Hệ kiến ACS)
Max-Min Ant System
(Hệ kiến MMAS)
Smooth-Max Min Ant System
(Hệ kiến MMAS trơn)
Travelling Salesman Problem

6

TSP

7

TƢTH

Tối ưu tổ hợp

8

PMS

Planted Motif Search

(Bài toán ngƣời chào hàng)


6

DANH MỤC CÁC BẢNG

Hình 3.2: Cách xây dựng đường đi của kiến ...................................................... 39
Hình 4.1: Đồ thị so sánh độ chính xác của F-ACOMotif so với PairMotif+ và
MEME ................................................................................................................. 48


8

MỞ ĐẦU
Tin sinh học có ứng dụng cao trong cuộc sống, đặc biệt trong lĩnh vực y –
dƣợc. Về cơ bản, tin sinh học tập trung vào nghiên cứu và áp dụng các phƣơng
pháp cũng nhƣ các kĩ thuật trong tin học để giải quyết các bài toán trong sinh
học phân tử.Tìm kiếm motif trong các chuỗi gene là một trong những bài toán
quan trọng nhất của tin sinh học và thuộc loại NP-khó.
Các thành phần điều hòa gene (gene regulatory elements) đƣợc gọi là các
DNA motif (về sau gọi là motif cho gọn), chúng chứa nhiều thông tin sinh học
quan trọng. Vì vậy việc nhận dạng DNA motif đang là một trong những bài toán
quan trọng nhất trong tin sinh học và thuộc loại NP-khó. Chủ yếu, có 2 cách tiếp
cận để tìm kiếm motif: các phƣơng pháp thực nghiệm và các phƣơng pháp tính
toán. Vì chi phí cao và tốn thời gian nên các phƣơng pháp thực nghiệm ít hiệu
quả.Phƣơng pháp tính toán đang đƣợc dùng rộng rãi cho dự đoán motif.
Ngƣời ta đƣa ra nhiều phát biểu cho bài toán tìm kiếm motif, và có nhiều
thuật toán nghiên cứu và công bố giải quyết bài toán tìm kiếm motif. Trong luận
văn này, tôi trình bày bài toán (ℓ,d) motif. Có nhiều thuật toán đƣa ra để giải
quyết bài toán (ℓ,d) motif, các thuật toán này có thể chia thành 2 loại đó là thuật
toán chính xác và thuật toán xấp xỉ. Các thuật toán chính xác luôn luôn tìm ra
những motif trong những chuỗi DNA đầu vào nhƣng chỉ hiệu quả với các dữ
liệu có kích thƣớc nhỏ và thực hiện mất nhiều thời gian. Các thuật toán xấp xỉ có
thể không tìm ra đƣợc tất cả các motif nhƣng nó chạy hiệu quả với các dữ liệu
lớn.
Luận văn đề xuất giải quyết bài toán (ℓ,d) motif theo thuật toán xấp xỉ,

đồng nghĩa với “Bioinformatics” [1]. Vậy Tin sinh học là gì? Fredj Tekaia
Thuộc viện Pasteur đã đƣa ra một định nghĩa về tin sinh học nhƣ sau:
“Tin sinh học là sử dụng toán học, thống kê và khoa học máy tính để giải
quyết các vấn đề về sinh học với DNA, chuỗi axit amin và các thông tin có liên
quan”.
1.1.2 Khái niệm trong sinh học
Mọi cơ thể sống đều đƣợc cấu thành từ một lƣợng rất lớn các tế bào. Mỗi
tế bào đều đƣợc cấu tạo gồm hạt nhân, ribôxom và nội bào. Hạt nhân của tế bào
chứa các nhiễm sắc thể đặc trƣng cho mỗi tế bào đó. Nhiễm sắc thể lại đƣợc tạo
thành bởi các axit nucleic và protein. Axit nucleic là những đại phân tử có cấu
trúc đa phân, đơn phân của nó là các nucleotide. Axit nucleic đƣợc chia làm 2
loại là DNA (deoxyribonucleic acid) và RNA. Một thành phần rất quan trọng
khác của tế bào là protein, đƣợc tạo ra từ các axit amin, là các thành phần thiết
yếu của mọi cơ quan và hoạt động hóa học liên quan đến toàn bộ hoạt động của
tế bào, chúng đƣợc biểu hiện thành những đặc điểm về cấu tạo và chức năng của
tế bào, hay chính là những tính trạng của sinh vật. Giữa protein và DNA có quan
hệ chặt chẽ với nhau, cụ thể là mỗi loại protein đều đƣợc xác định bởi một đoạn
trên dãy DNA gọi là gen.
1.1.2.1 DNA

Hình 1.1: DNA phân tử của sự sống


11

Vào năm 1944, Oswald Avery phát hiện ra DNA là một loại nguyên liệu
thô chứa gen. Bắt nguồn từ phát hiện này, một vài nhóm nghiên cứu đã tập trung
nghiên cứu về DNA và các thành phần hóa học cấu thành. DNA là một phân tử
đƣợc cấu tạo bởi đƣờng, photphat và bốn nitrogenous bases: adenine, cytosine,
guanine và thiamine, đƣợc lần lƣợt viết tắt là A, C, G, và T. Sau này, các nhà

snRNA: có chức năng hỗ trợ việc ghép mã mRNA.
gRNA: sử dụng để điều khiển việc thay đổi mRNA.
RNA có thể liên kết với một dải đơn của một phân tử DNA, bằng cách
thay T bằng U, và các phân tử kiểu này có vai trò quan trọng trong các quá trình
sống và công nghệ sinh học [1].

1.1.2.3 Protein

Hình 1.3:Cấu trúc Protein
Protein là một đại phân tử sinh học đƣợc hình thành từ 1 hay nhiều chuỗi
polypeptide sắp xếp theo một thứ tự đặc biệt, thứ tự này đƣợc xác định bởi dãy
cơ sở (peptide là một chuỗi nối tiếp nhiều axit amin với số lƣợng ít hơn 30, với
số lƣợng axit amin lớn hơn chuỗi đƣợc gọi là polypeptide) đƣợc hình thành từ
20 loại axit amin khác nhau lần lƣợt đƣợc biểu thị bằng 20 kí tự khác nhau trong
bảng chữ cái. Từ “ protein” dùng để chỉ một cấu trúc phức tạp trong không gian
chứ không đơn thuần chỉ là một trình tự axit amin. Các nucleotide trong gene mã


13

hóa cho protein. Các protein cần thiết cho cấu trúc, chức năng và điều chỉnh tế
bào, mô và tổ chức, mỗi protein có một vai trò đặc biệt.
Cấu trúc protein bao gồm 4 mức độ tổ chức: Cấu trúc bậc 1 là trình tự sắp
xếp các axit amin trong chuỗi polypeptid, cấu trúc bậc 2 phát sinh từ sự uốn các
thành phần của chuỗi polypeptid thành những cấu trúc đều đặn trong không gian
( dạng xoắn 𝛼 (alpha helix) hay lớp mỏng 𝛽 (Beta sheets)). Cấu trúc bậc 3 quy
định sự kết hợp các chuỗi xoắn hay lớp mỏng đó thành hình dạng ba chiều trong
không gian. Cấu trúc bậc 4 là sự tổ chức nhiều chuỗi polypeptid thành một phân
tử protein.
1.1.2.4 Quá trình tổng hợp protein

tác giữa DNA và protein, điều hòa gen cũng nhƣ sự phát triển và tƣơng tác trong
một tế bào.

Hình 1.5: Quá trình tổng hợp Protein
Motif là những đoạn trình tự có kích thƣớc ngắn, có thể là nucleotide hoặc
amino axit và mang ý nghĩa sinh học. Một vài đặc điểm của motif [15]:
 Motif là những mẫu có kích thƣớc từ 10-25 base và lặp lại nhiều lần qua
các chuỗi khác nhau.
 Motif là những đoạn trình tự đại diện cho vùng điều hòa của gen.
 Motif có kích thƣớc nhỏ, cố định, lặp lại rất nhiều lần và thƣờng xuyên.


15

Hình 1.6: Ví dụ về Motif
Khó khăn trong việc tìm kiếm motif [15]:
 Các Motif không bao giờ chính xác nhƣ chuỗi đƣợc bảo tồn. Luôn có
những sự thay đổi ở một vài base.
 Kích thƣớc của Motif quá ngắn so với kích thƣớc của chuỗi DNA đang
đƣợc xemxét.
 Vùng điều hòa bao gồm Motif có thể ở trị trí rất xa so với vùng mã hóa
của gen khiến cho việc tìm kiếm trở nên khó khăn hơn rất nhiều.
Vùng điều hòa có thể nằm trên mảnh DNA đối diện với vùng mã hóa trong
quá trình phiên mã
1.1.3.2 Ý nghĩa của Motif
Ngoài những vùng mã hóa quan trọng, trong hệ gen còn có những vùng
chứa các tín hiệu nhƣ tín hiệu khởi đầu phiên mã, tín hiệu cắt để xác định cùng
intron exon …
Phần tử điều hòa (Regulatory element) đƣợc chia làm 2 loại: promoter và
enhancer. Promoter là vùng gần với exon đầu tiên và là vị trí gắn (binding site)

1.1.3.3.3 Biểu tƣợng
Biểu tƣợng là cách dùng hình ảnh biểu diễn cho Motif.

Hình 1.9: Biểu diễn Motif dạng sequence


18

1.2. Bài toán tối ƣu tổ hợp và bài toán tìm kiếm (ℓ,d) motif
1.2.1 Bài toán tối ƣu tổ hợp
1.2.1.1Giới thiệu bài toán tối ƣu tổ hợp
Mỗi bài toán tối ƣu tổ hợp ứng với bộ ba(𝑆, 𝑓, Ω), trong đó 𝑆 là tập hữu
hạn các trạng thái (lời giải tiềm năng hay phƣơng án), 𝑓 là hàm mục tiêu xác
định trên 𝑆 và Ω là tập các ràng buộc. Mỗi phƣơng án 𝑠 ∈ 𝑆 thỏa mãn các ràng
buộc Ω gọi là phƣơng án chấp nhận đƣợc. Mục tiêu của chúng là tìm ra phƣơng
án 𝑠 ∗ tối ƣu hóa toàn cục đối với hàm mục tiêu 𝑓, nói cách khác chính là tìm
phƣơng án 𝑠 ∗ sao cho 𝑓 𝑠 ∗ ≤ 𝑓 𝑠 với mọi 𝑠 ∈ 𝑆. Đối với bài toán này ta có 3
cách giải quyết đó là: vét cạn, kỹ thuật ăn tham hoặc phƣơng pháp tối ƣu trong
lĩnh vực NP-khó.
Các thuộc tính của tập 𝑆, 𝐶 và Ω nhƣ sau:
1) Ký hiệu 𝑋 là tập các vectơ trên 𝐶 có độ dài không quá 𝑕: 𝑋 = {
𝑢𝑖 𝐶𝑖𝑘𝑕}.Khi đó, mỗi phƣơng án 𝑠 trong 𝑆 đƣợc xác
định nhờ ít nhất mộtvectơ trong 𝑋.
2) Tồn tại tập con 𝑋 ∗ của 𝑋 và ánh xạ  từ 𝑋 ∗ lên 𝑆 sao cho −1 (𝑠) không
rỗng với mọi 𝑠𝑆,trong đó tập 𝑋 ∗ có thể xây dựng đƣợc từ tập con 𝐶0 nào
đó của 𝐶 nhờ thủ tục mở rộng tuần tự dƣới đây.
3) Từ 𝐶0 ta mở rộng tuần tự thành 𝑋 ∗ nhƣ sau:
i) Ta xem 𝑥0 = < 𝑢0 >là mở rộng đƣợc với mọi 𝑢0  𝐶0 .
ii) Giả sử𝑥𝑘 =< 𝑢0 , … , 𝑢𝑘 > là mở rộng đƣợc và chƣa thuộc 𝑋 ∗ .Từ tập ràng
buộc Ω, xác định tập con 𝐽(𝑥𝑘 ) của 𝐶, sao cho với mọi 𝑢𝑘+1  𝐽 𝑥𝑘

𝑛−1
𝑖=1 𝑑(𝜋

𝑖 , 𝜋(𝑖 + 1)) + 𝑑(𝜋 𝑛 , 𝜋 1)

(1.1)

1.2.1.3 Các cách tiếp cận giải quyết bài toán tối ƣu tổ hợp
Nhƣ phần trên ta đã thấy các bài toán TƢTH có thể đƣa về bài toán tìm
kiếm trên đồ thị. Với những bài toán cỡ nhỏ hoặc những bài toán đặc biệt thì ta
hoàn toàn có thể tìm lời giải tối ƣu nhờ tìm kiếm vét cạn cũng nhƣ xây dựng
những lời giải đặc thù riêng. Tuy nhiên hầu hết các bài toán trong số đó là bài
toán NP-khó, nên với các bài toán cỡ lớn ngƣời ta phải tìm lời giải gần đúng.
Các thuật toán gần đúng đối với các bài toán TƢTH khó thƣờng dựa trên 2 kỹ
thuật cơ bản: heuristic cấu trúc (construction heuristic) và tìm kiếm địa phƣơng
(local search).
1.2.1.3.1 Heuristic cấu trúc
Khi không thể tìm lời giải tối ƣu của bài toán với thời gian đa thức, chúng
ta hƣớng đến việc tìm lời giải gần đúng. Kỹ thuật hay dùng trong việc tìm lời
giải gần đúng là heuristic cấu trúc, lời giải của bài toán đƣợc xây dựng thông
qua việc mở rộng tuần tự. Từ thành phố khởi tạo trong tập 𝐶0 , từng bƣớc mở
rộng không quay lui, thêm vào các thành phần mới theo phƣơng thức ngẫu nhiên
hay tất định dựa trên những quy tắc heuristic. Các quy tắc heuristic này khác
nhau tùy vào thuật toán cụ thể đƣợc xây dựng dựa trên toán học kết hợp với kinh


20

nghiệm. Chúng ta có thể khái quát hóa để mô phỏng dƣới dạng thuật toán nhƣ
sau:


Ví dụ. Lân cận 2-thay đổi của một lời giải 𝑠 trong bài toán TSP bao gồm
tất cả các lời giải 𝑠′ có thể nhận đƣợc từ 𝑠 bằng cách đổi hai cạnh. Hình 1.11 chỉ
ra một ví dụ một lời giải nhận đƣợc bằng cách thay hai cạnh (1,3), (2,6) bằng hai
cạnh (2,3), (1,6).
Việc cải tiến trong các bƣớc lặp thƣờng chọn theo phƣơng pháp leo đồi
dựa theo hai chiến lƣợc: Chiến lƣợc tốt nhất và chiến lƣợc tốt hơn. Với chiến
lƣợc tốt nhất, ngƣời ta thực hiện chọn lời giải tốt nhất trong lân cận để làm lời
giải cải tiến.Tuy nhiên, khi bài toán cỡ lớn có thể không tìm đƣợc lời giải tốt
nhất do bị hạn chế về thời gian. Còn với chiến lƣợc tốt hơn, ta chọn phƣơng án
đầu tiên trong lân cận, cải thiện đƣợc hàm mục tiêu. Nhƣợc điểm của tìm kiếm
địa phƣơng là thƣờng chỉ cho cực trị địa phƣơng.

Hình 1.11: Lời giải nhận đƣợc thông qua tìm kiếm địa phƣơng
Các kỹ thuật trên thƣờng đƣợc kết hợp, tạo thành các hệ lai trong các
phƣơng pháp mô phỏng tự nhiên dựa trên quần thể, chẳng hạn nhƣ thuật toán di
truyền (GA) hoặc tối ƣu đàn kiến (ACO).
1.2.1.3.3 Phƣơng pháp metaheuristic
Phƣơng pháp metaheuristic là một phƣơng pháp heuristic tổng quát đƣợc
thiết kế, định hƣớng cho các thuật toán cụ thể (bao gồm cả heuristic cấu trúc và
tìm kiếm địa phƣơng). Nhƣ vậy, một metaheuristic là một lƣợc đồ thuật toán
tổng quát ứng dụng cho các bài toán tối ƣu khác nhau, với một chút sửa đổi cho
phù hợp với từng bài toán.


22

1.2.1.3.4 Phƣơng pháp Memetic
Memetic là một mô hình theo phƣơng pháp metaheuristic. Trong các thuật
toán đƣợc thiết kế theo memetic, ngƣời ta tạo ra nhiều thế hệ quần thể lời giải

đƣợc xác định nhƣ sau:
a) dH(x,y) = số vị trí khác nhau của x và y nếu ℓ=n
b) dH(x,y) = min{dH( x,m)/ m là xâu con độ dài ℓ của y} nếu ℓ< n

Hình 1.13: Ví dụ khoảng cách hamming
Xác định đƣợc các motif và các instance tƣơng ứng của nó có ý nghĩa rất
quan trọng, từ đó các nhà nghiên cứu sinh học có thể phát hiện ra các tƣơng tác
giữa DNA và protein, điều hòa gen cũng nhƣ sự phát triển và tƣơng tác trong
một tế bào. Các bài toán tìm kiếm motif đã thu hút đƣợc nhiều nhà nghiên cứu.
Có nhiều phát biểu cho bài toán tìm kiếm motif. Điển hình có thể kể đến 3 bài
toán tìm kiếm motif nhƣ sau [14]: Simple Motif Search, (ℓ,d) Motif Search
(Planted Motif Search) và Edited Motif Search
Trong luận văn này, chúng tôi sẽ tập trung nghiên cứu bài toán (ℓ,d) Motif
Search (LDMS) hay chính là bài toán Planted Motif Search (PMS) từ nay sẽ gọi
là bài toán PMS.
Bài toán PMS đƣợc phát biểu nhƣ sau:
Cho một tập hợp N chuỗi S ={S1, S2,..,SN}, trong đó mỗi phần tử được lấy
ra từ tập ={A, C, G, T} và hai số nguyên không âm ℓ và d, thỏa mãn 0 ≤d