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

Lời mở đầu

Năm 1854, Charles Darwin cho xuất bản quyển sách “Nguồn gốc của các loài sinh vật”, một công trình nghiên cứu sinh học nổi tiếng và đặt nền tảng cho thuyết tiến hóa của ông. Trong đó có viết “tất cả các động vật tương tự nhau phải tiến hóa từ một tổ tiên chung và tất cả các sinh vật phải tiến hóa từ một vài hoặc một tổ tiên chung đã sống cách đây nhiều triệu năm.”

Bộ gen của sinh vật là một trình tự ADN, theo thuyết tiến hóa thì chúng cùng được biến đổi và phát triển từ một tổ tiên chung. Trải qua hàng triệu năm tiến hóa và phát triển, một số đoạn gen được mất đi cũng như bị di chuyển vị trí so với ban đầu, hình thành lên những hệ gen khác nhau đại diện cho hàng tỷ sinh vật trên trái đất. Một trong những nhiệm vụ cần thiết là phải tìm ra mối quan hệ về mặt cấu trúc giữa các hệ gen sinh vật, qua đó xây dựng lên một bức tranh toàn cảnh về sự tương tự và tiến hóa giữa các sinh vật trên hành tinh.

Với sự phát triển của công nghệ giải mã trình tự, ngày càng nhiều các hệ gen đã được giải mã hoàn chỉnh và được lưu trữ trong các ngân hàng cơ sở dữ liệu gen. Việc so sánh và tìm ra sự tương đồng giữa các hệ gen một cách thủ công là không thể thực hiện được. Do đó dẫn đến một nhu cầu cấp thiết phải nghiên cứu phương pháp và xây dựng chương trình để so sánh và bắt cặp trình tự cho hai hệ gen.

Mặc dù một số phương pháp đã được nghiên cứu và phát triển, chúng mới chỉ tập trung vào xác định và bắt cặp cho những vùng ADN có độ tương đồng cao giữa hai hệ gen. Tức là, một phần lớn trong hệ gen có thể không được bắt cặp và so sánh khi ta tiến hành với các loài sinh vật có hệ gen khác nhau nhiều. Vì vậy cần phải xây dưng một hệ thống có khả năng bắt cặp được toàn bộ các ADN trên hai hệ gen.

Chương 1. Giới thiệu

Chương này giới thiệu về những kiến thức cơ bản về tin sinh học, bài toán bắt cặp trình tự và bắt cặp trình tự theo hệ gen. Nội dung giới thiệu được dựa một phần trên bài giảng của Viện Đại học Ohio State, Hoa Kỳ

1.1. Trình tự

Một hệ gen của một sinh vật được thể hiện là một trình tự của các ADN.

Trình tự là một dãy tuyến tính các phần tử được sặp xếp theo thứ tự. Như vậy một trình tự chứa hai loại thông tin: thông tin về phần tử và thông tin định vị - thông tin về vị trí tương đối của từng phần tử so với các phần tử khác.

Các thông tin định vị có thể được xác định theo nhiều cách như theo trục, theo thời gian, vị trí của nhiễm sắc thể hoặc trong 1 vòng protein