Xây Dựng Đồ Thi Tái Tổ Hợp Di Truyền Cho Dữ Liệu Hệ Gen

ĐẠ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

4

1.5. Kết luận chương ..........................................................................................45

Chương 2.THUẬT TOÁN ARG4WG XÂY DỰNG ĐỒ THỊ TÁI TỔ HỢP DI

TRUYỀN HỢP LÝ CHO DỮ LIỆU HỆ GEN........................................47

2.1. Giới thiệu .....................................................................................................47

2.1.1. Các định nghĩa ...................................................................................47

2.1.2. Thuật toán Margarita xây dựng đồ thị ARG......................................48

2.2. Thuật toán ARG4WG..................................................................................51

2.2.1. Chiến lược tìm đoạn đầu chung dài nhất ...........................................51

2.2.2. Thuật toán ARG4WG ........................................................................54

2.3. Kết quả thực nghiệm....................................................................................61

2.3.1. Các kết quả trên dữ liệu thật ..............................................................61

2.3.2. Các kết quả trên dữ liệu mô phỏng ....................................................65

2.4. Kết quả ứng dụng ARG4WG vào bài toán tìm vùng gen liên quan đến bệnh

sốt rét ở Châu Phi.........................................................................................67

2.5. Kết luận chương ..........................................................................................72

Chương 3.PHƯƠNG PHÁP TỐI ƯU HÓA SỐ SỰ KIỆN TÁI TỔ HỢP TRONG

QUÁ TRÌNH XÂY DỰNG ĐỒ THỊ ARG.............................................75

3.1. Giới thiệu .....................................................................................................75

3.2. Một số định nghĩa và khái niệm sử dụng trong các thuật toán....................76

3.3. Hạn chế của thuật toán ARG4WG ..............................................................78

3.4. Thuật toán REARG .....................................................................................79

3.4.1. Động cơ nghiên cứu...........................................................................79

3.4.2. Thuật toán REARG............................................................................80

5

3.5. Thuật toán GAMARG .................................................................................83

3.5.1. Động cơ nghiên cứu...........................................................................83

3.5.2. Thuật toán GAMARG........................................................................83

3.6. Kết quả thực nghiệm....................................................................................88

3.6.1. Kết quả trên các tập dữ liệu nhỏ ........................................................89

3.6.2. Các kết quả trên các tập dữ liệu từ dự án 1kGP.................................90

3.7. Kết luận chương ..........................................................................................98

KẾT LUẬN.............................................................................................................100

DANH MỤC CÁC CÔNG TRÌNH KHOA HỌC CỦA TÁC GIẢ LIÊN QUAN

ĐẾN LUẬN ÁN ....................................................................................102

TÀI LIỆU THAM KHẢO.......................................................................................103

6

Danh mục các ký hiệu và chữ viết tắt

D Tập các trình tự

N Số lượng trình tự trong một tập các trình tự

m độ dài của trình tự

Sx Trình tự thứ x trong một tập các trình tự

Sx[i] Giá trị của Sx tại vị trí thứ i

ARG Đồ thị tái tổ hợp di truyền

1KGP Dự án 1000 hệ gen

GWAS Nghiên cứu tương quan toàn hệ gen

SNP Đa hình đơn nucleotit

MRCA Tổ tiên chung gần nhất

CwR Mô hình kết hợp và tái tổ hợp

STT Số thứ tự

RF Khoảng cách Robinson-Fould

7

Danh mục các bảng

Bảng 1.1: Các phần mềm xây dựng đồ thị ARG tiêu biểu........................................41

Bảng 2.1: Tập dữ liệu trích xuất từ dự án 1000 hệ gen người. .................................62

Bảng 3.1: Tập dữ liệu từ dự án 1kGP. ......................................................................89

Bảng 3.2: Các kết quả của các thuật toán khác nhau trên các tập dữ liệu nhỏ. ........89

Bảng 3.3: Số sự kiện tái tổ hợp ít nhất được tìm thấy bởi 5 thuật toán cho 100 trình

tự của (a) DS1, (b) DS2 và (c) DS3. .........................................................................91

Bảng 3.4: Số sự kiện tái tổ hợp ít nhất được tìm thấy bởi 5 thuật toán cho 200 trình

tự của (a) DS1, (b) DS2 và (c) DS3. .........................................................................92

Bảng 3.5: Trung bình thời gian chạy (giây) của 5 thuật toán cho 100 trình tự của các

tập dữ liệu (a) DS1, (b) DS2, và (c) DS3. .................................................................95

Bảng 3.6: Trung bình thời gian chạy (giây) của 5 thuật toán cho 200 trình tự của các

tập dữ liệu (a) DS1, (b) DS2, và (c) DS3. .................................................................97

8

Danh mục các hình vẽ, đồ thị

Hình 1.1: Cấu trúc hệ gen người. Hệ gen người gồm 23 cặp nhiễm sắc thể, có

khoảng 3 tỉ phân tử DNA, khoảng 20.000 đến 25.000 gen. Nguồn hình:

https://genomainternational.com/introduction-to-genomics/....................................16

Hình 1.2: Các kiểu biến thể trình tự: (a) Thay thế một cặp bazơ đơn. Trong ví dụ,

biến thể xuất hiện ở 2 vị trí so với trình tự tham chiếu, đó là thay thế nucleotit T↔A

và G↔A. (b) Chuỗi GCA được chèn vào so với trình tự tham chiếu. (c) Chuỗi CG

bị xóa so với trình tự tham chiếu...............................................................................17

Hình 1.3: Các loại biến thể cấu trúc: xóa, thêm, lặp, đảo hay lặp nhiều lần 1 đoạn

DNA. Đoạn đột biến cấu trúc có kích thước lớn hơn 1kb. .......................................18

Hình 1.4: Ví dụ dữ liệu SNP chứa biến thể 2 alen và nhiều alen. Có 8 vị trí SNP đều

là 2 alen, gồm alen tham chiếu và 1 alen biến thể, ví dụ như A và G ở vị trí 1; T và

C ở vị trí 2. Chỉ có vị trí 7 là 3 alen: alen tham chiếu (G) và 2 alen biến thể C, T...19

Hình 1.5: Ví dụ 4 haplotype của 4 cá thể trên một vùng gen. Một haplotype được

tạo thành từ sự kết hợp của các SNP được di truyền cùng nhau trong các đoạn DNA.

...................................................................................................................................19

Hình 1.6: Cây phân loài biểu diễn mối quan hệ tiến hóa của một số loài linh trưởng.

Đười ươi và Khỉ đột rẽ nhánh sớm hơn các loài linh trưởng khác. Con người rẽ ra

một nhánh riêng và nhánh còn lại cho ra Tinh tinh và vượn Bonobo.......................21

Hình 1.7: Khái quát hóa các mạng phát sinh loài điển hình [36]..............................23

Hình 1.8: Hai hiện tượng tái tổ hợp phổ biến của người: (a) trao đổi chéo và (b)

chuyển đổi gen. .........................................................................................................24

Hình 1.9: Biến đổi dữ liệu SNP thành dạng nhị phân. Vị trí có giá trị giống với tham

chiếu là 0, giá trị khác tham chiếu là 1......................................................................28

9

Hình 1.10: Đồ thị ARG cho tập dữ liệu M gồm 7 trình tự độ dài 5 [26]. Trình tự tổ

tiên là “00000”; 5 sự kiện đột biến tại các vị trí tương ứng (1,2,3,4,5) được ghi trên

các cạnh xảy ra đột biến của đồ thị; 2 sự kiện tái tổ hợp xảy ra tại vị trí 3 và 4.......29

Hình 1.11: Điểm cắt tái tổ hợp..................................................................................30

Hình 1.12: Một ví dụ đồ thị ARG cho 4 trình tự với các ký hiệu: ■: trạng thái di

truyền, ◘: trạng thái di truyền đột biến, □: trạng thái không xác định......................31

Hình 1.13: Các cây thành phần (đường đậm nét) của đồ thị ARG trong Hình 1.12.

Nguồn hình [43]. .......................................................................................................33

Hình 1.14: (a) Ví dụ cặp vị trí tương thích: cặp vị trí này chỉ chứa 3 loại giao tử và

có thể có được từ 1 tổ tiên chung thông qua 2 sự kiện đột biến. (b) Cặp vị trí không

tương thích: cặp vị trí chứa 4 loại giao tử và trong trường hợp này phải có ít nhất 1

sự kiện tái tổ hợp xảy ra dưới giả định các vị trí vô hạn (kí hiệu * biểu thị vị trí

không có thông tin). ..................................................................................................36

Hình 1.15: Một cây có nốt sùi cho tập trình tự giống với tập trong Hình 1.10 với 2

nốt sùi tương ứng với 2 chu trình tái tổ hợp không chung nút với nhau [27]...........38

Hình 1.16: (a) Đồ thị ARG cho tập 4 trình tự, trong đó trình tự s1, s2 là từ 2 cá thể

khỏe mạnh, trình từ s3, s4 là từ 2 cá thể bị bệnh. (b) Đột biến 3 (vùng khoanh tròn)

trên cây biên tại vị trí 3 của đồ thị ARG trong (a) cho ra sự phân biệt rõ nhất giữa

các trình tự bệnh và trình tự không bệnh. .................................................................44

Hình 2.1: Lưu đồ thuật toán Margarita. ....................................................................49

Hình 2.2: Vấn đề trong việc thực hiện sự kiện tái tổ hợp của Margarita. Hai trình tự

S1 và S2 với đoạn chung dài nhất giữa hai trình tự được biểu diễn bằng đoạn màu

đen. Thuật toán thực hiện lần lượt 2 sự kiện tái tổ hợp R1 và R2 trên trình tự S1 để

sinh ra 3 trình tự con S11, S12 và S13. Sau đó, trình tự con chứa đoạn chung dài nhất

S13 sẽ được kết hợp với S2. Vì vậy, khi đoạn chung dài nhất được tìm thấy bên trong