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 luận án

Luận án tiến sĩ "Các phương pháp xây dựng ma trận biến đổi axít amin" được thực hiện bởi nghiên cứu sinh Đặng Thị Thu Hiền thuộc chuyên ngành Khoa học Máy tính (mã số 62.01), dưới sự hướng dẫn khoa học của TS. Lê Sỹ Vinh và TS. Lê Sĩ Quang tại Trường Đại học Công nghệ, Đại học Quốc gia Hà Nội năm 2013.

Về tính cấp thiết, sự phát triển của công nghệ sinh học phân tử dẫn đến sự bùng nổ dữ liệu chuỗi sinh học, đặc biệt là chuỗi ADN và chuỗi prôtêin trên các cơ sở dữ liệu quốc tế như GenBank và UniProt. Trong tin sinh học, các bài toán cốt lõi bao gồm sắp hàng đa chuỗi, tìm kiếm chuỗi tương đồng và xây dựng cây phân loài đều phụ thuộc trực tiếp vào mô hình ma trận biến đổi axít amin (mô hình $Q$). Ma trận này biểu diễn xác suất và tốc độ biến đổi thay thế giữa 20 axít amin trong quá trình tiến hóa. Do việc ước lượng đồng thời khoảng 200 tham số trong quá trình phân tích dữ liệu thực tế là bài toán khó và tốn kém tài nguyên tính toán, các nhà nghiên cứu thường phải sử dụng một mô hình chung (general model) được ước lượng trước, tiêu biểu như PAM (năm 1978) hay LG (năm 2008).

Tác giả luận án xác định ba khoảng trống nghiên cứu chính của các phương pháp hiện tại:

1. Chi phí tính toán của các thuật toán xây dựng cây phân loài dùng trong quá trình ước lượng mô hình cực đại khả năng (Maximum Likelihood - ML) rất lớn, thường mất từ vài ngày đến nhiều tuần khi xử lý các tập dữ liệu lớn.
2. Độ chính xác của các mô hình hiện tại bị giới hạn do việc đơn giản hóa quá trình mô hình hóa, loại bỏ nhiều ràng buộc sinh học phân tử quan trọng, đặc biệt là tính không đồng nhất của tốc độ biến đổi tại các vị trí khác nhau trên chuỗi.
3. Việc sử dụng các mô hình chung không thể phản ánh chính xác các đặc trưng tiến hóa riêng biệt của từng loài sinh vật, trong khi các công cụ xây dựng mô hình chuyên biệt cho từng loài chưa được tự động hóa.

Mục tiêu nghiên cứu của luận án được cụ thể hóa thành 3 nhiệm vụ:

1. Đề xuất các phương pháp mới nhằm tăng tốc độ quá trình xây dựng cây phân loài, giảm bớt số bước tối ưu cấu trúc cây, từ đó giảm thời gian ước lượng mô hình biến đổi axít amin.
2. Đưa thêm các ràng buộc trong sinh học phân tử vào quá trình mô hình hóa (đặc biệt là mô hình hóa tính không đồng nhất về tốc độ biến đổi theo vị trí) nhằm nâng cao độ chính xác của mô hình khi phân tích dữ liệu prôtêin.
3. Xây dựng một hệ thống ước lượng tự động mô hình biến đổi axít amin từ dữ liệu người dùng nhằm hỗ trợ việc xây dựng các mô hình riêng biệt cho từng loài sinh vật; đồng thời xây dựng và kiểm nghiệm thực nghiệm mô hình biến đổi riêng cho vi rút cúm (mô hình FLU).

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

• Đối tượng nghiên cứu: Quá trình tiến hóa và biến đổi thay thế của 20 axít amin; các mô hình Markov thời gian liên tục; ma trận tốc độ biến đổi tức thời $Q$; ma trận hệ số hoán đổi $R$; véc tơ tần số $\Pi$; các thuật toán suy luận cây phân loài bằng phương pháp cực đại khả năng.
• Phạm vi dữ liệu: Tập dữ liệu các chuỗi prôtêin vi rút cúm thu thập từ NCBI (phiên bản năm 2011) với 1.373 sắp hàng đa chuỗi (tổng cộng 71.087 chuỗi) dùng để huấn luyện và 3.970 sắp hàng dùng để kiểm tra; bộ dữ liệu chuẩn Pfam gồm 3.912 sắp hàng (49.637 chuỗi) trích xuất từ Swiss-Prot và TrEMBL; các bộ dữ liệu kiểm chuẩn TreeBase (84 sắp hàng) và HSSP (300 sắp hàng).

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

Quá trình nghiên cứu ước lượng ma trận biến đổi axít amin trong hơn 30 năm qua được tác giả hệ thống hóa thành hai hướng tiếp cận chính:

1. Hướng tiếp cận bằng phương pháp đếm (counting approach):

• Dayhoff và cộng sự (1978) xây dựng mô hình PAM (Point Accepted Mutation) từ 71 nhóm prôtêin có độ tương đồng cao (tối thiểu 85%). Dựa trên các quan sát biến đổi trực tiếp, ma trận PAM1 được thiết lập và nhân lũy thừa để tạo ra chuỗi ma trận đến PAM250.
• Jones, Taylor và Thornton (1992) áp dụng phương pháp đếm của Dayhoff trên tập dữ liệu prôtêin lớn hơn để đề xuất mô hình JTT, khắc phục một phần hạn chế về kích thước dữ liệu của PAM.
• Henikoff và Henikoff (1992) phát triển ma trận BLOSUM (BLOSUM45, BLOSUM62, BLOSUM80) dựa trên cơ sở dữ liệu BLOCKS, tính toán tần số thay thế tại các vùng bảo tồn giữa các chuỗi prôtêin có tỷ lệ tương đồng tối thiểu tương ứng. Nhược điểm căn bản của nhóm phương pháp đếm là chỉ hoạt động chính xác trên các tập dữ liệu có độ tương đồng cao, dễ gặp lỗi hệ thống khi chuỗi có khoảng cách tiến hóa xa do xuất hiện đa biến đổi, biến đổi song song và biến đổi ngược.

2. Hướng tiếp cận bằng phương pháp cực đại khả năng (maximum likelihood approach):

• Adachi và Hasegawa (1996) đề xuất mô hình mtREV cho chuỗi prôtêin ti thể của 20 loài động vật có xương sống bằng phương pháp cực đại khả năng, chỉ ra tính ưu việt của ML so với phương pháp đếm trong việc hạn chế sai số hệ thống.
• Whelan và Goldman (2001/2002) phát triển phương pháp ML xấp xỉ trên cơ sở dữ liệu gồm 3.905 chuỗi prôtêin để tạo ra mô hình WAG, giúp giảm bớt độ phức tạp tính toán của phép suy luận ML toàn diện.
• Le và Gascuel (2008) kết hợp thông tin về tính không đồng nhất của tốc độ biến đổi theo vị trí trên cơ sở dữ liệu Pfam (gồm khoảng 50.000 chuỗi với 6,5 triệu axít amin) để xây dựng mô hình LG. Mô hình LG được đánh giá là mô hình chung chuẩn xác nhất ở thời điểm nghiên cứu.

Khoảng trống luận án lựa chọn giải quyết: Mặc dù phương pháp ML của Le và Gascuel đem lại độ chính xác cao, thời gian tính toán của nó vẫn quá lớn, trở thành rào cản khi ứng dụng trên các tập dữ liệu sinh học quy mô lớn. Luận án định vị trọng tâm vào việc giải quyết nút thắt cổ chai về thời gian ở bước dựng cây ML (chiếm phần lớn tổng thời gian tính toán), chuyển đổi cấu trúc mô hình từ đơn ma trận sang đa ma trận để tích hợp các ràng buộc sinh học thực tế, và giải quyết bài toán thiếu hụt mô hình tiến hóa đặc thù cho vi rút cúm.

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

Luận án dựa trên nền tảng sinh học phân tử và lý thuyết xác suất thống kê:

• Quá trình dịch mã sinh học: 64 codon (bộ ba nuclêotít) mã hóa cho 20 axít amin tự nhiên và 3 stop-codon (TAA, TAG, TGA).
• Mô hình Markov thời gian liên tục: Quá trình biến đổi giữa 20 axít amin tại một vị trí trên chuỗi được mô hình hóa thành một quá trình Markov với tập 20 trạng thái $S = {A, R, N, D, C, Q, E, G, H, I, L, K, M, F, P, S, T, W, Y, V}$ thỏa mãn 4 tính chất: độc lập với quá khứ (memoryless), đồng nhất (homologous), liên tục (continuous) và ổn định (stationary).
• Ma trận tốc độ biến đổi tức thời $Q = (q_{ij}){20 \times 20}$: Với $i \neq j$, $q{ij} = r_{ij}\pi_j$; với $i = j$, $q_{ii} = -\sum_{j \neq i} q_{ij}$. Ma trận được chuẩn hóa thỏa mãn $\sum_{i=1}^{20} \pi_i q_{ii} = -1$.
• Phân tích tham số: Ma trận hệ số hoán đổi đối xứng $R = (r_{ij})$ có 189 tham số tự do ($19 \times 20 / 2 - 1$). Véc tơ tần số ổn định $\Pi = (\pi_i)$ có 19 tham số độc lập ($\sum \pi_i = 1$). Tổng số tham số cần ước lượng cho mô hình $Q$ là 208 tham số.
• Phân phối Gamma: Sử dụng phân phối Gamma với tham số định hình $\alpha$ để mô hình hóa tính không đồng nhất về tốc độ biến đổi giữa các vị trí trên chuỗi.

Phương pháp thực tế:

• Phương pháp cực đại khả năng (ML): Hàm likelihood của mô hình $Q$ và cây phân loài $T$ trên sắp hàng $D$ có chiều dài $l$ được tính theo công thức: $$L(Q, T | D) = \prod_{i=1}^l L(Q, T | D_i)$$ Đối với tập $N$ sắp hàng đa chuỗi $A = {D_1, \dots, D_N}$, bài toán tìm mô hình $Q$ tối ưu quy về: $$Q = \arg\max_Q \sum_{a=1}^N \ln L(Q | T^_a, D_a)$$ trong đó $T^_a$ là cây phân loài gần tối ưu của sắp hàng $D_a$.
• Thuật toán cực đại hóa kỳ vọng (Expectation Maximization - EM) được sử dụng để ước lượng các tham số của ma trận từ cây phân loài và sắp hàng.
• Thuật toán BIONJ (độ phức tạp $O(m^3)$ với $m$ là số chuỗi) được sử dụng để tính toán cấu trúc gom cụm khoảng cách di truyền giữa các chuỗi.
• Phần mềm MUSCLE được sử dụng trong khâu tiền xử lý để xây dựng các sắp hàng đa chuỗi.
• Tiêu chuẩn đánh giá: Tiêu chuẩn thông tin Akaike (AIC), hàm sai biệt log-likelihood trung bình trên một vị trí, khoảng cách Robinson-Foulds (RF) để đo độ khác biệt cấu trúc cây, và hệ số tương quan tuyến tính Pearson.

Nguồn tư liệu và dữ liệu:

• Dữ liệu vi rút cúm: 71.087 chuỗi prôtêin tải từ NCBI năm 2011, phân loại theo ba nhóm cúm A, B, C và theo từng loại prôtêin, khử trùng lặp và chia thành 1.373 sắp hàng huấn luyện (kích thước từ 5 đến 99 chuỗi) cùng 3.970 sắp hàng kiểm tra độc lập.
• Bộ dữ liệu Pfam: 3.912 sắp hàng với 49.637 chuỗi prôtêin trích xuất từ Swiss-Prot và TrEMBL.
• Dữ liệu đối sánh mô hình: 84 sắp hàng từ TreeBase và 300 sắp hàng từ HSSP.

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

Chương 1: Bài toán ước lượng sự biến đổi của axít amin

Chương 1 hệ thống hóa cơ sở sinh học và toán học của bài toán ước lượng mô hình tiến hóa prôtêin. Tác giả phân tích cơ chế hình thành khoảng cách quan sát ($p$) và khoảng cách di truyền ($d$), chứng minh rằng do tác động của đa biến đổi, biến đổi song song và biến đổi ngược, khoảng cách quan sát luôn nhỏ hơn khoảng cách di truyền thực tế, đòi hỏi phải sử dụng mô hình xác suất Markov để hiệu chỉnh.

Tác giả phân tích chi tiết không gian tìm kiếm cây phân loài nhị phân không gốc đối với sắp hàng gồm $m$ chuỗi. Số lượng cấu trúc cây phân loài khả dĩ tăng bùng nổ theo công thức $(2m - 5)!! = \prod_{i=3}^m (2i - 5)$, khiến bài toán tìm cây tối ưu theo tiêu chuẩn ML trở thành bài toán NP-khó.

Số chuỗi ($m$)	Số lượng cây nhị phân không gốc
3	1
4	3
5	15
6	105
7	945
8	10.395
9	135.135
10	2.027.025

Chương này cũng phân định rõ ưu nhược điểm của các phương pháp đếm (PAM, JTT, BLOSUM) và phương pháp ML (mtREV, WAG, LG), đồng thời thiết lập ba tiêu chí toán học chuẩn để so sánh hai mô hình: hiệu số log-likelihood trên cây phân loài ML, khoảng cách cấu trúc cây Robinson-Foulds (RF) và hệ số tương quan Pearson giữa các ma trận hệ số hoán đổi $R$ và véc tơ tần số $\Pi$.

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

Chương 2 tập trung giải quyết nút thắt thời gian của thuật toán ML truyền thống. Tác giả tiến hành thực nghiệm định lượng thời gian chạy trên 200 sắp hàng lớn nhất của bộ dữ liệu Pfam và 1.373 sắp hàng của bộ dữ liệu vi rút cúm:

• Với 200 sắp hàng Pfam: Bước xây dựng cây bằng ML chiếm tới 35 giờ, trong khi bước ước lượng tham số ma trận bằng EM chỉ chiếm 4 giờ.
• Với 1.373 sắp hàng vi rút cúm: Bước xây dựng cây chiếm 273 giờ, trong khi bước ước lượng tham số chỉ chiếm 10 giờ.

Từ thực tế bước dựng cây chiếm phần lớn tổng thời gian xử lý do số chuỗi $m$ trong sắp hàng lớn, tác giả đề xuất hai thuật toán chia tách sắp hàng lớn thành các sắp hàng nhỏ có kích thước nằm trong khoảng $[k, 2k]$ (với ngưỡng $k \ge 4$):

1. Phương pháp chia tách ngẫu nhiên (Thuật toán 2.1): Chọn ngẫu nhiên $s$ chuỗi ($k \le s \le 2k$) từ sắp hàng ban đầu để tạo thành sắp hàng con cho đến khi số chuỗi còn lại nhỏ hơn $k + 4$.
2. Phương pháp chia tách dựa theo cấu trúc cây (Thuật toán 2.2): Sử dụng ma trận khoảng cách và thuật toán BIONJ để gom cụm các chuỗi có quan hệ gần gũi. Hai nhóm có khoảng cách nhỏ nhất được gộp lại tuần tự nếu tổng số chuỗi không vượt quá $2k$. Khi kích thước nhóm đạt ngưỡng giữa $k$ và $2k$, nhóm đó được tách thành một sắp hàng con độc lập.

Kết quả thực nghiệm trên hai bộ dữ liệu Pfam và vi rút cúm với các ngưỡng $k \in {4, 8, 16, 32}$ cho thấy:

• Cả hai phương pháp đều giảm thời gian xây dựng mô hình từ 3 đến 6 lần so với phương pháp gốc không chia tách.
• Phương pháp chia tách dựa theo cấu trúc cây vượt trội hơn phương pháp ngẫu nhiên về chất lượng cây và giá trị log-likelihood. Do phương pháp BIONJ giữ lại các chuỗi có quan hệ gần nhau trong cùng một nhóm con, nó hạn chế hiện tượng ghép cặp các chuỗi có khoảng cách tiến hóa quá xa, giúp ma trận ước lượng giữ được độ chính xác tương đương với khi chạy trên toàn bộ tập dữ liệu gốc mà không bị suy giảm thông tin.

Chương 3: Xây dựng mô hình biến đổi đa ma trận

Chương 3 đề xuất giải pháp cho hạn chế của các mô hình đơn ma trận (như LG hay WAG) vốn giả định rằng mọi vị trí trên prôtêin đều chịu chung một cơ chế thay thế axít amin. Trên thực tế sinh học, các vị trí nằm ở bề mặt prôtêin hoặc vùng chức năng có áp lực chọn lọc và tốc độ biến đổi rất khác nhau.

Tác giả đề xuất mô hình biến đổi đa ma trận gồm $K$ ma trận thành phần $Q_1, Q_2, \dots, Q_K$. Mỗi ma trận $Q_k$ có một trọng số $w_k$ ($\sum w_k = 1$) và tốc độ tương đối $\rho_k$. Cụ thể, luận án phát triển hai biến thể mô hình:

• Mô hình LG4M: Sử dụng 4 ma trận tốc độ riêng biệt tương ứng với 4 mức tốc độ tiến hóa khác nhau tại các vị trí trên chuỗi prôtêin.
• Mô hình LG4X: Mở rộng LG4M bằng cách tối ưu hóa đồng thời cấu trúc ma trận và tham số phân phối tốc độ biến đổi trên từng phân lớp vị trí.

Thực nghiệm đánh giá mô hình được tiến hành trên hai tập dữ liệu độc lập: 84 sắp hàng của TreeBase và 300 sắp hàng của HSSP. Các mô hình được so sánh theo tiêu chuẩn AIC trung bình trên mỗi vị trí và sai phân log-likelihood đối ứng với mô hình LG:

• Trên cả hai bộ dữ liệu TreeBase và HSSP, các mô hình đa ma trận LG4M và LG4X đều đạt giá trị AIC và log-likelihood tốt hơn mô hình đơn ma trận LG trên đa số các sắp hàng thử nghiệm.
• Về chi phí tài nguyên: Phân tích thực nghiệm trên 84 sắp hàng TreeBase cho thấy mô hình đa ma trận yêu cầu dung lượng bộ nhớ lớn hơn và thời gian xử lý tăng lên tương ứng với số lượng ma trận thành phần, nhưng mức độ sử dụng tài nguyên vẫn nằm trong giới hạn cho phép của hệ thống tính toán tiêu chuẩn.

Chương 4: Hệ thống ước lượng mô hình tự động

Trong Chương 4, tác giả phát hiện thêm một nguyên nhân gây lãng phí thời gian tính toán trong quy trình ML: việc tối ưu hóa lại toàn bộ cấu trúc cây phân loài ở mỗi vòng lặp ước lượng mô hình là không cần thiết, vì cấu trúc tô pô của cây thay đổi rất ít sau các vòng lặp đầu tiên.

Tác giả đề xuất thuật toán ước lượng nhanh cải tiến (Thuật toán 4.1): Cố định việc tối ưu hóa cấu trúc cây và chỉ cập nhật độ dài các nhánh của cây sau 3 lần lặp đầu tiên. Kết quả thực nghiệm đối soát thời gian cho thấy:

• Quá trình ước lượng lại mô hình LG trên dữ liệu Pfam giảm được 50% thời gian chạy.
• Quá trình ước lượng lại mô hình FLU trên dữ liệu vi rút cúm cũng giảm được 50% tổng thời gian tính toán, trong khi ma trận thu được có giá trị log-likelihood và các hệ số hoán đổi sai khác không đáng kể so với phương pháp lặp đầy đủ.

Dựa trên thuật toán cải tiến này, tác giả thiết kế và xây dựng một hệ thống phần mềm ước lượng mô hình tự động trực tuyến. Hệ thống cho phép người dùng tải lên tập dữ liệu sắp hàng đa chuỗi định dạng chuẩn, tự động thực hiện các công đoạn tiền xử lý, chia tách sắp hàng, suy luận cây ML và ước lượng ma trận $Q$ tương ứng, xuất ra ma trận hệ số hoán đổi $R$ và tần số $\Pi$ phục vụ trực tiếp cho các phần mềm phân tích phát sinh loài.

Chương 5: Mô hình biến đổi axít amin cho vi rút cúm

Chương 5 ứng dụng các phương pháp đã phát triển để xây dựng mô hình biến đổi axít amin chuyên biệt cho vi rút cúm, đặt tên là mô hình FLU. Dữ liệu huấn luyện gồm 1.373 sắp hàng prôtêin vi rút cúm từ NCBI (phiên bản 2011).

Mô hình FLU được đánh giá đối soát toàn diện với 14 mô hình thay thế axít amin phổ biến hiện hành, bao gồm: HIVb, HIVw, JTT, LG, mtREV, WAG, Dayhoff, DCMut, Blosum62, cpREV, RtREV, VT, MtMam và MtArt.

Kết quả kiểm định thực nghiệm:

• Tương quan hệ số hoán đổi: Hệ số tương quan Pearson giữa ma trận của FLU và 14 mô hình còn lại đều ở mức thấp. So sánh độ lệch tương đối cho thấy nhiều hệ số hoán đổi trong FLU chênh lệch từ 2 đến 5 lần so với các hệ số tương ứng trong LG và HIVb.
• Tiêu chuẩn AIC: Mô hình FLU đạt giá trị AIC trung bình trên mỗi vị trí thấp nhất (tốt nhất) trong toàn bộ 15 mô hình thử nghiệm.
• Kiểm tra trên 3.970 sắp hàng prôtêin vi rút cúm độc lập:
  • FLU xếp thứ nhất (1st) trên 2.499 sắp hàng và xếp thứ nhì (2nd) trên 482 sắp hàng trên tổng số 3.970 sắp hàng thử nghiệm.
  • Trong các phép so sánh cặp đôi (pairwise) giữa FLU với các mô hình tiêu biểu (LG, JTT, HIVb, HIVw), FLU đạt log-likelihood vượt trội trên phần lớn các sắp hàng thử nghiệm.
• Sai khác cấu trúc cây: Đo lường khoảng cách Robinson-Foulds (RF) chỉ ra rằng cây phân loài xây dựng bằng mô hình FLU có cấu trúc phân nhánh khác biệt rõ rệt so với cây xây dựng bằng mô hình LG hay JTT.
• Tính bền vững của mô hình: Thử nghiệm phân chia dữ liệu huấn luyện thành hai tập con ngẫu nhiên độc lập để ước lượng hai mô hình FLU1 và FLU2. Hệ số tương quan Pearson giữa ba mô hình FLU, FLU1 và FLU2 đạt mức rất cao (xấp xỉ 1,0), khẳng định tính ổn định thống kê của mô hình.

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

Luận án đã đạt được các kết quả cụ thể và đóng góp mới sau:

1. Đóng góp về mặt phương pháp luận và thuật toán:

• Đề xuất hai phương pháp chia tách sắp hàng đa chuỗi lớn thành các sắp hàng nhỏ hơn (ngẫu nhiên và dựa trên cấu trúc cây BIONJ), giúp giảm thời gian xây dựng cây phân loài ML và tăng tốc độ ước lượng mô hình từ 3 đến 6 lần mà không làm suy giảm chất lượng ma trận.
• Đề xuất giải thuật tối ưu hóa quy trình lặp bằng cách giới hạn số bước cập nhật cấu trúc cây sau 3 vòng lặp, giúp cắt giảm 50% thời gian ước lượng ma trận biến đổi axít amin.
• Xây dựng mô hình biến đổi đa ma trận (LG4M và LG4X) tích hợp tính không đồng nhất về tốc độ biến đổi theo vị trí, nâng cao giá trị log-likelihood và cải thiện chỉ số AIC so với mô hình đơn ma trận LG trên các bộ dữ liệu TreeBase và HSSP.

2. Đóng góp về mặt thực tiễn và ứng dụng:

• Xây dựng thành công hệ thống ước lượng mô hình tự động trực tuyến, hỗ trợ cộng đồng nghiên cứu tự động hóa quá trình xây dựng các ma trận biến đổi axít amin riêng biệt từ dữ liệu thực nghiệm.
• Ước lượng thành công mô hình FLU chuyên biệt cho vi rút cúm. Mô hình này được chứng minh qua 3.970 sắp hàng thực nghiệm là có hiệu quả cao hơn hẳn 14 mô hình hiện có khi phân tích dữ liệu tiến hóa và phát sinh loài của vi rút cúm.

Kiến nghị và giải pháp:

• Luận án khuyến nghị sử dụng mô hình FLU thay thế cho các mô hình chung như LG hay JTT trong tất cả các nghiên cứu phân tích phát sinh loài, dự đoán biến đổi kháng nguyên và truy vết nguồn gốc tiến hóa của các chủng vi rút cúm.
• Khuyến nghị áp dụng khung ước lượng đa ma trận và hệ thống tự động để xây dựng tiếp các ma trận chuyên biệt cho các loài vi sinh vật gây bệnh có tốc độ đột biến cao khác.

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

Về mặt hạn chế:

• Mô hình Markov thời gian liên tục được sử dụng trong luận án vẫn dựa trên các giả định lý thuyết về tính dừng (stationary) và tính đồng nhất theo thời gian (homologous), chưa mô phỏng được những giai đoạn áp lực chọn lọc đột biến thay đổi đột ngột qua thời gian.
• Hiệu quả của các phương pháp chia tách sắp hàng phụ thuộc vào độ chính xác của các thuật toán căn chỉnh đa chuỗi ban đầu.
• Mô hình FLU được tối ưu hóa riêng cho prôtêin của vi rút cúm nên không phù hợp để áp dụng cho các loài sinh vật khác ngoài phạm vi họ vi rút này.

Về hướng nghiên cứu tiếp:

• Tích hợp thêm các ràng buộc cấu trúc không gian 3 chiều của phân tử prôtêin vào khung mô hình đa ma trận để mô tả chính xác hơn các vị trí tương tác chức năng.
• Song song hóa các thuật toán chia tách và suy luận ML trên các hệ thống điện toán phân tán hoặc đồ họa để xử lý các bộ dữ liệu quy mô lớn hơn nữa.
• Tiếp tục mở rộng việc ước lượng các mô hình đặc thù cho các nhóm vi rút biến đổi nhanh khác ngoài vi rút cúm.

Giá trị tham khảo

Luận án là tài liệu tham khảo có giá trị chuyên môn cho các đối tượng sau:

• Nghiên cứu sinh, học viên cao học và giảng viên chuyên ngành Tin sinh học, Khoa học Máy tính: Cung cấp tài liệu chi tiết về cơ chế toán học của mô hình Markov trong tiến hóa phân tử, kỹ thuật ước lượng cực đại khả năng (ML), thuật toán EM và giải pháp xử lý bài toán tối ưu NP-khó trong xây dựng cây phát sinh loài.
• Các nhà nghiên cứu dịch tễ học, vi rút học và sinh học phân tử: Cung cấp mô hình FLU đã được kiểm chuẩn thực nghiệm để nâng cao độ chính xác khi phân tích tiến hóa, đột biến của các chủng vi rút cúm trên gia cầm và người.
• Các kỹ sư phát triển phần mềm tin sinh học: Có thể tham khảo thuật toán chia tách dữ liệu dựa trên BIONJ tại Chương 2 và thuật toán giảm số lần lặp tại Chương 4 để tối ưu hóa hiệu năng tính toán cho các công cụ xây dựng cây phân loài như PhyML hay RAxML.

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

1. Tại sao bước xây dựng cây phân loài bằng phương pháp cực đại khả năng (ML) lại là nút thắt thời gian chính khi ước lượng mô hình Q?

Theo công thức toán học, số lượng cấu trúc cây phân loài dạng nhị phân không gốc tăng theo cấp giai thừa lẻ $(2m - 5)!!$ với $m$ là số chuỗi trong sắp hàng. Khi sắp hàng có từ vài chục đến hàng trăm chuỗi, không gian trạng thái cây bùng nổ hàng triệu đến hàng tỷ cấu trúc khả dĩ. Thực nghiệm trong Chương 2 chứng minh bước tìm cây ML chiếm tới 35/39 giờ trên dữ liệu Pfam và 273/283 giờ trên dữ liệu vi rút cúm, áp đảo hoàn toàn thời gian ước lượng tham số của thuật toán EM.

2. Mô hình ma trận tốc độ biến đổi tức thời Q có bao nhiêu tham số độc lập và được phân bổ ra sao?

Mô hình ma trận $Q$ có kích thước $20 \times 20$, biểu diễn qua ma trận đối xứng hệ số hoán đổi $R$ và véc tơ tần số $\Pi$. Do tổng các tần số bằng 1, véc tơ $\Pi$ có 19 tham số độc lập. Ma trận đối xứng $R$ sau khi chuẩn hóa có $19 \times 20 / 2 - 1 = 189$ tham số độc lập. Như vậy, tổng cộng mô hình $Q$ cần ước lượng chính xác 208 tham số.

3. Phương pháp chia tách dựa theo cấu trúc cây trong Chương 2 có ưu thế gì so với chia tách ngẫu nhiên?

Phương pháp chia tách ngẫu nhiên dễ đưa các chuỗi có quan hệ tiến hóa xa vào cùng một sắp hàng con nhỏ, dẫn đến sai số khi xây dựng cây phân loài và làm giảm độ chính xác của ma trận ước lượng. Ngược lại, phương pháp chia tách dựa theo cây sử dụng thuật toán BIONJ để gom cụm các chuỗi lân cận di truyền gần nhau vào cùng một nhóm con kích thước $[k, 2k]$, từ đó bảo toàn các mối quan hệ nhánh cục bộ và duy trì độ chính xác cao cho mô hình ma trận đầu ra.

4. Hiệu quả của mô hình FLU so với các mô hình hiện hành trên dữ liệu vi rút cúm được thể hiện bằng những số liệu thực nghiệm nào?

Khi kiểm tra trên 3.970 sắp hàng prôtêin vi rút cúm độc lập, mô hình FLU xếp thứ nhất (1st) trên 2.499 sắp hàng và xếp thứ nhì (2nd) trên 482 sắp hàng. FLU cũng đạt chỉ số AIC trung bình trên mỗi vị trí tốt nhất trong số 15 mô hình so sánh và tạo ra các cây phân loài có cấu trúc khác biệt rõ rệt (thể hiện qua khoảng cách Robinson-Foulds) so với cây của các mô hình chung như LG hay JTT.

5. Thuật toán cải tiến trong Chương 4 làm thế nào để giảm được 50% thời gian ước lượng mô hình?

Thuật toán cải tiến nhận diện được rằng hình thái cấu trúc (tô pô) của cây phân loài ổn định rất nhanh sau các vòng lặp đầu tiên. Do đó, thay vì giải lại bài toán NP-khó về tìm kiếm cấu trúc cây ở tất cả các vòng lặp, thuật toán cố định cấu trúc cây sau 3 lần lặp đầu và chỉ tiếp tục tối ưu hóa độ dài các nhánh của cây. Giải pháp này giúp cắt giảm một nửa tổng thời gian ước lượng lại các mô hình LG và FLU mà không làm sai lệch đáng kể giá trị log-likelihood của ma trận kết quả.

Kết luận

Luận án tiến sĩ của tác giả Đặng Thị Thu Hiền đã giải quyết trọn vẹn các bài toán trọng tâm trong việc ước lượng mô hình biến đổi axít amin bằng phương pháp cực đại khả năng. Bằng cách đề xuất các kỹ thuật chia tách sắp hàng thông minh và tối ưu hóa số vòng lặp dựng cây, công trình đã rút ngắn đáng kể thời gian tính toán của phương pháp ML, đồng thời nâng cao độ chính xác mô hình hóa qua khung tiếp cận đa ma trận. Mô hình FLU và hệ thống ước lượng tự động được xây dựng trong luận án mang lại công cụ tính toán thiết thực cho lĩnh vực tin sinh học và nghiên cứu tiến hóa vi rút cúm.

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.