Luận án Tiến sĩ Công nghệ thông tin: Các phương pháp nhanh xây dựng cây bootstrap tiến hóa

Luận án nghiên cứu phương pháp chuẩn và các phương pháp nhanh hiện tại cho xây dựng cây bootstrap tiến hóa theo tiêu chuẩn ML, đặc biệt là UFBoot, từ đó đưa ra đề xuất cải tiến để giải quyết tốt hơn từng thách thức của bài toán thời gian chạy, độ chuẩn xác, ảnh hưởng của vi phạm mô hình và hiện tượng đa phân.
Nội dung trích xuất từ tài liệu:
Luận án Tiến sĩ Công nghệ thông tin: Các phương pháp nhanh xây dựng cây bootstrap tiến hóa ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Hoàng Thị Điệp CÁC PHƯƠNG PHÁP NHANHXÂY DỰNG CÂY BOOTSTRAP TIẾN HÓALUẬN ÁN TIẾN SĨ CÔNG NGHỆ THÔNG TIN Hà Nội – 2019 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Hoàng Thị Điệp CÁC PHƯƠNG PHÁP NHANHXÂY DỰNG CÂY BOOTSTRAP TIẾN HÓA Chuyên ngành: Khoa học Máy tính Mã số: 9480101.01LUẬN ÁN TIẾN SĨ CÔNG NGHỆ THÔNG TIN NGƯỜI HƯỚNG DẪN KHOA HỌC: 1. PGS.TS. Lê Sỹ Vinh 2. PGS.TS. Hoàng Xuân Huấn Hà Nội – 2019 Lời cam đoan Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi. Các kết quả đượcviết chung với các tác giả khác đều được sự đồng ý của các đồng tác giả trước khiđưa vào luận án. Các kết quả nêu trong luận án là trung thực và chưa từng được aicông bố trong các công trình nào khác. Tác giả 1 Lời cảm ơn Luận án được thực hiện tại Trường Đại học Công nghệ, Đại học Quốc gia HàNội, dưới sự hướng dẫn của PGS.TS. Lê Sỹ Vinh, PGS.TS. Hoàng Xuân Huấn vàTS. Bùi Quang Minh (hiện đang công tác tại Trung tâm Tin sinh Tích hợp Vienna,University of Vienna và Medical University Vienna, Vienna, nước Cộng hòa Áo). Tôi xin bày tỏ lòng biết ơn sâu sắc tới PGS.TS. Hoàng Xuân Huấn, thầy đã giớithiệu cho tôi nhiều kiến thức bổ ích về toán và học máy thống kê và về nhiều bài toánứng dụng khác nhau thông qua nhóm seminar học máy và tin sinh; giúp tôi định vịđược bài toán của mình trong tổng thể. Thầy cũng đã nhiệt tình hướng dẫn tôi tìmhiểu một số bài toán tin sinh và tạo điều kiện cho tôi tham gia nhóm làm việc tại Việnnghiên cứu cao cấp về toán. Tôi xin cảm ơn PGS.TS. Lê Sỹ Vinh, thầy đã tạo điều kiện tốt nhất để tôi kếtnối với nhóm chuyên gia nghiên cứu ở Trung tâm Tin sinh Tích hợp Vienna; đồngthời luôn theo sát góp ý, lên kế hoạch, đốc thúc và động viên tôi làm nghiên cứu. Tôi xin cảm ơn TS. Bùi Quang Minh, thầy đã giới thiệu cho tôi bài toán chínhtrong luận án này và hướng dẫn tôi vượt qua rất nhiều khó khăn khi triển khai cáchướng giải quyết khác nhau cho bài toán, cũng như khi viết bài. Tôi cũng xin cảm ơn tới các Thầy, Cô thuộc Khoa Công nghệ Thông tin, TrườngĐại học Công nghệ, Đại học Quốc gia Hà Nội đã tạo mọi điều kiện thuận lợi giúp tôitrong quá trình làm nghiên cứu sinh. Cuối cùng, tôi xin gửi lời cảm ơn sâu sắc tới gia đình và bạn bè, những ngườiđã cho tôi điểm tựa vững chắc để tôi hoàn thành tốt luận án này. 2 MỤC LỤCLời cam đoan ............................................................................................................... 1Lời cảm ơn .................................................................................................................. 2MỤC LỤC ................................................................................................................... 3Danh mục các ký hiệu và chữ viết tắt ......................................................................... 7Danh mục các bảng ..................................................................................................... 9Danh mục các hình vẽ, đồ thị .................................................................................... 10Danh mục các thuật toán ........................................................................................... 13MỞ ĐẦU ................................................................................................................. 14Chương 1 BÀI TOÁN XÂY DỰNG CÂY BOOTSTRAP TIẾN HÓA .................. 20 1.1. Một số khái niệm cơ bản .............................................................................. 20 1.1.1 Thông tin di truyền ............................................................................ 20 1.1.2 Sắp hàng đa chuỗi ............................................................................. 22 1.1.3 Cây tiến hóa....................................................................................... 23 1.2 Tổng quan phân tích tiến hóa ....................................................................... 25 1.3 Xây dựng cây tiến hóa ................................................................................. 26 1.3.1 Phát biểu bài toán .............................................................................. 26 1.3.2 Tiêu chuẩn tiết kiệm nhất (maximum parsimony – MP) .................. 27 1.3.3 Mô hình hóa quá trình biến đổi nucleotide . ...