Luận văn 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ỏ

76 trang phuongnguyen 2480

Download

Bạn đang xem 20 trang mẫu của tài liệu "Luận văn 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ỏ", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

luan_van_phuong_phap_dai_so_cho_bai_toan_uoc_luong_hop_ly_cu.pdf

Nội dung text: Luận văn 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 TỐN ƯỚC LƯỢNG HỢP LÝ CỰC ĐẠI – ÁP DỤNG TRÊN CÂY SINH LỒ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 HỒ 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 Khố : 2005 1- TÊN ĐỀ TÀI : PHƯƠNG PHÁP ĐẠI SỐ CHO BÀI TỐN ƯỚC LƯỢNG HỢP LÝ CỰC ĐẠI – ÁP DỤNG TRÊN CÂY SINH LỒI NHỎ 2- NHIỆM VỤ LUẬN VĂN : 3- NGÀY GIAO NHIỆM VỤ: 4- NGÀY HỒ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 HỒ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 tốn ước lượng hợp lý cực đại - Áp dụng trên cây sinh lồi nhỏ 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 Bùi Văn Đồng Trang 1
Phương pháp đại số cho bài tốn ước lượng hợp lý cực đại - Áp dụng trên cây sinh lồi nhỏ 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ể hồ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. Bùi Văn Đồng Trang 2
Phương pháp đại số cho bài tốn ước lượng hợp lý cực đại - Áp dụng trên cây sinh lồi nhỏ TĨM TẮT LUẬN VĂN Cây sinh lồi mơ tả lịch sử tiến hĩa của một nhĩm các lồ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 lồ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 lồ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 lồ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 lồi phù hợp nhất để giải thích quá trình tiến hố. Tuy nhiên, việc nghiên cứu cây sinh lồ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 hố 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 tố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 lồ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 tốn học, đại số máy tính để giải quyết bài tố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 lồi thích hợp nhất để giải thích sự tiến hố. 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 tốn. Giải phương trình hợp lý bằng phương pháp tính tốn đại số để tìm kết quả chính xác. - Về tính tố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 lồi và chạy tìm nghiệm phương trình hợp lý trên một số cây sinh lồi nhỏ 3 và 4 taxa ở một số mơ hình. Bùi Văn Đồng Trang 3
Phương pháp đại số cho bài tốn ước lượng hợp lý cực đại - Áp dụng trên cây sinh lồi nhỏ 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 Bùi Văn Đồng Trang 4
Phương pháp đại số cho bài tốn ước lượng hợp lý cực đại - Áp dụng trên cây sinh lồi nhỏ 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 lồ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 lồ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 lồi 4 taxa 35 Hình 7: Cây sinh lồ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 lồ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 lồi 53 Hình 10: Hai hình dạng cây 3 taxa cĩ gốc 55 Hình 11: Cây sinh lồi 4 taxa hình mĩng 68 Hình 12: Cây sinh lồi 4 taxa hình cần trục 68 Hình 13: Một số cây sinh lồi 4 taxa 68 Bùi Văn Đồng Trang 5
Phương pháp đại số cho bài tốn ước lượng hợp lý cực đại - Áp dụng trên cây sinh lồi nhỏ 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 tố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 tố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 Bùi Văn Đồng Trang 6
Phương pháp đại số cho bài tốn ước lượng hợp lý cực đại - Áp dụng trên cây sinh lồi nhỏ 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 LỒI - MƠ HÌNH XÁC SUẤT THỐNG KÊ TRÊN CÂY SINH LỒI 30 4.1. Giới thiệu sơ lược về cây sinh lồi 30 4.2. Các nghiên cứu phát sinh sinh lồi 31 4.3. Mơ hình ước lượng hợp lý cực đại trên cây sinh lồi 32 4.4. Mơ hình tiến hĩa 33 Chương 5. BẤT BIẾN TRÊN CÂY SINH LỒI 37 5.1. Dẫn nhập 37 5.2. Mơ hình xác suất trên cây sinh lồi 38 5.2.1. Mơ hình bài tốn cây sinh lồ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 lồi 42 5.5.1. Mơ hình bài tố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 tố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 tố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 Bùi Văn Đồng Trang 7
Phương pháp đại số cho bài tốn ước lượng hợp lý cực đại - Áp dụng trên cây sinh lồi nhỏ 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 lồ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 Bùi Văn Đồng Trang 8
Phương pháp đại số cho bài tốn ước lượng hợp lý cực đại - Áp dụng trên cây sinh lồi nhỏ 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 lồi đĩ là tái tạo lịch sử tiến hĩa dựa trên các phương pháp tố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 lồi sinh vật khác nhau và suy luận cây phát sinh sinh lồ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 tốn phát sinh sinh lồi đang chưa cĩ lời giải. Trong việc suy luận phát sinh sinh lồ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 lồ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ệu đã quan sát được. - Nhĩm phương pháp hợp lý cực đại (Maximum Likelihood methods): nhĩm phương pháp này dựa trên một hàm tốn học tính tốn xác suất khả năng một cây tiến hĩa được tạo thành từ dữ liệu đã quan sát. Hàm này cho phép việc tích hợp các quá trình tiến hĩa của đặc tính thành mơ hình xác suất. Phương pháp hợp lý cực đại chọn lựa cây tiến hĩa tối đa mà khi quan sát các dữ liệu dưới một mơ hình nào đĩ cĩ xác xuất tối đa. Trong các phương pháp giới thiệu ở trên thì phương pháp hợp lý cực đại là phương pháp là phức tạp nhất và cho kết quả đáng tin cậy nhất. Vì những lý do trên, Bùi Văn Đồng Trang 9
Phương pháp đại số cho bài tốn ước lượng hợp lý cực đại - Áp dụng trên cây sinh lồi nhỏ trong dự án nghiên cứu này chúng tơi hướng vào kỹ thuật đại số tính tốn cho vấn đề ước lượng khả năng cực đại và áp dụng để tái cấu trúc cây sinh lồi. Xuất phát từ những thực tế trên, đề tài này đặt ra một số mục tiêu sau: ¾ Tìm hiểu mơ hình xác suất thống kê trên cây sinh lồi. Tìm hiểu phương pháp hợp lý cực đại và áp dụng trên cây sinh lồi. ¾ Tìm những phương pháp tốn học thích hợp để giải bài tốn ước lượng hợp lý cực đại. ¾ Giải quyết cho trường hợp cây sinh lồi 3 và 4 taxa. ¾ Tìm kiếm kết quả tương tự cho trường hợp 5 taxa. ¾ Hồn thành một chương trình để kiểm nghiệm. Sau đây là một số kết quả thu được của đề tài: ¾ Xây dựng được mơ hình xác suất thống kê tổng quát trên cây sinh lồi. ¾ Chỉ ra sự tương đồng của mơ hình bài tốn với một số cấu trúc đại số cơ bản, từ đĩ tìm được thành phần bất biến trên cây sinh lồi và giải bài tốn. ¾ Xây dựng được một chương trình kiểm nghiệm. ¾ Chương trình đã giải quyết được bài tốn MLE để tái cấu trúc cây sinh lồi trên một số cây sinh lồi nhỏ 3 taxa và trường hợp đặc biệt với cây 4 và 5 taxa. 1.2. Cấu trúc luận văn Nội dung luận văn được trình bày trong các chương sau: 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. CHƯƠNG 2: CÁC CẤU TRÚC ĐẠI SỐ CƠ BẢN - CƠ SỞ LÝ THUYẾT VỀ XÁC SUẤT THỐNG KÊ Chương này giới thiệu các khái niệm cơ bản của tốn học đại số và xác suất thống kê được sử dụng vào các chương sau của đề tài. Các khái niệm về các cấu trúc đại số như: nhĩm, vành, trường, vành đa thức, ma trận, vectơ, . Các khái niệm về xác suất thống kê như: xác suất, đại lượng ngẫu nhiên và hàm phân phối, các đặc trưng của các đại lượng ngẫu nhiên, lý thuyết mẫu, và ước lượng hợp lý cực đại. CHƯƠNG 3: ƯỚC LƯỢNG HỢP LÝ CỰC ĐẠI Chương này chúng ta tìm hiểu kỹ hơn về MLE trên mơ hình thống kê. Dẫn ra một vài ví dụ về ước lượng hợp lý cực đại trên một số mẫu dữ liệu quan sát và giải bài tốn. CHƯƠNG 4: CÂY SINH LỒI – MƠ HÌNH XÁC SUẤT THỐNG KÊ TRÊN CÂY SINH LỒI Chương này giới thiệu cây sinh lồi, mơ hình xác suất thống kê trên cây sinh lồi. Ngồi ra cũng giới thiệu một số mơ hình thường sử dụng hiện nay trên cây sinh lồi như mơ hình Neyman 2 trạng thái, Jukes – Cantor, Kimura với 2 và 3 tham số. Bùi Văn Đồng Trang 10
Phương pháp đại số cho bài tốn ước lượng hợp lý cực đại - Áp dụng trên cây sinh lồi nhỏ CHƯƠNG 5: BẤT BIẾN TRÊN CÂY SINH LỒI Trong chương này, giới thiệu tổng quát hĩa mơ hình xác suất thống kê trên sinh lồi. Chỉ ra cấu trúc nhĩm Aben đối với các mơ hình sử dụng để từ đĩ tìm thành phần bất biến trên cây sinh lồi. CHƯƠNG 6: GIẢI PHƯƠNG TRÌNH HỢP LÝ Chương này đưa ra phương pháp giải phương trình hợp lý dựa vào tính bất biến của cây sinh lồi và mẫu dữ liệu quan sát. CHƯƠNG 7: CHƯƠNG TRÌNH THỰC HIỆN Chương này trình bày chi tiết hiện thực của chương trình. CHƯƠNG 8: TỔNG KẾT – ĐÁNH GIÁ Chương này tổng kết lại những cơng việc đã làm được, sau đĩ nêu ra những đĩng gĩp và hướng phát triển của luận văn. Bùi Văn Đồng Trang 11
Phương pháp đại số cho bài tốn ước lượng hợp lý cực đại - Áp dụng trên cây sinh lồi nhỏ 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Ê Các khái niệm cơ bản của đại số được trình bày ở phần đầu của chương này. Tiếp theo đĩ là phần giới thiệu về những khái niệm về xác suất thống kê trong đĩ cĩ phần khái quát về ước lượng hợp lý cực đại. 2.1. Một số cấu trúc đại số cơ bàn 2.1.1. Lý thuyết nhĩm Định nghĩa 1: Một nhĩm là một cặp (,)G trong đĩ G là một tập hợp khơng rỗng và là một luật hợp thành trên G thỏa mãn 3 điều kiện sau: (i) Luật hợp thành là kết hợp, tức là: ()x yzxyz= () với mọi x,,yz∈ G. (ii) Cĩ một phần tử e∈G, được gọi là phần tử trung lập, cĩ tính chất x eexx= = với mọi x∈G . Phần tử e cịn được gọi là phần tử đơn vị của G . (iii) Với mọi x∈G , cĩ một phần tử x, ∈G , được gọi là nghịch đảo của x sao cho x xxx,,= = e Nếu luật hợp thành đã rõ và khơng nhầm lẫn gì, người ta cũng nĩi G là một nhĩm. Định nghĩa 2: Nhĩm (,G )được gọi là giao hốn (hay Abel) nếu: x yyx= với mọi x, yG∈ . Định nghĩa 3: Giả sử G và G' là các nhĩm (với luật hợp thành viết theo lối nhân). Một ánh xạ ϕ :GG→ ' được gọi là một đồng cấu nhĩm nếu: ϕ()xyx= ϕϕ ()(y) với mọi x, yG∈ . Định nghĩa 4: Một đồng cấu nhĩm đồng thời là một song ánh được gọi là một đẳng cấu nhĩm. Định nghĩa 5: Hạt nhân và ảnh của đồng cấu nhĩm ϕ :GG→ ' được định nghĩa như sau: Bùi Văn Đồng Trang 12
Phương pháp đại số cho bài tốn ước lượng hợp lý cực đại - Áp dụng trên cây sinh lồi nhỏ Kerϕϕϕ:{=∈ x G : () x = e,1 } =− () e, Imϕ := {ϕϕ (x ) :xG∈= } ( G ) trong đĩ e, là đơn vị trong G' . Định nghĩa 6: Giả sử G là một nhĩm. Một tập con khơng rỗng SG⊂ được gọi là một nhĩm con của G nếu S khép kín đối với luật hợp thành trong G (tức là xyS∈ với mọi x, yS∈ ) và khép kín đối với phép lấy nghịch đảo trong G (tức là x−1 ∈ S với mọi x∈ S ). 2.1.2. Lý thuyết vành Định nghĩa 7: Ta gọi là vành mỗi tập hợp R ≠ ∅ cùng với hai phép tốn hai ngơi, gồm phép cộng + : R ×→RR (,x yx ) + y và phép nhân •: R ×→RR (,x yx ) y thỏa mãn ba điều kiện sau đây: (i) R là một nhĩm Abel đối với phép cộng. (ii) Phép nhân cĩ tính kết hợp. (iii) Phép nhân phân phối về hai phía đối với phép cộng: (x + y)z = xz + yz, z(x + y) = zx + zy với mọi x,,yz∈ R. Khi hai phép tốn đều đã rõ, ta sẽ nĩi đơn giản: R là một vành. Định nghĩa 8: Vành R được gọi là vành giao hốn nếu phép nhân của nĩ giao hốn. Định nghĩa 9: Giả sử R là một vành. Tập con S⊂ R được gọi là một vành con của R nếu S là một nhĩm con của nhĩm cộng R và khép kín đối với phép nhân, tức là x, yR∈ kéo theo xyS∈ . Định nghĩa 10: (i) Một iđêan trái của vành R là một vành con A ⊂ R cĩ tính hấp thụ đối với phép nhân từ bên trái, tức là ra∈ A,,∀∈ r R ∀∈ a A (ii) Một iđêan phải của vành R là một vành con A ⊂ R cĩ tính hấp thụ đối với phép nhân từ bên phải, tức là ar∈ A,,∀∈ r R ∀∈ a A (iii) Nếu vành con A ⊂ R vừa là một iđêan trái, vừa là một iđêan phải thì nĩ được gọi là một iđêan (hai phía) của R. Bùi Văn Đồng Trang 13
Phương pháp đại số cho bài tốn ước lượng hợp lý cực đại - Áp dụng trên cây sinh lồi nhỏ Định lí : Giả sử A là một iđêan của vành R, thì: (i) Lớp xy + A chỉ phụ thuộc vào các lớp x + A và y + A mà khơng phụ thuộc vào sự lựa chọn của các phần tử x, y từ các lớp đĩ. (ii) X/A cùng với 2 phép tốn (,x + AyA++ ) xyA+ (,x ++Ay A ) xy + A là một vành gọi là vành thương của R trên A. Định nghĩa 11: Giả sử R là một vành (giao hốn và cĩ đơn vị). Iđêan A của R được gọi là nguyên tố nếu A ≠ R và với mọi x, yR∈ , từ chỗ xyA∈ suy ra hoặc x∈ A hoặc yA∈ . 2.1.3. Trường Định nghĩa 12: (i) Vành cĩ đơn vị R được gọi là một thể nếu 1≠ 0và mọi phần tử khác 0 trong R đều khả nghịch, nĩi cách khác, nếu R \{0} là một nhĩm đối với phép nhân. (ii) Mỗi thể giao hốn được gọi là một trường. Chúng ta đã biết một số trường số quen thuộc như: QRC,, . 2.1.4. Vành đa thức Định nghĩa 13: Vành P được gọi là vành đa thức của ẩn x lấy hệ tử trong A, hay vắn tắt vành đa thức của ẩn x trên A, và kí hiệu là A[x]. Các phần tử của vành đĩ gọi là đa thức của ẩn x lấy hệ tử trong A. Trong một đa thức 01 n f ()xaxax=+++01 axn i các aii , = 0, 1, , n gọi là các hệ tử của đa thức. Các axi được gọi là các hạng tử của đa thức. Đa thức cĩ tất cả hệ tử bằng 0 gọi là đa thức 0. Định nghĩa 14: Giả sử A là một vành giao hốn cĩ đơn vị. Ta đặt AAx11= [] Annn= Ax−1[] vành Annn= Ax−1[] kí hiệu là A[,xx12 , ,] xn và gọi là vành đa thức của n ẩn x12,xx , , n lấy hệ tử trong vành A. Một phần tử của An gọi là một đa thức của n ẩn x12,xx , , n lấy hệ tử trong vành A, người ta kí hiệu bằng f (,xx12 , ,) xn hay gx(12 , x , , xn ) Định nghĩa 15: Giả sử f (,xx12 , ,) xn∈ Axx [,12 , ,] xn là một đa thức khác 0 aa11 1n am1 a mn f (xx12 , , , xnnm )=++ cx 11 x cx1 xn Bùi Văn Đồng Trang 14
Phương pháp đại số cho bài tốn ước lượng hợp lý cực đại - Áp dụng trên cây sinh lồi nhỏ với các cii ≠=0, 1, ,m và (aai1 , , in )≠ ( aaj1 , ,jn ) khi i≠ j. Ta gọi bậc của aai1 in hạng tử cxi1 xnlà tổng các số mũ đối với ẩn xi số mũ ai1+ + a in của các ẩn. Bậc của đa thức (đối với tồn thể các ẩn) là số lớn nhất trong các bậc của các hạng tử của nĩ. Đa thức 0 là đa thức khơng cĩ bậc. Nếu các hạng tử của f (,xx12 , ,) xn cĩ cùng bậc k thì f (,xx12 , ,) xn gọi là một đa thức thuần nhất cấp bậc k hay một dạng bậc k. Đặc biệt một dạng bậc nhất gọi là dạng tuyến tính, một dạng bậc 2 gọi là dạng tồn phương, một dạng bậc 3 gọi là dạng lập phương. 2.1.5. Ma trận Một ma trận A là một bảng cĩ mn× phần tử lấy ở vành R, viết như sau: ⎡ aa11 12 a1n ⎤ ⎢aa a⎥ A = ⎢ 21 22 2n ⎥ ⎢ ⎥ ⎢ ⎥ ⎣aamm12 a mn⎦ Các số aij được viết thành m dịng và n cột, chúng mang hai chỉ số: chỉ số i nĩi lên dịng và j nĩi lên cột mà aij được đặt trong bảng. Mỗi aij được gọi là một thành phần của ma trận. Một ma trận kiểu (m, n) là một ma trận cĩ m dịng và n cột. Khi m = n thì ta bảo ta cĩ một ma trận vuơng cấp n. Ma trận chuyển vị của ma trận A được kí hiệu là AT được định nghĩa như sau: ⎡aa11 21 am1 ⎤ ⎢aa a⎥ AT = ⎢ 12 22 m2 ⎥ ⎢ ⎥ ⎢ ⎥ ⎣aanm12 a nm⎦ hay ma trận AT là ma trận A nhưng chuyển dịng thành cột và cột thành dịng. 2.1.6. Định thức Giả sử A là một ma trận vuơng cấp nn(1≥ ) ⎡aa11 12 a1n ⎤ ⎢aa a⎥ A = ⎢ 21 22 2n ⎥ ⎢ ⎥ ⎢ ⎥ ⎣aann12 a nn⎦ Định thức của ma trận A là gọi là det(A) hay |A| được định nghĩa như sau theo cách triển khai theo dịng i: Bùi Văn Đồng Trang 15
Phương pháp đại số cho bài tốn ước lượng hợp lý cực đại - Áp dụng trên cây sinh lồi nhỏ det(A ) = aAi1 i1+++ aA i2 i2 aA in in ij+ trong đĩ Aij =−(1) M ij với Mij là định thức cấp n -1 suy ra từ A bằng cách bỏ dịng thứ i và cột thứ j. Aij được gọi là phần bù đại số của aij ta đi đến tính n định thức cấp n-1. Ma trận cĩ một phần tử thì định thức bằng chính phần tử đĩ. 2.1.7. Khơng gian vector K là một trường, chủ yếu là QRC,, , mà các phần tử kí hiệu là: λ, μν , , , E là một tập hợp mà các phần tử là x,,, yz . Giả sử cho 2 phép tốn: - Phép cộng: E × EE→ (,x yx ) + y và - Phép nhân: Một phần tử của K với một phần tử E: K × EE→ (,)λ x λx thỏa mãn các tính chất sau với mọi x, yE∈ và mọi λ, μ ∈ K : (i) E cùng với phép cộng là một nhĩm Abel. (ii) Phép nhân phân phối đối với phép cộng của trường K: ()λ + μλμx =+xx (iii) Phép nhân phân phối đối với phép cộng của E: λ()x + yx=+λλy (iv) Phép nhân cĩ tính kết hợp: λ()()μλμx = x (v) 1x = x , 1 là đơn vị của trường K. Lúc đĩ ta bảo E cùng với hai phép tốn: Cộng trong E và nhân đối với một phần tử trong trường K, thỏa tính chất (i), (ii), (iii), (iv) và (v) là một khơng gian vector trên trường K hay K – khơng gian vector (cũng gọi tắt là khơng gian vector khi khơng cần chỉ rõ K). Các phần tử của E gọi là các vector; các phần tử của K gọi là vơ hướng. Phép tốn + gọi là phép cộng vector, phép tốn nhân với một phần tử của trường K được gọi là phép nhân vector với vơ hướng. Độc lập tuyến tính và phụ thuộc tuyến tính Giả sử xx12, , , xn ( n≥ 1) là n vectơ của K – khơng gian vector E và λ12, λ , , λn là n phần tử của trường K. Vectơ x = λ11xx+++λλ 2 2 nnx Bùi Văn Đồng Trang 16
Phương pháp đại số cho bài tốn ước lượng hợp lý cực đại - Áp dụng trên cây sinh lồi nhỏ n cịn được viết là: x =∈∑λiixE và gọi là tổ hợp tuyến tính của các vectơ i=1 x12, x , , xn với các hệ tử λ12,λ , , λn . Trong trường hợp K là một trường số, các λi sẽ gọi là hệ số thay cho hệ tử. Hệ n vectơ xx12, , , xn ( n≥ 1) trong K khơng gian vectơ E gọi là độc lập tuyến tính khi vectơ 0 chỉ cĩ một biểu thị tuyến tính, đĩ là biểu thị tuyến tính tầm thường, qua hệ vectơ đĩ. Vậy hệ xx12, , , xn ( n≥ 1) độc lập tuyến tính khi và chỉ khi n ∑λiix = 0 kéo theo λ12= λλ== n = 0 i=1 Hệ vectơ xx12, , , xn ( n≥ 1) khơng độc lập tuyến tính thì gọi là phụ thuộc tuyến tính. Hạng của một hệ hữu hạn vectơ Giả sử I là một tập hữu hạn và ∅ ≠⊂JI. Giả sử cho hệ vectơ ()xiiI∈ trong K- khơng gian vector E. Hệ con ()x j jJ∈ gọi là một hệ con độc lập tuyến tính tối đại của hệ đã cho nếu nĩ là một hệ độc lập tuyến tính và nếu thêm bất cứ vector xi ()iIJ∈ − nào vào hệ con đĩ thì ta đều được một hệ phụ thuộc tuyến tính. Cho hệ hữu hạn vector ()xiiI∈ trong K- khơng gian vector E. Người ta chứng minh được rằng số phần tử của mọi hệ con độc lập tuyến tính tối đại của nĩ bằng nhau và gọi là hạng của hệ vector đã cho. Hạng của vectơ (0) được coi bằng 0. Hạng của ma trận Ma trận A cĩ m dịng và n cột với aKij ∈ . Hạng của A là hạng của hệ vector cột và người ta chứng minh nĩ cũng bằng hạng của vectơ dịng và bằng cấp cao nhất của các định thức con khác 0 của nĩ. Nếu A chứa một ma trận vuơng cấp p cĩ định thức khác 0, sao cho mọi ma trận vuơng cấp p+1 chứa nĩ cĩ định thức bằng 0, thì ma trận cĩ hạng là p. Cơ sở và số chiều của một K – khơng gian vector Ở đây chúng ta chỉ đề cập tới các khơng gian vector cĩ hữu hạn chiều. Giả sử E là một K – khơng gian vector. Giả sử tồn tại trong E một hệ vector độc lập tuyến tính (,ee12 , ,) en sao cho mọi vector của E đều biểu thị tuyến tính qua hệ đĩ. Lúc đĩ ta cĩ thể nĩi hệ (,ee12 , ,) en là độc lập tuyến tính tối đại trong E. Và ta nĩi (,ee12 , ,) en là một cơ sở của K – khơng gian vector E và số chiều (hay vắn tắt là chiều) của E, kí hiệu là dim E, là số vectơ của cơ sở. Ta viết dim E = n; và gọi E là K - khơng gian vector n chiều. Bùi Văn Đồng Trang 17
Phương pháp đại số cho bài tốn ước lượng hợp lý cực đại - Áp dụng trên cây sinh lồi nhỏ 2.1.8. Đa tạp đại số Tập hợp tất cả các điểm (,zz12 , ,) zn trong khơng gian phức n chiều thỏa mãn hệ phương trình dạng Fzin(12 , z , , z )= 0 ( i= 1,2, , s ) trong đĩ Fi là các đa thức của các biến số zjj ( =1, , n ) Nếu các Fi đều là bậc nhất đối với tất cả các z j thì ta cĩ đa tạp tuyến tính. Nếu các hệ số của Fi là số hữu tỉ (thực, phức) thì ta cĩ đa tạp đại số hữu tỉ (thực, phức). 2.2. Các khái niệm về xác suất thống kê 2.2.1. Định nghĩa về xác suất 1) Một số khái niệm Trong xác suất thống kê, thực hiện một phép thử nghĩa là làm một thí nghiệm, thực hiện một quan sát, thực hiện một cơng việc, một hành động nào đĩ. - Phép thử mà ta khơng khẳng định được một cách chắc chắn kết quả của nĩ trước khi thực hiện phép thử gọi là phép thử ngẫu nhiên. - Các phép thử cĩ thể xảy ra của phép thử gọi là các biến cố. - Các biến cố khơng thể phân tích được nữa gọi là biến cố sơ cấp. - Biến cố chắc chắn là biến cố nhất định xảy ra khi phép thử được thực hiện. Ta kí hiệu biến cố chắc chắn là Ω . - Biến cố khơng thể là biến cố khơng thể xảy ra khi phép thử được thực hiện. Ta kí hiệu là Φ . - Biến cố ngẫu nhiên là biến cố mà nĩ cĩ thể xảy ra và cũng cĩ thể khơng xảy ra khi phép thử được thực hiện. ta thường kí hiệu biến cố ngẫu nhiên bởi các chữ cái in hoa: A, B, C, 2) Quan hệ giữa các biến cố - Tổng của 2 biến cố: Tổng của 2 biến cố A và B là một biến cố được kí hiệu là A ∪ B , sao cho biến cố tổng A ∪ B xảy ra khi và chỉ khi hoặc A xảy ra hoặc B xảy ra. - Tích của 2 biến cố: Tích của 2 biến cố A và B là một biến cố được kí hiệu là A ∩ B hoặc AB, sao cho biến cố tích AB xảy ra khi và chỉ khi A xảy ra và B xảy ra. Định nghĩa xác suất dạng cổ điển Xác suất của biến cố A là một số khơng âm, kí hiệu P(A). Biểu thị khả năng xảy ra biến cố A và nĩ được xác định như sau: Số trường hợp thuận lợi cho A PA()= Số trường hợp có thể xảy ra phép thử được thực hiện Định nghĩa xác suất dạng thống kê Làm đi làm lại một phép thử nào đĩ n lần, thấy cĩ m lần biến cố A xuất hiện thì m tỷ số gọi là tần suất của biến cố A. n Bùi Văn Đồng Trang 18
Phương pháp đại số cho bài tốn ước lượng hợp lý cực đại - Áp dụng trên cây sinh lồi nhỏ m Khi n thay đổi, tần suất cũng thay đổi nhưng nĩ luơn dao động quanh một số n m cố định nào đĩ, n càng lớn thì càng gần số cố định đĩ. Số cố định ấy được gọi là n xác suất của biến cố A theo nghĩa thống kê. Trên thực tế khi n đủ lớn ta xấp xỉ P(A) m bởi . n m PA()≈ n Một số tính chất của xác suất 0()1≤ PA≤ PP()Φ =Ω= 0,()1 2.2.2. Xác suất cĩ điều kiện 1) Định nghĩa: Xác suất cĩ điều kiện của biến cố A với điều kiện biến cố B đã xảy ra là một con số khơng âm, được kí hiệu p(/)AB, nĩ biểu thị khả năng xảy ra biến cố A trong tình huống biến cố B đã xảy ra. 2) Tính độc lập của các biến cố Hai biến cố A và B gọi là độc lập với nhau nếu: p(/)AB= PA () hoặc p(/)BA= PB () hoặc p(AB )= P ()() A P B 3) Cơng thức nhân xác suất: Từ định nghĩa xác suất cĩ điều kiện, với n biến cố A12,AA , , n ta cĩ: PAA(12 Ann )= PA (1 ) PA ( 2 / A 1 ) PA ( 3 / AA 12 ) PA ( / AA12 An− 1 ) 4) Cơng thức xác suất đầy đủ và cơng thức Bayes Giả sử BB12,,, Bn là một nhĩm đầy đủ các biến cố. Xét biến cố A sao cho A xảy ra chỉ khi một trong các biến cố BB12,,, Bn xảy ra. Khi đĩ n PA()= ∑ PB (ii )(/ PAB ) i=1 Cơng thức trên được gọi là cơng thức xác suất đầy đủ. Và PB()(/)kk PA B PB(/)k A==n k1,2, , n ∑ PB()(/)ii PA B i=1 Cơng thức này được gọi là cơng thức Bayes. Bùi Văn Đồng Trang 19
Phương pháp đại số cho bài tốn ước lượng hợp lý cực đại - Áp dụng trên cây sinh lồi nhỏ 2.2.3. Đại lượng ngẫu nhiên và hàm phân phối 1) Định nghĩa: Một đại lượng (hay một biến) nhận các giá trị của nĩ với xác suất tương ứng nào đấy gọi là đại lượng ngẫu nhiên hay biến ngẫu nhiên. Phân loại các đại lượng ngẫu nhiên: Căn cứ vào giá trị mà biến ngẫu nhiên nhận ta phân các đại lượng ngẫu nhiên ra làm 2 loại chính: biến ngẫu nhiên rời rạc và biến ngẫu nhiên liên tục. Tuy nhiên, với vấn đề quan tâm của đề tài, chúng ta chỉ xét đến các biến ngẫu nhiên rời rạc. 2) Biến ngẫu nhiên rời rạc, bảng phân phối xác suất Nếu tập các giá trị mà biến ngẫu nhiên nhận là một tập gồm một số hữu hạn hoặc vơ hạn nhưng đếm được, khi đĩ biến ngẫu nhiên gọi là biến ngẫu nhiên rời rạc. Giả sử biến ngẫu nhiên ξ nhận các giá trị x12,xx , ,n , và Pxpi(),1,2,ξ ==∀=ii Để mơ tả biến ngẫu nhiên rời rạc ξ ta dùng bảng sau: ξ xxx12 n Pxpp()ξ = p in12 trong đĩ: ∑ pi =1. i Bảng với hai thơng tin xác định biến ngẫu nhiên ξ được gọi là bảng phân phối xác suất. 2.2.4. Các đặc trưng của đại lượng ngẫu nhiên 1) Kỳ vọng: Kỳ vọng của đại lượng ngẫu nhiên ξ là một con số, được kí hiệu là Eξ và được xác định như sau: Eξ = ∑ xpii i trong đĩ Pxpi(),1,2,ξ ==∀=ii Ý nghĩa: Kỳ vọng của biến ngẫu nhiên là giá trị trung bình mà biến ngẫu nhiên nhận hay là trọng tâm của phân phối xác suất. 2) Phương sai: Phương sai của đại lượng ngẫu nhiên ξ là một con số khơng âm, được kí hiệu là Dξ và được xác định như sau: DEξ =−()ξξ E2 Ý nghĩa: Phương sai của biến ngẫu nhiên là một số khơng âm dùng để đo mức độ phân tán (mức độ tản mát) của các giá trị của biến ngẫu nhiên ξ xung quanh tâm Eξ của nĩ. Dξ nhỏ thì độ phân tán nhỏ, độ tập trung lớn. Dξ càng lớn thì độ phân tán càng cao. Bùi Văn Đồng Trang 20
Phương pháp đại số cho bài tốn ước lượng hợp lý cực đại - Áp dụng trên cây sinh lồi nhỏ 2.2.5. Lý thuyết mẫu 1) Mẫu ngẫu nhiên Tiến hành n quan sát độc lập về biến ngẫu nhiên X nào đĩ. Ta gọi X i là việc quan sát lần thứ i về biến ngẫu nhiên X. Khi đĩ (,X12XX , ,n ) được gọi là mẫu ngẫu nhiên, n gọi là cỡ mẫu (số lần quan sát). Như vậy mẫu ngẫu nhiên cỡ n thực chất là n biến ngẫu nhiên độc lập, cùng phân phối như biến ngẫu nhiên X. Ta gọi xi là kết quả quan sát được ở lần thứ i. Khi đĩ (,x12xx , ,)n là n giá trị cụ thể ta quan sát được. Đĩ là giá trị cụ thể mà mẫu ngẫu nhiên (,X12XX , ,n )nhận. 2) Các đặc trưng mẫu Giả sử ta cần nghiên cứu biến ngẫu nhiên X với EX, DX mà ta chưa biết và đang phải đi tìm chúng. Ký hiệu μ = EX , σ 2 = DX . Giả sử (,X12XX , ,)n là mẫu ngẫu nhiên được rút ra từ X. Ta xây dựng biến 1 ngẫu nhiên rời rạc X ' nhận n giá trị mẫu với xác suất đều . n 1 PX()' = X = i n Kỳ vọng mẫu n ' 1 XEX==∑ Xi n i=1 Do (,X12XX , ,n )là các biến ngẫu nhiên độc lập cùng phân phối như X nên kỳ vọng mẫu là một biến ngẫu nhiên. Do đĩ ta lại tìm kỳ vọng và phương sai của X 11n EX= ∑ EXi == nEX μ nni=1 11n DX σ 2 DX===22∑ DXi n DX = nni=1 nn Phương sai mẫu nn 2'112 22 s ==DX∑∑() Xii −= X X − X nnii==11 n 22112 Es=−−−=−−−∑∑ E{( Xiiμμ ) ( X )}EXEX ( μ ) ( μ ) = nnii=1 11DX n − =−=−= nDX DX DX σ 2 nnn Bùi Văn Đồng Trang 21
Phương pháp đại số cho bài tốn ước lượng hợp lý cực đại - Áp dụng trên cây sinh lồi nhỏ 2.2.6. Ước lượng tham số Giả sử ta nghiên cứu biến ngẫu nhiên X và biết được phân phối X thuộc một họ phân phối nào đĩ. Khi đĩ để xác định hồn tồn phân phối của X ta phải xác định được các giá trị tham ẩn mà phân phối đĩ nhận. Trong trường hợp ta chưa biết được gì về phân phối của X, khi đĩ việc biết được các số đặc trưng của X cũng cho ta nhiều thơng tin giá trị. Do đĩ bài tốn đi tìm các ước lượng cho các tham ẩn của phân phối hoặc ước lượng cho các số đặc trưng của biến ngẫu nhiên là bài tốn rất cần thiết. 1) Ước lượng điểm Giả sử θ là tham ẩn cần ước lượng. Với mẫu ngẫu nhiên (,X12XX , ,n ), ta khơng thể ước lượng cho θ dựa vào mẫu ngẫu nhiên trên. Ta sẽ dùng một hàm nào đĩ của mẫu, tức là một hàm nào đĩ của n biến * X12,XX , , n để là ước lượng cho θ - Kí hiệu hàm đĩ là θ (X12 ,XX , ,n ) . Như vậy * θ (X12 ,XX , ,n ) là một biến ngẫu nhiên vì X12,XX , , n là các biến ngẫu nhiên độc * lập, cùng phân phối. θ (,X12XX , ,n )là ước lượng điểm vì với giá trị cụ thể của mẫu * * thì θ (,X12XX , ,n )nhận một giá trị cụ thể (một điểm) θ (x12 ,xx , ,n ) . 2) Ước lượng khơng chệch * Vì θ (x12 ,xx , ,n ) là một biến ngẫu nhiên nên ta khơng thể địi hỏi * θ (x12 ,xx , ,n ) đúng bằng giá trị θ cần tìm được. Lẽ tự nhiên ta địi hỏi * Exxxθ (12 , , ,n ) = θ * Ước lượng θ (x12 ,xx , ,n ) thỏa mãn hệ thức trên gọi là ước lượng khơng chệch của θ . Ta dùng X là ước lượng điểm cho EX , s2 là ước lượng điểm cho DX . 2.2.7. Sơ lược về ước lượng hợp lý cực đại Phần trên chúng ta đã đưa ra các ước lượng điểm cho kỳ vọng, phương sai. Cách đưa ra như vậy cĩ vẻ khơng được tự nhiên. Bây giờ chúng ta tìm hiểu một trong các phương pháp tìm được kết quả đã đưa ra. Đĩ là phương pháp hợp lý cực đại. Nội dung phương pháp như sau: Ta xét biến ngẫu nhiên ξ và đối với nĩ ta xác định: f (,xPxθ )= (ξθ= , ) θ là tham ẩn của phân phối của biến ngẫu nhiên ξ . Trước hết ta xét trường hợp θ là tham ẩn một chiều. Bùi Văn Đồng Trang 22
Phương pháp đại số cho bài tốn ước lượng hợp lý cực đại - Áp dụng trên cây sinh lồi nhỏ Giả sử (,X12XX , ,n ) là mẫu ngẫu nhiên cỡ n được rút ra từ ξ . Để cho gọn ta kí hiệu mẫu ngẫu nhiên là vectơ X. Đối với mẫu X đã cho ta xác định hàm Lx ()θ (hàm của tham ẩn θ ) như sau: nn LfXPXxi()θ ===∏∏ ( ,)θξ (i ,)θ ii==11 Lx ()θ được gọi là hàm hợp lý. ∂L ()θ Ta lập phương trình hợp lý x = 0 ∂θ ∂lnL (θ ) hoặc phương trình tương đương x = 0 ∂θ Nghiệm của phương trình trên phụ thuộc vào mẫu ngẫu nhiên X, và ta cũng chỉ xét những nghiệm như thế, được kí hiệu là θ *()X . θ *()X được gọi là ước lượng hợp lý cực đại. Ước lượng hợp lý cực đại cĩ các tính chất của một ước lượng tốt. Nếu θ là tham số ẩn vectơ, chẳng hạn θ = (θθ12 , , , θr ) khi đĩ phương trình hợp lý sẽ trở trở thành hệ phương trình: ⎧ ∂Lx ()θ ⎧ ∂lnLx (θ ) ⎪ ⎪ ⎨ ∂θi = 0 hoặc hệ tương đương ⎨ ∂θi = 0 ⎪ ⎪ ⎩ir=1,2, , ⎩ir=1,2, , Vì Lx ()θ và lnLx (θ )cĩ cùng điểm cực trị, mà hàm Lx ()θ lại biểu diễn dưới n dạng tích ∏ fX(,i θ ), cho nên ta thay phương trình hợp lý bởi dạng tương đương để i=1 giảm nhẹ khâu tính tốn: Lấy đạo hàm và giải phương trình. Ví dụ 1: Giả sử X = (XX12 , , , Xn ) là mẫu ngẫu nhiên, trong đĩ ⎧1 với xác suất p X i = ⎨ ⎩01 với xác suất qp= - Hãy chỉ ra hợp lý cực đại cho p (ở đây θ = p ) Ta cĩ: f (,xp )== P {ξ xp , } = px (1 − p )1−x với x = 0 hoặc x = 1 Khi đĩ nn nn ∑∑xnxii− xxiii1− ==11 inx n− nx Lpxi()===−=−∏∏ P {ξ Xp ,} p (1 p ) p (1) p =− p (1) p ii==11 ⇒=+−−lnLx ( p ) nX ln p ( n nX )ln(1 p ) Bùi Văn Đồng Trang 23
Phương pháp đại số cho bài tốn ước lượng hợp lý cực đại - Áp dụng trên cây sinh lồi nhỏ ∂−lnLp ( ) nXnnXnXnp− ⇒=−=x =0 ∂−−pp1(1) ppp Vậy nghiệm của phương trình hợp lý: n n * 1 m pX==∑ Xi =, vì m= ∑ Xi chính là tổng số lần X i nhận giá trị 1 hay nni=1 i=1 tổng số lần biến cố A, với p = PA(), xuất hiện. Ví dụ 2: Giả sử X = (XX12 , , , Xn ) là mẫu ngẫu nhiên rút ra từ phân phối chuẩn N(,μ σ 2 ). Hãy chỉ ra ước lượng hợp lý cực đại cho μ và σ 2 , ở đây θ = (,μσ2 ) tham số ẩn hai chiều 1 −−()x μ 2 1 2 fx(,θθ )== px (, ) e2σ σπ2 Khi đĩ: 1 n 1 2 2 n −−()x μ −−()xi μ 112 i 2 ∑ Le(,μσ2 )==2σ e2σ i=1 x ∏ nn i=1 σπ2 σπ(2 ) n 22nn 1 2 lnLXxi (μσ , )=− ln 2 π − ln σ −2 ∑() −μ 222σ i=1 ⎧ n ()X − μ ⎪∂lnL (μσ ,2 ) ∑ i ⎪ xi=1 ⎪ = 2 = 0 ⎨ ∂μ σ ⎪ 1 n ⎪ 2 −+nX2 ∑()0i −μ = ⎩⎪ σ i=1 Vậy ước lượng hợp lý cực đại cho μ là μ* = X , cho σ 2 = Dξ là n 2* 1 2 2 ()σ = ∑ (XXi −= ) s n i=1 Nhận xét: Qua 2 ví dụ trên chúng ta nhận lại được các ước lượng điểm đã nêu. Chúng ta sẽ phân tích kỹ về ước lượng hợp lý cực đại với mẫu quan sát ở chương sau. Bùi Văn Đồng Trang 24
Phương pháp đại số cho bài tốn ước lượng hợp lý cực đại - Áp dụng trên cây sinh lồi nhỏ Chương 3. ƯỚC LƯỢNG HỢP LÝ CỰC ĐẠI TRÊN MẪU QUAN SÁT Chương này chúng ta tìm hiểu kỹ hơn về MLE trên mơ hình thống kê. Dẫn ra một vài ví dụ về ước lượng hợp lý cực đại trên một số mẫu dữ liệu quan sát và giải bài tốn. 3.1. Ước lượng hợp lý cực đại là gì? MLE cĩ thể được cơng thức hĩa trong xác suất cổ điển với tên là Lý thuyết của ước lượng. Khả năng cực đại là một phương pháp đánh giá những tham số một mơ hình thối lui, từ đĩ giải quyết tốt cho những mẫu lớn. Từ chương trước cho thấy, MLE dẫn đến việc giải quyết làm cực đại tích của những đa thức. MLE được ứng dụng rộng rãi trong cuộc sống hiện nay, khơng chỉ trong ngành sinh học nĩi riêng mà cịn nhiều ngành khác như: xử lý ngơn ngữ tự nhiên, điện tử viễn thơng, tài chính ngân hàng, Vậy MLE là gì? Chúng ta lần lượt tìm hiểu những khái niệm và những mơ hình cho bài tốn. 3.1.1. Đặt vấn đề Chúng ta cĩ một mơ hình xác suất M của hiện tượng nào đĩ. Chúng ta biết chính xác cấu trúc của M, nhưng khơng biết là những giá trị của những tham số xác suất θ của nĩ. Mỗi sự hiện diện của M cho một sự quan sát x[i], tương ứng với phân phối của M. Mục tiêu của chúng ta là với các mẫu x[1], , x[N], ước lượng những tham số xác suất θ từ quá trình phát sinh quan sát dữ liệu trên. 3.1.2. Khái quát về ước lượng hợp lý cực đại Hàm khả năng (Likelihood Function) tương ứng với các mẫu x[1], , x[N] được cho bởi mơ hình những tham số θ với mơ hình xác xuất cĩ điều kiện M, được định nghĩa như sau: L()θ = Px ([1], ,[ xN ]|,θ M ) Điều kiện đặt ra cho những mơ hình chúng ta sẽ xem xét cho những mẫu x[1], x[2], , x[N] là: - Tập giá trị x[i] (i =1, , N) được xác định. - Sự phân bố của mỗi mẫu cĩ khả năng xảy ra là như nhau. - Mỗi mẫu được lấy độc lập với những mẫu trước đĩ. Trong MLE chúng ta tìm kiếm tham số mẫu θ làm cho hàm trên đạt giá trị cực đại. Hay là phải tìm một vectơ của những tham số θ mà được phát sinh từ bộ dữ liệu đã cho. Bùi Văn Đồng Trang 25
Phương pháp đại số cho bài tốn ước lượng hợp lý cực đại - Áp dụng trên cây sinh lồi nhỏ 3.1.3. Ví dụ về ước lượng hợp lý cực đại Chúng ta sẽ bắt đầu với từ một ví dụ đơn giản nhất là đánh giá sự thiên lệch khi tung một cây đinh bấm, sau đĩ đến những mơ hình phức tạp hơn từ đĩ áp dụng MLE tới phỏng đốn cây sinh lồi. Hình 1: Hai trường hợp xảy ra khi tung đinh bấm Đối với cây đinh, khi được tung lên khi rơi xuống nĩ cĩ thể ở một trong hai trường hợp sau (hình 1): Đầu (H) hoặc Đuơi (T), Chúng ta biểu thị bởi θ (chưa biết) là xác suất P(H). Cho một sự nối tiếp những mẫu quan sát D: x[1], x[2], , x[N] mà chúng ta muốn ước lượng PH()=θ và PT()= 1−θ Từ bộ mẫu dữ liệu quan sát trên ta cĩ hàm khả năng là: N LD ()θθ==PD ( | )∏ Pxi ([]) i=1 Với ví dụ trên, giả sử dãy mẫu quan sát là H, T, T, H, H ta cĩ hàm hợp lý: LD ().(1).(1) θ =θθ−− θθθ 3.2. Giải bài tốn ước lượng hợp lý cực đại 3.2.1. Nguyên lý ước lượng hợp lý cực đại Chọn những tham số mà làm cực đại hàm khả năng. Nguyên lý này được sử dụng rộng rãi trong việc ước lượng trong thống kê, cả trong việc nhìn nhận của trực giác. 3.2.2. Logarit hàm hợp lý Kỹ thuật khác để làm cho việc tính tốn dễ hơn khi làm việc trên logarit hàm likelihood hơn chính hàm likelihood. Lý do chính cho điều này bởi tính tốn hơn là lý thuyết. Nếu chúng ta nhân lên nhiều số rất nhỏ cùng nhau (ví dụ nhỏ hơn 0.0001) thì chúng ta sẽ khĩ cĩ thể biểu hiện số trên với một máy tính thơng thường nào đĩ hiện nay vì nĩ quá gần với 0. Tình trạng này thường xuất hiện trong việc tính tốn xác suất, khi chúng ta đang nhân những xác suất nhiều sự kiện hiếm cĩ nhưng độc lập để tính tốn xác suất chung. Log của hàm likelihood thường đơn giản nhiều cho tính tốn, và chúng ta thấy nghiệm thỏa giá trị lớn nhất của hàm log likelihood cũng là nghiệm giá trị lớn nhất của chính hàm likelihood. Với ví dụ ở 3.1.3, log likelihood là: lLDD()θ = ln ()θ haylNDH(θ )= lnθθ+− N T ln(1 ) Bùi Văn Đồng Trang 26
Phương pháp đại số cho bài tốn ước lượng hợp lý cực đại - Áp dụng trên cây sinh lồi nhỏ Cơng thức này thoạt nhìn khơng cĩ vẻ đơn giản, nhưng thật ra nĩ rất dễ dàng khi tính đạo hàm cho log likelihood trong trường hợp này cũng như nhiều trường hợp khác. Lấy đạo hàm và cho chúng bằng 0, chúng ta được: NNN(1−θ ) −−+ NNNNθθ() l' ()θ =−HT = H T= HHT=0 D θθθθ1.(1).(1)−− θθ − N ⇔θ = H NN+ HT Bảng 1: Bảng biến thiên của hàm hợp lý với θ là nghiệm chúng ta cần tìm, phù hợp với những gì chúng ta mong muốn. Theo 3 ví dụ trên nếu (NH, NT ) = (3, 2) và MLE tính được là = 0.6 . Đồ thị của hàm hợp lý 5 cho ta thấy ở hình 2. Hình 2: Đồ thị của hàm hợp lý 3.3. Tổng quát hĩa bài tốn ước lượng hợp lý cực đại 3.3.1. Ước lượng hợp lý cực đại trên mẫu quan sát Nếu x là biến ngẫu nhiên với hàm phân bố: fx[]iK(θ 1 ,θθ 2 , , ) với θ12,θθ , , K là K tham số cần phải ước lượng, với dãy N mẫu độc lập là x[1], x[2], , x[N]. Thì hàm likelihood được cho bởi tích sau: N LfDKx(,θ12θθ , ,)= ∏ []12i (, θθθ , ,) K i=1 Bùi Văn Đồng Trang 27
Phương pháp đại số cho bài tốn ước lượng hợp lý cực đại - Áp dụng trên cây sinh lồi nhỏ và hàm ln likelihood như sau: N DD(θ )== ln Lf (θθθ )∑ ln x[]i ( 1 , 1 , ,θk ) i=1 MLE của θ12,θθ , , K đạt được khi LD ()θ hay D ()θ là lớn nhất, chúng ta đã biết xác định giá trị lớn nhất với D ()θ dễ hơn với LD ()θ , vậy MLE của θ12,θθ , , K là giải hệ K phương trình sau: ∂() ==0, j 1,2, , K ∂θ j Ví dụ: Tung một con xúc sắc cĩ K = 6 mặt, chúng ta muốn xác định những tham số θ12,θθ , , K là xác suất của mặt cĩ nút tương ứng 1, 2, , K nhận được khi tung xúc sắc. Từ quan sát ta cĩ NN12, , , NK là số lượng tương ứng của từng mặt khi quan sát. Theo cơng thức hàm khả năng sẽ: K N j LDj()θ = ∏θ j=1 và hàm ln likelihood tương ứng sẽ là: K lLDD()θ == ln ()θθ∑ N i ln()i i=1 Sau khi giải hệ phương trình ∂()l ==0, j 1,2, ,K ∂θ j chúng ta được: Nk θk = K với k =1, , K ∑ Nl l=1 3.3.2. Một số phương pháp giải phương trình hợp lý Theo trên, giải phương trình hợp lý làm cực đại phương trình: uu12 un Lff()θ = 12 ()θθ () () fn θ với ui ∈ . Hiện nay cĩ hai hướng tiếp cận khác nhau để giải quyết bài tốn này, trong mỗi phương pháp cĩ những ưu và khuyết điểm riêng của nĩ: Phương pháp gần đúng: Giải phương trình hợp lý bằng phương pháp tìm kiếm cục bộ, heuristics, Ưu điểm của phương pháp này là nhanh chĩng, cĩ thể giải quyết Bùi Văn Đồng Trang 28
Phương pháp đại số cho bài tốn ước lượng hợp lý cực đại - Áp dụng trên cây sinh lồi nhỏ trên những bài tốn lớn. Nhược điểm lớn nhất của phương pháp này là tính tin cậy khơng cao. Phương pháp tính tốn đại số: Ngược lại với phương pháp gần đúng trên, phương pháp tính tốn đại số hiện nay chỉ giải quyết được với những bài tốn nhỏ, nhưng cho kết quả chính xác. Với sự tiến bộ của khoa học kỹ thuật nĩi chung và ngành máy tính cũng như lãnh vực đại số máy tính nĩi riêng, đã mở ra con đường cho hướng tiếp cận này. Vì lý do trên phương pháp này được chọn sử dụng để giải quyết bài tốn ước lượng hợp lý cực đại - áp dụng trên cây sinh lồi nhỏ. Để hiểu rõ cây sinh lồi, ước lượng hợp lý cực đại trên cây sinh lồi chúng ta tìm hiểu sơ qua cây sinh lồi và mơ hình xác suất thống kê trên cây sinh lồi ở chương sau. Bùi Văn Đồng Trang 29
Phương pháp đại số cho bài tốn ước lượng hợp lý cực đại - Áp dụng trên cây sinh lồi nhỏ Chương 4. CÂY SINH LỒI - MƠ HÌNH XÁC SUẤT THỐNG KÊ TRÊN CÂY SINH LỒI Chương này giới thiệu cây sinh lồi cũng mơ hình xác suất thống kê trên cây sinh lồi. Ngồi ra cũng giới thiệu một số mơ hình thường sử dụng hiện nay trên cây sinh lồi như mơ hình Neyman 2 trạng thái, Jukes – Cantor, Kimura với 2 và 3 tham số. 4.1. Giới thiệu sơ lược về cây sinh lồi Cây sinh lồi (cịn gọi là cây tiến hĩa hay là cây chủng lồi) mơ tả lịch sử tiến hĩa của một nhĩm các lồi (species) 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ĩ nhiều hướng nghiên cứu khác nhau để chứng minh đặc điểm phát sinh sinh lồi này. Trước hết, người ta cĩ thể so sánh trình tự các đoạn DNA (thuộc sinh học phân tử hay hệ gene học (genomics); hoặc so sánh các hĩa thạch (fossil) hoặc các di chỉ (record) của sinh vật cổ (thuộc khảo cổ học - paleontology). Các nhà sinh học tổ chức và phân tích các mối quan hệ tiến hĩa thơng qua các phương pháp khác nhau, bao gồm phân loại học (phylogenetics), ngoại hình học (phenetics) và cladistics. Các sự kiện chính xảy ra trong quá trình tiến hĩa của sự sống được xây dựng thành biểu đồ thời gian của tiến hĩa (evolutionary timeline) dựa trên các hiểu biết hiện nay của khoa học. Hình 3 cho ta thấy hình dạng của cây sinh lồi sự sống trên hành tinh chúng ta. Hình 3: Cây sinh lồi của sự sống Bùi Văn Đồng Trang 30
Phương pháp đại số cho bài tốn ước lượng hợp lý cực đại - Áp dụng trên cây sinh lồi nhỏ 4.2. Các nghiên cứu phát sinh sinh lồi Trong ngành sinh học, người ta nghiên cứu mối quan hệ giữa các lồi sinh vật thơng qua các bằng chứng phân tử, cụ thể là trình tự DNA và protein. Như vậy sự khác biệt giữa các trình tự (DNA) chỉ định sự phân kỳ di truyền như là kết quả của tiến hĩa phân tử theo tiến trình thời gian. Các phương pháp dùng để nghiên cứu phát sinh sinh lồi chủ yếu dựa trên một sự giả định về các tiến trình tiến hĩa ở mức phân tử thơng qua việc quan sát phân tích trình tự DNA hoặc protein. Bằng cách sử dụng cơng cụ máy tính, các chuỗi dữ liệu sẽ được mơ phỏng tiến trình tiến hĩa và phân tích tiến trình phát sinh sinh lồi. Giả sử là chúng ta cĩ một “cây tiến hĩa đúng”, chúng ta cĩ thể dùng nĩ để kiểm tra lại độ chính xác, tính nhất quán khả năng tin cậy của những mơ hình tiến hĩa. Tuy nhiên khi sử dụng các dữ liệu sinh học, cái gọi là cây tiến hĩa cĩ thể khơng bao giờ cĩ, hoặc ít ra cũng cĩ thể nĩi là KHƠNG BIẾT. Do vậy người ta chấp nhận một cây tiến hĩa được dựng nên mà người ta tin là nĩ GIỐNG NHẤT với cây tiến hĩa đúng. Trong các bước trình tự cơ bản để cho một nghiên cứu phát sinh sinh lồi thì đánh giá sự phát sinh sinh lồi cũng là một bước khơng thể bỏ qua. Sau đây là một số phương pháp được sử dụng hiện nay: Phương pháp Hà tiện tối đa (Maximum parsimony), một sự giả định cho rằng cây tiến hĩa tốt nhất mổ tả tiến trình tiến hĩa tốt nhất chính là cây mơ tả được các lồi ít thay đổi nhất tức là cĩ ít đột biến nhất, cây vì thế cĩ điểm thấp nhất (hà tiện) theo một tiêu chuẩn định sẵn. Phương pháp Khoảng cách (Distance method): Khác với phương pháp parsimony cĩ mơ hình tiến hĩa là một hàm ẩn, thì phương pháp khoảng cách lại cĩ mơ hình tiến hĩa là một hàm hiện. Trong phương pháp này từng cặp trình tự một sẽ được so sánh thẳng hàng cặp đơi và ứng với từng cặp, khoảng cách di truyền sẽ được tính tốn. Do mơ hình tiến hĩa là một hàm hiện nên một trong số mơ hình tiến hĩa cĩ thể được chọn để tính tốn khoảng cách di truyền giữa từng cặp taxa từ đĩ cho ra một ma trận khoảng cách giữa tất cả các taxa. Và để cĩ được cây tiến hĩa, phương pháp phân rã hình ngơi sao thường được sử dụng ví dụ phương pháp neighbor-joining(liên kết cận kề). Do phương pháp neighbor-joining mà một trong những phương pháp nhanh nhất để dị tìm cây tiến hĩa nên nĩ thường được sử dụng để phân tích khối dữ liệu lớn với nhiều taxa. Phương pháp Hợp lý cực đại (Maximum Likelihood) là phương pháp tiêu tốn nhiều thời gian nhất nhưng lại cho kết quả đáng tin cậy nhất. Mơ hình tiến hĩa dùng trong phương pháp này cũng là một hàm hiện. Ứng với mỗi mơ hình tiến hĩa được chọn, phương pháp này sẽ tính tốn khả năng xác suất mà một cây tiến hĩa cĩ thể cĩ từ chuỗi trình tự phân tích. Cây tiến hĩa cĩ xác suất cao nhất là cây cuối cùng được chọn. Chúng ta tập trung vào phương pháp ML, để hiểu được điều này chúng ta bắt đầu với những ví dụ cụ thể để mơ hình hĩa bài tốn trên cây sinh lồi. Bùi Văn Đồng Trang 31
Phương pháp đại số cho bài tốn ước lượng hợp lý cực đại - Áp dụng trên cây sinh lồi nhỏ 4.3. Mơ hình ước lượng hợp lý cực đại trên cây sinh lồi Cho S1, S2, , SN là một dãy mẫu DNA mà chúng ta cĩ. Để đơn giản, giả thiết rằng mọi chuỗi trên cĩ cùng chiều dài. Chúng ta muốn xác định những tham số của một cây sinh lồi thơng qua dãy mẫu trên và làm cực đại khả năng cĩ thể xảy ra. Để giải bài tốn này ta cần chỉ rõ một mơ hình xác suất. Cho đơn giản, giả thiết “DNA” của chúng ta chỉ cĩ hai trạng thái X và Y. Cạnh e được gán xác suất pe , cĩ nghĩa là xác suất những thay thế (X ÙY) ngang qua e là pe (Hình 4). Hình 4: Mơ tả xác suất chuyển đổi trạng thái của chuỗi “DNA” Phải chăng cạnh e được gán xác suất pe , cĩ nghĩa xác suất của những mẫu liên quan thay thế ngang qua e, ví dụ XXYXÝYXYXX được xác định rõ, và dễ dàng tính 23 tốn hàm Likelihood cho mẫu này: ppee(1− ) . Qua bài tốn trên cĩ câu hỏi đặt ra như sau: Cái gì “hợp lý” mẫu trên? Cĩ nghĩa là tìm kiếm pe mà nĩ làm cực đại xác suất của các mẫu trên. Mở rộng mơ hình bài tốn trên, mơ hình mới của chúng ta sẽ gồm cĩ một cây thơng thường, nhưng ngồi ra các cạnh được gán những xác suất thay thế. Ví dụ ở đây, cây cĩ 4 taxa. Những taxa này là sinh vật hoặc là gen, mỗi một taxa được mơ tả bởi chuỗi DNA: Human: ATGGCTATTCTTATAGTACG Mouse: BATCGCTAGTCTTATATTACA Rate: TTCACTAGACCTGTGGTCCA Chicken: TTGACCAGACCTGTGGTCCG Hình 5: Cây sinh lồi với các nút trong và xác suất chuyển đổi Bùi Văn Đồng Trang 32
Phương pháp đại số cho bài tốn ước lượng hợp lý cực đại - Áp dụng trên cây sinh lồi nhỏ Bây giờ chúng ta khơng biết trạng thái ở tại nút trong, đồng thời cũng khơng biết những tham số cạnh ppppppp,,,,,,(Hình 5). ee123455 ee eee6 Hai hướng được đưa ra: 1. Cực đại qua những trạng thái của những nút bên trong. 2. Trung bình qua những trạng thái của những nút bên trong. Trong cả hai trường hợp, chúng ta đều làm cực đại những tham số qua cạnh. Trong hướng đầu tiên (trung bình, hoặc tổng những trạng thái những nút trong) chúng ta đang tìm kiếm “thích hợp nhất” đặt trên những cạnh của cây. Hướng này được gọi là cực đại khả năng cây sinh lồi. Trong hướng này ML cĩ lẽ là phương pháp suy diễn rộng rãi nhất được sử dụng hiện nay. Trong hướng thứ hai (làm cực đại qua những trạng thái của những nút trong) Chúng ta đang tìm kiếm “thích hợp nhất” những trạng thái tổ tiên. Hướng này được cực đại khả năng xảy ra ở tổ tiên (ancestral maximum likelihood -AML). Hướng thứ hai cũng phải sử dụng phương pháp ML bởi vì mục tiêu cuối cùng cũng phải là cực đại khả năng. 4.4. Mơ hình tiến hĩa Trong sinh vật học, quá trính tiến hĩa là một quá trình phức tạp. Trong quá trình đĩ, các chuỗi gen phân kỳ từ cùng một tổ tiên. Nhưng vì sự đột biến và chia rẽ của sự đột biến đĩ làm tiến hĩa cộng đồng bởi sự chọn lọc. Kết quả là sự thay đổi trạng thái của một nucleotide này thành một nucleotide khác ở những vị trí khác nhau. Trong việc tái cấu trúc cây sinh lồi, chúng ta cần phải chấp nhận mơ hình với một số giả định về quá trình cũng như trạng thái thay thế sau: - Mơ hình đơn giản nhất là mơ hình mà trong đĩ khả năng của bất kỳ nucleotide nào thay đổi thành bất kỳ nucleotide khác là bằng nhau. - Dự đốn khả năng rằng một nucleotide cụ thể ở một vị trí cụ thể sẽ thay đổi thành một nucleotide xác định khác trong một khoảng thời gian, cái chúng ta cần biết ở đây là tỷ lệ tức thời của sự thay đổi. Ma trận tỷ lệ (hoặc ma trận Q) là ma trận vuơng Qq= (ij ), với chỉ mục hàng và cột cho bởi ∑={,A CGT , ,}. Chúng ta cũng cĩ thể sử dụng ký tự nhị phân hoặc 20 kí tự của amino axit cho tập ∑ . Ma trận tỷ lệ phải thỏa những yêu cầu sau: qij ≥ 0 với ij≠ ∑ qij = 0 cho tất cả i∈∑ , j∈∑ qii < 0 với tất cả i∈∑ Bùi Văn Đồng Trang 33
Phương pháp đại số cho bài tốn ước lượng hợp lý cực đại - Áp dụng trên cây sinh lồi nhỏ Ma trận tỷ lệ cĩ được từ ý nghĩa từ tỷ lệ tức thời của đột biến. Từ ma trận tỷ lệ Q, chúng ta cĩ thể tính được ma trận thay thế θ ()t bởi hàm mũ theo cơng thức sau: ∞ 1 θ ()te==Qt ∑ Qti i i=0 i! Phần tử của θ ()t ở dịng i và cột j chính là xác suất mà sự thay đổi i→→ j xảy ra trong một khoảng thời gian là t. Mơ hình đơn giản cĩ một tham số và được biết là mơ hình Jukes-Cantor với tỷ lệ chuyển đổi từ một nucleotide này đến một nucleotide khác là bằng nhau như sau: A GCT A ⎛⎞−3α ααα ⎜⎟ G α −3αα α Q = ⎜⎟ C ⎜⎟α ααα−3 ⎜⎟ T ⎝⎠α αα−3 α Và ma trận thay thế tương ứng là: ⎛⎞13111+eeee−−44ααααtttt −−− − 4 − 4 ⎜⎟ 1 ⎜⎟11311−+eeee−−−−444αααttt − −4αt θ ()t = 4 ⎜⎟−−44ααtt −− 4 α t4αt ⎜⎟11131−−+−ee ee ⎜⎟−−−444αααttt −4αt ⎝⎠11113−−−+eee e Ma trận θ ()t thỏa: các phần tử của ma trận đều lớn hơn hoặc bằng 0 và nhỏ hơn hoặc bằng 1, tổng các phần tử trên một hàng bằng 1. Chúng ta cần xác định tính hợp lý mơ hình trên. Giả sử chúng ta cĩ G ở vị trí nào đĩ ở thời điểm t = 0, chúng ta hỏi rằng khả năng bao nhiêu ở đĩ vẫn là G vào thời điểm t (kí hiệu Pt()GG ()), và tương tự như vậy khả năng là bao nhiêu nếu như A thay thế vào vị trí đĩ (kí hiệu Pt()GA ()). Nếu tỉ lệ thay đổi là α trên đơn vị thời gian như mơ hình Jukes - Cantor trên, thì: 13 11 Pt() =+ e-4αt và Pt()=− e-4αt ()GG 44 ()GA 44 Cũng theo mơ hình Jukes-Cantor thì tất cả thay thế là như nhau, nên phát biểu chung là: 13 11 Pt() =+ e-4αt và Pt()=− e-4αt ()ii 44 ()ij 44 Ta thấy: Khi t → 0 thì Pt()ii ()→ 1 và Pt()ij ()→ 0, Bùi Văn Đồng Trang 34
Phương pháp đại số cho bài tốn ước lượng hợp lý cực đại - Áp dụng trên cây sinh lồi nhỏ 1 1 Khi t →∞ thì Pt()→ và Pt()→ ()ii 4 ()ij 4 Điều này rõ ràng là phù hợp với thực tế của mơ hình Jukes - Cantor, vì tại một thời điểm tức thời việc giử nguyên trạng thái với xác suất rõ ràng là bằng 1 và chuyển trạng thái này sang trạng thái khác là 0. Tương tự khi thời gian vơ cùng lớn thì việc chuyển đổi trạng thái từ một nucleotide này sang một nucleotide khác hay giữ nguyên trạng thái là bằng nhau và bằng 0.25. Hiện nay, ngồi mơ hình Jukes-Cantor cịn cĩ một số mơ hình khác thường sử dụng như: Kimura-2, Kimura-3, . Trong các mơ hình này cĩ sự khác nhau về tỉ lệ thay đổi trạng thái giữa các cơ sở. Khi sử dụng mơ hình tiến hĩa để tái cấu trúc cây, một là gán giá trị cụ thể cho tỉ lệ hoặc là ước lượng giá trị từ dữ liệu. Những mơ hình này hồn tồn giả định rằng các tốc độ là như nhau ở tất cả các vị trí. ML cố gắng suy ra một cây sinh lồi bằng cách tìm ra cây mà cực đại khả năng đối với dữ liệu mẫu. Ví dụ: Dữ liệu mẫu ở đây là những chuỗi bằng nhau của nucleotides hoặc amino acids (chiều dài mỗi chuỗi N=32): TCAAAAATGGCTTTATTCGCTTAATGCCGTTA TCCGTGATGGATTTATTTCTGCAATGCCTGTC TTCGTGATGGATTTATTGTTGGTATGCCAGTC TTCGTGACGGGTTTATCTTGGCAATGCCGGTC Chúng ta bắt đầu với một mơ hình tiến hĩa cho bởi ma trận θ ()t và một giả định một số hình dáng cây với chiều dài tương ứng. Cĩ 15 khả năng cho các dạng cây cĩ gốc với 4 taxa, một trong những cây đĩ là hình 6, trong đĩ các đỉnh ở lá tương ứng với các dữ liệu dĩng theo cột được đánh dấu đánh đậm trên 4 chuỗi trên. Hình 6: Một trong những cây sinh lồi 4 taxa Chúng ta khơng biết các nucleotide ở nút X và Y, nhưng cĩ 4 khả năng xảy ra cho mỗi nút X và Y, vậy cĩ cĩ 16 trường hợp cĩ thể xảy ra ở cây trên, một trong những trường hợp đĩ là hình 7. Bùi Văn Đồng Trang 35
Phương pháp đại số cho bài tốn ước lượng hợp lý cực đại - Áp dụng trên cây sinh lồi nhỏ Hình 7: Cây sinh lồ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 Xác xuất cho sự kiện mà mẫu quan sát A ở gốc là PA, bằng tần suất xuất hiện của A và thường được lấy bằng 0.25, giá trị này xác định được do thực nghiệm và độc lập với mơ hình. Xác suất chuyển đổi từ A ở gốc đến G ở lá được tính tốn từ ma trận θ ()t và chiều dài của nhánh từ A đến G là P(AG). Vậy xác suất của cây là: PPPPPPPtreeAAGACATTTT1= ()()()()( T). Bởi vì cĩ 16 trường hợp như vậy, xác suất của cây được tính bằng tổng các khả năng như sau: PPPtree_ i =+++ tree12 tree Ptree16 Đây chỉ là xác suất cho cây với dữ liệu quan sát ở một vị trí i được đánh dấu màu đậm ở các chuỗi trên. Khả năng của tồn bộ dữ liệu mẫu ở tất cả các vị trí bằng tích các khả năng cho mỗi một vị trí từ 1 đến N N PPTREE= ∏ tree_ i i=1 Áp dụng phương pháp ML là tìm xác suất các Ptree_ i hay rõ hơn là tìm xác suất chuyển đổi trạng thái trên các nhánh của cây dựa theo tham số của ma trận θ ()t trên từng nhánh của cây sao cho xác suất PTREE đạt giá trị lớn nhất. Tuy nhiên việc giải bài tốn trên là việc giải một hệ thống phương trình phi tuyến với nhiều ẩn số. Việc giải bằng tay là một điều khơng thể. Hướng giải quyết đưa ra là chọn một phương pháp tốn học thích hợp kết hợp những ứng dụng của đại số máy tính hiện nay chúng ta cĩ thể giải quyết bài tốn trên với một số cây sinh lồi nhỏ với một số mơ hình chuyển đổi thường sử dụng.Với cách tiếp cận như vậy chúng ta cĩ thể giải tìm nghiệm chính xác cho bài tốn trên. Một trong những phương pháp đĩ là tìm thành phần bất biến trên cây sinh lồi sẽ giới thiệu ở chương sau. Bùi Văn Đồng Trang 36
Phương pháp đại số cho bài tốn ước lượng hợp lý cực đại - Áp dụng trên cây sinh lồi nhỏ Chương 5. BẤT BIẾN TRÊN CÂY SINH LỒI Theo chương trước chúng ta nhận thấy, giải bài tốn cây sinh lồi dẫn đến giải một bài tốn cực đại một phương trình phi tuyến rất nhiều ẩn. Việc làm này khĩ khả thi ngay cả những cây sinh lồi nhỏ. Người ta nhận thấy, đối với những mơ hình thường sử dụng, trên cây sinh lồi tồn tại những thành phần bất biến. Đối với một cây sinh lồi cụ thể thành phần khơng đổi và khơng phụ thuộc vào mẫu dữ liệu quan sát. Từ những thành phần bất biến này, thay vì giải bài tốn trên các tham số thì ta giải bài tốn tương đương dựa trên các thành phần bất biến với sẽ đơn giản hơn. Trong chương này tập trung vào việc tìm tất cả thành phần bất biến. Cuối chương cĩ một ví dụ về bất biến trên một cây sinh lồi cụ thể. 5.1. Dẫn nhập Mơ hình thống kê đại số mà chúng ta đang xét trên cây sinh lồi là một ánh xạ cĩ dạng: f : dm→ ở đây khơng gian tổng quát trên trường số phức, tuy nhiên các toạ độ thực tế f1, , fm của hàm số là các đa thức cĩ hệ số hữu tỷ, cĩ nghĩa là ff11, ,md∈ [θ , ,θ ]. Sử dụng phương pháp hợp lý cực đại, với các chuỗi dữ liệu quan sát ta cĩ phương trình hợp lý tương ứng sau: u1 um L= f1 fm (1) trong đĩ uu1, , m là các số nguyên dương. Mục tiêu cuối cùng là làm cực đại hàm L trên bằng cách giải các phương trình đạo hàm riêng của nĩ: m uf∂ ∑ ii= 0 với j = 1, , d (2) i=0 fij∂θ Tuy nhiên, khi nghiên cứu bài tốn trên cây sinh lồi các đa thức f1, , fm là những phương trình phi tuyến với nhiều tham số θ1, ,θd , cho nên việc giải bài tốn trên với việc giải hệ phương trình (2) là việc làm khĩ khả thi. Một câu hỏi được đặt ra: các tập ảnh f1, , fm như thế nào khi các θ1, ,θd chạy trên miền xác định của nĩ? Nếu chúng ta xác định được tập các ảnh f1, , fm thì thay vì giải quyết bài tốn (1) trên các tham số θ1, ,θd chúng ta chỉ xét bài tốn (1) trên các tọa độ f1, , fm sẽ đơn giản hơn nhiều. Ví dụ: Chúng ta xét các ví dụ với ánh xạ f : 23→ Bùi Văn Đồng Trang 37
Phương pháp đại số cho bài tốn ước lượng hợp lý cực đại - Áp dụng trên cây sinh lồi nhỏ 2 (i) Nếu f = (,,)θ1 θ1 θ 2 θ 1 θ 2 thì tập ảnh là nghiệm phương trình f2− f 3 = 0 2 2 (ii) Nếu f = (θ1 ,2 θ1 θ 2 , θ 2 ) thì tập ảnh là nghiệm phương 2 trình f2 −4 f1 f 3 = 0 5 5 4 4 (iii) Nếu f =(,,)θ1 + θ1 θ 2 θ 1 + θ2 θ1 θ 2 + θ 2 thì tập ảnh là nghiệm phương 11 4 5 20 trình 2 ( f1+ f 2 − f 3 )( f2 + f 3 − f 1)( − f1 + f 3 − f 2 ) = 0 Qua các ví dụ trên cĩ nhận xét sau: Các đa thức f1, , fm ở dạng những đơn thức thì tập ảnh là nghiệm của những phương trình đơn giản, ngược lại thì là những phương trình bậc rất lớn. Quay trở lại bài tốn trên cây sinh lồi chúng ta quan tâm, những đa thức f1, , fm đối với từng cây cụ thể cĩ tính chất riêng của chúng. Tập hợp ảnh của những f1, , fm tức là tìm tất cả các phương trình quan hệ của chúng. Tập các phương trình như thế được gọi là thành phần bất biến của cây sinh lồi. Mục tiêu của phần này giới thiệu một phép biến đổi cĩ tên là phép biến đổi Fourier để tìm ra tất cả các bất biến trên một cây sinh lồi cụ thể. 5.2. Mơ hình xác suất trên cây sinh lồi 5.2.1. Mơ hình bài tốn cây sinh lồi Cho T là cây cĩ gốc với n lá. Đặt V(T) là tập các nút của T. Với mỗi một vVT∈ (), chúng ta kí hiệu biến Xv, mỗi biến này mang 1 trong k giá trị. Trong sinh học, k hầu như cĩ các giá trị 2, 4 và 20. Kí hiệu P(Xv = i) cho xác suất Xv mang trạng thái i. Mối quan hệ giữa các biến ngẫu nhiên Xv được xác định bởi cấu trúc của cây. Đặt π là phân bố của biến Xr tại nút gốc r. Với mỗi một nút vVT∈ ()\{} r, đặt a(v) là nút cha duy nhất của v. Sự chuyển trạng thái từ a(v) đến v được cho bởi ma trận xác suất chuyển đổi A(v) cĩ kích cỡ kk× . Và xác suất phân bố ở mỗi một nút được tính tốn đệ quy như sau: k ()v P().() Xv = j = ∑ Aij P Xa() v = i i=1 Cơng thức này được suy ra từ phân bố trên tất cả biến ngẫu nhiên Xv. Chúng ta gán nhãn các nút lá cho T bởi 1, 2, , n và ta cĩ xác suất phân bố các biến tại các lá: p= P( X= i , X= i , , X= i ) i1 i 2 in 1 1 2 2 n n Trong các ứng dụng sinh học, người ta ước lượng cĩ kn khả năng từ n chuỗi bằng nhau trên k kí tự. Mục đích chúng ta là dựa vào n chuỗi bằng nhau đĩ, xác định hình dáng cây sinh lồi ở quá khứ mà khả năng xảy ra lớn nhất, nĩi cách khác là tái cấu trúc cây sinh lồi. Vậy đầu vào bài tốn chúng ta chỉ cĩ n mẫu dữ liệu, tức là n chuỗi DNA tương ứng, các phân bố gốc π và ma trận chuyển trạng thái A(v) là chưa biết. Tuy nhiên để đơn giản cho các bài tốn, người ta đưa ra các mơ hình đơn giản Bùi Văn Đồng Trang 38
Phương pháp đại số cho bài tốn ước lượng hợp lý cực đại - Áp dụng trên cây sinh lồi nhỏ gần với thực tế thường sử dụng là: Phân phối π là phân phối đều và ma trận chuyển trạng thái A(v) được sử dụng là mơ hình Jukes - Cantor hay Kimura 2 và 3 trạng thái. Với các giả thiết trên, các bất biến của cây sinh lồi của mơ hình là một đa thức dựa trên các khả năng ở lá là p và triệt tiêu với mọi sự chọn lựa tham số của mơ i1 i 2 in hình. Tập các đa thức là iđêan nguyên tố trên vành đa thức với các biến chưa biết p . Mục tiêu chúng ta là tìm các iđêan này. i1 i 2 in 5.2.2. Nhĩm Abel và sự liên hệ với các ma trận chuyển đổi Ở mơ hình Neyman trên 2 kí tự (k = 2) là mơ hình với ma trận chuyển đổi ⎛1− a a ⎞ A()v = ⎜ v v ⎟ ⎜ a1− a ⎟ ⎝ v v ⎠ với av là xác suất được tạo ra bởi sự chuyển đổi giữa các trạng thái dọc theo cạnh từ a(v) đến v. Mơ hình Kimura với 3 tham số với k = 4 kí tự (đối với chuỗi DNA) cĩ ma trận chuyển đổi sau: ⎛1−a − b − c a b c ⎞ ⎜ v v v v v v ⎟ ()v ⎜ av 1−av − b v − c v cv bv ⎟ A = ⎜ ⎟ bv cv 1−av − b v − c v av ⎜ ⎟ ⎝ cv bv av 1−av − b v − c v ⎠ Mơ hình Kimura 2 tham số được định nghĩa như ma trận trên với bcvv= . Tương tự, mơ hình Jukes- Cantor với 4 kí tự, ma trận trên với abcvv==v. Chìa khĩa đối với trạng thái các biến ngẫu nhiên X v là nhĩm hữu hạn Abel (ví dụ Z2 = {0,1} hoặc ZZ22⊕={(0,0),(0,1),(1,0),(1,1)} với phép tốn cộng trên các tọa độ và mod cho 2). Giả sử rằng, chúng ta xem các cơ sở {A, G, C, T} như là các phần tử của nhĩm Abel, với phép tốn được định nghĩa với bảng cộng sau: + AGCT A A G C T G G A T C C C T A G T T C G A Nhĩm trên đẳng cấu với nhĩm ZZ2⊕ 2 , tương ứng với Á(0,0), GÙ(0,1), CÙ(1,0), TÙ(1,1). Từ đĩ dễ thấy rằng, ma trận ở mơ hình Kimura 3 tham số cĩ tính chất tương ứng với từng cặp cơ sở (,ggij ). Mặt khác, chúng ta thấy rằng sự chuyển trạng thái từ gi đến g j chỉ phụ thuộc vào hiệu ggi− j. Điều đĩ cũng đúng khi chúng ta xem xét Bùi Văn Đồng Trang 39
Phương pháp đại số cho bài tốn ước lượng hợp lý cực đại - Áp dụng trên cây sinh lồi nhỏ đối với mơ hình Jukes-Cantor. Vì thế, ma trận chuyển đổi của những mơ hình đang quan tâm khơng gì khác hơn những ma trận trên nhĩm chúng ta đang xét. 5.3. Biến đổi Fourier Đặt G là nhĩm hữu hạn Abel với phép tốn được viết như là +. Đặt YC=∈{:zz =1} như là vịng trịn đơn vị trên mặt phẳng số phức. Chúng ta thấy rằngYlà một nhĩm Abel với phép tốn nhân thơng thường của số phức. Những đặc trưng của G là những đồng cấu nhĩm từ G vào Y. Nghĩa là χ :GY→ là một đặc trưng nếu χ()(,gg12+=χ gg 12) cho tất cả gg12, ∈G . Những đặc trưng là nhĩm Abel dưới phép tốn nhân của các hàm. Nhĩm trên được gọi là nhĩm đối ngẫu của nhĩm G và ký hiệu bởi Gˆ . Nhĩm G và Gˆ là một đẳng cấu. Cho g ∈G và χ ∈Gˆ , nn chúng ta ký hiệu 〈χ, g〉 thay cho χ()g . Đối ngẫu trực tiếp tổng G=⊕i=1G là đẳng n cấu Gˆ n dưới phép đẳng cấu cho bởi 〈(χχ , , ),(gg , , )〉= 〈χ , g 〉. 11nn∏i=1 i ˆ Ví dụ: Giả sử rằng GZ=⊕2 Z2. Thì ta cĩ thể viết G = {1,φ ,ψφψ , } , trong đĩ các giá trị 〈χ, g〉 với g ∈ Gvà χ ∈Gˆ cho bởi bảng sau: (0 , 0) (0 , 1) (1 , 0) (1 , 1) 1 1 1 1 1 φ 1 - 1 1 - 1 ψ 1 1 - 1 - 1 φψ 1 - 1 - 1 1 Cho ánh xạ Gf : → Cvà ánh xạ fˆ :Gˆ → Cđược định nghĩa: fˆ(),()χ =∑ 〈gχ 〉 f g g∈ G gọi là biến đổi Fourier của f. Cho hai hàm số f1 và f2 trên G , tính chập f1*f2 của chúng là một ánh xạ mới được định nghĩa như sau: (f1 * f 2 )( g )= ∑ f1 ( h ) f 2 ( g− h ) h∈ G Một số tính chất xung quanh về nhĩm đối ngẫu và biến đổi Fourier như sau: Bổ đề: Cho f1 và f2 là những hàm số trên nhĩm hữu hạn Abel G đến và 1 là hàm hằng. (i) Nhĩm G và nhĩm đối ngẫu Gˆ là đẳng cấu. (ii) Biến đổi Fourier cĩ tính chập đối với phép nhân, nghĩa là Bùi Văn Đồng Trang 40
Phương pháp đại số cho bài tốn ước lượng hợp lý cực đại - Áp dụng trên cây sinh lồi nhỏ ˆˆ f12*()fg= f 1 *f2 (iii) 1(ˆ χ ) = G nếu χ =1 (phần tử đơn vị trong Gˆ ) và 1(ˆ χ )= 0 ngược lại. Ví dụ (Biến đổi Fourier cho những cây đơn giản): Cho TK= 1,n là cây cĩ gốc và n lá. Khả năng xảy ra của mơ hình cơ sở nhĩm được cho bởi: n ()i p( g1 , , gn )= ∑π (h )∏ f ( h− gi ) h∈ G i=1 Chúng ta sẽ biến đổi Fourier đối với những tổ hợp của xác suất trên đối với nhĩm Gn . Để làm điều đĩ, chúng ta thay thế phân bố gốc π :GR→ bởi một hàm số mới π :Gn →nh Rư sau: ⎧π ()h112 nếu hh= == hn π(hh1 , ,n ) = ⎨ ⎩ 0 ngược lại Từ đĩ chúng ta cĩ: n ~ ()i p( g1 , , gn ) = ∑ π (h1 , , hn )∏ f ( hi− g i ) n (h1 , , hn )∈ G i=1 vì thế p là chập của hai hàm số trên Gn . Biến đổi Fourier cho ra: n ~ˆ ˆ ()i q(χ1 , , χn ) = π( χ1 , , χn )∏ f ()χi i=1 bởi cơng thức tính chập là độc lập của f(i) trong biến đổi Fourier. Mặt khác ~ˆ ~ π( χ1 , , χn ) = ∑ n 〈(χ1 , , χn ),(g1 , , gn )〉 .π ( g1 , , gn ) (g1 , , gn )∈ G =∑ g∈ G 〈χ1 χ 2 χn ),g〉 . π ( g ) = πˆ( χ1 χ 2 χn ) cho nên n ˆ ()i q(χ1 , , χn ) = πˆ( χ1 , , χn )∏ f ()χi i=1 Ví dụ trên là cơ sở để giới thiệu sự cần thiết để chứng minh những kết quả tổng quát sau. Định lý ([Evans and Speed, 1993]): Cho p( g1 , , gn ) là phân phối cĩ điều kiện của một mơ hình cơ sở nhĩm đối với cây sinh lồi T được giới thiệu ở phần trên. Thì biến đổi Fourier của p cĩ dạng ˆ ()v q(χ1 , , χn ) = πˆ( χ1 , , χ n ) ∏ f ()∏ χl vv∈ΛV() T)\{ r } l∈ ( với Λ()v là tập của lá cĩ v như là cha. Bùi Văn Đồng Trang 41
Phương pháp đại số cho bài tốn ước lượng hợp lý cực đại - Áp dụng trên cây sinh lồi nhỏ Thay thế tọa độ gốc p bởi tọa độ Fourier q , kết quả của q là các i1 i 2 in i1 i 2 in i1 i 2 in đơn thức của các tham số. 5.4. Toạ độ Fourier Mỗi một tọa độ Fourier của 2n hoặc 4n tọa độ được ký hiệu bởi q . Chú ý, i1 i 2 in với phân phối tại gốc là phân phối đều và mơ hình chúng ta đang xét cĩ cấu trúc nhĩm như Jukes-Cantor hay Kimura-2, Kimura-3, biến đổi Fourier từ p theo q và i1 i 2 in i1 i 2 in ngược lại theo định lý trên (ở phần 5.3) như sau: p = χj1 (i ) χ jn ( i ) q , i1 i 2 in ∑ 1 n j1 jn j1, , jn 1 q = χi1 (j ) χ in ( j ) p . i1 i 2 in n ∑ 1 n j1 jn k j1, , jn Ở đây χ i là đặc trưng của nhĩm kết hợp đến phần tử thứ i của nhĩm. Bảng đặc trưng của nhĩm chúng ta sử dụng là Z2 và ZZ2⊕ 2 sau: A C G T 0 1 A 1 1 1 1 0 1 1 và C 1 - 1 1 - 1 1 1 - 1 G 1 1 - 1 - 1 T 1 - 1 - 1 1 Nĩi cách khác, χ i ()j là chính là phần tử (i, j) tương ứng trong bảng đặc trưng trên. 5.5. Áp dụng tìm bất biến trên một cây sinh lồi 5.5.1. Mơ hình bài tốn Để làm rõ vấn đề trên chúng ta xem xét một cây sinh lồi cụ thể sau: Cho cây sinh lồi cĩ gốc với 3 lá với hình 8 sau: Hình 8: Cây sinh lồi cĩ gốc với 3 nút lá Để đơn giản, giả sử mơ hình chúng ta đang xét là mơ hình Jukes – Cantor với 4 trạng thái. Ngồi ra, các kí tự tại nút gốc cĩ phân phối đều, nĩi cách khác xác suất xuất hiện các ký tự {A, G, C, T} tại gốc là bằng nhau và bằng 0.25. Theo hình dáng cây trên, chúng ta cĩ 3 cạnh bằng nhau, cho nên ma trận xác xuất chuyển đổi như sau: Bùi Văn Đồng Trang 42
Phương pháp đại số cho bài tốn ước lượng hợp lý cực đại - Áp dụng trên cây sinh lồi nhỏ ⎛⎞cccc0111 ⎜⎟cccc c = ⎜⎟1011 ⎜⎟cccc1101 ⎜⎟ ⎝⎠cccc1110 (Với ma trận trên ta cĩ ràng buộc c0+3c1=1). 5.5.2. Các khả năng xảy ra trên các nút lá Như trên, vì cây cĩ 3 lá, nên số trường hợp cĩ thể xảy ra trên lá là 64 khả năng. (Xem Phụ lục 1) 5.5.3. Các lớp xác suất tương đương Trong 64 toạ độ trên, thì chỉ cĩ 4 lớp tương đương sau: Lớp 1 cĩ 4 toạ độ: 13 pp===+ pp c33c AAA GGG CCC TTT 4401 Lớp 2 cĩ 36 tọa độ: pppppppppAAC=== AAG AAT ACA ACC AGA AGG ATA ATT === pCAA pppppp CAC CCA CCG CCT CGC CGG pp CTC CTT ===pppppppppGAA GAG GCC = GCG == GGA GGC === GGT GTG GTT ===pppppTAA TAT TCC == TCT TGG = pppp TGT === TTA TTC TTG 111 =+cc2 ccc23+ 4401 0112 Lớp 3 cĩ 24 tọa độ: pppppppppACG=== ACT AGC AGT ATC ATG CAG CAT CGA === pCGTCTACTGGACGATGCAGCTGTAGT ppp ppp pp C 31 === pppppp ccc23 + TAC TAG TCA TCG TGA TGC 4401 1 Đặt p01,2, pp là tổng các xác suất trong một lớp tương đương trên, ta cĩ: 33 pc00=+3 c1 223 pccccc10101=++99181 23 pcc201=+18 6c1 Vậy ánh xạ chúng ta cần xem xét f : d→ m, trong đĩ: Trong đĩ d = 2 (c0 và c1) và cây cĩ 3 lớp đại diện cho 64 khả năng xảy ra ở các nút lá cho nên m = 3. Bùi Văn Đồng Trang 43
Phương pháp đại số cho bài tốn ước lượng hợp lý cực đại - Áp dụng trên cây sinh lồi nhỏ Vì thế thực tế ánh xạ chúng ta đang xét đĩ là: f : 23→ 5.5.4. Chuyển đổi Fourier Sử dụng cơng thức chuyển đổi Fourier 1 q = χi1 (j ) χ in ( j ) p . i1 i 2 in n ∑ 1 n j1 jn k j1, , jn ta được: 32 2 3 qpppccccccAAA =++=+ 012 092727 01011 + + 111 115 1 qpppccccc=+ =+ 32 2 +c3 AAG 981279901200101 9 31 111 115 1 qpppccccc=+ =+ 32 2 +c3 AAC 9812799012 00101 9 31 111 115 1 qpppccccc=+ =+ 32 2 +c3 AAT 9812799012 00101 9 31 111 115 1 qpppccccc=+ =+ 32 2 +c3 AGA 9812799012 00101 9 31 111 115 1 qpppccccc=+ =+ 32 2 +c3 AGG 9812799012 00101 9 31 1111 1 11 qpppccccc=+=+ 32 23-c AGC 660118 18 2 001012 2 61 1111 1 11 qpppccccc=+=+ 32 23-c AGT 660118 18 2 001012 2 61 111 115 1 qpppccccc=+ =+ 32 2 +c3 ACA 9812799012 00101 9 31 1111 1 11 qpppccccc=+=+ 32 2-c3 ACG 660118 18 2 001012 2 61 111 115 1 qpppccccc=+ =+ 32 2 +c3 ACC 9812799012 00101 9 31 1111 1 11 qpppccccc=+=+ 32 23-c ACT 660118 18 2 001012 2 61 111 115 1 qpppccccc=+ =+ 32 2 +c3 ATA 9812799012 00101 9 31 1111 1 11 qpppccccc=+=+ 32 23-c ATG 660118 18 2 001012 2 61 Bùi Văn Đồng Trang 44
Phương pháp đại số cho bài tốn ước lượng hợp lý cực đại - Áp dụng trên cây sinh lồi nhỏ 1111 1 11 qpppccccc=+=+ 32 23-c ATC 660118 18 2 001012 2 61 111 115 1 qpppccccc=+ = 32 + 2 +c3 ATT 9812799012 00101 9 31 Tất cả q cịn lại đều mang giá trị 0. Các q trên được chia thành 3 lớp tương đương: Lớp 1(cĩ một tọa độ): 32 2 3 qpppcccccAAA =++ 123 =+ 092727 0101 + +c1 Lớp 2 (cĩ 9 tọa độ): qqqAAG=== AAC AAT q AGA = q AGG = q ACA = q ACC = qq ATA = ATT 111 115 1 =+ppp = cccccc32 + 23 + 9812799123 001011 9 3 Lớp 3 (cĩ 6 tọa độ): qqqqqqAGC=== AGT ACG ACT ATG ATC 1111 111 =+=+ p pp ccccc32 23-c 661218 18 3 001012 2 61 Đặt qqq012,, là tổng giá trị của từng lớp tương đương trên, thì 32 2 3 qpppc0012=++=+ 092727 ccccc 0101 + +1 11 qp=+ p p =+ cccccc325 2 +33 1093 1 2 00101 1 11 qp=+=+ p p cccccc3233 2-3 2033 1 2 001011 5.5.5. Kết quả tìm được Bất biến cần tìm là được: 23 qq02-0 q 1= Hay bất biến cần tìm: 11 11 ()(-)-(-)0pppp++ p + p23 p + p p = 012033 1 2 0 93 1 2 8164 8084 4 ⇔+++pp2 pp 2232 pp p pp- pp 23 p =0 327902 01 02 729812727 1 12 12 2 Bùi Văn Đồng Trang 45
Phương pháp đại số cho bài tốn ước lượng hợp lý cực đại - Áp dụng trên cây sinh lồi nhỏ 5.6. Những tính chất của thành phần bất biến Cũng theo các tác giả [Evans and Speed, 1993] thì với phép biến đổi Fourier trên, chúng ta sẽ tìm được tất cả các thành phần bất biến trên cây sinh lồi. Và một điều quan trọng nữa là các thành phần bất biến trên là những đa thức thuần nhất. Thành phần bất biến tầm thường nhất là ∑ pi =1 mà ta đã biết. Những thành phần bất i biến tìm được ở đây là dữ liệu đầu vào để giải trình hợp lý ở chương sau. Bùi Văn Đồng Trang 46
Phương pháp đại số cho bài tốn ước lượng hợp lý cực đại - Áp dụng trên cây sinh lồi nhỏ Chương 6. GIẢI PHƯƠNG TRÌNH HỢP LÝ Chương này đưa ra phương pháp giải phương trình hợp lý dựa vào tính bất biến của cây sinh lồi và mẫu dữ liệu quan sát. 6.1. Quỹ tích hợp lý trên một đa tạp Chúng ta mơ tả một mơ hình thống kê là một tập con của: n+1 Δ=nn{(pp01 , , , p )∈R : pp01 , , , p n> 0 và p0 + p 1 + + pn = 1} giả sử rằng, mơ hình được mơ tả như là một tập nghiệm chứa trong Δn bởi một hệ các phương trình các đa thức thuần nhất với các biến chưa biết pp01, , , pn . Các đa thức được biết như là thành phần bất biến ở chương 5. Gọi V là tập của tất cả nghiệm phức được cho bởi hệ các phương trình đa thức thuần nhất. Vấn đề cực đại hợp lý là tìm những điểm pppp= (01 , , ,n ) ở mơ hình VV>0 = ∩ Δn n+1 mà giải thích hợp lý nhất cho bởi véc tơ dữ liệu (,, ,)uu01 un ∈ . Nghĩa là giải quyết vấn đề tối ưu với ràng buộc sau: u0 u1 un Cực đại hàm hợp lý L = pp01 pn hay bài tốn log tương đương lu=++00log p un log pn với giả thuyết là pV∈ >0 . Tiếp cận của chúng ta là tìm tất cả các điểm tới hạn của hàm hợp lý cực đại L và sau đĩ chọn những nghiệm thực dương, những điểm đĩ là cực trị địa phương. Trong quá trình giải tìm cực đại hàm trên, chúng ta sẽ tìm tất cả điểm tới hạn trên đa tạp phức V. Cho Vsin g ký hiệu những điểm kỳ dị của đa tạp V và tập VVVreg :\= sin g . Đặt P là iđêan trên vành đa thức R[pp01 , , , pn ] được sinh bởi các đa thức được xác định bởi V, hay: RR[Vppp ]= [01 , , ,n ]/ P Định nghĩa: Cho U là một tập mở Vppppreg \( (℘ 01 n∑ i ))của V . Quỹ tích hợp lý Zu là tập các điểm p∈U mà dL = 0 . Iđêan hợp lý Iu ⊂ R[]V là iđêan của tập đĩng của Zu trong V. 6.2. Ma trận Jacobi của các đa thức bất biến 6.2.1. Gradient- Vector vận tốc Cho f : n → khả vi. Khi đĩ gradient của f tại x, được ký hiệu gradf ()x và định nghĩa là vector: Bùi Văn Đồng Trang 47
Phương pháp đại số cho bài tốn ước lượng hợp lý cực đại - Áp dụng trên cây sinh lồi nhỏ ∂ff∂ gradf ()xx= ( (), , ())x ∂∂xx1 n n −1 Với c∈ , tập M c =∈{:()}xfxcf == ()c gọi là mặt mức. Về mặt hình học vector grad f(x) vuơng gĩc với mặt mức của M c tại x. Vậy phương trình mặt phẳng tiếp xúc với M c tại aa= (1 , , an ) là ∂∂ff ()(ax11− a )++ ()( axnn − a ) = 0 ∂∂xx1 n 6.2.2. Ma trận Jacobi của các đa thức bất biến Đặt {gg01 , , , gr } là tập các đa thức thuần nhất được sinh ra bởi iđêan P. Chúng ta mơ tả ma trận Jacobi như sau: ⎡⎤11 1 ⎢⎥∂∂gp ∂∂ gp ∂∂ gp ⎢⎥10 11 1n Jgpgp=∂⎢⎥20 ∂ ∂ 21 ∂ ∂ gp 2 ∂n ⎢⎥ ⎢⎥ ⎢⎥ ⎣⎦∂∂gprr01 ∂∂ gp ∂∂ gp rn và ma trận chuyển vị của J là J T : ⎡⎤1 ∂∂gp10 ∂∂ gp 20 ∂∂ gpr 0 ⎢⎥1 ∂∂gp ∂∂ gp ∂∂ gp J T = ⎢⎥11 21 r 1 ⎢⎥ ⎢⎥ ⎣⎦1 ∂∂gp12nnr ∂∂ gp ∂∂ gpn Chúng ta nhân J bởi ma trận đường chéo các phần tử trên đường chéo là các biến như sau: ⎡ pp01 pn ⎤ ⎢ ⎥ ∂∂gg11 ∂g1 ⎢ pp01 pn ⎥ ⎢ ∂∂p01pp ∂n ⎥ ⎢ ∂∂gg ∂ g⎥ ⎢ 22 2⎥ J== J. diag ( p01 , p , , pn ) pp01 pn ⎢ ∂∂p01pp ∂n ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ∂∂ggrr ∂ gr⎥ ⎢ pp01 pn ⎥ ⎣ ∂∂p00pp ∂n ⎦ Bùi Văn Đồng Trang 48
Phương pháp đại số cho bài tốn ước lượng hợp lý cực đại - Áp dụng trên cây sinh lồi nhỏ 6.2.3. Khơng gian tiếp xúc Vì V là một đa tạp khả vi và p ∈V , tập vector tiếp xúc với M tại p được gọi là khơng gian tiếp xúc với V tại p và ký hiệu TVp thì: n TVpi=∈{: vP v ⊥grad g (),1, , p i = m} n Viết một các khác TVp cho bởi hệ phương trình vJv∈ P :.= 0, hay TVp là Ker của ma trận J trên [Vppp ]= R [01 , , ,n ]/ P. 6.3. Bài tốn cực trị điều kiện Ta cĩ bài tốn tìm cực trị của hàm hợp lý chính là tìm cực trị hàm lV: → . Nĩi cách khác là tìm cực trị của hàm l với điều kiện ràng buộc gg01=== gr 0 . Ta cĩ: uu gradlp( )= (0 , ,n ) p0 pn Điều kiện cần: Nếu l đặt cực trị với ràng buộc gg01= == gr = 0 tại p, thì gradf ()pTV⊥ p suy ra uu0 n vv0 + +n = 0 với vTV∈ p pp0 n n vì pii ≠=0, 0, ,n nên tập các p thuộc tập: ∑uiiφ = 0 với các vector (φ0 , ,φn ) i=0 chạy trên tập Ker của ma trận J trên [Vppp ]= R [01 , , ,n ]/ P Phương pháp nhân tử hố Lagrange: Từ trên, để tìm điểm nghi ngờ cực trị của l với điều kiện gg01=== gr 0 , ta lập hàm Lagrange r+1 L (plpg ,λλλ )=− ( )00 −−∈ rr gpV , ,( λλ0 , ,r ) ∈ r+1 Nếu p là điểm cực trị cĩ điều kiện thì tồn tại (λλ0 , ,r )∈ sao cho (,p λ)là nghiệm của hệ: ⎧∂L (,)p λ = 0 ⎪ ∂p ⎪ ⎨gp0 ()= 0 ⎪ ⎪ ⎩⎪gpr ()= 0 Bùi Văn Đồng Trang 49
Phương pháp đại số cho bài tốn ước lượng hợp lý cực đại - Áp dụng trên cây sinh lồi nhỏ * Điều kiện đủ: Đặt HppL (*,)λ là Hessian của hàm Lagrange L theo biến p. Khi * * đĩ: Nếu HppL (*,)λ xác định âm, thì l đạt cực đại tại p . ( Xem [Tạ Lê Lợi, 2002]) 6.4. Bậc của hợp lý cực đại Bậc hợp lý cực đại của mơ hình thống kê đại số là số điểm tới hạn phức của logarit phương trình hợp lý l đối với vector dữ liệu u ∈ n+1 và nĩ hữu hạn và bị chặn trên theo định lý sau: Định lý: Cho P =〈gg0 , , r 〉 là một iđêan trong [pp0 , ,n ] với gi là đa thức thuần nhất cĩ bậc là di với i= 0, ,r. Thì bậc hợp lý cực đại của P là hữu hạn và bị chặn trên bởi i 0 ii1 r Ddd= ∑ 00 dr ii01+++≤− inrr ii0 >>0, ,r 0 Chứng minh: Xem [Hoşten et al., 2005]. 6.5. Các thuật tốn Từ các phân tích trên ta xây dựng một số thuật tốn sau giải phương trình hợp lý. Thuật tốn 1: (Tính tốn phương trình hợp lý) n+1 Input: Một iđêan thuần nhất Ppp⊂ [0 , ,n ] và một vector u ∈ . Output: Iđêan hợp lý Iu của mơ hình V=υ()P cho dữ liệu u. Bước 1: Tính cn=+−(1)dim( V). Đặt Q là iđêan những quỹ tích điểm kỳ dị của V. Bước 2: Tính Ker M của ma trận J trên [Vppp ]= R [01 , , ,n ]/ P. n ' Bước 3: Đặt Iu là iđêan trong []V sinh bởi đa thức ∑uiiφ = 0, với vector i=0 (φ0 , ,φn ) chạy trên tập M. ' Bước 4: Iđêan Iu bằng Iu loại bỏ đi những điểm kỳ dị. (Chứng minh tính đúng thuật tốn trên: Bước 1, tìm quỹ tích những điểm kỳ dị được chứng minh ở [J.S. Milne, 2005]. Các bước cịn lại cĩ được bởi sự phân tích ở phần đầu chương). Bùi Văn Đồng Trang 50
Phương pháp đại số cho bài tốn ước lượng hợp lý cực đại - Áp dụng trên cây sinh lồi nhỏ Thuật tốn 2: (Tính tốn cực đại địa phương của hàm hợp lý) Input: Iđêan hợp lý Iu của mơ hình V và dữ liệu u. Output: Danh sách của tất cả các cực đại địa phương cho phương trình hợp lý. Bước 1: Nếu dim(Iu )= 0 đối với dữ liệu u, tính ra tập Zu . * Với mỗi một nghiệm dương pZ∈∩u V>0 thực hiện các bước sau: T * * Bước 2: Giải phương trình tuyến tính Jp().λ = u để thu các nhân tử Lagrange λi . * Bước 3: Tính tốn Hessian HppL (*,)λ của hàm L (,)p λ . Bước 4: Nếu HpL (*,)λ* ở bước 3 là xác định âm thì xuất p* với giá trị hàm p lp(*)tương ứng. 6.6. Áp dụng giải phương trình hợp lý Xét ví dụ cây sinh lồi ở chương 5, thành phần bất biến chúng ta tìm được là: 8164 8084 4 gppppppp=+++222322 ppppp-3=0 102010213 27 9 729 81 12122 27 27 và bất biến tầm thường là: gppp0012= ++−=10 hay : 8164 8084 4 I :1=〈ppp + + − ,- pp222322 pppp+ + p pp pp+ p3 〉 u 0123279 02 0102 729812727 1 12 12 2 Giả sử bộ dữ liệu quan sát đếm được cho từng xác suất ppp012,, tương ứng là u = (700,45,49) . Kết quả sau khi chạy thuật tốn 1: Xem phụ lục 2. Kết quả sau khi chạy thuật tốn 2 tìm được số nghiệm của phương trình hợp lý là 5 nghiệm như sau: (0.2474737682, 2.5624447362, -1.8099185045) (0.8289181084, 0.1641242871, 0.0069576045) (0.1469015638, 0.7993903746, 0.0537080615) (-0.0296031392-i*0.2337477875,0.0376058385-i*0.0038708209, 0.9919973007+i*0.2376186084) (-0.0296031392+i*0.2337477875,0.0376058385+i*0.0038708209, 0.9919973007-i*0.2376186084) Trong 5 nghiệm trên cĩ 2 nghiệm thực dương là: Bùi Văn Đồng Trang 51
Phương pháp đại số cho bài tốn ước lượng hợp lý cực đại - Áp dụng trên cây sinh lồi nhỏ (0.8289181084, 0.1641242871, 0.006957604546) (0.1469015638, 0.7993903746, 0.05370806152) Hàm Lagrange tương ứng: L (ppppg ,λ )=++++ 700ln(0120 ) 45ln( ) 49ln( ) λλ01g1 Với nghiệm thứ nhất nhân tử Lagrange tìm được tương ứng là: * * λ0 = 844.4742431640 , λ1 =18.6903667449 Ma trận Hessian tương ứng ⎡-7.000e+02 -3.441e-03 7.832e-02 ⎤ 1 HpL (,) λ = ⎢ -3.441e-03 -4.502e+01 -6.100e-04⎥ p ⎢ ⎥ ppp012 ⎣⎢ 7.832e-02 -6.100e-04 -4.899e+01⎦⎥ Ma trận Hessian trên cho xác định âm, cho nên hàm hợp lý trên đạt giá trị cực đại cục bộ tại điểm trên và giá trị hàm hợp lý tương ứng là: l = -456.0927286 Với nghiệm thứ hai nhân tử Lagrange tìm được tương ứng là: * * λ0 = 4765.0976562500 , λ1 =64.9804763793 Ma trận Hessian tương ứng ⎡-6.999e+02 -3.883e-01 3.407e-01 ⎤ 1 HpL (,) λ = ⎢ -3.883e-01 -4.486e+01 -7.124e-02⎥ p ⎢ ⎥ ppp012 ⎣⎢ 3.407e-01 -7.124e-02 -4.904e+01⎦⎥ Ma trận Hessian trên cũng cho xác định âm, cho nên hàm hợp lý trên đạt giá trị cực đại cục bộ tại điểm trên và giá trị hàm hợp lý tương ứng là: l = -1495.955966 Với 2 kết quả trên ta cĩ thể kết luận, hàm hợp lý đạt giá trị cực đại tồn cục tại p = (0.8289181084, 0.1641242871, 0.0069576045) và giá trị hàm hợp lý tương ứng là l = -456.0927286 . Kết quả chương trình với số cây khác xem phụ lục 4. Vì chúng ta xử lý bài tốn trên những xác suất nên độ chính xác là cần thiết, vì thế độ dài phần lẻ được lấy ở chương trình là 10 con số. Và chương 7 sẽ cho chúng ta một cái nhìn tổng quan hơn về chương trình thực hiện giải phương trình hợp lý - áp dụng trên cây sinh lồi. Bùi Văn Đồng Trang 52
Phương pháp đại số cho bài tốn ước lượng hợp lý cực đại - Áp dụng trên cây sinh lồi nhỏ Chương 7. CHƯƠNG TRÌNH THỰC HIỆN 7.1. Sơ đồ khối chương trình Begin Input: Các chuỗi DNA N := Số cây sinh lồi được tạo ra từ các chuỗi trên i: = 1 Tính các lớp tương đương trên cây i Tính các thành phần bất biến của cây i Tính vector u từ các chuỗi Giải phương trình hợp lý i<N Output: Cây sinh lồi cĩ hàm hợp lý lớn nhất End Hình 9: Sơ đồ khối chương trình tìm cấu trúc cây sinh lồi Bùi Văn Đồng Trang 53
Phương pháp đại số cho bài tốn ước lượng hợp lý cực đại - Áp dụng trên cây sinh lồi nhỏ 7.2. Sơ lược về chương trình Bài tốn trên được chia thành nhiều bài tốn nhỏ tách rời nhau. Vì thế để chọn một ngơn ngữ lập trình phù hợp của từng cơng đoạn cũng cần được tính đến. Trong luận văn này, hai ngơn ngữ được chọn để viết và kiểm nghiệm đĩ là ngơn ngữ C++ và Singular. Gĩi phần mềm viết bằng C++ giải quyết phần đầu bài tốn là xác định các xác suất xảy ra trên cây và đếm số lượng các vector dữ liệu u. Phần quan trọng nhất của chương trình là tìm các thành phần bất biến và giải phương trình hợp lý được viết trên ngơn ngữ Singular (Xem phụ lục 3). Singular là một hệ thống các phương pháp tính tốn đa thức, đại số giao hốn và hình học đại số. Nĩ là một gĩi phần mềm rất hữu hiệu cho đại số thống kê. 7.3. Kết quả chương trình Xét cây sinh lồi cĩ gốc với 3 taxa, dữ liệu tương ứng với mỗi lá ở đây là những gen cĩ tên là HIVenvSweden (dữ liệu lấy ở [Yang, Z. 1997]) cĩ chiều dài 273 ký tự như sau: U68496:=GTAGTAATTAGATCTGAAAACTTCACGAACAATGCTAAAACCAT AATAGTACAGCTAAATAAATCTGTAGAAATTAATTGTGTAAGACCCGGCA ACAATACAAGAAGAAGTATACATATAGGACCAGGGAGAGCATATTATACA GGAGAAGTAATAGGAGATATAAGACAAGCACATTGTAACCTTAGTAGAAC AGACTGGAATAAAACTTTAAAACAGGTAGCTGAAAAATTAAGAGAACAAT TTAATACAACAATAGTCTTTAATCAATCC U68497:=GTAGTAATTAGATCTGAAAACTTCTCGAACAATGCTAAAACCATA ATAGTACAGCTAAATAAATCTGTAGAAATTAATTGTACAAGACCCAACAA CAATACAAGAAGAAGTATACATTTTGGACCAGGGAAAGCATTTTATGCAG GAGAAATAATAGGAGATATAAGACAAGCATATTGTACCCTTAATGGAACA GAATGGAATAACACTTTAAAACAGGTAGCTGAAAAATTAAGAGAACAATT TATTAAAACAATAGTTTTTAATCAATCC U68498:=ATAGTAATTAGATCTGAAAACTTCTCGAACAATGCTAAAACCATA ATAGTACAGCTAAATAAATCTGTAGAAATTAATTGTACAAGACCCAACAA CAATACAAGAAGAAGTATACATTTCGGACCAGGGAAAGCATTTTATGCAG GAGAAATAATAGGAGATATAAGACAAGCATATTGTACTCTTAATGGAGCA GAATGGAATAACACTGTAAAACAGGTAGCTGCAAAATTAAGAGAACAATT TAATAAAACAATAATCTTTAATCAATCC Bùi Văn Đồng Trang 54
Phương pháp đại số cho bài tốn ước lượng hợp lý cực đại - Áp dụng trên cây sinh lồi nhỏ Với 3 gen này mục đích chúng ta là tìm mối liên hệ tổ tiên giữa chúng. Cĩ 2 dạng cây 3 taxa cĩ gốc như hình 10. Cây 3 taxa hình mĩng Cây3 taxa hình lược Hình 10: Hai hình dạng cây 3 taxa cĩ gốc Ta chọn mơ hình Jukes – Cantor cho bài tốn này. Với Cây hình mĩng: Chỉ cĩ một trường hợp duy nhất, dữ liệu quan sát khi so dĩng trên từng cột như Bảng 2. 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) A A A A A A A A G G G C C C C C T T T Các A A G G C C C T A A G A C C T T G C T mẫu A T A G A C T T A G G A C T C T T C T Số 113 1 1 2 1 2 1 3 6 2 39 2 34 1 1 1 1 1 61 lượng Cây này cĩ 3 lớp tương đương, số lượng từng lớp trên dữ liệu là u=(247, 25, 1), khi chạy chương trình cho kết quả: p= (0.903285626594, 0.094557322708, 0.00215705069738) và giá trị hàm hợp lý tương ứng lp()= -90.22670674 Với Cây hình lược: Cĩ 4 lớp xác suất tương đương và 3 trường hợp xảy ra: Trường hợp 1: Các nút cây tương ứng (U68496,(U68496, U68496)) và số lượng các mẫu dữ liệu quan sát khi so dĩng trên từng cột đối với trường hợp này ở bảng 3. 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)) A A A A A A A A G G G C C C C C T T T Các A A G G C C C T A A G A C C T T G C T mẫu A T A G A C T T A G G A C T C T T C T Số 113 1 1 2 1 2 1 3 6 2 39 2 34 1 1 1 1 1 61 lượng Bùi Văn Đồng Trang 55
Phương pháp đại số cho bài tốn ước lượng hợp lý cực đại - Áp dụng trên cây sinh lồi nhỏ Vector dữ liệu tương ứng là: u = (247, 8, 17, 1) và kết quả khi chạy chương trình: p =(0.9027837320165, 0.03154973251390, 0.0640321523858, 0.001634383083735) và giá trị hàm lp( )= -106.0495469 Trường hợp 2: Các nút cây tương ứng (U68497,(U68496, U68498)) và số lượng các mẫu dữ liệu quan sát khi so dĩng trên từng cột đối với trường hợp này giống như bảng 2, vì thế tương tự như trường hợp 1. Trường hợp 3: Các nút cây tương ứng (U68498,(U68496, U68497)) và số lượng các mẫu dữ liệu quan sát khi so dĩng trên từng cột đối với trường hợp này trên bảng 4. 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)) A A A A A G G G G C C C C C C T T T T Các A A A G T A G G G A C C C T T C T T T mẫu A G C G A A A G T A A C T A C C A C T Số 113 6 2 2 1 1 2 39 1 1 2 34 1 1 1 1 3 1 61 lượng Vector dữ liệu tương ứng u = (247, 19, 6, 1), kết quả khi chạy chương trình: p =(0.9032484236332, 0.07179349581611, 0.0228400591792, 0.0021180213714) và giá trị hàm lp( )= -104.0121158 Với kết quả trên thì ta thấy với trường hợp cây sinh lồi thứ 2 thì các dữ liệu trên đựợc gán cho cây với thứ tự ((U68498,(U68496, U68497)) là “hợp lý” nhất. Xét về cây thì cây sinh lồi giải thích tốt nhất cho dữ liệu trên là cây sinh lồi hình lược, vì nĩ cĩ hàm hợp lý cho kết quả lớn nhất. Bùi Văn Đồng Trang 56
Phương pháp đại số cho bài tốn ước lượng hợp lý cực đại - Áp dụng trên cây sinh lồi nhỏ Chương 8. TỔNG KẾT – ĐÁNH GIÁ Chương này tổng kết lại những cơng việc đã làm được, sau đĩ nêu ra những đĩng gĩp và hướng phát triển của luận văn. 8.1. Tổng kết Luận văn đã nghiên cứu đến một lãnh vực đang được rất nhiều người quan tâm trong giai đoạn hiện nay. Luận văn cho ta một cái nhìn tổng thể về cây sinh lồi và phương pháp để giải phương trình hợp lý, cũng như cách mơ hình hĩa bài tốn và chọn phương pháp và giải quyết bài tốn. Trong đĩ phương pháp được chọn là phương pháp đại số nĩi chung và đại số máy tính nĩi riêng. Ngồi ra, luận văn cũng cung cấp một gĩi phần mềm được sử dụng như là kiểm nghiệm những lý thuyết đưa ra. Vì kiến thức cũng như thời gian cĩ hạn nên luận văn cĩ nhiều khiếm khuyết như nội dung luận văn chưa được cơ đọng, phần chương trình kiểm nghiệm các mơ đun chưa tích hợp được các phần lại với nhau. Hạn chế lớn nhất phải kể đến là chương trình chỉ chạy được trên cây sinh lồi 3 taxa, cịn trường hợp 4 và 5 taxa chỉ chạy được ở những mơ hình đơn giản. 8.2. Những đĩng gĩp của luận văn - Đối với bản thân qua luận văn này đã thu thập kiến thức cơ bản về sinh học nĩi chung và việc nghiên cứu tiến hố hiện nay nĩi riêng. Cũng qua luận văn này đã bổ sung cho tơi kiến thức về tốn học, xác suất thống kê và nhất là đại số máy tính. - Luận văn này như là một tài liệu tham khảo ban đầu cho những ai quan tâm đến lãnh vực tính tốn thống kê về sinh học phân tử, về cây tiến hĩa. Ngồi ra cũng là tài liệu bổ ích cho một cái nhìn tổng quan về phương pháp ước lượng hợp lý cực đại và cách giải chúng bằng phương pháp đại số. Những lãnh vực được đề cập trong luận văn này đang được quan tâm và phát triển mạnh trên thế giới trong những năm gần đây. Bùi Văn Đồng Trang 57
Phương pháp đại số cho bài tốn ước lượng hợp lý cực đại - Áp dụng trên cây sinh lồi nhỏ 8.3. Hướng phát triển Với những hạn chế đã nêu ở trên, hướng phát triển luận văn đưa ra chủ yếu là khắc phục những nhược điểm là làm sao để giải bài tốn trên những cây sinh lồi lớn hơn: - Cải tiến các thuật tốn để cĩ thể chạy tốt hơn. - Song song hĩa để giải bài tốn ước lượng hợp lý cực đại. - Một hướng khác cũng nên quan tâm là nghiên cứu đặc tính của từng cây cụ thể và tập trung giải quyết bài tốn trên những cây riêng biệt đĩ. Bùi Văn Đồng Trang 58
Phương pháp đại số cho bài tốn ước lượng hợp lý cực đại - Áp dụng trên cây sinh lồi nhỏ TÀI LIỆU THAM KHẢO [Hồng Xuân Sính, Hồng Xuân Sinh. Đại số đại cương. Nhà xuất bản GD, 2003. 2003] [Đào Hữu Hồ, 2002] Đào Hữu Hồ. Xác suất thống kê. Nhà xuất KHKT, 2002. [Tạ Lê Lợi, 2002] Tạ Lê Lợi. Giải Tích – Giáo trình cử nhân tốn. Đại học Đà Lạt, 2002. [Benny Chor, 2005] Maximum likelihood Jukes-Cantor Triplets: Analytic Solutions. arXiv: q-bio.PE/0505054 v1 27 May 2005 [B. Chor, M. Hendy, B. Multiple maxima of likelihood in phylogenetic trees: An analytic Holland, and D. Penny, approach. MBE, 17(10):1529–1541, 2000. Earlier version appeared in 2000] RECOMB 2000. [Catanese et al., 2005] F Catanese, S Ho¸sten, A Khetan, and B Sturmfels. The maximum likelihood degree. American Journal of Mathematics, 2005. To appear. Cited on p. 10, 106 [Evans and Steven N.Evans and Speed. Invariants of some probability models used Speed,1993] in phylogenetic inference. The Annals of Statistics 1993, vol. 21, No. 1, 355-377. [Hoşten et al., 2005] S Hoşten, A Khetan, and B Sturmfels. Solving the likelihood equations. Foundations of Computational Mathematics, 2005. To appear. Cited on p. 108, 335, 343, 344 [J.S. Milne, 2005] J.S. Milne. Algebraic Geometry. Taiaroa Publishing Erehwon. Version 5.00. February 20,2005 [Lior Pachter and Lior Pachter and Bernd Sturmfels. Algebraic Statistics for Bernd Sturmfels, 2005] Computational Biology. Cambridge University Press 2005. [Luis D. Garcia, 2006] Luis David Garcia. Small Phylogennetic Trees. [Melvyn B. Melvyn B. Nathanson. Elementary Methods in Number Theory . Nathanson,1999] Springer, 1999. [Nguyen V.M. Nguyen V.M. Man. Computational Algebraic Statistics(CAS). Man,2007] [Sturmfels and Bernd Sturmfels and Seth Sullivant. Toric Ideals of Phylogenetic Sullivant, 2005] Invariants. [Yang, Z. 1997] Ziheng Yang. A program package for phylogenetic analysis by maximum likelihood. Computer Applications in BioSciences 13:555- 556 Bùi Văn Đồng Trang 59
Phương pháp đại số cho bài tốn ước lượng hợp lý cực đại - Áp dụng trên cây sinh lồi nhỏ Phụ lục 1. Tập các xác suất trình bày ở chương 5 pAAA=1/4*c0*c0*c0+1/4*c1*c1*c1+1/4*c1*c1*c1+1/4*c1*c1*c1=1/4*c0^3+3/4*c1^3, pAAG=1/4*c0*c1*c0+1/4*c1*c0*c1+1/4*c1*c1*c1+1/4*c1*c1*c1=1/4*c0^2*c1+1/4*c0*c1^2+1/2*c1^3, pAAC=1/4*c0*c1*c0+1/4*c1*c1*c1+1/4*c1*c0*c1+1/4*c1*c1*c1=1/4*c0^2*c1+1/4*c0*c1^2+1/2*c1^3, pAAT=1/4*c0*c1*c0+1/4*c1*c1*c1+1/4*c1*c1*c1+1/4*c1*c0*c1=1/4*c0^2*c1+1/4*c0*c1^2+1/2*c1^3, pAGA=1/4*c1*c0*c0+1/4*c0*c1*c1+1/4*c1*c1*c1+1/4*c1*c1*c1=1/4*c0^2*c1+1/4*c0*c1^2+1/2*c1^3, pAGG=1/4*c1*c1*c0+1/4*c0*c0*c1+1/4*c1*c1*c1+1/4*c1*c1*c1=1/4*c0^2*c1+1/4*c0*c1^2+1/2*c1^3, pAGC=1/4*c1*c1*c0+1/4*c0*c1*c1+1/4*c1*c0*c1+1/4*c1*c1*c1=3/4*c0*c1^2+1/4*c1^3, pAGT=1/4*c1*c1*c0+1/4*c0*c1*c1+1/4*c1*c1*c1+1/4*c1*c0*c1=3/4*c0*c1^2+1/4*c1^3, pACA=1/4*c1*c0*c0+1/4*c1*c1*c1+1/4*c0*c1*c1+1/4*c1*c1*c1=1/4*c0^2*c1+1/4*c0*c1^2+1/2*c1^3, pACG=1/4*c1*c1*c0+1/4*c1*c0*c1+1/4*c0*c1*c1+1/4*c1*c1*c1=3/4*c0*c1^2+1/4*c1^3, pACC=1/4*c1*c1*c0+1/4*c1*c1*c1+1/4*c0*c0*c1+1/4*c1*c1*c1=1/4*c0^2*c1+1/4*c0*c1^2+1/2*c1^3, pACT=1/4*c1*c1*c0+1/4*c1*c1*c1+1/4*c0*c1*c1+1/4*c1*c0*c1=3/4*c0*c1^2+1/4*c1^3, pATA=1/4*c1*c0*c0+1/4*c1*c1*c1+1/4*c1*c1*c1+1/4*c0*c1*c1=1/4*c0^2*c1+1/4*c0*c1^2+1/2*c1^3, pATG=1/4*c1*c1*c0+1/4*c1*c0*c1+1/4*c1*c1*c1+1/4*c0*c1*c1=3/4*c0*c1^2+1/4*c1^3, pATC=1/4*c1*c1*c0+1/4*c1*c1*c1+1/4*c1*c0*c1+1/4*c0*c1*c1=3/4*c0*c1^2+1/4*c1^3, pATT=1/4*c1*c1*c0+1/4*c1*c1*c1+1/4*c1*c1*c1+1/4*c0*c0*c1=1/4*c0^2*c1+1/4*c0*c1^2+1/2*c1^3, pGAA=1/4*c0*c1*c0+1/4*c1*c1*c1+1/4*c1*c0*c1+1/4*c1*c1*c1=1/4*c0^2*c1+1/4*c0*c1^2+1/2*c1^3, pGAG=1/4*c0*c1*c0+1/4*c1*c0*c1+1/4*c1*c1*c1+1/4*c1*c1*c1=1/4*c0^2*c1+1/4*c0*c1^2+1/2*c1^3, pGAC=1/4*c1*c1*c0+1/4*c1*c1*c1+1/4*c1*c0*c1+1/4*c0*c1*c1=3/4*c0*c1^2+1/4*c1^3, pGAT=1/4*c1*c1*c0+1/4*c1*c1*c1+1/4*c1*c0*c1+1/4*c0*c1*c1=3/4*c0*c1^2+1/4*c1^3, pGGA=1/4*c1*c0*c0+1/4*c0*c1*c1+1/4*c1*c1*c1+1/4*c1*c1*c1=1/4*c0^2*c1+1/4*c0*c1^2+1/2*c1^3, pGGG=1/4*c0*c0*c0+1/4*c1*c1*c1+1/4*c1*c1*c1+1/4*c1*c1*c1=1/4*c0^3+3/4*c1^3, pGGC=1/4*c0*c1*c0+1/4*c1*c1*c1+1/4*c1*c0*c1+1/4*c1*c1*c1=1/4*c0^2*c1+1/4*c0*c1^2+1/2*c1^3, pGGT=1/4*c0*c1*c0+1/4*c1*c1*c1+1/4*c1*c0*c1+1/4*c1*c1*c1=1/4*c0^2*c1+1/4*c0*c1^2+1/2*c1^3, pGCA=1/4*c1*c1*c0+1/4*c1*c0*c1+1/4*c0*c1*c1+1/4*c1*c1*c1=3/4*c0*c1^2+1/4*c1^3, pGCG=1/4*c0*c1*c0+1/4*c1*c1*c1+1/4*c1*c0*c1+1/4*c1*c1*c1=1/4*c0^2*c1+1/4*c0*c1^2+1/2*c1^3, pGCC=1/4*c1*c1*c0+1/4*c1*c1*c1+1/4*c0*c0*c1+1/4*c1*c1*c1=1/4*c0^2*c1+1/4*c0*c1^2+1/2*c1^3, pGCT=1/4*c1*c1*c0+1/4*c1*c1*c1+1/4*c0*c1*c1+1/4*c1*c0*c1=3/4*c0*c1^2+1/4*c1^3, pGTA=1/4*c1*c1*c0+1/4*c1*c0*c1+1/4*c0*c1*c1+1/4*c1*c1*c1=3/4*c0*c1^2+1/4*c1^3, pGTG=1/4*c0*c1*c0+1/4*c1*c1*c1+1/4*c1*c0*c1+1/4*c1*c1*c1=1/4*c0^2*c1+1/4*c0*c1^2+1/2*c1^3, pGTC=1/4*c1*c1*c0+1/4*c1*c1*c1+1/4*c1*c0*c1+1/4*c0*c1*c1=3/4*c0*c1^2+1/4*c1^3, pGTT=1/4*c1*c1*c0+1/4*c1*c1*c1+1/4*c1*c1*c1+1/4*c0*c0*c1=1/4*c0^2*c1+1/4*c0*c1^2+1/2*c1^3, pCAA=1/4*c0*c1*c0+1/4*c1*c1*c1+1/4*c1*c0*c1+1/4*c1*c1*c1=1/4*c0^2*c1+1/4*c0*c1^2+1/2*c1^3, pCAG=1/4*c1*c1*c0+1/4*c1*c0*c1+1/4*c0*c1*c1+1/4*c1*c1*c1=3/4*c0*c1^2+1/4*c1^3, pCAC=1/4*c0*c1*c0+1/4*c1*c1*c1+1/4*c1*c0*c1+1/4*c1*c1*c1=1/4*c0^2*c1+1/4*c0*c1^2+1/2*c1^3, pCAT=1/4*c1*c1*c0+1/4*c1*c1*c1+1/4*c1*c0*c1+1/4*c0*c1*c1=3/4*c0*c1^2+1/4*c1^3, Bùi Văn Đồng Trang 60
Phương pháp đại số cho bài tốn ước lượng hợp lý cực đại - Áp dụng trên cây sinh lồi nhỏ pCGA=1/4*c1*c1*c0+1/4*c1*c0*c1+1/4*c0*c1*c1+1/4*c1*c1*c1=3/4*c0*c1^2+1/4*c1^3, pCGG=1/4*c1*c1*c0+1/4*c0*c0*c1+1/4*c1*c1*c1+1/4*c1*c1*c1=1/4*c0^2*c1+1/4*c0*c1^2+1/2*c1^3, pCGC=1/4*c0*c1*c0+1/4*c1*c1*c1+1/4*c1*c0*c1+1/4*c1*c1*c1=1/4*c0^2*c1+1/4*c0*c1^2+1/2*c1^3, pCGT=1/4*c1*c1*c0+1/4*c0*c1*c1+1/4*c1*c1*c1+1/4*c1*c0*c1=3/4*c0*c1^2+1/4*c1^3, pCCA=1/4*c1*c0*c0+1/4*c1*c1*c1+1/4*c0*c1*c1+1/4*c1*c1*c1=1/4*c0^2*c1+1/4*c0*c1^2+1/2*c1^3, pCCG=1/4*c0*c1*c0+1/4*c1*c1*c1+1/4*c1*c0*c1+1/4*c1*c1*c1=1/4*c0^2*c1+1/4*c0*c1^2+1/2*c1^3, pCCC=1/4*c0*c0*c0+1/4*c1*c1*c1+1/4*c1*c1*c1+1/4*c1*c1*c1=1/4*c0^3+3/4*c1^3, pCCT=1/4*c0*c1*c0+1/4*c1*c1*c1+1/4*c1*c0*c1+1/4*c1*c1*c1=1/4*c0^2*c1+1/4*c0*c1^2+1/2*c1^3, pCTA=1/4*c1*c1*c0+1/4*c1*c0*c1+1/4*c0*c1*c1+1/4*c1*c1*c1=3/4*c0*c1^2+1/4*c1^3, pCTG=1/4*c1*c1*c0+1/4*c1*c0*c1+1/4*c1*c1*c1+1/4*c0*c1*c1=3/4*c0*c1^2+1/4*c1^3, pCTC=1/4*c0*c1*c0+1/4*c1*c1*c1+1/4*c1*c0*c1+1/4*c1*c1*c1=1/4*c0^2*c1+1/4*c0*c1^2+1/2*c1^3, pCTT=1/4*c1*c1*c0+1/4*c1*c1*c1+1/4*c1*c1*c1+1/4*c0*c0*c1=1/4c0^2*c1+1/4*c0*c1^2+1/2*c1^3, pTAA=1/4*c0*c1*c0+1/4*c1*c1*c1+1/4*c1*c0*c1+1/4*c1*c1*c1=1/4*c0^2*c1+1/4*c0*c1^2+1/2*c1^3, pTAG=1/4*c1*c1*c0+1/4*c1*c0*c1+1/4*c0*c1*c1+1/4*c1*c1*c1=3/4*c0*c1^2+1/4*c1^3, pTAC=1/4*c1*c1*c0+1/4*c1*c1*c1+1/4*c1*c0*c1+1/4*c0*c1*c1=3/4*c0*c1^2+1/4*c1^3, pTAT=1/4*c0*c1*c0+1/4*c1*c1*c1+1/4*c1*c1*c1+1/4*c1*c0*c1=1/4*c0^2*c1+1/4*c0*c1^2+1/2*c1^3, pTGA=1/4*c1*c1*c0+1/4*c1*c0*c1+1/4*c0*c1*c1+1/4*c1*c1*c1=3/4*c0*c1^2+1/4*c1^3, pTGG=1/4*c1*c1*c0+1/4*c0*c0*c1+1/4*c1*c1*c1+1/4*c1*c1*c1=1/4*c0^2*c1+1/4*c0*c1^2+1/2*c1^3, pTGC=1/4*c1*c1*c0+1/4*c0*c1*c1+1/4*c1*c0*c1+1/4*c1*c1*c1=3/4*c0*c1^2+1/4*c1^3, pTGT=1/4*c0*c1*c0+1/4*c1*c1*c1+1/4*c1*c0*c1+1/4*c1*c1*c1=1/4*c0^2*c1+1/4*c0*c1^2+1/2*c1^3, pTCA=1/4*c1*c1*c0+1/4*c1*c0*c1+1/4*c0*c1*c1+1/4*c1*c1*c1=3/4*c0*c1^2+1/4*c1^3, pTCG=1/4*c1*c1*c0+1/4*c1*c0*c1+1/4*c0*c1*c1+1/4*c1*c1*c1=3/4*c0*c1^2+1/4*c1^3, pTCC=1/4*c1*c1*c0+1/4*c1*c1*c1+1/4*c0*c0*c1+1/4*c1*c1*c1=1/4*c0^2*c1+1/4*c0*c1^2+1/2*c1^3, pTCT=1/4*c0*c1*c0+1/4*c1*c1*c1+1/4*c1*c0*c1+1/4*c1*c1*c1=1/4*c0^2*c1+1/4*c0*c1^2+1/2*c1^3, pTTA=1/4*c1*c0*c0+1/4*c1*c1*c1+1/4*c1*c1*c1+1/4*c0*c1*c1=1/4*c0^2*c1+1/4*c0*c1^2+1/2*c1^3, pTTG=1/4*c0*c1*c0+1/4*c1*c1*c1+1/4*c1*c0*c1+1/4*c1*c1*c1=1/4*c0^2*c1+1/4*c0*c1^2+1/2*c1^3, pTTC=1/4*c0*c1*c0+1/4*c1*c1*c1+1/4*c1*c0*c1+1/4*c1*c1*c1=1/4*c0^2*c1+1/4*c0*c1^2+1/2*c1^3, pTTT=1/4*c0*c0*c0+1/4*c1*c1*c1+1/4*c1*c1*c1+1/4*c1*c1*c1=1/4*c0^3+3/4*c1^3; Bùi Văn Đồng Trang 61
Phương pháp đại số cho bài tốn ước lượng hợp lý cực đại - Áp dụng trên cây sinh lồi nhỏ 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 c = (n+1) - dim(V) = 2 Q:= M = Ker( J ) := Iu :=<57425888*p1^2 + 60331008*p1*p2 + 5850720*p2^2 - 58311573*p1 - 13781205*p2 + 8050185, 43118186428457088*p2^3 - 135923428146969968*p1*p2 - 88536193620103176*p2^2 + 5367437095038981*p1 + 53799892346655045*p2 – 1095761223392121, 28745457618971392*p1*p2^2 + Bùi Văn Đồng Trang 62