#
Trường Đại học Công Nghệ - ĐHQGHN
#
Luận văn tốt nghiệp cao học
2

MỤC LỤC

MỤC LỤC 2
LỜI CẢM ƠN 5
DANH MỤC HÌNH VẼ 6
DANH MỤC BẢNG 7
DANH MỤC TỪ VIẾT TẮT 8
MỞ ĐẦU 9
CHƯƠNG I : GIỚI THIỆU CHUNG 11
1.1 Các khái niệm cơ bản 11
1.1.1 Tin-sinh là gì? 11
1.1.2 DNA(deoxyribonucleic acid) 12
1.1.3 RNA(ribonucleic acid) 13
1.1.4 Protein 14
1.2 Nucleosome 15
1.2.1 Nucleosome là gì? 15
1.2.2 Sự choán chỗ của nucleosome trong chuỗi DNA 18
1.2.3 Histone là gì? 19
1.2.4 Trạng thái thay đổi của Histone. 21
1.3 Mục tiêu của luận văn 23
CHƯƠNG II : MÔ HÌNH CONDITIONAL RANDOM FIELD 24
2.1 Giới thiệu 24
#
Trường Đại học Công Nghệ - ĐHQGHN
#

Luận văn tốt nghiệp cao học
4
4.1 Kết quả 63
4.1.1 Dự đoán sự choán chỗ của nucleosome và sự thay đổi trạng thái của
histone trong chuỗi DNA
63
4.1.2 Tìm các vùng trên chuỗi DNA ảnh hưởng đến mức độ trạng thái khác
nhau của Histone
66
4.2 Thảo luận 69
4.2.1 Dự đoán sự choán chỗ và các trạng thái thay đổi của histone. 69
4.2.2 Phân tích các vùng hữu ích của chuỗi DNA ảnh hưởng đến các tính chất
của histone
70
KẾT LUẬN 71
5.1 Nội dung của luận văn 71
5.1.1 Các kết quả đạt được 71
5.1.2 Một số hạn chế cần khắc phục. 72
5.2 Công việc tiếp theo 72
PUBLICATION 74
TÀI LIỆU THAM KHẢO 75

#
Trường Đại học Công Nghệ - ĐHQGHN
#
Luận văn tốt nghiệp cao học
5
LỜI CẢM ƠN

Vui mừng khi hoàn thành luận văn, tôi không quên công ơn của các thầy cô, bạn bè

6
DANH MỤC HÌNH VẼ

Hình 1 Cấu trúc xoắn kép của DNA 12
Hình 2 Một phân tử tRNA 14
Hình 3 Các dạng cấu trúc của protein 15
Hình 4 Cấu tạo của nucleosome 16
Hình 5 Cấu trúc đóng gói của chuỗi DNA tạo thành một nhiễm sắc thể 17
Hình 6 Các nucleosome liên tiếp nhau được nối bởi linker DNA 18
Hình 7 Cấu tạo của histone octamer 19
Hình 8 Các protein có trong nhân histone 20
Hình 9 Cấu trúc chi tiết của nhân histone 20
Hình 10 Các vị trí trên đuôi của các histone có thể đính thêm các nhóm chức 22
Hình 11 Cấu trúc đồ thị của HMM bậc 1 27
Hình 12 Cấu trúc đồ thị của mô hình MEMM bậc 1. 30
Hình 13 Một ví dụ về vấn đề bias. 31
Hình 14 Cấu trúc đồ thị của CRFs cho trường hợp chuỗi 35
Hình 15 Lược đồ của phương pháp ChIP-chip [21]. 51
Hình 16 Chuyển dữ liệu định lượng về dữ liệu định tính. 56
Hình 17 Tạo dữ liệu có nhãn từ dữ liệu gene của loài Yeast và dữ liệu định tính 57
Hình 18 Biểu diễn dãy DNA dưới dạng vector (với k = 3). 58
Hình 19 Dữ liệu đã có nhãn. Gồm vector biểu diễn chuỗi DNA và nhãn tương ứng

59
#
Trường Đại học Công Nghệ - ĐHQGHN
#
Luận văn tốt nghiệp cao học
7
Hình 20 Biểu diễn gene thành chuỗi quan sát. p

Bảng 7 Kết quả dự đoán khả năng choán chỗ, acetyl hóa, methyl hóa của histone,
với kích thước của cửa sổ k = 4, k = 5 và k = 6
65
Bảng 8 Kết quả dự đoán khả năng choán chỗ, acetyl hóa, methyl hóa của histone,
với kích thước của cửa sổ k = 7; k = 4,5 và k = 5,6
65
Bảng 9 Một số feature hữu ích cho lớp positive được chọn từ mô hình CRFs, trong
trường hợp k = 4 và k = 5. T.số: là trọng số của feature tương ứng sau khi huấn
luyện mô hình CRFs
68
Bảng 10 Một số feature hữu ích cho lớp negative được chọn từ mô hình CRFs,
trong trường hợp k = 4 và k = 5. T.số: là trọng số của feature tương ứng sau khi
huấn luyện mô hình CRFs
69

#
Trường Đại học Công Nghệ - ĐHQGHN
#
Luận văn tốt nghiệp cao học
8
DANH MỤC TỪ VIẾT TẮT

Cụm từ viết tắt Cụm từ chi tiết
KPDL Khai phá dữ liệu
CRFs Conditional Random Fields
HMM Hidden Markov Model
MEMM Maximum Entropy Markov Model
ME Maximum Entropy
SVM Support Vector Machine
#

ệ di
truyền giữa các loài sinh vật hay phát hiện ra chức năng của các đại phân tử trong
sinh học phân tử,…
Trong khi tìm hiểu các bài toán trong lĩnh vực tin-sinh học, chúng tôi đã phát
hiện ra vị trí, cấu tạo và trạng thái của các histone trong chuỗi DNA ảnh hưởng đến
các tiến trình sinh học trong tế bào. Đã có nhiều các nghiên cứu trước đây nghiên
#
Trường Đại học Công Nghệ - ĐHQGHN
#
Luận văn tốt nghiệp cao học
10
cứu vấn đề này, nhưng đều là các nghiên cứu thực nghiệm. Trong luận văn này,
chúng tôi áp dụng một phương pháp tính toán để dự đoán sự choán chỗ của
nucleosome và các trạng thái thay đổi của nó trong chuỗi DNA. Chúng tôi đã sử
dụng mô hình Conditional Random Fields (CRFs), một mô hình xác suất điều kiện
được đánh giá là hiệu quả trong nhiều lĩnh vực khác nhau. Ngoài ra, dựa vào mô
hình này, chúng tôi còn phân tích được nhiều đặc trưng quan trọng của chuỗi DNA
liên quan đến các d
ấu hiệu của quá trình thể hiện gene.
Ngoài phần mở đầu và kết luận, luận văn được chia làm 4 chương, cụ thể nội
dung các chương như sau:
Chương I trình bày các khái niệm chung của sinh học phân tử. Giải thích cấu tạo cơ
bản và chức năng của các đại phân tử sinh học. Mục đích của chương này nhằm làm
rõ các khái kiệm liên quan đến bài toán mà luận văn đề cập.
Chương II
giới thiệu mô hình CRFs đối với bài toán phân đoạn và gán nhãn. Trước
khi trình bày định nghĩa và cấu tạo của mô hình CRFs chúng tôi đã trình bày ngắn
gọn về các mô hình trước đó như mô hình Markov ẩn (HMM), mô hình Maximum
Entropy Markov (MEMM) và hạn chế của các mô hình này.
Chương III áp dụng mô hình CRFs vào bài toán dự đoán sự choán chỗ của

Các đại phân tử sinh học là protein, nucleic acid, lipid và polysaccaride, trong
đó quan trọng hơn cả là nucleic acid lưu trữ thông tin di truyền và protein - biểu
hiện củ
a vật chất sống. Protein được hình thành từ 20 loại amino acid, có cấu trúc
không gian đặc trưng. Chức năng của protein rất đa dạng: tham gia vào cấu tạo tế
bào, xúc tác các phản ứng chuyển hóa, nhận biết các phân tử lạ, tham gia vào các
quá trình sống như actin và myosin trong sự vận động cơ. Nucleic acid được hình
thành từ 4 loại nucleotide (adenine, thymine, cytosine, và guanine) và gồm hai loại:
DNA và RNA. Phân tử DNA là một chuối xoắn kép do sự kết hợp của hai mạch bổ
sung. RNA là mộ
t phân tử mạch đơn, gồm ba loại: mRNA mang thông tin mã hóa
cho protein, rRNA là một thành phần của ribosome và tRNA tham gia vào quá trình
dịch mã. Trong phần này chúng tôi giới thiệu tổng quan về một số đối tượng nghiên
cứu của tin-sinh.
#
Trường Đại học Công Nghệ - ĐHQGHN
#
Luận văn tốt nghiệp cao học
12
1.1.2 DNA(deoxyribonucleic acid)
Phân tử DNA là một chuỗi xoắn kép gồm hai mạch đơn, mỗi mạch đơn là một
chuỗi nucleotide. Mỗi nucleotide gồm có nhóm phosphate, đường desoxyribose và
một trong bốn base (adenine - A, cytosine - C, guanine - G và thymine - T). Hai
mạch đơn kết hợp với nhau nhờ các liên kết hydro hình thành giữa các base bổ sung
nằm trên hai mạch. A bổ sung cho T và C bổ sung cho G. Mỗi mạch đơn là một
trình tự có định hướng với một đầu là 5’phosphate tự do, đầu kia là đầu 3’hydroxyl
tự do (hướng quy ước là 5’->3’). Hướ
ng mạch đơn của hai chuỗi xoắn kép là ngược
nhau, người ta gọi chúng là hai mạch đối song song. Mỗi mạch đơn có một trình tự
những base khác nhau, như vậy mỗi mạch đơn mang thông tin khác với mạch kia.

dù ở dạng nào thì các DNA đều ở
dạng cuộn chặt. DNA của eucaryote có kích
thước rất lớn (ví dụ: ở người DNA có thể dài đến 1m) mà DNA lại nằm trong nhân
của tế bào với kích thước rất nhỏ, nên các chuỗi DNA được nén với nhiều mức độ
khác nhau, mức độ thấp nhất là nucleosome và mức độ cao nhất là nhiễm sắc chất
(chromatin).
1.1.3 RNA(ribonucleic acid)
Phân tử RNA có cấu trúc giống với DNA nhưng có một số điểm khác biệt so
với DNA. Phân tử RNA luôn là chuỗi đơn, vẫn có 4 loại base như DNA nhưng T
được thay thế bằng U (uracil). Trong tế bào có 3 loại RNA chính, với các vai trò
khác nhau.
RNA thông tin (mRNA) là bản sao của những trình tự nhất định trên phân tử
DNA đóng vai trò trung gian chuyển thông tin mã hóa trên phân tử DNA đến bộ
máy giải mã thành phân tử protein tương ứng. Các mRNA có cấu trúc đa dạng, kích
thước nhỏ hơn so với DNA vì ch
ỉ chứa thông tin mã hóa cho một hoặc vài protein,
mRNA chiếm khoảng 2-5% tổng số RNA trong tế bào.
RNA vận chuyển (tRNA) đóng vai trò vận chuyển các amino acid cần thiết
đến bộ máy dịch mã để tổng hợp protein từ mRNA tương ứng. Các tRNA có cấu
trúc ổn định nhờ các liên kết bổ sung có ở nhiều vùng của phân tử tRNA. Hai vị trí
không có liên kết bổ sung đóng vai trò đặc biệt quan trọng đối với chức năng của
tRNA. Một là tình t
ự anticodon gồm 3 nucleotide bổ sung cho codon (tức bộ ba
#
Trường Đại học Công Nghệ - ĐHQGHN
#
Luận văn tốt nghiệp cao học
14
nucleotide mã hóa trên mRNA). Hai là trình tự CCA có khả năng nối cộng hóa trị
với một amino acid đặc trưng (hình 2).

#
Luận văn tốt nghiệp cao học
15
gian. Cấu trúc bậc 4 (quarternary protein structure): là sự tổ chức nhiều chuỗi
polypeptide thành một phân tử protein.
Protein có vai trò rất lớn đối với cơ thể sống. Nó tham gia vào hầu hết các quá
trình sinh học. Protein đóng vai trò là các enzyme làm chất xúc tác trong hầu hết các
phản ứng hóa học trong hệ thống sống, nhận biết các lọai phân tử khác nhau, chịu
trách nhiệm về sự vận động của động vật ở mức tế bào và cơ thể.

1.2 Nucleosome
1.2.1 Nucleosome là gì?
DNA trong nhân tế bào của các loài eucaryote được chia vào trong một tập
hợp gồm các nhiễm sắc thể (chromosome) khác nhau. Chẳng hạn ở người có 23 cặp
nhiễm sắc thể. Mỗi nhiễm sắc thể bao gồm một sợi DNA rất dài kết hợp với một số
protein rồi cuộn tròn và đóng gói lại thành một cấu trúc phức hợp gọi là nhiễm sắc
chất, tập hợp các nhiễm sắc chất này liên k
ết lại với nhau theo một trình tự tạo thành
một nhiễm sắc thể.
Hình 3 Các dạng cấu trúc của
protein. Cấu trúc không gian của
protein rất phức tạp, việc tìm ra
cấu trúc không gian của protein
là một vấn đề khó và nhiều thách
thức. Từ cấu trúc không gian của
protein có thể cho chúng ta biết
về chức năng của nó trong các
tiến trình sinh học.

#

Đường kính của nucleosome là
khoảng 11nm.
#
Trường Đại học Công Nghệ - ĐHQGHN
#
Luận văn tốt nghiệp cao học
17
nucleosome. Hình ảnh về mức thấp hơn được phóng đại bằng cách trích một tiểu
đơn vị trong mức cao.
Như vậy, nucleosome gồm có hai thành phần chính là một nhân gồm 8 protein
gọi là histone octamer và một đoạn ngắn chuỗi xoắn kép DNA bao quanh (Hình 6).
Các nucleosome liên tiếp nhau được liên kết bởi các đoạn DNA (gọi là linker
DNA). Như vậy nếu coi nhiễm sắc thể bao gồm tập hợp các nucleosome liên kết với
nhau thì mỗi nucleosome có khoảng 200 cặp nucleotide.

Hình 5 Cấu trúc đóng gói của
chuỗi DNA tạo thành một nhiễm
sắc thể. Mức 1: chuỗi xoắn kép
DNA. Mức 2: chuỗi DNA quấn
quanh nhân histone tạo thành
nucleosome. Mức 3: chuỗi liên
tiếp các nucleosome tạo thành
nhiễm sắc chất. Mức 4: các đơn
vị nhiễm sắc chất quấn lại theo
cùng một khuôn dạng để tạo
thành nhiễm sắc thể.
#
Trường Đại học Công Nghệ - ĐHQGHN
#
Luận văn tốt nghiệp cao học

1.2.3 Histone là gì?
Trong phần trước chúng ta đã nhắc đến khái niệm histone khi nói về cấu tạo
của nucleosome. Trong phần này chúng ta sẽ tìm hiểu về cấu tạo và vai trò của nó
đối với các tiến trình sinh học. Histone là một tập hợp gồm các protein kiềm nhỏ
cùng một họ hàng và có thứ tự amino acid rất bảo thủ [
2]. Trong cấu trúc của
nucleosome gồm có hai loại histone. Một là nhân gồm 8 protein tạo thành histone
octamer và một protein giàu Lys (histone H1) gắn vào sợi DNA. Việc gắn H1 vào
sợi DNA phụ thuộc vào tích điện âm mạnh của nucleic acid và tích điện dương của
protein. Tuy nhiên trong luận văn này chúng tôi tập trung vào tìm hiểu histone
octamer. Từ đây về sau nói đến histone sẽ ngầm hiểu là histone octamer. Hình 7 chỉ
ra cấu tạo của histone octamer.

Mỗi nhân histone bao gồm 8 phân tử protein của 4 loại histone H2A, histone
H2B, histone H3 và histone H4, mỗi loại có 2 phân tử. Cả 4 loại protein tạo nên
nhân histone đều là các protein loại nhỏ chỉ gồm khoảng từ 102-135 amino acid,
giàu lysin và arginine, và có chung một khuôn dạng (motif) cấu trúc (hình 8) [
3].
Hình 7 Cấu tạo của histone
octamer.
Gồm 8 protein, 2 H2A,
2 H2B, 2 H3 và 2 H4.

#
Trường Đại học Công Nghệ - ĐHQGHN
#
Luận văn tốt nghiệp cao học
20
Trường Đại học Công Nghệ - ĐHQGHN
#
Luận văn tốt nghiệp cao học
21
Mối quan hệ giữa DNA và nhân histone rất chặt chẽ, có khoảng 142 liên kết
hydro hình thành giữa DNA và nhân histone trong mỗi nucleosome. Gần một nửa
số đó là liên kết giữa amino acid của histone và nucleotide của DNA. Các liên kết
này giữ cho DNA và nhân histone tạo thành nucleosome.
Một điểm đặc biệt là các protein có trong nhân histone đều chia làm hai phần,
phía đầu N tương đối dài và được thò ra ngoài nhân histone (tạm gọi là các đuôi của
histone) và phần còn lại (đầu C) được đóng gói trong nhân histone (hình 9). Các
đuôi của histone có vai trò quan trọng đối với c
ấu trúc của histone, vì đây là đối
tượng dễ bị thay đổi khi có các nhóm chức khác “đính” thêm vào các amino acid, sự
biến đổi này có thể là acetyl hóa, methyl hóa hoặc phosphory hóa. Trong phần sau
chúng ta sẽ thảo luận chi tiết hơn vì đây là các đối tượng nghiên cứu chính của luận
văn.
1.2.4 Trạng thái thay đổi của Histone.
Trong các nghiên cứu gần đây người ta phát hiện ra rằng: trạng thái thay đổi
của histone (histone modification) có vai trò quan trọng đối với quá trình điều chỉnh
và sao chép gene [
4,5,6,14,15,17,27]. Sự thay đổi trạng thái của histone xảy ra trên
các phần đuôi thò ra ngoài của các histone H3, H4, H2A, H2B khi có thêm một
hoặc nhiều nhóm chức đính thêm (hoặc rời đi) vào các amino acid. Việc đính thêm
(rời đi) được thực hiện bởi các enzim có trong nhân tế bào. Chẳng hạn nhóm acetyl
được đính thêm vào các vị trí có amino acid lysine bởi enzim có tên là histone
acetyl transferaza (HATs). Cho đến nay người ta phát hiện ra bốn loại nhóm chức
làm thay đổi trạng thái của histone là acetyl, methyl, phosphoryl, ubiquitin và
sumoyl. Tuy nhiên, các nhóm này chỉ tác động đến một số loại amino acid, nh
ư

Hình 10 Các vị trí trên đuôi
của các histone có thể đính
thêm các nhóm chức.
Ac = nhóm
Acetyl, Me = nhóm Methyl, P = nhóm
Phosphotyl, u = nhóm ubiquitin. Ac:
H2BK5, H2BK12, H2BK15, H2BK20,
H3K9, H3K14,…Me: H3K9
, H3K27,
H4K20. P: H3S10, H3S28, H4S1. u:
H2BK120.
#
Trường Đại học Công Nghệ - ĐHQGHN
#
Luận văn tốt nghiệp cao học
23
1.3 Mục tiêu của luận văn
Trong luận văn này, chúng tôi sẽ áp dụng phương pháp tính toán vào bài toán
dự đoán sự choán chỗ và trạng thái thay đổi của histone trong chuỗi DNA. Có khá
nhiều các nghiên cứu trước đây nghiên cứu vấn đề này [
4,6,7,11,14,17,18,27].
Nhưng hầu như các nghiên cứu này đều là nghiên cứu thực nghiệm, và kết quả của
các nghiên cứu nhiều khi chưa đồng nhất [
27]. Nghiên cứu của chúng tôi sẽ dựa trên
dữ liệu thực nghiệm của nhóm Pokholok et al.[
27]. Công trình của nhóm này được
công bố trên tạp chí Cell ngày 26/08/2005.
Từ dữ liệu định lượng của nhóm Pokholok et al. chúng tôi sẽ chuyển về dạng
dữ liệu định tính, và phát biểu bài toán dưới dạng bài toán gán nhãn cho các đối
tượng, sau đó áp dụng các mô hình tính toán vào việc dự đoán.

Bài toán phân đoạn (segmenting) và gán nhãn (labeling) cho các chuỗi dữ liệu
là một bài toán xuất hiện trong nhiều lĩnh vực, bao gồm tin-sinh học, xử lý ngôn
ngữ, xử lý tiếng nói, vv.
Mô hình Markov ẩn (Hidden Markov Model-HMM)[
28] được dùng rộng rãi
và thành công trong loại bài toán này. HMM thuộc lớp mô hình generative, mô hình
này sử dụng một xác suất liên kết (joint probability) p(x,y) để ghép đôi một chuỗi
quan sát (observation sequence) và một chuỗi nhãn (label sequence). Để định nghĩa
được một xác suất liên kết thì các mô hình generative phải liệt kê (enumrate) toàn
bộ các khả năng có thể của chuỗi quan sát. Nhưng trong thực tế thì đây là một bài
toán khó trong hầu hết các lĩnh vực trừ phi các phần tử quan sát được biểu diễn nh
ư
các đơn vị riêng rẽ, độc lập (independent) giữa các phần tử trong cùng một tập,
nhưng trong thực tế thì hầu hết các chuỗi quan sát đều tồn tại trong một mối quan hệ
giữa các phần tử hoặc là phụ thuộc long-range giữa các phần tử trong chuỗi quan
sát.
Vấn đề biểu diễn dữ liệu cũng là một trong những vấn đề cơ bản khi gán nhãn
chuỗi dữ
liệu. Ngoài việc yêu cầu mô hình dễ dàng suy luận chúng ta rất cần một
mô hình mà không có các ràng buộc về tính độc lập của dữ liệu. Có một cách thỏa
#
Trường Đại học Công Nghệ - ĐHQGHN
#
Luận văn tốt nghiệp cao học
25
mãn cả hai điều kiện trên là sử dụng một mô hình được định nghĩa bằng xác suất
điều kiện (conditional probability) trên một chuỗi nhãn và một chuỗi quan sát đã
cho. Mô hình xác suất điều kiện được sử dụng để gán nhãn cho một chuỗi x bằng
cách chọn chuỗi nhãn y sao cho thu được cực đại xác suất điều kiện p(y|x).
Một số mô hình xác suất điều kiệ

#
Luận văn tốt nghiệp cao học
26
2.2 Mô hình Markov ẩn
2.2.1 Giới thiệu
Mô hình Markov ẩn đã được áp dụng thành công trong nhiều bài toán gán
nhãn như phân tích từ vựng, nhận dạng tiếng nói và phân tích chuỗi gene
[
16,28,33]. HMM là một mô hình xác suất hữu hạn trạng thái theo kiểu phát sinh
tiến trình bằng cách định nghĩa xác suất liên kết trên các chuỗi quan sát và chuỗi
nhãn. Mỗi chuỗi nhãn coi như được sinh ra (generated) bởi một chuỗi các phép
chuyển trạng thái, bắt đầu từ trạng thái khởi đầu cho đến khi thu được trạng thái kết
thúc. Tại mỗi trạng thái thì một phần tử của chuỗi quan sát được coi như phát sinh
ngẫu nhiên trước khi chuyển sang trạng thái tiế
p theo. Các trạng thái của HMM
được coi như là ẩn bên trong mô hình vì tại mỗi thời điểm chúng ta chỉ nhìn thấy
các kí hiệu quan sát còn các trạng thái cũng như sự chuyển đổi trạng thái được vận
hành ẩn bên trong mô hình.
Định nghĩa HMM đầy đủ bao gồm các thành phần sau:
 Tập hữu hạn trạng thái S.
 Tập hữu hạn kí hiệu ra X.
 P(s’|s) – Phân bố xác suất chuyền từ trạ
ng thái s đến trạng thái s’. Trong đó
s, s’
∈
S.
 P(x|s) – Phân bố xác suất phát sinh kí hiệu x khi mô hình đang ở trạng thái s.
Trong đó x
∈
X, s