BLAST

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:
AGTTAHTQ&lt;br&gt;
xxx||||x&lt;br&gt;
ACFTAQAC&lt;br&gt; 
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
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 . Các hiện thực khác có thể tìm thấy tại và 
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ó: