Tổng quan luận án

Tính cấp thiết và khoảng trống nghiên cứu

Tái dựng lịch sử tiến hóa dựa trên dữ liệu sinh học phân tử là bài toán trung tâm trong phân tích sinh học và tin sinh học, phục vụ nghiên cứu dịch tễ học virus, kiểm định nguồn gốc sinh vật, y học Darwin và phân tích hệ gen so sánh. Sau khi xây dựng cây tiến hóa từ sắp hàng đa chuỗi (MSA), việc đánh giá mức độ tin cậy thống kê cho các phân nhánh (cạnh trong) của cây thường được thực hiện bằng phương pháp phân tích bootstrap phi tham số do Felsenstein đề xuất.

Theo phương pháp bootstrap chuẩn (SBS), quy trình đòi hỏi lặp lại $B$ lần việc xây dựng cây tiến hóa độc lập trên $B$ bản sao sắp hàng bootstrap. Bản thân bài toán xây dựng cây tiến hóa đơn lẻ đã thuộc 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). Do đó, phân tích SBS làm tăng chi phí tính toán lên $B$ lần (thường $B = 100$ đến $1000$), tạo ra nút thắt nghẽn nghiêm trọng khi xử lý các tập dữ liệu lớn sinh ra từ công nghệ giải trình tự thế hệ mới (NGS).

Bên cạnh chi phí thời gian, phương pháp SBS còn tồn tại các vấn đề về mặt phương pháp luận:

  • Giá trị hỗ trợ bootstrap tính bởi SBS thường ước lượng thấp hơn xác suất đúng của cạnh trong cây tiến hóa (mang tính bảo thủ).
  • Phân tích theo tiêu chuẩn ML dễ bị ảnh hưởng bởi hiện tượng vi phạm giả thiết mô hình tiến hóa và hiện tượng không đủ thông tin dẫn đến cấu trúc đa phân (polytomy), làm sai lệch giá trị hỗ trợ thống kê.
  • Mặc dù phương pháp UFBoot đã giải quyết một phần tốc độ trong ML, các vấn đề về xử lý đỉnh đa phân, vi phạm mô hình và phân tích dữ liệu hệ gen phân hoạch vẫn chưa được giải quyết triệt để.
  • Trong phân tích theo tiêu chuẩn MP, các công cụ phổ biến như TNT và PAUP* chủ yếu vẫn dựa trên phương pháp bootstrap chuẩn tốn kém thời gian, thiếu một giải pháp bootstrap nhanh chuyên biệt có độ chuẩn xác cao.

Mục tiêu nghiên cứu

Luận án xác định ba mục tiêu 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à UFBoot; từ đó đề xuất các cải tiến nhằm 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 đ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 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 nhằm phục vụ cộng đồng nghiên cứu phân tích cây tiến hóa.

Đối tượng và phạm vi nghiên cứu

  • Đối tượng nghiên cứu: Các thuật toán, mô hình toán học và kỹ thuật tính toán xấp xỉ trong bài toán xây dựng cây tiến hóa và cây bootstrap tiến hóa dựa trên dữ liệu chuỗi sinh học phân tử (DNA, RNA, protein/axít amin, codon).
  • Phạm vi nghiên cứu:
    • Tập trung vào hai tiêu chuẩn tối ưu tổ hợp phổ biến: Tiêu chuẩn hợp lý nhất (ML) và tiêu chuẩn tiết kiệm nhất (MP).
    • Về quy trình phân tích tiến hóa tổng thể theo Warnow, luận án tập trung vào bước (4) xây dựng cây tiến hóa đơn gen và bước (5) tính toán độ hỗ trợ thống kê cho mỗi cạnh trong bằng bootstrap phi tham số, đồng thời mở rộng cho phân tích sắp hàng đa gen.
    • Dữ liệu thực nghiệm bao gồm dữ liệu mô phỏng từ công cụ Seq-Gen, tập dữ liệu chuẩn PANDIT và các bộ dữ liệu sinh học thực gồm 114 đến 115 sắp hàng thu thập từ cơ sở dữ liệu TreeBASE.

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

Các hướng nghiên cứu trước

Phân tích quan hệ tiến hóa dựa trên dữ liệu phân tử đã phát triển qua nhiều giai đoạn với các cách tiếp cận chính:

  1. Phương pháp dựa trên khoảng cách: Tính toán ma trận khoảng cách tiến hóa kết hợp mô hình rồi áp dụng phân cụm, tiêu biểu là thuật toán Neighbor Joining (NJ) của Saitou và Nei (1987). Tiếp cận này nhanh nhưng làm mất mát thông tin ký tự nguyên bản.
  2. Phương pháp dựa trên ký tự: Khảo sát đồng thời tất cả vị trí trong sắp hàng để tính điểm số cây:
    • Tiêu chuẩn tiết kiệm nhất (MP): Tìm cây có số lượng biến đổi tối thiểu, được hiện thực trong các chương trình PAUP* (Swofford), MEGA (Kumar và cộng sự), TNT (Goloboff và cộng sự, 2008). Để tính điểm MP với ma trận chi phí không đều, thuật toán quy hoạch động Sankoff (1975) được sử dụng.
    • Tiêu chuẩn hợp lý nhất (ML): Do Felsenstein (1981) khởi xướng, tính toán likelihood thông qua thuật toán pruning. Các phần mềm ML hiện đại gồm PhyML (Guindon và cộng sự), GARLI (Zwickl), RAxML (Stamatakis, 2014), RAxML-NG (Kozlov và cộng sự, 2019) và IQ-TREE (Nguyen và cộng sự, 2015).
    • Suy luận Bayes: Sử dụng xích Markov Monte Carlo (MCMC) để ước lượng phân bố xác suất hậu nghiệm của cây, tiêu biểu là MrBayes (Ronquist và Huelsenbeck) và BEAST (Drummond và cộng sự).
  3. Các phương pháp đánh giá độ tin cậy và bootstrap nhanh:
    • Efron (1979) đề xuất kỹ thuật bootstrap phi tham số trong thống kê; Felsenstein (1985) đưa bootstrap vào phân tích cây tiến hóa.
    • Hillis và Bull (1993) chỉ ra giá trị hỗ trợ của SBS thường thấp hơn xác suất đúng của cạnh và đề xuất cách hiểu giá trị hỗ trợ như một ước lượng xác suất đúng.
    • Các kỹ thuật tăng tốc ML bootstrap: Phương pháp RELL (Kishino và cộng sự, 1990; Hasegawa và Kishino, 1994) lấy mẫu điểm log-likelihood ước lượng; LBP (Adachi và Hasegawa, 1996) tính xác suất bootstrap cục bộ trên các cấu trúc hoán đổi hàng xóm gần nhất (NNI); phương pháp aLRT (Anisimova và Gascuel, 2006) và SH-aLRT (Guindon và cộng sự, 2010); phương pháp Rapid Bootstrap (RBS) của Stamatakis và cộng sự (2008) sử dụng kỹ thuật Lazy Subtree Rearrangement (LSR) đơn giản hóa trong RAxML.
    • Minh và cộng sự (2013) đề xuất UFBoot trong IQ-TREE, kết hợp duyệt không gian cây gốc bằng thuật toán IQPNNI (Vinh và von Haeseler, 2004) với việc chấm điểm nhanh cây bootstrap bằng RELL, đạt tốc độ nhanh hơn RBS từ 3 đến 10 lần.

Khoảng trống luận án lựa chọn giải quyết

Mặc dù UFBoot mang lại cải tiến lớn về thời gian chạy, thuật toán này vẫn bộc lộ các hạn chế: tính toán pruning cho việc ước lượng độ dài cạnh chưa tối ưu triệt để; có xu hướng gán giá trị hỗ trợ cao giả tạo khi dữ liệu thiếu thông tin (tồn tại đỉnh đa phân); suy giảm độ chuẩn xác khi dữ liệu vi phạm giả thiết mô hình tiến hóa; và chưa hỗ trợ các sắp hàng hệ gen phân hoạch lớn. Đồng thời, trong tiêu chuẩn MP, chưa có một thuật toán bootstrap nhanh tương đương để thay thế phương pháp bootstrap chuẩn nặng nề của TNT và PAUP*. Luận án định vị nghiên cứu vào việc hoàn thiện phương pháp UFBoot (xây dựng UFBoot2) cho ML và phát triển phương pháp MPBoot mới cho MP.

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

Cơ sở lý thuyết và mô hình toán học

  • Biểu diễn dữ liệu di truyền: Sắp hàng đa chuỗi $n \times m$ gồm $n$ chuỗi (loài/taxa) với độ dài $m$ vị trí (cột). Tập trạng thái $\mathcal{E}$ gồm 4 nucleotide ${A, C, G, T}$ hoặc 20 axít amin chuẩn mã hóa từ 64 codon (trong đó có 3 stop-codon).
  • Không gian cấu trúc cây: Số lượng cây nhị phân 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)$$
  • Mô hình tiến hóa nucleotide: Quá trình 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 ma trận tốc độ biến đổi tức thì $Q = {q_{ij}}$ kích thước $|\mathcal{E}| \times |\mathcal{E}|$. Ma trận xác suất chuyển trạng thái sau khoảng thời gian $t$ là $P(t) \approx P(0) + Q\Delta t$. Tốc độ được chuẩn hóa sao cho $-\sum_{i} \pi_i q_{ii} = 1$.
  • Lớp mô hình thuận nghịch thời gian (Time-reversible): Thỏa mãn điều kiện cân bằng chi tiết $\pi_i q_{ij} = \pi_j q_{ji}$.
Tên mô hình Số tham số tự do Ràng buộc tham số trong ma trận $Q$ Tần suất nucleotide
GTR 8 $a, b, c, d, e$ ($a+b+c+d+e+f=1$) $\pi_A, \pi_C, \pi_G$ ($\sum \pi_i = 1$)
TN93 5 $a=c=d=f$, $b=e$ $\pi_A, \pi_C, \pi_G$
HKY85 / F84 4 $a=c=d=1$, $b=e=k$ $\pi_A, \pi_C, \pi_G$
F81 3 $a=c=d=f=b=e=1$ $\pi_A, \pi_C, \pi_G$
K80 1 $a=c=d=f=1$, $b=e=k$ $\pi_A=\pi_C=\pi_G=\pi_T=0.25$
JC69 0 $a=b=c=d=e=f=1$ $\pi_A=\pi_C=\pi_G=\pi_T=0.25$
  • Tính không đồng nhất của tốc độ biến đổi giữa các vị trí: Sử dụng phân bố Gamma liên tục hoặc mô hình Gamma rời rạc với $k$ lớp tốc độ ($+\Gamma$) có tham số hình dạng $\alpha$, kỳ vọng bằng 1.0 và phương sai $1/\alpha$.
  • Hàm chấm điểm cây:
    • Tiêu chuẩn MP: Điểm MP là số lượng biến đổi tối thiểu trên toàn bộ sắp hàng, tính qua ma trận chi phí đều hoặc không đều bằng thuật toán Sankoff.
    • Tiêu chuẩn ML: Likelihood của cây $T$ trên sắp hàng $A$ được tính theo tích likelihood tại từng vị trí $L(T|A) = \prod_{i=1}^m L(T|A_i)$ thông qua thuật toán pruning của Felsenstein.

Phương pháp thực tế và kỹ thuật tối ưu

  • Kỹ thuật xáo trộn cục bộ (Branch-swapping): Sử dụng các phép biến đổi cây để tìm kiếm cấu trúc tối ưu:
    • Hoán đổi hàng xóm gần nhất (Nearest-Neighbor Interchange – NNI).
    • Cắt và ghép cây con (Subtree Pruning and Regrafting – SPR).
    • Chặt đôi và nối lại (Tree Bisection and Reconnection – TBR).
  • Phương pháp đánh giá độ chuẩn xác ước lượng bootstrap:
    • Định nghĩa hàm độ chuẩn xác $f_Z(x)$ là tỷ lệ phần trăm các cạnh thuộc cây đúng trong số tất cả các cạnh được phương pháp $Z$ gán giá trị hỗ trợ bootstrap $x%$ ($x \in [0, 100]$).
    • Phương pháp được xem là không chệch nếu đồ thị $f_Z(x)$ trùng đường chéo $y=x$; bảo thủ nếu nằm phía trên đường chéo; lạc quan nếu nằm phía dưới đường chéo. Trong thực hành, phân tích tập trung vào vùng $x \ge 70%$.

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 1 hệ thống hóa toàn diện các khái niệm nền tảng của phân tích tiến hóa phân tử và kỹ thuật bootstrap thống kê:

  • Trình bày cấu trúc thông tin di truyền từ nucleotide (A, C, G, T), 64 bộ ba codon, 20 axít amin tiêu chuẩn đến cấu trúc sắp hàng đa chuỗi (MSA) và biểu diễn cây tiến hóa nhị phân không gốc.
  • Phân tích chi tiết quy trình 7 bước phân tích quan hệ tiến hóa theo Warnow, định vị trọng tâm nghiên cứu vào hai bước cốt lõi: suy luận cây đơn gen và xác định độ hỗ trợ thống kê bằng bootstrap.
  • Trình bày bài toán tối ưu tổ hợp trong suy luận cây theo hai tiêu chuẩn MP và ML; phân tích các mô hình biến đổi nucleotide thuận nghịch thời gian (JC69, K80, F81, HKY85, TN93, GTR) kết hợp phân bố Gamma ($+\Gamma$).
  • Mô tả cơ chế lấy mẫu có hoàn lại của bootstrap thống kê (Efron) và quy trình 3 bước của bootstrap tiến hóa phi tham số (Felsenstein): (1) Sinh $B$ sắp hàng bootstrap, (2) Xây dựng cây độc lập cho từng sắp hàng, (3) Tính tần suất xuất hiện của các phân hoạch cạnh trên tập cây bootstrap.
  • Phân biệt rõ hai khái niệm: "khả năng lặp lại" (repeatability) và "độ chuẩn xác ước lượng" (bootstrap accuracy), đồng thời làm rõ bản chất bảo thủ của phương pháp SBS theo các phát hiện của Hillis và Bull.
  • Khảo sát các phương pháp bootstrap nhanh hiện có: RELL, LBP, aLRT, SH-aLRT, RBS trong RAxML/RAxML-NG, và phương pháp UFBoot trong IQ-TREE.

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 tập trung phân tích các hạn chế của UFBoot và đề xuất giải pháp toàn diện UFBoot2:

  • Cải tiến thuật toán tính likelihood: Đề xuất thuật toán pruning nhanh để ước lượng độ dài cạnh khi áp dụng cho 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 mức thấp để tăng tốc độ tính toán điểm likelihood.
  • Xử lý hiện tượng đỉnh đa phân (Polytomy): Khắc phục lỗi gán giá trị hỗ trợ cao cho các cạnh không có thực khi dữ liệu thiếu tín hiệu phân kỳ (cấu trúc cây hình sao) bằng cơ chế kiểm soát giá trị hỗ trợ nghiêm ngặt.
  • Giảm ảnh hưởng của vi phạm mô hình (UFBoot2+NNI): Tích hợp thêm bước tinh chỉnh tối ưu hóa cấu trúc cây bằng các phép biến đổi NNI trên các cây ứng viên, giúp duy trì độ chuẩn xác khi dữ liệu thực tế vi phạm các giả thiết của mô hình tiến hóa lý thuyết.
  • Mở rộng phân tích hệ gen (Phylogenomics): Bổ sung khả năng phân tích sắp hàng đa gen theo mô hình phân hoạch độ dài cạnh không liên kết (edge-unlinked partition model), hỗ trợ 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à lấy mẫu kết hợp gen-vị trí (gene-site resampling).
  • Kết quả thực nghiệm:
    • Khảo sát thời gian tính toán trên 115 sắp hàng thực từ TreeBASE: UFBoot2 và phiên bản UFBoot2+NNI cho thấy tốc độ vượt trội so với SBS và RBS trong RAxML, đồng thời nhanh hơn đáng kể so với UFBoot nguyên bản.
    • Phân tích dữ liệu mô phỏng từ cây đúng hình sao khẳng định UFBoot2 loại bỏ hoàn toàn tỷ lệ dương tính giả cho các cạnh không tồn tại.
    • Đồ thị độ chuẩn xác $f(x)$ trên dữ liệu mô phỏng vi phạm mô hình chứng minh cấu hình UFBoot2+NNI bám sát đường không chệch hơn so với SBS và RBS.

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 giải quyết bài toán bootstrap nhanh cho tiêu chuẩn tiết kiệm nhất (MP) thông qua phương pháp mới MPBoot:

  • Nguyên lý thuật toán MPBoot: Kết hợp kỹ thuật lấy mẫu không gian cây trên sắp hàng gốc với kỹ thuật lấy mẫu điểm MP (Resampling Parsimony Score – REPS).
  • Tăng tốc tính toán REPS: Phát triển thuật toán tính toán nhanh điểm REPS trên từng sắp hàng bootstrap mà không cần dựng lại cây từ đầu, áp dụng các bước hoán đổi nhánh SPR với bán kính tìm kiếm được kiểm soát (MPBoot SPR3 và MPBoot SPR6).
  • Thiết kế thực nghiệm:
    • Dữ liệu mô phỏng: Bộ dữ liệu DNA và protein mô phỏng chuẩn PANDIT.
    • Dữ liệu sinh học thực: 114 sắp hàng đa chuỗi DNA và axít amin từ TreeBASE.
    • Các phương pháp đối sánh: Thuật toán fast-TNT, intensive-TNT (trong phần mềm TNT) và lệnh bootstrap chuẩn trong PAUP*, khảo sát trên cả ma trận chi phí đều và ma trận chi phí không đều.
  • Kết quả thực nghiệm:
    • Thời gian chạy: MPBoot (đặc biệt là MPBoot SPR3) đạt tổng thời gian chạy thấp nhất trên 114 sắp hàng TreeBASE so với các chế độ của TNT và PAUP*.
    • Chất lượng cây gốc: Tần suất tìm được cây có điểm MP tối ưu trên sắp hàng gốc của MPBoot tương đương hoặc vượt trội so với fast-TNT và intensive-TNT trên cả bộ dữ liệu PANDIT và TreeBASE.
    • Độ chuẩn xác ước lượng bootstrap: Đường cong độ chuẩn xác của MPBoot SPR3 và MPBoot SPR6 trên dữ liệu mô phỏng PANDIT bám sát đường lý tưởng hơn so với các phương pháp bootstrap chuẩn của TNT và PAUP*.
    • Phân bố hiệu điểm MP trên cây bootstrap thực tế giữa TNT và MPBoot chứng minh MPBoot tìm được các cây có điểm MP xấp xỉ tối ưu trong thời gian ngắn.

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

Đóng góp về mặt lý thuyết và phương pháp luận

  1. Đề xuất thuật toán pruning nhanh và hoàn thiện phương pháp UFBoot2: Cải tiến quy trình tính toán likelihood cho các mô hình thuận nghịch thời gian; đề xuất giải pháp xử lý triệt để hiện tượng đỉnh đa phân và cơ chế tinh chỉnh NNI (UFBoot2+NNI) để khắc phục sai lệch ước lượng khi dữ liệu vi phạm mô hình tiến hóa.
  2. Xây dựng phương pháp MPBoot cho tiêu chuẩn MP: Lần đầu tiên phát triển thành công kỹ thuật lấy mẫu điểm MP (REPS) kết hợp hoán đổi nhánh cục bộ SPR để giải nhanh bài toán cây bootstrap tiến hóa theo tiêu chuẩn tiết kiệm nhất, cung cấp một khung tính toán có độ chuẩn xác thống kê cao hơn bootstrap chuẩn.
  3. Mở rộng mô hình phân tích hệ gen: Thiết lập cơ chế lấy mẫu bootstrap linh hoạt (theo vị trí, theo gen, và kết hợp gen-vị trí) cho các bộ dữ liệu phân hoạch lớn gồm nhiều gen.

Đóng góp về mặt thực tiễn và phần mềm

  1. Cài đặt hoàn chỉnh các cải tiến của UFBoot2 vào phần mềm phân tích tiến hóa IQ-TREE (công cụ mã nguồn mở được sử dụng phổ biến trên thế giới tại địa chỉ http://www.iqtree.org).
  2. Xây dựng và phát hành phần mềm độc lập MPBoot phục vụ cộng đồng nghiên cứu suy luận cây tiến hóa nhanh và chuẩn xác theo tiêu chuẩn MP.
  3. Các kết quả nghiên cứu trong luận án đã được công bố trong 02 bài báo khoa học thuộc danh mục tạp chí ISI và 01 báo cáo tại kỷ yếu hội nghị quốc tế.

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

Hạn chế của luận án

  • Các phương pháp đề xuất chủ yếu tập trung vào lớp mô hình biến đổi nucleotide/axít amin có tính thuận nghịch thời gian (time-reversible); việc mở rộng sang các mô hình không thuận nghịch (non-reversible) chưa được tối ưu chuyên sâu.
  • Các phân tích thực nghiệm so sánh phương pháp MPBoot mới chỉ tập trung đối sánh với hai công cụ MP chuẩn là TNT và PAUP*; chưa khảo sát mở rộng trên các công cụ mới xuất hiện sau thời điểm nghiên cứu như BOOSTER.
  • Nghiên cứu tập trung vào bài toán bootstrap phi tham số (non-parametric bootstrap) trên cấu trúc cây nhị phân, chưa khảo sát mở rộng cho phân tích bootstrap có tham số (parametric bootstrap) hoặc cấu trúc mạng lưới tiến hóa phức tạp (phylogenetic networks).

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

  • Nghiên cứu tối ưu hóa thuật toán tính likelihood nhanh cho các mô hình tiến hóa phức tạp hơn, bao gồm mô hình không thuận nghịch thời gian và mô hình codon tổng quát.
  • Ứng dụng các kỹ thuật tính toán song song hiệu năng cao (OpenMP, MPI, GPU) cho thuật toán MPBoot để xử lý các siêu bộ dữ liệu hệ gen (phylogenomics) có hàng chục nghìn loài.
  • Mở rộng phương pháp bootstrap nhanh cho việc ước lượng độ tin cậy trên các mạng lưới tiến hóa đa gen (phylogenomic networks) nhằm mô hình hóa hiện tượng lai ghép hoặc chuyển gen ngang.

Giá trị tham khảo

Luận án là tài liệu tham khảo chuyên sâu trong các lĩnh vực:

  • Nghiên cứu sinh và học viên cao học ngành Tin sinh học, Khoa học Máy tính và Toán ứng dụng: Có thể tham khảo Chương 1 và Chương 2 về cách xây dựng mô hình Markov trong tiến hóa phân tử, kỹ thuật tối ưu hóa tổ hợp trên cây và phương pháp xấp xỉ thống kê bootstrap.
  • Các nhà nghiên cứu Sinh học tiến hóa, Dịch tễ học và Di truyền học phân tử: Phần mềm UFBoot2 (trong IQ-TREE) và MPBoot cung cấp công cụ tính toán hiệu năng cao giúp phân tích cây quan hệ tiến hóa chính xác trên các tập dữ liệu giải trình tự thế hệ mới quy mô lớn.
  • Kỹ sư phần mềm tính toán khoa học: Tham khảo Phụ lục 1 và Phụ lục 2 về cấu hình tham số, dòng lệnh vận hành TNT, PAUP*, IQ-TREE và RAxML, cùng các kỹ thuật tối ưu mã nguồn cho các thuật toán tìm kiếm cục bộ (NNI, SPR, TBR).

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

1. Tại sao phương pháp bootstrap chuẩn (SBS) lại tốn kém thời gian tính toán và có nhược điểm gì về độ chuẩn xác?

Xây dựng cây tiến hóa theo MP là bài toán NP-đầy đủ và theo ML là bài toán NP-khó. Phương pháp SBS yêu cầu lặp lại toàn bộ quy trình tìm kiếm cây độc lập trên $B$ bản sao bootstrap (thường từ 100 đến 1000 lần), do đó thời gian chạy tăng gấp $B$ lần. Về độ chuẩn xác, các nghiên cứu thực nghiệm của Hillis & Bull (1993) và Minh & cs (2013) đã chứng minh SBS cho ước lượng mang tính bảo thủ, tức là giá trị hỗ trợ bootstrap gán cho cạnh thường thấp hơn xác suất thực sự thuộc về cây đúng của cạnh đó.

2. Thuật toán UFBoot2 đã thực hiện những cải tiến kỹ thuật cụ thể nào so với phiên bản UFBoot ban đầu?

UFBoot2 tích hợp bốn cải tiến chính:

  1. Tối ưu thuật toán pruning tính likelihood nhanh cho các mô hình thuận nghịch thời gian kết hợp tối ưu mã nguồn.
  2. Bổ sung cơ chế kiểm soát xử lý đỉnh đa phân, loại bỏ việc gán giá trị hỗ trợ giả tạo trên dữ liệu thiếu thông tin (cây hình sao).
  3. Đề xuất bước tinh chỉnh tối ưu hóa cấu trúc cây UFBoot2+NNI nhằm giảm thiểu sai số ước lượng khi dữ liệu vi phạm giả thiết mô hình tiến hóa.
  4. Mở rộng khả năng phân tích sắp hàng đa gen theo mô hình phân hoạch edge-unlinked với 3 chiến lược lấy mẫu (vị trí, gen, gen-vị trí).

3. Nguyên lý hoạt động cơ bản của phương pháp MPBoot trong Chương 3 là gì?

MPBoot giải nhanh bài toán bootstrap theo tiêu chuẩn MP bằng cách: thay vì chạy thuật toán tìm kiếm cây độc lập từ đầu cho từng bản sao bootstrap, MPBoot tiến hành duyệt tìm cây trên sắp hàng gốc kết hợp lấy mẫu điểm MP (Resampling Parsimony Score – REPS). Thuật toán sử dụng các biến đổi cục bộ SPR với bán kính nhỏ (SPR3, SPR6) để cập nhật và chấm điểm nhanh các cây ứng viên trên toàn bộ các bản sao bootstrap cùng lúc, giúp giảm thiểu tối đa thời gian tính toán mà vẫn đảm bảo tìm được cây tối ưu.

4. Bảng danh mục mô hình nucleotide thuận nghịch thời gian trong luận án gồm những mô hình nào và số lượng tham số tự do của chúng là bao nhiêu?

Luận án khảo sát 6 mô hình nucleotide thuận nghịch thời gian chính:

  • GTR: 8 tham số tự do ($a, b, c, d, e$ và 3 tần suất $\pi_A, \pi_C, \pi_G$).
  • TN93: 5 tham số tự do ($a=c=d=f$, $b=e$ và 3 tần suất).
  • HKY85 / F84: 4 tham số tự do ($a=c=d=1$, $b=e=k$ và 3 tần suất).
  • F81: 3 tham số tự do (tần suất $\pi_A, \pi_C, \pi_G$, các tốc độ biến đổi bằng nhau).
  • K80: 1 tham số tự do ($b=e=k$, tần suất nucleotide bằng nhau 0.25).
  • JC69: 0 tham số tự do (tất cả tốc độ và tần suất đều bằng nhau).

5. Dữ liệu thực nghiệm được sử dụng để đánh giá các phương pháp trong luận án gồm những nguồn nào?

Thực nghiệm sử dụng kết hợp dữ liệu mô phỏng và dữ liệu thực:

  • Dữ liệu mô phỏng: Sinh ra từ công cụ Seq-Gen theo các cấu trúc cây và mô hình định sẵn; bộ dữ liệu mô phỏng DNA và axít amin chuẩn PANDIT.
  • Dữ liệu thực: Tập hợp 114 đến 115 sắp hàng đa chuỗi DNA và protein thu thập từ cơ sở dữ liệu sinh học TreeBASE.

Kết luận

Luận án đã giải quyết bài toán nút thắt tính toán và độ chuẩn xác của phương pháp bootstrap trong phân tích cây tiến hóa phân tử dưới hai tiêu chuẩn tối ưu hợp lý nhất (ML) và tiết kiệm nhất (MP). Bằng việc đề xuất phương pháp UFBoot2 cải tiến (tích hợp trong phần mềm IQ-TREE) và phát triển phương pháp MPBoot mới, tác giả đã cung cấp các giải pháp tính toán hiệu năng cao, giảm thiểu thời gian thực thi đồng thời nâng cao độ tin cậy của các giá trị hỗ trợ thống kê. Các đóng góp của luận án có ý nghĩa khoa học và giá trị ứng dụng thực tiễn trong lĩnh vực tin sinh học và phân tích hệ gen tiến hóa.