Luận án tiến sĩ Hoàng Thị Điệp: Các phương pháp nhanh xây dựng cây bootstrap tiến hóa

Khám phá các phương pháp nhanh xây dựng cây bootstrap tiến hóa trong luận án tiến sĩ, cung cấp kiến thức và ứng dụng trong nghiên cứu sinh học.

• Tác giả: Hoàng Thị Điệp
• Người hướng dẫn: PGS. Lê Sỹ Vinh
• Trường học: Trường Đại học Công nghệ, Đại học Quốc gia Hà Nội
• Chuyên ngành: Công nghệ Thông tin
• Đề tài: Các Phương Pháp Nhanh Xây Dựng Cây Bootstrap Tiến Hóa
• Loại tài liệu: Luận án Tiến sĩ
• Năm xuất bản: 2019
• Địa điểm: Hà Nội

Mục lục chi tiết

• LỜI CAM ĐOAN
• 1. CHƯƠNG 1: BÀI TOÁN XÂY DỰNG CÂY BOOTSTRAP TIẾN HÓA
• 1.1. Một số khái niệm cơ bản
• 1.2. Thông tin di truyền
• 1.3. Sắp hàng đa chuỗi
• 1.4. Tổng quan phân tích tiến hóa
• 1.5. Xây dựng cây tiến hóa
• 1.5.1. Phát biểu bài toán
• 1.5.2. Tiêu chuẩn tiết kiệm nhất (maximum parsimony – MP)
• 1.5.3. Mô hình hóa quá trình biến đổi nucleotide
• 1.5.4. Tiêu chuẩn hợp lý nhất (maximum likelihood – ML)
• 1.5.5. Một số kỹ thuật biến đổi cục bộ trên cây dùng trong xây dựng cây tiến hóa
• 1.6. Giới thiệu phương pháp bootstrap trong thống kê
• 1.7. Xây dựng cây bootstrap tiến hóa
• 1.7.1. Phát biểu bài toán
• 1.7.2. Các tiêu chí đánh giá
• 1.7.3. Các phương pháp hiện tại
• 1.8. Kết luận chương
• 2. CHƯƠNG 2: PHƯƠNG PHÁP UFBOOT2 GIẢI NHANH BÀI TOÁN XÂY DỰNG CÂY BOOTSTRAP TIẾN HÓA THEO TIÊU CHUẨN HỢP LÝ NHẤT
• 2.1. Giới thiệu về xây dựng cây tiến hóa theo tiêu chuẩn hợp lý nhất
• 2.2. Thuật toán pruning để tính likelihood cây
• 2.2.1. Tính likelihood cho một cây theo định nghĩa
• 2.2.2. Tính likelihood cho một cây theo thuật toán pruning
• 2.3. Thuật toán UFBoot
• 2.4. Thuật toán IQPNNI
• 2.5. Công thức RELL
• 2.6. Giả mã của thuật toán UFBoot
• 2.7. Thuật toán pruning ước lượng độ dài cạnh
• 2.8. Đề xuất thuật toán UFBoot2
• 2.8.1. Cải tiến tốc độ
• 2.8.2. Cải tiến để xử lý đỉnh đa phân tốt hơn
• 2.8.3. Cải tiến để giảm ảnh hưởng của vi phạm mô hình
• 2.9. Cải tiến mở rộng để phân tích sắp hàng các bộ gen
• 2.10. Thực nghiệm và kết quả
• 2.10.1. Thời gian tính toán
• 2.10.2. Tỉ lệ dương tính giả
• 2.10.3. Độ chuẩn xác của ước lượng bootstrap
• 2.10.4. Khả năng phân tích sắp hàng bộ gen
• 2.11. Kết luận chương
• 3. CHƯƠNG 3: PHƯƠNG PHÁP MỚI MPBOOT GIẢI NHANH BÀI TOÁN XÂY DỰNG CÂY BOOTSTRAP TIẾN HÓA THEO TIÊU CHUẨN TIẾT KIỆM NHẤT
• 3.1. Xây dựng cây tiến hóa theo tiêu chuẩn MP
• 3.2. Đề xuất thuật toán MPBoot
• 3.2.1. Lấy mẫu cây trên sắp hàng gốc
• 3.2.2. Lấy mẫu điểm MP (Resampling parsimony score - REPS)
• 3.2.3. Tăng tốc tính toán REPS
• 3.2.4. Thuật toán MPBoot
• 3.3. Thiết kế thực nghiệm
• 3.3.1. Dữ liệu mô phỏng
• 3.3.2. Dữ liệu thực
• 3.4. Kết quả thực nghiệm
• 3.4.1. Thời gian tính toán
• 3.4.2. Khả năng tìm được cây có điểm MP tốt nhất
• 3.4.3. Độ chuẩn xác của ước lượng bootstrap
• 3.5. Bình luận về kết quả
• 3.6. Kết luận chương
• DANH MỤC CÁC CÔNG TRÌNH KHOA HỌC CỦA TÁC GIẢ LIÊN QUAN ĐẾN LUẬN ÁN
• TÀI LIỆU THAM KHẢO
• PHỤ LỤC 1: BẢNG BỔ SUNG
• PHỤ LỤC 2: CÁC CÂU LỆNH TNT VÀ PAUP*

Tóm tắt

I. Tổng quan về cây bootstrap tiến hóa và ứng dụng của nó

Cây bootstrap tiến hóa là một công cụ quan trọng trong phân tích tiến hóa, giúp xác định mối quan hệ giữa các loài dựa trên dữ liệu di truyền. Phương pháp này cho phép các nhà nghiên cứu đánh giá độ tin cậy của các cây tiến hóa được xây dựng từ dữ liệu sinh học phân tử. Cây bootstrap tiến hóa được xây dựng thông qua việc lấy mẫu có hoàn lại từ dữ liệu gốc, tạo ra nhiều bản sao để phân tích. Điều này giúp tăng cường độ chính xác và độ tin cậy của các kết quả phân tích. Cây bootstrap không chỉ được sử dụng trong sinh học mà còn có ứng dụng trong y học, sinh thái học và nhiều lĩnh vực khác.

1.1. Khái niệm cơ bản về cây bootstrap tiến hóa

Cây bootstrap tiến hóa là một phương pháp thống kê được sử dụng để đánh giá độ tin cậy của các cây tiến hóa. Phương pháp này dựa trên việc lấy mẫu có hoàn lại từ dữ liệu gốc, cho phép xây dựng nhiều cây khác nhau từ cùng một bộ dữ liệu. Mỗi cây được xây dựng sẽ cung cấp thông tin về mối quan hệ tiến hóa giữa các loài, từ đó giúp các nhà nghiên cứu đưa ra những kết luận chính xác hơn về lịch sử tiến hóa.

1.2. Ứng dụng của cây bootstrap trong nghiên cứu sinh học

Cây bootstrap tiến hóa có nhiều ứng dụng trong nghiên cứu sinh học, đặc biệt trong việc phân tích mối quan hệ giữa các loài. Nó giúp các nhà khoa học xác định các loài có liên quan gần gũi và phát hiện các biến thể di truyền. Ngoài ra, cây bootstrap còn được sử dụng trong nghiên cứu dịch tễ học để theo dõi sự phát triển của các chủng virus và vi khuẩn, từ đó đưa ra các biện pháp phòng ngừa hiệu quả.

II. Thách thức trong xây dựng cây bootstrap tiến hóa

Mặc dù cây bootstrap tiến hóa mang lại nhiều lợi ích, nhưng việc xây dựng chúng cũng gặp phải nhiều thách thức. Một trong những thách thức lớn nhất là thời gian tính toán. Việc phân tích một lượng lớn dữ liệu sinh học có thể tiêu tốn rất nhiều thời gian và tài nguyên tính toán. Hơn nữa, độ chính xác của các cây bootstrap cũng phụ thuộc vào chất lượng của dữ liệu đầu vào. Nếu dữ liệu không chính xác hoặc không đầy đủ, kết quả phân tích sẽ bị ảnh hưởng nghiêm trọng.

2.1. Vấn đề về thời gian tính toán trong phân tích bootstrap

Thời gian tính toán là một trong những thách thức lớn nhất khi xây dựng cây bootstrap tiến hóa. Việc phân tích hàng triệu vị trí di truyền có thể mất nhiều giờ hoặc thậm chí nhiều ngày. Điều này đặc biệt đúng khi sử dụng các phương pháp truyền thống mà không có sự tối ưu hóa. Do đó, cần phát triển các thuật toán nhanh hơn để giảm thiểu thời gian tính toán mà vẫn đảm bảo độ chính xác.

2.2. Ảnh hưởng của chất lượng dữ liệu đến kết quả phân tích

Chất lượng dữ liệu đầu vào có ảnh hưởng lớn đến độ chính xác của cây bootstrap. Dữ liệu không chính xác hoặc thiếu sót có thể dẫn đến việc xây dựng cây không chính xác, từ đó ảnh hưởng đến các kết luận được rút ra. Việc đảm bảo dữ liệu đầu vào có chất lượng cao là rất quan trọng để đạt được kết quả phân tích đáng tin cậy.

III. Phương pháp xây dựng cây bootstrap tiến hóa hiệu quả

Để xây dựng cây bootstrap tiến hóa hiệu quả, nhiều phương pháp đã được phát triển. Các phương pháp này không chỉ giúp giảm thời gian tính toán mà còn cải thiện độ chính xác của các cây được xây dựng. Một số phương pháp nổi bật bao gồm UFBoot và MPBoot, được thiết kế để tối ưu hóa quy trình xây dựng cây bootstrap. Những phương pháp này đã được chứng minh là có khả năng xử lý các bộ dữ liệu lớn một cách nhanh chóng và hiệu quả.

3.1. Phương pháp UFBoot trong xây dựng cây bootstrap

UFBoot là một trong những phương pháp nhanh nhất để xây dựng cây bootstrap tiến hóa. Phương pháp này sử dụng các thuật toán tối ưu hóa để giảm thiểu thời gian tính toán mà vẫn đảm bảo độ chính xác cao. UFBoot đã được áp dụng rộng rãi trong nhiều nghiên cứu và cho thấy hiệu quả vượt trội so với các phương pháp truyền thống.

3.2. Phương pháp MPBoot và ưu điểm của nó

MPBoot là một phương pháp khác được sử dụng để xây dựng cây bootstrap tiến hóa. Phương pháp này tập trung vào việc tối ưu hóa quy trình lấy mẫu và tính toán điểm số cho cây. MPBoot cho phép xây dựng cây bootstrap một cách nhanh chóng và chính xác, giúp các nhà nghiên cứu tiết kiệm thời gian và tài nguyên.

IV. Kết quả nghiên cứu và ứng dụng thực tiễn của cây bootstrap

Kết quả nghiên cứu từ việc xây dựng cây bootstrap tiến hóa đã cho thấy nhiều ứng dụng thực tiễn trong các lĩnh vực khác nhau. Các cây bootstrap không chỉ giúp xác định mối quan hệ tiến hóa giữa các loài mà còn hỗ trợ trong việc phát hiện các biến thể di truyền có thể ảnh hưởng đến sức khỏe con người. Hơn nữa, cây bootstrap còn được sử dụng trong nghiên cứu dịch tễ học để theo dõi sự phát triển của các chủng virus và vi khuẩn, từ đó đưa ra các biện pháp phòng ngừa hiệu quả.

4.1. Ứng dụng trong nghiên cứu dịch tễ học

Cây bootstrap tiến hóa đã được sử dụng trong nghiên cứu dịch tễ học để theo dõi sự phát triển của các chủng virus. Việc phân tích cây tiến hóa giúp các nhà khoa học dự đoán các chủng virus có khả năng gây dịch trong tương lai, từ đó đưa ra các biện pháp phòng ngừa kịp thời.

4.2. Ứng dụng trong phát hiện biến thể di truyền

Cây bootstrap cũng được sử dụng để phát hiện các biến thể di truyền có thể ảnh hưởng đến sức khỏe con người. Việc phân tích mối quan hệ tiến hóa giữa các loài giúp các nhà nghiên cứu xác định các gen có liên quan đến các bệnh di truyền, từ đó mở ra hướng nghiên cứu mới trong y học.

V. Kết luận và triển vọng tương lai của cây bootstrap tiến hóa

Cây bootstrap tiến hóa đã chứng minh được giá trị của mình trong nghiên cứu sinh học và y học. Tuy nhiên, vẫn còn nhiều thách thức cần phải vượt qua để tối ưu hóa quy trình xây dựng cây bootstrap. Trong tương lai, việc phát triển các thuật toán nhanh hơn và chính xác hơn sẽ giúp cải thiện đáng kể hiệu quả của phương pháp này. Hơn nữa, việc tích hợp công nghệ mới như trí tuệ nhân tạo vào quy trình phân tích cũng sẽ mở ra nhiều cơ hội mới cho nghiên cứu.

5.1. Triển vọng phát triển thuật toán mới

Trong tương lai, việc phát triển các thuật toán mới để xây dựng cây bootstrap tiến hóa sẽ là một hướng đi quan trọng. Các thuật toán này cần phải nhanh hơn và chính xác hơn, giúp các nhà nghiên cứu tiết kiệm thời gian và tài nguyên trong quá trình phân tích.

5.2. Tích hợp công nghệ mới vào phân tích cây bootstrap

Việc tích hợp công nghệ mới như trí tuệ nhân tạo vào quy trình phân tích cây bootstrap sẽ mở ra nhiều cơ hội mới cho nghiên cứu. Công nghệ này có thể giúp tự động hóa quy trình phân tích, từ đó nâng cao độ chính xác và hiệu quả của các kết quả nghiên cứu.

Trích đoạn nội dung tài liệu

ĐẠ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 NHANH XÂY DỰNG CÂY BOOTSTRAP TIẾN HÓA LUẬN ÁN TIẾN SĨ CÔNG NGHỆ THÔNG TIN Hà Nội – 2019 LUAN VAN CHAT LUONG download : add [e-mail] ĐẠ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 NHANH XÂY DỰNG CÂY BOOTSTRAP TIẾN HÓA Chuyên ngành: Khoa học Máy tính Mã số: 9480101.01 LUẬN ÁN TIẾN SĨ CÔNG NGHỆ THÔNG TIN NGƯỜI HƯỚNG DẪN KHOA HỌC: 1. Lê Sỹ Vinh 2. Hoàng Xuân Huấn Hà Nội – 2019 LUAN VAN CHAT LUONG download : add [e-mail] 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ả được viế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 ai công bố trong các công trình nào khác. Tác giả 1 LUAN VAN CHAT LUONG download : add [e-mail] 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. Lê Sỹ Vinh, PGS. 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. Hoàng Xuân Huấn, thầy đã giới thiệ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ìm hiể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ện nghiên cứu cao cấp về toán. Tôi xin cảm ơn PGS. Lê Sỹ Vinh, thầy đã tạo điều kiện tốt nhất để tôi kết nối với nhóm chuyên gia nghiên cứu ở Trung tâm Tin sinh Tích hợp Vienna; đồng thờ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ính trong 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ác hướ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ôi trong 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 LUAN VAN CHAT LUONG download : add [e-mail] MỤC LỤC Lời cam đoan . 3 Danh mục các ký hiệu và chữ viết tắt . 7 Danh mục các bảng . 9 Danh mục các hình vẽ, đồ thị . 10 Danh mục các thuật toán . 14 Chương 1 BÀI TOÁN XÂY DỰNG CÂY BOOTSTRAP TIẾN HÓA . Một số khái niệm cơ bản .1 Thông tin di truyền .2 Sắp hàng đa chuỗi .2 Tổng quan phân tích tiến hóa .3 Xây dựng cây tiến hóa .1 Phát biểu bài toán .2 Tiêu chuẩn tiết kiệm nhất (maximum parsimony – MP) .3 Mô hình hóa quá trình biến đổi nucleotide .4 Tiêu chuẩn hợp lý nhất (maximum likelihood – ML) .5 Một số kỹ thuật biến đổi cục bộ trên cây dùng trong xây dựng cây tiến hóa .4 Giới thiệu phương pháp bootstrap trong thống kê . 36 3 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.5 Xây dựng cây bootstrap tiến hóa.2 Phát biểu bài toán .3 Các tiêu chí đánh giá .4 Các phương pháp hiện tại.6 Kết luận chương . 48 Chương 2 PHƯƠNG PHÁP UFBOOT2 GIẢI NHANH BÀI TOÁN XÂY DỰNG CÂY BOOTSTRAP TIẾN HÓA THEO TIÊU CHUẨN HỢP LÝ NHẤT .1 Giới thiệu về xây dựng cây tiến hóa theo tiêu chuẩn hợp lý nhất.2 Thuật toán pruning để tính likelihood cây .1 Tính likelihood cho một cây theo định nghĩa .2 Tính likelihood cho một cây theo thuật toán pruning .3 Thuật toán UFBoot.2 Thuật toán IQPNNI .3 Công thức RELL .4 Giả mã của thuật toán UFBoot .5 Thuật toán pruning ước lượng độ dài cạnh .4 Đề xuất thuật toán UFBoot2 .1 Cải tiến tốc độ .2 Cải tiến để xử lý đỉnh đa phân tốt hơn .3 Cải tiến để giảm ảnh hưởng của vi phạm mô hình . 67 4 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.4 Cải tiến mở rộng để phân tích sắp hàng các bộ gen .5 Thực nghiệm và kết quả .1 Thời gian tính toán .2 Tỉ lệ dương tính giả .3 Độ chuẩn xác của ước lượng bootstrap .4 Khả năng phân tích sắp hàng bộ gen.6 Kết luận chương . 76 Chương 3 PHƯƠNG PHÁP MỚI MPBOOT GIẢI NHANH BÀI TOÁN XÂY DỰNG CÂY BOOTSTRAP TIẾN HÓA THEO TIÊU CHUẨN TIẾT KIỆM NHẤT .2 Xây dựng cây tiến hóa theo tiêu chuẩn MP .3 Đề xuất thuật toán MPBoot.1 Lấy mẫu cây trên sắp hàng gốc .2 Lấy mẫu điểm MP (Resampling parsimony score - REPS) .3 Tăng tốc tính toán REPS .4 Thuật toán MPBoot .4 Thiết kế thực nghiệm .1 Dữ liệu mô phỏng.2 Dữ liệu thực .5 Kết quả thực nghiệm .1 Thời gian tính toán .2 Khả năng tìm được cây có điểm MP tốt nhất. 89 5 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.3 Độ chuẩn xác của ước lượng bootstrap .6 Bình luận về kết quả.7 Kết luận chương . 101 DANH MỤC CÁC CÔNG TRÌNH KHOA HỌC CỦA TÁC GIẢ LIÊN QUAN ĐẾN LUẬN ÁN . 104 TÀI LIỆU THAM KHẢO . 105 PHỤ LỤC 1: BẢNG BỔ SUNG . 117 PHỤ LỤC 2: CÁC CÂU LỆNH TNT VÀ PAUP* . Script TNT để thực hiện fast-TNT với ma trận chi phí đều . Script TNT để thực hiện intensive-TNT với ma trận chi phí đều . Các lệnh TNT làm việc với ma trận chi phí không đều . Lệnh bootstrap trong PAUP* sử dụng chiến lược giống fast-TNT với ma trận chi phí đều . 120 6 LUAN VAN CHAT LUONG download : add [e-mail] Danh mục các ký hiệu và chữ viết tắt thuật toán do Vinh và cộng sự [49] đề xuất để giải nhanh xây IQPNNI dựng cây tiến hóa theo tiêu chuẩn ML (Important Quartet Puzzling and NNI Optimization) ML tiêu chuẩn hợp lý nhất (Maximum Likelihood) MP tiêu chuẩn tiết kiệm nhất (Maximum Parsimony) phương pháp mới luận án đề xuất để giải nhanh bài toán xây MPBoot dựng cây bootstrap tiến hóa theo tiêu chuẩn MP MSA sắp hàng đa chuỗi (Multiple Sequence Alignment) NNI hoán đổi hàng xóm gần nhất (Nearest-Neighbor Interchange) phương pháp bootstrap nhanh trong RAxML (RAxML Rapid RBS Bootstrap) lấy mẫu ước lượng log-likelihood (Resampling Estimated RELL Log-Likelihoods) REPS lấy mẫu điểm MP (REsampling Parsimony Score) SBS phương pháp bootstrap chuẩn (Standard BootStrap) SPR cắt và ghép cây con (Subtree Pruning and Regrafting) TBR chặt đôi và nối lại (Tree Bisection and Reconnection). phương pháp do Minh và cộng sự [56] đề xuất để giải nhanh UFBoot bài toán xây dựng cây bootstrap tiến hóa theo tiêu chuẩn ML (UltraFast Bootstrap approximation) phương pháp luận án đề xuất để giải nhanh bài toán xây UFBoot2 dựng cây bootstrap tiến hóa theo tiêu chuẩn ML 7 LUAN VAN CHAT LUONG download : add [e-mail] thuật toán UFBoot2 tích hợp bước tinh chỉnh tối ưu để giảm UFBoot2+NNI ảnh hưởng của vi phạm mô hình 8 LUAN VAN CHAT LUONG download : add [e-mail] Danh mục các bảng Bảng 1. Danh sách 64 codon. Mỗi codon mã hoá một axít amin. Danh sách 20 axít amin. Ví dụ minh họa (A) ma trận chí phí đều và (B) ma trận chi phí không đều cho dữ liệu DNA. Các tham số tự do của một số mô hình biến đổi nucleotide điển hình. Thông tin bộ dữ liệu thực từ TreeBASE. Tóm tắt giá trị hỗ trợ bootstrap cho cạnh đúng không tồn tại của UFBoot2 khi bật và tắt cải tiến xử lý đỉnh đa phân trên dữ liệu mô phỏng từ cây đúng hình sao. Thông tin bộ dữ liệu DNA mô phỏng PANDIT. Thông tin bộ dữ liệu mô phỏng PANDIT (loại trừ các sắp hàng có phân tích TNT hoặc PAUP* không hoàn thành). Tổng thời gian chạy (giờ) của 5 phương pháp trên 114 sắp hàng TreeBASE. Con số in đậm ứng với phương pháp nhanh nhất theo ma trận chi phí tương ứng. Các dòng lệnh dùng để chạy các thuật toán của IQ-TREE và RAxML dùng trong Chương 2 luận án.117 9 LUAN VAN CHAT LUONG download : add [e-mail] Danh mục các hình vẽ, đồ thị Hình 0. Ví dụ minh họa đầu ra bài toán xây dựng cây tiến hóa và bài toán xây dựng cây bootstrap tiến hóa trong phân tích tiến hóa cho 4 loài. Minh họa một sắp hàng đa chuỗi axít amin của bốn loài linh trưởng. Một ví dụ về cây tiến hóa giữa bốn loài linh trưởng: (A) dạng cây nhị phân có gốc và (B) dạng cây nhị phân không gốc. Minh họa cách tìm điểm MP cho cấu trúc cây 1 bằng cách khảo sát 4 cách gán đỉnh trong. Minh họa đa biến đổi trên cây gồm 1 đỉnh cha và 2 đỉnh con. Điểm MP bằng 1 trong khi số biến đổi thực sự là 3. Tần suất tương đối của biến đổi giữa các nucleotide. Một cây 𝑇𝑇 đơn giản để minh họa cách tính likelihood của cây tại một vị trí sắp hàng. Ba kỹ thuật xáo trộn cấu trúc cây (NNI, SPR và TBR) trên cạnh tô đậm của cây ban đầu. Với SPR và TBR, tất cả các cặp cạnh đánh dấu bằng vòng tròn nhỏ trên 2 cây con sẽ được nối với nhau (các đường kẻ đứt), trừ phép nối 2 hình tròn đen với nhau vì nó sẽ tạo ra cây ban đầu. Minh họa phân bố của trung vị mẫu tìm bằng phương pháp bootstrap. Minh họa 3 bước làm bootstrap chuẩn phi tham số. Sắp hàng gốc có 4 taxa với 10 vị trí sắp hàng. Trong ví dụ này, ta làm bootstrap tiến hóa với 3 bản sao (𝐵𝐵 = 3). Phân tích thực tế thường cần tới 1000 bản sao bootstrap (𝐵𝐵 = 1000). Minh họa khái niệm độ chuẩn xác và khả năng lặp lại khi làm bootstrap với 𝐵𝐵 bản sao trên sắp hàng gốc 1.43 10 LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Ví dụ đồ thị thể hiện độ chuẩn xác của phương pháp bootstrap lạc quan (màu đỏ), phương pháp bảo thủ (màu xanh), phương pháp không chệch (màu đen). Ta chỉ phân tích phần bên phải của đồ thị (x >= 70). Một cây biết độ dài cạnh và dữ liệu tại một vị trí đơn lẻ trên sắp hàng. Ví dụ này để minh họa tính likelihood bằng định nghĩa và bằng thuật toán pruning. Đỉnh gốc là u. Một cây T để minh họa thuật toán pruning và pruning nhanh. Nó được định gốc ngẫu nhiên tại điểm r trên cạnh (a,b). Gốc cách 2 đầu cạnh khoảng tương ứng là 𝑡𝑡𝑡𝑡 và 𝑡𝑡𝑡𝑡. Sơ đồ khối thuật toán IQPNNI.