Bài giảng Tin sinh học đại cương - Chương 4: Phân tích trình tự DNA - Trần Văn Lăng

ã thông điệp được mã hóa này 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 44 
12 
•  Các gợi ý như sau: 
–  Thông điệp được mã hóa 
bằng tiếng Anh 
–  Mỗi ký hiệu tương ứng với 
một chữ cái trong bảng chữ 
cái tiếng Anh 
–  Không có dấu chấm câu 
được mã hóa 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 45 
Cách giải quyết 
•  Đếm tần số xuất hiện 
của mỗi ký hiệu trong 
thông điệp được mã hóa 
•  Tìm tần số của mỗi ký tự 
trong bảng chữ cái của 
văn bản tiếng Anh 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 46 
•  So sánh các tần số của 
các bước trước đó, cố 
gắng tìm một mối tương 
quan và ánh xạ các ký 
hiệu với một ký tự trong 
bảng chữ cái 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 47 
•  Tần số theo thông điệp của Gold Bug 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 48 
•  Tần số theo bảng chữ cái tiếng Anh 
e t a o i n s r h l d c u m f p g w y b v k x j q z 
Tần số cao tần số thấp 
Symbol 8 ; 4 ) + * 5 6 ( ! 1 0 2 9 3 : ? ` - ] . 
Frequency 34 25 19 16 15 14 12 11 9 8 7 6 5 5 4 4 3 2 1 1 1 
13 
•  Bằng cách ánh xạ đơn giản các ký hiệu có 
tần số cao nhất đến các ký tự có tần số cao 
nhất tương ứng trong bảng chữ cái. 
•  Giải mã 4 mãnh trong thông điệp bí mật 
sfiilfcsoorntaeuroaikoaiotecrntaeleyr
cooestvenpinelefheeosnlt 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 49 
arhteenmrnwteonihtaesotsnlupnihtamsrn
uhsnbaoeyentacrmuesotorl 
eoaiitdhimtaecedtepeidtaelestaoaeslsu
eecrnedhimtaetheetahiwfa 
taeoaitdrdtpdeetiwt 
•  Kết quả không có ý nghĩa gì cả 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 50 
Cách tiếp cận tốt hơn 
•  Đánh giá tần số của l-tuples như tổ hợo 
của 2 ký hiệu, 3 ký hiệu, v.v Chẳng hạn, 
– “The” là 3-tupe có tần số cao nhất trong tiếng 
Anh; “;48” là 3-tuple có tần số cao nhất trong 
thông điệp mã hóa 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 51 
•  Suy ra tương tự cho 
các ký hiệu chưa biết 
trong văn bản mã hóa 
dựa trên tần số của 
các l-tuple. 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 52 
14 
•  Ánh xạ “the” đến “;48” và thay thế tất cả 
các ký hiệu xuất hiện: 
 53++!305))6*the26)h+.)h+)te06*the!
e`60))e5t]e*:+*e!e3(ee)5*!t 
 h6(tee*96*?te)*+(the5)t5*!2:*+
(th956*2(5*h)e`e*th0692e5)t)6!e 
 )h++t1(+9the0e1te:e+1the!e5th)he5!
52ee06*e1(+9thet(eeth(+?3ht 
 he)h+t161t:1eet+?t 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 53 
•  Suy đoán 
 53++!305))6*the26)h+.)h+)te06*the!
e`60))e5t]e*:+*e!e3(ee)5*!t 
 h6(tee*96*?te)*+(the5)t5*!2:*+
(th956*2(5*h)e`e*th0692e5)t)6!e 
 )h++t1(+9the0e1te:e+1the!e5th)he5!
52ee06*e1(+9thet(eeth(+?3ht 
 he)h+t161t:1eet+?t 
•  “thet(ee” most likely means “the tree” 
–  Suy ra Infer “(“ = “r” 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 54 
•  Khi đó, “th(+?3h” trở thành “thr+?3h” 
–  Sau đó có thể đề xuất “+”, “?” được mã hóa 
ra sao. 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 55 
•  Sau khi tìm ra tất cả các ánh xạ, thông điệp 
có thể giải mã như sau: 
AGOODGLASSINTHEBISHOPSHOSTELINTHEDEVILSSEATWEN
YONEDEGREESANDTHIRTEENMINUTESNORTHEASTANDBYNOR
THMAINBRANCHSEVENTHLIMBEASTSIDESHOOTFROMTHELEF
TEYEOFTHEDEATHSHEADABEELINEFROMTHETREETHROUGHT
HESHOTFIFTYFEETOUT 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 56 
15 
•  Sử dụng dấu chấm câu, thông điệp có thể là: 
 A GOOD GLASS IN THE BISHOP’S HOSTEL IN THE 
DEVIL’S SEA, 
 TWENY ONE DEGREES AND THIRTEEN MINUTES 
NORTHEAST AND BY NORTH, 
 MAIN BRANCH SEVENTH LIMB, EAST SIDE, SHOOT 
FROM THE LEFT EYE OF 
 THE DEATH’S HEAD A BEE LINE FROM THE TREE 
THROUGH THE SHOT, 
 FIFTY FEET OUT. 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 57 
Giải bài toán Gold Bug 
•  Những điều kiện tiên quyết để giải bài toán: 
–  Cần phải biết tần số tương đối của các chữ cái, 
và sự kết hợp của hai và ba chữ cái trong tiếng 
Anh 
–  Kiến thức về tất cả các từ trong từ điển tiếng Anh 
là mong muốn cao để có những kết luận chính 
xác 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 58 
Sự tương tự giữa 2 bài toán 
•  Những nucleotide trong một 
motif mã hóa là ngôn ngữ của 
di truyền, tương tự như ký hiệu 
mã hóa trong “The Gold Bug” 
của một thông điệp (message) 
bằng tiếng Anh 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 59 
•  Để giải mã, cần phân tích tần số của các 
mẫu thông điệp DNA/Gold Bug 
•  Kiến thức của các motif điều chỉnh được thiết 
lập làm cơ sở cho việc tìm motif; cũng như 
kiến thức về các từ trong từ điển Tiếng Anh 
làm cơ sở cho việc giải bài táon Gold Bug 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 60 
16 
•  Bài toán Motif Finding: 
–  Phân tích tần suất xuất hiện các 
mẫu (pattern) trong những trình 
tự nucleotide 
•  Bài toán Gold Bug Problem 
–  Phân tích tần suất xuất hiện các 
mẫu trong văn bản được viết 
bằng Tiếng Anh 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 61 
•  Motif Finding: 
–  Kiến thức về các motif được thiết lập làm giảm 
độ phức tạp của bài toán 
•  Gold Bug Problem: 
–  Kiến thức về các từ trong từ điển Tiếng Anh là 
hết sức mong đợi 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 62 
•  Bài toán Motif Finding khó hơn bài toán Gold 
Bug: 
–  Không có từ điển đầy đủ về motif 
–  Ngôn ngữ di truyền học không có văn phạm 
chuẩn 
–  Chỉ một phần nhỏ trình tự nucleotide mã hóa cho 
motif, trong khi đó kích thước dữ liệu lại rất lớn 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 63 
Minh họa bài toán Motif Finding 
•  Cho một mẫu ngẫu nhiên các trình tự DNA 
cctgatagacgctatctggctatccacgtacgtaggtcctctgtgcgaatctatgcgtttccaaccat 
agtactggtgtacatttgatacgtacgtacaccggcaacctgaaacaaacgctcagaaccagaagtgc 
aaacgtacgtgcaccctctttcttcgtggctctggccaacgagggctgatgtataagacgaaaatttt 
agcctccgatgtaagtcatagctgtaactattacctgccacccctattacatcttacgtacgtataca 
ctgttatacaacgcgtcatggcggggtatgcgttttggtcgtcgtacgctcgatcgttaacgtacgtc 
•  Tìm mẫu được ghép vào mỗi trình tự riêng, 
gọi là motif 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 64 
17 
•  Thông tin thêm: 
–  Mỗi trình tự che dấu có 
chiều dài 8 
–  Các mẫu không hoàn toàn 
giống nhau bởi điểm đột 
biến là ngẫu nhiên xẩy ra 
trong các trình tự 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 65 
•  Các mẫu cho thấy không có đột biến 
cctgatagacgctatctggctatccacgtacgtaggtcctctgtgcgaatctatgcgtttccaaccat 
agtactggtgtacatttgatacgtacgtacaccggcaacctgaaacaaacgctcagaaccagaagtgc 
aaacgtacgtgcaccctctttcttcgtggctctggccaacgagggctgatgtataagacgaaaatttt 
agcctccgatgtaagtcatagctgtaactattacctgccacccctattacatcttacgtacgtataca 
ctgttatacaacgcgtcatggcggggtatgcgttttggtcgtcgtacgctcgatcgttaacgtacgtc 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 66 
acgtacgt 
Chuỗi liên ứng (Consensus String) 
•  Mẫu với 2 đột biến: 
cctgatagacgctatctggctatccaGgtacTtaggtcctctgtgcgaatctatgcgtttccaaccat 
agtactggtgtacatttgatCcAtacgtacaccggcaacctgaaacaaacgctcagaaccagaagtgc 
aaacgtTAgtgcaccctctttcttcgtggctctggccaacgagggctgatgtataagacgaaaatttt 
agcctccgatgtaagtcatagctgtaactattacctgccacccctattacatcttacgtCcAtataca 
ctgttatacaacgcgtcatggcggggtatgcgttttggtcgtcgtacgctcgatcgttaCcgtacgGc 
•  Liệu có thể tìm được motif với 2 đột biến 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 67 
aGgtacTt 
CcAtacgt 
acgtTAgt 
acgtCcAt 
CcgtacgG 
Mẫu với 2 đột biến 
acgtacgt 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 68 
18 
Phân loại bài toán tìm motif 
•  Có 2 dạng bài toán tìm motif: 
–  Không đột biến: Cho trước t trình tự, hãy xác định 
các đoạn trình tự có chiều dài l (l-mer) trên mỗi 
trình tự sao cho đoạn này bắt cặp giống nhau. 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 69 
–  Dạng đột biến: Cho trước t trình 
tự, hãy xác định các đoạn trình 
tự có chiều dài l sao cho các 
đoạn này gần giống nhau trên 
các trình tự cho phép đột biến 
(sai lệch) d vị trí 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 70 
Định nghĩa Motif 
•  Để định nghĩa một motif, cần biết vị trí bắt 
đầu của motif trong trình tự. 
•  Vị trí này có thể biểu diễn bởi s = (s1,s2,s3,
,st) 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 71 
Profiles và Consensus 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 72 
 a G g t a c T t 
 C c A t a c g t 
Alignment a c g t T A g t 
 a c g t C c A t 
 C c g t a c g G 
 A 3 0 1 0 3 1 1 0 
Profile C 2 4 0 0 1 4 0 0 
 G 0 1 4 0 0 0 3 1 
 T 0 0 0 5 1 0 1 4 
Consensus A C G T A C G T 
•  Sắp hàng các mẫu theo 
vị trí bắt đầu của nó 
 s = (s1, s2, , st) 
•  Xây dựng ma trận profile 
với tần suất xuất hiện của 
mỗi nucleotide theo cột 
•  Consensus nucleotide là 
nucleotide có điểm cao 
nhất trong cột 
19 
Consensus 
•  Consensus (trình tự liên ứng) ở đây được 
hiểu như là một motif tổ tiên mà từ đó các 
motif đột biến xuất hiện 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 73 
Khoảng cách giữa các trình tự 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 74 
Đánh giá motif 
•  Trước hết, ta có các tham số 
–  t - số mẫu trình tự DNA 
–  n - chiều dài mỗi trình tự DNA 
–  DNA –mẫu DNA (mảng t x n) 
–  l - chiều dài của motif (l-mer) 
–  si - vị trí bắt đầu của motif trong trình tự i 
–  s=(s1, s2, st) - mảng chứa các vị trí bắt đầu của 
motif 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 75 
Ví dụ về các tham số 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 76 
 cctgatagacgctatctggctatccaGgtacTtaggtcctctgtgcgaatctatgcgtttccaaccat 
 agtactggtgtacatttgatCcAtacgtacaccggcaacctgaaacaaacgctcagaaccagaagtgc 
 aaacgtTAgtgcaccctctttcttcgtggctctggccaacgagggctgatgtataagacgaaaatttt 
 agcctccgatgtaagtcatagctgtaactattacctgccacccctattacatcttacgtCcAtataca 
 ctgttatacaacgcgtcatggcggggtatgcgttttggtcgtcgtacgctcgatcgttaCcgtacgGc 
l = 8 
s1 = 26 s2 = 21 s3= 3 s4 = 56 s5 = 60 s 
DNA 
n = 69 
20 
Tính điểm để đánh giá 
•  Cho s = (s1,  st) và DNA: 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 77 
 a G g t a c T t 
 C c A t a c g t 
 a c g t T A g t 
 a c g t C c A t 
 C c g t a c g G 
 _________________ 
 A 3 0 1 0 3 1 1 0 
 C 2 4 0 0 1 4 0 0 
 G 0 1 4 0 0 0 3 1 
 T 0 0 0 5 1 0 1 4 
 _________________ 
 Consensus a c g t a c g t 
 Score 3+4+4+5+3+4+3+4=30 
score(s,DNA) =
k∈{A,T ,C,G}
max count(k, i)
i=1
l
∑
–  Với count(k,i) là số 
nucleotide thứ k ở vị trí thứ 
i của l-motif 
l 
t 
•  Nếu các vị trí bằt đầu s=(s1, s2, st) cho 
trước, việc tìm consensus dễ dàng ngay cả 
khi có đột biến trong các trình tự. 
–  Bởi khi đó ta có thể xây dựng ma trận profile, từ 
đó tìm motif (consensus) 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 78 
•  Nhưng, khi s không cho trước, làm thế nào 
để tìm ma trận profile tốt nhất. 
–  Bài toán đặt ra: 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 79 
Bài toán 
•  Mục tiêu: Cho mẫu DNA, tìm tập l-mers từ 
các trình tự sao cho điểm consensus là cực 
đại 
•  Nhập: A t x n mảng các mẫu DNA, và chiều 
lài l của pattern muốn tìm 
•  Xuất: Mảng t vị trí s = (s1, s2,  st) mà 
Score(s,DNA) đạt cực đại 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 80 
21 
Thuật toán Brute Force 
•  Tính score của một tổ hợp với vị trí bắt đầu s 
•  Điểm tốt nhất được xác định bởi profile tốt 
nhất. 
•  Tìm Score(s,DNA) lớn nhất bằng cách thay 
đổi vị trí bắt đầu si, với i từ 1 đến n-l+1 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 81 
BruteForceMotifSearch(DNA, t, n, l)
bestScoe ß 0
for s=(s1,s2 , . . ., st) from (1,1 . . . 1) to 
(n-l+1, . . ., n-l+1)
if (Score(s,DNA) > bestScore)
bestScore ß score(s, DNA)
bestMotif ß (s1,s2 , . . . , st) 
return bestMotif
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 82 
Nhận xét 
•  Thay đổi (n - l + 1) vị trí trong t trình tự, cần 
(n - l + 1)t tập hợp các vị trí bắt đầu 
•  Đối với mỗi tập hợp vị trí bắt đầu, score 
được tính dựa trên l phép toán, vì vậy độ 
phức tạp tính toán là l x (n – l + 1)t = O(lnt) 
•  Với t = 8, n = 1000, l = 10 phải thực hiện 
xấp xỉ 1032 tính toán. 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 83 
Bài toán Median String 
•  Với lý do trên, nên vấn đề đặt ra là tìm một 
thuật toán nhanh hơn để giải quyết. 
•  Bài toán Motif Finding được đưa về bài toán 
Median String (chuỗi trung bình) 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 84 
22 
•  Bài toán Median String: 
–  Cho mẫu t trình tự DNA tìm pattern xuất hiện 
trong tất cả t trình tự với số đột biến ít nhất 
–  Pattern này chính là motif 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 85 
Khoảng cách Hamming 
•  Khoảng cách Hamming: 
–  dH(v,w) là số cặp nucleotide mismatch (do not 
match) khi sắp hàng v và w. Chẳng hạn 
dH(AAAAAA,ACAAAC) = 2 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 86 
Ví dụ 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 87 
•  Cho v = “acgtacgt” và mẫu DNA 
 acgtacgt 
cctgatagacgctatctggctatccacgtacgtaggtcctctgtgcgaatctatgcgtttccaaccat 
 acgtacgt 
agtactggtgtacatttgatacgtacgtacaccggcaacctgaaacaaacgctcagaaccagaagtgc 
 acgtacgt 
aaacgtacgtgcaccctctttcttcgtggctctggccaacgagggctgatgtataagacgaaaatttt 
 acgtacgt 
agcctccgatgtaagtcatagctgtaactattacctgccacccctattacatcttacgtacgtataca 
 acgtacgt 
ctgttatacaacgcgtcatggcggggtatgcgttttggtcgtcgtacgctcgatcgttaacgtacgtc 
dH(v, x) = 0 
dH(v, x) = 0 
dH(v, x) = 0 
dH(v, x) = 0 dH(v, x) = 0 
TotalDistance(v,DNA) = 0 
Ví dụ 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 88 
•  Cho v = “acgtacgt” và mẫu DNA 
 acgtacgt 
cctgatagacgctatctggctatccacgtacAtaggtcctctgtgcgaatctatgcgtttccaaccat 
 acgtacgt 
agtactggtgtacatttgatacgtacgtacaccggcaacctgaaacaaacgctcagaaccagaagtgc 
 acgtacgt 
aaaAgtCcgtgcaccctctttcttcgtggctctggccaacgagggctgatgtataagacgaaaatttt 
 acgtacgt 
agcctccgatgtaagtcatagctgtaactattacctgccacccctattacatcttacgtacgtataca 
 acgtacgt 
ctgttatacaacgcgtcatggcggggtatgcgttttggtcgtcgtacgctcgatcgttaacgtaGgtc 
dH(v, x) = 1 
dH(v, x) = 0 
dH(v, x) = 0 
dH(v, x) = 1 dH(v, x) = 2 
TotalDistance(v,DNA) = 1 + 0 + 2 + 0 + 1 = 4 
23 
•  Với trình tự DNA thứ i, tính tất cả dH(v, x), ở đó x là 
l-mer với vị trí bắt đầu si 
 (1 < si < n – l + 1) 
•  Tìm cực tiểu dH(v, x) của tất cả các l-mers trong 
trình tự i 
•  TotalDistance(v,DNA) tổng của các khoảng cách 
Hamming tối thiểu cho trình tự DNA thứ i 
•  TotalDistance(v,DNA) = mins dH(v, s), ở đó s là 
tập hợp các vị trí bắt đầu s1, s2, st 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 89 
Thuật toán 
•  Mục tiêu: cho mẫu các trình tự DNA, tìm 
chuỗi trung bình 
•  Nhập: Ma trận DNA t x n, chiều dài l của 
mẫu cần tìm. 
•  Xuất: chuỗi v gồm l nucleotides mà 
TotalDistance(v,DNA) đạt cực tiểu đối với tất 
cả các chuỗi có cùng chiều dài. 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 90 
MedianStringSearch (DNA, t, n, l)
bestWord ß AAAA
bestDistance ß ∞
for each l-mer s from AAAA to TTTT 
if TotalDistance(s,DNA) < bestDistance
 bestDistanceßTotalDistance(s,DNA) 
 bestWord ß s
 return bestWord
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 91 
•  Motif Finding Problem == Median String 
Problem 
–  Motif Finding là bài toán cực đại, trong khi 
Median String là bài toán cực tiểu 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 92 
24 
•  Tuy nhiên, đây là 2 bài toán tương đương 
–  TotalDistance đạt cực tiểu tương đương Score 
đạt cực đại 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 93 
Sự giống nhau 
Ta có: 
Scorei + TotalDistancei = t với các 
cột 
Suy ra: 
l x (Scorej + TotalDistancej)= l x t 
Hay Score = l x t – TotalDistance 
Mà l x t là hằng, nên vế phải đạt cực 
tiểu tương đương vế trái đạt cực đại 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 94 
 a G g t a c T t 
 C c A t a c g t 
Alignment a c g t T A g t 
 a c g t C c A t 
 C c g t a c g G 
 _________________ 
 A 3 0 1 0 3 1 1 0 
Profile C 2 4 0 0 1 4 0 0 
 G 0 1 4 0 0 0 3 1 
 T 0 0 0 5 1 0 1 4 
 _________________ 
Consensus a c g t a c g t 
Score 3+4+4+5+3+4+3+4 
TotalDistance 2+2+2+2+2 = 10 = 
2+1+1+0+2+1+2+1 
Sum 5 5 5 5 5 5 5 5 
•  Tại sao lại quan tâm đến chuyện thay bài 
toán Motif Finding bằng Median String 
–  Motif Finding Problem cần tính toán với tất cả các 
tổ hợp của s. Đó là (n - l + 1)t tổ hợp. 
–  Median String Problem cần tính toán 4l tổ hợp 
của v. Con số này tương đối nhỏ hơn. 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 95 
Các bước tìm motif 
•  Cho một trình tự v có chiều dài l (gọi là l-mer) 
•  Và cho t trình tự có chiều dài n 
•  Tính các khoảng cách Hamming dH(v,x), 
trong đó x là l-mer có vị trí bắt đầu lần lượt từ 
1 đến n-l+1 trong trình tự thứ i 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 96 
25 
•  Từ đây suy ra dH(v,xi) là khoảng cách cực 
tiển trong các khoảng cách này của trình tự i. 
•  Tính TotalDistance là tổng các dH(v,xi) với i 
từ 1 đến t. 
•  Khi đó các xi là các motif tìm được trên cơ sở 
trình tự v cho trước. 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 97 
•  Nhận xét: 
–  Trong trường hợp v chưa biết trước, số lượng 
motif xi cần tìm là quá ít so với tập hợp tìm kiếm. 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 98 
KÝ HIỆU PROTEIN MOTIF 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 99 
Ký hiệu protein motif 
•  x: được dùng để chỉ vị trí mà bất cứ amino 
acide nào cũng được chấp nhận 
•  []: tại vị trí này có thể là một trong các amino 
acide được liệt kê 
•  {}: tại vị trí này có thế bất kỳ amino acide nào 
ngoại trừ phân tử được liệt kê 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 100 
26 
•  Ví dụ: 
–  [AC]xVx(2){GV} 
–  Là motif gồm: Alanine hoặc Cysteine - amino 
acide – Valine - amino acide -amino acide -Ngoại 
trừ Glutamate và Valine 
•  x(2): có 2 amino acide bất kỳ 
•  x(0,3): có từ 0 đến 3 amino acide bất kỳ 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 101 
•  <: cho biết motif nằm ở đầu trình tự protein 
•  >: cho biết motif nằm ở cuối trình tự protein 
•  Ví dụ: < Ax[ST](2)x(0,1)V 
–  Motif nằm ở đầu trình tự gồm: Alanine – amino 
acide - Serine hoặc Threonine - Serine hoặc 
Threonine – có amino acide hoặc không – Valine 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 102 
•  Ví dụ: 
–  Với l = 10, n = 1000, t = 8 
–  Số mẫu l-mer cần tìm trong mổi trình tự là 
1000-10+1 = 991 
–  Trong t trình tự có 8 x 991 = 7928 mẫu 
–  Như vậy: chỉ tìm 8 mẫu (8 motif) trong 7928 mẫu 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 103 
Motif 
Trình tự sinh học 
dài 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 104