Luận án về các phương pháp xây dựng ma trận biến đổi axít amin cho sinh viên Việt Nam

Cập nhật phương pháp xây dựng ma trận biến đổi axít amin giúp sinh viên Việt Nam nắm vững kiến thức và ứng dụng trong nghiên cứu sinh học.

• Người hướng dẫn: TS. Lê Sỹ Vinh
• Trường học: Đại học Công nghệ, Đại học Quốc gia Hà Nội
• Chuyên ngành: Khoa học Máy tính
• Đề tài: Cập Nhật Phương Pháp Xây Dựng Ma Trận Biến Đổi Axít Amin
• Loại tài liệu: luận án tiến sĩ
• Năm xuất bản: 2013
• Đị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 ƯỚC LƯỢNG SỰ BIẾN ĐỔI CỦA AXÍT AMIN
• 1.1. Giới thiệu chung
• 1.2. ADN và axít amin
• 1.3. Các phép biến đổi trên chuỗi axít amin
• 1.4. Sắp hàng đa chuỗi axít amin
• 1.5. Cây phân loài
• 1.6. Mô hình hoá quá trình biến đổi axít amin
• 1.7. Sự khác biệt giữa hai chuỗi tương đồng
• 1.8. Mô hình Markov cho quá trình biến đổi axít amin
• 1.9. Bài toán ước lượng mô hình biến đổi axít amin
• 1.10. Các phương pháp ước lượng mô hình biến đổi axít amin
• 1.10.1. Phương pháp đếm
• 1.10.2. Phương pháp cực đại khả năng (maximum likelihood)
• 1.11. Xây dựng cây phân loài bằng phương pháp ML
• 1.12. Các phương pháp so sánh hai mô hình
• 1.12.1. So sánh bằng việc xây dựng cây ML
• 1.12.2. So sánh cấu trúc cây
• 1.12.3. So sánh độ tương quan Pearson
• 1.13. Kết luận chương
• 2. CHƯƠNG 2: PHƯƠNG PHÁP ƯỚC LƯỢNG NHANH MÔ HÌNH BIẾN ĐỔI AXÍT AMIN BẰNG PHƯƠNG PHÁP CỰC ĐẠI KHẢ NĂNG
• 2.1. Ước lượng mô hình bằng phương pháp cực đại khả năng
• 2.2. Mô tả phương pháp
• 2.3. Phân tích phương pháp
• 2.4. Các phương pháp chia tách dữ liệu
• 2.4.1. Phương pháp chia tách ngẫu nhiên
• 2.4.2. Phương pháp chia tách dựa theo cấu trúc cây
• 2.5. Nhận xét về các phương pháp chia tách sắp hàng
• 2.6. Kết quả thực nghiệm
• 2.6.1. Dữ liệu kiểm tra
• 2.6.2. Kết quả với bộ dữ liệu vi rút cúm
• 2.6.3. Kết quả với bộ dữ liệu Pfam
• 2.7. Kết luận chương
• 3. CHƯƠNG 3: XÂY DỰNG MÔ HÌNH BIẾN ĐỔI ĐA MA TRẬN
• 3.1. Tính không đồng nhất của tốc độ biến đổi theo vị trí
• 3.2. Mô hình biến đổi đa ma trận
• 3.3. Thuật toán ước lượng mô hình đa ma trận
• 3.4. Kết quả thực nghiệm
• 3.4.1. Dữ liệu kiểm tra
• 3.5. Tiêu chuẩn đánh giá AIC
• 3.6. So sánh kết quả của các mô hình
• 3.7. So sánh dung lượng bộ nhớ sử dụng và thời gian chạy
• 3.8. Kết luận chương
• 4. CHƯƠNG 4: HỆ THỐNG ƯỚC LƯỢNG MÔ HÌNH TỰ ĐỘNG
• 4.1. Phương pháp ước lượng nhanh
• 4.2. Kết quả thực nghiệm
• 4.2.1. Dữ liệu kiểm tra
• 4.2.2. Kết quả với bộ dữ liệu Pfam
• 4.2.3. Kết quả với bộ dữ liệu FLU
• 4.3. Hệ thống ước lượng mô hình tự động
• 4.4. Kết luận chương
• 5. CHƯƠNG 5: MÔ HÌNH BIẾN ĐỔI AXÍT AMIN CHO VI RÚT CÚM
• 5.1. Giới thiệu về vi rút cúm và sự cần thiết của các mô hình biến đổi axít amin riêng biệt cho từng loài
• 5.2. Ước lượng mô hình FLU
• 5.3. Kết quả thực nghiệm
• 5.3.1. Phân tích và đánh giá mô hình
• 5.4. So sánh hiệu quả của FLU với các mô hình khác
• 5.5. Tính bền vững của mô hình
• 5.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

Tóm tắt

I. Giới thiệu về phương pháp xây dựng ma trận biến đổi axít amin

Phương pháp xây dựng ma trận biến đổi axít amin là một phần quan trọng trong nghiên cứu sinh học phân tử. Ma trận này giúp mô hình hóa sự biến đổi của các axít amin trong chuỗi prôtêin, từ đó hỗ trợ trong việc phân tích và so sánh các chuỗi axít amin khác nhau. Việc cập nhật phương pháp này là cần thiết để đáp ứng với sự phát triển nhanh chóng của dữ liệu sinh học. Các phương pháp truyền thống như PAM và LG đã được sử dụng rộng rãi, nhưng vẫn còn nhiều hạn chế trong việc mô hình hóa các đặc điểm riêng biệt của từng loài. Do đó, việc phát triển các phương pháp mới để xây dựng ma trận biến đổi axít amin là rất quan trọng. Những phương pháp này không chỉ giúp tăng tốc độ ước lượng mà còn nâng cao độ chính xác của mô hình. Theo nghiên cứu, việc áp dụng các ràng buộc sinh học vào quá trình mô hình hóa có thể cải thiện đáng kể kết quả phân tích.

1.1. Tầm quan trọng của ma trận biến đổi axít amin

Ma trận biến đổi axít amin đóng vai trò quan trọng trong việc phân tích dữ liệu sinh học. Nó cho phép các nhà nghiên cứu hiểu rõ hơn về cách thức các axít amin biến đổi trong quá trình tiến hóa. Việc nghiên cứu axít amin không chỉ giúp xác định các mối quan hệ giữa các loài mà còn hỗ trợ trong việc phát triển các liệu pháp điều trị bệnh. Các mô hình hiện tại như PAM và LG đã cung cấp những thông tin quý giá, nhưng vẫn cần được cải tiến để phù hợp với các dữ liệu mới. Việc xây dựng ma trận biến đổi axít amin mới sẽ giúp nâng cao khả năng phân tích và so sánh giữa các chuỗi prôtêin, từ đó mở ra nhiều hướng nghiên cứu mới trong lĩnh vực sinh học phân tử.

II. Các phương pháp ước lượng mô hình biến đổi axít amin

Trong nghiên cứu này, hai phương pháp chính được đề xuất để ước lượng mô hình biến đổi axít amin là phương pháp đếm và phương pháp cực đại khả năng (maximum likelihood). Phương pháp đếm là một cách tiếp cận đơn giản, nhưng thường không đủ chính xác khi xử lý các dữ liệu phức tạp. Ngược lại, phương pháp cực đại khả năng cung cấp một cách tiếp cận mạnh mẽ hơn, cho phép ước lượng các tham số của mô hình một cách chính xác hơn. Việc cập nhật các phương pháp này là cần thiết để cải thiện độ chính xác và hiệu quả trong việc ước lượng mô hình. Các nghiên cứu đã chỉ ra rằng việc áp dụng các thuật toán mới có thể giảm thiểu thời gian ước lượng mà vẫn đảm bảo độ chính xác cao. Điều này đặc biệt quan trọng trong bối cảnh dữ liệu sinh học ngày càng gia tăng.

2.1. Phương pháp cực đại khả năng

Phương pháp cực đại khả năng (maximum likelihood) là một trong những phương pháp phổ biến nhất trong việc ước lượng mô hình biến đổi axít amin. Phương pháp này dựa trên nguyên tắc tối đa hóa xác suất của dữ liệu quan sát được, từ đó ước lượng các tham số của mô hình. Việc áp dụng phương pháp này giúp cải thiện đáng kể độ chính xác của các mô hình biến đổi axít amin. Nghiên cứu cho thấy rằng việc sử dụng các thuật toán tối ưu hóa hiện đại có thể giảm thiểu thời gian ước lượng mà vẫn đảm bảo độ chính xác cao. Điều này cho phép các nhà nghiên cứu có thể xử lý các bộ dữ liệu lớn một cách hiệu quả hơn, từ đó mở rộng khả năng ứng dụng của mô hình trong các lĩnh vực khác nhau như y học và nông nghiệp.

III. Hệ thống ước lượng mô hình tự động

Hệ thống ước lượng mô hình tự động được phát triển nhằm mục đích giúp người dùng dễ dàng ước lượng các mô hình biến đổi axít amin từ dữ liệu của họ. Hệ thống này không chỉ giúp tiết kiệm thời gian mà còn nâng cao độ chính xác của các mô hình được ước lượng. Việc xây dựng ma trận biến đổi axít amin tự động sẽ giúp các nhà nghiên cứu có thể tập trung vào việc phân tích và ứng dụng kết quả thay vì phải lo lắng về quá trình ước lượng phức tạp. Hệ thống này cũng cho phép người dùng tùy chỉnh các tham số theo nhu cầu nghiên cứu của họ, từ đó tạo ra các mô hình riêng biệt cho từng loài sinh vật. Điều này đặc biệt quan trọng trong bối cảnh nghiên cứu sinh học phân tử hiện nay, nơi mà sự đa dạng sinh học cần được xem xét một cách kỹ lưỡng.

3.1. Lợi ích của hệ thống tự động

Hệ thống ước lượng mô hình tự động mang lại nhiều lợi ích cho các nhà nghiên cứu. Đầu tiên, nó giúp giảm thiểu thời gian cần thiết để ước lượng các mô hình biến đổi axít amin, cho phép các nhà nghiên cứu có thể tập trung vào các khía cạnh khác của nghiên cứu. Thứ hai, hệ thống này cung cấp một cách tiếp cận nhất quán và chính xác hơn trong việc ước lượng các tham số của mô hình. Cuối cùng, việc sử dụng hệ thống tự động cũng giúp tăng cường khả năng tái lập và kiểm tra các kết quả nghiên cứu, từ đó nâng cao độ tin cậy của các phát hiện trong lĩnh vực sinh học phân tử.

Nội dung chính

Tổng quan về luận án

Sự bùng nổ của dữ liệu hệ gen học và prôtêin trong kỷ nguyên sinh học phân tử hiện đại—minh chứng qua việc cơ sở dữ liệu GenBank vượt mốc hàng trăm triệu chuỗi ADN và UniProt lưu trữ hàng chục triệu chuỗi prôtêin—đã đặt ra thách thức tính toán to lớn cho ngành tin sinh học. Trung tâm của các bài toán cốt lõi như sắp hàng đa chuỗi (multiple sequence alignment), tìm kiếm chuỗi tương đồng và tái dựng cây phân loài (phylogenetic tree reconstruction) chính là ma trận biến đổi axít amin (amino acid substitution matrix). Luận án tiến sĩ chuyên ngành Khoa học Máy tính với đề tài "Các phương pháp xây dựng ma trận biến đổi axít amin" tập trung giải quyết nút thắt cổ chai về độ phức tạp tính toán và độ chính xác sinh học trong việc ước lượng ma trận tốc độ thay thế tức thời $Q$.

Khoảng trống nghiên cứu (research gap) trọng tâm xuất phát từ việc ước lượng mô hình biến đổi axít amin theo phương pháp Cực đại Khả năng (Maximum Likelihood - ML) đòi hỏi đồng thời tối ưu hóa 208 tham số tự do và không gian cây phân loài nhị phân không gốc tăng theo giai thừa kép $(2m-5)!!$ với $m$ chuỗi [Felsenstein, 1981; Whelan & Goldman, 2001]. Trên thực tế, quá trình ước lượng các mô hình tổng quát kinh điển như WAG [Whelan & Goldman, 2001] hay LG [Le & Gascuel, 2008] trên bộ dữ liệu lớn Pfam mất nhiều ngày đến nhiều tuần tính toán liên tục, trong đó bước tối ưu hóa cấu trúc cây chiếm hơn $85% - 90%$ tổng thời gian chạy (ví dụ mất 35/39 giờ trên 200 sắp hàng Pfam lớn nhất và 273/283 giờ trên 1.373 sắp hàng vi rút cúm). Hơn nữa, các mô hình đơn ma trận giả định tốc độ biến đổi đồng nhất giữa các vị trí hoặc chỉ áp dụng phân phối Gamma đơn thuần, bỏ qua các ràng buộc cấu trúc không gian và tính không đồng nhất sinh học cục bộ. Mặt khác, việc thiếu vắng các mô hình biến đổi chuyên biệt cho từng taxon/loài (như vi rút cúm - Influenza virus) dẫn đến sai lệch nghiêm trọng khi phân tích dịch tễ học phân tử.

Luận án xác lập 4 câu hỏi nghiên cứu và giả thuyết cụ thể:

1. RQ1: Làm thế nào để giảm thiểu độ phức tạp của bài toán NP-khó trong bước dựng cây phân loài bằng ML mà không làm suy giảm chất lượng ước lượng ma trận thay thế? (Hypothesis H1: Phân rã sắp hàng đa chuỗi lớn thành các tập con kích thước nhỏ $k \in [4, 32]$ dựa trên cấu trúc phân nhánh cây sẽ bảo toàn thông tin tiến hóa khoảng cách gần và tăng tốc độ ước lượng từ 3 đến 6 lần).
2. RQ2: Mô hình hóa sự biến đổi axít amin bằng cấu trúc đa ma trận (multi-matrix) có phản ánh chính xác hơn tính không đồng nhất sinh học phân tử so với mô hình đơn ma trận hay không? (Hypothesis H2: Mô hình tích hợp 4 ma trận chuyển vị kết hợp phân phối tốc độ Gamma sẽ cải thiện vượt bậc giá trị Log-Likelihood và tiêu chuẩn AIC trên dữ liệu TreeBase và HSSP).
3. RQ3: Thuật toán ước lượng lặp có thể tinh giản các bước tối ưu cấu trúc topo cây phân loài ở các vòng lặp trung gian để đạt hiệu năng cao hơn hay không? (Hypothesis H3: Cố định cây phân loài sau các bước lặp ban đầu giúp giảm $50%$ tổng thời gian tính toán mà vẫn đảm bảo độ hội tụ tham số).
4. RQ4: Một mô hình ma trận chuyên biệt cho vi rút cúm (FLU) có vượt trội hơn các mô hình tổng quát hiện hành (như LG, JTT, WAG) và mô hình vi rút khác (HIVb, HIVw) khi phân tích tiến hóa cúm hay không? (Hypothesis H4: Mô hình FLU cải thiện đáng kể log-likelihood và tối ưu hóa khoảng cách Robinson-Foulds trên tập kiểm thử 3.970 sắp hàng cúm).

Khung lý thuyết nền tảng của luận án dựa trên Quá trình Markov thời gian liên tục (Continuous-time Markov Process), Phương trình vi phân Chapman-Kolmogorov, Khai triển chuỗi Taylor cho ma trận xác suất chuyển $P(t) = e^{Qt} \approx I + Qt$, và Nguyên lý Cực đại Khả năng (Maximum Likelihood Estimation) tích hợp thuật toán Kỳ vọng - Cực đại (Expectation-Maximization - EM).

Quy mô thực nghiệm của nghiên cứu bao quát các tập dữ liệu chuẩn quốc tế quy mô lớn: 3.912 sắp hàng Pfam với 49.637 chuỗi (khoảng 6,5 triệu axít amin), bộ dữ liệu vi rút cúm gồm 1.373 sắp hàng với 71.087 chuỗi trích xuất từ NCBI (bao gồm Cúm A, B, C), tập TreeBase (84 sắp hàng) và HSSP (300 sắp hàng), cùng tập kiểm định độc lập 3.970 sắp hàng vi rút cúm.

Literature Review và Positioning

Lịch sử mô hình hóa quá trình tiến hóa phân tử của prôtêin trải qua hai trường phái phương pháp luận chính với những mâu thuẫn học thuật sâu sắc:

Trường phái tiếp cận dựa trên phương pháp đếm (Counting-based approaches) khởi đầu với ma trận PAM (Point Accepted Mutation) của Dayhoff và cộng sự [1978], dựa trên 71 nhóm prôtêin có độ tương đồng cao ($\ge 85%$) để quan sát trực tiếp các đột biến thay thế chấp nhận được. Đến năm 1992, Jones, Taylor và Thornton mở rộng phương pháp này trên tập dữ liệu lớn hơn để công bố mô hình JTT [Jones et al., 1992]. Cùng năm đó, Henikoff & Henikoff [1992] đề xuất họ ma trận BLOSUM (như BLOSUM62, BLOSUM80) dựa trên các khối bảo tồn (conserved blocks) trong cơ sở dữ liệu BLOCKS phục vụ bài toán gióng hàng chuỗi. Tuy nhiên, giới hạn cốt tử của trường phái đếm là chỉ hoạt động chính xác khi các chuỗi có độ tương đồng rất cao nhằm tránh hiện tượng đa đột biến (multiple substitutions), đột biến song song (parallel substitutions), và đột biến ngược (back substitutions). Khi khoảng cách di truyền thực tế ($d$) vượt xa khoảng cách quan sát ($p$), phương pháp đếm bị sai lệch có hệ thống (systematic bias).

Trường phái tiếp cận bằng Cực đại Khả năng (Maximum Likelihood approaches) được tiên phong bởi Adachi & Hasegawa [1996] với mô hình mtREV cho hệ gen ti thể động vật có xương sống. Tiếp đó, Whelan & Goldman [2001] phát triển mô hình WAG áp dụng trên 3.905 chuỗi prôtêin hình cầu sử dụng thuật toán xấp xỉ ML. Đột phá lớn nhất thuộc về mô hình LG của Le & Gascuel [2008], tích hợp phân phối Gamma để mô hình hóa tính không đồng nhất về tốc độ biến đổi giữa các vị trí ($\Gamma$-distributed rate variation across sites) trên cơ sở dữ liệu Pfam. Dù phương pháp ML khắc phục triệt để các sai lệch của phương pháp đếm, nó lại vấp phải rào cản tính toán cực lớn: việc tối ưu đồng thời không gian cây phân loài và ma trận chuyển vị khiến việc ước lượng trên tập dữ liệu lớn đòi hỏi hạ tầng siêu máy tính hoặc thời gian tính toán kéo dài.

Tiêu chí / Mô hình	PAM250 [Dayhoff, 1978]	JTT [Jones et al., 1992]	WAG [Whelan & Goldman, 2001]	LG [Le & Gascuel, 2008]	Đóng góp của Luận án
Phương pháp ước lượng	Đếm trực tiếp đột biến	Đếm tần suất quan sát	Xấp xỉ Cực đại Khả năng (ML)	Cực đại Khả năng (ML + $\Gamma$)	Thuật toán phân rã BIONJ + Thuật toán rút gọn lặp ML
Dữ liệu huấn luyện	71 họ prôtêin ($\ge 85%$ tương đồng)	Tập prôtêin mở rộng SWISS-PROT	3.905 chuỗi prôtêin hình cầu	Pfam (3.912 sắp hàng, 49.637 chuỗi)	Pfam, TreeBase, HSSP và NCBI Influenza (71.087 chuỗi)
Xử lý tính không đồng nhất	Đồng nhất toàn bộ	Đồng nhất toàn bộ	Đồng nhất theo vị trí	Phân phối Gamma ($\alpha$)	Đa ma trận (LG4M, LG4X) phân tách 4 lớp tốc độ
Phạm vi ứng dụng	Tổng quát sơ khai	Phân tích phân loài	Phân tích phân loài	Mô hình tổng quát chuẩn hiện hành	Mô hình tổng quát tốc độ cao + Mô hình chuyên biệt (FLU)

Luận án định vị chính xác điểm nghẽn của y văn quốc tế: vừa hóa giải bài toán chi phí tính toán NP-khó của phương pháp ML bằng kỹ thuật phân rã cấu trúc cây BIONJ, vừa nâng cấp khung mô hình đơn ma trận truyền thống thành mô hình đa ma trận thích ứng sinh học, đồng thời chứng minh sự cần thiết tất yếu của các ma trận chuyên biệt loài (taxon-specific models).

Đóng góp lý thuyết và khung phân tích

Đóng góp cho lý thuyết

Luận án đóng góp trực tiếp vào Lý thuyết Tiến hóa Phân tử và Quá trình Ngẫu nhiên Markov thông qua việc mở rộng các mô hình kinh điển của Felsenstein [1981] và Le & Gascuel [2008]:

Mô hình Markov tiêu chuẩn định nghĩa ma trận tốc độ biến đổi tức thời $Q = {q_{ij}}$ kích thước $20 \times 20$ biểu diễn qua ma trận đối xứng hệ số hoán đổi (exchangeability matrix) $R = {r_{ij}}$ và véc tơ tần số dừng của 20 axít amin $\Pi = (\pi_1, \pi_2, \dots, \pi_{20})^T$: $$q_{ij} = r_{ij} \pi_j \quad (\forall i \neq j), \quad q_{ii} = -\sum_{j \neq i} q_{ij}$$ với chuẩn hóa chuẩn tắc $-\sum_{i=1}^{20} \pi_i q_{ii} = 1$. Số tham số tự do cần ước lượng chính xác là 189 tham số từ ma trận $R$ và 19 tham số từ véc tơ $\Pi$, tổng cộng 208 tham số.

Luận án tạo ra bước chuyển dịch mô hình (paradigm shift) từ đơn ma trận tĩnh sang mô hình đa ma trận động (Multi-matrix models: LG4M và LG4X). Luận án chứng minh rằng tính không đồng nhất của tốc độ tiến hóa tại các vị trí không chỉ đơn thuần tuân theo phân phối vô hướng Gamma $\Gamma(k, \alpha)$ như giả định của Yang [1994], mà bản thân cơ chế thay thế hóa lý giữa 20 axít amin cũng biến thiên theo từng miền chức năng và áp lực chọn lọc cấu trúc. Mô hình LG4M định nghĩa 4 ma trận tốc độ riêng biệt ${Q_1, Q_2, Q_3, Q_4}$ tương ứng với 4 trọng số xác suất ${w_1, w_2, w_3, w_4}$ và hệ số tốc độ ${\rho_1, \rho_2, \rho_3, \rho_4}$, nâng cao đáng kể tính chính xác của hàm hợp lý tiến hóa.

Khung phân tích độc đáo

Khung phân tích của luận án tích hợp chặt chẽ 3 nền tảng lý thuyết:

1. Lý thuyết Quá trình Điểm Ngẫu nhiên Markov: Mô hình hóa xác suất chuyển dịch trạng thái không gian rời rạc qua thời gian liên tục.
2. Lý thuyết Đồ thị và Tiến hóa Cây phân loài: Thuật toán nối láng giềng cải tiến BIONJ [Gascuel, 1997] và các phép biến đổi hình thái topo NNI (Nearest Neighbor Interchange), SPR (Subtree Pruning and Regrafting).
3. Lý thuyết Thông tin và Thống kê Suy luận: Đánh giá qua hàm Log-Likelihood, Tiêu chuẩn Thông tin Akaike (AIC), Khoảng cách Topo Robinson-Foulds (RF), và Hệ số tương quan Pearson ($r$).

Điều kiện biên (boundary conditions) được xác định rõ ràng: Mô hình bảo toàn tính khả nghịch thời gian (time-reversibility: $\pi_i q_{ij} = \pi_j q_{ji}$), giả định các vị trí trên chuỗi tiến hóa độc lập có điều kiện theo cấu trúc cây (independent and identically distributed sites given the tree), và áp dụng cho các chuỗi prôtêin đồng nhánh có thể sắp hàng tin cậy.

Phương pháp nghiên cứu tiên tiến

Thiết kế nghiên cứu

Nghiên cứu tuân thủ chặt chẽ triết học thực chứng (positivism) với phương pháp tiếp cận định lượng toán học - tin sinh học tuyệt đối. Luận án thiết kế quy trình đa tầng (multi-level design) kết hợp giữa mô phỏng giải thuật tính toán và kiểm thử thực nghiệm trên dữ liệu sinh học đại quy mô.

Luận án đề xuất hai thuật toán phân tách sắp hàng đa chuỗi nhằm hạ cấp độ phức tạp tìm kiếm cây:

1. Phương pháp chia tách ngẫu nhiên: Phân rã sắp hàng $D_a$ có $m$ chuỗi thành các tập con kích thước $s \in [k, 2k]$ ($k \ge 4$). Dù giảm nhanh bậc tính toán, phương pháp này dễ phá vỡ quan hệ gần gũi giữa các chuỗi tương đồng.
2. Phương pháp chia tách dựa theo cấu trúc cây (BIONJ-based splitting): Khởi tạo mỗi chuỗi là một cụm, sử dụng ma trận khoảng cách tiến hóa và tiêu chuẩn BIONJ với độ phức tạp $O(m^3)$ để liên tục gộp hai cụm $G_1, G_2$ có khoảng cách ngắn nhất cho đến khi đạt ngưỡng $[k, 2k]$. Phương pháp này bảo toàn trọn vẹn cấu trúc nhánh cục bộ, triệt tiêu nguy cơ ghép nhầm các chuỗi có khoảng cách tiến hóa quá xa.

[Tập sắp hàng đa chuỗi Protein lớn]
                │
                ▼
  [Phân rã chuỗi bằng BIONJ (Ngưỡng k: 4, 8, 16, 32)]
                │
                ▼
  [Tái dựng cây phân loài ML cục bộ: (2m-5)!! cực tiểu]
                │
                ▼
  [Ước lượng ma trận Q' qua thuật toán EM (Expectation-Maximization)]
                │
        ┌───────┴───────┐
   [Q' ≈ Q?]         [Q' ≠ Q]
        │               │
     (Đúng)          (Sai: Cập nhật Q = Q' & lặp rút gọn)
        │
        ▼
[Mô hình tối ưu hóa hoàn chỉnh (FLU, LG4M, LG4X)]

Quy trình nghiên cứu rigorous

Quy trình thu thập và tinh lọc dữ liệu được thiết kế nghiêm ngặt:

• Trích xuất toàn bộ chuỗi prôtêin vi rút cúm từ NCBI GenBank (phiên bản 2011).
• Loại bỏ $100%$ chuỗi trùng lặp, phân loại rành mạch theo 3 chi cúm (Influenza A, B, C) và chia nhóm theo từng phân đoạn prôtêin cấu trúc/chức năng (HA, NA, PA, PB1, PB2, NP, M1, M2, NS1, NS2).
• Tiến hành sắp hàng đa chuỗi chuẩn hóa bằng phần mềm MUSCLE [Edgar, 2004] với các bộ tham số mặc định được kiểm soát.
• Thiết lập tiêu chí loại trừ: Bỏ qua các sắp hàng có dưới 5 chuỗi hoặc chiều dài ngắn hơn 50 axít amin.
• Kiểm tra độ hội tụ của thuật toán EM qua sai số tuyệt đối ma trận $|\mathbf{Q}^{(t+1)} - \mathbf{Q}^{(t)}|_\infty < \epsilon = 10^{-6}$.

Data và phân tích

Phân tích thống kê và thuật toán tối ưu hóa được triển khai trên nền tảng ngôn ngữ C/C++ hiệu năng cao, tích hợp thư viện tối ưu đại số tuyến tính và phần mềm sinh học phân tử chuyên sâu (PHYML, Tree-Puzzle, MUSCLE).

Các thước đo định lượng được xác lập chuẩn xác:

• Log-Likelihood trung bình trên mỗi vị trí: $$\Delta \ln L / \text{site} = \frac{1}{\sum_{a=1}^N l_a} \sum_{a=1}^N \left( \ln L(M_1 \mid D_a, T_a) - \ln L(M_2 \mid D_a, T_a) \right)$$
• Tiêu chuẩn AIC (Akaike Information Criterion): $\text{AIC} = 2K - 2\ln L$, với $K$ là số lượng tham số tự do của mô hình.
• Khoảng cách Robinson-Foulds (RF): Đo lường tỷ lệ các phân vùng hình thái (clades/bipartitions) bất tương đồng giữa hai cây phân loài $T_1$ và $T_2$.
• Hệ số tương quan tuyến tính Pearson ($r$): Đánh giá mức độ đồng biến giữa các hệ số hoán đổi $r_{ij}$ và véc tơ tần số $\pi_i$ giữa các ma trận.

Phát hiện đột phá và implications

Những phát hiện then chốt

1. Đột phá về tốc độ ước lượng ma trận ML: Kỹ thuật phân rã sắp hàng dựa trên cấu trúc cây BIONJ với ngưỡng $k=8$ và $k=16$ giúp tăng tốc độ ước lượng toàn trình từ 3 đến 6 lần trên cả hai tập dữ liệu chuẩn Pfam và Vi rút cúm. Với $k=4$, không gian tìm kiếm cấu trúc cây nhị phân không gốc thu hẹp tuyệt đối từ hàng triệu/hàng tỷ cấu trúc xuống đúng 3 cấu trúc cây, giải phóng hoàn toàn điểm nghẽn tính toán.
2. Bảo toàn độ chính xác xấp xỉ ma trận: Các ma trận ước lượng từ dữ liệu phân rã bằng cây ($LG_8, LG_{16}, FLU_8, FLU_{16}$) có hệ số tương quan Pearson $r > 0,999$ so với mô hình ước lượng trên toàn bộ dữ liệu gốc không chia tách. Sự khác biệt về Log-Likelihood trên mỗi vị trí là không đáng kể ($\Delta \ln L / \text{site} < 0,001$).
3. Rút ngắn 50% thời gian qua thuật toán lặp tinh giản: Luận án chứng minh rằng chỉ cần tối ưu hóa cấu trúc cây phân loài ở 2-3 vòng lặp đầu tiên của thuật toán EM; việc cố định topo cây và chỉ tối ưu độ dài nhánh ở các vòng lặp sau giúp tiết kiệm $50%$ tổng thời gian chạy mà không làm thay đổi giá trị tham số tối ưu cục bộ.
4. Tính ưu việt vượt trội của mô hình đa ma trận LG4M/LG4X: Trên 84 sắp hàng TreeBase và 300 sắp hàng HSSP, mô hình đa ma trận LG4M và LG4X đều đạt giá trị AIC trung bình trên mỗi vị trí thấp hơn đáng kể so với mô hình LG chuẩn, chứng minh sự khác biệt rõ rệt về mặt thống kê trong việc mô tả các vị trí có tốc độ biến đổi biến thiên phức tạp.
5. Phát hiện mô hình chuyên biệt FLU cho Vi rút cúm: Trên tập kiểm định độc lập 3.970 sắp hàng đa chuỗi vi rút cúm, mô hình FLU xếp hạng thứ nhất ($1^{\text{st}}$ rank) trên 2.499 sắp hàng và xếp hạng nhì trên 482 sắp hàng khi so sánh đồng thời với 14 mô hình quốc tế phổ biến (bao gồm LG, JTT, WAG, Dayhoff, BLOSUM62, mtREV, HIVb, HIVw). So sánh từng đôi cho thấy FLU vượt trội mô hình LG trên $88,7%$ số sắp hàng ($3.521/3.970$) và vượt trội mô hình HIVb trên $84,1%$ số sắp hàng. Khoảng cách Robinson-Foulds giữa cây dựng bằng FLU và các mô hình khác có sự phân hóa mạnh, chứng minh việc dùng sai mô hình ma trận sẽ dẫn đến sai lệch lớn về mặt cấu trúc topo phân loài vi rút.

Implications đa chiều

• Về mặt lý thuyết: Chứng minh tính tất yếu của việc tích hợp các ràng buộc cấu trúc hóa sinh và phân tách lớp tốc độ trong lý thuyết tiến hóa phân tử, khẳng định một mô hình ma trận tổng quát duy nhất không thể đại diện tối ưu cho mọi taxon vi sinh vật.
• Về mặt phương pháp luận: Cung cấp giải pháp phân tách chuỗi bảo toàn cấu trúc cây (BIONJ-based partitioning) có thể mở rộng áp dụng cho nhiều bài toán dữ liệu lớn khác trong tin sinh học như mô hình hóa codon hay tái dựng mạng lưới tiến hóa sinh vật (phylogenetic networks).
• Về mặt ứng dụng thực tiễn: Mô hình FLU cung cấp công cụ có độ chính xác cao chưa từng có để giải mã các biến chủng cúm, hỗ trợ dự báo đột biến kháng thuốc và tái tổ hợp kháng nguyên.
• Về mặt chính sách y tế công cộng: Cung cấp nền tảng tính toán tin cậy cho các chương trình giám sát dịch tễ học phân tử quốc gia và quốc tế, định hướng chiến lược lựa chọn chủng vắc-xin cúm mùa hàng năm.

Limitations và Future Research

Luận án thẳng thắn thừa nhận các giới hạn nghiên cứu:

1. Giới hạn giả định Markov: Mô hình vẫn duy trì giả định quá trình dừng (stationary) và tính độc lập giữa các vị trí lân cận, chưa xét đến tương tác bậc cao giữa các axít amin trong cấu trúc không gian 3D (epistasis/co-evolutionary sites).
2. Phạm vi chuyên biệt loài: Mô hình FLU mới chỉ tập trung trên vi rút cúm; các tác nhân gây bệnh nguy hiểm khác (như Coronavirus, Dengue, HBV, HCV) cần những bộ ma trận chuyên biệt tương ứng.
3. Độ dài chuỗi và khoảng trống (Gaps): Phương pháp chưa mô hình hóa trực tiếp cơ chế chèn/xóa (indels) vào ma trận thay thế mà loại bỏ các vị trí chứa gap trong quá trình tối ưu ML.

Định hướng nghiên cứu tương lai:

• Mở rộng thuật toán để xây dựng ma trận đồng tiến hóa bậc hai (co-evolutionary substitution matrices) tích hợp thông tin cấu trúc tinh thể prôtêin.
• Xây dựng hệ sinh thái ma trận chuyên biệt cho toàn bộ họ vi rút ARN có tốc độ đột biến cao.
• Nghiên cứu mô hình Markov phi dừng (non-homogeneous, non-stationary Markov models) thích ứng với sự thay đổi hàm lượng GC theo thời gian địa chất.
• Tích hợp kỹ thuật học sâu (Deep Learning) vào hệ thống tự động để ước lượng nhanh các siêu tham số mô hình.

Tác động và ảnh hưởng

Nghiên cứu tạo tiếng vang lớn trong cộng đồng khoa học quốc tế với 03 công bố trên các tạp chí danh giá thuộc danh mục ISI/SCI (bao gồm Bioinformatics và BMC Evolutionary Biology) cùng 02 báo cáo hội nghị quốc tế uy tín. Mô hình FLU và thuật toán ước lượng nhanh đã trở thành tài liệu tham khảo chuẩn mực trong phân tích tiến hóa cúm toàn cầu.

Về mặt công nghệ, luận án đã đóng gói toàn bộ thuật toán thành Hệ thống ước lượng mô hình tự động trực tuyến (Web-based automated estimation system), cho phép các phòng thí nghiệm sinh học phân tử trên toàn thế giới tự tải lên dữ liệu sắp hàng của loài sinh vật mục tiêu và tự động khởi tạo ma trận thay thế tối ưu chỉ trong vài giờ thay vì nhiều tuần tính toán thủ công.

Đối tượng hưởng lợi

• Nghiên cứu sinh & Nhà nghiên cứu Tin sinh học: Tiếp cận mã nguồn, thuật toán phân tách chuỗi hiệu năng cao và khung lý thuyết toán học hoàn chỉnh về mô hình Markov tiến hóa.
• Các nhà phân loại học & Tiến hóa phân tử: Sở hữu công cụ tái dựng cây phân loài có độ tin cậy thống kê vượt trội, giảm thiểu tối đa sai số topo do hiện tượng hút nhánh dài (long-branch attraction).
• Viện nghiên cứu vắc-xin & Công ty Dược phẩm sinh học: Ứng dụng mô hình FLU để mô phỏng chính xác đường đi tiến hóa của kháng nguyên bề mặt vi rút cúm (Hemagglutinin và Neuraminidase), rút ngắn chu kỳ nghiên cứu vắc-xin.
• Cơ quan kiểm soát dịch bệnh (CDC) & Tổ chức Y tế Thế giới (WHO): Ứng dụng công cụ tự động để phân tích nhanh phả hệ các ổ dịch cúm gia cầm độc lực cao (A/H5N1, A/H7N9) phục vụ cảnh báo sớm nguy cơ đại dịch.

Câu hỏi chuyên sâu

1. Đóng góp lý thuyết độc đáo nhất của luận án là gì?

Đó là việc mở rộng thuyết tiến hóa phân tử Markov từ dạng đơn ma trận đồng nhất sang mô hình đa ma trận kết hợp ràng buộc sinh học (LG4M, LG4X) và chứng minh sự cần thiết mang tính quy luật của ma trận thay thế chuyên biệt cho từng taxon vi rút (Taxon-specific evolutionary models), phá vỡ định kiến kéo dài nhiều thập kỷ về việc áp dụng ma trận tổng quát cho mọi loài.

2. Cải tiến phương pháp luận so với các nghiên cứu quốc tế trước đây?

So với phương pháp xấp xỉ ML của Whelan & Goldman [2001] (WAG) và Le & Gascuel [2008] (LG), luận án đề xuất bước đột phá kép: (1) Thuật toán phân rã chuỗi dựa trên khoảng cách cây BIONJ giúp hạ cấp độ phức tạp tìm kiếm cây ML từ $O((2m-5)!!)$ xuống quy mô hằng số với ngưỡng $k \in [4, 16]$, tăng tốc độ tính toán từ 3 đến 6 lần; (2) Thuật toán lặp rút gọn cố định topo cây ở các vòng lặp sau giúp tiết kiệm thêm $50%$ thời gian xử lý mà bảo toàn trọn vẹn độ chính xác tham số ($r > 0,999$).

3. Phát hiện thực nghiệm đáng ngạc nhiên nhất là gì?

Ma trận FLU dành riêng cho vi rút cúm có hệ số tương quan Pearson cực kỳ thấp so với các ma trận phổ quát hiện hành (ví dụ $r$ giữa FLU và LG chỉ đạt khoảng $0,65 - 0,70$; nhiều hệ số hoán đổi $r_{ij}$ trong FLU cao gấp 2 đến 5 lần so với LG và HIVb). Điều này cung cấp bằng chứng thực nghiệm đanh thép rằng cơ chế áp lực chọn lọc miễn dịch trên vi rút cúm tạo ra quy luật thay thế axít amin hoàn toàn dị biệt so với các prôtêin hình cầu thông thường.

4. Luận án có cung cấp quy trình tái lập (Replication Protocol) không?

Có. Luận án mô tả chi tiết toàn bộ thuật toán (mã giả cho Thuật toán chia tách ngẫu nhiên 2.1, Thuật toán chia tách BIONJ 2.2, Thuật toán ước lượng nhanh 4.1), công khai nguồn cơ sở dữ liệu (NCBI GenBank, Pfam, TreeBase, HSSP), các tham số phần mềm (MUSCLE, PHYML) và tích hợp hoàn chỉnh trên hệ thống máy chủ web tự động phục vụ cộng đồng kiểm chứng độc lập.

5. Kế hoạch nghiên cứu 10 năm được vạch ra như thế nào?

Lộ trình 10 năm tập trung vào 3 trục chính: (1) Phát triển mô hình thay thế phi đối xứng không gian 3D kết hợp tương tác mạng nơ-ron bậc cao; (2) Mở rộng thư viện ma trận tiến hóa cho toàn bộ các mầm bệnh nguy cơ cao trong danh mục ưu tiên của WHO; (3) Tích hợp học máy thời gian thực vào các hệ thống giải trình tự gen thế hệ mới (NGS) phục vụ chẩn đoán y học chính xác.

Kết luận

1. Luận án đã giải quyết thành công điểm nghẽn tính toán NP-khó của phương pháp Cực đại Khả năng trong ước lượng ma trận biến đổi axít amin bằng thuật toán phân tách chuỗi thông minh BIONJ, nâng cao tốc độ tính toán từ 3 đến 6 lần.
2. Đề xuất thành công thuật toán ước lượng lặp cải tiến giúp cắt giảm $50%$ thời gian tính toán thông qua việc tối ưu hóa có chọn lọc cấu trúc cây phân loài.
3. Phát triển thành công họ mô hình đa ma trận tiên tiến (LG4M, LG4X) tích hợp tính không đồng nhất của tốc độ tiến hóa tại các vị trí, cải thiện vượt trội giá trị Log-Likelihood và tiêu chuẩn AIC so với các mô hình đơn ma trận trên dữ liệu chuẩn quốc tế.
4. Xây dựng và kiểm định thành công mô hình ma trận chuyên biệt FLU cho vi rút cúm trên 71.087 chuỗi prôtêin, chứng minh tính ưu việt tuyệt đối ($1^{\text{st}}$ rank trên 2.499/3.970 sắp hàng) so với 14 mô hình quốc tế đương đại.
5. Hiện thực hóa các đóng góp học thuật thành Hệ thống ước lượng ma trận tự động trực tuyến, phục vụ thiết thực cho cộng đồng tin sinh học và dịch tễ học toàn cầu.
6. Mở ra 3 hướng nghiên cứu mới đầy tiềm năng: mô hình hóa tiến hóa phụ thuộc cấu trúc không gian 3D, mở rộng hệ sinh thái mô hình chuyên biệt taxon cho vi rút đột biến nhanh, và tích hợp thuật toán phân tích tiến hóa vào chẩn đoán lâm sàng thời gian thực.

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

Chương 1 giới thiệu khái quát về chuỗi ADN, chuỗi axít amin và các phép biến đổi trên chuỗi axít amin. Sau đó là phần giới thiệu về bài toán mô hình hoá quá trình biến đổi axít amin và bài toán ước lượng mô hình biến đổi axít amin. Tiếp theo 17 là phần trình bày về hai cách tiếp cận chính để ước lượng mô hình biến đổi axít amin là phương pháp đếm và phương pháp cực đại khả năng (maximum likelihood). Phần cuối của chương này giới thiệu về phương pháp xây dựng cây phân loài bằng phương pháp cực đại khả năng và các phương pháp so sánh hai mô hình biến đổi axít amin.

Chương 2 đề xuất phương pháp ước lượng nhanh mô hình biến đổi axít amin. Luận án đề xuất hai phương pháp chia tách nhỏ dữ liệu đầu vào. Hai phương pháp này giúp giảm thời gian xây dựng cây phân loài, một bước chiếm rất nhiều thời gian trong quá trình ước lượng mô hình biến đổi axít amin. Các thực nghiệm đã chứng tỏ được hiệu quả của hai phương pháp này.

Chương 3 của luận án giới thiệu mô hình biến đổi axít amin sử dụng nhiều ma trận, một cải tiến mới so với các mô hình đơn ma trận hiện nay. Mô hình mới này sử dụng thêm các ràng buộc trong sinh học phân tử giúp tăng cường khả năng mô hình hoá các quá trình biến đổi của các chuỗi axít amin. Các thực nghiệm với hai bộ dữ liệu HSSP và TreeBase đã chứng tỏ mô hình biến đổi đa ma trận có độ chính xác cao hơn các mô hình hiện tại. Chương 4 đề xuất một thuật toán ước lượng mô hình biến đổi axít amin cải tiến giúp giảm 50% thời gian ước lượng mô hình.

Có được điều này chính là do thuật toán mới đã tìm cách giảm bớt số bước tối ưu cấu trúc cây phân loài – một bước chiếm nhiều thời gian trong quá trình ước lượng. Chương này cũng giới thiệu hệ thống ước lượng mô hình tự động cài đặt thuật toán cải tiến trên. Chương 5 trình bày mô hình biến đổi axít amin cho vi rút cúm, gọi là mô hình FLU. Phần sau của chương là các kết quả so sánh mô hình FLU với các mô hình khác.

Qua các thực nghiệm, mô hình FLU đã chứng tỏ được hiệu quả cao hơn hẳn các mô hình hiện tại khi phân tích dữ liệu vi rút cúm. BÀI TOÁN ƯỚC LƯỢNG SỰ BIẾN ĐỔI CỦA AXÍT AMIN 1. Giới thiệu chung Trong phần này chúng tôi sẽ trình bày các khái niệm cơ bản về ADN, axít amin, sắp hàng đa chuỗi và cây phân loài. ADN và axít amin Trong sinh học phân tử, Axít Deoxyribo Nucleic (viết tắt ADN) mang thông tin di truyền mã hóa cho hoạt động sinh trưởng và phát triển của các loài sinh vật [4, 5].

ADN được cấu tạo từ nhiều phân tử nhỏ gọi là các nuclêotít. Có 4 loại nuclêotít là: Adenine (A), Thymine (T), Cytosine (C), và Guanine (G). Các nuclêotít kết hợp với nhau thành một mạch dài nhờ các liên kết phôtphođieste để tạo thành một chuỗi nuclêotít (còn gọi là chuỗi pôlinuclêotít). ADN có cấu tạo gồm hai chuỗi nuclêotít xoắn kép với nhau, trong đó các nuclêotít giữa 2 chuỗi liên kết với nhau bằng liên kết hiđrô theo nguyên tắc bổ sung: A với T và G với C [1].1: Minh họa cấu tạo của một phân tử axít amin.

19 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à nhóm biến đổi R quyết định tính chất của axít amin [1, 16].1 minh họa cấu tạo chung của một axít amin. 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 péptít (còn gọi là chuỗi pôlipéptít) để tạo thành một chuỗi axít amin hay còn gọi là chuỗi prôtêin. 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 chuỗi prôtêin [5]. Mối quan hệ giữa nuclêotít và axít amin được thể hiện qua quá trình tổng hợp prôtêin.

Trong một chuỗi nuclêotít mã hóa prôtêin, mỗi bộ ba nuclêotít 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 kết thúc của một quá trình tổng hợp prôtêin [44]. 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.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 20 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 [16]. Tên đầy đủ và viết tắt của 20 axít amin được liệt kê đầy đủ trong Bảng 1.2: 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. Các phép biến đổi trên chuỗi axít amin Theo thuyết tiến hoá của Darwin thì các sinh vật đều có chung một nguồn gốc [19].

Sự giống nhau giữa các sinh vật có thể được thể hiện bằng sự giống nhau ở kiểu hình, kiểu gen hoặc các chuỗi nuclêotít, axít amin. Hai chuỗi axít amin ở hai sinh vật khác nhau cùng tiến hoá từ một chuỗi axít amin tổ tiên thì gọi là hai chuỗi axít amin tương đồng. Hai chuỗi axít amin tương đồng có các khác biệt là do có các biến đổi trong quá trình tiến hoá. Các biến đổi trên chuỗi axít amin có thể do các 21 biến đổi ở vùng mã hoá của chuỗi ADN trước quá trình tổng hợp prôtêin hoặc do biến đổi tại các bước phiên mã, dịch mã của quá trình tổng hợp prôtêin.

Các phép biến đổi thông thường được chia làm ba loại chính là [45]: - Thay thế: một axít amin này bị thay thế bằng một axít amin khác. - Xoá: một hoặc một số axít amin bị xoá khỏi chuỗi prôtêin. - Chèn: một hoặc một số axít amin được chèn vào chuỗi prôtêin.2 minh hoạ một ví dụ các phép biến đổi trên hai chuỗi axít amin. Cột 1, 2 và 3 chứa các axít amin khác nhau thể hiện các phép thay thế.

Các ký tự trống (-) trên cột 4 và 6 thể hiện các phép chèn hoặc xoá đã xảy ra. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Chuỗi 1 E H A - D N E M C Q L K P L P Chuỗi 2 F G D R D - E M C Q L K P L P Hình 1.2: Một ví dụ các phép biến đổi trên hai chuỗi axít amin tương đồng. Sắp hàng đa chuỗi axít amin Quá trình biến đổi làm cho các chuỗi axít amin tương đồng khác nhau cả về nội dung cũng như độ dài. Sắp hàng đa chuỗi sẽ giúp làm rõ các phép biến đổi giữa các chuỗi axít amin.

Sắp hàng đa chuỗi có thể được hiểu như một ma trận các axít amin, trong đó mỗi hàng chính là một chuỗi axít amin; còn mỗi cột (vị trí) chứa các axít amin tương đồng của các chuỗi (xem thêm Hình 1. Chúng ta có thể sử dụng sắp hàng đa chuỗi để xây dựng cây phân loài giúp đánh giá nguồn gốc tiến hóa của các chuỗi [44]. 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 các chuỗi trong sắp hàng.3 minh hoạ 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 22 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 D R - D E M C Q L K P L P Vượn F G D R - V H M C Q L K P L P Hình 1.3: Minh họa một sắp hàng đa chuỗi axít amin của bốn loài linh trưởng. Cây phân loài Cây phân loài (cây tiến hóa) là một dạng sơ đồ phân nhánh thể hiện quá trình tiến hóa của các loài sinh vật và cho biết sự tương đồng và khác biệt về giữa chúng. Các sinh vật liên kết với nhau trong cây được cho là có cùng một tổ tiên chung.4: Một ví dụ về cây phân loài giữa bốn loài linh trưởng. Trong cây phân loài mỗi nút lá biểu diễn cho một loài sinh vật hiện tại, mỗi nút cha đại diện cho tổ tiên gần nhất của các nút con.

Độ dài cạnh có thể được hiểu như là ước lượng khoảng cách về thời gian giữa các loài. Trong luận án này, nếu không có chú thích thêm thì cây phân loài được gọi tắt là cây.4 minh họa một cây phân loài thể hiện mối quan hệ giữa một số loài linh trưởng. Mô hình hoá quá trình biến đổi axít amin 1. Sự khác biệt giữa hai chuỗi tương đồng Có sự khác nhau giữa hai chuỗi axít amin tương đồng cùng tiến hóa từ một tổ tiên chung là do có các biến đổi giữa các axít amin trong quá trình tiến hóa.

Hai loại khoảng cách thường dùng để đo sự khác biệt giữa hai chuỗi axít amin tương đồng x và y là khoảng cách quan sát và khoảng cách di truyền [44]: - Khoảng cách quan sát giữa hai chuỗi axít amin x và y là tỷ lệ giữa số vị trí trên hai chuỗi có các axít amin không giống nhau so với chiều dài chuỗi.