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 - Đặng Cao Cường

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ ------------------------------------------ ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ ĐẶNG CAO CƯỜNG CÁC PHƯƠNG PHÁP XÂY DỰNG MA TRẬN BIẾN ĐẶNG ĐỔI AXÍT AMIN THỊ THU HIỀN LUẬN ÁN TIẾN SĨ CÔNG NGHỆ THÔNG TIN I TOÁN NỘI SUY VÀ MẠNG NƠRON RBF 1 Hà Nội – 2013 TIEU LUAN MOI download : skknchat@gmail.com ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ ------------------------------------------- ĐẶNG CAO CƯỜNG CÁC PHƯƠNG PHÁP XÂY DỰNG MA TRẬN BIẾN ĐỔI AXÍT AMIN Chuyên ngành: Khoa học Máy tính Mã số: 62.01 LUẬN ÁN TIẾN SĨ CÔNG NGHỆ THÔNG TIN NGƯỜI HƯỚNG DẪN KHOA HỌC: 1. Lê Sỹ Vinh 2. Lê Sĩ Quang 2 Hà Nội – 2013 TIEU LUAN MOI download : skknchat@gmail.com Lời cam đoan Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi. Các kết quả được viết chung với các tác giả khác đều được sự đồng ý của các đồng tác giả trước khi đưa vào luận án.

Các kết quả nêu trong luận án là trung thực và chưa từng được công bố trong các công trình khác. Tác giả 1 TIEU LUAN MOI download : skknchat@gmail.com Lời cảm ơn Luận án được thực hiện tại Trường Đại học Công nghệ, Đại học Quốc gia Hà Nội, dưới sự hướng dẫn của TS. Lê Sỹ Vinh và TS. Tôi xin bày tỏ lòng biết ơn sâu sắc tới TS.

Lê Sỹ Vinh, TS. Lê Sĩ Quang và giáo sư Oliver Gascuel, những người đã có những định hướng giúp tôi thành công trong việc nghiên cứu của mình. Các thầy cũng đã động viên và chỉ bảo giúp tôi vượt qua những khó khăn để tôi hoàn thành được luận án này. Tôi cũng chân thành cảm ơn thầy Hoàng Xuân Huấn, thầy đã cho tôi nhiều kiến thức quý báu về nghiên cứu khoa học và cuộc sống.

Những sự chỉ bảo quý giá của các thầy đã giúp tôi hoàn thành tốt luận án này. Tôi cũng xin cảm ơn tới các Thầy, Cô thuộc Khoa Công nghệ Thông tin, Trường Đại học Công nghệ, Đại học Quốc gia Hà Nội đã tạo mọi điều kiện thuận lợi giúp tôi trong quá trình làm nghiên cứu sinh. Cuối cùng, tôi xin gửi lời cảm ơn sâu sắc tới gia đình và bạn bè, những người đã cho tôi điểm tựa vững chắc để tôi có được thành công như ngày hôm nay. 2 TIEU LUAN MOI download : skknchat@gmail.com MỤC LỤC Lời cam đoan.

3 Danh mục các ký hiệu và chữ viết tắt. 7 Danh mục các bảng. 9 Danh mục các hình vẽ, đồ thị. 12 Danh mục các thuật toán.

BÀI TOÁN ƯỚC LƯỢNG SỰ BIẾN ĐỔI CỦA AXÍT AMIN. Giới thiệu chung. ADN và axít amin. Các phép biến đổi trên chuỗi axít amin.

Sắp hàng đa chuỗi axít amin. Cây phân loài. Mô hình hoá quá trình biến đổi axít amin. Sự khác biệt giữa hai chuỗi tương đồng.

Mô hình Markov cho quá trình biến đổi axít amin. Bài toán ước lượng mô hình biến đổi axít amin. Các phương pháp ước lượng mô hình biến đổi axít amin. Phương pháp đếm.

Phương pháp cực đại khả năng (maximum likelihood). 34 3 TIEU LUAN MOI download : skknchat@gmail. Xây dựng cây phân loài bằng phương pháp ML. Các phương pháp so sánh hai mô hình.

So sánh bằng việc xây dựng cây ML. So sánh cấu trúc cây. So sánh độ tương quan Pearson. Kết luận chương.

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. Ước lượng mô hình bằng phương pháp cực đại khả năng. Mô tả phương pháp. Phân tích phương pháp.

Các phương pháp chia tách dữ liệu. Phương pháp chia tách ngẫu nhiên. Phương pháp chia tách dựa theo cấu trúc cây. Nhận xét về các phương pháp chia tách sắp hàng.

Kết quả thực nghiệm. Dữ liệu kiểm tra. Kết quả với bộ dữ liệu vi rút cúm. Kết quả với bộ dữ liệu Pfam.

Kết luận chương. XÂY DỰNG MÔ HÌNH BIẾN ĐỔI ĐA MA TRẬN. Tính không đồng nhất của tốc độ biến đổi theo vị trí. 54 4 TIEU LUAN MOI download : skknchat@gmail.

Mô hình biến đổi đa ma trận. Thuật toán ước lượng mô hình đa ma trận. Kết quả thực nghiệm. Dữ liệu kiểm tra.

Tiêu chuẩn đánh giá AIC. So sánh kết quả của các mô hình. So sánh dung lượng bộ nhớ sử dụng và thời gian chạy. Kết luận chương.

HỆ THỐNG ƯỚC LƯỢNG MÔ HÌNH TỰ ĐỘNG. Phương pháp ước lượng nhanh. Kết quả thực nghiệm. Dữ liệu kiểm tra.

Kết quả với bộ dữ liệu Pfam. Kết quả với bộ dữ liệu FLU. Hệ thống ước lượng mô hình tự động. Kết luận chương.

MÔ HÌNH BIẾN ĐỔI AXÍT AMIN CHO VI RÚT CÚM. 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. Ước lượng mô hình FLU. Kết quả thực nghiệm.

Phân tích và đánh giá mô hình. 78 5 TIEU LUAN MOI download : skknchat@gmail. So sánh hiệu quả của FLU với các mô hình khác. Tính bền vững của mô hình.

Kết luận chương. 89 DANH MỤC CÁC CÔNG TRÌNH KHOA HỌC CỦA TÁC GIẢ LIÊN QUAN ĐẾN LUẬN ÁN. 91 TÀI LIỆU THAM KHẢO. 92 6 TIEU LUAN MOI download : skknchat@gmail.com Danh mục các ký hiệu và chữ viết tắt l Chiều dài của một sắp hàng m Số lượng chuỗi có trong một sắp hàng N Số lượng sắp hàng trong một tập các sắp hàng S Tậ hợ 20 axít amin qij Tốc độ biến đổi tức thời giữa axít amin i và axít amin j πi Tần số của axít amin i rij Hệ số hoán đổi giữa axít amin i và axít amin j α Tham số định hình của phân phối gamma A Tập các sắp hàng D Một sắ hàng đa chuỗi Da Sắ hàng đa chuỗi thứ a trong một tập các sắp hàng Di Vị trí thứ i trong sắ hàng đa chuỗi D Q Ma trận tốc độ biến đổi tức thời Π Véc tơ tần số của 20 axít amin R Ma trận hệ số hoán đổi T Cây hân loài tương ứng với sắp hàng D 7 TIEU LUAN MOI download : skknchat@gmail.com Qk Ma trận thứ k của một mô hình đa ma trận wk Trọng số của ma trận Qk ρk Tốc độ của ma trận Qk EM Thuật toán cực đại hoá kỳ vọng (expectation maximization) ML Phương há cực đại khả năng (maximum likelihood) STT Số thứ tự RF Khoảng cách Robinson-Fould 8 TIEU LUAN MOI download : skknchat@gmail.com Danh mục các bảng Bảng 1.1: Danh sách 64 codon.

Mỗi codon mã hoá một axít amin.2: Danh sách 20 axít amin.3: Danh sách độ đột biến tương đối của 20 axít amin. Độ đột biến của Ala (A) được đặt là 100. Asn (N) và Ser (S) là 2 axít amin có độ đột biến lớn nhất còn Trp (W) và Cys (C) là 2 axít amin có độ đột biến nhỏ nhất.1: Số lượng cây nhị phân không gốc tương ứng với số chuỗi axít amin m.2: Thời gian ước lượng mô hình của phương pháp chia tách ngẫu nhiên với bộ dữ liệu vi rút cúm. FLU Rk là mô hình ước lượng từ các sắp hàng được chia nhỏ bằng phương pháp chia tách ngẫu nhiên với ngưỡng k.3: Thời gian ước lượng mô hình của phương pháp chia tách dựa theo cấu trúc cây với bộ dữ liệu vi rút cúm.

FLUk là mô hình ước lượng từ các sắp hàng được chia nhỏ bằng phương pháp chia tách dựa theo cấu trúc cây với ngưỡng k.4: So sánh kết quả các mô hình của phương pháp chia tách ngẫu nhiên trên bộ dữ liệu vi rút cúm. M1: mô hình thứ nhất; M2: mô hình thứ hai; M1-M2: Khác biệt về giá trị trung bình log-likelihood trên một vị trí giữa hai mô hình M1 và M2; M1>M2: M1 tốt hơn M2; M1<M2: M2 tốt hơn M1; T1≠T2: cây ước lượng bởi M1 và M2 có cấu trúc khác nhau.5: So sánh kết quả các mô hình của phương pháp chia tách dựa theo cấu trúc cây trên bộ dữ liệu vi rút cúm. M1: mô hình thứ nhất; M2: mô hình thứ hai; M1-M2: Khác biệt về giá trị trung bình log-likelihood trên một vị trí giữa hai mô hình M1 và M2; M1>M2: M1 tốt hơn M2; M1<M2: M2 tốt hơn M1; T1≠T2: cây ước lượng bởi M1 và M2 có cấu trúc khác nhau.50 9 TIEU LUAN MOI download : skknchat@gmail.6: Thời gian ước lượng mô hình của phương pháp chia tách ngẫu nhiên với bộ dữ liệu Pfam. LGRk là mô hình ước lượng từ các sắp hàng được chia nhỏ bằng phương pháp chia tách ngẫu nhiên với ngưỡng k.7: Thời gian ước lượng mô hình của phương pháp chia tách tách dựa theo cấu trúc cây với bộ dữ liệu Pfam.

LGk là mô hình ước lượng từ các sắp hàng được chia nhỏ bằng phương pháp chia tách dựa theo cấu trúc cây với ngưỡng k.8: So sánh kết quả của phương pháp chia tách ngẫu nhiên với bộ dữ liệu Pfam. M1: mô hình thứ nhất; M2: mô hình thứ hai; M1-M2: Khác biệt về giá trị trung bình log-likelihood trên một vị trí giữa hai mô hình M1 và M2; M1>M2: M1 tốt hơn M2; M1<M2: M2 tốt hơn M1; T1≠T2: cây ước lượng bởi M1 và M2 có cấu trúc khác nhau.9: So sánh kết quả của phương pháp chia dựa theo cấu trúc cây với bộ dữ liệu Pfam. M1: mô hình thứ nhất; M2: mô hình thứ hai; M1-M2: Khác biệt về giá trị trung bình log-likelihood trên một vị trí giữa hai mô hình M1 và M2; M1>M2: M1 tốt hơn M2; M1<M2: M2 tốt hơn M1; T1≠T2: cây ước lượng bởi M1 và M2 có cấu trúc khác nhau.1: So sánh log-likelihood và cấu trúc cây giữa các mô hình trên 84 sắp hàng TreeBase.2: So sánh log-likelihood và cấu trúc cây giữa các mô hình trên 300 sắp hàng HSSP.3: Kết quả so sánh dung lượng bộ nhớ sử dụng (GB) và thời gian chạy (giờ) của các mô hình với bộ dữ liệu TreeBase.1: So sánh thời gian ước lượng lại mô hình LG với hai phương pháp. Quá trình ước lượng mô hình dừng sau 3 lần lặp.2: So sánh thời gian ước lượng lại mô hình FLU với hai phương pháp.

Quá trình ước lượng mô hình dừng sau 3 lần lặp.72 10 TIEU LUAN MOI download : skknchat@gmail.1: Danh sách các dịch cúm lớn xảy ra với con người.2: Độ tương quan Pearson giữa mô hình FLU và 14 mô hình phổ biến hiện có. Các giá trị tương quan thấp cho thấy mô hình FLU là rất khác biệt so với các mô hình hiện có.3: Độ lệch tương đối giữa các hệ số hoán đổi của FLU so với HIVb và LG. Giá trị ở hàng "Hai lần” và cột “FLU>LG” cho biết số hệ số hoán đổi trong FLU lớn hơn ít nhất hai lần hệ số tương ứng trong LG.