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.