如何在MATLAB中實現不匹配的內核函數？

Question

有誰知道如何找到不匹配發生的子序列模式？

對於不匹配的內核函數，它允許m不匹配。例如，'工具'有三個3克（'too'，'ool'），並且不匹配的內核函數將計數爲 'aoo'，'boo'，...，'zoo'，'tao'... 「TZO」，「TOA」 ...「特茲」 ......當m爲1 有關具體說明，請參閱http://www.cs.columbia.edu/~cleslie/cs4761/papers/string-kernel-slides.pdf 只看到頁12-17

我如何寫一個功能的MATLAB那可以計算這個度量？

非常感謝。

Answer 1

我要提出的解決方案實際上是基於bruteforce方法（沒有花哨的不匹配樹）。
如果你正在處理核苷酸，你只有4個符號，這很好，但是對於大字母和/或大值k，它可能是相當低效的內存。
好消息是它不包含任何循環，每個語句都是矢量化的，所以它的工作速度非常快。首先，我想你知道如何選擇k-mers;如果不是，解決方案建議here（功能n_gram()由gnovice）出色地工作。
我不喜歡「n-gram」，我更喜歡「k-mers」，所以我將在下面用它來表示長度爲k的子字符串。

其次，讓我們聲明一些變量：

m=1; k=3; 
alphabet='abcdefghijklmnopqrstuvwxyz'; 
kmerUT='too'; 

其中m是距離（如幻燈片），alphabet是相當不言自明的（是集合所有可能的值），kmerUT是被測試的k-mer（即我們想要計算距離的k-mer）和k是k-mer的長度。

第三，讓我們計算從alphabet的k符號的所有可能的組合：

C = cell(k, 1);      %// Preallocate a cell array 
[C{:}] = ndgrid(alphabet);   %// Create K grids of values 
combs = cellfun(@(x){x(:)}, C);  %// Convert grids to column vectors 
combs = sortrows([combs{:}]);  %// Obtain all permutations 

此代碼段中，爲了，預先分配的細胞陣列k細胞。所述第二表達以後，在這些3個單元將有來自alphabet的值用「不同期間」（第一小區：abcdefh ...;第二單元具有26倍一個，26倍b等;第三個單元有2×26次a,2 * 26次b等等......），因爲它們是字母表中的字母。最後一行將單元陣列C解開爲矩陣，然後按字母順序對這些組合進行排序。致謝Eithan T。
注意：如果在此步驟之後內存不足（這是內存方面最昂貴的），那麼也可以通過命令clear C從主內存中移除單元陣列C。從現在起我們不需要這樣的變量。

第四，比較各行combs與目標k鏈節：

fun=@(a,b) (a~=b); 
comparisons=bsxfun(fun,combs,kmerUT); 

，所以我們定義一個函數fun簡單地在位置Ĵ返回與1邏輯矢量如果a和b是不同的在位置j，然後向combs中的所有行應用（感謝bsxfun()）此功能。換句話說，我們將每行與被測試的k-mer進行比較。因此comparisons將是一個邏輯矩陣，其中行是這種比較的結果。
注意：combs是另一個可能需要大量內存的變量。既然我們現在不需要它，你也可以clear combs。

第五，計數不等於符號的每一個進行測試組合數目：具有comparisons爲1和0的矩陣

counter=sum(comparisons,2); 

，人們可以簡單地總結中的每一行以獲得每行中1的個數（即每行不同符號的數量）。
注：counter是其大小爲卡（字母）^ K A矢量其中卡（字母）是值的alphabet數量，因爲它必須包含所有可能的組合的值。這種矢量在某些情況下可能很大，並且考慮到這種矢量中的每個項目需要8字節，整個矢量可能佔用大量內存。現在如果你已經清除了C和combs它應該不是問題，但是爲了完整起見，你可能想要使用一個整數類型來拋出counter，該整數類型每個項目少於8字節。關於Matlab中的數字類型的更多信息可以在here找到。

第六，從kmerUT數組合內m錯配的數量：

result=sum(counter<=m);