Đề tài Phương pháp đại số cho bài toán ước lượng hợp lý cực đại – Áp dụng trên cây sinh loài nhỏ

Đại Học Quốc Gia Thành Phố Hồ Chí Minh Trường Đại Học Bách Khoa BÙI VĂN ĐỒNG PHƯƠNG PHÁP ĐẠI SỐ CHO BÀI TOÁN ƯỚC LƯỢNG HỢP LÝ CỰC ĐẠI – ÁP DỤNG TRÊN CÂY SINH LOÀI NHỎ Chuyên ngành: Khoa học Máy tính LUẬN VĂN THẠC SĨ TP. HỒ CHÍ MINH, tháng 11 năm 2007 ĐẠI HỌC QUỐC GIA TP. HCM CỘNG HOÀ Xà HỘI CHỦ NGHIà VIỆT NAM TRƯỜNG ĐẠI HỌC BÁCH KHOA Độc Lập - Tự Do - Hạnh Phúc ---------------- ---oOo--- Tp. HCM, ngày . .05. . tháng . .11. . năm .2007. NHIỆM VỤ LUẬN VĂN THẠC SĨ Họ và tên học viên : Bùi Văn Đồng Giới tính : Nam ;/ Nữ … Ngày, tháng, năm sinh : 10/10/1969 Nơi sinh : Quảng Ngãi Chuyên ngành : Khoa học Máy tính Khoá : 2005 1- TÊN ĐỀ TÀI : PHƯƠNG PHÁP ĐẠI SỐ CHO BÀI TOÁN ƯỚC LƯỢNG HỢP LÝ CỰC ĐẠI – ÁP DỤNG TRÊN CÂY SINH LOÀI NHỎ 2- NHIỆM VỤ LUẬN VĂN : 3- NGÀY GIAO NHIỆM VỤ: 4- NGÀY HOÀN THÀNH NHIỆM VỤ: 5- HỌ VÀ TÊN CÁN BỘ HƯỚNG DẪN : TS. Nguyễn Văn Minh Mẫn Nội dung và đề cương Luận văn thạc sĩ đã được Hội Đồng Chuyên Ngành thông qua. CÁN BỘ HƯỚNG DẪN CHỦ NHIỆM BỘ MÔN (Họ tên và chữ ký) QUẢN LÝ CHUYÊN NGÀNH Họ tên và chữ ký) TS. Nguyễn Văn Minh Mẫn TS. Đinh Đức Anh Vũ CÔNG TRÌNH ĐƯỢC HOÀN THÀNH TẠI TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐẠI HỌC QUỐC GIA TP HỒ CHÍ MINH Cán bộ hướng dẫn khoa học : TS. Nguyễn Văn Minh Mẫn Cán bộ chấm nhận xét 1 : Cán bộ chấm nhận xét 2 : Luận văn thạc sĩ được bảo vệ tại HỘI ĐỒNG CHẤM BẢO VỆ LUẬN VĂN THẠC SĨ TRƯỜNG ĐẠI HỌC BÁCH KHOA, ngày . . . . tháng . . . . năm . 2007 . Phương pháp đại số cho bài toán ước lượng hợp lý cực đại - Áp dụng trên cây sinh loài nhỏ Bùi Văn Đồng Trang 1 LỜI CAM ĐOAN Tôi cam đoan rằng, ngoại trừ các kết quả tham khảo từ các công trình khác như đã ghi rõ trong luận văn, các công việc trình bày trong luận văn này là do chính tôi thực hiện và chưa có phần nội dung nào của luận văn này được nộp để lấy một bằng cấp ở trường này hoặc trường khác. Ngày 05 tháng 11 năm 2007 Bùi Văn Đồng Phương pháp đại số cho bài toán ước lượng hợp lý cực đại - Áp dụng trên cây sinh loài nhỏ Bùi Văn Đồng Trang 2 LỜI CẢM ƠN Xin gởi lời cảm ơn chân thành và sâu sắc đến TS. Nguyễn Văn Minh Mẫn, người Thầy đã tận tình hướng dẫn và tạo mọi điều kiện để tôi có thể hoàn thành luận văn này. Xin gởi lời cảm ơn đến các Thầy Cô đã dạy cho tôi trong thời gian qua. Tôi xin cảm ơn các bạn đồng môn và đồng nghiệp đã quan tâm, chia sẻ trong suốt quá trình học và làm luận văn. Luận văn này như một món quà nhỏ đáp lại tình cảm của gia đình và bạn bè thân thích. Phương pháp đại số cho bài toán ước lượng hợp lý cực đại - Áp dụng trên cây sinh loài nhỏ Bùi Văn Đồng Trang 3 TÓM TẮT LUẬN VĂN Cây sinh loài mô tả lịch sử tiến hóa của một nhóm các loài với những đặc tính khác nhau nhưng cùng có mối quan hệ họ hàng với nhau và cùng hình thành từ một tổ tiên chung trong quá khứ. Đặc tính của mỗi loài được chúng ta quan tâm ở đây tương ứng với các bộ gen. Gen là các chuỗi DNA được bao gồm từ các kí tự A, G, C và T hợp thành. Cây sinh loài là một cây mà các nút lá (taxa) của nó có thể là các vật sống hiện tại ngày nay, các nút trong của cây đó là các tổ tiên của các nút lá. Tái cấu trúc cây sinh loài chính là tìm những gen phù hợp nhất để đưa vào các nút tổ tiên hoặc là đưa ra một cây sinh loài phù hợp nhất để giải thích quá trình tiến hoá. Tuy nhiên, việc nghiên cứu cây sinh loài cho nhiều hướng tiếp cận. Mỗi phương pháp có những ưu điểm và khuyết điểm của nó. Phương pháp ước lượng hợp lý cực đại được chọn ở đây là phương pháp phức tạp nhất nhưng lại là phương pháp cho kết quả tin cậy nhất. Công cụ chính sử dụng trong phương pháp này là Đại số thống kê và Đại số máy tính. Đó là những lãnh vực phát triển mạnh mẽ trong những năm gần đây. Thống kê là ngành khoa học phân tích dữ liệu. Đối với các chuỗi DNA thì thống kê sẽ xây dựng những mô hình quá trình phát sinh dữ liệu. Đưa ra những kết luận chung về quá trình phát sinh đó. Mô hình thống kê là nguyên tắc cơ bản đối với các gen. Đại số thống kê làm sáng tỏ cho những ý tưởng trọng tâm về phân tích dữ liệu rời rạc nói riêng và phân tích chuỗi sinh học nói riêng. Ước lượng hợp lý cực đại (Maximum Likelihood Estimation – MLE) được công thức hoá trong Xác suất cổ điển, nó có tính chất của một ước lượng tốt. Phương pháp MLE đánh giá những tham số của một mô hình thối lui. MLE dẫn đến việc giải quyết là làm cực đại tích của những đa thức. Đại số máy tính là một lãnh vực mới, nó cung cấp những nền tảng để giải bài toán MLE trên máy tính. Đề tài này tập trung vào việc nghiên cứu mô hình xác suất thống kê trên cây sinh loài từ những dữ liệu là các gen của sinh vật sống. Sau đó sử dụng những nền tảng toán học, đại số máy tính để giải quyết bài toán hợp lý cực đại của mô hình xác suất trên. Mục tiêu cuối cùng là tìm một cây sinh loài thích hợp nhất để giải thích sự tiến hoá. Những kết quả của luận văn đã làm như sau: - Về phương pháp: Chọn phương pháp đáng tin cậy nhất là phương pháp ước lượng hợp lý cực đại cho mô hình hóa bài toán. Giải phương trình hợp lý bằng phương pháp tính toán đại số để tìm kết quả chính xác. - Về tính toán: Viết một chương trình để mô hình hóa ước lượng hợp lý cực đại trên cây sinh loài và chạy tìm nghiệm phương trình hợp lý trên một số cây sinh loài nhỏ 3 và 4 taxa ở một số mô hình. Phương pháp đại số cho bài toán ước lượng hợp lý cực đại - Áp dụng trên cây sinh loài nhỏ Bùi Văn Đồng Trang 4 DANH MỤC BẢNG Bảng 1: Bảng biến thiên của hàm hợp lý.......................................................................27 Bảng 2: Các mẫu và số lượng từng mẫu trên 3 chuỗi gen HIVenvSweden với cây hình móng (U68496, U68497, U68498).........................................................................55 Bảng 3: Các mẫu và số lượng từng mẫu trên 3 chuỗi gen HIVenvSweden với cây hình lược với trường hợp ((U68496,(U68497, U68498))...............................................55 Bảng 4: Các mẫu và số lượng từng mẫu trên 3 chuỗi gen HIVenvSweden với cây hình lược với trường hợp ((U68498,(U68496, U68497))...............................................56 Phương pháp đại số cho bài toán ước lượng hợp lý cực đại - Áp dụng trên cây sinh loài nhỏ Bùi Văn Đồng Trang 5 DANH MỤC HÌNH Hình 1: Hai trường hợp xảy ra khi tung đinh bấm ........................................................26 Hình 2: Đồ thị của hàm hợp lý ......................................................................................27 Hình 3: Cây sinh loài của sự sống .................................................................................30 Hình 4: Mô tả xác suất chuyển đổi trạng thái của chuỗi “DNA”..................................32 Hình 5: Cây sinh loài với các nút trong và xác suất chuyển đổi ...................................32 Hình 6: Một trong những cây sinh loài 4 taxa...............................................................35 Hình 7: Cây sinh loài với dữ liệu trên nút lá và các khả năng xảy ra ở các nút tổ tiên.36 Hình 8: Cây sinh loài có gốc với 3 nút lá ......................................................................42 Hình 9: Sơ đồ khối chương trình tìm cấu trúc cây sinh loài .........................................53 Hình 10: Hai hình dạng cây 3 taxa có gốc.....................................................................55 Hình 11: Cây sinh loài 4 taxa hình móng......................................................................68 Hình 12: Cây sinh loài 4 taxa hình cần trục ..................................................................68 Hình 13: Một số cây sinh loài 4 taxa.............................................................................68 Phương pháp đại số cho bài toán ước lượng hợp lý cực đại - Áp dụng trên cây sinh loài nhỏ Bùi Văn Đồng Trang 6 MỤC LỤC LỜI CAM ĐOAN ..........................................................................................................1 LỜI CẢM ƠN ................................................................................................................2 TÓM TẮT LUẬN VĂN ................................................................................................3 DANH MỤC BẢNG ......................................................................................................4 DANH MỤC HÌNH .......................................................................................................5 MỤC LỤC ......................................................................................................................6 Chương 1. GIỚI THIỆU ĐỀ TÀI ................................................................................9 1.1. Giới thiệu ..............................................................................................................9 1.2. Cấu trúc luận văn ..............................................................................................10 Chương 2. CƠ SỞ LÝ THUYẾT VỀ CÁC CẤU TRÚC ĐẠI SỐ VÀ XÁC SUẤT THỐNG KÊ ..............................................................................................12 2.1. Một số cấu trúc đại số cơ bàn ...........................................................................12 2.1.1. Lý thuyết nhóm.........................................................................................................12 2.1.2. Lý thuyết vành ..........................................................................................................13 2.1.3. Trường ......................................................................................................................14 2.1.4. Vành đa thức.............................................................................................................14 2.1.5. Ma trận......................................................................................................................15 2.1.6. Định thức ..................................................................................................................15 2.1.7. Không gian vector.....................................................................................................16 2.1.8. Đa tạp đại số .............................................................................................................18 2.2. Các khái niệm về xác suất thống kê .................................................................18 2.2.1. Định nghĩa về xác suất ..............................................................................................18 2.2.2. Xác suất có điều kiện ................................................................................................19 2.2.3. Đại lượng ngẫu nhiên và hàm phân phối ..................................................................20 2.2.4. Các đặc trưng của đại lượng ngẫu nhiên...................................................................20 2.2.5. Lý thuyết mẫu ...........................................................................................................21 2.2.6. Ước lượng tham số....................................................................................................22 2.2.7. Sơ lược về ước lượng hợp lý cực đại ........................................................................22 Chương 3. ƯỚC LƯỢNG HỢP LÝ CỰC ĐẠI TRÊN MẪU QUAN SÁT............25 3.1. Ước lượng hợp lý cực đại là gì? ........................................................................25 3.1.1. Đặt vấn đề .................................................................................................................25 3.1.2. Khái quát về ước lượng hợp lý cực đại.....................................................................25 3.1.3. Ví dụ về ước lượng hợp lý cực đại ...........................................................................26 3.2. Giải bài toán ước lượng hợp lý cực đại............................................................26 3.2.1. Nguyên lý ước lượng hợp lý cực đại ........................................................................26 3.2.2. Logarit hàm hợp lý....................................................................................................26 3.3. Tổng quát hóa bài toán ước lượng hợp lý cực đại ..........................................27 3.3.1. Ước lượng hợp lý cực đại trên mẫu quan sát ............................................................27 Phương pháp đại số cho bài toán ước lượng hợp lý cực đại - Áp dụng trên cây sinh loài nhỏ Bùi Văn Đồng Trang 7 3.3.2. Một số phương pháp giải phương trình hợp lý .........................................................28 Chương 4. CÂY SINH LOÀI - MÔ HÌNH XÁC SUẤT THỐNG KÊ TRÊN CÂY SINH LOÀI...............................................................................................30 4.1. Giới thiệu sơ lược về cây sinh loài ....................................................................30 4.2. Các nghiên cứu phát sinh sinh loài...................................................................31 4.3. Mô hình ước lượng hợp lý cực đại trên cây sinh loài .....................................32 4.4. Mô hình tiến hóa ................................................................................................33 Chương 5. BẤT BIẾN TRÊN CÂY SINH LOÀI .....................................................37 5.1. Dẫn nhập.............................................................................................................37 5.2. Mô hình xác suất trên cây sinh loài..................................................................38 5.2.1. Mô hình bài toán cây sinh loài..................................................................................38 5.2.2. Nhóm Abel và sự liên hệ với các ma trận chuyển đổi ..............................................39 5.3. Biến đổi Fourier .................................................................................................40 5.4. Toạ độ Fourier ...................................................................................................42 5.5. Áp dụng tìm bất biến trên một cây sinh loài ...................................................42 5.5.1. Mô hình bài toán .......................................................................................................42 5.5.2. Các khả năng xảy ra trên các nút lá ..........................................................................43 5.5.3. Các lớp xác suất tương đương ..................................................................................43 5.5.4. Chuyển đổi Fourier ...................................................................................................44 5.5.5. Kết quả tìm được ......................................................................................................45 5.6. Những tính chất của thành phần bất biến.......................................................46 Chương 6. GIẢI PHƯƠNG TRÌNH HỢP LÝ..........................................................47 6.1. Quỹ tích hợp lý trên một đa tạp .......................................................................47 6.2. Ma trận Jacobi của các đa thức bất biến.........................................................47 6.2.1. Gradient- Vector vận tốc...........................................................................................47 6.2.2. Ma trận Jacobi của các đa thức bất biến ...................................................................48 6.2.3. Không gian tiếp xúc..................................................................................................49 6.3. Bài toán cực trị điều kiện ..................................................................................49 6.4. Bậc của hợp lý cực đại .......................................................................................50 6.5. Các thuật toán ....................................................................................................50 6.6. Áp dụng giải phương trình hợp lý....................................................................51 Chương 7. CHƯƠNG TRÌNH THỰC HIỆN ...........................................................53 7.1. Sơ đồ khối chương trình....................................................................................53 7.2. Sơ lược về chương trình ....................................................................................54 7.3. Kết quả chương trình ........................................................................................54 Chương 8. TỔNG KẾT – ĐÁNH GIÁ ......................................................................57 8.1. Tổng kết ..............................................................................................................57 8.2. Những đóng góp của luận văn ..........................................................................57 8.3. Hướng phát triển ...............................................................................................58 TÀI LIỆU THAM KHẢO...........................................................................................59 Phương pháp đại số cho bài toán ước lượng hợp lý cực đại - Áp dụng trên cây sinh loài nhỏ Bùi Văn Đồng Trang 8 Phụ lục 1. Tập các xác suất trình bày ở chương 5....................................................60 Phụ lục 2. Tập các dữ liệu kết quả thực hiện trình bày ở chương 6.......................62 Phụ lục 3. Trích một số SourceCodes chương trình viết trên Singular .................64 Phụ lục 4. Một số kết quả chương trình trên cây sinh loài 4 taxa ..........................68 Phụ lục 5. Bảng đối chiếu Thuật ngữ Anh - Việt.....................................................69 Danh mục các tên.........................................................................................................70 Phương pháp đại số cho bài toán ước lượng hợp lý cực đại - Áp dụng trên cây sinh loài nhỏ Bùi Văn Đồng Trang 9 Chương 1. GIỚI THIỆU ĐỀ TÀI Chương này giới thiệu chung về bối cảnh, mục tiêu và kết quả thu được của đề tài. Cấu trúc nội dung của quyển thuyết minh được trình bày ở cuối chương. 1.1. Giới thiệu Phát sinh sinh loài đó là tái tạo lịch sử tiến hóa dựa trên các phương pháp toán học nhằm suy luận lịch sử tiến hóa sự sống trên hành tinh chúng ta. Việc tái cấu trúc này liên quan đến việc nhận diện chỉ định những đặc tính đồng dạng (homologous characters) được chia sẻ giữa các loài sinh vật khác nhau và suy luận cây phát sinh sinh loài từ việc so sánh các đặc tính thông qua việc sử dụng các phương pháp tái cấu trúc có độ tin cậy cao. Độ chính xác của quá trình suy luận vì thế phụ thuộc rất lớn vào độ tin cậy của các mô hình dùng để đánh giá sự tiến hóa của các đặc tính này. Trước đây việc tái tạo cây tiến hóa chủ yếu dựa trên phân tích hình thái và các đặc tính siêu cấu trúc. Trong nửa cuối thập niên 1980 nguồn dữ liệu trình tự DNA gia tăng cộng với sự phát triển ngành công nghệ thông tin, từ đó giúp nhà nghiên cứu có được những công cụ mạnh mẽ và nhằm giải quyết vài bài toán phát sinh sinh loài đang chưa có lời giải. Trong việc suy luận phát sinh sinh loài có 2 bước cơ bản đó là: - Chỉ định những đặc tính đồng dạng là những đặc tính chung truyền từ một tổ tiên chung cho đến các thế hệ hiện tại. - Tái cấu trúc cây tiến hóa bằng việc sử dụng các phương pháp thích hợp. Các dạng đặc tính có thể sử dụng là cấu trúc hình thái, siêu cấu trúc của tế bào, gene, trình tự DNA và protein miễn rằng chúng thỏa điều kiện là Đồng dạng. Có 3 nhóm phương pháp thường được dùng để tái cấu trúc cây phát sinh sinh loài từ một ma trận đặc tính: - Nhóm các phương pháp khoảng cách (Distance methods): Khoảng cách chính là khoảng cách tiến hóa giữa các cặp đối tượng đang được so sánh. - Nhóm phương pháp hà tiện đến mức tối đa (Maximum parsimony - MP): phương pháp này sẽ chọn lựa cây tiến hóa thỏa điều kiện là số lượng đặc tính bị biến đổi phải thấp nhất để giải thích những dữ liệ