Loading AI tools
生物信息學中的算法 来自维基百科,自由的百科全书
生物信息學中,BLAST(英語:Basic Local Alignment Search Tool)它是一個用來比對生物序列的一級結構(如不同蛋白質的氨基酸序列或不同基因的DNA序列)的算法。 已知一個包含若干序列的資料庫,BLAST可以讓研究者在其中尋找與其感興趣的序列相同或類似的序列。 例如如果某種非人動物的一個以前未知的基因被發現,研究者一般會在人類基因組中做一個BLAST搜索來確認人類是否包含類似的基因(通過序列的相似性)。BLAST演算法以及實現它的程序由美國國家生物技術信息中心(NCBI)的Eugene Myers、Stephen Altschul、Warren Gish、David J. Lipman及Webb Miller博士開發的。
研究者利用BLAST來解决的其他問题有:
……等等。
BLAST是一個被廣泛使用於分析生物資訊的程式,因為它可以兼顧我們在做搜尋時的速度以及搜尋結果的精確度。因為當我們所要搜尋的目標資料庫非常龐大的時候,速度就變成一項很需要考量的因素。在像BLAST和FASTA這些快速算法被開發之前,我們是使用动态规划算法來作資料庫的序列搜尋,這真的非常的耗時。BLAST使用啟發式搜索來找出相關的序列,在速度上比完全只使用动态规划大約快上50倍左右,不過它不像动态规划能夠保證搜尋到的序列(Database sequence)和所要找的序列(Query sequence)之間的相關性,BLAST的工作就是盡可能找出資料庫中和所要查詢的序列相關的資訊而已,精確度稍微低一點。此外,BLAST比FASTA更快速,因為BLAST只對比較少出現或是較重要的一些關鍵字作更進一步的分析,而FASTA是考慮所有共同出現在所要搜尋的序列和目標序列的字。從下面介紹的演算法可以更進一步的瞭解。
這邊我們以蛋白質對蛋白質序列搜尋所用的程式BLASTP之實做的步驟,來了解BLAST這程式的主要思想。[1]
由NCBI管理的BLAST网站允许任何人使用浏览器来在包含大部分新测序的物种的不停更新的DNA或蛋白质数据库中进行相似性搜索。这个服务器包含很多程序,最重要的几个如下:
已知一个蛋白的氨基酸序列,通过这个程序可以找出在用户选择的蛋白质数据库中与其最相似的序列。
已知一段已經轉錄的序列,藉由這個程式對這段序列的6個ORF對上用戶所選擇的蛋白質資料庫, 比對最相似的序列。其功用可以找出在基因體DNA(genomic DNA)上轉譯出蛋白質的序列。
已知一段蛋白質的氨基酸序列,藉由這個程式可將此序列,對用戶所選擇的已轉錄序列資料庫(包含這個資料庫的6個ORF),比對出最相似的序列。
已知一段已轉錄的序列,藉由這個程式對這已知序列的6個ORF,對上用戶所選擇的已轉錄序列資料庫(亦包含6個ORF),比對出最相似的序列,因為這個程式比對來源的6個ORF,與資料庫的6個ORF,所以會執行相當久。
这个程序用来搜索蛋白质的"远亲".首先,一个用户提交的蛋白质序列的所有"近亲"的列表被建立起来,然后这些蛋白质被结合在一个作为对序列的某种平均的"特征序列"当中。再然后用这个特征序列在蛋白质数据库中进行搜索,就会找出更大的一组蛋白质的列表。这个蛋白质列表有一个不同的特征序列,这个序列被用来迭代地运行上述过程。
通过在搜索中包含相关的蛋白质,PSI-BLAST对于寻找已知蛋白进化上的"远亲"的灵敏度要比一般的blastp高很多。
Focuses search around pattern (motif)
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.