0

我想以最佳方式比对两个 DNA 序列，但我有长度为 L 的空位惩罚函数，如果 L 是 3 的倍数，则对于某个常数 a，惩罚是 a * L。如果 L 不是 3 的倍数，那么对于某个常数 b，惩罚是 b * L。

我应该设计一个 O(n * m) 算法，其中 n 和 m 是 DNA 序列的长度，可以找到最佳比对。但棘手的部分是我必须跟踪它正在扩展的间隙的大小。例如，如果我有两个连续的差距并进一步扩大一个差距，我需要将分数更新为L - b (L-1)，但我无法制定能很好地处理这种情况的子问题。我考虑过引入一个新参数 L 来“猜测”最终间隙的长度，但这很容易超过 O(n * m)。

有没有办法有效地制定这些子问题？任何关键意见将不胜感激。

4

1 回答 1

0

你能澄清一下你所说的连续间隙是什么意思吗？如果我对您的理解正确，那么您的场景的示例对齐方式将如下所示： AAATTTGGGAA----CCCGG AAATTTCGGAA-----GCGG 但是，在两条链上包含匹配的间隙将无济于事。上述对齐方式与此相同： AAATTTGGGAACCCGG AAATTTCGGAA-GCGG 在任何给定时间，空位罚分只应与单链相关。为了衡量更改对齐参数如何影响对齐输出，我建议查看 biopython Pairwise2 模块（它可以包括间隙罚分/间隙扩展罚分）。http://biopython.org/DIST/docs/api/Bio.pairwise2-module.html

于 2017-10-06T20:12:45.093 回答