i
..

ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN&TRUYỀN THƠNG

PHẠM THỊ NGA

CÂY QUẢN LÍ ĐOẠN VÀ ỨNG DỤNG

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Thái Ngun - 2015
Số hóa bởi Trung tâm Học liệu – ĐHTN




ii

LỜI CAM ĐOAN
Tôi xin cam đoan luận văn này của tự bản thân tơi tìm hiểu, nghiên cứu.
Các tài liệu tham khảo được trích dẫn và chú thích đầy đủ. Nếu khơng đúng
tơi xin hồn tồn chịu trách nhiệm.
Tác giả luận văn

Phạm Thị Nga

Số hóa bởi Trung tâm Học liệu – ĐHTN

iii

LỜI CẢM ƠN
Lời đầu tiên tôi xin được bày tỏ lòng biết ơn chân thành đến Ban Giám
Hiệu, các thầy giáo, cơ giáo phịng Sau đại học trường Đại học Công Nghệ
Thông Tin & Truyền Thông, các thầy giáo ở Viện Công Nghệ Thông Tin đã
giảng dạy và tạo mọi điều kiện cho tơi học tập, nghiên cứu và hồn thành luận
văn này.
Đặc biệt, tơi xin bày tỏ sự kính trọng và lòng biết ơn sâu sắc đến PGS.
TSKH. Vũ Đình Hịa, người đã tận tình hướng dẫn và giúp đỡ tơi trong suốt
q trình học tập, nghiên cứu và hồn thành luận văn.
Tơi chân thành cảm ơn các thầy cô tổ Tin học, trường Trung học phổ
thông chuyên Lam Sơn, Thanh Hóa, nơi tơi cơng tác đã tạo điều kiện và hỗ
trợ tôi trong suốt thời gian qua.
Tôi cũng xin chân thành cảm ơn người thân, bạn bè đã giúp đỡ và động
viên tôi trong suốt thời gian học tập cũng như trong thời gian thực hiện luận
văn.
Xin chân thành cảm ơn !
Thanh Hóa, ngày 10 tháng 04 năm 2015

Số hóa bởi Trung tâm Học liệu – ĐHTN




iv

MỤC LỤC

Trang
Lời cam đoan ...................................................................................................... i
Lời cảm ơn ....................................................................................................... iii
Mục lục ............................................................................................................. iv
Danh mục các bảng ........................................................................................... v
Danh mục các hình .......................................................................................... vii
Danh mục các kí hiệu, chữ viết tắt ................................................................. viii
MỞ ĐẦU .......................................................................................................... 1
Chƣơng 1. TỔNG QUAN VỀ SINH HỌC PHÂN TỬ, TIN SINH HỌC
VÀ BÀI TỐN TÌM GIAO CÁC ĐOẠN GEN ........................................... 4
1.1. Một số khái niệm cơ bản của sinh học phân tử ...................................... 4
1.1.1. Ở cấp độ tế bào................................................................................ 4
1.1.2. Ở cấp độ phân tử ............................................................................. 7
1.1.3. Phiên mã và dịch mã ..................................................................... 11
1.2. Tổng quan về tin sinh học .................................................................... 12
1.3. Bài tốn tìm giao các đoạn gen ............................................................ 15
Chƣơng 2. ỨNG DỤNG CỦA CÂY QUẢN LÍ ĐOẠN ĐỂ TÌM GIAO
CÁC ĐOẠN GEN .......................................................................................... 17
2.1. Đặc tả bài tốn tìm giao các đoạn gen ................................................. 17
2.2. Thuật tốn tìm kiếm tuần tự ................................................................. 18
2.3. Cây quản lí đoạn................................................................................... 19
2.3.1. Cấu trúc cây quản lí đoạn.............................................................. 22
2.3.2. Các thao tác trên cây quản lí đoạn ................................................ 23
2.4. Thuật tốn tìm giao của các đoạn gen sử dụng cây quản lí đoạn ........ 28
2.4.1. Xây dựng rừng cây quản lí đoạn lưu trữ thơng tin các đoạn gen . 29
2.4.2. Tìm kiếm các đoạn gen giao nhau ................................................ 34
Số hóa bởi Trung tâm Học liệu – ĐHTN





v

Chƣơng 3. MÃ HĨA, THỬ NGHIỆM CHƢƠNG TRÌNH TÌM GIAO
CÁC ĐOẠN GEN .......................................................................................... 36
3.1. Chuẩn bị dữ liệu ................................................................................... 36
3.2. Mã hóa chương trình tìm giao các đoạn gen ........................................ 37
3.2.1. Ngơn ngữ và mơi trường lập trình ................................................ 37
3.2.2. Chức năng cửa sổ truy vấn gen ..................................................... 39
3.2.3. Chức năng tìm giao hai tập các đoạn gen ..................................... 41
3.3. Kiểm thử chương trình ......................................................................... 43
3.3.1. Sử dụng cửa sổ truy vấn tìm giao giữa các đoạn gen của virus
Ebola với hệ gen người ........................................................................... 43
3.3.2. Tìm giao giữa hệ gen người và hệ gen chuột ................................ 44
3.3.3. Tìm giao giữa hệ gen chuột nhắt và hệ gen chuột cống ............... 46
3.4. Đánh giá độ phức tạp và kết quả thực hiện chương trình .................... 48
3.4. Mở rộng hướng nghiên cứu.................................................................. 49
KẾT LUẬN .................................................................................................... 51
TÀI LIỆU THAM KHẢO
PHỤ LỤC

Số hóa bởi Trung tâm Học liệu – ĐHTN




vi

DANH MỤC CÁC BẢNG
Trang

Bảng 3.1. Kết quả kiểm thử cửa sổ truy vấn ................................................... 44
Bảng 3.2. Kết quả kiểm thử tính đúng đắn chương trình tìm giao giữa hai hệ
gen ................................................................................................................... 45
Bảng 3.3. Thời gian (s) trung bình chạy chương trình .................................... 47

Số hóa bởi Trung tâm Học liệu – ĐHTN




vii

DANH MỤC CÁC HÌNH
Trang
Hình 1.1. Xếp bộ nhiễm sắc thể người.............................................................. 5
Hình 1.2. Gen được cấu tạo từ ADN, một nhiễm sắc thể chứa nhiều gen ........ 6
Hình 1.3. Cấu trúc phân tử ADN và ARN ........................................................ 8
Hình 1.4. Học thuyết trung tâm của sinh học phân tử .................................... 12
Hình 2.1. Hình vẽ thể hiện giao của hai tập các đoạn gen .............................. 18
Hình 2.2. Sơ đồ khối mơ tả thuật tốn tìm kiếm tuần tự.................................19
Hình 2.3. Ví dụ về một cây quản lí đoạn ........................................................ 21
Hình 2.4. Ví dụ về cửa sổ truy vấn ................................................................. 22
Hình 2.5. Các bước tìm giao của một đoạn gen với các đoạn gen trong một hệ
gen ................................................................................................................... 28
Hình 2.6. Cấu trúc nút và cây quản lí đoạn lưu thơng tin các đoạn gen của một
nhiễm sắc thể ................................................................................................... 31
Hình 3.1. Giao diện mơ phỏng cách lấy dữ liệu hệ gen người từ UCSC Table
Browser ........................................................................................................... 37
Hình 3.2. Giao diện lựa chọn chức năng ......................................................... 39
Hình 3.3. Giao diện cửa sổ truy vấn gen ......................................................... 39

Hình 3.4. Giao diện hộp thoại chỉ định tệp dữ liệu về đoạn gen .................... 40
Hình 3.5. Giao diện chức năng tìm giao hai tập các đoạn gen ....................... 42
Hình 3.6. Giao diện hộp thoại lưu kết quả các đoạn gen giao nhau vào tệp .. 42

Số hóa bởi Trung tâm Học liệu – ĐHTN




viii

DANH MỤC CÁC KÍ HIỆU, CHỮ VIẾT TẮT
A

adenine
:

ADN

Axit
: deoxyribonucleic

ARN

Axit
: ribonucleic

BED

Browser

:
Extensible Data

C

cytosine
:

G

guanine
:

mARN

messenger
:
ARN

NST

nhiễm
: sắc thể

PTB

Polypyrimidine Tract-Binding protein

rARN


ribosomal
:
ARN

T

thymine,
:
thymidine

tARN

transfer
:
ARN

U

uracil
:

UCSC

University
:
of California Santa Cruz

Số hóa bởi Trung tâm Học liệu – ĐHTN





1

MỞ ĐẦU
1. Lý do chọn đề tài
Từ những năm 2001 trở lại đây, sự tiến bộ về công nghệ và sự phổ cập
của các hệ thống phần mềm tiên tiến đã đưa đến những sự thay đổi cách đào
tạo chuyên gia trong lĩnh vực tin học. Các kiến thức giải thuật được coi là
đỉnh cao trước đây bây giờ đã trở thành “bảng cửu chương” mà ai cũng phải
biết và phải thuộc. Những giải thuật ít dùng và phức tạp thì khơng nhất thiết
phải biết hoặc nhớ vì bất cứ ai và lúc nào cũng có thể tra cứu, tìm kiếm chúng
trên internet khi cần thiết. Thử thách bây giờ là ở chỗ ta có thể tìm ra những
giải pháp hữu hiệu giải quyết một cách có hiệu quả các bài tốn, các vấn đề có
mơ hình tốn học đơn giản nhưng có kích thước lớn hay khơng?
Để đạt được mục đích đó, người lập trình phải tận dụng tối đa khả năng
mà phần cứng và hệ điều hành cung cấp, khai thác tối đa khả năng của công
cụ lập trình, sử dụng linh hoạt các cấu trúc dữ liệu. Trong đó, cây quản lí đoạn
(interval tree) là một cấu trúc dữ liệu quan trọng, có nhiều ứng dụng trong
hình học tính tốn, truy vấn cơ sở dữ liệu và xử lí tín hiệu.
Bên cạnh đó, tin sinh học là một lĩnh vực mới, giải quyết các bài toán
sinh học bằng các phương pháp của khoa học tính tốn với nguồn dữ liệu
khổng lồ. Việc so sánh các bộ dữ liệu đa dạng di truyền là căn bản để hiểu hệ
gen sinh học. Các nhà nghiên cứu phải khám phá nhiều bộ dữ liệu lớn về các
đoạn gen (ví dụ như gen, sắp trình tự) để đặt các kết quả thí nghiệm của họ
trong một bối cảnh rộng hơn và thực hiện những khám phá mới. Mối quan hệ
giữa các tập hợp dữ liệu về gen thường được đo bằng cách xác định các đoạn
giao nhau, nghĩa là, chúng chồng lên nhau và do đó chia sẻ một đoạn gen
chung. Với những tiến bộ trong cơng nghệ sắp trình tự ADN, phương pháp



2

hiệu quả để đo mối quan hệ có ý nghĩa thống kê giữa nhiều bộ tính năng di
truyền là rất quan trọng đối với những phát hiện trong tương lai .
Trong khuôn khổ luận văn thạc sĩ, tôi chọn đề tài nghiên cứu: “Cây quản
lí đoạn và ứng dụng”, nghiên cứu về cấu trúc dữ liệu cây quản lí đoạn và thực
hiện một phương pháp tiếp cận mới, nhanh chóng và linh hoạt để tìm giao
giữa các đoạn gen bằng cách sử dụng cấu trúc dữ liệu này.

2. Đối tƣợng và phạm vi nghiên cứu
Cây quản lí đoạn và ứng dụng để tìm giao các đoạn gen.

3. Những nội dung nghiên cứu chính
Chương 1. Tổng quan về sinh học phân tử, tin sinh học và bài tốn tìm
giao các đoạn gen
Chương này trình bày một số khái niệm cơ bản của sinh học phân tử,
tổng quan về tin sinh học và bài tốn tìm giao của các đoạn gen trong sinh
học.
Chương 2. Ứng dụng của cây quản lí đoạn để tìm giao các đoạn gen
Chương này trình bày cấu trúc và các thao tác trên cấu trúc dữ liệu cây
quản lí đoạn và ứng dụng nó để giải bài tốn tìm giao các đoạn gen.
Chương 3. Mã hóa, thử nghiệm chương trình tìm giao các đoạn gen.

4. Phƣơng pháp nghiên cứu
 Phương pháp nghiên cứu lí thuyết: Tổng hợp tài liệu, suy diễn, quy
nạp, các phương pháp hình thức,...
 Phương pháp thực nghiệm: xử lí thống kê, đối sánh,...
 Phương pháp trao đổi khoa học, tổng hợp các kết quả của các nhà
nghiên cứu liên quan đến lĩnh vực nghiên cứu, lấy ý kiến chuyên gia.



3

5. Ý nghĩa khoa học của đề tài
Đề tài đưa ra một phương pháp nhanh chóng, hiệu quả và linh hoạt để
tìm giao các đoạn gen. Điều này mang ý nghĩa thiết thực trong việc hỗ trợ các
nhà khoa học, những người làm cơng tác nghiên cứu, tìm tịi có một cơng cụ
hữu ích, thuận tiện nhanh chóng tìm ra câu trả lời về số đoạn gen giao nhau,
vị trí giao nhau trên đường đi tìm mối quan hệ giữa các chủng loài, mối quan
hệ giữa các tập hợp gen. Việc giải bài tốn tìm giao các đoạn gen cho ta một
cơng cụ lượng hóa (đo) mối quan hệ có ý nghĩa thống kê giữa các đặc tính di
truyền, giải mã các đầu mối tiến hóa, chẩn đốn cấu trúc và chức năng của các
gen. Từ đó, việc giải bài tốn theo cách thức nhanh chóng, hiệu quả sẽ có
những đóng góp nhất định cho việc phát triển tin sinh học trong tương lai.


4

Chƣơng 1.
TỔNG QUAN VỀ SINH HỌC PHÂN TỬ, TIN SINH HỌC VÀ BÀI
TỐN TÌM GIAO CÁC ĐOẠN GEN
1.1. Một số khái niệm cơ bản của sinh học phân tử
1.1.1. Ở cấp độ tế bào
Mỗi sinh vật đều gồm các tế bào. Có khoảng 6 1013 tế bào trong cơ thể
người (có ước tính khác cho rằng con số này là 100.000 tỉ) [5] với khoảng 320
kiểu khác nhau, chẳng hạn như tế bào não có nhiệm vụ giữ gìn trí nhớ và tri
thức, tế bào tim làm cho tim ta đập nhịp nhàng, tế bào ruột làm ra chất nhầy,
v.v... Những tế bào này có thời gian tồn tại nhất định. Chẳng hạn như tế bào
tinh trùng nam chỉ sống khoảng vài tháng, trong khi đó tế bào trứng của phái

nữ có thể tồn tại đến 50 năm.
Mặc dù khác nhau về chức năng, các tế bào đều có cấu trúc giống nhau:
trong mỗi tế bào đều có một nhân nằm chính giữa chứa tất cả các chỉ thị di
truyền. Những chỉ thị này là chức năng của tế bào, và cũng để phân biệt cá thể
này với cá thể khác.
Hạt nhân tế bào chứa ADN gói trong các cặp nhiễm sắc thể. Nhiễm sắc
thể là thể vật chất di truyền tồn tại trong nhân tế bào bị bắt màu bằng thuốc
nhuộm kiềm tính, có số lượng, hình dạng, kích thước, cấu trúc đặc trưng:
nhiễm sắc thể có khả năng tự nhân đôi, phân li, tổ hợp ổn định qua các thế hệ.
Nhiễm sắc thể khác nhau giữa các sinh vật khác nhau, có thể bao gồm từ
100.000 đến 10.000.000.000 nucleotit trong một chuỗi dài [10] .
Mỗi tế bào người có 46 nhiễm sắc thể, được tổ chức thành 23 cặp, đánh
số từ 1 đến 23, được sắp xếp theo kích thước. Hình 1.1 mơ tả cách xếp bộ
nhiễm sắc thể người.


5

Hình 1.1. Xếp bộ nhiễm sắc thể người
Hay như bộ nhiễm sắc thể của chuột cống là 44 (22 cặp), chuột nhắt là
40 (20 cặp).
Mỗi nhiễm sắc thể được cấu thành bởi một hay một vài phân tử ADN
dài, gọi là một trình tự ADN.
Một gen là một đoạn của ADN với trình tự bazơ đặc trưng - cụ thể, gọi là
mã di truyền để xác định chức năng của tế bào.
Gen có chức năng gửi các tín hiệu hóa học đi đến tất cả các nơi trong cơ
thể. Những tín hiệu này có chứa đầy đủ các thơng tin, các chỉ thị cụ thể cho
các cơ quan trong cơ thể ta phải hoạt động ra sao. Việc tìm hiểu số lượng gen
cũng như cơ cấu tổ chức của gen trong cơ thể con người là một điều tất yếu để
mang lại những tiến bộ mới và quan trọng của y sinh học. Nhưng khơng phải

gen nào cũng có chức năng rõ ràng. Trong thực tế, có khoảng 47% gen chẳng
có chức năng gì cụ thể (hay chúng ta chưa biết chức năng của chúng).


6

Hình 1.2. Gen được cấu tạo từ ADN, một nhiễm sắc thể chứa nhiều gen
Một hệ gen hay bộ gen là tập hợp toàn bộ ADN của cơ thể, bao gồm tất
cả các gen của cơ thể đó. Mỗi bộ gen chứa tất cả thông tin cần để xây dựng và
duy trì cơ thể đó. Ở người, một bản sao của tồn bộ hệ gen, có hơn 3 nghìn tỉ
cặp bazơ, được chứa trong nhân tế bào.
Năm 2003, các nhà khoa học đã hoàn thiện việc giải mã bộ gen người.
Mỗi chúng ta đều có khoảng 30.000 gen trong cơ thể. Chẳng hạn như chúng
ta đều mang trong người những gen như VDR, COLIA1, apoE4, v.v... Nhưng
cái khác biệt giữa hai người là biến thể gen, chứ không phải gen. Gen thực ra
chỉ là một thực thể với một cái tên, hay nói theo ngơn ngữ tốn, là một biến
số. Chẳng hạn như chiều cao, giới tính, v.v... là những biến số. Mỗi biến số có
nhiều giá trị: chiều cao của người này là 158cm, của nhiều người khác có thể
cao hơn hay thấp hơn. Mỗi biến thể gen được cấu tạo từ hai thành tố: một
thành tố được nhận từ cha, và một từ mẹ. Chẳng hạn như gen VDR có hai
thành tố T và G, và do đó có 3 biến thể: TT, TG và GG. Người này có biến
thể TG, người khác có thể mang trong người biến thể TT,v.v.
Các nghiên cứu gần đây cho thấy, sự chồng chéo gen là mối quan hệ phổ
biến ở virus, vi khuẩn và khá hiếm ở sinh vật nhân chuẩn. Có một số báo cáo
mơ tả chồng chéo gen trong động vật có vú, sinh vật có xương sống, một số


7

nghiên cứu đã minh họa sự chồng chéo gen khác nhau theo các mảnh và có sự

phân bố khác nhau trong lịch sử tiến hóa [8].
1.1.2. Ở cấp độ phân tử
Trong các tế bào sống có ba loại phân tử quan trọng nhất là: ADN, ARN
và protein.
ADN, ARN là hai loại của phân tử axit nucleic. Chúng đều được tạo
thành từ các nucleotides.
ADN là chuỗi xoắn kép gồm 2 mạch đơn, mỗi mạch đơn là một chuỗi
nucleotide. Chuỗi nucleotide của ADN bao gồm: phosphate, đường
desoxyribose và một trong 4 bazơ hữu cơ A, C, G, T. Các nucleotide trong
một mạch đơn liên kết với nhau bằng liên kết cộng hóa trị, là liên kết được
hình thành giữa các nguyên tử bằng một hay nhiều cặp electron chung. Liên
kết cộng hoá trị là liên kết rất bền đảm bảo cho thông tin di truyền trên mỗi
mạch đơn ổn định kể cả khi ADN tái bản và phiên mã. Hai mạch đơn liên kết
với nhau bằng liên kết hydro hình thành giữa các bazơ, là tương tác tĩnh điện
yếu giữa phần tử hydro mang điện tích dương với phần tử mang điện tích
âm. Trong hai mạch đơn liên kết với nhau thì các bazơ liên kết với nhau theo
nguyên tắc bổ sung: G của mạch này liên kết với C của mạch kia, A của
mạch này liên kết với T của mạch kia, nên A-T và C-G là các cặp bazơ (bp)
trong trình tự ADN. Có khoảng 3 tỷ cặp A-T, G-C cho một phân tử ADN.


8

Hình 1.3. Cấu trúc phân tử ADN và ARN
ARN được sinh ra trong tế bào từ thông tin của một đoạn ADN. Nó là
một đa phân tử được cấu tạo từ nhiều đơn phân, mỗi đơn phân là một
nucleotide gồm 3 thành phần: phosphate, đường ribose, và một trong bốn
bazơ hữu cơ A, U, G, C. ARN có cấu trúc mạch đơn. Trên phân tử ARN các
nucleotide liên kết với nhau bằng liên kết cộng hoá trị giữa đường ribose của
nucleotide này với phân tử phosphate của nucleotide kế tiếp, tạo nên một

chuỗi poly-nucleotide. Có 3 loại ARN chính là: mARN, rARN, tARN. Trong
đó:
 mARN là ARN thơng tin, chiếm 5-10%, sao chép đúng một đoạn
mạch ADN theo nguyên tắc bổ sung nhưng A thay cho T tạo thành
cặp A-U, G-C. Nó đóng vai trị là bản phiên thơng tin di truyền từ gen
cấu trúc, trực tiếp tham gia tổng hợp protein dựa trên cấu trúc và trình
tự các bộ ba trên mARN.


9

 rARN chiếm 70-80%, là thành phần cấu tạo nên ribose, liên kết với
các phân tử protein tạo trên các ribose tiếp xúc với mARN và chuyển
dịch từng bước trên mARN, mỗi bước là một bộ ba nhờ đó mà lắp ráp
chính xác các axit amin vào chuỗi polipeptide theo đúng thông tin di
truyền được quy định từ gen cấu trúc.
 tARN chiếm 10-20%, có chức năng vận chuyển, lắp ráp chính xác các
axit amin vào chuỗi polipeptide dựa trên nguyên tắc đối mã di truyền
giữa bộ ba đối mã trên tARN với bộ ba phiên mã trên mARN. Nó là
một mạch poly-nucleotide nhưng cuộn lại một đầu, ở một đầu của
tARN có bộ ba đối mã gồm 3 nucleotide đặc hiệu đối diện với axit
amin mà nó vận chuyển, đầu đối diện có vị trí gắn axit amin đặc hiệu.
Virus cúm là một loại ARN virus, là nguyên nhân gây ra bệnh cúm ở
người và động vật. Virus cúm được chia thành ba loại chính là cúm A, cúm B,
và cúm C. Cúm A và cúm B có 8 loại gen giống nhau, cúm C có 7 loại gen.
Với khả năng biến đổi và lan truyền nhanh từ động vật sang động vật, từ động
vật sang người, và đặc biệt là từ người sang người, virus cúm là một trong
những loài virus nguy hiểm nhất cho nền kinh tế cũng như sức khỏe con
người trên toàn thế giới từ trước đến nay. Do mức độ đặc biệt nghiêm trọng
của virus cúm, các nghiên cứu về virus cúm đã được tiến hành nhiều năm nay.

Các nhà khoa học từng bước hiểu được cấu trúc, cơ chế biến đổi và lây truyền
của virus cúm, qua đó tìm ra các loại vacxin phòng chống. Do khả năng biến
đổi nhanh của virus cúm, cho nên quá trình nghiên cứu và sản xuất các loại
vacxin để cách phòng chống các chủng virus cúm mới được tiến hành thường
xuyên.
Protein là các phân tử cơ bản thực hiện chức năng của tế bào. Nó được
tạo thành từ một hay nhiều dãy amino axit theo một thứ tự đặc biệt; thứ tự
này được xác định bởi dãy các nucleotides trong gen mã hóa cho protein. Các


10

proteins cần thiết cho cấu trúc, chức năng và điều chỉnh tế bào, mơ và tổ chức,
mỗi protein có một vai trị đặc biệt. Vài thí dụ về proteins là: protein cấu trúc có thể coi như các khối tạo dựng cơ sở của sinh vật; enzymes - thực hiện (làm
xúc tác) một số lớn các phản ứng sinh hóa học, tạo ra sự trao đổi chất; protein
màng - chìa khóa của sự duy trì mơi trường tế bào, điều hịa dung tích tế
bào,v.v. Các proteins là phân tử quyết định tính trạng của sinh vật (thơng
minh hay khơng, màu mắt, ...).
Amino axit được cấu thành từ các bazơ trên trình tự ADN. Có tất cả 20
amino axit chính. Cấu trúc amino axit bao gồm: một nguyên tử carbon ở trung
tâm, nguyên tử carbon này được gắn với nguyên tử hydro và được gọi là
nguyên tử C-α; nguyên tử C-α liên kết với 3 thành phần khác là nhóm amino
(NH2), nhóm carboxylic (COOH) và gốc amino axit ký hiệu là R. Các gốc
amino axit khác nhau sẽ tạo ra các amino axit với tính chất hóa học khác
nhau.
Cấu trúc của axit nucleic (gồm ADN, ARN) và protein thường được
chia thành 4 loại:
 Cấu trúc bậc một: dãy của các nucleotide hay các amino axit nối với
nhau theo một thứ tự tuyến tính bất kỳ. Do các nucleotide chỉ khác
nhau thành phần bazơ hữu cơ, nên đại phân tử ADN, ARN như là một

trình tự sinh học gồm các bazơ A, C, G, T (U). Điều này rất thuận lợi
khi biểu diễn các đại phân tử ADN, ARN trên máy tính bằng chuỗi ký
tự chứa các ký tự chữ A, C, G, T, U. Trình tự này được trình bày theo
chiều 5'-3' và xác định cấu trúc hóa trị của tồn bộ phân tử.
 Cấu trúc bậc hai: xác định bởi tập hợp của các cặp bazơ tương tác với
nhau trong cùng một phân tử hoặc với các phân tử khác. ADN là một
chuỗi xoắn kép gồm 2 mạch đơn, các nucleotide trong mạch đơn này
bắt cặp với nucleotide trong mạch còn lại theo nguyên tắc bổ sung A-


11

T, G-C. ARN có dạng mạch đơn, có dạng tương tác phức tạp hơn. Với
phân tử protein, khi các amino axit gần nhau liên kết với nhau thông
qua liên kết hydro giữa nhóm amin (NH) của amino axit này với
nguyên tử oxy của amino axit khác sẽ tạo nên vòng xoắn của chuỗi
polypeptide. Sự xoắn gấp của dãy các amino axit tạo nên cấu trúc bậc
hai.
 Cấu trúc bậc ba: do xoắn gấp, nhiều phần của dãy phân tử protein có
sự tiếp xúc với nhau, tạo ra nhiều lực hút và lực đẩy giữa chúng, tạo
cho phân tử có được một cấu trúc 3D tương đối bền vững và cố định.
 Cấu trúc bậc bốn: một protein có thể được tạo ra từ nhiều hơn một dãy
amino axit. Thí dụ như haemoglobin được tạo ra từ bốn dãy trong đó
mỗi dãy có khả năng bó lại một phân tử.
Tìm ra cấu trúc của ADN, ARN và protein là bài toán khó và tốn kém
hiện nay.
1.1.3. Phiên mã và dịch mã
Biểu hiện gen, ám chỉ mọi quá trình liên quan đến việc chuyển đổi thông
tin di truyền chứa trong gen (một đoạn/chuỗi ADN) để chuyển thành các axít
amin (hay protein), mỗi loại protein sẽ thể hiện một cấu trúc và chức năng

riêng của tế bào. Tuy nhiên, cũng tồn tại các gen khơng mã hóa cho protein
(ví dụ: gen rARN, gen tARN).
Q trình tổng hợp proteins dựa trên thơng tin được mã hóa trong gens
gồm ba giai đoạn chính: phiên mã, ghép mã, dịch mã (hình 1.4).
Hiện nay, chúng ta có một sự hiểu biết quá cơ bản về trình tự gen mã hóa
thành một protein cụ thể. Chúng ta cũng thiếu thông tin cần thiết để hiểu một
cách đầy đủ về vai trò của ADN trong những căn bệnh cụ thể, hoặc để hiểu
được chức năng của hàng ngàn protein được sản sinh ra. Ngoài ra, sự đột biến


12

là sự thay đổi một hay nhiều bazơ trong phân tử ADN. Điều này có thể dẫn
đến sự biến đổi đặc trưng hoặc dẫn đến bệnh di truyền. Mà càng phong phú,
đa dạng về sự sống đang tồn tại, hiểu biết của con người lại càng ít ỏi. Do đó
cần có các phương pháp dùng để tập hợp, lưu trữ, khơi phục, phân tích, tìm ra
mối tương quan của một lượng thông tin khổng lồ, phức tạp và ngành tin sinh
học ra đời từ đó.

Hình 1.4. Học thuyết trung tâm của sinh học phân tử

1.2. Tổng quan về tin sinh học
Tin sinh học là một lĩnh vực khoa học sử dụng các cơng nghệ của các
ngành tốn học ứng dụng, tin học, thống kê, khoa học máy tính, trí tuệ nhân
tạo, hóa học và hóa sinh để giải quyết các vấn đề, dữ liệu liên quan đến sinh
học phân tử.
Các lĩnh vực nghiên cứu chính của tin sinh học gồm: hệ gen học phân
tích trình tự (sắp dãy), tìm kiếm gen, tìm kiếm các đột biến, phân loại học
phân tử, bảo tồn đa dạng sinh học, phân tích chức năng gen hay biểu hiện
nhận diện chuỗi polypeptid, dự đoán cấu trúc, hệ thống sinh học kiểu mẫu,

phân tích hình ảnh mức độ cao, công cụ phần mềm.


13

Bài toán dự đoán cấu trúc bao gồm dự đoán cấu trúc axit nucleic, protein
là bài toán quan trọng của tin sinh học. Dự đoán cấu trúc axit nucleic nhằm
xác định cấu trúc cấp hai và cấu trúc cấp ba thơng qua trình tự của nó (cấu
trúc cấp một). Cấu trúc cấp hai có thể được dự đốn từ một hoặc một số trình
tự axit nucleic. Việc dự đốn cấu trúc cấp hai của axit nucleic phụ thuộc chủ
yếu vào việc xếp cặp và tương tác của các cặp bazơ. Nhiều phân tử ADN,
ARN có thể có một số cấu trúc ba chiều, tuy vậy để dự đoán những cấu trúc
này vẫn cịn là điều khó khăn, trừ khi xác định được rõ ràng trình tự và chức
năng phân lớp. Các phương pháp nghiên cứu cấu trúc ADN, ARN là tương tự
nhau, tuy nhiên vẫn có sự khác biệt nhỏ trong cách tiếp cận do ADN tạo thành
từ hai chuỗi nucleotide theo nguyên tắc bổ sung, trong khi đó ARN có nhiều
khả năng gấp trong q trình phiên mã tạo thành cấu trúc cấp ba, cấp bốn
phức tạp như trong các ribosome, spliceosome, hoặc tARN. Từ đó dẫn đến
việc phân tích, so sánh các phương thức dự đốn cấu trúc cấp hai của ARN
trong khi phiên mã, dịch mã là vấn đề cần giải quyết.
Mục đích của tin sinh học là cung cấp cho những nhà khoa học cách thức
lý giải: sự tiến triển sinh học bình thường, những trục trặc trong quá trình phát
triển này dẫn đến bệnh tật và cách thức tiếp cận để cải thiện việc khám phá
thuốc điều trị.
Chức năng chính của tin sinh học là xây dựng các ngân hàng dữ liệu để
lưu trữ và quản lý dữ liệu sinh học phân tử; tìm ra các phương pháp để xác
định mối quan hệ về mặt sinh học giữa các dữ liệu; xây dựng các công cụ để
phân tích từ đó có những hiểu biết rõ hơn về nguồn dữ liệu sinh học.
Phát triển các cơ sở dữ liệu về thông tin sinh học là một nhiệm vụ quan
trọng, để có được một kho lưu trữ lớn. Hiện nay, cơ sở dữ liệu về tin sinh học

được lưu trữ rất nhiều trên các ngân hàng cơ sở dữ liệu như: DDBJ (Ngân
hàng cơ sở dữ liệu sinh học ADN của Nhật), GenBank (ngân hàng cơ sở dữ


14

liệu sinh học của Mỹ), EMBL (cơ sở dữ liệu dự đoán tương tác proteinprotein), miRBase (ngân hàng cơ sở dữ liệu về các microARN), NCBIUnigen, TRANSFAC, EBI,v.v… , đây là những kho dữ liệu khổng lồ được
cập nhật hàng ngày và miễn phí đối với tất cả mọi người trên thế giới [1].
Cho đến nay, nhiều bộ gen đã được giải mã gần như hồn tồn. Có thể
nói chưa bao giờ thông tin sinh học trở nên phong phú và đa dạng như hiện
nay. Để tìm kiếm và khai phá thông tin trong khối lượng dữ liệu đồ sộ như
vậy, công nghệ thông tin đã được ứng dụng vào sinh học một cách khá triệt
để.
Với khối lượng lớn dữ liệu sinh học tác động qua lại lẫn nhau cũng đặt ra
nhiều vấn đề. Chẳng hạn, bộ gen người đã được giải mã, tuy nhiên để hiểu và
sử dụng được bộ mã này cần phải có những kiến thức về cấu trúc, chức năng
của protein, từ đó mới vận dụng được những kiến thức của bộ gen vào thực tế,
tác động vào sự di truyền.
Vấn đề lớn đối với tin sinh học hiện nay là làm sao để các thông tin về
các trình tự sinh học phục vụ thiết thực hơn nữa cho sự sống, không dừng ở
mức độ lưu trữ thơng tin. Từ đó hướng đến việc chuyển đổi thơng tin trình tự
sinh học sang các tri thức hóa sinh và lý sinh; giải mã các đầu mối tiến hóa;
chẩn đốn cấu trúc và chức năng của các cơ thể sống.
Trên thế giới, đã có nhiều phần mềm tin sinh học hỗ trợ các nhà nghiên
cứu, các nhà khoa học xử lý trình tự, dự đốn cấu trúc bậc hai ADN, ARN,
protein; có các cơng cụ tiện ích giúp thực hiện các thao tác tìm kiếm, tổ chức,
sắp xếp dữ liệu đồ sộ về các hệ gen, chú giải hệ gen như: PC-gens, Discovery
Studio gen, DNASIS, DNAMAN, VECTOR NTI, AnnHyb, DNA Club,
Plasmid Processor, Oligos, BEDTools v.v…
Trong nước, sự đóng góp của các nhà sinh học cũng khá phong phú như:

Viện Công nghệ Sinh học thuộc Viện Khoa học và Công nghệ Việt Nam,


15

Phịng Kỹ thuật di truyền, Phịng Cơng nghệ ADN ứng dụng, Phịng Hố sinh
protein, Phịng Vi sinh vật học phân tử, Viện Sinh học Nhiệt đới. Tuy nhiên,
sự đóng góp của các nhà tin học vào lĩnh vực này còn khá khiêm tốn. Cũng đã
có nhiều nhóm nghiên cứu xây dựng trang web, phần mềm để xử lý và hiển
thị thơng tin sinh học. Tuy kết quả cịn hạn chế nhưng đây là một đóng góp
đáng kể cho ngành tin sinh học đang mới hình thành ở Việt Nam.

1.3. Bài tốn tìm giao các đoạn gen
Việc so sánh các bộ dữ liệu đa dạng di truyền là căn bản để hiểu hệ gen
sinh học. Các nhà nghiên cứu phải khám phá nhiều bộ dữ liệu lớn về các đoạn
gen để đặt các kết quả thí nghiệm của họ trong một bối cảnh rộng hơn, tìm lời
giải cho các giả thuyết khoa học, từ đó thực hiện những khám phá mới.
Mối quan hệ giữa các tập hợp dữ liệu về gen thường được đo bằng cách
xác định các đoạn giao nhau, nghĩa là, chúng chồng lên nhau và do đó chia sẻ
một đoạn gen chung. Việc tìm ra phương pháp hiệu quả để đo mối quan hệ có
ý nghĩa thống kê giữa nhiều bộ tính năng di truyền là rất quan trọng đối với
những phát hiện trong tương lai.
Sự chồng chéo gen là mối quan hệ phổ biến ở virus, vi khuẩn và khá
hiếm ở sinh vật nhân chuẩn. Có một số báo cáo mô tả chồng chéo gen trong
động vật có vú, sinh vật có xương sống, một số nghiên cứu đã minh họa sự
chồng chéo gen khác nhau theo các mảnh và có sự phân bố khác nhau trong
lịch sử tiến hóa [8].
Bài tốn đặt ra là: cho hai tập các đoạn gen, mỗi đoạn gen cho biết tên
nhiễm sắc thể, vị trí đầu đoạn gen, vị trí cuối đoạn gen trên nhiễm sắc thể này.
Hãy tìm ra các đoạn gen giao nhau của tập thứ nhất với tập thứ hai, chỉ xét

các gen giao nhau của cùng một nhiễm sắc thể.
Vậy bài toán con của bài toán trên là: cho một tập các đoạn gen, và một
đoạn gen g bao gồm: tên nhiễm sắc thể, vị trí đầu đoạn gen, vị trí cuối đoạn


16

gen trên nhiễm sắc thể này. Hãy cho biết các đoạn gen trong cùng nhiễm sắc
thể và có giao với đoạn gen g, chỉ rõ vị trí giao nhau của chúng. Bài tốn này
có thể xem như là bài tốn đã phát biểu ở trên trong trường hợp tập thứ hai chỉ
gồm một đoạn gen duy nhất.
Hiện nay, BEDtools được đề xuất như là một cơng cụ tích hợp tiện ích
tìm giao của hai tập các đoạn gen. Tuy nhiên, nó vẫn cịn một số hạn chế: tốc
độ và hiệu quả chưa cao, chưa linh hoạt. Về khả năng linh hoạt của công cụ
này, trong trường hợp người dùng muốn thực hiện nhiều truy vấn tìm giao của
một hay một số đoạn gen với một tập các đoạn gen cố định thì nó chưa đáp
ứng tốt ngay được. Vì vậy, luận văn tiến hành nghiên cứu cấu trúc dữ liệu cây
quản lí đoạn, và áp dụng nó, đưa ra một phương pháp linh hoạt, nhanh chóng
để truy vấn tìm giao của một hay một số đoạn gen với một hệ gen từ trước, từ
đó mở rộng áp dụng để tìm giao giữa hai tập các đoạn gen.

Như vậy, chương này đã trình bày một số khái niệm cơ bản của sinh
học phân tử, tin sinh học và nêu lên bài tốn tìm giao của hai tập các đoạn
gen.


17

Chƣơng 2.
ỨNG DỤNG CỦA CÂY QUẢN LÍ ĐOẠN ĐỂ TÌM GIAO CÁC

ĐOẠN GEN
2.1. Đặc tả bài tốn tìm giao các đoạn gen
Xét bài toán: cho một tập các đoạn gen và một cửa sổ truy vấn, mỗi truy
vấn cung cấp thông tin một đoạn gen g bao gồm: tên nhiễm sắc thể, vị trí đầu
đoạn gen, vị trí cuối đoạn gen trên nhiễm sắc thể này. Hãy cho biết các đoạn
gen trong tập ban đầu cùng nhiễm sắc thể và có giao với đoạn gen g, chỉ rõ vị
trí giao nhau của chúng, số lượng đoạn gen giao với g.
Cụ thể về dữ liệu vào và kết quả ra của bài toán là:
Dữ liệu vào:
 Tệp gen1.inp gồm một số dịng, mỗi dịng là thơng tin về một đoạn
gen gồm: [Tên nhiễm sắc thể] [vị trí đầu đoạn gen] [vị trí cuối đoạn
gen].
 Thơng tin về một đoạn gen cần tìm kiếm gồm: [Tên nhiễm sắc thể] [vị
trí đầu đoạn gen] [vị trí cuối đoạn gen].
Trong đó:
 [Tên nhiễm sắc thể] là một chuỗi kí tự xác định tên của nhiễm sắc thể,
ví dụ: chr3, chrY, chr2_random, scaffold10671,...
 [Vị trí đầu đoạn gen], [vị trí cuối đoạn gen]: là hai số nguyên dương
xác định vị trí đầu và vị trí cuối của đoạn gen trên nhiễm sắc thể đang
xét. Giá trị này có thể là một số nguyên lớn, có thể có tới 11-12 chữ
số.
Thơng tin về đoạn gen cần tìm kiếm sẽ được cấp cho chương trình theo
hai dạng thức: