bioinformatics - FASTA算法说明

Question

我试图了解 FASTA 算法在数据库中搜索查询序列的相似序列时的基本步骤。这些是算法的步骤：

1. 识别 I 和 J 之间的常见 k 词
2. 用 k 词匹配对对角线进行评分，确定 10 个最佳对角线
3. 使用替换分数矩阵重新对初始区域进行评分
4. 使用间隙连接初始区域，对间隙进行惩罚
5. 执行动态规划以找到最终对齐

我对使用 PAM250 分数矩阵的第 3 步和第 4 步以及如何“使用间隙加入”感到困惑。

有人可以“尽可能具体地”为我解释这两个步骤吗？谢谢

Answer 1

这就是 FASTA 的工作原理：

1. 找到所有k-length identities，然后通过选择那些密集的k-word identities（即许多k-words，之间没有太多间隙）来找到局部相似的区域。使用最好的十个初始区域。
2. 通过以通常的方式应用替换矩阵，沿着它们的长度对初始区域重新评分。确定最佳评分子区域。
3. 使用动态编程创建修剪后的初始区域的对齐方式，间隙罚分为 20。不包括分数过低的区域。
4. 使用“带状”动态规划 (Smith-Waterman) 优化 3) 的对齐方式。这是限制在原始对齐周围的 32 个残基宽频带的动态编程，与完全动态编程相比，它节省了空间和时间。

如果在 3) 中没有足够的初始区域来形成比对，则可以使用 2) 中的最佳分数来按相似性对序列进行排序。3) 和 4) 的分数也可用于此目的。

不幸的是，我的机构无法访问原始 FASTA 论文，因此我无法提供上述各种参数的原始值。

Answer 2

解释基本上是正确的，但最终的条带优化集中在第 2 步中找到的一个最佳无间隙比对上。第 3 步仅用于提高选择第 4 步的序列的灵敏度。

原始论文可以在这里看到：http ://faculty.virginia.edu/wrpearson/papers/pearson_lipman_pnas88.pdf