bioinformatics - FASTA算法说明

Question

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

识别 I 和 J 之间的常见 k 词

用 k 字匹配对对角线进行评分，确定 10 个最佳
对角线

使用替代分数矩阵对初始区域重新评分

使用间隙连接初始区域，惩罚间隙

执行动态规划以查找最终对齐

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

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

Answer 1

这就是 FASTA 的工作原理:

找到所有 k 长度的身份，然后通过选择那些 找到局部相似的区域致密 具有 k 字身份(即许多 k 字，之间没有太多差距)。使用最好的十个初始区域。

通过以通常的方式应用替换矩阵，初始区域沿着它们的长度重新计分。确定最佳评分子区域。

使用动态规划创建修剪初始区域的对齐，间隙惩罚为 20。不包括分数太低的区域。

使用“带状”动态编程(Smith-Waterman)优化 3) 中的对齐。这是仅限于原始比对周围 32 个残基宽频带的动态编程，与完全动态编程相比，这可以节省空间和时间。

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

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