ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
Nguyễn Thị Phương Thảo
XÂY DỰNG ĐỒ THỊ TÁI TỔ HỢP DI TRUYỀN
CHO DỮ LIỆU HỆ GEN
LUẬN ÁN TIẾN SĨ CÔNG NGHỆ THÔNG TIN
Hà Nội – 2020
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
Nguyễn Thị Phương Thảo
XÂY DỰNG ĐỒ THỊ TÁI TỔ HỢP DI TRUYỀN
CHO DỮ LIỆU HỆ GEN
Chuyên ngành: Khoa học Máy tính
Mã số: 9480101.01
LUẬN ÁN TIẾN SĨ CÔNG NGHỆ THÔNG TIN
NGƯỜI HƯỚNG DẪN KHOA HỌC:
1.PGS.TS. Lê Sỹ Vinh
2.PGS.TS. Lương Chi Mai
Hà Nội – 2020
Lời cam đoan
Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi. Các kết quả được viết
chung với các tác giả khác đều được sự đồng ý của các đồng tác giả trước khi đưa
vào luận án. Các kết quả nêu trong luận án là trung thực và chưa từng được ai công
bố trong các công trình nào khác.
Tác giả
Nguyễn Thị Phương Thảo
2
Lời cảm ơn
Luận án được thực hiện tại Trường Đại học Công nghệ, Đại học Quốc gia Hà Nội,
dưới sự hướng dẫn của PGS. TS. Lê Sỹ Vinh và PGS. TS. Lương Chi Mai.
Tôi xin bày tỏ lòng biết ơn sâu sắc tới PGS. TS. Lê Sỹ Vinh, PGS. TS. Lương Chi
Mai và TS. Lê Sĩ Quang, những người đã có những định hướng giúp tôi thành công
trong việc nghiên cứu của mình. Các Thầy Cô cũng đã động viên và khích lệ tinh
thần, giúp tôi vượt qua những khó khăn để tôi hoàn thành được luận án này. Tôi
cũng chân thành cảm ơn thầy Hồ Tú Bảo, Thầy đã cho tôi nhiều kiến thức quý báu
về nghiên cứu khoa học. Những sự chỉ bảo quý giá của các Thầy Cô đã giúp tôi
hoàn thành tốt luận án này.
Tôi cũng xin cảm ơn tới các Thầy, Cô thuộc Khoa Công nghệ Thông tin, Trường
Đại học Công nghệ, Đại học Quốc gia Hà Nội đã tạo mọi điều kiện thuận lợi giúp
tôi trong quá trình làm nghiên cứu sinh.
Tôi xin chân thành cảm ơn các đồng nghiệp trong phòng Nhận dạng và Công nghệ
Tri thức, Viện Công nghệ Thông tin, Viện Hàn lâm Khoa học và Công nghệ Việt
Nam đã luôn động viên, tạo điều kiện thuận lợi, bố trí thời gian tốt nhất cho tôi
trong suốt quá trình làm nghiên cứu sinh.
Cuối cùng, tôi xin gửi lời cảm ơn sâu sắc tới gia đình và bạn bè, những người đã
cho tôi điểm tựa vững chắc để tôi có được thành công như ngày hôm nay.
3
MỤC LỤC
Lời cam đoan ............................................................................................................... 1
Lời cảm ơn .................................................................................................................. 2
MỤC LỤC ................................................................................................................... 3
Danh mục các ký hiệu và chữ viết tắt ......................................................................... 6
Danh mục các bảng ..................................................................................................... 7
Danh mục các hình vẽ, đồ thị ...................................................................................... 8
Danh mục các thuật toán ........................................................................................... 12
MỞ ĐẦU 13
Chương 1. GIỚI THIỆU ............................................................................................ 16
1.1. Giới thiệu chung ........................................................................................... 16
1.1.1. Hệ gen người ...................................................................................... 16
1.1.2. Mạng phát sinh loài ............................................................................ 21
1.2. Xây dựng đồ thị tái tổ hợp di truyền ........................................................... 23
1.2.1. Sự kiện tái tổ hợp ............................................................................... 23
1.2.2. Đồ thị tái tổ hợp di truyền .................................................................. 25
1.2.3. Bài toán xây dựng đồ thị ARG .......................................................... 32
1.3. Các phương pháp xây dựng đồ thị ARG ..................................................... 35
1.3.1. Các phương pháp xây dựng đồ thị ARG tối thiểu ............................. 35
1.3.2. Các phương pháp xây dựng đồ thị ARG hợp lý ................................ 39
1.3.3. Tổng hợp các phần mềm xây dựng đồ thị ARG ................................ 41
1.4. Ứng dụng ARG trong nghiên cứu tương quan toàn hệ gen ......................... 42