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
32 trang |
Chia sẻ: phuongt97 | Lượt xem: 432 | Lượt tải: 0
Bạn đang xem trước 20 trang nội dung tài liệu Bài giảng Giải thuật nâng cao: Quy hoạch động cho bài toán Sequence Alignment - Ngô Quốc Việt, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
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
AGGCTATCACCTGACCTCCAGGCCGATGCCC
TAGCTATCACGACCGCGGTCGATTTGCCCGAC
-AGGCTATCACCTGACCTCCAGGCCGA--TGCCC---
TAG-CTATCAC--GACCGC--GGTCGATTTGCCCGAC
• Đị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
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
1. xi align với yj
x1xi-1 xi m, if xi = yj
F(i, j) = F(i – 1, j – 1) +
y1yj-1 yj
-s, if not
2. xi align với gap
x1xi-1 xi
y1yj - F(i, j) = F(i – 1, j) – d
3. y aligns với gap
j
x1xi - F(i, j) = F(i, j – 1) – d
y1yj-1 yj
Giải thuật nâng cao-DP-Sequence Alignment 16
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ụ
x = AGTA m = 1
y = ATA Outputs = -1 Alignment
d = -1
• Theo vết backpointers
F(i,j) i = 0 1 2 3 4
• GặpF(1, diagonal, 1) =
A G T A OUTPUTmax{F(0,0) xi, y +j s(A, A),
F(0, 1) – d,
j = 0 0 -1 -2 -3 -4 • Gặp up, F(1, 0) – d} =
OUTPUT yj
A -1 1 0 -1 -2 max{0 + 1,
1 • Gặp left, -1 – 1,
OUTPUT -1 – 1}x = 1
2 T -2 0 0 1 0 i
3 A -3 -1 -1 0 2 A G T A
A - T A
Giải thuật nâng cao-DP-Sequence Alignment 18
Giải thuật Needleman-Wunsch
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
Giải thuật nâng cao-DP-Sequence Alignment 19
Local alignment
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
Giải thuật nâng cao-DP-Sequence Alignment 20
Lý do cần local alignment
• Genes are shuffled between genomes
• Các phần của các protein thường được bảo toàn
Giải thuật nâng cao-DP-Sequence Alignment 21
Sự tương tự genome Cross-species
• 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 Ví dụ các chuỗi tương
tự trong human, rat,
hum_a : AGCGCACTCTCCTTTCAGGCAGCTCCCCGGGGAGCTGTGCGGCCACATTT @ 57431/400001
mus_a : AGCGCACTCG-CTTTCAGGCCGCTCCCCGGGGAGCTGAGCGGCCACATTT @ 78659/400001 mouse, cá nóc (fugu)
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
Giải thuật nâng cao-DP-Sequence Alignment 22
Giải thuật Smith-Waterman
Ý 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)
Giải thuật nâng cao-DP-Sequence Alignment 23
Smith-Waterman algorithm
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 )
Giải thuật nâng cao-DP-Sequence Alignment 24
Scoring các gap chính xác hơn
Mô hình hiện tại: (n)
Gap chiều dài n
incurs penalty nd
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)
(n):
for all n, (n + 1) - (n) (n) - (n – 1)
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
(n)
| |
gap gap
open extend e
d
Để 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
Needleman-Wunsch with affine gaps
Vì sao cần 3 ma trận F, G, H?
Vì:
•G(i, j)x <i Valigns(i, j) to yj
(best để xalign1 x vớix yi- 1nếu x đangi x i+align1
i j Add -d
chỉ x x với y y và not the rest of x, y),
1 yi 11 yj j-1 yj -
G(i+1, j) = F(i, j) – d
Nhưng ngược lại
•G(i, j)x –i ealigns > V(i, j) –to d a gap after yj
(i.e., hadx we1 “fixed”x ouri-1 decision xi x i+that1 xi aligns
Add -e
to yj, we could regret it at the next step when
aligning xy1x1i+1 to y1j yj) - -
G(i+1, j) = G(i, j) – e
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:
x1 xM F(i,0), F(0,j) không xác định cho i, j > k
N
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)
y
F(i – 1, j) – d, if j < i + k(N)
1
y
k(N) Termination: không thay đổi
Dễ dàng áp dụng cho affine gap
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
Các file đính kèm theo tài liệu này:
- bai_giang_giai_thuat_nang_cao_quy_hoach_dong_cho_bai_toan_se.pdf