Ứng dụng thuật toán Burrows – Wheeler Transform trong quá trình giải mã hệ gen lúa tại Việt Nam

 


Tin - Sinh học (Bioinformatics) là một lĩnh vực khoa học sử dụng các công nghệ của các ngành toán học ứng dụng, tin học, thống kê, khoa học máy tính, trí tuệ nhân tạo, hóa học và hóa sinh để giải quyết các vấn đề sinh học. Sự ra đời của Tin - Sinh học là sự hợp tác chặt chẽ giữa các nhà Tin học và các nhà nghiên cứu Sinh học nhằm khai phá dữ liệu hiệu quả, Tin – Sinh học đã trở thành mục tiêu công nghệ của ngành Sinh học trong thế kỉ mới. Bắt kịp xu thế phát triển của khoa học thế giới, những năm gần đây các nhà Tin - Sinh học Việt Nam đã xác định được những hướng đi phù hợp và đạt được thành công bước đầu với một số công trình nghiên cứu mang tính ứng dụng cao.

Trong sinh học, việc giải mã trình tự gen rất quan trọng, nó góp phần trong việc nghiên cứu sinh học cơ bản và trong nhiều lĩnh vực ứng dụng như chẩn đoán bệnh tật, công nghệ sinh học, sinh học pháp y, sinh học hệ thống... Do đặc tính khí hậu nhiệt đới, Việt Nam có những lợi thế về những nguồn dữ liệu Sinh học to lớn, hữu ích, điều đó trở thành một điều kiện thuận lợi và cũng là thách thức cần đến sự đóng góp của Tin - Sinh học.


NỘI DUNG:


CHƢƠNG 1: CƠ SỞ LÝ THUYẾT ............................................................................. 3

1.1 Đặt vấn đề ............................................................................................................... 3

1.1.1


Tin – Sinh học ..................................................................................................... 3


1.1.2


Khai phá dữ liệu trong Tin – Sinh học ................................................................ 4


1.1.3


Hướng phát triển của ngành Tin – Sinh học tại Việt Nam ................................. 5


1.2 Mục tiêu của luận văn ........................................................................................... 6

1.3 Các khái niệm cơ bản trong sinh học phân tử .................................................... 7

1.3.1


DNA .................................................................................................................... 7


1.3.2


Gen ...................................................................................................................... 8


1.3.3


Hệ gen tham chiếu............................................................................................... 9


1.3.4


Định dạng dữ liệu trong bài toán Tin – Sinh học ................................................ 9


CHƢƠNG 2 : CƠ SỞ LÝ THUYẾT VÀ THUẬT TOÁN ........................................ 14

BURROWS WHEELER TRANSFORM.................................................................. 14

2.1 Quy trình giải mã hệ gen và bài toán gióng hàng trình tự .............................. 14

2.1.1


Giải mã hệ gen và quy trình .............................................................................. 14


2.1.2


Nội dung bài toán gióng hàng trình tự (Sequence Alignment) ......................... 16


2.1.3


Ý nghĩa sinh học của bài toán gióng hàng trình tự ........................................... 17


2.1.4


Phân loại bài toán gióng hàng trình tự .............................................................. 18


2.2 Một số thuật toán cơ bản cho bài toán gióng hàng trình tự ............................ 20

2.2.1


Thuật toán ma trận điểm ................................................................................... 20


2.2.2


Thuật toán quy hoạch động Smith-Waterman .................................................. 24


2.3 Thuật toán Burrows – Wheeler Tranform (BWT ) ......................................... 31

2.3.1


Chuyển đổi Burrows-Wheeler thuâ ̣n ................................................................ 32


2.3.2


Chuyển đổi Burrows-Wheeler nghich

̣ .............................................................. 38


2.3.3


Tìm kiếm chính xác (Exact matching) .............................................................. 41


2.3.4


Tìm kiếm có sai khác không nhiều hơn z vị trí (Inexact matching) ................. 49


2.4 Kết luận ................................................................................................................ 53

CHƢƠNG 3 : ỨNG DỤNG THUẬT TOÁN BWT VÀ THỬ NGHIỆM TRÊN DỮ

LIỆU SINH HỌC ......................................................................................................... 55

3.1 Quy trình thực nghiệm ........................................................................................ 55

3.2 Cài đặt ứng dụng ................................................................................................. 56

3.3 Chuẩn bị dữ liệu .................................................................................................. 58

3.4 Kết quả và đánh giá ............................................................................................. 62

3.5 Đánh giá kết quả của luận văn ........................................................................... 67

KẾT LUẬN ................................................................................................................... 69

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



LINK DOWNLOAD

 


Tin - Sinh học (Bioinformatics) là một lĩnh vực khoa học sử dụng các công nghệ của các ngành toán học ứng dụng, tin học, thống kê, khoa học máy tính, trí tuệ nhân tạo, hóa học và hóa sinh để giải quyết các vấn đề sinh học. Sự ra đời của Tin - Sinh học là sự hợp tác chặt chẽ giữa các nhà Tin học và các nhà nghiên cứu Sinh học nhằm khai phá dữ liệu hiệu quả, Tin – Sinh học đã trở thành mục tiêu công nghệ của ngành Sinh học trong thế kỉ mới. Bắt kịp xu thế phát triển của khoa học thế giới, những năm gần đây các nhà Tin - Sinh học Việt Nam đã xác định được những hướng đi phù hợp và đạt được thành công bước đầu với một số công trình nghiên cứu mang tính ứng dụng cao.

Trong sinh học, việc giải mã trình tự gen rất quan trọng, nó góp phần trong việc nghiên cứu sinh học cơ bản và trong nhiều lĩnh vực ứng dụng như chẩn đoán bệnh tật, công nghệ sinh học, sinh học pháp y, sinh học hệ thống... Do đặc tính khí hậu nhiệt đới, Việt Nam có những lợi thế về những nguồn dữ liệu Sinh học to lớn, hữu ích, điều đó trở thành một điều kiện thuận lợi và cũng là thách thức cần đến sự đóng góp của Tin - Sinh học.


NỘI DUNG:


CHƢƠNG 1: CƠ SỞ LÝ THUYẾT ............................................................................. 3

1.1 Đặt vấn đề ............................................................................................................... 3

1.1.1


Tin – Sinh học ..................................................................................................... 3


1.1.2


Khai phá dữ liệu trong Tin – Sinh học ................................................................ 4


1.1.3


Hướng phát triển của ngành Tin – Sinh học tại Việt Nam ................................. 5


1.2 Mục tiêu của luận văn ........................................................................................... 6

1.3 Các khái niệm cơ bản trong sinh học phân tử .................................................... 7

1.3.1


DNA .................................................................................................................... 7


1.3.2


Gen ...................................................................................................................... 8


1.3.3


Hệ gen tham chiếu............................................................................................... 9


1.3.4


Định dạng dữ liệu trong bài toán Tin – Sinh học ................................................ 9


CHƢƠNG 2 : CƠ SỞ LÝ THUYẾT VÀ THUẬT TOÁN ........................................ 14

BURROWS WHEELER TRANSFORM.................................................................. 14

2.1 Quy trình giải mã hệ gen và bài toán gióng hàng trình tự .............................. 14

2.1.1


Giải mã hệ gen và quy trình .............................................................................. 14


2.1.2


Nội dung bài toán gióng hàng trình tự (Sequence Alignment) ......................... 16


2.1.3


Ý nghĩa sinh học của bài toán gióng hàng trình tự ........................................... 17


2.1.4


Phân loại bài toán gióng hàng trình tự .............................................................. 18


2.2 Một số thuật toán cơ bản cho bài toán gióng hàng trình tự ............................ 20

2.2.1


Thuật toán ma trận điểm ................................................................................... 20


2.2.2


Thuật toán quy hoạch động Smith-Waterman .................................................. 24


2.3 Thuật toán Burrows – Wheeler Tranform (BWT ) ......................................... 31

2.3.1


Chuyển đổi Burrows-Wheeler thuâ ̣n ................................................................ 32


2.3.2


Chuyển đổi Burrows-Wheeler nghich

̣ .............................................................. 38


2.3.3


Tìm kiếm chính xác (Exact matching) .............................................................. 41


2.3.4


Tìm kiếm có sai khác không nhiều hơn z vị trí (Inexact matching) ................. 49


2.4 Kết luận ................................................................................................................ 53

CHƢƠNG 3 : ỨNG DỤNG THUẬT TOÁN BWT VÀ THỬ NGHIỆM TRÊN DỮ

LIỆU SINH HỌC ......................................................................................................... 55

3.1 Quy trình thực nghiệm ........................................................................................ 55

3.2 Cài đặt ứng dụng ................................................................................................. 56

3.3 Chuẩn bị dữ liệu .................................................................................................. 58

3.4 Kết quả và đánh giá ............................................................................................. 62

3.5 Đánh giá kết quả của luận văn ........................................................................... 67

KẾT LUẬN ................................................................................................................... 69

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



LINK DOWNLOAD

M_tả
M_tả

Không có nhận xét nào: