Cải tiến clustalw cho bài toán sắp hàng đa trình tự

Trang 11 CHƯƠNG 1: TỔNG QUAN 1.1 GIỚI THIỆU Trong lĩnh vực nghiên cứu phân tích cấu trúc và chức năng của gene và protein, phân tích trình tự (chuỗi DNA, protein) đóng vai trò quan trọng. Thông thường, khi phát hiện ra một gene hay một protein mới, một trong những yêu cầu quan trọng là làm thế nào xác định được chức năng và cấu trúc của gene hay protein này. Một cách tiếp cận phổ biến là so sánh đoạn gene hoặc protein này với đoạn gene hoặc protein đã biết, từ đó có thể dự đoán chức năng và cấu trúc của chúng. Tuy nhiên, với số lượng tế bào trong cơ thể là khoảng 1014 và mỗi tế bào mang khoảng 3.109 ký tự trong đoạn gene của chúng thì việc so sánh là vô cùng mất thời gian và công sức. Sắp hàng đa trình tự là một trong những bài toán quan trọng và phổ biến nhằm hỗ trợ phân tích các trình tự sinh học. Bản thân nó là bài toán cơ sở cho những bài toán khác. Từ kết quả đạt được của việc giải bài toán này, người ta có thể sử dụng để phát hiện và chứng minh sự tương đồng giữa các trình tự mới so với các trình tự sinh học đã tồn tại; xác định quá trình tiến hóa của các họ trình tự đễ xây dựng các cây sinh loài; hỗ trợ để chNn đoán cấu trúc của các protein, v.v... Hình 1.1 Ứng dụng của MSA Trong việc giải quyết bài toán sắp hàng trình tự, trước hết phải xem xét bài toán sắp hàng 2 trình tự (Pairwise Sequence Alighment – PSA). Bài toán này đã được giải quyết trọn vẹn bằng nhiều phương pháp khác nhau. Đồng thời với việc giải quyết bài toán sắp hàng hai trình tự này, xuất hiện nhu cầu sắp hàng đa trình tự (Multiple Trang 12 Sequence Aligment – MSA) để so sánh nhiều đoạn gene hoặc tìm một phần tử đại diện cho một tập gene, khi dữ liệu sinh học ngày càng lớn. Tuy nhiên, cho đến nay, bài toán sắp hàng đa trình tự vẫn còn là một bài toán khó, chưa có một phương pháp nào có thể cung cấp một lời giải trọn vẹn. Các lời giải thường tập trung vào việc tìm ra phép so sánh “gần” tốt nhất và mỗi phương pháp tiếp cận sẽ chỉ cho những lời giải thật sự tốt tùy từng yêu cầu tiếp cận và bài toán cụ thể. Trong nước cũng như thế giới đã có rất nhiều công trình nghiên cứu, các sản phNm phần mềm giải quyết bài toán này và nó vẫn còn đang được quan tâm, nghiên cứu, cải tiến hằng ngày. Một số công trình tiêu biểu đã thực hiện trong việc sắp hàng đa trình tự sinh học được liệt kê như sau:
Ngoài nước: • Phần mềm − ClustalW (Thompson, 1994) :đây là chương trình phổ biến nhất − PRRP (Gotoh, 1993) − HMMT (Eddy, 1995) − DIALIGN (Morgenstern, 1998) − T-Coffee (Notredame, 2000) − MUSCLE (Edgar, 2004) − Align-m (Walle, 2004) − PROBCONS (Do, 2004)
Trong nước: • Phần mềm Trang 13 − GENESYS2000 (Trường Đại học Khoa học tự nhiên TPHCM, 2001) − HiBio (Phân viện Công nghệ thông tin tại TP. Hồ Chí Minh, 2004) • Đề tài, dự án: − Hoàng Văn Kiếm, Nguyễn Văn Uyển, Xây dựng mô hình và công cụ Tin học để xử lý thông tin về Gen, hỗ trợ nghiên cứu ứng dụng trong Công nghệ Sinh học ở Việt Nam. Đề tài do Sở Khoa học và Công nghệ TPHCM quản lý, 2000 – 2001. − Trần Văn Lăng, Nghiên cứu để xây dựng công cụ tin học xử lý thông tin về gen và protein. Đề tài cấp bộ, Viện Khoa học và Công nghệ Việt Nam quản lý, 2003 - 2004. • Sách, bài báo, luận văn được trình bày trong các công trình [1][2][3] 1.2 SẮP HÀNG TRÌNH TỰ 1.2.1 Định nghĩa Sắp hàng trình tự (hay phép gióng hàng, gióng cột) là quá trình nghiên cứu sự giống nhau giữa các chuỗi trình tự (sequence), đo lường sự giống nhau giữa các chuỗi trình tự. Là cách thức so sánh giữa 2 hay nhiều trình tự dựa trên việc so sánh một chuỗi các thành phần (ký tự) của trình tự để tìm ra điểm tương đồng, giống nhau giữa các trình tự. Các trình tự là các chuỗi DNA, RNA hoặc các trình tự amino acid (protein). Sắp hàng trình tự giúp cho quá trình dự báo sự giống nhau về chức năng của các trình tự, dự báo cấu trúc bậc 3 của DNA, protein. Trong việc tìm hiểu một gene mới, chúng ta thường quan tâm đến việc xác định những đặc điểm để phân biệt gene đồng thời đưa ra những giả thuyết về chức năng của gene. Trang 14 Việc đưa ra giả thuyết về chức năng của gene thường dựa vào những giải thuật đánh giá sự giống nhau, tương đồng giữa các trình tự. 1.2.2 Phân loại Dựa trên phương pháp, người ta chia thành 2 loại sắp hàng (alignment) • Phép sắp hàng theo hướng toàn cục (Global Sequence Alignment): Phép sắp hàng được áp dụng trên toàn bộ chuỗi trình tự. Thường được sử dụng khi các trình tự so sánh có kích thước gần tương đương và các trình tự này có độ tương đồng cao. • Phép sắp hàng theo hướng cục bộ (Local Sequence Alignment): Phép toán sắp hàng được áp dụng trên một phần của chuỗi trình tự. Thường được sử dụng khi các trình tự có độ dài lớn, độ tương đồng không cao hoặc khi các trình tự có kích thước khác biệt lớn. Dựa trên số lượng trình tự được sắp hàng, người ta chia thành 2 loại sắp hàng: 1. Sắp hàng từng cặp (Pairwise Sequence Alignment-PSA) 2. Sắp hàng đa trình tự (Multiple Sequence Alignment-MSA) 1.2.3 Sắp hàng từng cặp (Pairwise Sequence Alignment-PSA) Hình 1.2: Sắp hàng từng cặp Trang 15 1.2.4 Sắp hàng đa trình tự (Multiple Sequence Alignment-MSA) Hình 1.3: Sắp hàng đa trình tự Thông thường, các protein được lưu trữ trong cơ sở dữ liệu thường được tổ chức thành các nhóm chung (protein family), có sự tương đồng về cấu trúc, chức năng và cấu trúc bậc 3. Khi có một protein mới muốn khảo sát, chúng ta mong rằng thông qua phép toán sắp hàng để có thể đưa ra các giả thuyết về cấu trúc, chức năng và quá trình tiến hóa của nó. Tuy nhiên chúng ta không thể thực hiện việc sắp hàng trình tự protein này với từng trình tự của mỗi protein trong cơ sở dữ liệu, điều này là không thể về mặt thời gian xử lý. Do đó cách tiếp cận tốt nhất là chúng ta sẽ so sánh trình tự của protein này với mỗi tập hợp protein trong cơ sở dữ liệu thông qua việc so sánh các trình tự của protein này với một trình tự đại diện cho mỗi tập hợp protein. Vấn đề đặt ra là làm cách nào để tìm ra trình tự đại diện cho một tập hợp protein? Trình tự đại diện cho một tập hợp protein được tìm thấy thông qua phép sắp hàng đa trình tự để tìm ra trình tự tương đồng nhất. Phép sắp hàng k trình tự S1, S2, S3, …, Sk sẽ tạo ra k trình tự mới S’1, S’2, S’3,…, S’k bằng cách thêm các ký tự “-“ (được gọi là gap) vào các chuỗi ban đầu trong đó các chuỗi mới tạo này phải có chiều dài bằng nhau. Vậy có thể nói rằng việc biến đổi từ trình tự S1 sang trình tự S’1 là sự kết hợp của các quá trình: quá trình thay thế, sự xuất hiện của các gap. Trang 16 1.2.5 Các khái niệm khác 1.2.5.1 Trình tự: Các dữ liệu thường được đem ra so sánh và phân tích bao gồm các chuỗi trình tự những nucleotic (DNA) và chuỗi trình tự những amino acid (protein). DNA (Deoxyribo Nucleic Acid) và RNA (Ribo Nucleic Acid) là hai đại phân tử (đa phân tử) sinh học. Chúng là các nucleic acid vật chất mang thông tin di truyền từ các hệ thống sống. DNA là một chuỗi các nucleotic sắp xếp kế tiếp nhau. Nucleotic có 4 loại và được ký hiệu là A (Adenine), G (Guanine), C (Cytosine), T (Thymine). Ta có bộ ký hiệu cho các nucleotic như sau: Nuc={A, C, G, T}. Protein là biểu hiện của vật chất sống. Nó tham gia hầu hết vào các quá trình sinh học và là cơ sở của sự đa dạng về cấu trúc và chức năng của tất cả các sinh vật. Trong sự sống, protein được tạo ra trong quá trình dịch mã từ đoạn gene biểu hiện chứa thông tin di truyền trong DNA. Protein là một chuỗi các trình tự amino acid nối kết nhau bằng các liên kết tạo nên cấu trúc (được chia thành nhiều dạng cấu trúc như bậc 1, bậc 2, và cấu trúc không gian bậc 3, bậc 4, bậc 5). Amino acid gồm 20 loại được ký hiệu tắt bởi các chữ cái. Mỗi amino acid được mã hóa từ bộ 3 nucleotic. Tuy có 64 bộ mã hóa nhưng chỉ có 20 loại amino acid và một số mã làm tín hiệu cho việc dịch mã từ DNA. Bộ ký hiệu cho các amino acid : AA={A, C, D, E, F, G, G, I, K, L, M, N, P, Q, R, S, T, V, W, Y}. Trình tự các protein là một chuỗi trình tự các amino acid. 1.2.5.2 GAP Ký hiệu là – Trong quá trình tiến hóa, các trình tự có thể thêm hoặc bớt một số phần tử (thường ký hiệu là InDel – insertions/deletions) trong trình tự, cho nên các sinh vật có họ hàng gần nhau có thể khác nhau ở phần thêm vào giữa các trình tự. Bởi vậy khi chuyển sang việc so sánh trong mô hình toán học cần phải cho phép Trang 17 có quãng cách (gap) để có thể tìm được các phần trình tự giống nhau nhất. Tuy nhiên, khả năng thêm hay bớt trong các trình tự là quá trình tiến hóa lâu dài, vì vậy khi đánh giá các sinh vật nào gần nhau thì cũng có ít quãng cách hơn. Do đó trong mô hình toán học có đưa thêm vào điểm phạt cho quãng cách (gap penalties) sao cho đáp ứng giống bài toán thực tế. Các loài gần nhau sẽ có trình tự giống nhau các đoạn liên tục và dài cho nên các mô hình toán học còn thêm điểm phạt cho mỗi một đoạn quãng cách (open gap penalties). Bên cạnh đó, trong quá trình tiến hóa cũng có trường hợp bị đột biến tại một số phần tử trong trình tự (có thể hiểu đơn giản là nucleotic hay amino acid này được thay thế bằng phần tử khác). Gồm 2 loại: deletion gap và insertion gap tương ứng với quá trình thêm vào hoặc mất đi các phần tử di truyền 1.2.5.3 Giá trị của GAP Theo các nghiên cứu, các thay đổi dạng chèn và xóa bớt các ký tự trong trình tự xuất hiện rất ít so với trường hợp do đột biến. Do đó, trong mô hình so sánh các trình tự không quan tâm tới việc chèn hay xóa thêm các ký tự mà chỉ xét thêm các gap trong việc so sánh để đảm bảo phản ánh chính xác loại thay đổi này. Gap được hiểu đơn giản khi nhìn trong chuỗi trình tự là phần trống, không có ký tự để so sánh với ký tự của các chuỗi khác. Khi tính điểm so sánh cần phải tính thêm điểm phạt (gap penalty) do quãng cách này gây ra vì càng nhiều quãng cách thì các trình tự đem ra so sánh càng ít giống nhau. Dựa trên hàm tuyến tính theo chiều dài gap để tính giá trị của gap: γ (k) = −(q+r*k) Hình 1.4: Các loại GAP Trang 18 q (q>0): giá trị xác định khả năng mở gap (gap open) r (r>0) : giá trị xác định khả năng xuất hiện mỗi phần tử trong gap (gap extension) Hình 1.5: Giá trị của GAP 1.2.5.4 Ma trận đánh giá Kết quả của việc tính giá trị cho mỗi phép sắp hàng phụ thuộc nhiều và kết quả của hàm đánh giá sự tương đồng của mỗi cặp amino acid σ(a,b). Trong thực tế sinh học khả năng xuất hiện của mỗi cặp amino acid là khác nhau, xác suất xuất hiện cùng lúc của mỗi cặp amino acid này có thể cao trong khi xác suất xuất hiện của cặp amino acid kia có thể thấp. Vì thế, độ tương dồng của các cặp amino acid thường được lưu trữ dưới dạng một ma trận 2 chiều gọi là ma trận đánh giá. Hình 1.6: Ma trận Blosum Trang 19 Có nhiều hình thức ma trận đánh giá khác nhau dựa trên quá trình nghiên cứu thống kê thực tế sinh học. • Identity matrix: Đây là cơ chế đánh giá độ tương đồng đơn giản nhất. Trong ma trận này, các cặp amino acid giống nhau sẽ có giá trị của phần tử tương ứng trong ma trận là 1, các cặp amino acid còn lại sẽ nhận giá trị 0. • Ma trận mã di truyền (Genetic code matrix): Trong ma trận này, hàm đánh giá của mỗi cặp amino acid dựa trên độ tương đồng về mã di truyền. Ngày nay ma trận này hiếm khi được sử dụng trong việc sắp hàng các trình tự. • Ma trận tương đồng hóa học (chemical similarity matrix): trong ma trận này, các amino acid có cấu trúc tương đồng về cấu trúc vật lý cũng như thuộc tính hóa học như kích thước, hình dạng, khả năng phân cực,…thì phần tử tương ứng trong ma trận sẽ nhận giá trị lớn hôn so với các cặp còn lại. • Ma trận thay thế (substitution matrix) : Ma trận này được tính toán và xây dựng trên các quan sát thống kê về tần số thay đổi của các amino acid trong việc sắp hàng các chuỗi trình tự. Ma trận thay thế được đánh giá là tốt hơn so với 3 ma trận trên và hiện nay cũng được sử dụng nhiều nhất. Ma trận BLOSUM gồm nhiều cấp độ, ký hiệu là BLOSUMn. Ma trận BLOSUMn (1≤n≤100) cho biết độ tương đồng của các chuỗi được dùng để tính ra chúng. Ví dụ ma trận BLOSUM62, giá trị các phần từ trong ma trận được tính từ tập các protein có độ tương đồng không lớn hơn 62%. Trong tập các ma trận BLOSUMn, các ma trận có chỉ số n nhỏ thường được sử dụng trong việc align các trình tự có độ khác biệt cao (độ tương đồng thấp), và các ma trận có chỉ số n lớn Trang 20 thường được sử dụng cho các trình tự có độ tương đồng cao. Chẳng hạn ma trận BLOSUM62 thường được dùng cho việc align các trình tự khi chưa xác định độ tương đồng của chúng, ma trận BLOSUM45 thường được dùng cho các trình tự có độ khác biệt cao, ma trận BLOSUM100 thường được sùng cho các trình tự có độ tương đồng cao. Việc tính toán các tập ma trận BLOSUM dựa trên công thức xác suất biến đổi: score(a,b)=σ(a,b)=klog(P0PE ) Trong đó P0 là xác suất chuyển đổi từ amino acid a sang amino acid b trong tập quan sát. PE là xác suất xuất hiện của amino acid b trong tập quan sát. k là hệ số làm tròn. Thông thường k=10 và giá trị hàm đánh giá được làm tròn thành số nguyên. score(a,b)>0 cho biết sự thay thế giữa amino acid a và b có khả năng xảy ra cao hơn so với sự thay đổi một cách ngẫu nhiên. score(a,b)<0 cho biết sự thay thế giữa amino acid a và b có khả năng xảy ra thấp hơn so với sự thay đổi một cách ngẫu nhiên. score(a,b)=0 cho biết sự thay thế giữa amino acid a và b tương đương với việc thay thế 2 amino acid một cách ngẫu nhiên. Trang 21 Hình 1.7: Tính score bằng ma trận đánh giá 1.2.5.5 Phương pháp đánh giá (score method): Phương pháp đánh giá cho phép đánh giá sự giống nhau, tương đồng giữa các trình tự dựa trên một số tiêu chí nào đó. Việc sắp hàng giữa 2 hay nhiều trình tự sẽ cho kết quả khác nhau từ một tập chuỗi trình tự ban đầu. Cơ sở để đánh giá sự giống nhau giữa các trình tự sau phép sắp hàng thường căn cứ vào một hàm đánh giá cụ thể. Việc xây dựng hàm đánh giá tốt sẽ cho phép xác định được kết quả nào của phép sắp hàng tối ưu. Hàm đánh giá chính là cốt lõi của một phương pháp đánh giá. Đối với PSA, phương pháp đánh giá phổ biến nhất là dựa vào tổng giá trị của các cặp ký tự đại diện không phải là Gap và giá trị của Gap trong PSA. Đối với MSA, vì tính chất phức tạp của dữ liệu sinh học nên tất cả các phương thức đánh giá đều có những hạn chế và không có một tiêu chuNn tổng quát nào để đo lường chất lượng của nó. Trong phần này xin giới thiệu một phương pháp phổ biến nhất cho một MSA, đó là phương pháp Sum of Pair. Trang 22 Hình 1.8: Phương pháp đánh giá Sum of Pair Nội dung của phương pháp này là đánh giá MSA của k trình tự dựa trên tổng kết quả align của tất cả (k2 ) cặp trình tự có trong MSA. Theo phương pháp này giá trị của mỗi cột của MSA sẽ được tính bắng tổng tất cả các hàm đánh giá độ tương đồng của các cặp phần tử trong cột này. 1.3 MỘT SỐ PHƯƠNG PHÁP SẮP HÀNG TRÌNH TỰ 1.3.1 Phương pháp sắp hàng chính xác (Exact algorithms) Thuật toán sắp hàng chính xác dựa trên việc tổng quát hóa thuật toán Needleman-Wunsch. Đây là thuật toán luôn luôn đưa ta sắp hàng tối ưu bằng cách sử dụng thuật toán quy hoạch động “quay về theo lối cũ” (backtracking). Khuyết điểm trong chiến lược sắp hàng chính xác là yêu cầu về thời gian và bộ nhớ (tăng theo hàm số mũ với số lượng các trình tự). 1.3.2 Phương pháp sắp hàng lũy tiến toàn cục (Progressive algorithms) Về cơ bản, phương pháp này vẫn dựa trên nền tảng của thuật toán qui hoạch động. Thuật toán này tìm ra các trình tự có quan hệ gần nhau bằng cách sử dụng cây hướng dẫn (guide tree). Đây là phương pháp đơn giản và hiệu quả về mặt thời gian và bộ nhớ. Thuật toán được đề xuất đầu tiên bởi Hogeweg Trang 23 và sau đó được phát triển bởi Feng-Dolittle. Ý tưởng của thuật toán này là ban đầu thực hiện thiết lặp sắp hàng 2 trình tự, sau đó sắp hàng kết quả của cặp này với một trình tự khác để mở rộng sắp hàng đa trình tự. Tiến trình này được lặp đi lặp lại nhiều lần cho đến khi tất cả các trình tự được sắp hàng. Một số chương trình được hiện thực theo phương pháp này: ClustalW, Multalign, Pileup, Blast, Fasta, Multal, Dialign. 1.3.3 Phương pháp sắp hàng lặp (Iterative algorithms) Thuật toán này lặp đi lặp lại việc sắp hàng để cố gắng tìm ra sắp hàng tối ưu nhất bằng cách sử dụng các profile, block, pattern,…Phương pháp này thường được áp dụng cho sắp hàng cục bộ. Khuyết điểm của phương pháp này là đòi hỏi thời gian tính toán cao và trong một số trường hợp kết quả thu được không tốt. 1.3.4 Phương pháp dựa trên mô hình Makov &n (Hidden Markov Model- HMM) Là phương pháp dựa trên thống kê các trạng thái và xác suất chuyển đổi giữa chúng. Được áp dụng cho cả sắp hàng toàn cục và sắp hàng cục bộ. Các thuật toán phổ biến như thuật toán Forward-Backward, thuật toán Viterbi, thuật toán Baum-Welch. Ý tưởng của phương pháp này là sử dụng mô hình Markov Nn để biểu diễn MSA, sau đó tối ưu khả năng mà một mô hình HMM có thể biểu diễn cho các trình tự đã được align. Trong mô hình này, các nucleotic (A, C, T, G) hoặc 23 amino acid sẽ là tập hợp các ký tự. Các trạng thái của mô hình sẽ thuộc 3 loại trạng thái: match, insert, delete. Mỗi ký tự sẽ có một xác suất xuất hiện nhất định tại mỗi trạng thái. Giữa các trạng thái sẽ có xác suất chuyển đổi từ trạng thái này sang trạng thái khác. Dựa trên mô hình này, mỗi chuỗi trình tự bất kỳ trong sinh học sẽ được sinh ra bằng một con đường tập các trạng thái. Tập hợp các trạng thái của các chuỗi trình tự trong mô hình HMM sẽ là 1 kết quả của bài toán sắp hàng đa Trang 24 trình tự. Và như vậy bài toán sắp hàng đa rình tự sẽ trở thành bài toán tìm xác xuất điều kiện cực đại của các chuỗi trình tự khi biết mô hình.