TIN SINH HỌC P48
Chia sẻ bởi Võ Phương Thảo |
Ngày 23/10/2018 |
49
Chia sẻ tài liệu: TIN SINH HỌC P48 thuộc Bài giảng khác
Nội dung tài liệu:
TÌM KiẾM TRÌNH TỰ GiỐNG NHAU BLAST
Học viên: Lê Thị Diệu Hiền
Lớp: Sinh Hoc Thực Nghiệm K14
Phần 3:
Tìm kiếm Trình tự giống nhau: BLAST
1. Bối cảnh và lý thuyết
1.1 Trình tự tìm kiếm tương tự
Trình tự tìm kiếm tương tự được sử dụng để tìm kiếm một cơ sở dữ liệu trình tự protein với tương đồng với một loại protein truy vấn. Các cơ sở dữ liệu protein chứa thứ tự của 100 triệu dư lượng. Để tìm kiếm với nhiều trình tự khác nhau, thời gian nhanh chóng trở thành một vấn đề quan trọng. Vì lý do này, đã có nhiều nỗ lực để sản xuất các thuật toán nhanh hơn so với lập trình. Trong trường hợp trình tự rất giống nhau, có một số phương pháp dựa trên máy tính mở rộng phù hợp với khoa học chính xác .
1.2 Một số kỹ thuật
Hầu hết các chương trình phổ biến là:
• BLAST
• FastA
1.2.1 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.
+Làm thế nào để sử dụng BLAST (http://www.ncbi.nlm.nih.gov/Education/BLASTinfo/tut1.html)
+Lựa chọn các chương trình BLAST
BLAST các trang tìm kiếm cho phép bạn chọn từ một vài chương trình khác nhau.
+Dưới đây là một bảng của các chương trình này.
- blastp: Đưa protein (AA) trình tự và so sánh chúng đối với các cơ sở dữ liệu protein NCBI
- blastn: Đưa nucleotide trình tự và so sánh chúng với các cơ sở dữ liệu nucleotide NCBI.
+ blastx: So sánh một chuỗi truy vấn nucleotide dịch trong tất cả các khung đọc đối với một cơ sở dữ liệu trình tự protein.
+ tblastn: So sánh một chuỗi truy vấn protein với một cơ sở dữ liệu trình tự nucleotide tự động dịch trong tất cả các khung đọc.
+ tblastx: So sánh các bản dịch sáu khung của một chuỗi truy vấn nucleotide với các bản dịch sáu khung của một cơ sở dữ liệu trình tự nucleotide. Xin lưu ý rằng chương trình tblastx không có thể được sử dụng với cơ sở dữ liệu nr trên trang Web BLAST bởi vì nó được tính toán chuyên sâu.
3.2.2 DNA và protein chuỗi
Trình tự DNA: Chọn một cơ sở dữ liệu axit nucleic. Chọn trong số các sinh vật cụ thể (ví dụ như: Agrobacterium), bao gồm (ví dụ, blastn nonredundant), hoặc chuyên ngành thiết lập (ví dụ, dbEST, dbSTS, GSS, HTG) cơ sở dữ liệu và sử dụng blastn chương trình BLAST.
Trình tự protein : Chọn một cơ sở dữ liệu protein hiện tại (ví dụ như SwissProt) sử dụng chương trình BLAST blastp.
Những hình ảnh cho thấy một ví dụ cho một protein. Thay vì một trình tự protein, nó cũng có thể sử dụng một chuỗi DNA.
Hình 1: Pubmed nhập cảnh của epoxide hydrolase từ radiobacter AD1 Agrobacterium.
Hình 2: Để sao chép và dán chuỗi vào blastp, định dạng FastA được sử dụng.
3.2.3 Kiểm tra các điểm liên kết và thống kê
Điểm số nguyên "S" của sự liên kết thường được tính bằng cách cộng điểm. Điểm cho mỗi vị trí của một liên kết được bắt nguồn từ một ma trận thay thế phổ biến nhất trong số này là các ma trận BLOSUM và PAM. Không giống như số điểm thô, tài khoản số điểm bit (được hiển thị ở bên phải trong cửa sổ đầu ra) cho các loại hình của hệ thống tính điểm được sử dụng, và do đó thông tin mới hơn. Điểm số bit được tính từ số điểm thô bằng cách bình thường với các biến số thống kê để xác định một hệ thống tính điểm.
Do đó, điểm số bit từ sự sắp xếp khác nhau, thậm chí cả những người sử dụng ma trận điểm khác nhau có thể được so sánh. Số điểm càng cao càng tốt sự liên kết, nhưng ý nghĩa của một sự liên kết không thể được rút ra từ số điểm một mình. Xem Thống kê dưới đây. Khoảng cách điểm số là tiêu cực. Kể từ khi một sự kiện đột biến duy nhất có thể gây ra chèn vào hoặc xóa nhiều hơn một dư lượng, sự hiện diện của khoảng cách là thường xuyên được gán cho ý nghĩa quan trọng hơn chiều dài của khoảng cách. Do đó khoảng cách bị trừng phạt nặng nề, trong khi một hình phạt nhẹ hơn là gán cho mỗi dư lượng tiếp theo trong khoảng cách.
Nguyên Điểm
Điểm số của một liên kết, S, được tính là tổng của điểm thay thế và khoảng cách. Thay thế (không giống hệt các axit amin ở một vị trí nhất định trong sự liên kết một) điểm được đưa ra bởi nhìn lên bảng (xem PAM, BLOSUM). Khoảng cách điểm số thường được tính là tổng của G, mở L, khoảng cách hình phạt và phần mở rộng khoảng cách hình phạt. Đối với một khoảng cách của n dài, chi phí khoảng cách sẽ được G + Ln. Việc lựa chọn chi phí khoảng cách, G và L là thực nghiệm, nhưng nó là phong tục để lựa chọn một giá trị cao cho G (10-15) và một giá trị thấp cho L (1-2).
Điểm rời rạc
`S giá trị có nguồn gốc từ S Điểm số nguyên liên kết, trong đó các thuộc tính thống kê của hệ thống tính điểm được sử dụng đã được đưa vào tài khoản. Bởi vì điểm số rời rạc đã được bình thường hoá quan đến hệ thống tính điểm, họ có thể được sử dụng để so sánh điểm liên kết từ tìm kiếm khác nhau.
S `= S - (lnK/ln2)
Lambda và K là các thông số phụ thuộc vào các hệ thống tính điểm (ma trận thay thế và chi phí khoảng cách) đã sử dụng [4-6].
E giá trị: giá trị mong đợi
Với giá trị E, ý nghĩa của điểm số có thể được đánh giá. Nó là một phương pháp để quyết định, nếu một liên kết sinh học có ý nghĩa và đưa ra bằng chứng cho tương đồng hay chỉ là sự liên kết tốt nhất giữa hai trình tự hoàn toàn không liên quan.
Số lượng các sự sắp xếp khác nhau với số điểm tương đương hoặc tốt hơn so với S được dự kiến sẽ xảy ra trong một tìm kiếm cơ sở dữ liệu bằng cơ hội. E thấp hơn các giá trị, quan trọng hơn số điểm.
E = mn * 2-S `
Các tham số m và n là độ dài của chuỗi truy vấn và cơ sở dữ liệu.
3.2.4 PSI-BLAST
Chức vụ BLAST lặp đi lặp lại cụ thể (PSI-BLAST) đề cập đến một tính năng của 2,0 BLAST trong đó một hồ sơ cá nhân (hoặc vị trí cụ thể ghi bàn ma trận, PSSM) được xây dựng (tự động) từ một liên kết nhiều chạm mức điểm cao nhất trong một tìm kiếm BLAST ban đầu. PSSM được tạo ra bằng cách tính toán điểm số vị trí cụ thể cho từng vị trí trong sự liên kết. Vị trí cao bảo tồn nhận được điểm cao và yếu vị trí bảo tồn nhận được điểm gần bằng không. Hồ sơ cá nhân được sử dụng để thực hiện một tìm kiếm BLAST tiếp theo và kết quả của mỗi "lặp đi lặp lại" được sử dụng để tinh chỉnh hồ sơ cá nhân. Điều này lặp đi lặp lại tìm kiếm kết quả chiến lược tăng nhạy cảm.
Tài liệu tham khảo
1. Chang, WI, Lawler, EL, xấp xỉ chuỗi kết hợp trong thời gian dự kiến sublinear. Kỷ yếu của Hội nghị chuyên đề thứ 31 hàng năm IEEE Khoa học máy tính Cơ sở năm 1990: p. 116-124.
2. Wu, S., Manber, U., Fast văn bản tìm kiếm các lỗi cho phép. Comunications của ACM, năm 1992. 35: p. 83-90.
3. Myers, EW, thuật toán sublinear để tìm kiếm từ khóa gần đúng. Algorithmica, năm 1994. 12: p. 345-374.
4. Altschul, SF, et al, Gapped BLAST và BLAST PSI: một thế hệ mới của chương trình tìm kiếm cơ sở dữ liệu protein. Axit nucleic Res năm 1997. 25 (17): p. 3389-402.
5. Altschul, SF và W. Gish, số liệu thống kê liên kết địa phương. Phương Pháp Enzymol, năm 1996. 266: p. 460-80.
6. Karlin, S. và SF Altschul, phương pháp đánh giá ý nghĩa thống kê các tính năng trình tự phân tử bằng cách sử dụng chương trình chấm điểm chung. Proc Natl Acad Sci U S A, 1990. 87 (6): p. 2264-8.
BLAST: http://www.ncbi.nlm.nih.gov/BLAST/
FastA: http://www.ebi.ac.uk/fasta33/index.html
Swiss-Prot: http://www.expasy.ch/sprot/sprot-top.html
NCBI databases: http://www.ncbi.nlm.nih.gov/entrez/query.fcgi?db=Nucleotide
Học viên: Lê Thị Diệu Hiền
Lớp: Sinh Hoc Thực Nghiệm K14
Phần 3:
Tìm kiếm Trình tự giống nhau: BLAST
1. Bối cảnh và lý thuyết
1.1 Trình tự tìm kiếm tương tự
Trình tự tìm kiếm tương tự được sử dụng để tìm kiếm một cơ sở dữ liệu trình tự protein với tương đồng với một loại protein truy vấn. Các cơ sở dữ liệu protein chứa thứ tự của 100 triệu dư lượng. Để tìm kiếm với nhiều trình tự khác nhau, thời gian nhanh chóng trở thành một vấn đề quan trọng. Vì lý do này, đã có nhiều nỗ lực để sản xuất các thuật toán nhanh hơn so với lập trình. Trong trường hợp trình tự rất giống nhau, có một số phương pháp dựa trên máy tính mở rộng phù hợp với khoa học chính xác .
1.2 Một số kỹ thuật
Hầu hết các chương trình phổ biến là:
• BLAST
• FastA
1.2.1 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.
+Làm thế nào để sử dụng BLAST (http://www.ncbi.nlm.nih.gov/Education/BLASTinfo/tut1.html)
+Lựa chọn các chương trình BLAST
BLAST các trang tìm kiếm cho phép bạn chọn từ một vài chương trình khác nhau.
+Dưới đây là một bảng của các chương trình này.
- blastp: Đưa protein (AA) trình tự và so sánh chúng đối với các cơ sở dữ liệu protein NCBI
- blastn: Đưa nucleotide trình tự và so sánh chúng với các cơ sở dữ liệu nucleotide NCBI.
+ blastx: So sánh một chuỗi truy vấn nucleotide dịch trong tất cả các khung đọc đối với một cơ sở dữ liệu trình tự protein.
+ tblastn: So sánh một chuỗi truy vấn protein với một cơ sở dữ liệu trình tự nucleotide tự động dịch trong tất cả các khung đọc.
+ tblastx: So sánh các bản dịch sáu khung của một chuỗi truy vấn nucleotide với các bản dịch sáu khung của một cơ sở dữ liệu trình tự nucleotide. Xin lưu ý rằng chương trình tblastx không có thể được sử dụng với cơ sở dữ liệu nr trên trang Web BLAST bởi vì nó được tính toán chuyên sâu.
3.2.2 DNA và protein chuỗi
Trình tự DNA: Chọn một cơ sở dữ liệu axit nucleic. Chọn trong số các sinh vật cụ thể (ví dụ như: Agrobacterium), bao gồm (ví dụ, blastn nonredundant), hoặc chuyên ngành thiết lập (ví dụ, dbEST, dbSTS, GSS, HTG) cơ sở dữ liệu và sử dụng blastn chương trình BLAST.
Trình tự protein : Chọn một cơ sở dữ liệu protein hiện tại (ví dụ như SwissProt) sử dụng chương trình BLAST blastp.
Những hình ảnh cho thấy một ví dụ cho một protein. Thay vì một trình tự protein, nó cũng có thể sử dụng một chuỗi DNA.
Hình 1: Pubmed nhập cảnh của epoxide hydrolase từ radiobacter AD1 Agrobacterium.
Hình 2: Để sao chép và dán chuỗi vào blastp, định dạng FastA được sử dụng.
3.2.3 Kiểm tra các điểm liên kết và thống kê
Điểm số nguyên "S" của sự liên kết thường được tính bằng cách cộng điểm. Điểm cho mỗi vị trí của một liên kết được bắt nguồn từ một ma trận thay thế phổ biến nhất trong số này là các ma trận BLOSUM và PAM. Không giống như số điểm thô, tài khoản số điểm bit (được hiển thị ở bên phải trong cửa sổ đầu ra) cho các loại hình của hệ thống tính điểm được sử dụng, và do đó thông tin mới hơn. Điểm số bit được tính từ số điểm thô bằng cách bình thường với các biến số thống kê để xác định một hệ thống tính điểm.
Do đó, điểm số bit từ sự sắp xếp khác nhau, thậm chí cả những người sử dụng ma trận điểm khác nhau có thể được so sánh. Số điểm càng cao càng tốt sự liên kết, nhưng ý nghĩa của một sự liên kết không thể được rút ra từ số điểm một mình. Xem Thống kê dưới đây. Khoảng cách điểm số là tiêu cực. Kể từ khi một sự kiện đột biến duy nhất có thể gây ra chèn vào hoặc xóa nhiều hơn một dư lượng, sự hiện diện của khoảng cách là thường xuyên được gán cho ý nghĩa quan trọng hơn chiều dài của khoảng cách. Do đó khoảng cách bị trừng phạt nặng nề, trong khi một hình phạt nhẹ hơn là gán cho mỗi dư lượng tiếp theo trong khoảng cách.
Nguyên Điểm
Điểm số của một liên kết, S, được tính là tổng của điểm thay thế và khoảng cách. Thay thế (không giống hệt các axit amin ở một vị trí nhất định trong sự liên kết một) điểm được đưa ra bởi nhìn lên bảng (xem PAM, BLOSUM). Khoảng cách điểm số thường được tính là tổng của G, mở L, khoảng cách hình phạt và phần mở rộng khoảng cách hình phạt. Đối với một khoảng cách của n dài, chi phí khoảng cách sẽ được G + Ln. Việc lựa chọn chi phí khoảng cách, G và L là thực nghiệm, nhưng nó là phong tục để lựa chọn một giá trị cao cho G (10-15) và một giá trị thấp cho L (1-2).
Điểm rời rạc
`S giá trị có nguồn gốc từ S Điểm số nguyên liên kết, trong đó các thuộc tính thống kê của hệ thống tính điểm được sử dụng đã được đưa vào tài khoản. Bởi vì điểm số rời rạc đã được bình thường hoá quan đến hệ thống tính điểm, họ có thể được sử dụng để so sánh điểm liên kết từ tìm kiếm khác nhau.
S `= S - (lnK/ln2)
Lambda và K là các thông số phụ thuộc vào các hệ thống tính điểm (ma trận thay thế và chi phí khoảng cách) đã sử dụng [4-6].
E giá trị: giá trị mong đợi
Với giá trị E, ý nghĩa của điểm số có thể được đánh giá. Nó là một phương pháp để quyết định, nếu một liên kết sinh học có ý nghĩa và đưa ra bằng chứng cho tương đồng hay chỉ là sự liên kết tốt nhất giữa hai trình tự hoàn toàn không liên quan.
Số lượng các sự sắp xếp khác nhau với số điểm tương đương hoặc tốt hơn so với S được dự kiến sẽ xảy ra trong một tìm kiếm cơ sở dữ liệu bằng cơ hội. E thấp hơn các giá trị, quan trọng hơn số điểm.
E = mn * 2-S `
Các tham số m và n là độ dài của chuỗi truy vấn và cơ sở dữ liệu.
3.2.4 PSI-BLAST
Chức vụ BLAST lặp đi lặp lại cụ thể (PSI-BLAST) đề cập đến một tính năng của 2,0 BLAST trong đó một hồ sơ cá nhân (hoặc vị trí cụ thể ghi bàn ma trận, PSSM) được xây dựng (tự động) từ một liên kết nhiều chạm mức điểm cao nhất trong một tìm kiếm BLAST ban đầu. PSSM được tạo ra bằng cách tính toán điểm số vị trí cụ thể cho từng vị trí trong sự liên kết. Vị trí cao bảo tồn nhận được điểm cao và yếu vị trí bảo tồn nhận được điểm gần bằng không. Hồ sơ cá nhân được sử dụng để thực hiện một tìm kiếm BLAST tiếp theo và kết quả của mỗi "lặp đi lặp lại" được sử dụng để tinh chỉnh hồ sơ cá nhân. Điều này lặp đi lặp lại tìm kiếm kết quả chiến lược tăng nhạy cảm.
Tài liệu tham khảo
1. Chang, WI, Lawler, EL, xấp xỉ chuỗi kết hợp trong thời gian dự kiến sublinear. Kỷ yếu của Hội nghị chuyên đề thứ 31 hàng năm IEEE Khoa học máy tính Cơ sở năm 1990: p. 116-124.
2. Wu, S., Manber, U., Fast văn bản tìm kiếm các lỗi cho phép. Comunications của ACM, năm 1992. 35: p. 83-90.
3. Myers, EW, thuật toán sublinear để tìm kiếm từ khóa gần đúng. Algorithmica, năm 1994. 12: p. 345-374.
4. Altschul, SF, et al, Gapped BLAST và BLAST PSI: một thế hệ mới của chương trình tìm kiếm cơ sở dữ liệu protein. Axit nucleic Res năm 1997. 25 (17): p. 3389-402.
5. Altschul, SF và W. Gish, số liệu thống kê liên kết địa phương. Phương Pháp Enzymol, năm 1996. 266: p. 460-80.
6. Karlin, S. và SF Altschul, phương pháp đánh giá ý nghĩa thống kê các tính năng trình tự phân tử bằng cách sử dụng chương trình chấm điểm chung. Proc Natl Acad Sci U S A, 1990. 87 (6): p. 2264-8.
BLAST: http://www.ncbi.nlm.nih.gov/BLAST/
FastA: http://www.ebi.ac.uk/fasta33/index.html
Swiss-Prot: http://www.expasy.ch/sprot/sprot-top.html
NCBI databases: http://www.ncbi.nlm.nih.gov/entrez/query.fcgi?db=Nucleotide
* Một số tài liệu cũ có thể bị lỗi font khi hiển thị do dùng bộ mã không phải Unikey ...
Người chia sẻ: Võ Phương Thảo
Dung lượng: |
Lượt tài: 1
Loại file:
Nguồn : Chưa rõ
(Tài liệu chưa được thẩm định)