Bài giảng Tin sinh học đại cương - Chương 3: Bắt cặp trình tự (Sequence Alignment) - Trần Văn Lăng

Y OF SCIENCE AND TECHNOLOGY 62 
C A T G T
0 -2 -4 -6 -8 -10
A -2 -1 0 -2 -4 -6 
C -4 0 -2 -1 -3 -5
G -6 -2 
C -8 
T -10
G -12 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 63 
C A T G T
0 -2 -4 -6 -8 -10
A -2 -1 0 -2 -4 -6 
C -4 0 -2 -1 -3 -5
G -6 -2 -1 
C -8 
T -10
G -12 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 64 
C A T G T
0 -2 -4 -6 -8 -10
A -2 -1 0 -2 -4 -6 
C -4 0 -2 -1 -3 -5
G -6 -2 -1 -3 
C -8 
T -10
G -12 
17 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 65 
C A T G T
0 -2 -4 -6 -8 -10
A -2 -1 0 -2 -4 -6 
C -4 0 -2 -1 -3 -5
G -6 -2 -1 -3 1 
C -8 
T -10
G -12 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 66 
C A T G T
0 -2 -4 -6 -8 -10
A -2 -1 0 -2 -4 -6 
C -4 0 -2 -1 -3 -5
G -6 -2 -1 -3 1 -1
C -8 
T -10
G -12 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 67 
C A T G T
0 -2 -4 -6 -8 -10
A -2 -1 0 -2 -4 -6 
C -4 0 -2 -1 -3 -5
G -6 -2 -1 -3 1 -1
C -8 -4 
T -10
G -12 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 68 
C A T G T
0 -2 -4 -6 -8 -10
A -2 -1 0 -2 -4 -6 
C -4 0 -2 -1 -3 -5
G -6 -2 -1 -3 1 -1
C -8 -4 -3 
T -10
G -12 
18 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 69 
C A T G T
0 -2 -4 -6 -8 -10
A -2 -1 0 -2 -4 -6 
C -4 0 -2 -1 -3 -5
G -6 -2 -1 -3 1 -1
C -8 -4 -3 -2
T -10
G -12 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 70 
C A T G T
0 -2 -4 -6 -8 -10
A -2 -1 0 -2 -4 -6 
C -4 0 -2 -1 -3 -5
G -6 -2 -1 -3 1 -1
C -8 -4 -3 -2 -1
T -10
G -12 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 71 
C A T G T
0 -2 -4 -6 -8 -10
A -2 -1 0 -2 -4 -6 
C -4 0 -2 -1 -3 -5
G -6 -2 -1 -3 1 -1
C -8 -4 -3 -2 -1 0
T -10
G -12 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 72 
C A T G T
0 -2 -4 -6 -8 -10
A -2 -1 0 -2 -4 -6 
C -4 0 -2 -1 -3 -5
G -6 -2 -1 -3 1 -1
C -8 -4 -3 -2 -1 0
T -10 -6
G -12 
19 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 73 
C A T G T
0 -2 -4 -6 -8 -10
A -2 -1 0 -2 -4 -6 
C -4 0 -2 -1 -3 -5
G -6 -2 -1 -3 1 -1
C -8 -4 -3 -2 -1 0
T -10 -6 -5
G -12 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 74 
C A T G T
0 -2 -4 -6 -8 -10
A -2 -1 0 -2 -4 -6 
C -4 0 -2 -1 -3 -5
G -6 -2 -1 -3 1 -1
C -8 -4 -3 -2 -1 0
T -10 -6 -5 -1
G -12 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 75 
C A T G T
0 -2 -4 -6 -8 -10
A -2 -1 0 -2 -4 -6 
C -4 0 -2 -1 -3 -5
G -6 -2 -1 -3 1 -1
C -8 -4 -3 -2 -1 0
T -10 -6 -5 -1 -3
G -12 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 76 
C A T G T
0 -2 -4 -6 -8 -10
A -2 -1 0 -2 -4 -6 
C -4 0 -2 -1 -3 -5
G -6 -2 -1 -3 1 -1
C -8 -4 -3 -2 -1 0
T -10 -6 -5 -1 -3 1
G -12 
20 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 77 
C A T G T
0 -2 -4 -6 -8 -10
A -2 -1 0 -2 -4 -6 
C -4 0 -2 -1 -3 -5
G -6 -2 -1 -3 1 -1
C -8 -4 -3 -2 -1 0
T -10 -6 -5 -1 -3 1
G -12 -8 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 78 
C A T G T
0 -2 -4 -6 -8 -10
A -2 -1 0 -2 -4 -6 
C -4 0 -2 -1 -3 -5
G -6 -2 -1 -3 1 -1
C -8 -4 -3 -2 -1 0
T -10 -6 -5 -1 -3 1
G -12 -8 -7 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 79 
C A T G T
0 -2 -4 -6 -8 -10
A -2 -1 0 -2 -4 -6 
C -4 0 -2 -1 -3 -5
G -6 -2 -1 -3 1 -1
C -8 -4 -3 -2 -1 0
T -10 -6 -5 -1 -3 1
G -12 -8 -7 -3 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 80 
C A T G T
0 -2 -4 -6 -8 -10
A -2 -1 0 -2 -4 -6 
C -4 0 -2 -1 -3 -5
G -6 -2 -1 -3 1 -1
C -8 -4 -3 -2 -1 0
T -10 -6 -5 -1 -3 1
G -12 -8 -7 -3 1 
21 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 81 
C A T G T
0 -2 -4 -6 -8 -10
A -2 -1 0 -2 -4 -6 
C -4 0 -2 -1 -3 -5
G -6 -2 -1 -3 1 -1
C -8 -4 -3 -2 -1 0
T -10 -6 -5 -1 -3 1
G -12 -8 -7 -3 1 -1 
•  Bước 2: Tìm vết dựa trên kết quả tính các giá trị 
của ma trận trước đó. Xuất phát từ Mnm nếu: 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 82 
− Mi−1, j−1 =Mij −σ ij , theo duong chéo, (i,j)→ (i-1,j-1)
− Mi−1, j =Mij −d , dich chuyen lên trên, (i,j)→ (i-1,j)
− Mi , j−1 =Mij −d , dich chuyen lui, (i,j)→ (i,j-1)
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 83 
C A T G T
0 -2 -4 -6 -8 -10
A -2 -1 0 -2 -4 -6 
C -4 0 -2 -1 -3 -5
G -6 -2 -1 -3 1 -1
C -8 -4 -3 -2 -1 0
T -10 -6 -5 -1 -3 1
G -12 -8 -7 -3 1 -1 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 84 
C A T G T
0 -2 -4 -6 -8 -10
A -2 -1 0 -2 -4 -6 
C -4 0 -2 -1 -3 -5
G -6 -2 -1 -3 1 -1
C -8 -4 -3 -2 -1 0
T -10 -6 -5 -1 -3 1
G -12 -8 -7 -3 1 -1 
22 
•  Bước 3: Bắt cặp trình tự 
–  Xuất phát từ phần tử Mnm 
–  Nếu phần tử kế nằm trên đường chéo: hai ký tự được 
bắt cặp với nhau 
–  Nếu phần tử kế nằm bên trái: thêm gap cho trình tự 
thứ hai (ở dưới) 
–  Ngược lại, nếu phần tử kế nằm ở trên: thêm gap cho 
trình tự thứ nhất 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 85 
-CA-TGT
ACGCTG-
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 86 
C A T G T
0 -2 -4 -6 -8 -10
A -2 -1 0 -2 -4 -6 
C -4 0 -2 -1 -3 -5
G -6 -2 -1 -3 1 -1
C -8 -4 -3 -2 -1 0
T -10 -6 -5 -1 -3 1
G -12 -8 -7 -3 1 -1 
•  Điểm đánh giá = 3x2 + 1x(-1) + 3(-2) = -1 
CATG-T-
-ACGCTG
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 87 
C A T G T
0 -2 -4 -6 -8 -10
A -2 -1 0 -2 -4 -6 
C -4 0 -2 -1 -3 -5
G -6 -2 -1 -3 1 -1
C -8 -4 -3 -2 -1 0
T -10 -6 -5 -1 -3 1
G -12 -8 -7 -3 1 -1 
•  Điểm: 3x2 + 1(-1) + 3(-2) = -1 
Xem xét ví dụ khác 
•  Xét 2 trình tự peptide như sau: 
–  U = AlaCysGlyCysAspGly 
–  V = CysAlaAspGlyAsp 
•  Gồm các amino acid: Alanin (A), Cystein (C), 
Glycine (G), Aspartic acid (D) 
PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM 
23 
•  Có thể biểu diễn 
–  U = “ACGCDG” 
–  V = “CADGD” 
PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM 
•  Tạo ma trận đánh giá theo quy tắc: 
–  M00 = 0 
–  Mi0 = Mi-1,0 + d 
–  M0j = M0,j-1 + d 
–  Mij = Max {Mi-1,j-1 + σij, Mi,j-1 + d, Mi-1,j + d} 
–  d = -1 
•  Trong đó 
–  σij = +2 nếu Ui và Vj giống nhau 
–  σij = -1 nếu Ui và Vj khác nhau 
PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM 
C A D G D
0 -1 -2 -3 -4 -5 
A -1 -1 1 0 -1 -2 
C -2 1 0 0 -1 -2 
G -3 0 0 -1 2 1 
C -4 -1 -1 -1 1 1 
D -5 -2 -2 1 0 3 
G -6 -3 -3 0 3 2 
PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM 
•  Tìm vết bằng cách dùng d = -1 và ma trận σ để 
so sánh trên 2 trình tự: 
•  Xuất phát từ M65, nếu: 
–  Mij = Mi-1,j-1 + σij thì vết (i,j) → (i-1,j-1) đi theo đường 
chéo 
–  Mij = Mi,j-1 + d thì vết (i,j) → (i,j-1) đi lui 
–  Mij = Mi-1,j + d thì vết (i,j) → (i-1,j) đi lên 
PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM 
24 
•  Trong trường hợp này, có nhiều vết được tạo ra 
(màu red, blue, green) 
PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM 
C A D G D
0 -1 -2 -3 -4 -5 
A -1 -1 1 0 -1 -2 
C -2 1 0 0 -1 -2 
G -3 0 0 -1 2 1 
C -4 -1 -1 -1 1 1 
D -5 -2 -2 1 0 3 
G -6 -3 -3 0 3 2 
PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM 
C A D G D
0 -1 -2 -3 -4 -5 
A -1 -1 1 0 -1 -2 
C -2 1 0 0 -1 -2 
G -3 0 0 -1 2 1 
C -4 -1 -1 -1 1 1 
D -5 -2 -2 1 0 3 
G -6 -3 -3 0 3 2 
C A D G D
0 -1 -2 -3 -4 -5 
A -1 -1 1 0 -1 -2 
C -2 1 0 0 -1 -2 
G -3 0 0 -1 2 1 
C -4 -1 -1 -1 1 1 
D -5 -2 -2 1 0 3 
G -6 -3 -3 0 3 2 
•  Sử dụng kỹ thuật lưu vết theo quy tắc: 
–  (i,j) →(i-1,j-1): Ui và Vj được ghi vào 
–  (i,j) →(i-1,j): “-” và Vj được ghi và 
–  (i,j) →(i,j-1): Ui và “-” được ghi vào 
PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM 
•  Vết Red: 3(2) + 1(-1) + 3(-1) = 2 
CADG-D-
-ACGCDG
•  Vết Blue: 3(2) + 1(-1) + 3(-1) = 2 
-CA-DGD
ACGCDG-
•  Vết Green: 3(2) + 1(-1) + 3(-1) = 2 
-C-ADGC
ACGCDG-
PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM 
25 
Một ví dụ khác 
•  Cho 2 trình tự DNA: 
GGATCGA
GAATTCAGTTA
PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM 
G A A T T C A G T T A
0 -1 -2 -3 -4 -5 -6 -7 -8 -9 -10 -11 
G -1 2 1 0 -1 -2 -3 -4 -5 -6 -7 -8 
G -2 1 1 0 -1 -2 -3 -4 -2 -3 -4 -5 
A -3 0 3 3 2 1 0 -1 -2 -3 -4 -2 
T -4 -1 2 2 5 4 3 2 1 0 -1 -2 
C -5 -2 1 1 4 4 6 5 4 3 2 1 
G -6 -3 0 0 3 3 5 5 7 6 5 4 
A -7 -4 -1 2 2 2 4 7 6 6 5 7 
•  Bắt cặp 2 trình tự này là: 
GGA-TC-G--A
| | || | |
GAATTCAGTTA
•  Kết quả: 6(2) + 4(-1) + 1(-1) = 7 
PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM 
Bài tập 
•  (P1) Tính toán các giá trị của ma trận với trường 
hợp tương tự, nhưng: 
–  M00 = 0 
–  Mi0 = Mi-1,0 + d 
–  M0j = M0,j-1 + d 
–  d = -2 
•  Rút ra nhận xét 
PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM 
26 
TG Needleman – Wunsch nguyên thủy 
for i=0 to length(U)
M(i,0) ← d*i
for j=0 to length(V)
M(0,j) ← d*j
for i=1 to length(U)
for j=1 to length(V){
Match ← M(i-1,j-1) + σ(i,j)
Delete ← M(i-1,j) + d
Insert ← M(i,j-1) + d
M(i,j) ← max(Match, Insert, Delete)
}
PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM 
 AlignmentU ← ""
 AlignmentV ← ""
 i ← length(U)
 j ← length(V)
 while (i > 0 and j > 0){
 Score ← M(i,j)
 ScoreDiag ← M(i - 1, j - 1)
 ScoreUp ← M(i, j - 1)
 ScoreLeft ← M(i - 1, j)
 if (Score == ScoreDiag + σ(i,j)){
 AlignmentU ← Ui + AlignmentU
 AlignmentV ← Vj + AlignmentV
 i ← i - 1
 j ← j - 1
 }
PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM 
 else if (Score == ScoreLeft + d){
 AlignmentU ← Ui + AlignmentU
 AlignmentV ← "-" + AlignmentV
 i ← i - 1
 }
 otherwise (Score == ScoreUp + d){
 AlignmentU ← "-" + AlignmentU
 AlignmentV ← Vj + AlignmentV
 j ← j - 1
 }
 }
PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM 
 while (i > 0){
 AlignmentU ← Ui + AlignmentU
 AlignmentV ← "-" + AlignmentV
 i ← i - 1
 }
 while (j > 0){
 AlignmentU ← "-" + AlignmentU
 AlignmentV ← Vj + AlignmentV
 j ← j - 1
 }
PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM 
Coi thêm NeedWun.java 
27 
SMITH - WATERMAN 
Thuật toán 
PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM 
•  Do Temple F. Smith và 
Michael S. Waterman đưa ra 
vào 1981 
•  Khác biệt so với thuật toán Needleman – 
Wunsch là chỉ sử dụng để bắt cặp 2 trình tự 
trong một đoạn của trình tự (bắt cặp cục bộ - 
Local Alignment) 
•  Các bước tính toán hoàn toàn tương tự, chỉ khác 
một số bước như sau: 
–  Cách thức tính ma trận: 
Assoc. Prof. Tran Van Lang, PhD, VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY 
H
i0 =0, ∀i=0,n, H0 j =0, ∀j=0,m
H
ij
=max 0,H
i−1,j−1 +σ ij ,Hi−1,j +d,Hi,j−1 +d}{ , 
 ∀i=1,n; j=1,m
 σ
ij
=
match
mismatch
#
$
%
, d=gap
•  Do chỉ bắt cặp cục bộ, nên vết được xác định 
không phải bắt đầu từ giá trị cuối (Hnm), mà từ giá 
trị tốt nhất (điểm cao nhất của ma trận) 
PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM 
28 
Ví dụ 
•  Với U = “ACA”, V = “AGCA”, với d = -1 ta có các 
phần tử của ma trận H như sau: 
PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM 
H11 =max{0,H00 +σ11 ,H01 −1,H10 −1}=max{0,0+2,0−1,0−1}=2
H12 =max{0,H01 +σ12 ,H02 −1,H11 −1}=max{0,0−1,0−1,2−1}=1
H13 =max{0,H02 +σ13 ,H03 −1,H12 −1}=max{0,0+2,0−1,1−1}=2
A C A
0 0 0 0 
A 0 H11 H12 H13 
G 0 H21 H22 H23 
C 0 H31 H32 H33 
A 0 H41 H42 H43 
PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM 
H21 =max{0,H10 +σ 21 ,H11 −1,H20 −1}
 =max{0,0−1,2−1,0−1}=1
H22 =max{0,H11 +σ 22 ,H12 −1,H21 −1}
 =max{0,2−1,1−1,2−1}=1
H23 =max{0,H12 +σ 23 ,H13 −1,H22 −1}
 =max{0,1−1,2−1,1−1}=1
PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM 
H31 =max{0,H20 +σ 31 ,H21 −1,H30 −1}
 =max{0,0−1,1−1,0−1}=0
H32 =max{0,H21 +σ 32 ,H22 −1,H31 −1}
 =max{0,1+2,1−1,0−1}=3
H33 =max{0,H22 +σ 33 ,H23 −1,H32 −1}
 =max{0,1−1,1−1,3−1}=2
PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM 
H41 =max{0,H30 +σ 41 ,H31 −1,H40 −1}
 =max{0,0+2,0−1,0−1}=2
H42 =max{0,H31 +σ 42 ,H32 −1,H41 −1}
 =max{0,0−1,3−1,2−1}=2
H43 =max{0,H32 +σ 43 ,H33 −1,H42 −1}
 =max{0,3+2,2−1,2−1}=5
29 
PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM 
A C A
0 0 0 0 
A 0 2 1 2 
G 0 1 1 1 
C 0 0 3 2 
A 0 2 2 5 
Tạo vết 
•  Xuất phát từ Hnmax,mmax, nếu: 
–  Hij = Hi-1,j-1 + σij thì vết (i,j) → (i-1,j-1) theo đường chéo 
–  Hij = Hi,j-1 + d thì vết (i,j) → (i,j-1) đi lui 
–  Hij = Hi-1,j + d thì vết (i,j) → (i-1,j) đi lên 
PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM 
PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM 
A C A
0 0 0 0 
A 0 2 1 2 
G 0 1 1 1 
C 0 0 3 2 
A 0 2 2 5 
Tìm kết quả 
•  Nếu 
–  (i,j) →(i-1,j-1): theo đường chéo 
Ui và Vj được ghi vào 
–  (i,j) →(i-1,j): đi lên 
“-” và Vj được ghi vào 
–  (i,j) →(i,j-1): đi lui 
Ui và “-” được ghi vào 
PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM 
30 
•  Kết quả bắt cặp 
–  U’ = “A-CA” 
–  V’ = “AGCA” 
•  Độ đánh giá: 3(2) + 1(-1) + 0(-1) = 5 
PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM 
Ví dụ 
•  Với trình tự dài hơn, chẳng hạn: 
U = “ATATGCTAAG” 
V = “ACTACTTAG” 
•  Chọn d = -1, Match = 2 và Mismatch = -1 cho sự 
tương đồng và không tương đồng của 2 phân tử 
trong 2 trình tự. 
PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM 
A T A T G C T A A G
0 0 0 0 0 0 0 0 0 0 0
A 0 2 1 2 1 0 0 0 2 2 1
C 0 1 1 1 1 0 2 1 1 1 1
T 0 0 3 2 3 2 1 4 3 2 1
A 0 2 2 5 4 3 2 3 6 5 4
C 0 1 1 4 4 3 5 4 5 5 4
T 0 0 3 3 6 5 4 7 6 5 4
T 0 0 2 2 5 5 4 6 6 5 4
A 0 2 1 4 4 4 4 5 8 7 7
G 0 1 1 3 3 6 5 4 7 6 10
PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM 
Với kỹ thuật lưu vết như trên 
PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM 
A T A T G C T A A G
0 0 0 0 0 0 0 0 0 0 0
A 0 2 1 2 1 0 0 0 2 2 1
C 0 1 1 1 1 0 2 1 1 1 1
T 0 0 3 2 3 2 1 4 3 2 1
A 0 2 2 5 4 3 2 3 6 5 4
C 0 1 1 4 4 3 5 4 5 5 4
T 0 0 3 3 6 5 4 7 6 5 4
T 0 0 2 2 5 5 4 6 6 5 4
A 0 2 1 4 4 4 4 5 8 8 7
G 0 1 1 3 3 6 5 4 7 7 10
31 
•  Cũng bằng cách ghi kết quả theo vết, 2 trình tự 
được bắt cặp: 
–  U’ = “ACTA--CTAAG” 
–  V’ = “A-TATGCTAAG” 
•  Kết quả: 8(2) + 3(-1) + 0(-1) = 13 
PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM 
Ví dụ 
•  Với 2 trình tự như hình, có thể tính được 
PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM 
•  Kết quả trên ứng với match = 2, mismatch = -3 
và gap = -2 
•  Khi đó, 8 là giá trị lớn nhất, nên bắt đầu từ vị trị 
này để xác định vết. 
•  Từ đó, kết quả bắt cặp cục bộ của 2 đoạn trình 
tự: 
ATCC
ATCC
PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM 
32 
CLUSTAL 
Thuật toán 
PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM 
Thuật toán ClustalW 
•  Dùng cho việc bắt cặp nhiều trình tự (giải 
bài toán MSA) 
•  Lấy ý tưởng từ thuật toán lũy tiến 
(Progessive Algorithm) 
PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM 
•  Thuật toán lũy tiến như sau: 
–  Bước 1: giải bài toán PSA trên 2 trình tự bất kỳ được 
chọn. 
–  Bước 2: chọn một trình tự khác rồi sắp hàng với nhóm 
đã thực hiện. 
–  Bước 3: lặp lại Bước 2 cho trình tự khác 
PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM 
Thuật toán Clustal W 
•  Bước 1: 
–  Dùng PSA cho tất cả các trình tự 
–  Xác định mức độ tương đồng mỗi cặp 
–  Xây dựng ma trận khoảng cách tương đồng giữa các 
trình tự. 
PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM 
33 
•  Bước 2: 
–  Xây dựng cây cây tương đồng (similarity tree) hay cây 
hướng dẫn (guide tree) bằng cách dùng thuật toán 
gom nhóm Neighbor – Joining. 
–  Cây hướng dẫn hể hiện mối quan hệ tương đồng giữa 
các trình tự với nhau 
PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM 
•  Bước 3: Thực hiện quá trình lũy tiến 
–  Căn cứ vào cây hướng dẫn xác định những nhánh có 
cặp trình tự tương đồng lớn nhất 
–  Thực hiện PSA trên từng cặp 
–  Kết hợp những cặp đó lại thu được kết quả đa trình tự. 
PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM 
Minh họa 
•  Xét 5 trình tự: 
–  S1 = “ARDFGI” 
–  S2 = “AKHGL” 
–  S3 = “ADFIKF” 
–  S4 = “ARFGLI” 
–  S5 = “AKDILM” 
PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM 
•  Lần lượt bắt cặp: 
–  S1’ = “ARDFGI” 
–  S2’ = “A-KHGL” 
–  S1’ = “ARDFGI--” 
–  S3’ = “A-DF-IKF” 
–  S1’ = “ARDFG-I” 
–  S4’ = “AR-FGLI” 
–  S1’ = “ARDFGI--” 
–  S5’ = “AKD--ILM” 
PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM 
34 
–  S2’ = “A---KHGL” 
–  S3’ = “ADFIK--F” 
–  S2’ = “AKHGL-” 
–  S4’ = “ARFGLI” 
–  S2’ = “AKHGL-” 
–  S5’ = “AKDILM” 
PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM 
–  S3’ = “ADF--IKF” 
–  S4’ = “ARFGLI--” 
–  S3’ = “A-DFIKF” 
–  S5’ = “AKD-ILM” 
–  S4’ = “ARFGLI” 
–  S5’ = “AKDILM” 
PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM 
•  Khoảng cách D(S1’,S2’) giữa 2 trình tự bằng tỷ số 
giữa m và n. Trong đó 
–  m = số mismatch giữa 2 trình tự (không tính gap) 
–  n = số cặp không phải là gap giữa 2 trình tự 
•  Ví dụ: 
–  S1’ = “ARDFGI” 
–  S2’ = “A-KHGL” 
Có m = 3, n = 5. Suy ra D(S1’,S2’) = 3/5 = 0,6 
PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM 
•  Ví dụ: 
–  S1’ = “ARDFGI--” 
–  S3’ = “A-DF-IKF” 
Có m = 0, n = 4. Suy ra D(S1’,S3’) = 0/4 = 0 
PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM 
35 
•  Ví dụ: 
–  S1’ = “ARDFGI--” 
–  S5’ = “AKD--ILM” 
Có m = 1, n = 4. Suy ra D(S1’,S5’) = 1/4 = 0.25 
PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM 
Ma trận khoảng cách 
S1 S2 S3 S4 S5 
S1 - 
S2 0,60 - 
S3 0 0,33 - 
S4 0 0,40 0,25 - 
S5 0,25 0,60 0,40 0,66 - 
PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM 
•  Theo ma trận khoảng cách, có thể S1 và S3 là 
nhỏ nhất, nên mức độ gần nhau là nhiều nhất. 
•  Hoặc S1 và S4 
PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM 
S13 S2 S4 S5 
S13 
S2 (0,6+0,33)/2 = 
0.465 
S4 (0+0,25)/2 = 
0.125 
0,4 
S5 (0,25+0,4)/2 = 
0.325 
0,6 0,66 
PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM 
36 
•  Tiếp tục, khoảng cách giữa S13 và S4 là nhỏ 
nhất. 
•  Nên S13 và S4 là gần nhau nhất 
PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM 
S13,4 S2 S5 
S13,4 
S2 (0,465+0,4)/2 = 
0,4325 
S5 (0,325+0,66)/2 
= 0,4925 
0,6 
PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM 
•  Tiếp tục, còn S134 và S2 là nhỏ nhất 
PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM 
S134,2 S5 
S134,2 
S5 (0,4925+0,6)/2 = 
0,54625 
PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM 
S1 
S3 
S4 
S2 
S5 
ARDFGI
ADFIKF
ARFGLI
AKHGL
AKDILM
ARDFGI--
A-DF-IKF
ARDFG-I--
A-DF--IKF
AR-FGLI--ARDFG-I--
A-DF--IKF
AR-FGLI--
A-KHGL---
ARDFG-I--
A-DF--IKF
AR-FGLI--
A-KHGL---
AKD---ILM
37 
•  Ở đây kết quả có được bằng cách gióng từng 
cặp: 
–  S1, S3 
–  Lấy kết quả S1 có được để bắt cặp với S4 
–  Tương tự, với S2 
–  Rồi với S5 
PGS.TS. Trần Văn Lăng, VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM