FASTA算法解释

Question

我试图了解FASTA算法在数据库中搜索类似查询序列的基本步骤。算法的步骤如下：

diagonals

• Rescore

• 用k字匹配识别I和J

• 记分对角线之间常见的k-字，用替换分数矩阵

• 识别10个最佳的

初始区域，利用空格连接初始区域，对

• 执行动态规划以找到最终对齐的

g 211

我混淆了使用PAM250分数矩阵的第3和第4步，以及如何“加入使用空白”。

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

Answer 1

FASTA就是这样工作的：

1. 找到所有k长度恒等式，然后通过选择具有k字恒等式的稠密(即多个k字，之间没有太多空隙)来寻找局部相似的区域。使用最优的十个初始区域，

，

1. ，根据它们的长度，用通常的方法应用替换矩阵对初始区域重新评分。最优的评分子区域是identified.
2. Create --使用动态规划对齐的初始区域，间隙惩罚为20。得分过低的区域不是使用“带状”动态规划(Smith-Waterman)对齐。这是一种动态规划，限制在原始对准周围的32剩余宽的带宽范围内，这在全动态programming.

上节省了空间和时间。

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

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

Answer 2

这一解释基本上是正确的，但最终的波段优化集中在步骤2中找到的最佳无接对齐上。步骤3只是用来提高在选择步骤4的序列时的灵敏度。

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