Báo cáo Nghiên cứu một số giải pháp gom cụm dữ liệu trình tự sinh học metagenomic (Phần 1)

Nội dung text: Báo cáo Nghiên cứu một số giải pháp gom cụm dữ liệu trình tự sinh học metagenomic (Phần 1)

1. BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT THÀNH PHỐ HỒ CHÍ MINH CÔNG TRÌNH NGHIÊN CỨU KHOA HỌC CẤP TRƯỜNG NGHIÊN CỨU MỘT SỐ GIẢI PHÁP GOM CỤM DỮ LIỆU TRÌNH TỰ SINH HỌC METAGENOMIC MÃ SỐ: T2013-43 S K C0 0 5 4 2 9 Tp. Hồ Chí Minh, 2013
2. BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT THÀNH PHỐ HỒ CHÍ MINH BÁO CÁO TỔNG KẾT ĐỀ TÀI KH&CN CẤP TRƯỜNG NGHIÊN CỨU MỘT SỐ GIẢI PHÁP GOM CỤM DỮ LIỆU TRÌNH TỰ SINH HỌC METAGENOMIC Mã số: T2013-43 Chủ nhiệm đề tài: GV. ThS. Lê Văn Vinh TP. HCM, 12/2013
3. TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT THÀNH PHỐ HỒ CHÍ MINH KHOA CÔNG NGHỆ THÔNG TIN BÁO CÁO TỔNG KẾT ĐỀ TÀI KH&CN CẤP TRƯỜNG NGHIÊN CỨU MỘT SỐ GIẢI PHÁP GOM CỤM DỮ LIỆU TRÌNH TỰ SINH HỌC METAGENOMIC Mã số: T2013-43 Chủ nhiệm đề tài: GV. ThS. Lê Văn Vinh TP. HCM, 12/2013
4. Mục lục 1 CÁC KIẾN THỨC CƠ SỞ 9 1.1 Bài toán phân loại trình tự metagenomic . . . . . . . . . . . 10 1.2 Quy trình xử lý dữ liệu metagenomic . . . . . . . . . . . . . . 11 1.2.1 Thu thập mẫu thực nghiệm . . . . . . . . . . . . . . . 11 1.2.2 Xác định trình tự . . . . . . . . . . . . . . . . . . . . . 12 1.2.3 Phân tích dữ liệu . . . . . . . . . . . . . . . . . . . . . 13 2 TỔNG QUAN GIẢI PHÁP GOM CỤM TRÌNH TỰ METAGE- NOMIC 15 2.1 Định nghĩa bài toán . . . . . . . . . . . . . . . . . . . . . . . . 15 2.2 Các giải pháp gom cụm . . . . . . . . . . . . . . . . . . . . . . 16 2.2.1 Phương pháp sử dụng giải thuật k-means . . . . . . . 16 2.2.2 Phương pháp dựa trên mô hình . . . . . . . . . . . . . 17 2.2.3 Phương pháp dựa trên đồ thị . . . . . . . . . . . . . . 18 2.3 Đặc trưng sử dụng cho bài toán gom cụm trình tự . . . . . . 19 2.3.1 Dấu hiệu hệ gien . . . . . . . . . . . . . . . . . . . . . 19 2.3.2 Một số tính chất dựa trên quan sát của trình tự DNA 25 1
5. 3 BÀI TOÁN GOM CỤM DỰA TRÊN SỰ PHONG PHÚ CỦA HỆ GIEN 27 3.1 Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.2 Ứng dụng gom cụm trình tự metagenomic dựa trên sự phong phú của hệ gien . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.2.1 Bước 1: Đếm l-mers . . . . . . . . . . . . . . . . . . . 30 3.2.2 Bước 2: Gom cụm các l-mer . . . . . . . . . . . . . . . 30 3.2.3 Bước 3: Gán trình tự vào các cụm . . . . . . . . . . . 31 3.3 Kết quả thực nghiệm . . . . . . . . . . . . . . . . . . . . . . . 32 4 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN 36 2
6. Danh sách hình vẽ 1.1 Quy trình xử lý của một dự án trong lĩnh vực metagenomics (Tham khảo [30]) . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.1 Tỉ lệ lẻ các cặp nucleotide của 20 trình tự ngẫu nhiên độ dài 50 kbp từ hệ gien của hai loài: Neisseriameningitidis và aquifexaeolicus. [18] . . . . . . . . . . . . . . . . . . . . . . . . 22 2.2 Hình ảnh 3 chiều và 2 chiều của tần số 7 nucleotides của 4 loài. Độ dài trình tự là 100 kb [4] . . . . . . . . . . . . . . . . 23 2.3 Mức độ sai sót của giá trị tần số các oligonucleotide trong các loài U.urealyticum, C.kroppenstedtil, B.pumilus,và Xautop- tropicus. [18] . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.1 Sự phong phú của hệ gien trong tập dữ liệu metagenomic . . 28 3.2 Gom cụm trình tự dựa trên sự phong phú của hệ gien . . . . 29 3
7. Danh sách bảng 3.1 Hiệu năng của giải pháp . . . . . . . . . . . . . . . . . . . . . 33 3.2 Kết hợp giải pháp cài đặt với MetaCluster 2.0 . . . . . . . . 35 4
8. MỞ ĐẦU 1. Tình hình nghiên cứu trong và ngoài nước Metagenomics là lĩnh vực nhận được rất nhiều sự quan tâm của các nhà nghiên cứu về sinh học cũng như tin sinh học trong những năm gần đây. Trong đó, bài toán gom cụm trình tự sinh học là một trong những vấn đề quan trọng cần giải quyết. Một số giải pháp đã được đề xuất trước đây như: AbundanceBin [36], Scimm [10], MetaCluster ([37], [38], [13], [32], [33]) và giải pháp của Shruthi Prabhakara và cộng sự [21]. Trong giải pháp Scimm, tác giả đề xuất kỹ thuật gom cụm dựa trên mô hình (model-based approach) sử dụng mô hình Markov nội suy (interpolated Markov models). MetaCluster 3.0 cũng như các phiên bản MetaCluster 1.0, 2.0 áp dụng giải thuật k-median trong gom cụm, và chỉ phân loại cho trình tự có độ dài từ 500 bp trở lên (theo thử nghiệm của tác giả). AbundanceBin và giải pháp của Shruthi Prabhakara thực hiện gom cụm trình tự dựa trên mô hình hỗn hợp (mixture model), trong đó sử dụng hàm phân phối xác suất Poisson hay Gaussian. Hai giải pháp này và MetaCluster 4.0, MetaCluster 5.0 có thể áp dụng trong phân loại trình tự ngắn. Ở Việt Nam, lĩnh vực tin sinh học nói chung cũng được quan tâm nghiên 5
9. cứu trong những năm gần đây. Một số nhóm nghiên cứu như: nhóm nghiên cứu về mạng sinh học của Đại học sư phạm Hà nội. Nhóm nghiên cứu cấu trúc RNA của Viện cơ học và Tin học ứng dụng. Lĩnh vực metagenomics cũng đã được áp dụng trong nghiên cứu sinh học của một số tổ chức ở Việt Nam như: Viện Công nghệ Sinh học (thuộc Viện Khoa học và Công nghệ Việt Nam), Viện Khoa học Kỹ thuật Nông nghiệp Việt Nam 2. Tính cấp thiết của đề tài Metagenomics (còn được gọi là environmental genomics hay community genomics) là lĩnh vực nghiên cứu cộng đồng vi sinh vật (microbial commu- nities). Đây được xem là cuộc cách mạng trong lĩnh vực vi sinh. Khác với những nghiên cứu về vi sinh vật truyền thống, các vật liệu di truyền sau khi được thu thập từ môi trường không cần thông qua quá trình nuôi cấy (microbial culture) mà được đưa trực tiếp vào quá trình xác định trình tự để tạo ra dữ liệu trình tự sinh học (gọi là read hay fragment) cho quá trình phân tích. Lĩnh vực nghiên cứu này giúp giải quyết những vấn đề quan trọng trong y học, sinh thái học, khoa học môi trường, nông nghiệp, v.v. . . Bởi vì mẫu DNA sau khi được thu thập từ môi trường thực tế, được đưa trực tiếp vào giai đoạn xác định trình tự. Do đó, dữ liệu trình tự metagenmic thường không chứa trình tự của từng loài vi sinh vật riêng biệt, mà bao gồm trình tự của rất nhiều loài khác nhau (có khi hơn 10.000 loài trong một mẫu [35]. Vì vậy, bài toán phân loại trình tự là một trong những vấn đề quan trọng cần giải quyết khi phân tích dữ liệu metagenomic. Mục tiêu của bài 6
10. toán là phân chia trình tự theo từng nhóm vi sinh vật. Đối với nhà sinh học, bài toán này là cơ sở để họ có thể xác định những nhóm vi sinh vật nào tồn tại trong mẫu thực nghiệm và phát hiện những nhóm vi sinh vật mới. Hơn nữa, từ kết quả phân loại, nhà sinh học có thể thực hiện tiếp những phân tích và xử lý trên trình tự của từng loài vi sinh vật như: xác định vị trí xuất hiện gien, ráp nối trình tự trong cùng hệ gien (gọi là genome). Việc phân loại trình tự có thể sử dụng cơ sở dữ liệu tham khảo (gọi là giải pháp phân loại - classification approaches), hoặc chỉ dựa trên thông tin được rút trích từ chính tập dữ liệu đang được phân tích (gọi là giải pháp gom cụm - cluster approaches). Một tỉ lệ lớn các loài vi sinh vật chưa được biết đến trong môi trường thực tế dẫn đến sự thiếu hiệu quả của các phương pháp phân loại có giám sát. Vì vậy, phương pháp gom cụm (hay phân loại không có giám sát) là một hướng giải quyết phù hợp cho việc phân tích trình tự DNA của các loài vi sinh vật mới 3. Mục tiêu Muc tiêu thực hiện của đề tài bao gồm: - Tìm hiểu các giải pháp gom cụm dữ liệu trình tự sinh học metagenomic - Đánh giá, nhận xét những ưu điểm, khuyết điểm của các nhóm giải pháp. - Xây dựng ứng dụng gom cụm trình tự sinh học metagenomic cơ bản. 7
11. 4. Đối tượng và phạm vi nghiên cứu + Các phần tử cơ bản trong sinh học ở mức độ phân tử: DNA, RNA, protein, gien; các đặc trưng của trình tự sinh học; hệ thống phân loại vi sinh vật; cơ sở dữ liệu sinh học NCBI, KEGG. + Các phương pháp học máy không có giám sát. 5. Nội dung nghiên cứu + Nghiên cứu lý thuyết cơ bản tin sinh học, các phương pháp học máy không có giám sát (unsupervised machine learning). + Tìm hiểu các giải pháp gom cụm dữ liệu metagenomic. + Đánh giá ưu điểm, khuyết điểm của các nhóm giải pháp. + Xây dựng ứng dụng gom cụm trình tự sinh học metagenomic cơ bản. + Viết báo cáo khoa học. 8
12. Chương 1 CÁC KIẾN THỨC CƠ SỞ Vi sinh vật (microbes) là những sinh vật sống rất nhỏ mà mắt thường không nhìn thấy được như: vi khuẩn (bacteria), vi rút (viruses) hay vi khuẩn cổ (archaea). Chúng xuất hiện ở mọi nơi và chiếm đa số trong sự đa dạng sinh học của sự sống [7]. Việc nghiên cứu vi sinh vật có ý nghĩa quan trọng trong nhiều lĩnh vực, bao gồm: y học, nông nghiệp, công nghệ sinh học, nghiên cứu năng lượng thay thế, môi trường [35]. Một số nghiên cứu đầu tiên về vi sinh vật là vào khoảng những năm 1970, khi hệ gien của một số vi sinh vật được xác định trình tự ([5], [24]). Trong phương pháp nghiên cứu vi sinh vật truyền thống (gọi là microbial genomics), nhà sinh học sau khi lấy mẫu thực nghiệm từ môi trường thực tế sẽ thực hiện nuôi cấy và phân tách theo từng loài vi sinh vật trước khi mang đi xác định trình tự. Sau đó, trình tự sinh học của từng loài vi sinh vật được đưa vào giai đoạn phân tích dữ liệu. Tuy nhiên, trở ngại của phương pháp này là một số lượng rất lớn các vi sinh vật (hơn 99%) không thể nuôi cấy và 9
13. phân tách trong phòng thí nghiệm [7]. Vì vậy, chỉ một tỉ lệ nhỏ các vi sinh vật có thể được phát hiện và nghiên cứu. Một hướng tiếp cận khác trong nghiên cứu vi sinh vật ra đời và thay thế cho phương pháp nghiên cứu truyền thống, gọi là metagenomics. Theo hướng này, mẫu thực nghiệm sau khi được thu thập từ môi trường, không cần trải qua giai đoạn nuôi cấy và phân tách trong phòng thí nghiệm, mà được đưa trực tiếp vào quá trình xác định trình tự sinh học. Những vấn đề trong lĩnh vực metagenomics bắt đầu được tập trung nghiên cứu từ năm 2007 với sự ra đời của dự án nghiên cứu vi sinh vật trong cơ thể con người [31]. Tiếp theo đó, hàng trăm dự án nghiên cứu vi sinh vật khác cho các môi trường khác nhau (như môi trường đất, nước biển) ra đời trên thế giới [39]. Đồng thời, nhiều bài toán cần giải quyết được đặt ra cho những người làm trong lĩnh vực tin sinh học nhằm hỗ trợ cho quá trình phân tích dữ liệu trình tự metagenomic. 1.1 Bài toán phân loại trình tự metagenomic Mẫu thực nghiệm sau khi được thu thập từ môi trường thực tế, được đưa trực tiếp vào giai đoạn xác định trình tự. Do đó, dữ liệu trình tự metagenmic thường không chứa trình tự của từng loài vi sinh vật riêng biệt, mà bao gồm trình tự của rất nhiều loài khác nhau (có khi hơn 10.000 loài trong một mẫu [35]. Vì vậy, đối với nhà sinh học, một trong những vấn đề cần giải quyết là thực hiện phân loại trình tự metagenomic. Bài toán này được phát biểu 10
14. như sau (theo Thomas và cộng sự [30]): "Phân loại trình tự metagenomic là quá trình sắp xếp trình tự DNA vào các nhóm bao gồm các trình tự thuộc cùng hệ gien của một cá thể hoặc hệ gien của các vi sinh vật có quan hệ gần nhau". Kết quả của bài toán này là cơ sở để nhà sinh học có thể xác định những nhóm vi sinh vật nào tồn tại trong mẫu thực nghiệm, giúp họ thực hiện nghiên cứu trên trình tự của từng nhóm, và tìm ra những nhóm vi sinh vật mới. Ngoài ra, nó là mắt xích quan trọng trong chuỗi các công việc phân tích dữ liệu metagenomic. Điều này được thể hiện trong quy trình xử lý dữ liệu metagenomic. 1.2 Quy trình xử lý dữ liệu metagenomic Bài toán phân loại trình tự metagenomic (taxonomic binning) là một trong những vấn đề cần giải quyết trong giai đoạn phân tích dữ liệu của một dự án trong lĩnh vực metagenomics. Quy trình xử lý thông thường của một dự án được Thomas và cộng sự trình bày trong [30]. Trong đó, một số bước xử lý chính như sau (Hình 1.1) 1.2.1 Thu thập mẫu thực nghiệm Đầu tiên là giai đoạn thu thập mẫu thực nghiệm từ môi trường chứa vi sinh vật và thực hiện một số bước xử lý ban đầu như: cắt ngắn mẫu thực nghiệm, trích lọc mẫu DNA. DNA (Deoxyribonucleic acid) là phân tử 11
15. có cấu trúc ba chiều, bao gồm hai chuỗi đơn xoắn ốc, cuộn xung quanh một trục chung, tạo thành một chuỗi xoắn kép. Chuỗi DNA được hình thành bởi các loại phân tử nhỏ hơn, gọi là nucleotide. Có bốn loại nucleotide được ký hiệu là: A, C, G và T (tương ứng với Adenine, Cytosine, Guanine và Thymine) [14]. Hình 1.1: Quy trình xử lý của một dự án trong lĩnh vực metagenomics (Tham khảo [30]) 1.2.2 Xác định trình tự Tiếp theo, mẫu DNA được đưa vào quá trình xác định trình tự. Xác định trình tự là quá trình xác định dãy các nucleotide trong trình tự đó. Phương pháp Sanger [25], hay còn gọi là phương pháp dideoxy sequencing hay chain 12
16. termination, là công nghệ được sử dụng từ những năm 1970 đến nay. Phương pháp này cho phép xác định trình tự (read) có độ dài trong khoảng từ 500 - 1000 bp. Nhược điểm của phương pháp này là chi phí cao và hiệu suất xử lý thấp, không đáp ứng được yêu cầu của những dự án lớn. Một nhóm các công nghệ xác định trình tự mới ra đời, thay thế cho phương pháp Sanger, như: 454 pyrosequencing, Illumina Genome Analyzer, AB SOLiD [26]. Chúng được gọi chung là công nghệ xác định trình tự thế hệ tiếp theo (Next-generation sequencing [16]). Ưu điểm của các phương pháp này là hiệu suất cao hơn so với phương pháp Sanger. Chúng cho phép xác định một khối lượng lớn trình tự trong một đơn vị thời gian. Tuy nhiên, hạn chế của chúng là độ dài của các trình tự được xác định có kích thước ngắn. Chẳng hạn, trình tự được xác định bởi Illumina có độ dài trung bình khoảng 75 - 100 bp [26]. 1.2.3 Phân tích dữ liệu Ở giai đoạn này, dữ liệu trình tự DNA được phân tích bởi nhà sinh học dựa trên sự hỗ trợ của máy tính. Nhiều bài toán khác nhau cần giải quyết đã được đặt ra như: ráp nối trình tự (assembly), phân loại trình tự (taxnomic binning), chú thích trên trình tự (annotation), v.v Trong đó, dữ liệu đầu ra của bài toán này có thể là dữ liệu đầu vào của bài toán khác và ngược lại. Chẳng hạn, kết quả của bài toán phân loại trình tự có thể được sử dụng cho bài toán chú thích trên trình tự (annotation) nhằm xác định vị trí gien hay vị trí mang mã di truyền trên trình tự. Bài toán phân loại và ráp nối trình 13
17. tự có thể được sử dụng hỗ trợ cho nhau trong việc phân tích và xử lý dữ liệu metagenomic. Bài toán phân loại có thể được sử dụng như là bước tiền xử lý cho bài toán ráp nối trình tự nói chung áp dụng cho dữ liệu metagenomic [7] (Bao hàm cả bài toán genome assembly, và bài toán metagenome assembly). Ngược lại, bài toán phân loại còn có thể được áp dụng sau khi trình tự sinh học đã được ráp nối. Khi đó, việc phân loại cho trình tự dài hơn giúp mang lại độ chính xác cao hơn. Tuy nhiên, bài toán ráp nối trình tự metagenomic (metagenome assembly) là một vấn đề khó và nhiều thách thức lớn. Hiện tại, cũng chỉ có một vài giải pháp được đề xuất cho vấn đề này [30]. Bài toán phân loại trình tự metagenomic có thể được chia thành hai bài toán khác nhau dựa trên cách tiếp cận. Khi giải quyết bài toán này theo hướng không sử dụng hệ gien tham khảo, bài toán này có thể được hiểu là một bài toán gom cụm. Đây là vấn đề cần giải quyết trong đề tài này. 14
18. Chương 2 TỔNG QUAN GIẢI PHÁP GOM CỤM TRÌNH TỰ METAGENOMIC 2.1 Định nghĩa bài toán Vấn đề gom cụm có thể được phát biểu theo khía cạnh một bài toán phân hoạch như sau: Cho tập dữ liệu trình tự metagenomic X = {x1, x2, . . . , xn}, tìm một cách phân hoạch tập X thành các tập con C1,C2, ,Ck, với k ≤ n, sao cho thỏa điều kiện: (i) Ci 6= ∅, i = 1, 2, . . . , k Sk (ii) i=1 Ci = X (iii) Ci ∩ Cj = ∅, i, j = 1, 2, . . . , k và i 6= j 15
19. Và thỏa mãn một tập các điều kiện ràng buộc để mỗi phần tử xi (1 ≤ i ≤ n) thuộc về một tập Cj (1 ≤ j ≤ k) nào đó. Điều kiện ràng buộc thường được xây dựng dựa trên dấu hiệu hệ gien (genome signatures) và tính chất quan sát được của trình tự sinh học, gọi chung là đặc trưng gom cụm (charateristic). 2.2 Các giải pháp gom cụm Các giải pháp gom cụm hiện nay có thể được chia thành ba nhóm chính như sau: Phương pháp dựa trên k-means và tựa k-means, phương pháp dựa trên mô hình, và phương pháp dựa trên đồ thị. 2.2.1 Phương pháp sử dụng giải thuật k-means Nhóm giải pháp sử dụng thuật toán k-means hay tựa k-means (k-mediods, k-medians). Các thuật toán này sử dụng kỹ thuật tìm kiếm nhằm tìm được giá trị nghiệm tối ưu cục bộ dựa trên hàm mục tiêu cụ thể. Tuy không phải là kỹ thuật tìm chính xác, nhưng chúng có ưu điểm là thực thi nhanh. Ngoài ra, đây là phương pháp được chấp nhận và sử dụng rộng rãi. Các thuật toán này chỉ khác nhau ở việc lựa chọn phần tử trung tâm của cụm dữ liệu. MetaCluster 1.0 và 2.0 ([37], [38]) sử dụng giải thuật k-means để phân loại dựa trên sự khác biệt trong tần số xuất hiện các l-mer của trình tự. Trong khi MetaCluster 1.0 sử dụng độ đo Chebychev để xác định khoảng cách giữa hai trình tự, MetaCluster 2.0 sử dụng độ đo Spearman Footrule. Khi sử dụng tính hợp thành, khoảng cách giữa hai trình tự khác loài chỉ được thể hiện rõ khi độ dài trình tự đủ lớn. Vì vậy, các giải pháp này chỉ 16
20. cho phép phân loại trình tự lớn hơn 500bp. Một số giải pháp lai, trong đó giải thuật k-means hay tựa k-means được sử dụng trong một giai đoạn của quá trình xử lý như: MetaCluster 3.0, 4.0, 5.0 ([13], [32], [33]), MetaBinning [19]. Các giải pháp này được trình bày là có khả năng phân loại cho trình tự ngắn nhờ quá trình tiền xử lý. Trong đó, trình tự được gom thành từng cụm nhỏ. Đặc trưng hợp thành được rút trích trong từng cụm thay vì trong từng trình tự. Thuật toán dạng k-means được sử dụng để gom các cụm này thành cụm lớn hơn dựa trên khoảng cách dựa các cụm. 2.2.2 Phương pháp dựa trên mô hình Giải pháp theo hướng tiếp cận này thường sử dụng giả định đoạn trình tự nucleotide (gọi là k-mer) hay trình tự (read) tuân theo một mô hình nào đó. Chẳng hạn, giải pháp AbundanceBin [36], giải pháp của Olga và cộng sự [29] và giải pháp của Shruthi và cộng sự [21] giả định phân phối xác suất các k-mers trong một hệ gien tuân theo phân phối Poisson. Giải thuật cực đại hóa kỳ vọng (Expectation Maximization) thường được sử dụng nhằm ước lượng tham số của mô hình. AbundanceBin [36] và giải pháp của Olga là hai giải pháp gần đây nhất cho phép thực hiện gom cụm chỉ dựa trên sự phong phú. So sánh với AbundanceBin, giải pháp của Olga cải tiến việc đếm số lần xuất hiện l-mers bằng cách sử dụng thêm ý tưởng từ bài toán Balls and Bins để giảm nhiễu do lỗi xác định trình tự. Hai giải pháp này cũng có thể được sử dụng như là bước tiền xử lý cho các giải pháp dựa trên 17
21. tính hợp thành nhằm tăng độ chính xác cho việc gom cụm [28], [36] . Trong khi đó, LikelyBin [11] giả định tập trình tự của một hệ gien là một quá trình ngẫu nhiên (stochastic process). Tập hợp nhiều hệ gien là nhiều quá trình ngẫu nhiên. Mỗi quá trình ngẫu nhiên tương ứng với một phân phối xác suất riêng biệt. Phương pháp Markov Chain Monte Carlo được dùng để ước lượng tham số cực đại cho mô hình xác suất. Một phương pháp khác, Scimm [10] dựa trên giả định rằng xác suất xuất hiện của một nucleotide trong một trình tự phụ thuộc vào các nucleotide đứng trước nó. Qua đó, giải pháp này sử dụng mô hình Markov hồi quy (Interpolated Markov Models - IMM) để dự đoán mối liên hệ giữa các trình tự. Một dạng của giải thuật k-means, giải thuật Classification Expectation Maximization (CEM) được sử dụng. Trong đó, k cụm tương ứng với k mô hình IMM. Trong số các giải pháp này, AbundanceBin và giải pháp của Shruthi và cộng sự được trình bày là có thể phân loại cho trình tự ngắn. Trong khi đó, các giải pháp còn lại chỉ phù hợp cho phân loại trình tự dài (≥ 800bp). 2.2.3 Phương pháp dựa trên đồ thị Một hướng tiếp cận khác là chuyển bài toán gom cụm trình tự thành bài toán phân hoạch trên đồ thị. TOSS [28] là giải pháp sử dụng kỹ thuật này. Giải pháp thực hiện phân loại theo hai pha. Pha một, gom cụm trình tự dựa trên việc gom cụm các unique l-mer (các l-mer chỉ xuất hiện một lần duy nhất trong các hệ gien). Vấn đề gom cụm các unique k-mer được chuyển thành bài toán phân hoạch đồ thị. Trong đó, mỗi unique k-mer là một đỉnh. 18
22. S K L 0 0 2 1 5 4