如何在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);