如何处理实现Needleman-Wunsche算法的多个最佳编辑路径？

Question

尝试实施Needleman-Wunsche算法进行生物序列比较.在某些情况下,存在多个最佳编辑路径.

1. 生物seq比较工具处理此问题的常见做法是什么？替换/插入/删除中的任何优先级/首选项？

2. 如果我想在内存中保留多个编辑路径,建议使用任何数据结构？或者一般来说,如何存储分支和合并的路径？

任何评论赞赏.

Answer 1

1. 如果两条路径具有相同的分数，则意味着无论它们使用哪种操作，它们的可能性都是相同的。在获得该分数时已经处理了替换与插入或删除的优先级。因此，如果两个分数相同，通常的做法是任意打破平局。

2. 您应该能够通过记录所有可能从回溯矩阵中到达当前单元格的潜在单元格来处理此问题。然后，在回溯期间，每当到达分支点时就启动一个单独的分支。为了也允许合并，存储有关每个单元格的一些附加数据（具体方式取决于您使用的语言），指示从该单元格剩下多少条不同的路径。然后，在回溯期间，在给定单元处等待，直到该数量的路径返回到该单元，然后将它们合并为一个。您可以通过真正的并行处理来遵循不同的分支，或者只是交替您正在推进的分支。