尝试实现用于生物序列比较的 Needleman-Wunsche 算法。在某些情况下，存在多个最佳编辑路径。
处理此问题的 bio-seq-compare 工具的常见做法是什么？替代/插入/删除之间的任何优先级/偏好？
如果我想在内存中保留多个编辑路径，建议使用任何数据结构吗？或者一般来说，如何存储带有分支和合并的路径？
任何意见表示赞赏。
问问题
556 次
2 回答
0
如果两条路径具有相同的分数，这意味着无论它们使用哪种操作，它们的可能性都是相同的。在获得该分数时已经处理了替换与插入或删除的优先级。因此，如果两个分数相同，通常的做法是任意打破平局。
您应该能够通过记录所有可能已经从您的回溯矩阵中到达当前单元的潜在单元来处理此问题。然后，在回溯期间，无论何时到达分支点，都启动一个单独的分支。为了也允许合并，请存储一些关于每个单元格的附加数据（如何取决于您使用的语言），指示从它那里剩下多少不同的路径。然后，在回溯期间，在给定的单元格处等待，直到该数量的路径返回到它，然后将它们合并为一个。您可以使用真正的并行处理来跟踪不同的分支，或者只是交替您正在推进的分支。
于 2014-01-19T01:51:58.997 回答
0
除非您有理由提前选择一个输入序列而不是另一个输入序列，否则这无关紧要。
否则，您可能会将 seq_a 视为垂直轴，将 seq_b 视为水平轴，然后如果有平局要打破，则始终选择朝着您喜欢的方向前进……但我无法说服自己与对齐假设有任何区别一个优先于另一个起始序列之一
于 2020-01-02T21:55:32.880 回答