FASTA算法解释

Question

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

1. 识别I和J之间的常见k字
2. 使用k字匹配对角线进行评分,确定10个最佳对角线
3. 使用替换分数矩阵重新构造初始区域
4. 使用间隙加入初始区域,惩罚差距
5. 执行动态编程以查找最终对齐

我对使用PAM250评分矩阵的第3步和第4步以及如何"加入使用差距"感到困惑.

有人可以"尽可能具体地"为我解释这两个步骤.谢谢

Answer 1

这就是FASTA的工作方式:

1. 找到所有k长度的身份,然后通过选择那些密集的k字身份(即许多k字,没有太多间隙)来找到本地相似的区域.使用最好的十个初始区域.
2. 通过以常规方式应用替换矩阵,沿着它们的长度重新评分初始区域.确定了最佳评分子区域.
3. 使用动态编程创建修剪的初始区域的对齐,间隙罚分为20.不包括分数太低的区域.
4. 使用"带状"动态编程(Smith-Waterman)优化3)的对齐.这是动态编程,仅限于原始对齐周围的32个残余宽带,从而节省了完整动态编程的空间和时间.

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

不幸的是,我的机构无法访问原始的FASTA纸张,因此我无法提供上述各种参数的原始值.