БПФ и сравнение двух генетических последовательностей

@Maxim_Aliev · Регистрация: 06.10.2014

Author24 — интернет-сервис помощи студентам

Надеюсь, что тут мне помогут.

Написал БПФ, но теперь даже в голову не приходит, как мне использовать БПФ для сравнения двух ген. последовательностей. Задача такая: нужно найти наибольший участок совпадения двух этих последовательностей.

Подайте идею, пожалуйста, объясните, как это сделать. Было бы замечательно, если ответ был бы в виде кода.

@OstapBender · 06.10.2014, 19:22

Сообщение от Maxim_Aliev

нужно найти наибольший участок совпадения двух этих последовательностей.

то есть имеется 2 последовательности, допустим "1 2 3 1 2 3 4 4 4 4 1 2 3" и "5 5 5 5 4 4 4 5 5 5 5 5" и нужно найти что в них обоих есть "4 4 4", так что ли?

Сообщение от Maxim_Aliev

как мне использовать БПФ для сравнения двух ген. последовательностей

похоже тебе надо "быстрая корреляция с использованием БПФ"

@Maxim_Aliev · 06.10.2014, 19:41 **[ТС]**

Суть в том, что допустим имеем последовательности AGTCAAGT и CCGAG, нужно найти такой сдвиг одной последовательности относительно другой, чтобы совпало наибольшее число символов, в данном случае сдвиг второй последовательности на два символа относительно другой дает наибольшее кол-во совпадающих символов.

@gazlan · 06.10.2014, 21:15

Сообщение от Maxim_Aliev

наибольший участок совпадения

Longest common substring problem

@OstapBender · 10.10.2014, 17:16

Сообщение от Maxim_Aliev

Суть в том, что допустим имеем последовательности AGTCAAGT и CCGAG, нужно найти такой сдвиг одной последовательности относительно другой, чтобы совпало наибольшее число символов, в данном случае сдвиг второй последовательности на два символа относительно другой дает наибольшее кол-во совпадающих символов.

для этого можно воспользоваться корреляцией: http://www.mathworks.co.uk/hel... xcorr.html
см. пример "Delay Between Two Correlated Signals"
можно написать такой простой код (примеры на матлабе):

Matlab M

a = [1 2 3 4 1 1 2 3];
b = [4 4 2 1 2];
[corr, lags] = xcorr(a,b);
[~, ind] = max(corr);
lags(ind) % <--- ваше смещение

БПФ тут можно использовать для расчета корреляции (см. "Теорема о свертке", "Быстрая корреляция").
тогда код выше можно переписать как:

Matlab M

a = [1 2 3 4 1 1 2 3];
b = [4 4 2 1 2];
nfft = length(a)*2 - 1;
corr = ifft( fft(a,nfft) .* conj(fft(b,nfft)) ); % теорема о свертке
corr = [corr(end-len+2:end); corr(1:len)]; % см. дополнение
lags = -length(a):length(a)+1;
[~, ind] = max(corr);
lags(ind) % <--- ваше смещение

дополнение: перестановка необходима в следствие того, что свертка (корреляция) через БПФ получается циклической, а мы возвращаем её в последовательную.

@Maxim_Aliev 0 / 0 / 0 Регистрация: 06.10.2014 Сообщений: 2
		1
	БПФ и сравнение двух генетических последовательностей 06.10.2014, 15:55. Показов 1395. Ответов 4 Метки нет (Все метки) Надеюсь, что тут мне помогут. Написал БПФ, но теперь даже в голову не приходит, как мне использовать БПФ для сравнения двух ген. последовательностей. Задача такая: нужно найти наибольший участок совпадения двух этих последовательностей. Подайте идею, пожалуйста, объясните, как это сделать. Было бы замечательно, если ответ был бы в виде кода. 0

@OstapBender 594 / 532 / 76 Регистрация: 22.03.2011 Сообщений: 1,585
	06.10.2014, 19:22	2
	Сообщение от Maxim_Aliev нужно найти наибольший участок совпадения двух этих последовательностей. то есть имеется 2 последовательности, допустим "1 2 3 1 2 3 4 4 4 4 1 2 3" и "5 5 5 5 4 4 4 5 5 5 5 5" и нужно найти что в них обоих есть "4 4 4", так что ли? Сообщение от Maxim_Aliev как мне использовать БПФ для сравнения двух ген. последовательностей похоже тебе надо "быстрая корреляция с использованием БПФ" 0

@Maxim_Aliev 0 / 0 / 0 Регистрация: 06.10.2014 Сообщений: 2
	06.10.2014, 19:41 [ТС]	3
	Суть в том, что допустим имеем последовательности AGTCAAGT и CCGAG, нужно найти такой сдвиг одной последовательности относительно другой, чтобы совпало наибольшее число символов, в данном случае сдвиг второй последовательности на два символа относительно другой дает наибольшее кол-во совпадающих символов. 0

@gazlan 3176 / 1935 / 312 Регистрация: 27.08.2010 Сообщений: 5,131 Записей в блоге: 1
	06.10.2014, 21:15	4
	Сообщение от Maxim_Aliev наибольший участок совпадения Longest common substring problem 0

	10.10.2014, 17:16