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

Chương 1 BÀI TOÁN XÂY DỰNG CÂY BOOTSTRAP TIẾN HÓA 1. Một số khái niệm cơ bản Phần này của luận án sẽ trình bày các khái niệm cơ bản trong lĩnh vực phân tích quan hệ tiến hóa dựa trên dữ liệu sinh học phân tử: thông tin di truyền, sắp hàng đa chuỗi, cây tiến hóa.1 Thông tin di truyền Kiểu hình của sinh vật sống luôn là kết quả của thông tin di truyền (mà sinh vật mang và truyền cho thế hệ kế tiếp) và tương tác với môi trường. Vì vậy, để nghiên cứu về tiến hóa, ta cần tìm hiểu về biến đổi trong thông tin di truyền của sinh vật [50]. Bộ gen của hầu hết các sinh vật là DNA (axít deoxyribonucleic), trong khi một số virus có bộ gen RNA (axít ribonucleic).

DNA là một phân tử mã hóa bản đồ thiết kế di truyền của sinh vật. Nói cách khác, DNA chứa tất cả các thông tin để tạo ra và duy trì một sinh vật. DNA được cấu tạo từ nhiều phân tử nhỏ gọi là các nucleotide. Có 4 loại nucleotide là: adenine (A), cytosine (C), guanine (G) và thymine (T) được xếp thành 2 nhóm purin (gồm A và G) và pyrimidine (gồm C và T) dựa trên các điểm tương đồng về cấu trúc hóa học.

Các nucleotide kết hợp với nhau thành một mạch dài nhờ các liên kết hóa học để tạo thành một chuỗi nucleotide (còn gọi là chuỗi polynucleotide). DNA có cấu tạo gồm hai chuỗi nucleotide, trong đó các nucleotide giữa 2 chuỗi liên kết với nhau bằng liên kết hydrogen theo nguyên tắc bổ sung: A với T và G với C [1]. Do tính chất đặc biệt của ghép cặp bổ sung, mỗi chuỗi trong 2 chuỗi polynucleotide nói trên có chứa đầy đủ các thông tin mang trong chuỗi còn lại. RNA được tổng hợp từ DNA nhờ quá trình phiên mã theo nguyên tắc bổ sung.

Trong RNA, thymine được thay bằng uracil (U). 20 LUAN VAN CHAT LUONG download : add [e-mail] Axít amin là một hợp chất hữu cơ được cấu tạo bởi ba thành phần: nhóm amin (-NH2), nhóm cacboxyl (-COOH) và nguyên tử cacbon trung tâm đính với 1 nguyên tử hyđrô và nhóm biến đổi R quyết định tính chất của axít amin [1,11]. Các axít amin kết hợp với nhau thành một mạch dài nhờ các liên kết peptide (còn gọi là chuỗi polypeptide) để tạo thành một chuỗi axít amin hay còn gọi là protein. Các chuỗi này có thể xoắn cuộn hoặc gấp theo nhiều cách để tạo thành các bậc cấu trúc không gian khác nhau của protein [2].

Mối quan hệ giữa nucleotide và axít amin được thể hiện qua quá trình tổng hợp protein. Trong một chuỗi nucleotide mã hóa protein, mỗi chuỗi ba nucleotide liên tiếp được gọi là một codon. Mỗi codon có thể mã hóa một axít amin hoặc là tín hiệu bắt đầu hoặc kết thúc của một quá trình tổng hợp protein [50]. Có tất cả 64 codon, trong đó có 61 codon mã hóa cho các axít amin, 3 codon còn lại được gọi là stop-codon (xem thêm Bảng 1.

Danh sách 64 codon. Mỗi codon mã hoá một axít amin. T C A G Axít Axít Axít Axít Codon Codon Codon Codon amin amin amin amin TTT Phe TCT Ser TAT Tyr TGT Cys T TTC Phe TCC Ser TAC Tyr TGC Cys C T TTA Leu TCA Ser TAA STOP TGA STOP A TTG Leu TCG Ser TAG STOP TGG Trp G CTT Leu CCT Pro CAT His CGT Arg T CTC Leu CCC Pro CAC His CGC Arg C C CTA Leu CCA Pro CAA Gln CGA Arg A CTG Leu CCG Pro CAG Gln CGG Arg G ATT Ile ACT Thr AAT Asn AGT Ser T ATC Ile ACC Thr AAC Asn AGC Ser C A ATA Ile ACA Thr AAA Lys AGA Arg A ATG Met ACG Thr AAG Lys AGG Arg G GTT Val GCT Ala GAT Asp GGT Gly T GTC Val GCC Ala GAC Asp GGC Gly C G GTA Val GCA Ala GAA Glu GGA Gly A GTG Val GCG Ala GAG Glu GGG Gly G 21 LUAN VAN CHAT LUONG download : add [e-mail] Tuy nhiên, do có nhiều codon cùng mã hoá một axít amin nên số axít amin được mã hoá chỉ là 20 [11]. Tên đầy đủ và viết tắt của 20 axít amin được liệt kê đầy đủ trong Bảng 1.

Danh sách 20 axít amin. STT Tên axít amin Tên viết tắt (3 ký tự) Tên viết tắt (1 ký tự) 1 Alanine Ala A 2 Arginine Arg R 3 Asparagine Asn N 4 Aspartic Asp D 5 Cysteine Cys C 6 Glutamine Gln Q 7 Glutamic Glu E 8 Glycine Gly G 9 Histidine His H 10 Isoleucine Ile I 11 Leucine Leu L 12 Lysine Lys K 13 Methionine Met M 14 Phenylalanine Phe F 15 Proline Pro P 16 Serine Ser S 17 Threonine Thr T 18 Tryptophan Trp W 19 Tyrosine Tyr Y 20 Valine Val V 1.2 Sắp hàng đa chuỗi Để xây dựng cây tiến hóa, ta sử dụng các đặc tính tương đồng – là đặc tính ở những sinh vật khác nhau nhưng tương tự nhau bởi chúng được kế thừa từ một tổ tiên chung có đặc tính đó. Trong phân tích tiến hóa dựa trên dữ liệu phân tử sinh học, ta sử dụng các chuỗi nucleotide/axít amin tương đồng 22 LUAN VAN CHAT LUONG download : add [e-mail] Quá trình tiến hóa làm cho các chuỗi phân tử sinh học (nucleotide/axít amin) tương đồng khác nhau về nội dung cũng như độ dài. Sắp hàng đa chuỗi (multiple sequence alignment – MSA) sẽ giúp làm rõ các phép biến đổi giữa các chuỗi phân tử sinh học.

Sắp hàng đa chuỗi có thể được hiểu như một ma trận các phân tử sinh học. Trong đó mỗi hàng chính là một chuỗi phân tử sinh học còn mỗi cột chứa các phân tử sinh học tương đồng của các chuỗi [50] (xem thêm Hình 1. Mỗi cột được gọi là một vị trí sắp hàng. Kích thước của một sắp hàng đa chuỗi được hiểu là số lượng chuỗi có trong sắp hàng đó, còn chiều dài của một sắp hàng đa chuỗi chính là chiều dài của một chuỗi trong sắp hàng.1 là một ví dụ của một sắp hàng đa chuỗi với bốn chuỗi axít amin của bốn loài linh trưởng.

Sắp hàng có chiều dài là 15. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Người E H D - N D E M C Q L K P L P Tinh tinh F H D R - D E M C Q L K P L P Khỉ đột F G R R - D E M C Q L K P L P Đười ươi F G D R - V H M C Q L K P L P Hình 1. Minh họa một sắp hàng đa chuỗi axít amin của bốn loài linh trưởng.3 Cây tiến hóa Cây tiến hóa là một dạng sơ đồ phân nhánh thể hiện mối quan hệ tiến hóa giữa các loài (cũng có thể mở rộng cho các cá thể hay các gen) dựa trên những điểm giống và khác trong thông tin di truyền. Các loài đưa vào phân tích quan hệ tiến hóa được cho là có một tổ tiên chung.

Mối quan hệ tiến hóa giữa các loài thường được biểu diễn bởi một cây nhị phân với cấu trúc như sau: mỗi đỉnh lá của cây biểu diễn một loài hiện tại (cho bởi dữ liệu vào); mỗi đỉnh trong của cây biểu diễn một loài tổ tiên (ta không có thông tin về các loài tổ tiên); mỗi cạnh của cây nối hai đỉnh của cây và biểu diễn mối quan hệ trực tiếp giữa hai loài ở hai đỉnh của cây; độ dài của cạnh nối hai loài trên cây cho biết khoảng cách tiến hóa giữa chúng. Khoảng cách tiến hóa này có thể được biểu diễn bằng thời 23 LUAN VAN CHAT LUONG download : add [e-mail] gian, hay số lượng các biến đổi nucleotide/axít amin giữa hai chuỗi nucleotide/axít amin được sử dụng để so sánh hai loài. Ta thường không có thông tin về các loài tổ tiên, cho nên không xác định được chính xác gốc của cây tiến hóa. Chính vì vậy, cây tiến hóa thường được biểu diễn bằng một cây nhị phân không gốc như minh họa ở Hình 1.

Sau đó, khi có thêm thông tin tiến hóa, ta sẽ dùng một kỹ thuật định gốc, ví dụ như kỹ thuật outgroup: lúc đầu bổ sung vào sắp hàng một chuỗi nucleotide/axít amin của một loài khác xa với nhóm loài đang xét, tới cuối cùng khi đã tìm được cây thì đặt gốc trên cạnh nối với loài này [50]. (A) (B) Người Tinh tinh Khỉ đột Đười ươi Người Khỉ đột Tinh tinh Đười ươi Hình 1. 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. Cây tiến hóa là một thành phần hữu ích trong các lĩnh vực sinh học, tin sinh học và nhân chủng học.

Trong luận án này, nếu không có chú thích thêm thì cây tiến hóa được gọi tắt là cây. Ngoài ra, luận án gọi cây tiến hóa là cấu trúc phân nhánh khi muốn nhấn mạnh việc các cạnh của cây chưa xác định được độ dài mà chỉ thể hiện mối quan hệ liền kề giữa các đỉnh trong cây. Luận án này sẽ bàn nhiều về cạnh trong của cây với vai trò phân hoạch. Đây là đơn vị nhỏ nhất trong quan hệ tiến hóa mà cây thể hiện.

Xét cạnh trong 𝑒𝑒(𝑎𝑎, 𝑏𝑏) thuộc tập cạnh 𝐸𝐸 của cây 𝑇𝑇, cạnh trong 𝑒𝑒 sẽ phân tách tập các lá của cây 𝑇𝑇 ra thành hai tập con 𝐿𝐿𝑎𝑎 |𝐿𝐿𝑏𝑏 , trong đó tập 𝐿𝐿𝑎𝑎 chứa các lá nằm cùng phía với đỉnh 𝑎𝑎; tập 𝐿𝐿𝑏𝑏 chứa các lá nằm cùng phía với đỉnh 𝑏𝑏. Ta gọi 𝐿𝐿𝑎𝑎 |𝐿𝐿𝑏𝑏 là một cách phân hoạch của cây 𝑇𝑇. Lưu ý, 24 LUAN VAN CHAT LUONG download : add [e-mail] hai phân hoạch 𝐿𝐿𝑎𝑎 |𝐿𝐿𝑏𝑏 và 𝐿𝐿𝑏𝑏 |𝐿𝐿𝑎𝑎 được coi là như nhau. Cây trong Hình 1.2B có duy nhất một cạnh trong.

Nó thể hiện rằng “Người” có họ hàng gần với “Tinh tinh” hơn là với “Khỉ đột” và “Đười ươi”.2 Tổng quan phân tích tiến hóa Theo Warnow [90], một quy trình phân tích quan hệ tiến hóa tổng quát và hoàn thiện gồm các bước: (1) Nhà sinh học nhận định câu hỏi nghiên cứu, từ đó lựa chọn các loài và các gen cần phân tích. (2) Thu thập chuỗi phân tử sinh học cho các loài và các gen này, thường là chuỗi DNA. (3) Với mỗi gen, xây dựng sắp hàng đa chuỗi. (4) Với mỗi gen, sử dụng sắp hàng đa chuỗi để xây dựng cây tiến hóa đơn gen.

(5) Tính toán độ hỗ trợ thống kê cho mỗi cạnh trong của cây tiến hóa đơn gen. Cách phổ biến nhất là dùng phương pháp bootstrap phi tham số (non- parametric bootstrap) [15]. Do trong luận án không khảo sát bootstrap có tham số (parametric bootstrap) [15] nên sau đây sẽ gọi tắt phương pháp bootstrap phi tham số là phương pháp bootstrap.