DP中的回溯Needleman-Wunsch/Smith-Waterman

在Needleman-Wunsch和Smith-Waterman中，實現回溯的最佳方式是什麼？我們通常保留兩個矩陣，每個條目的前一個矩陣都有一個？也就是說，每個條目都是UP，DIAG或LEFT。還是有更簡單，更節省空間的追蹤方式？我理解算法以及如何獲得最高分數，但不是追蹤。謝謝！DP中的回溯Needleman-Wunsch/Smith-Waterman

來源

2014-03-04 goodcow

使用2個矩陣可以工作，但這是一種天真的方法，尤其是如果大小或內存是問題。問題是2個單獨的矩陣空間效率低下。

由於N-W中只有3個可能的追溯方向，而S-W中有4個可能（需要添加STOP），所以可以將每個方向存儲爲2位。如果您的分數足夠小，您可以將相應矩陣單元格的兩個值打包到一個矩陣的單個單元格中，然後進行位掩碼以獲得分數和追溯方向。或者，如果您仍然需要2個矩陣，沒有理由爲回溯矩陣佔用太多空間。您仍然可以打包回溯矩陣，以便4個回溯位置位於字節矩陣的單個單元格中。（你將不得不相似位掩碼）。

來源

2014-03-06 16:09:40 dkatzel

我通過存儲值來自哪裏的數組索引來實現它。 – goodcow

-1

我的理解是肯定的，你確實需要2個矩陣。

然後你從右下角回溯。請參閱http://en.wikipedia.org/wiki/Smith%E2%80%93Waterman_algorithm

來源

2014-03-06 08:11:58 davo36

您可以從全局對齊的右下角回溯，如Needleman-Wunsch。您可以從Smith-Waterman矩陣中的最大值中追溯。 –

DP中的回溯Needleman-Wunsch/Smith-Waterman

回答

相關問題