Luận Văn Giải pháp sắp xếp chuỗi gen sử dụng cây hậu tố

Mở đầu

Trong thời đại khoa học công nghệ phát triển như vũ bão, nhất là lĩnh vực sinh học phân tử, hiện nay, các nhà sinh học đang phải làm việc với một lượng dữ liệu sinh học khổng lồ. Dường như những thao tác xử lý dữ liệu bằng tay trở nên không tưởng, điều này chính là nguyên nhân chủ yếu thúc đẩy sự ra đời của Tin sinh học, một ngành khoa học mới kết hợp giữa Khoa học máy tính và Sinh học phân tử như là một qui luật tất yếu của sự phát triển.
Cho đến nay, thành tựu quan trọng nhất của Tin sinh học là thành công của dự án giải mã bộ gen người (được tạo thành bởi trên 3 tỉ cặp cơ sở). Đây là một bước tiến đáng kể trong quá trình con người tìm hiểu về chính bản thân mình, công trình này có ý nghĩa vô cùng quan trọng, nó hứa hẹn tìm ra các phương pháp chữa bệnh mới có khả năng chữa được hầu hết các căn bệnh nan y hiện nay. Đồng thời, nó cũng là một nền tảng vững chắc cho các nghiên cứu về gen sau này. Đặc biệt là nghiên cứu về sắp xếp các chuỗi gen để tìm ra mối quan hệ tiến hóa giữa chúng.
Ngày nay, khi xã hội ngày càng phát triển, con người càng có nhu cầu tìm hiểu về nguồn gốc của mình, về tổ tiên xa xưa của chúng ta, về những loài động vật có mối liên hệ gần với loài người nhất. Những thắc mắc này phần nào có thể được giải quyết thông qua các nghiên cứu về sắp xếp chuỗi sinh học, từ đó tìm ra mối quan hệ tiến hóa giữa 2 chuỗi gen của hai loài đó với nhau.
Khóa luận của tôi trình bày về ứng dụng của cây hậu tố trong vấn đề sắp xếp chuỗi sinh học nhằm tăng tốc độ sắp xếp so với phương pháp quy hoạch động truyền thống mà vẫn giữ được độ chính xác trong sắp xếp. Cấu trúc của khóa luận này gồm có 4 chương. Chương thứ nhất sẽ giới thiệu tổng quan về Tin sinh học và các khái niệm chủ đạo của nó như DNA, RNA, protein. Chương hai trình bày về sắp xếp hai chuỗi sinh học và đề cập đến phương pháp sắp xếp sử dụng biểu đồ điểm, sau đó giới thiệu thuật toán sắp xếp loại I, đây là thuật toán quy hoạch động sẽ được dùng để so sánh với thuật toán sử dụng cây hậu tố sẽ được trình bày ở Chương ba. Chương ba sẽ đi chi tiết vào bài toán sắp xếp chuỗi sinh học bằng cách tìm ra các Maximal Unique Match (MUM) sử dụng các phương pháp Brute-force, k-mers và phương pháp sử dụng cây hậu tố. Chương bốn tôi sẽ đưa ra đánh giá về các kết quả thực nghiệm khi sử dụng phương pháp quy hoạch động và phương pháp sắp xếp sử dụng cây hậu tố. Cuối cùng là phần kết luận và định hướng phát triển trong tương lai của khóa luận.

Tin sinh học là một vấn đề mới mẻ, đã và đang được nghiên cứu trên thế giới nói chung và ở Việt Nam nói riêng. Nó đặt ra những đòi hỏi về kiến thức đa dạng ở các lĩnh vực khoa học khác nhau cũng như quá trình nghiên cứu lâu dài và kỹ lưỡng. Do thời gian có hạn nên mức độ nghiên cứu của khóa luận này còn hạn chế. Tôi xin chân thành cảm ơn và mong muốn nhận được ý kiến đóng góp và bổ sung của bạn đọc.





Lời cảm ơn

Khóa luận này được hoàn thành với sự giúp đỡ nhiệt tình của các thầy cô giáo, bạn bè và những người thân trong gia đình. Trước hết, tôi xin chân thành cảm ơn tất cả các thầy cô giáo, đặc biệt là các thầy cô giáo trường Đại học Công nghệ - ĐHQGHN, đã cho tôi nhiều kiến thức bổ ích trong quá trình học tập tại trường. Tôi xin chân thành cảm ơn TS. Hà Quang Thụy, ngươi đã định hướng cho tôi đến với Tin sinh học. Tôi cũng xin bày tỏ lòng biết ơn đến TS. Lê Sỹ Vinh, TS. Bùi Thế Duy đã tận tình chỉ bảo và hướng dẫn trực tiếp cho tôi trong quá trình hoàn thành khóa luận. Tôi xin chân thành cảm ơn anh Vũ Hồng Khiêm và các bạn bè đã giúp đỡ tôi rất nhiều về tài liệu cũng như kiến thức bổ ích và cần thiết về lĩnh vực Tin sinh học. Cuối cùng, tôi xin chân thành bày tỏ lòng biết ơn tới gia đình và toàn thể bạn bè đã động viên và giúp đỡ tôi hoàn thành bản khóa luận này.



Tóm tắt nội dung của khóa luận tốt nghiệp

Khóa luận của tôi đề cập về vấn đề sắp xếp chuỗi gen sử dụng cây hậu tố nhằm tối ưu tốc độ sắp xếp mà vẫn giữ được kết quả sắp xếp so với phương pháp sử dụng quy hoạch động. Nội dung khóa luận được phân ra làm 5 phần chính. Trong Phần đầu tiên tôi sẽ trình bày tổng quan về Tin sinh học và các khái niệm chủ đạo của nó như DNA, RNA, protein Phần thứ hai tập trung vào một số phương pháp sắp xếp chuối gen như phương pháp biểu đồ điểm và phương pháp sắp xếp loại I, đặc biệt đi sâu tìm hiểu thuật toán sắp xếp loại I, đây là một thuật toán quy hoạch động chuẩn sẽ được sử dụng để so sánh kết quả sắp xếp với phương pháp sử dụng cây hậu tố sẽ được trình bày ở phần thứ ba. Phần ba là phần giải quyết vấn đề sắp xếp chuỗi sinh học bằng cách tìm ra các Maximal Unique Match (MUM) sử dụng các phương pháp Brute-force, k-mers và phương pháp sử dụng cây hậu tố. Phần thứ tư tôi sẽ đưa ra đánh giá về các kết quả thực nghiệm khi sử dụng phương pháp quy hoạch động và phương pháp sắp xếp sử dụng cây hậu tố. Phần cuối cùng đưa ra kết luận và định hướng phát triển trong tương lai của khóa luận.



Mục lục


Mở đầu 1
Chương 1: Tổng quan về Tin sinh học 6
1.1 Giới thiệu về Tin sinh học 6
1.2 Một số khái niệm trong sinh học phân tử 7
1.2.1 DNA 9
1.2.2 RNA 13
1.2.3 Protein 15
1.2.4 DNA, RNA và quá trình tổng hợp protein 17
Chương 2: Sắp xếp hai chuỗi sinh học 18
2.1 Giới thiệu về so sánh 2 chuỗi sinh học 19
2.2 Biểu đồ điểm 20
2.3 Sắp xếp 2 chuỗi sinh học 21
2.4 Thuật toán sắp xếp 2 chuỗi sinh học 24
2.4.1 Giới thiệu về thuật toán sắp xếp loại I 24
2.4.2 Sắp xếp loại I 26
Định nghĩa 1: 26
Định nghĩa 2: 26
Thuật toán A-I: 27
Chương 3: Phương pháp sắp xếp 2 chuỗi sinh học dùng Maximal unique match(MUM) 30
3.1 Giới thiệu về MUM 30
3.2 Một số phương pháp tìm MUM 31
3.2.1 Phương pháp Brute-force: 31
3.2.2 Phương pháp k-mers: 32
3.2.3 Phương pháp sử dụng cây hậu tố: 33
Chương 4: Đánh giá kết quả thực nghiệm 43
4.1 Kết quả thực nghiệm 43
4.2 Đánh giá kết quả 46
Kết luận 47
Tài liệu tham khảo 48