Tổng quan luận án

Tái dựng lịch sử tiến hóa của sinh vật đóng vai trò quan trọng trong việc lý giải các hiện tượng sinh học, hỗ trợ các phát hiện trong y học và dược học, cũng như cung cấp nền tảng cho việc so sánh hệ gen để tìm kiếm gen. Khi dữ liệu giải trình tự thế hệ mới (Next-generation sequencing – NGS) bùng nổ, nhu cầu phân tích các tập dữ liệu sinh học phân tử có kích thước lớn ngày càng gia tăng.

Bài toán xây dựng cây tiến hóa từ sắp hàng đa chuỗi được xếp vào lớp NP-đầy đủ theo tiêu chuẩn tiết kiệm nhất (Maximum Parsimony – MP) và NP-khó theo tiêu chuẩn hợp lý nhất (Maximum Likelihood – ML). Để đánh giá mức độ tin cậy của các nhánh trên cây tiến hóa, phương pháp bootstrap phi tham số do Felsenstein (1985) đề xuất là tiếp cận phổ biến nhất. Phương pháp bootstrap chuẩn (Standard Bootstrap – SBS) đòi hỏi việc xây dựng lại cây tiến hóa độc lập $B$ lần trên $B$ bản sao bootstrap (thông thường $B$ từ 100 đến 1000), khiến thời gian tính toán tăng gấp $B$ lần so với việc dựng một cây gốc. Bên cạnh thách thức về mặt thời gian, SBS còn có xu hướng đưa ra giá trị hỗ trợ thống kê thấp hơn xác suất đúng của cạnh. Đối với tiêu chuẩn ML, các phương pháp hiện tại còn chịu ảnh hưởng bởi hiện tượng vi phạm giả thiết mô hình và hiện tượng đỉnh đa phân. Đối với tiêu chuẩn MP, cộng đồng nghiên cứu vẫn thiếu các giải pháp bootstrap nhanh tương tự như bên ML.

Mục tiêu nghiên cứu của luận án gồm ba nhiệm vụ cụ thể:

  1. 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à phương pháp UFBoot), từ đó đề xuất cải tiến giải quyết các thách thức về 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 đỉnh đa phân.
  2. Nghiên cứu phương pháp chuẩn cho xây dựng cây bootstrap tiến hóa theo tiêu chuẩn MP, từ đó đề xuất phương pháp nhanh mới hiệu quả cho bài toán.
  3. Cài đặt các đề xuất cải tiến cho UFBoot và tích hợp vào hệ thống phần mềm IQ-TREE; xây dựng phần mềm MPBoot cài đặt phương pháp nhanh đề xuất cho tiêu chuẩn MP.

Đối tượng nghiên cứu của luận án là các thuật toán và mô hình toán học giải quyết bài toán xây dựng cây tiến hóa và cây bootstrap tiến hóa theo hai tiêu chuẩn ML và MP. Phạm vi nghiên cứu về mặt dữ liệu bao gồm các bộ dữ liệu mô phỏng được tạo bởi công cụ Seq-Gen và dữ liệu mô phỏng PANDIT (cho cả chuỗi DNA và protein), cùng các bộ dữ liệu sinh học thực tế thu thập từ cơ sở dữ liệu TreeBASE (115 sắp hàng trong phân tích ML và 114 sắp hàng trong phân tích MP). Về mặt mô hình, luận án giới hạn khảo sát trên lớp mô hình biến đổi nucleotide có tính thuận nghịch thời gian (Time-Reversible), mô hình tốc độ biến đổi không đồng nhất phân bố Gamma rời rạc ($+\Gamma$), cùng các dạng ma trận chi phí đều và không đều trong tiêu chuẩn MP.

Tổng quan tài liệu và vị trí của luận án

Quy trình phân tích tiến hóa phân tử tổng quát được Warnow hệ thống hóa thành 7 bước, trong đó bước dựng cây đơn gen và bước xác định độ hỗ trợ thống kê bằng bootstrap phi tham số là trọng tâm gắn kết chặt chẽ. Kỹ thuật bootstrap gốc do Efron (1979, 1986) phát triển trong thống kê nhằm ước lượng thực nghiệm mức độ biến thiên của tham số. Khi ứng dụng vào tiến hóa, Hillis và Bull (1993) đã chứng minh bằng thực nghiệm rằng giá trị hỗ trợ bootstrap nên được hiểu là ước lượng cho xác suất phân hoạch thuộc về cây đúng, đồng thời chỉ ra SBS là phương pháp ước lượng bảo thủ (cho giá trị thấp hơn xác suất đúng của cạnh).

Để giải quyết vấn đề thời gian tính toán của SBS theo tiêu chuẩn ML, nhiều phương pháp tiếp cận nhanh đã được phát triển:

  • Phương pháp Resampling Estimated Log-Likelihoods (RELL) của Kishino và cộng sự (1990), Hasegawa và Kishino (1994) tái sử dụng điểm log-likelihood trên các vị trí sắp hàng gốc để ước lượng điểm likelihood trên bản sao bootstrap.
  • Phương pháp Local Bootstrap Probabilities (LBP) của Adachi và Hasegawa (1996) dùng RELL so sánh 3 cấu trúc hoán đổi hàng xóm gần nhất (NNI).
  • Phương pháp kiểm định tỉ lệ likelihood xấp xỉ aLRT (Anisimova và Gascuel, 2006) và SH-aLRT (Guindon và cộng sự, 2010) cài đặt trong PhyML 3.0, thực hiện kiểm định SH trên 3 cấu trúc NNI mà không tối ưu lại độ dài cạnh và tham số mô hình.
  • Phương pháp Rapid Bootstrap (RBS) của Stamatakis và cộng sự (2008) tích hợp trong RAxML và RAxML-NG (Kozlov và cộng sự, 2019), sử dụng thuật toán Lazy Subtree Rearrangement (LSR) thu gọn để tìm kiếm nhanh trên từng bản sao bootstrap.
  • Các phương pháp lấy mẫu cây như Quartet Puzzling (Strimmer và von Haeseler, 1996) hay phân tích Bayes trong MrBayes (Ronquist và Huelsenbeck, 2003) và BEAST (Drummond và Rambaut, 2007). Tuy nhiên, các phương pháp Bayes có chi phí tính toán lớn và độ hỗ trợ bị suy giảm khi vi phạm mô hình hoặc có đỉnh đa phân.
  • Phương pháp UltraFast Bootstrap (UFBoot) của Minh và cộng sự (2013) kết hợp thuật toán IQPNNI (Vinh và von Haeseler, 2004) để duyệt cây trên sắp hàng gốc và chấm điểm nhanh bằng RELL cho các bản sao bootstrap.

Khoảng trống nghiên cứu mà luận án xác định: Dù UFBoot mang lại tốc độ cao và ước lượng không chệch khi mô hình đúng, phương pháp này vẫn xuất hiện dương tính giả khi cây chứa đỉnh đa phân, suy giảm độ chuẩn xác khi dữ liệu thực tế vi phạm giả thiết mô hình tiến hóa, và chưa tối ưu hóa cho phân tích dữ liệu hệ gen đa phân hoạch. Mặt khác, đối với tiêu chuẩn MP, các công cụ phổ biến như TNT (Goloboff và cộng sự) và PAUP* (Swofford) vẫn chủ yếu dựa vào SBS hoặc các heuristic cơ bản, chưa có giải pháp bootstrap nhanh dựa trên nguyên lý tái lấy mẫu điểm số kết hợp duyệt không gian cây một lần.

Cơ sở lý thuyết và phương pháp nghiên cứu

Luận án dựa trên cơ sở lý thuyết tiến hóa phân tử và lý thuyết mô hình xác suất:

  • Cấu trúc dữ liệu di truyền: Bộ mã di truyền gồm 64 codon (trong đó 61 codon mã hóa cho 20 loại axít amin và 3 stop-codon). Sắp hàng đa chuỗi (MSA) kích thước $n \times m$ ($n$ loài, $m$ vị trí). Cây tiến hóa không gốc với không gian tìm kiếm gồm $S(n) = \prod_{i=3}^n (2i - 5)$ cấu trúc phân nhánh cho $n \ge 3$.
  • Mô hình hóa quá trình biến đổi nucleotide: Biến đổi tại mỗi vị trí được mô hình hóa bằng xích Markov thời gian liên tục với tập trạng thái $\mathcal{E} = {A, C, G, T}$. Ma trận tốc độ biến đổi tức thì $Q = {q_{ij}}$ thỏa mãn $\sum_{j=1}^{|\mathcal{E}|} q_{ij} = 0$. Ma trận xác suất chuyển sau khoảng thời gian $t$ được xấp xỉ qua khai triển Taylor: $P(\Delta t) \approx P(0) + Q\Delta t$.
  • Lớp mô hình thuận nghịch thời gian (Time-Reversible): Gồm các mô hình chuẩn hóa với số lượng tham số tự do khác nhau:
Tên mô hình Số tham số tự do Ràng buộc tham số trong ma trận $Q$
JC69 0 $a=b=c=d=e=f$; $\pi_A=\pi_C=\pi_G=\pi_T=0.25$
K80 1 $a=c=d=f=1$, $b=e=k$; $\pi_A=\pi_C=\pi_G=\pi_T=0.25$
F81 3 $a=b=c=d=e=f=1$; $\pi_A, \pi_C, \pi_G, \pi_T$ tự do
HKY85 / F84 4 $a=c=d=f=1$, $b=e=k$; $\pi_A, \pi_C, \pi_G, \pi_T$ tự do
TN93 5 $a=c=d=f$, $b=e$; $\pi_A, \pi_C, \pi_G, \pi_T$ tự do
GTR 8 $a, b, c, d, e$ ($a+b+c+d+e+f=1$); $\pi_A, \pi_C, \pi_G$ tự do
  • Tốc độ biến đổi không đồng nhất: Sử dụng phân bố Gamma rời rạc ($+\Gamma$) với tham số hình dạng $\alpha$ xấp xỉ qua $k$ lớp tốc độ (Yang, 1994).
  • Hàm mục tiêu và giải thuật tìm kiếm: Tính likelihood theo thuật toán pruning của Felsenstein (1981); tính điểm MP qua thuật toán Sankoff (1974) cho ma trận chi phí không đều hoặc thuật toán Fitch cho ma trận chi phí đều; các phép biến đổi cây cục bộ gồm NNI, SPR và TBR.
  • Phương pháp đánh giá thực nghiệm: Đo tổng thời gian tính toán trên cùng phần cứng; đánh giá độ chuẩn xác ước lượng bootstrap $f_Z(x)$ bằng tỷ lệ phần trăm số cạnh đúng trên tổng số cạnh nhận giá trị hỗ trợ $x%$ thông qua việc sinh dữ liệu mô phỏng từ cây đúng bằng Seq-Gen.

Nội dung chính theo từng chương

Chương 1: Bài toán xây dựng cây bootstrap tiến hóa

Chương này thiết lập nền tảng lý thuyết và định nghĩa hình thức cho bài toán. Tác giả phân tích cấu trúc dữ liệu sinh học phân tử, cơ chế mã hóa từ 64 codon thành 20 axít amin, và vai trò của sắp hàng đa chuỗi trong việc xác định các vị trí tương đồng. Cây tiến hóa được biểu diễn dưới dạng cây nhị phân không gốc, trong đó mỗi cạnh trong $e(a, b)$ tương ứng với một phân hoạch tập đỉnh lá $L_a | L_b$.

Bài toán tối ưu hóa cây tiến hóa được phân tích theo hai hướng tiếp cận:

  1. Tiêu chuẩn tiết kiệm nhất (MP): Cực tiểu hóa tổng số biến đổi trên toàn bộ các vị trí sắp hàng. Tác giả phân biệt rõ các vị trí hằng (điểm MP bằng 0), vị trí singleton (điểm MP bằng 1), cũng như sự khác biệt giữa ma trận chi phí đều (biến đổi giữa mọi trạng thái có trọng số là 1) và ma trận chi phí không đều (áp dụng thuật toán Sankoff với chi phí thay đổi theo từng cặp trạng thái).
  2. Tiêu chuẩn hợp lý nhất (ML): Cực đại hóa hàm log-likelihood thông qua mô hình Markov và ma trận xác suất chuyển trạng thái. Tác giả trình bày các kỹ thuật tìm kiếm cục bộ (NNI, SPR, TBR) nhằm khảo sát không gian $S(n)$ cấu trúc cây ứng viên.

Chương 1 cũng trình bày kỹ thuật bootstrap phi tham số: từ sắp hàng gốc $n \times m$, lấy mẫu có hoàn lại $m$ cột để tạo ra $B$ bản sao bootstrap, xây dựng cây trên từng bản sao và tính tỷ lệ xuất hiện của các phân hoạch để gán giá trị hỗ trợ bootstrap. Độ chuẩn xác của phương pháp $Z$, ký hiệu $f_Z(x)$, được phân tích thông qua vị trí của đường cong thực nghiệm so với đường chéo không chệch nối điểm (0; 0) và (100; 100), tập trung vào vùng có ý nghĩa thực tế ($x \ge 70%$). Phần cuối chương điểm lại các phương pháp tính nhanh gồm RELL, LBP, aLRT, SH-aLRT, RBS và UFBoot.

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

Chương 2 trình bày chi tiết thuật toán pruning của Felsenstein và cơ chế hoạt động của thuật toán UFBoot gốc. Trên cơ sở đó, tác giả chỉ ra các điểm nghẽn tính toán và đề xuất phiên bản nâng cấp UFBoot2 với bốn cải tiến:

  1. Cải tiến tốc độ bằng thuật toán pruning nhanh: Tận dụng tính chất đối xứng của ma trận chuyển trạng thái trong các mô hình tiến hóa thuận nghịch thời gian, kết hợp tối ưu hóa mã nguồn để giảm thiểu số phép tính số học dấu phẩy động khi ước lượng độ dài cạnh.
  2. Cải tiến xử lý đỉnh đa phân: Thiết kế cơ chế kiểm soát nhằm ngăn chặn việc thuật toán gán giá trị hỗ trợ giả tạo cho các cạnh không tồn tại khi cấu trúc tiến hóa thực tế có dạng đa phân (phân nhánh hình sao), từ đó triệt tiêu tỉ lệ dương tính giả.
  3. Cải tiến giảm ảnh hưởng của vi phạm mô hình (UFBoot2+NNI): Đề xuất tích hợp thêm bước tinh chỉnh tối ưu hóa NNI sau quá trình ước lượng RELL. Khi dữ liệu thực tế không hoàn toàn tuân theo các giả thiết phân bố của mô hình tiến hóa, bước tinh chỉnh này giúp điều chỉnh lại cây bootstrap, duy trì độ chuẩn xác của giá trị hỗ trợ.
  4. Cải tiến mở rộng phân tích sắp hàng bộ gen: Hỗ trợ phân tích dữ liệu đa gen với mô hình phân hoạch edge-unlinked thông qua ba chiến lược lấy mẫu bootstrap: lấy mẫu theo vị trí (site-resampling), lấy mẫu theo gen (gene-resampling), và kết hợp gen-vị trí (gene-site resampling).

Kết quả thực nghiệm trên 115 bộ dữ liệu TreeBASE cho thấy:

  • UFBoot2 đạt tốc độ nhanh hơn SBS từ hàng chục đến hàng trăm lần, nhanh hơn RBS của RAxML trung bình từ 3 đến 10 lần, đồng thời nhanh hơn đáng kể so với phiên bản UFBoot gốc.
  • Về độ chuẩn xác: Trên dữ liệu mô phỏng, đường cong độ chuẩn xác của UFBoot2 bám sát đường chéo không chệch khi mô hình đúng. Trong điều kiện vi phạm mô hình mạnh, biến thể UFBoot2+NNI duy trì tính không chệch, khắc phục hoàn toàn hiện tượng lệch ước lượng mà các phương pháp SBS và RBS gặp phải (vốn rơi vào trạng thái quá bảo thủ).
  • Trên cấu trúc cây hình sao mô phỏng, việc kích hoạt tính năng xử lý đỉnh đa phân giúp loại bỏ hoàn toàn các giá trị hỗ trợ cao cho các cạnh không có thực.

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

Chương 3 đề xuất phương pháp MPBoot nhằm áp dụng nguyên lý lấy mẫu cây và tái lấy mẫu điểm số sang tiêu chuẩn MP. Thuật toán MPBoot gồm ba kỹ thuật trọng tâm:

  1. Lấy mẫu cây trên sắp hàng gốc: Thay vì chạy độc lập thuật toán tìm kiếm trên từng bản sao bootstrap, MPBoot chỉ thực hiện khảo sát không gian cây một lần duy nhất trên sắp hàng gốc để thu thập một tập hợp các cây ứng viên chất lượng cao.
  2. Lấy mẫu điểm MP (Resampling Parsimony Score – REPS): Tác giả xây dựng công thức REPS, cho phép từ điểm MP đã tính cho từng vị trí của cây trên sắp hàng gốc, suy dẫn trực tiếp điểm MP của cây đó trên bất kỳ sắp hàng bootstrap nào mà không cần duyệt lại toàn bộ cấu trúc cây.
  3. Tăng tốc tính toán REPS kết hợp biến đổi SPR: Tích hợp các phép biến đổi cắt và ghép cây con (SPR) để mở rộng không gian tìm kiếm cây MP tối ưu cho từng bản sao bootstrap. Luận án thiết kế hai cấu hình thực thi: MPBoot SPR3 (bán kính hoán đổi 3) cho tốc độ cao và MPBoot SPR6 (bán kính hoán đổi 6) cho mức độ tìm kiếm sâu hơn.

Thực nghiệm đánh giá được tiến hành trên:

  • Bộ dữ liệu mô phỏng PANDIT (cả DNA và protein).
  • 114 bộ dữ liệu thực tế từ cơ sở dữ liệu TreeBASE, khảo sát độc lập với cả ma trận chi phí đều và ma trận chi phí không đều.

Kết quả thực nghiệm đối sánh với các công cụ hàng đầu là TNT (với hai chế độ fast-TNT và intensive-TNT) và PAUP*:

  • Thời gian thực hiện: MPBoot đạt tốc độ nhanh vượt trội so với PAUP* và cạnh tranh trực tiếp với TNT, đặc biệt khi áp dụng ma trận chi phí không đều (nơi các công cụ truyền thống tốn nhiều chi phí cho thuật toán Sankoff).
Phương pháp khảo sát Tổng thời gian chạy trên 114 sắp hàng TreeBASE Đặc điểm thuật toán
MPBoot SPR3 Nhanh nhất trên đa số tập dữ liệu REPS kết hợp tìm kiếm SPR cục bộ mức 3
MPBoot SPR6 Nhanh hơn intensive-TNT và PAUP* REPS kết hợp tìm kiếm SPR sâu mức 6
fast-TNT Tương đương hoặc chậm hơn MPBoot SPR3 SBS sử dụng script heuristic nhanh trong TNT
intensive-TNT Chậm hơn đáng kể so với MPBoot SBS sử dụng chiến lược tìm kiếm vét sâu trong TNT
PAUP* Chậm nhất trong các phương pháp khảo sát SBS sử dụng chiến lược tương tự fast-TNT
  • Khả năng tìm điểm MP tối ưu: Tần suất tìm được điểm MP tốt nhất trên sắp hàng gốc của MPBoot (cả SPR3 và SPR6) tương đương hoặc cao hơn fast-TNT và intensive-TNT trên cả hai tập dữ liệu PANDIT và TreeBASE.
  • Độ chuẩn xác bootstrap: MPBoot cho đường cong độ chuẩn xác gần với đường không chệch hơn so với SBS trong TNT và PAUP*, hạn chế mức độ sai lệch thống kê khi ước lượng xác suất của các cạnh đúng.

Kết quả và những đóng góp mới

Luận án đạt được những kết quả và đóng góp mới cụ thể về lý thuyết và thực tiễn:

  1. Đóng góp về mặt giải thuật cho tiêu chuẩn ML:
    • Xây dựng thuật toán pruning nhanh dựa trên tính chất đối xứng của các mô hình biến đổi thuận nghịch thời gian, giúp giảm đáng kể độ phức tạp tính toán khi ước lượng độ dài cạnh.
    • Hoàn thiện phương pháp UFBoot2 giải quyết bốn bài toán kỹ thuật: tăng tốc độ thực thi, triệt tiêu dương tính giả khi xuất hiện đỉnh đa phân, bổ sung bước tinh chỉnh UFBoot2+NNI giúp chống chịu vi phạm mô hình tiến hóa, và cung cấp ba chiến lược lấy mẫu bootstrap cho sắp hàng bộ gen đa phân hoạch.
  2. Đóng góp về mặt giải thuật cho tiêu chuẩn MP:
    • Đề xuất kỹ thuật lấy mẫu điểm MP (REPS), lần đầu tiên chuyển giao thành công nguyên lý ước lượng điểm nhanh sang bài toán bootstrap theo tiêu chuẩn tiết kiệm nhất.
    • Phát triển thuật toán MPBoot hoàn chỉnh (với hai biến thể SPR3 và SPR6), chứng minh khả năng tìm kiếm cây MP tương đương hoặc tốt hơn các công cụ TNT và PAUP* trong khi rút ngắn thời gian tính toán trên cả ma trận chi phí đều và không đều.
  3. Đóng góp về phần mềm và công bố khoa học:
    • Cài đặt toàn bộ các thuật toán cải tiến của UFBoot2 vào phần mềm mã nguồn mở IQ-TREE (http://www.iqtree.org), phục vụ trực tiếp cộng đồng nghiên cứu sinh học phân tử quốc tế.
    • Xây dựng độc lập phần mềm MPBoot, cung cấp công cụ phân tích bootstrap nhanh cho tiêu chuẩn MP.
    • Các kết quả nghiên cứu đã được công bố trong 2 bài báo trên các tạp chí quốc tế thuộc danh mục ISI và 1 báo cáo tại kỷ yếu hội nghị quốc tế chuyên ngành.

Luận án kiến nghị sử dụng UFBoot2 (đặc biệt là tùy chọn UFBoot2+NNI) như một giải pháp mặc định khi phân tích cây tiến hóa theo tiêu chuẩn ML trên các tập dữ liệu lớn hoặc dữ liệu đa gen, và sử dụng MPBoot như phương án thay thế cho các quy trình bootstrap chuẩn trong phần mềm TNT và PAUP* khi thực hiện phân tích theo tiêu chuẩn MP.

Hạn chế và hướng nghiên cứu tiếp

Dựa trên các nội dung được văn bản đề cập, luận án có các phạm vi giới hạn sau:

  • Luận án tập trung giải quyết bài toán theo hai tiêu chuẩn MP và ML; không khảo sát sâu việc so sánh thực nghiệm với các phương pháp suy luận Bayes do sự khác biệt về nền tảng triết lý đánh giá độ hỗ trợ và chi phí tính toán quá cao của phương pháp Bayes.
  • Thuật toán pruning nhanh trong Chương 2 được thiết kế tối ưu riêng cho lớp mô hình biến đổi thuận nghịch thời gian (Time-Reversible), chưa mở rộng cho các mô hình không thuận nghịch (Non-reversible).
  • Các thực nghiệm đánh giá chưa so sánh trực tiếp với phương pháp BOOSTER do công trình này được công bố sau thời điểm hoàn thiện các nghiên cứu chính của luận án.

Hướng nghiên cứu tiếp theo được xác định bao gồm việc mở rộng các kỹ thuật tối ưu hóa tính toán likelihood cho các lớp mô hình tiến hóa phức tạp hơn (không thuận nghịch thời gian), tiếp tục tối ưu hóa các chiến lược di chuyển trong không gian cây, và nâng cao khả năng xử lý song song trên các hệ thống điện toán hiệu năng cao.

Giá trị tham khảo

Luận án cung cấp giá trị tham khảo rõ ràng cho các nhóm đối tượng:

  • Nghiên cứu sinh và học viên chuyên ngành Khoa học máy tính, Tin sinh học: Có thể tham khảo Chương 1 để nắm bắt có hệ thống các mô hình toán học Markov trong tiến hóa phân tử, cấu trúc không gian tìm kiếm cây, và cơ sở thống kê của kỹ thuật bootstrap.
  • Các nhà phát triển phần mềm tin sinh học: Thuật toán pruning nhanh, kỹ thuật tối ưu hóa mã nguồn trong Chương 2 và giải thuật REPS trong Chương 3 cung cấp các giải pháp kỹ thuật cụ thể để tối ưu hóa hiệu năng tính toán trên các cấu trúc cây nhị phân.
  • Các nhà nghiên cứu trong lĩnh vực sinh học tiến hóa, y học và dược học: Có thể tham khảo hướng dẫn thực thi, các tập script và câu lệnh chạy thực nghiệm của IQ-TREE, RAxML, TNT và PAUP* được trình bày chi tiết tại phần Phụ lục để áp dụng vào các bài toán phân tích chủng virus, dịch tễ học hoặc hệ gen so sánh.

Câu hỏi thường gặp

1. Giá trị hỗ trợ bootstrap trong cây tiến hóa phản ánh điều gì theo các nghiên cứu thực nghiệm?

Theo Felsenstein (1985), mục đích ban đầu của bootstrap tiến hóa là đánh giá khả năng lặp lại (repeatability) của các cạnh. Tuy nhiên, nghiên cứu thực nghiệm của Hillis và Bull (1993) đã chứng minh rằng giá trị hỗ trợ bootstrap thực chất là ước lượng cho xác suất cạnh đó thuộc về cây đúng. Nghiên cứu này cũng chỉ ra phương pháp bootstrap chuẩn (SBS) có tính bảo thủ, nghĩa là ước lượng thu được thường thấp hơn xác suất đúng thực tế; do đó một cạnh đạt độ hỗ trợ bootstrap từ 70% trở lên trên thực tế đã có thể xem là một cạnh đúng.

2. Thuật toán UFBoot2 đã thực hiện những cải tiến cụ thể nào để khắc phục nhược điểm của UFBoot gốc?

UFBoot2 thực hiện bốn cải tiến chính: (1) Áp dụng thuật toán pruning nhanh cho các mô hình biến đổi thuận nghịch thời gian kết hợp tối ưu mã nguồn để tăng tốc tính toán; (2) Thiết lập cơ chế kiểm soát phân nhánh giúp giảm tỷ lệ dương tính giả khi cây chứa đỉnh đa phân; (3) Tích hợp bước tinh chỉnh tối ưu hóa NNI (UFBoot2+NNI) nhằm bảo toàn độ chuẩn xác khi dữ liệu vi phạm giả thiết mô hình tiến hóa; (4) Mở rộng chức năng phân tích sắp hàng bộ gen lớn với ba chiến lược lấy mẫu: theo vị trí, theo gen, và kết hợp gen-vị trí.

3. Kỹ thuật REPS trong phương pháp MPBoot hoạt động theo nguyên lý nào?

Kỹ thuật REPS (Resampling Parsimony Score) hoạt động tương tự như nguyên lý của RELL bên ML nhưng áp dụng cho tiêu chuẩn tiết kiệm nhất. Thay vì phải dựng lại cây và duyệt qua từng vị trí trên mỗi bản sao bootstrap, REPS sử dụng lại điểm số MP đã tính toán chi tiết tại từng vị trí của cây trên sắp hàng gốc. Từ ma trận điểm số vị trí này, điểm MP tổng thể của cây trên một bản sao bootstrap được tính toán trực tiếp thông qua phép cộng có trọng số dựa trên tần suất xuất hiện của các cột, giúp giảm thiểu đáng kể thời gian đánh giá cấu trúc cây.

4. Không gian tìm kiếm cấu trúc cây tiến hóa cho $n$ loài có độ phức tạp như thế nào?

Số lượng tất cả các cấu trúc phân nhánh không gốc khả dĩ cho $n \ge 3$ loài được tính theo công thức tổ hợp: $$S(n) = \prod_{i=3}^n (2i - 5)$$ Không gian này tăng trưởng theo giai thừa kép khi số lượng loài $n$ tăng lên. Do việc tìm kiếm cấu trúc tối ưu toàn cục là bài toán NP-đầy đủ (theo MP) và NP-khó (theo ML), các phương pháp bắt buộc phải áp dụng các chiến lược heuristic và các kỹ thuật biến đổi cục bộ như NNI, SPR, TBR để tìm kiếm lời giải chấp nhận được.

5. Phương pháp MPBoot được thiết kế với những cấu hình nào và so sánh với các công cụ nào?

MPBoot được thiết kế với hai cấu hình tìm kiếm cục bộ dựa trên phép biến đổi cây con: MPBoot SPR3 (bán kính cắt ghép mức 3) và MPBoot SPR6 (bán kính cắt ghép mức 6). Hiệu năng và độ chuẩn xác của hai cấu hình này được đối sánh trực tiếp với phương pháp bootstrap chuẩn của phần mềm TNT (ở hai chế độ fast-TNT và intensive-TNT) và phần mềm PAUP* trên cả dữ liệu mô phỏng PANDIT lẫn dữ liệu thực TreeBASE.

Kết luận

Luận án đã giải quyết thành công bài toán thắt nút cổ chai về mặt thời gian và độ chuẩn xác khi xây dựng cây bootstrap tiến hóa trên các tập dữ liệu sinh học phân tử quy mô lớn. Bằng việc đề xuất phương pháp UFBoot2 cho tiêu chuẩn hợp lý nhất và phương pháp MPBoot cho tiêu chuẩn tiết kiệm nhất, nghiên cứu mang lại các thuật toán có tốc độ tính toán vượt trội, hạn chế tối đa sai lệch ước lượng do đỉnh đa phân hoặc vi phạm mô hình gây ra. Các thuật toán đề xuất đã được tích hợp hoàn chỉnh vào phần mềm quốc tế IQ-TREE và công cụ MPBoot, cung cấp phương tiện phân tích đáng tin cậy cho các nghiên cứu sinh học phân tử và y học tiến hóa.