Báo cáo Nguồn gốc và ý nghĩa của thuật toán

BÁO CÁO CHUYÊN ĐỀ 8 GV:NGÔ CÔNG THẮNG SV:VŨ THỊ THÙY LINH NỘI DUNG I.Nguồn gốc và ý nghĩa của thuật toán 1.Nguồn gốc 2.Ý nghĩa của thuật toán II. Thuật toán +Phần 1:Thuật toán tìm kiếm + Phần 2:Đánh giá thống kê I.Nguồn gốc và ý nghĩa của thuật toán Nguồn gốc -Thuật toán blast và các chương trình máy tính thực hiện thuật toán được phát triển bởi Stephen Altschul,  Warren Gish, David Lipman tại Mỹ Trung tâm quốc gia thông tin Công nghệ sinh học (NCBI), Webb Miller tại Đại học Pennsylvania, và Gene Myers tại Đại học Arizona. Nó có sẵn trên trang web NCBI 2. Ý nghĩa của thuật toán -Trả lời các câu hỏ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. -Xác định loài +Với việc sử dụng BLAST, bạn có thể có thể xác định chính xác một loài hoặc tìm sự tương đồng giữa các loài. Điều này có thể là hữu ích, ví dụ như khi bạn làm việc với một chuỗi DNA từ một loài chưa biết. -Thành lập Phylogeny +Sử dụng kết quả nhận được thông qua BLAST bạn có thể tạo một cây phát sinh loài bằng cách sử dụng trang web BLAST. -Lập bản đồ AND +Khi làm việc với một loài được biết đến, và tìm cách để chuỗi một gen ở một vị trí không rõ, BLAST có thể so sánh các vị trí nhiễm sắc thể của chuỗi quan tâm, để chuỗi liên quan trong các cơ sở dữ liệu (s). -So sánh +Khi làm việc với các gen, BLAST có thể xác định vị trí gen phổ biến trong hai loài có liên quan, và có thể được sử dụng để chú thích bản đồ từ một trong những sinh vật khác. II. Thuật toán 1. Bài toán -Cho một chuỗi. Tìm trong ngân hàng gen các chuỗi có độ tương đồng với chuỗi đã cho. Các chuỗi tìm được được xắp xếp theo chiều giảm dần về mức độ tương đồng với chuỗi đã cho -Input: +một chuỗi truy vấn,cơ sở dữ liệu chuỗi +w: chiều dài của một chuỗi con (đối với protein thường là w=3, đối với DNA w=11) +d:khoảng các giữa các Hits (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 ) +Ma trận thay thế (Substitutionsmatrix) BLOSUM hoặc PAM BLOSUM PAM -Output: Các chuỗi có độ tương đồng cao với chuỗi đã cho *Thuật toán: 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 +Phần 1: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:A G T T A H T Qx x x | | | | x A C F T A Q A C +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. + Phần 2: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. Tài liệu tham khảo - - - -