在Needleman-Wunsch和Smith-Waterman中，实现回溯的最佳方法是什么？我们通常保留两个矩阵，一个与每个条目的前置矩阵？也就是说，每个条目都将是 UP、DIAG 或 LEFT。或者有没有更简单、更节省空间的方法来进行回溯？我了解算法以及如何获得最高分，但不了解回溯。谢谢！
使用 2 个矩阵可以工作，但这是一种幼稚的方法，尤其是在大小或内存有问题的情况下。 问题是 2 个单独的矩阵空间效率低下。
由于在 N-W 中只有 3 个可能的跟踪方向，在 S-W 中只有 4 个可能的方向（您需要添加 STOP），因此您可以将每个方向存储为 2 位。 如果分数足够小，则可以将相应矩阵单元格的两个值打包到一个矩阵的单个单元格中，然后执行位掩码以获取分数和回溯方向。
或者，如果您仍然想要 2 个矩阵，则没有理由为回溯矩阵占用这么多空间。 您仍然可以打包回溯矩阵，以便 4 个回溯位置位于字节矩阵的单个单元格中。（您必须进行类似的位屏蔽）。
我的理解是肯定的，您确实需要 2 个矩阵。
然后你从右下角的位置追溯。见 http://en.wikipedia.org/wiki/Smith%E2%80%93Waterman_algorithm