BLAST

Bài này viết về BLAST (viết hoa), một chương trình dùng trong tin sinh học. Về các nghĩa khác, xem tại blast (định hướng)

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ạy, BLAST 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. 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 là 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.

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. 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

Ý 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.

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.
  Một điểm chú ý ở đây là phiên bản gốc của BLAST không cho phép chỗ trống (gap) trong quá trình mở rộng, nhưng ở phiên bản mới hơn đã cho phép chỗ trống.
  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.
  Ví dụ, với chuỗi AGTTAHTQ và ACFTAQAC với Hit TAH và TAQ sẽ được mở rộng như sau:

AGTTAHTQ
xxx||||x
ACFTAQAC

Những cặp HSP đã tìm được được BLAST sắp xếp theo giá trị đánh giá giảm dần, đưa ra màn hình, và thực hiện phần đánh giá thống kê trên những cặp HSP này.

Trong phần đánh giá thống kê, BLAST dựa trên cơ sở đánh giá của một cặp HSP để tính ra một giá trị gọi là ''Bit-Score'', giá trị này không phụ thuộc vào ma trận thay thế và được sử dụng để đánh giá chất lượng của các bắt cặp. Giá trị càng cao chứng tỏ khả năng tương tựu của các bắt cặp càng cao. Ngoài ra BLAST tính toán một giá trị trông đợi E-Score (Expect-Score) phụ thuộc vào Bit-Score. Giá trị E-Score này thể hiện xác suất ngẫu nhiên của các bắt cặp, giá trị càng thấp càng chứng tỏ những bắt cặp này được phát sinh theo quy luật tự nhiên, ít phụ thuộc vào tính ngẫu nhiên. (Xem thêm về đột biến (Mutation)).

Ứ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.

Một vài ví dụ về những câu hỏi mà các nhà nghiên cứu dùng BLAST để tìm câu trả lời

• Chủng loại vi khuẩn nào có các protein có liên hệ về giống loài với một loại protein khác mà có chuỗi amino-acid mà ta đã biết không?
• Chuỗi DNA mà ta vừa sắp xếp có nguồn gốc từ đâu?
• 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?

BLAST còn được dùng kết hợp với các giải thuật khác có đòi hỏi sự so trùng chuỗi gần đúng.

Giải thuật BLAST và các chương trình máy tính hiện thực nó đã được phát triển bởi Stephen Altschul, Warren Gish, David Lipman tại U.S. National Center for Biotechnology Information (NCBI), Webb Miller tại Đại học Bang Pennsylvania, và Gene Myers tại Đại học Arizona. Nó có sẵn trên web tại [1]. Các hiện thực khác có thể tìm thấy tại [2] Lưu trữ 2011-07-20 tại Wayback Machine và [3] Lưu trữ 2006-02-22 tại Wayback Machine

Bài báo gốc "Altschul, SF, W Gish, W Miller, EW Myers, and DJ Lipman. Basic local alignment search tool. J Mol Biol 215(3):403-10, 1990." được đánh giá là ấn bản có giá trị nhất trong thập niên 1990s.

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

Chương trình BLAST có thể được tải về và chạy dưới dạng tiện ích dòng lệnh tên là "blastall" hoặc có thể truy xuất miễn phí qua web. Máy chủ web chứa BLAST, đăng ký bởi NCBI, cho phép mọi người dùng trình duyệt web để thực thi tìm kiếm sự giống nhau trên các cơ sở dữ liệu các protein và DNA được cập nhật liên tục với hầu hết các chuỗi mới được tìm thấy trên các thực thể sống.

Một đối trọng với tốc độ cực kì nhanh so với BLAST nhằm so sánh các chuỗi nucleotide với genome là BLAT (Blast Like Alignment Tool). Một phiên bản được thiết kế cho việc so sánh nhiều genome hay chromosomes lớn là BLASTZ.

Các phiên bản BLAST song song được hiện thực dùng MPI,Pthreads và có thể chạy trên các hệ điều hành khác nhau bao gồm Windows, Linux, Solaris, AIX

BLAST thực sự là một họ các chương trình (bao gồm cả chương trình blastall). Sau đây là một số chương trình trong họ, được sắp xếp theo thứ tự quan trọng của nó:

• Nucleotide-nucleotide BLAST (blastn): Chương trình này, khi đưa vào một DNA truy vấn, sẽ trả về các chuỗi DNA gần giống nhất từ cơ sở dữ liệu DNA mà người dùng chỉ định.
• Protein-protein BLAST (blastp): Chương trình này, khi đưa vào một protein truy vấn, sẽ trả về các chuỗi protein gần giống nhất từ cơ sở dữ liệu protein mà người dùng chỉ đị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ả hai 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.

Tham khảo

• Hans-Joachim Böckenhauer, Dirk Bongartz, (2003) Algorithmische Grundlagen der Bioinformatik ISBN 3-519-00398-8
• Dan Gusfield, (1997) Algorithms on strings, trees, and sequences ISBN 0-521-58519-8
• Warren J. Ewens, Gregory R. Grant, (2005) Statistical Methods in Bioinformatics - An Introduction ISBN 0-387-40082-6

Xem thêm

• Thuật toán FASTA
• Ma trận thay thế BLOSUM^[liên kết hỏng]
• Ma trận thay thế PAM^[liên kết hỏng]
• Đột biến

Các liên kết ngoài

• NCBI-BLAST Home page
• NCBI-BLAST Tutorial
• WU-BLAST Lưu trữ 2011-07-20 tại Wayback Machine (Một hiện thực khác của BLAST do Warren Gish tại Đại học Washington)
• FSA-BLAST Lưu trữ 2006-02-22 tại Wayback Machine (Một phiên bản mới, nhanh hơn nhưng vẫn chính xác của BLAST dựa trên những cải tiến giải thuật mới công bố gần đây)
• BioASP BLAST Lưu trữ 2005-09-15 tại Wayback Machine (Bioinformatics Application Services Platform, running BLAST)
• Parallel BLAST Lưu trữ 2006-03-04 tại Wayback Machine[A dual scheduling BLAST tested on the Blue Gene/L)

Tham khảo