BLAST算法原理与应用详解
BLAST算法原理与应用详解
BLAST（Basic Local Alignment Search Tool）是生物信息学中用于序列比对的经典算法，广泛应用于基因组学、蛋白质组学等领域。本文将详细介绍BLAST算法的原理和具体步骤，帮助读者深入理解这一重要工具。
BLAST原理
1. 序列比对
序列比对的主要目的是通过比较序列的相似性来推断未知序列的功能或进行演化分析。相似的序列往往具有相似的结构和功能，或者在演化树构建中反映同源性关系。
2. 打分矩阵、起始空位和延伸空位
在序列比对中，需要使用打分矩阵（如BLOSUM62）来评估氨基酸的匹配程度。对于空位的处理，分为起始空位罚分和延伸空位罚分。起始空位罚分是在首次出现空位时减去的分数，而延伸空位罚分则是在连续空位的后续位置减去的分数。这种设计基于进化上的考虑，认为连续的空位更可能是作为一个片段同时丢失或插入的结果。
3. Needle算法
对于两段序列的全局比对，如果采用枚举法，计算量将非常庞大。例如，对于长度为300的序列，可能的比对方式数量约为目前宇宙中可见原子数量的一亿倍。因此，通常采用动态规划算法（Needleman-Wunsch算法）来优化计算过程。该算法的核心思想是将问题分解为子问题，通过递推的方式计算最优解。
4. Water算法
当两序列只有局部相似时，全局比对不再适用。此时可以使用Smith-Waterman算法（Water算法），它允许比对从任意位置开始，从而找到局部相似区域。
5. BLAST算法
BLAST算法通过以下步骤实现快速序列比对：
- Seeding：将查询序列分割成固定长度的种子序列（k-mers）。
- Find neighborhood words：使用needle/water算法找到与种子序列相似的邻近词。
- Index database：在数据库中查找这些邻近词，找到匹配的hit。
- Extending：对找到的hit进行延伸，直到得分低于特定阈值。
统计显著性检验
由于序列的随机性，两条随机序列也可能有一定程度的相似性。因此，需要使用E-value来评估比对结果的统计显著性。E-value表示在随机情况下获得当前或更高比对分数的可能比对条数。
PSI-BLAST
PSI-BLAST（Position-Specific Iterated BLAST）通过迭代方式改进比对结果。它首先进行一轮BLAST搜索，然后根据搜索结果构建PSSM（Position-Specific Scoring Matrix），再以PSSM为打分矩阵进行下一轮BLAST，从而能够发现亲缘关系更远的序列。
参考资料
- 生物信息学方法，北京大学 高歌
- BLAST算法，降帅
- Needleman, S. B. & Wunsch, C. D. (1970). J. Mol. Biol. 48, 443-453.
- Waterman, M. S. (1984). Bull. Math. Biol. 46, 473-500.
- Altschul, S. F., et al. Basic Local Alignment Search Tool. Journal of Molecular Biology 215, 403–410 (1990) doi:10.1016/S0022-2836(05)80360-2
- Karlin, S. and S. F. Altschul (1990). “METHODS FOR ASSESSING THE STATISTICAL SIGNIFICANCE OF MOLECULAR SEQUENCE FEATURES BY USING GENERAL SCORING SCHEMES.” Proceedings of the National Academy of Sciences of the United States of America 87(6): 2264-2268.