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” , BLASTZ và “Optimal Alignment with Linear space” . 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 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.

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

3.2. Giới thiệu về BLASTZ 25

3.2.1. Tính năng của BLASTZ 25

3.2.2. Chương trình BLASTZ 27

3.3. Optimal Alignment with Linear space 28

Chương 4. Kết quả 31

4.1. Chương trình 31

4.2. Kiểm thử 33

4.2.1. Dữ liệu mô phỏng 33

4.2.2. Dữ liệu thật 35

Chương 5. Kết luận 38

Tài liệu tham khảo 39

Danh sách hình vẽ

Hình 1. Ví dụ về một trình tự. 8

Hình 2: Các biến đổi ở mức độ gen giữa Người và Khỉ 13

Hình 3:Ví dụ về phép biến đổi trong “Simulaneous Character Swapping". 20

Hình 4: Single Swap (trái) và Couple Swap (phải) 22

Hình 5:Bắt cặp trình tự với Ukkonen Barrier 29

Hình 6: Giao diện chương trình 31

Hình 7: Kết quả chương trình 32