1

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

对于不匹配核函数，它允许 m 个不匹配。比如'tool'有3个3-gram（'too','ool'），错配核函数会统计'aoo','boo',...,'zoo','tao'...' tzo','toa'...'toz',....当m为1时。具体解释见http://www.cs.columbia.edu/~cleslie/cs4761/papers/string- kernel-slides.pdf 见第 12-17 页

如何编写一个可以计算该指标的 MATLAB 函数？

非常感谢。

4

1 回答 1

0

我要提出的解决方案实际上是基于蛮力方法（没有花哨的不匹配树）。
如果您正在处理核苷酸，那么您只有 4 个符号，这很好，但是对于大字母和/或大值来说，k它可能会非常低效。
好消息是它不包含任何循环，并且每个语句都是矢量化的，所以它运行得非常快。

首先，我想你知道如何选择k-mers；如果没有，这里提出的解决方案（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聚体的长度。

第三，让我们计算所有可能的k符号组合alphabet：

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 次a，26 次b等等；第三个单元格有 2*26 次a , 2*26 乘以b等等...) 带有“26”，因为它们是字母表中的字母。最后一行将元胞数组C展开为矩阵，然后按字母顺序对组合进行排序。归功于Eithan T。
注意：如果您在此步骤之后内存不足（就内存而言，这是最昂贵的），您也可以删除单元阵列C由于命令从主内存中clear C。从现在开始，我们将不再需要这样的变量。

第四，将每一行combs与目标 k-mer 进行比较：

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

所以我们声明了一个函数，它简单地返回一个位置为jfun的逻辑向量，如果并且在位置j上不同，然后将这样的函数应用（感谢）到. 换句话说，我们将每一行与被测 k-mer 进行比较。因此将是一个逻辑矩阵，其中任何行都是此类比较的结果。注意：是另一个可能占用大量内存的变量。既然我们从现在开始不需要它，你也可以。1abbsxfun()combscomparisons
combsclear combs

第五，计算每个测试组合的不等符号数：

counter=sum(comparisons,2);

作为 1 和 0的comparisons矩阵，可以简单地将每一行求和以获得每行 1 的数量（即每行不同符号的数量）。
注意:counter是一个大小为card(alphabet)^k的向量，其中card(alphabet)是 中的值的数量alphabet，因为它必须包含所有可能组合的值。在某些情况下，这样的向量可能会很大，并且考虑到这样的向量中的每个项目都需要 8 个字节，整个向量可能会占用大量内存。现在，如果您已经清除C并且combs这应该不是问题，但只是为了完整起见，您可能想要投射counter使用每个项目占用少于 8 个字节的整数类型。有关 Matlab 中数字类型的更多信息，请参见此处。

第六，计算m不匹配中的组合数kmerUT：

result=sum(counter<=m);
于 2016-04-03T19:54:11.040 回答