TIN SINH HỌC P27

Tiểu luận tin sinh học
Chuyên đề
TÌM KIẾM CHUỖI TƯƠNG ĐỒNG ĐỐI VỚI DNA VÀ PROTEIN

GVHD: TS.Võ Văn Toàn
HVTH: Đoàn Thị Hoài Hương
Lớp: Cao học SHTN khóa 12
TIN SINH H?C
Trong tin sinh học, Basic Local Alignment Search Tool, hay BLAST, là một giải thuật để so sánh các chuỗi sinh học, như các chuỗi amino-acid của các protein hay của các chuỗi DNA khác nhau. Khi được cung cấp một thư viện hay cơ sở dữ liệu các chuỗi đó, một tìm kiếm BLAST sẽ cho phép nhà nghiên cứu tìm kiếm các chuỗi con giống với chuỗi có sẵn mà ta quan tâm.
Ví dụ, tiếp sau việc khám phá ra các gen mà trước đây chưa biết ở chuột (loại mus musculus), một nhà khoa học sẽ thường thực thi một tìm kiếm BLAST trên genome người để tìm kiếm xem liệu con người có mang các gen giống vậy không; BLAST sẽ xác định các chuỗi nào trong genome người mà giống với gen chuột dựa trên sự giống nhau của chuỗi.
CH?C NANG C?A BLAS
Ý tưởng của BLAST dựa trên cơ sở xác suất rằng những chuỗi bắt cặp trình tự (alignment) thường sở hữu nhiều đoạn chuỗi con có tính tương tự cao. Những chuỗi con này được mở rộng để tăng tính tương tự trong quá trình tìm kiếm.
BLAST tìm kiếm những bắt cặp trình tự có điểm số cao giữa chuỗi truy vấn và các chuỗi trong cơ sở dữ liệu bằng cách sử dụng phương pháp dựa trên kinh nghiệm (heuristic) để có thể có tìm được kết quả gần tốt bằng với giải thuật Smith-Waterman.

Tuy nhiên, thuật toán bắt cặp trình tự tối ưu của Smith-Waterman là quá chậm khi tìm kiếm trong một cơ sở dữ liệu gen quá lớn như Ngân Hàng Gen (GenBank). Bởi vậy, giải thuật BLAST dùng một hướng tiếp cận heuristic, dù ít chính xác hơn Smith-Waterman nhưng lại cho tốc độ nhanh hơn gấp 50 lần.
Tốc độ và sự chính xác tương đối của BLAST là những cải tiến kĩ thuật quan trọng của các chương trình BLAST và những điều đó cho thấy lí do vì sao công cụ này lại là công cụ tìm kiếm phổ biến nhất trong tin sinh học.



Thuật toán của BLAST có 2 phần
- một phần tìm kiếm
- và một phần đánh giá thống kê dựa trên kết quả tìm được.

Thuật toán tìm kiếm của BLAST bao gồm 3 bước sau:
Bước 1: BLAST tìm kiếm các chuỗi con ngắn với chiều dài cố định W có tính tương tự cao (không cho phép khoảng trống gaps) giữa chuỗi truy vấn và các chuỗi trong cơ sở dữ liệu.

Những chuỗi con với chiều dài W được BLAST gọi là một từ (word).
Giá trị W tham khảo cho Protein là 3 và DNA là 11.
Những chuỗi con này được đánh giá cho điểm dựa trên ma trận thay thế (Substitutionsmatrix) BLOSUM hoặc PAM, những chuỗi con nào có số điểm lớn hơn một giá trị ngưỡng T (threshold value) thì được gọi là tìm thấy và được BLAST gọi là Hits.
Ví dụ, khi cho sẵn các chuỗi AGTTAH và ACFTAQ và một từ có chiều dài W = 3, BLAST sẽ xác định chuỗi con TAH và TAQ với số điểm theo ma trận PAM là 3 + 2 + 3 = 8 và gọi chúng là một Hit.
Bước 2: BLAST tiếp tục tìm kiếp những cặp Hits tiếp theo dựa trên cơ sở những Hit đã tìm được trong bước 1. Những cặp Hits này được BLAST giới hạn bởi một giá trị cho trước d, gọi là khoảng cách giữa những Hits. Những cặp Hits có khoảng cách lớn hơn d sẽ bị BLAST bỏ qua.
Giá trị d phụ thuộc vào độ dài W ở bước 1, ví dụ nếu W = 2 thì giá trị d đề nghị là d = 16.
Bước 3: Cuối cùng BLAST mở rộng những cặp Hits đã tìm được theo cả hai chiều và đồng thời đánh số điểm. Quá trình mở rộng kết thúc khi điểm của các cặp Hits không thể mở rộng thêm nữa.

Những cặp Hits sau khi mở rộng có điểm số cao hơn một giá trị ngưỡng S (threshold value) thì được BLAST gọi là "cặp điểm số cao" (high scoring pair) HSP.


Các biến thể của BLAST

Nucleotide-nucleotide BLAST (blastn): Chuong trỡnh n�y, khi dua v�o m?t DNA truy v?n, s? tr? v? cỏc chu?i DNA g?n gi?ng nh?t t? co s? d? li?u DNA m� ngu?i dựng ch? d?nh.
Protein-protein BLAST (blastp): Chuong trỡnh n�y, khi dua v�o m?t protein truy v?n, s? tr? v? cỏc chu?i protein g?n gi?ng nh?t t? co s? d? li?u protein m� ngu?i dựng ch? d?nh.
Position-Specific Iterative BLAST (PSI-BLAST): Một trong những chương trình BLAST mới nhất, chương trình này dùng để tìm kiếm các mối quan hệ xa (distant relative) của một protein. Trước tiên, một danh sách các protein liên quan sẽ được tạo ra. Sau đó, những protein này được kết hợp thành một "profile" dưới dạng chuỗi trung bình (average sequence).
Một câu truy vấn tới một cơ sở dữ liệu protein sẽ được thực thi nhờ profile này, và một nhóm lớn hơn các protein được tìm thấy. Nhóm lớn này lại được dùng để tạo ra một profile khác, và quá trình này cứ lặp lại.
Bằng cách thêm các protein liên quan vào việc tìm kiếm, PSI-BLAST trở nên tốt hơn trong việc lựa ra các mối quan hệ tiến hóa cách xa nhau hơn là phần mềm chuẩn protein-protein BLAST.
Nucleotide-protein 6-frame translation (blastx): Chương trình này so sánh các sản phẩm chuyển đổi (trừu tượng) sang 6-khung của một chuỗi nucleotide truy vấn (cả 2 dải) với một cơ sở dữ liệu chuỗi protein. Quá trình này có thể rất chậm.
Nucleotide-nucleotide 6-frame translation (tblastx): Chương trình này là chậm nhất trong họ BLAST. Nó chuyển chuỗi nucleotide truy vấn thành mọi 6-khung (frame) có thể và so sánh các proteins tạo thành. Mục tiêu của tblastx là tìm kiếm mối quan hệ rất xa giữa các chuỗi nucleotide.

Protein-nucleotide 6-frame translation (tblastn): Chương trình này chuyển cơ sở dữ liệu đích thành mọi 6-khung (frame) và so sánh với chuỗi protein truy vấn .
Large numbers of query sequences (megablast): Khi so sánh một số lượng lớn các chuỗi đầu vào qua chỉ một BLAST dạng dòng lệnh, "megablast" là nhanh hơn rất nhiều so với chạy BLAST nhiều lần.

Ứng dụng

BLAST là một trong những chương trình được sử dụng rộng rãi nhất trong tin sinh học, có lẽ là vì nó giúp giải quyết một vấn đề cơ bản và giải thuật tập trung vào tốc độ hơn tính chính xác.
Nó tập trung vào tốc độ vì đó là quyết định đến tính thực tiễn của giải thuật do cơ sở dữ liệu về genome người là cực kì lớn, mặc dù các giải thuật về sau có thể nhanh hơn.
BLAS được sử dụng để tìm kiếm các dữ liệu trình tự của protein hoặc DNA mà nó có tương đồng với nhau.
BLAS gồm 2 phần mềm chính hiện nay:
BLAST Pr: Tìm kiếm chuỗi trình tự tương đồng về protein
BLAS L dùng để so sánh các chuỗi nucleotit
Cách sử dụng BLAS
BLAST sẽ tìm kiếm các chuỗi con trong câu truy vấn mà giống với các chuỗi con trong cơ sở dữ liệu chuỗi. Thông thường, khi sử dụng, chuỗi truy vấn nhỏ hơn rất nhiều so với cơ sở dữ liệu, ví dụ: chuỗi truy vấn có thể chỉ gồm 1 nghìn nucleotide trong khi cơ sở dữ liệu chuỗi có hàng tỉ nucleotide.

Để chạy BLAS cần đầu vào là 2 chuỗi: một là chuỗi truy vấn (hay còn gọi là chuỗi đích) và một cơ sở dữ liệu chuỗi.
Đầu tiên: Xác định mã số truy cập của một trình tự
Mã số truy cập của một trình tự là mã số do các nhà quản trị CSDLSH đặt cho một trình tự, thường có dạng :
8 ký tự : 2 chữ và 6 số ví dụ như AY690640
6 ký tự : 1 chữ và 5 dố ví dụ như U20068

Sau đó lấy mã số truy cập tìm được dán vào phần mềm BLAS để biết được
Protein đó có liên hệ về giống loài với một loại protein khác có chuỗi amino-acid mà ta đã biết không?
Hay chuỗi DNA mà ta vừa sắp xếp có nguồn gốc từ đâu?
Hay có gen nào khác dùng để mã hóa các protein có cấu trúc hay dáng dấp gần với cái mà ta vừa xác định không?
- Ứng dụng BLAS trong việc xây dựng cây phát sinh chủng loài: Thông tin từ các nucleotit và các chuỗi protein có thể được sử dụng để suy ra mối quan hệ phát sinh loài. Bởi vì cần nhiều đột biến nhỏ tích lũy thành đột biến lớn để có thể thay đổi chuỗi này thành chuỗi khác. Vì vậy một cặp so sánh giống nhau hơn về trình tự hay có ít hơn các thay đổi có thể cho thấy chúng có tổ tiên gần nhau hơn. Do vậy chúng ta có thể xây dựng được cây phát sinh chủng loại
B1: mở trình duyệt NCBI  chọn BAST
Cick
Program query Database
1
Blastn: DNA DNA
1
Blastp: protein protein
6
Blastx: DNA protein

Bastn:
Ch?n co s? d? li?u
Kết Quả
Thể hiện bằng sơ đồ đồ họa (a); mô tả cụ thể (b); thể hiện các trình tự tương đồng (b)
Tiến hành tương tự với Bastp ta có kết quả:
Blastx: dịch mã protein từ trình tự DNA nhập vào