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

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