ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
Hà Tuấn Cường
SẮP HÀNG HOÀN CHỈNH HAI HỆ GENOME
KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY

Ngành: Công Nghệ Thông Tin
HÀ NỘI – 2010
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
Hà Tuấn Cường
SẮP HÀNG HOÀN CHỈNH HAI HỆ GENOME
KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY


Ngành: Công Nghệ Thông Tin
GV hướng dẫn: TS. Lê Sỹ Vinh
HÀ NỘI – 2010
Page|1
Lời cảm ơn
Lời đầu tiên, em xin gửi lời cảm ơn sâu sắc nhất đến thầy giáo TS. Lê Sỹ
Vinh người đã không quản vất vả tận tình hướng dẫn em trong suốt thời gian làm
khóa luận tốt nghiệp vừa qua.
Em cũng xin bày tỏ lòng biết ơn tới các thầy, cô giáo trong trường Đại
học Công nghệ - Đại học Quốc gia Hà Nội. Các thầy cô đã dạy bảo, chỉ dẫn
chúng em và luôn tạo điều kiện tốt nhất cho chúng em học tập trong suốt quá
trình học đại học.
Em cũng xin gửi lời cảm ơn tới thầy giáo PGS.TS. Từ Minh Phương,
người đã cho em những lời khuyên bổ ích trong quá trình làm khóa luận.
Tôi cũng xin cảm ơn những người bạn của mình, các bạn đã luôn ở bên
tôi, giúp đỡ và cho tôi những ý kiến đóng góp quý báu trong học tập cũng như
trong cuộc sống.
Cuối cùng con xin gửi tới bố mẹ và toàn thể gia đình lòng biết ơn và tình
cảm yêu thương nhất. Con xin dành tặng bố mẹ kết quả mà con đã đạt được trong
suốt bốn năm học đại học. Con cám ơn bố mẹ và chị nhiều.
Khóa luận được tài trợ một phần bởi đề tài nghiên cứu QC.09.09 thuộc
Đại học Quốc Gia Hà Nội.
Hà Nội, tháng 5 năm 2010
Hà Tuấn Cường
Page|2
Tóm tắt
Sự phát triển của công nghệ giải mã trình tự đã giúp giải mã ngày càng
nhiều các hệ gen, đặc biệt là những hệ gen có kích thước vừa và nhỏ như vi rút
hay vi khuẩn (hơn 7000 bộ gen của vi rút và vi khuẩn đã được giải mã). Bên
cạnh đó hệ gen của những sinh vật bậc cao cũng đã được giải mã hoàn chỉnh như
người, chó, chuột. Điều đó dẫn đến một nhu cầu cấp thiết là phải nghiên cứu các
phương pháp và xây dựng một chương trình so sánh và bắt cặp trình tự cho hai
hệ gen.
Trong khóa luận này, em xin được trình bày phương pháp và xây dựng
một chương trình so sánh bắt cặp trình tự hoàn chỉnh cho hai hệ gen. Chương
trình cho phép bắt cặp toàn bộ các ADN trên cả hai hệ gen, xác định được cả
những biến đổi của tửng nucleotide và các biến đổi ở mức độ gen.
Chương trình được xây dựng dựa trên cở s
ở kết hợp và cải tiến các
phương pháp đã có như “Pairwise Alignment with Rearrangement” [23],
BLASTZ [18] và “Optimal Alignment with Linear space” [9]. Qua đó khắc
phục những hạn chế và lựa chọn những ưu điểm của chúng để tạo thành một
chương trình sắp hàng hệ gen hoàn chỉnh. Chương trình đã được thực nghiệm kết
quả trên các dữ liệu mô phỏng và các dữ liệu thật được lấy từ Gen Bank tại NCBI
http://www.ncbi.nlm.nih.gov và thu được những kết quả khả quan.
Đối với các dữ mô phỏng, kết quả sắp hàng của chương trinh cho thấy đã
xác định được các đoạn gen có độ tương đồng rất cao, tỷ lể sắp hàng giữa các
nucleotide giống nhau đạt mức trên 97%. Khi thực nghiệm với dữ liệu thật và so
sánh độ tương đồng với giá trị bắt cặp thu được khi chạy phương thức
Hungarian[8] với các hệ gen được chia sẵn bằng cách sử dụng các đoạn gen cung
cấp tại Gen Bank cũng cho kết quả tương đương thậm chí tốt hơn trong hầu hết
các trường hợp.
Page|3
Mục lục
Lời cảm ơn...........................................................................................................1
Tóm tắt..................................................................................................................2
Mục lục.................................................................................................................3
Danh sách hình vẽ............................................................................................5
Danh sách các bảng..........................................................................................6
Lời mở đầu..........................................................................................................7
Chương 1. Giới thiệu........................................................................................8
1.1.Trình tự....................................................................................................8
1.1.1. Hệ thống ký tự......................................................................................9
1.1.2. Các phép biến đổi.................................................................................9
1.1.3. Khoảng cách.......................................................................................10
1.2.Bắt cặp trình tự.....................................................................................10
1.3.Bắt cặp trình tự hệ gen .........................................................................12
Chương 2. Bài toán sắp hàng hoàn chỉnh hai hệ gen..........................16
2.1. Tổng quan .................................................................................................16
2.2 Pairwise Alignment with Rearrangement...............................................16
2.2.1. Cơ sở lý thuyết...................................................................................17
2.2.2. Thuật toán...........................................................................................18
2.2.3. Độ phức tạp của thuật toán .................................................................21
2.3. Bắt cặp với những trình tự lớn................................................................22
Chương 3. Full Genome Alignment ..........................................................24
3.1. Xây dựng hệ thống ...................................................................................24