строка «кросс-корреляция» в MATLAB

Question

Предположит, что у меня есть 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 

Answer 1

С наконечником шляпу 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 становится большим, лучше использовать цикл (или метод Шая).

Answer 2

Вы можете преобразовать каждый символ в двоичную колонку размера 4:

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

В результате строка длины n становится бинарной матрицей размера 4 матрица с размерностью n.

Теперь вы можете перекрестно коррелировать (только по оси X) два n -by-4 и m -by-4, чтобы получить результат.