Bài giảng Giải thuật nâng cao - Quy hoạch động cho bài toán - Ngô Quốc Việt

QUY HOẠCH ĐỘNG CHO BÀI TOÁN 
SEQUENCE ALIGNMENT 
TS. NGÔ QUỐC VIỆT 
2015 
Nội dung 
• Giới thiệu tóm tắt về dự án Human Genome 
• Bài toán sequence alignment 
• Các vấn đề cần giải quyết 
• Scoring system 
• Lập trình động cho vấn đề pairwise alignment 
• Bài toán local sequence alignment 
Giải thuật nâng cao-DP-Sequence Alignment 2 
Human genome project (HGP) – some milestones 
• 1977. Allan Maxam and Walter Gilbert at Harvard University and 
Frederick Sanger at the U.K. Medical Research Council (MRC) phát triển 
các phương pháp sequencing DNA. 
• 1988. NIH (National Institutes of Health) thành lập Office of Human 
Genome Research. 
• 1995. Patrick Brown of Stanford và cộng sự đăng first paper sử dụng 
printed glass microarray of complementary DNA (cDNA) probes 
• Các nhà nghiên cứu ở Whitehead và Généthon (Lander, Thomas 
Hudson at Whitehead) đăng physical map của human genome chứa 
15,000 markers. 
• 1996. NIH tài trợ 6 nhóm giải quyết large-scale sequencing of the 
human genome. 
• An international consortium publicly releases the complete 
 genome sequence of the yeast 
• 1998 NIH công bố dự án tìm SNP (Single Nucleotide Polymorphism) 
• 2001 The HGP consortium publishes its working draft in Nature (15 
February), Celera publishes its draft in Science (16 February). 
• 2006. Sequence tất cả chromosomes finalized. 
Giải thuật nâng cao-DP-Sequence Alignment 3 
Giới thiệu 
• Alignment nhằm: xác định hai hoặc nhiều chuỗi có liên 
quan với nhau hay không (quá trình tiến hóa). 
• Ví dụ: tìm được gene mới của người. Mong muốn xác 
định các tính chất. Khi đó, cần xác định phần tương ứng 
có trong chuột. Có hàng vạn gene của chuột, cần tìm cái 
nào tương ứng nhất với gene vừa tìm được. 
• Align proteins chia sẻ chức năng để xác định các chuỗi 
peptide có ảnh hưởng nhiều đến chức năng đó. 
• Align các chuỗi DNA nhằm xác định (chức năng hay tiến 
hóa) các gene liên quan để tìm các segments gắn liền 
với transcription factors. 
Giải thuật nâng cao-DP-Sequence Alignment 4 
Giới thiệu 
Giải thuật nâng cao-DP-Sequence Alignment 5 
Giới thiệu 
• Alignment là nền tảng để xác định các quan hệ tiến 
hóa. 
• Ví dụ: 
Giải thuật nâng cao-DP-Sequence Alignment 6 
Sequence Alignment 
• Trong thiết kế và/hoặc diễn dịch dữ liệu của các kỹ 
thuật high-throughput screening (dùng trong 
dược) dựa trên chuỗi. Khi đó so sánh chuỗi là cần 
thiết nhằm: 
- Để xác định microarray probes không có sequence 
tương tự với các gene khác. 
- Để match các sequence trong high-throughput 
sequencing data sang genome. 
- Để tìm motifs dựa trên ChIP-chip/ChIP-seq data. 
 Giải thuật nâng cao-DP-Sequence Alignment 7 
Sequence Alignment 
• Định nghĩa: Cho hai chuỗi 𝑥 = 𝑥1𝑥2𝑥𝑀, 𝑦 =
 𝑦1𝑦2𝑦𝑁, 
Alignment là gán các gap vào các vị trí 0,  , 𝑁 trong 
chuỗi x, và 0, , 𝑁 trong y, sao cho align thẳng hàng 
các chữ trong một chuỗi với chữ hoặc gap của chuỗi 
kia. 
 Giải thuật nâng cao-DP-Sequence Alignment 8 
-AGGCTATCACCTGACCTCCAGGCCGA--TGCCC--- 
TAG-CTATCAC--GACCGC--GGTCGATTTGCCCGAC 
AGGCTATCACCTGACCTCCAGGCCGATGCCC 
TAGCTATCACGACCGCGGTCGATTTGCCCGAC 
Sequence Alignment: Các vấn đề 
Không gian tìm kiếm lớn (số các alignments) 
Sequence 1: GSAQVK 
Sequence 2: GNPKVK 
GSAQVK----- GSAQVK---- 
-----GNPKVK ----GNPKVK 
GSAQ--VK -----GSAQVK 
-G-NPKVK GNPKVK----- 
Chọn giải pháp nào?? 
Giải thuật nâng cao-DP-Sequence Alignment 9 
Tiêu chuẩn đánh giá alignment 
AGGCTAGTT, AGCGAAGTTT 
AGGCTAGTT- 6 matches, 3 mismatches, 1 gap 
AGCGAAGTTT 
AGGCTA-GTT- 7 matches, 1 mismatch, 3 gaps 
AG-CGAAGTTT 
AGGC-TA-GTT- 7 matches, 0 mismatches, 5 gaps 
AG-CG-AAGTTT 
Giải thuật nâng cao-DP-Sequence Alignment 10 
Scoring Function 
• Để so sánh độ tương tự giữa hai chuỗi với các thay 
đổi như: đột biến, chèn, xóa. Cho chuỗi AGGCCTC 
• Mutations AGGACTC 
• Insertions AGGGCCTC 
• Deletions AGG . CTC 
• Ký hiệu 
• Match: +m 
• Mismatch: -s 
• Gap: -d 
• Scoring đơn giản: 
Score: F=(# matches)  m-(# mismatches) s–(#gaps)  d 
Giải thuật nâng cao-DP-Sequence Alignment 11 
Scoring Function 
• Độ đo: quasi-statistical model log-likelihood ratio. 
• Ký hiệu: 
• x, y là hai chuỗi, i là vị trí align. 
• Pxiyi: P(xi và yi đúng vị trí align) 
• Pxi: P(xi xuất hiện) 
• Pyi: P(yi xuất hiện) 
• M: một kiểu alignment 
• R: x, y là các chuỗi độc lập 
• Độ đo MLE 
𝑙𝑜𝑔
𝑃 𝑥, 𝑦|𝑀
𝑃 𝑥, 𝑦|𝑅
= 𝑙𝑜𝑔
 𝑃𝑥𝑖𝑦𝑖
 𝑃𝑥𝑖 𝑃𝑦𝑖
= 𝑙𝑜𝑔
𝑃𝑥𝑖𝑦𝑖
𝑃𝑥𝑖𝑃𝑥𝑖
Giải thuật nâng cao-DP-Sequence Alignment 12 
Scoring Function 
• M trong độ đo “quasi-statistical model log-likelihood 
ratio” là một lời giải sequence alignment. 
• Trong thực tế có thể sử dụng nhiều “lời giải” khác 
nhau 𝑀1, 𝑀2,  ,𝑀𝑛 
• Theo Bayes Rule 
𝑃 𝑀𝑖|𝑥, 𝑦 =
𝑃 𝑥, 𝑦|𝑀𝑖 𝑃 𝑀𝑖
 𝑃 𝑥, 𝑦|𝑀𝑗 𝑃 𝑀𝑗
∝ 𝑃 𝑥, 𝑦|𝑀𝑖 
• Mục tiêu là tìm alignment tốt nhất sao cho cực đại 
 𝑙𝑜𝑔
𝑃𝑥𝑖𝑦𝑖
𝑃𝑥𝑖𝑃𝑥𝑖
Giải thuật nâng cao-DP-Sequence Alignment 13 
Scoring Function 
Nhận xét: 
 Score của alignment x1xM 
 y1yN 
 có tính cộng 
Nghĩa là x1xi xi+1xM 
align với y1yj yj+1yN 
Hai scores có thể cộng: 
F(x[1:M], y[1:N]) = F(x[1:i], y[1:j]) + F(x[i+1:M], y[j+1:N]) 
Giải thuật nâng cao-DP-Sequence Alignment 14 
Quy hoạch động 
• There are only a polynomial number of subproblems 
• Align x1xi to y1yj 
• Original problem is one of the subproblems 
• Align x1xM to y1yN 
• Each subproblem is easily solved from smaller subproblems 
• Then, we can apply Dynamic Programming!!! 
Đặt 
 F(i, j) = optimal score of aligning 
 x1xi 
 y1yj 
Giải thuật nâng cao-DP-Sequence Alignment 15 
Sequence Alignment - Quy hoạch động 
• Có 3 trường hợp 
Giải thuật nâng cao-DP-Sequence Alignment 16 
1. xi align với yj 
 x1xi-1 xi 
 y1yj-1 yj 
2. xi align với gap 
 x1xi-1 xi 
 y1yj - 
3. yj aligns với gap 
 x1xi - 
 y1yj-1 yj 
 m, if xi = yj 
F(i, j) = F(i – 1, j – 1) + 
 -s, if not 
F(i, j) = F(i – 1, j) – d 
F(i, j) = F(i, j – 1) – d 
Sequence Alignment - Quy hoạch động 
Giả sử quy nạp : 
 F(i, j – 1), F(i – 1, j), F(i – 1, j – 1) là tối ưu 
Thì, 
 F(i – 1, j – 1) + s(xi, yj) 
 F(i, j) = max F(i – 1, j) – d 
 F(i, j – 1) – d 
Với s(xi, yj) = m, if xi = yj; -s, if not 
 Giải thuật nâng cao-DP-Sequence Alignment 17 
Sequence alignment – ví dụ 
Giải thuật nâng cao-DP-Sequence Alignment 18 
G 
 - 
A G T A 
0 -1 -2 -3 -4 
A -1 1 0 -1 -2 
T -2 0 0 1 0 
A -3 -1 -1 0 2 
F(i,j) i = 0 1 2 3 4 
x = AGTA m = 1 
y = ATA s = -1 
 d = -1 
j = 0 
1 
2 
3 
F(1, 1) = 
max{F(0,0) + s(A, A), 
 F(0, 1) – d, 
 F(1, 0) – d} = 
max{0 + 1, 
 -1 – 1, 
 -1 – 1} = 1 
A 
A 
T 
T 
A 
A 
Output Alignment 
• Theo vết backpointers 
• Gặp diagonal, 
OUTPUT xi, yj 
• Gặp up,
OUTPUT yj 
• Gặp left, 
OUTPUT xi 
Giải thuật Needleman-Wunsch 
Giải thuật nâng cao-DP-Sequence Alignment 19 
1. Initialization. 
a. F(0, 0) = 0 
b. F(0, j) = - j  d 
c. F(i, 0) = - i  d 
2. Main Iteration. Filling-in partial alignments 
a. For each i = 1M 
 For each j = 1N 
 F(i – 1,j – 1) + s(xi, yj) [case 1] 
 F(i, j) = max F(i – 1, j) – d [case 2] 
 F(i, j – 1) – d [case 3] 
 DIAG, if [case 1] 
 Ptr(i, j) = LEFT, if [case 2] 
 UP, if [case 3] 
3. Termination. F(M, N) is the optimal score, and 
 from Ptr(M, N) can trace back optimal alignment 
Local alignment 
Giải thuật nâng cao-DP-Sequence Alignment 20 
Cho hai chuỗi x = x1xM, 
 y = y1yN 
Tìm substrings x’, y’ sao cho có độ tương tự 
 (optimal global alignment value) 
 lớn nhất 
 x = aaaacccccggggtta 
 y = ttcccgggaaccaacc 
Lý do cần local alignment 
Giải thuật nâng cao-DP-Sequence Alignment 21 
• Genes are shuffled between genomes 
• Các phần của các protein thường được bảo toàn 
Sự tương tự genome Cross-species 
Giải thuật nâng cao-DP-Sequence Alignment 22 
• 98% genes được duy trì giữa hai loài động vật có vú bất kỳ 
• Nhiều hơn 70% average similarity trong protein sequence 
hum_a : GTTGACAATAGAGGGTCTGGCAGAGGCTC--------------------- @ 57331/400001 
mus_a : GCTGACAATAGAGGGGCTGGCAGAGGCTC--------------------- @ 78560/400001 
rat_a : GCTGACAATAGAGGGGCTGGCAGAGACTC--------------------- @ 112658/369938 
fug_a : TTTGTTGATGGGGAGCGTGCATTAATTTCAGGCTATTGTTAACAGGCTCG @ 36008/68174 
hum_a : CTGGCCGCGGTGCGGAGCGTCTGGAGCGGAGCACGCGCTGTCAGCTGGTG @ 57381/400001 
mus_a : CTGGCCCCGGTGCGGAGCGTCTGGAGCGGAGCACGCGCTGTCAGCTGGTG @ 78610/400001 
rat_a : CTGGCCCCGGTGCGGAGCGTCTGGAGCGGAGCACGCGCTGTCAGCTGGTG @ 112708/369938 
fug_a : TGGGCCGAGGTGTTGGATGGCCTGAGTGAAGCACGCGCTGTCAGCTGGCG @ 36058/68174 
hum_a : AGCGCACTCTCCTTTCAGGCAGCTCCCCGGGGAGCTGTGCGGCCACATTT @ 57431/400001 
mus_a : AGCGCACTCG-CTTTCAGGCCGCTCCCCGGGGAGCTGAGCGGCCACATTT @ 78659/400001 
rat_a : AGCGCACTCG-CTTTCAGGCCGCTCCCCGGGGAGCTGCGCGGCCACATTT @ 112757/369938 
fug_a : AGCGCTCGCG------------------------AGTCCCTGCCGTGTCC @ 36084/68174 
hum_a : AACACCATCATCACCCCTCCCCGGCCTCCTCAACCTCGGCCTCCTCCTCG @ 57481/400001 
mus_a : AACACCGTCGTCA-CCCTCCCCGGCCTCCTCAACCTCGGCCTCCTCCTCG @ 78708/400001 
rat_a : AACACCGTCGTCA-CCCTCCCCGGCCTCCTCAACCTCGGCCTCCTCCTCG @ 112806/369938 
fug_a : CCGAGGACCCTGA------------------------------------- @ 36097/68174 
Ví dụ các chuỗi tương 
tự trong human, rat, 
mouse, cá nóc (fugu) 
Giải thuật Smith-Waterman 
Giải thuật nâng cao-DP-Sequence Alignment 23 
Ý tưởng: bỏ qua các vùng badly aligning 
Điều chỉnh giải thuật Needleman-Wunsch: 
Khởi tạo: F(0, j) = F(i, 0) = 0 
 0 
Iteration: F(i, j) = max F(i – 1, j) – d 
 F(i, j – 1) – d 
 F(i – 1, j – 1) + s(xi, yj) 
Smith-Waterman algorithm 
Giải thuật nâng cao-DP-Sequence Alignment 24 
Kết thúc: 
1. Nếu muốn best local alignment 
 FOPT = maxi,j F(i, j) 
 Tìm FOPT và theo vết ngược 
2. Nếu muốn all local alignments có scoring > t 
 For all i, j find F(i, j) > t, and trace back? 
Complicated by overlapping local alignments 
( Waterman–Eggert ’87: find all non-overlapping local alignments with 
 minimal recalculation of the DP matrix ) 
Scoring các gap chính xác hơn 
Mô hình hiện tại: 
 Gap chiều dài n 
 incurs penalty nd 
Tuy nhiên, gaps thường xuất hiện thành các nhóm 
Khi đó, dùng hàm Convex gap penalty: 
 (n): 
 for all n, (n + 1) - (n)  (n) - (n – 1) 
(n) 
(n) 
Convex gap dynamic programming 
Khởi tạo: không thay đổi 
Iteration: 
 F(i – 1, j – 1) + s(xi, yj) 
 F(i, j) = max maxk=0i-1F(k, j) – (i – k) 
 maxk=0j-1F(i, k) – (j – k) 
Termination: không thay đổi 
Running Time: O(N2M) (giả sử N>M) 
Space: O(NM) 
Compromise: affine gaps 
(n) = d + (n – 1)  e 
 | | 
 gap gap 
 open extend 
Để tính optimal alignment, 
Tại vị trí i, j, cần “lưu trữ” best score nếu gap là open 
 best score if gap là not open 
F(i, j): score của alignment x1xi với y1yj 
 if xi aligns to yj 
G(i, j): score if xi aligns với gap sau yj 
H(i, j): score if yj aligns với gap sau xi 
V(i, j) = best score của alignment x1xi to y1yj 
d 
e 
(n) 
Needleman-Wunsch with affine gaps 
Vì sao cần 3 ma trận F, G, H? 
• xi aligns to yj 
 x1xi-1 xi xi+1 
 y1yj-1 yj - 
• xi aligns to a gap after yj 
 x1xi-1 xi xi+1 
 y1yj - - 
Add -d 
Add -e 
G(i+1, j) = F(i, j) – d 
G(i+1, j) = G(i, j) – e 
Vì: 
G(i, j) < V(i, j) 
(best để align xi với yj nếu đang align 
chỉ x1xi với y1yj và not the rest of x, y), 
Nhưng ngược lại 
G(i, j) – e > V(i, j) – d 
(i.e., had we “fixed” our decision that xi aligns 
to yj, we could regret it at the next step when 
aligning x1xi+1 to y1yj) 
Needleman-Wunsch dùng affine gaps 
Khởi tạo: V(i, 0) = d + (i – 1)e 
 V(0, j) = d + (j – 1)e 
Lặp: 
 V(i, j) = max{ F(i, j), G(i, j), H(i, j) } 
 F(i, j) = V(i – 1, j – 1) + s(xi, yj) 
 V(i – 1, j) – d 
 G(i, j) = max 
 G(i – 1, j) – e 
 V(i, j – 1) – d 
 H(i, j) = max 
 H(i, j – 1) – e 
Kết thúc: V(i, j) có best alignment 
Bounded Dynamic Programming 
Giả sử x và y rất tương tự 
Giải sử: # gaps(x, y) < k(N) 
 xi 
 Thì, | suy ra | i – j | < k(N) 
 yj 
Có thể align x và y hiệu quả hơn: 
 Time, Space: O(N  k(N)) << O(N2) 
Bounded Dynamic Programming 
Khởi tạo: 
 F(i,0), F(0,j) không xác định cho i, j > k 
Lặp: 
For i = 1M 
 For j = max(1, i – k)min(N, i+k) 
 F(i – 1, j – 1)+ s(xi, yj) 
 F(i, j) = max F(i, j – 1) – d, if j > i – k(N) 
 F(i – 1, j) – d, if j < i + k(N) 
Termination: không thay đổi 
Dễ dàng áp dụng cho affine gap 
x1  xM 
y
1
y
N
k(N) 
Tóm tắt 
• Global sequence alignment 
• Needleman–Wunsch 
• Overlap detection 
• Banded alignment 
• Convex gaps 
• Affine gaps 
• Local sequence alignment 
• Smith-Waterman 
Giải thuật nâng cao-DP-Sequence Alignment 32