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 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 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 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.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 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 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].1: Quy trình xử lý của một dự án trong lĩnh vực metagenomics (Tham khảo [30]) 1.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 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].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. 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 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 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 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 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ị.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.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 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.
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 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 đó.
