- Sự phát triển của công nghệ giải mã trình tự đã giúp giải mã ngày càng nhiều các hệ gen, đặc biệt là những hệ gen có kích thước vừa và nhỏ như vi rút hay vi khuẩn (hơn 7000 bộ gen của vi rút và vi khuẩn đã được giải mã). - Bên cạnh đó hệ gen của những sinh vật bậc cao cũng đã được giải mã hoàn chỉnh như người, chó, chuột. - Điều đó dẫn đến một nhu cầu cấp thiết là phải nghiên cứu các phương pháp và xây dựng một chương trình so sánh và bắt cặp trình tự cho hai hệ gen.. - Trong khóa luận này, em xin được trình bày phương pháp và xây dựng một chương trình so sánh bắt cặp trình tự hoàn chỉnh cho hai hệ gen. - Qua đó khắc phục những hạn chế và lựa chọn những ưu điểm của chúng để tạo thành một chương trình sắp hàng hệ gen hoàn chỉnh. - Khi thực nghiệm với dữ liệu thật và so sánh độ tương đồng với giá trị bắt cặp thu được khi chạy phương thức Hungarian[8] với các hệ gen được chia sẵn bằng cách sử dụng các đoạn gen cung cấp tại Gen Bank cũng cho kết quả tương đương thậm chí tốt hơn trong hầu hết các trường hợp.. - Trình tự. - Bắt cặp trình tự. - Bắt cặp trình tự hệ gen. - Bài toán sắp hàng hoàn chỉnh hai hệ gen. - Thuật toán. - Bắt cặp với những trình tự lớn. - Ví dụ về một trình tự.. - 29Hình 5:Bắt cặp trình tự với Ukkonen Barrier. - Trải qua hàng triệu năm tiến hóa và phát triển, một số đoạn gen được mất đi cũng như bị di chuyển vị trí so với ban đầu, hình thành lên những hệ gen khác nhau đại diện cho hàng tỷ sinh vật trên trái đất. - Một trong những nhiệm vụ cần thiết là phải tìm ra mối quan hệ về mặt cấu trúc giữa các hệ gen sinh vật, qua đó xây dựng lên một bức tranh toàn cảnh về sự tương tự và tiến hóa giữa các sinh vật trên hành tinh.. - Với sự phát triển của công nghệ giải mã trình tự, ngày càng nhiều các hệ gen đã được giải mã hoàn chỉnh và được lưu trữ trong các ngân hàng cơ sở dữ liệu gen. - Việc so sánh và tìm ra sự tương đồng giữa các hệ gen một cách thủ công là không thể thực hiện được. - Do đó dẫn đến một nhu cầu cấp thiết phải nghiên cứu phương pháp và xây dựng chương trình để so sánh và bắt cặp trình tự cho hai hệ gen.. - Mặc dù một số phương pháp đã được nghiên cứu và phát triển, chúng mới chỉ tập trung vào xác định và bắt cặp cho những vùng ADN có độ tương đồng cao giữa hai hệ gen. - Tức là, một phần lớn trong hệ gen có thể không được bắt cặp và so sánh khi ta tiến hành với các loài sinh vật có hệ gen khác nhau nhiều. - Vì vậy cần phải xây dưng một hệ thống có khả năng bắt cặp được toàn bộ các ADN trên hai hệ gen.. - Chương này giới thiệu về những kiến thức cơ bản về tin sinh học, bài toán bắt cặp trình tự và bắt cặp trình tự theo hệ gen. - Một hệ gen của một sinh vật được thể hiện là một trình tự của các ADN.. - Ví dụ về một trình tự. - Hệ thống ký tự Tập hợp các phần tử có thể xuất hiện trong trình tự được gọi là một hệ thống các ký tự. - Khoảng cách Một điều quan trọng và cần thiết là xây dựng một hàm mục tiêu đánh giá khoảng cách giữa hai trình tự, qua đó đánh giá sự tương đồng, mối quan hệ giữa hai hệ gen. - Khoảng cách giữa hai trình tự có thể chỉ được tính đơn giản chỉ là chi phí thay thế (Hamming Hamming [10]) trong những trình tự có độ dài bằng nhau hay phức tạp hơn bao gồm cả chi phí chèn – xóa và dịch chuyển.. - Sắp hàng trình tự. - Thuật toán Quy hoạch động tính toán chi phí bắt cặp theo công thức sau:. - Thuật toán Needleman – Wunsch hoạt động khi mà chi phí cho việc chèn – xóa các nucleotide là một trọng số cố định. - Tức chi phí cho việc chèn một đoạn gap có độ dài k là wk. - Sắp hàng trình tự hệ gen. - Ta thấy gen số 1 đã bị dịch chuyển, nó nằm ở đầu của hệ gen Người nhưng lại nằm ở cuối ở hệ gen của Khỉ. - Tức là hoặc nó bị xóa khỏi hệ gen của Người hoặc nó được chèn thêm vào hệ gen của Khỉ. - Trải qua hàng triệu năm tiến hóa, với sự biến đổi ở mức độ gen, hệ gen của các sinh vật ngày nay đã có sự khác nhau rất lớn về kích thước, số lượng gen, thứ tự các gen cũng như về nội dung của các gen.. - Hình 2: Các biến đổi ở mức độ gen giữa Người và Khỉ Sắp hàng trình tự hệ gen là một trường hợp riêng của sắp hàng trình tự, trong đó đầu vào là toàn bộ trình tự ADN của một hệ gen sinh vật. - Sắp hàng trình tự hệ gen giúp xây dựng bức tranh toàn cảnh về sự tương tự và tiến hóa giữa các sinh vật, là cơ sở cho hướng nghiên cứu Comparative genomics [4], cho phép nâng cao độ chính xác dự đoán gen. - Về mặt tính toán, bắt cặp hệ gen đặt ra nhiều vấn đề cần giải quyết như kích thước trình tự lớn, thứ tự các phần tương đồng trên các hệ gen thường thay đổi. - Do tính quan trọng cũng như đặc thù phương pháp, vấn đề so sánh và sắp hàng trình tự hệ gen được trình bày thành một phần riêng, tách khỏi sắp hàng trình tự nói chung.. - Các thuật toán sắp hàng trình tự thông thường mới chỉ xác định được các biến đổi ở mức độ điểm (sự biến đổi của các nucleotide) cũng như chỉ làm việc được với các dữ liệu nhỏ. - Khi nghiên cứu về việc sắp hàng trình tự theo hệ gen, chúng ta phải tính toán cả những biến đổi ở mức độ điểm lẫn mức độ gen. - Đặc biệt thời gian thực thi cũng là một vấn đề hết sức quan trọng do kích thước rất lớn của các hệ gen. - Ví dụ kích thước của hệ gen người lên tới 3 tỉ ADN. - Một trong những hệ thống sắp hàng hệ gen đầu tiên là BLASTZ [18] được phát triển bới nhóm của Webb Miller vào đầu những năm 2000 tại đại học Pennsylvania để sắp hàng hệ gen của người và chuột. - Cũng như các phương pháp sắp hàng hệ gen khác, Phương pháp BLASTZ được phát triển từ tư tưởng thuật toán tìm kiếm BLAST [2] (thuật toán xác định những đoạn giống nhau cao giữa hai chuỗi). - Bước 1: Tìm kiếm những cặp đoạn ADN ngắn rất giống nhau ở cả hai hệ gen được gọi là hạt giống (seed). - Họ định nghĩa hạt giống là những cặp ADN giống nhau và xuất hiện duy nhất trên cả hệ gen. - Nhóm tác giả đã xây dựng hệ thống MAUVE để sắp hàng đa hệ gen và thu được những kết quả có độ chính xác cao trên những hệ gen có độ tương đồng cao [1]. - Lê Sỹ Vinh và đồng nghiệp tại Bảo Tàng Lịch Sử Tự Nhiên Hoa Kỳ, và tại trường Đại Học Công Nghệ nhằm so sánh và sắp hàng toàn bộ hệ gen đã được tiến hành và cho kết quả thử nghiệm khả quan [23,24]. - Nhóm nghiên cứu định nghĩa việc sắp hàng toàn bộ hệ gen phải thỏa mãn ba điều kiện chính sau. - Bắt cặp toàn bộ các ADN trên hệ gen. - Điều này cho phép chúng ta xây dựng hàm tục tiêu rõ ràng để tìm ra cách bắt cặp toàn bộ hệ gen tốt nhất. - Bài toán sắp hàng hoàn chỉnh hai hệ gen 2.1. - Lê Sỹ Vinh và đồng nghiệp [23,24], một hệ thống sắp hàng hoàn chỉnh hai hệ gen phải thỏa mãn ba điều kiện chính. - Bắt cặp toàn bộ các ADN trên hệ gen.. - Các phương pháp bắt cặp hệ gen tiêu biểu như BLASTZ[18], SLAGAN[5], MAUVE[1] mới chỉ dừng lại ở mức phát hiện và sắp hàng các đoạn ADN tương đồng. - Như vậy sẽ có một phần lớn trong hệ gen có thể không được bắt cặp và so sánh khi ta tiến hành với các loài sinh vật có hệ gen khác nhau nhiều. - Giải quyết vấn đề này, Lê Sỹ Vinh và các đồng nghiệp đã giới thiệu một phương pháp có khả năng sắp hàng hoàn toàn được hệ gen của hai sinh vật bất kỳ “Pairwise Alignment with Rearrangement” [23]. - Ưu điểm của thuật toán này so với các thuật toán bắt cặp trình tự trước đây ở chỗ nó cho phép có sự di chuyển vị trí của các ký tự. - Đầu vào hai trình tự, “Pairwise Alignment with Rearrangement” sẽ đưa ra cách sắp hàng sao cho tổng 3 chi phí : Chi phí thay đổi vị trí (Break Cost), chi phí chèn – xóa và chi phí thay thế các ký tự là nhỏ nhất. - Thực nghiệm cho thấy, việc sắp hàng trình tự có sự đổi chỗ của các ký tự cho kết quả tối hơn so với cắt bắt cặp trình tự thông thường không có sự đổi chỗ. - Cơ sở lý thuyết Trong “Pairwise Alignment with rearrangement”, ta xem hai hệ gen như hai chuỗi ký tự, tức là mỗi đoạn gen sẽ được xem như là một ký tự trong chuỗi đầu vào. - C(xi, yj) là chi phí để thay thế ký tự xi thành ký tự yj với i = 1 … p, j = 1. - C(xi, y0) và C(x0, yj) là chi phí chèn/xóa kí tự xi và yj tương ứng. - Chi phí C(A) của một bắt cặp A là tổng chi phí thay thế và chèn/xóa của các ký tự trong X và Y.. - Chi phí tối ưu để bắt cặp A*(X,Y. - yk’) được gọi là một bắt cặp trình tự có sắp xếp lại (PAR) của hai chuỗi X và Y. - Ký tự yj được thêm vào vị trí sao cho chi phí của AR mới là thấp nhất. - Một phép biến đổi được gọi có thể thực hiện được nếu chi phí của AR mới giảm đi.. - Ngược lại nếu S1 và S2 không độc lập, chỉ thực hiện phép biến đổi cho chi phí thấp hơn.. - Bắt cặp với những trình tự lớn Như đã trình bày ở trên, thuật toán “Pairwise Alignment with Rearrangement” yêu cầu về độ phức tạp thời gian tối thiếu là O(pq3) trong mỗi vòng lặp. - Chi phí sắp hàng giữa các ký tự (chèn, xóa, sửa) và chi phí sắp xêp lại thứ tự. - Chi phí sắp xếp lại thức tự R(X, XR. - Chi phí sắp hàng giữa các ký tự C(X’, Y. - Xét một phép đổi chỗ yi’ và yj’, chi phí sắp hàng có thể dễ dàng được tính lại với độ phức tạp thời gian yêu cầu là O(1) là : C(X’, Y. - Một phép đổi chỗ được gọi là có thể thực hiện nếu nó làm cho chi phí CR(AR) giảm xuống. - Xây dựng hệ thống Thuật toán “Pairwise Alignment with Rearrangement” [23] tuy đã sắp hàng được hoàn toàn hai hệ gen, tuy nhiên nhược điểm của nó chỉ có thể bắt cặp với những hệ gen đã được chia sẵn. - Vấn đề đặt ra là khi đưa vào một hệ gen mới bất kỳ, chúng ta phải tiến hành xác định những đoạn gen trong đó để tiến hành sắp hàng các đoạn gen. - Điều này đòi hỏi phải khi đưa vào hai hệ gen của hai sinh vật bất kỳ, phải tìm cách chia các hệ gen thành nhiều đoạn gen con liên tiếp sao cho khi sắp hàng với nhau chúng tạo được những cặp gen có độ tương đồng cao, tức là những cặp gen có nhiều khả năng là được biến đổi và tiến hoá từ cùng một đoạn gen trong hệ gen tổ tiên chung xa xưa của chúng.. - Như đã trình bày ở phần đầu, một số chương trình sắp hàng hệ gen hiện có tập trung vào việc tìm kiếm những vùng gen tương đồng trên hai hệ gen như MUAVE[1], SLAGAN[5] và nổi bật là BLASTZ[18]. - Trong khóa luận này, em xây dựng lên một hệ thống bắt cặp hệ gen hoàn chỉnh, dựa trên ý tưởng sử dụng BLASTZ như một bước tiền xử lý trước khi áp dụng thuật toán “Pairwise Alignment with Rearrangement”, qua đó khắc phục được nhược điểm hiện có của phương pháp này. - Cụ thể chúng ta sẽ sử dụng những vùng tương đồng mà BLASTZ nhận dạng được để tiến hành chia cắt hệ gen thành những đoạn gen ngắn liên tiếp, tạo thành đầu vào cho chương trình “Pairwise Alignment with Rearrangement” với “Fast Swapping” [20], trong quá trình này vấn đề cần lưu ý là phải tiến hành loại bỏ các đoạn trùng lặp, lựa chọn và giữ lại các cặp gen có độ tương đồng cao hơn. - Thuật toán “Pairwise Alignment with Rearrangement”, sử dụng phương pháp bắt cặp trình tự theo thuật toán quy hoạch động của Needleman – Wunsch [16]( Xem phần 1.2). - Đầu vào là hai hệ gen hoàn chỉnh bất kỳ.. - Tiến hành tách từng hệ gen thành một dãy các đoạn ADN thành phần nhỏ liên tục dựa vào các vùng có độ tương đồng cao xác định được bởi BLASTZ.. - Dựa trên thuật toán Gotoh và nhận xét của Ukkonen, xây dựng chương chình bắt cặp trình tự. - Cho biết thông tin về các đoạn gen đã bị dịch chuyển, bị đảo ngược, tồn tại ở hệ gen này nhưng không tồn tại ở hệ gen kia. - Sắp hàng hoàn chỉnh hai hệ gen.. - Nó được áp dụng thành công trong việc bắt cặp giữa hai hệ Gen Người và Chuột [18] 3.2.1. - Tìm kiếm những cặp đoạn ngắn ADN rất giống nhau ở cả hai hệ gen được gọi là hạt giống (seed).. - Tuy nhiên so với Gapped BLAST và các chương trình sắp hàng hệ gen khác, BLASTZ có những ba sự cải tiến quan trọng. - Chi phí chèn – xóa các ký tự gap được cho bởi một hàm tuyến tính. - Quá trình mở rộng dừng lại khi chi phí phạt vượt quá một ngưỡng cho phép (X. - Quá trình mở rộng tiến hành cho đến khi chi phí phạt vẫn chưa vượt quá ngưỡng cho phép (Y). - Bước 4 là thực hiện ghi nhận lại vị trí các đoạn tương đông tìm được sao cho phù hợp với 2 hệ gen ban đầu.. - Cuồi cùng, BLASTZ có 1 tùy chọn cho phép việc đảo ngược một hệ gen rồi tiến hành sắp hành lại với hệ gen còn lại. - dAB( Ai , Bj ) là chi phí bắt cặp giữa hai đoạn Ai và Bj trong đó Ai được sắp hàng với Bj.. - Ai , Bj ) là chi phí bắt cặp giữa hai đoạn Ai và Bj trong đó Ai được sắp hàng với kí tự gap · d-B ( Ai , Bj ) là chi phí bắt cặp giữa hai đoạn Ai và Bj trong đó Bj được sắp hàng với kí tự gap Với w(Ai, Bj) là chi phí khi sắp hàng ký tự Ai và ký tự Bj. - b Chi phí tối ưu để bắt cặp hai trình tự A và B là giá trị nhỏ nhất trong ba giá trí dAB(A, B), dA-(A, B) và d-B(A, B).