sequence analysis
Summary: sequence analysis
SỰ TƯƠNG ĐỒNG TRÌNH TỰ
Giới thiệu
Trong Bioinformatics, sắp gióng cột trình tự được dùng để sắp xếp các trình tự DNA, RNA hoặc protein để xác định những vùng tương đồng có thể có sự bảo tồn về cấu trúc, chức năng hoặc có mối quan hệ tiến hóa giữa chúng với nhau. Trong quá trình sắp gióng cột, các khoảng trống (gap, được kí hiệu bằng dấu –) được chèn vào giữa vị trí các nucleotide hay amino acid để các trình tự có sự tương tự nhau nhiều nhất trong mỗi cột (Hình 1.1.)
***SORRY, THIS MEDIA TYPE IS NOT SUPPORTED.***
Figure 1
Hình 1.1. Kết quả của một quá trình sắp gióng cột bởi chương trình ClustalW giữa các protein Zinc finger ở người.
Nếu hai trình tự được sắp gióng cột có chung một tổ tiên, các gap biểu thị cho các đột biến thêm vào hay mất đi của nucleotide trong quá trình tiến hóa. Trong sắp gióng cột các trình tự protein, mức độ tương đồng giữa các amino acid biểu thị cho sự bảo tồn của một vùng đặc biệt trong trình tự. Sắp gióng cột giữa các trình tự protein cũng cho thấy có sự thay thế các amino acid. Sự thay thế bởi các amino acid có chuỗi bên có đặc tính sinh hóa tương tự nhau (sự thay thế có tính bảo tồn) tại một vùng đặc biệt của trình tự giải thích cho vai trò quan trọng về cấu trúc hoặc chức năng của vùng đó.
Bằng phương pháp thủ công, có thể dễ dàng sắp gióng cột những trình tự rất ngắn hoặc rất tương đồng với nhau. Tuy nhiên, trên thực tế, các trình tự protein, đặc biệt là các trình tự nucleotide rất dài, đòi hỏi phải có các công cụ, phần mềm, thuật toán để giải quyết vấn đề này. Trong trường hợp này, việc sắp gióng cột được thực hiện bằng hai cách: sắp gióng cột toàn bộ (global alignment) và sắp gióng cột cục bộ (local alignment). Sắp gióng cột toàn bộ nhằm gióng cột toàn bộ chiều dài của tất cả các trình tự, thường được sử dụng khi các trình tự khá tương đồng và có chiều dài tương đương nhau. Thuật toán Needleman-Wunsch thường được sử dụng cho việc sắp gióng cột toàn bộ. Trong sắp gióng cột cục bộ, chỉ một phần của trình tự được xác định sự tương đồng. Phương pháp này thường được sử dụng khi các trình tự không có mức tương đồng cao hoặc được cho là có những vùng motif bảo tồn. Sắp gióng cột cục bộ thường sử dụng thuật toán Smith-Waterman. Hình 1.2. minh họa sự khác biệt giữa sắp gióng cột toàn trình tự và sắp gióng cột cục bộ.
***SORRY, THIS MEDIA TYPE IS NOT SUPPORTED.***
Hình 1.2. Sắp gióng cột toàn bộ và sắp gióng cột cục bộ
Sắp gióng cột cặp trình tự (Pairwise Alignment – PA)
Nguyên tắc sắp gióng cột toàn bộ bằng thuật giải Needleman-Wunsch
Thuật giải sắp gióng cột trên toàn bộ chiều dài của hai trình tự được Needleman và Wunsh đưa ra vào năm 1970
Giả sử có hai trình tự A và B. Để việc sắp gióng cột cặp trình tự AB có điểm cao nhất (tức cho kết quả tương đồng cao nhất), một ma trận F hai chiều được tạo ra. Mỗi vị trí trong ma trận được kí hiệu là Fij. Điểm cho sắp gióng cột được đặc trưng bằng ma trận tương đồng, trong đó, S(i,j) là điểm tương đồng giữa hai kí tự i và j. d là một điểm phạt tuyến tính cho các gap (gap penalty). Trong ma trận, trục hoành là các kí tự của trình tự A (có chiều dài x), các kí tự của trình tự B (có chiều dài y) được biểu diễn trên trục tung.
Khởi tạo ma trận F như sau:
F(11) = 0
F(1j) = 0
F(i1) = 0
Tiếp theo tiến hành lấp đầy ma trận F từ đỉnh bên trái tới đáy bên phải. Giá trị tại vị trí F(i,j) sẽ được tính dựa trên điểm tại F(i-1,j-1), F(i-1,j), và F(i,j-1) theo công thức:
***SORRY, THIS MEDIA TYPE IS NOT SUPPORTED.***
Nếu F(i, j) = F(i-1, j-1) + s(xi,yj), xi sẽ được sắp gióng hàng với yj. Nếu F(i,j) = F(i-1,j) – d, xi sắp gióng hàng với một khoảng trống. Nếu F(i,j) = F(i,j-1) – d, yj sắp gióng hàng với một khoảng trống. Công thức này sẽ được tính lặp lại cho đến khi tất cả các giá trị F(i,j) được xác định (hai trường hợp đặc biệt F(i,0) và F(0,j) được xác định bằng công thức F(i,0) = -id, F(0,j) = -jd).
Như vậy giá trị F(i,j) cuối cùng là điểm tốt nhất cho sắp gióng cột hai trình tự. Bước tiếp theo chúng ta phải xác định con đường đi đến giá trị cuối cùng này. Quá trình này gọi là traceback, bắt đầu từ giá trị cuối cùng của ma trận. Trong mỗi bước traceback, chúng ta sẽ di chuyển ô hiện tại (i,j) đến một trong 3 ô (i-1,j-1), (i-1,j) hay (i,j-1) và đặt cặp ký tự vào hàng gióng hiện tại. xi và yi sẽ được gióng với nhau nếu từ ô (i,j) di chuyển đến ô (i-1,j-1), xi gióng với “–” nếu di chuyển đến ô (i-1,j) và yj gióng với ‘-‘ nếu di chuyển đến ô (i,j-1) và kết thúc khi i = j = 0.
Ví dụ cho hai trình tự sau:
s :GACGGATTAGAA
t :GATCGGAATAG
Điểm số cho các kí tự như sau: +1 nếu hai kí tự giống nhau, -1 nếu hai kí tự khác nhau và điểm phạt khi một kí tự bắt cặp với một gap là -2.
G A – C G G A T T A G A A
G A T C G G A A T A G – –
1 1 -2 1 1 1 1 -1 1 1 1 -2 -2
Như vậy, điểm tổng cộng cho quá trình sắp gióng cột của hai trình tự trên là:
1+1-2+1+1+1+1-1+1+1+1-2-2=2
Ta có ma trận F cho hai trình tự này trên Bảng 1.1.
Bảng 1.1. Ma trận cho sắp gióng cột hai trình tự
***SORRY, THIS MEDIA TYPE IS NOT SUPPORTED.***
Và kết quả sắp gióng cột cho ra:
G A – C G G A T T A G A A
G A – C G G A A T A G – –
1 1 -2 1 1 1 1 -1 1 1 1 -2 -2
Comments, questions, feedback, criticisms?
Send feedback
- E-mail the author of the module, sequence analysis
Footer
More about this content: Metadata | Version History
This work is licensed by Quy Vo under a Creative Commons Attribution License (CC-BY 2.0).
Last edited by Quy Vo on Jun 18, 2007 11:35 pm GMT-5.