2

假设我有 2 个字符串：

AACCCGGAAATTTGGAATTTTCCCCAAATACG

CGATGATCGATGAATTTTAGCGGATACGATTC

我想找出我应该移动多少第二个字符串以使其与第一个字符串最匹配。

有2例。第一个是我们假设字符串被缠绕，第二个是我们没有。

是否有一个 matlab 函数返回一个 N 数组或 2N+1 数组值，以了解移位的字符串 2 与字符串 1 的相关程度？

如果没有，是否有比类似的方法更快/更简单的方法

result = zeroes(length, 1)
for i = 0:length-1
    result(i+1) = sum (str1 == circshift(str2, i));
end
4

2 回答 2

5

您可以将每个 char 转换为大小为 4 的二进制列：

A -> [1;0;0;0]
C -> [0;1;0;0]
G -> [0;0;1;0]
T -> [0;0;0;1]

结果，一个长度的字符串变成了一个大小为-by-n的二进制矩阵。4n

您现在可以交叉关联（仅沿 X 轴）两个n-by-4 和m-by-4 以获得您的结果。

于 2013-06-13T21:52:06.717 回答
4

向John d'Errico 致敬：

str1 = 'CGATGATCGATGAATTTTAGCGGATACGATTC';
str2 = 'AACCCGGAAATTTGGAATTTTCCCCAAATACG';

% the circulant matrix
n = length(str2);
C = str2( mod(bsxfun(@plus,(0:n-1)',0:n-1),n)+1 ); %//'

% Find the maximum number of matching characters, and the amount 
% by which to shift the string to achieve this result
[score, shift] = max( sum(bsxfun(@eq, str1, C), 2) );

更快，是的，更简单......好吧，我会让你决定:)

请注意，此方法以内存换取速度。也就是说，它（有效地）创建了内存中所有可能移位的矩阵，并将字符串与该矩阵的所有行进行比较。该矩阵将包含N²元素，因此如果N变大，最好使用循环（或 Shai 的方法）。

于 2013-06-13T21:51:32.350 回答