Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
Maxim_Aliev
0 / 0 / 0
Регистрация: 06.10.2014
Сообщений: 2
06.10.2014, 15:55     БПФ и сравнение двух генетических последовательностей #1
Надеюсь, что тут мне помогут.

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

Подайте идею, пожалуйста, объясните, как это сделать. Было бы замечательно, если ответ был бы в виде кода.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.10.2014, 15:55     БПФ и сравнение двух генетических последовательностей
Посмотрите здесь:

C++ Функция для сравнения двух символьных последовательностей
C++ Найти наибольшую общую подпоследовательность двух последовательностей
C++ Сравнение двух списков
C++ Сравнение двух слов
сравнение двух string C++
Сравнение двух массивов C++
Найти произведение двух последовательностей наиболее близкое к числу R C++
Сравнение двух дат C++ Builder
Объединение двух упорядоченных последовательностей чисел в одну C++
Сравнение двух чисел C++
Из двух заданных последовательностей образовать новую согласно условию C++
В массиве найти произведение двух заданных последовательностей чисел; полученные произведения сравнить C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
OstapBender
 Аватар для OstapBender
581 / 519 / 35
Регистрация: 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 Посмотреть сообщение
как мне использовать БПФ для сравнения двух ген. последовательностей
похоже тебе надо "быстрая корреляция с использованием БПФ"
Maxim_Aliev
0 / 0 / 0
Регистрация: 06.10.2014
Сообщений: 2
06.10.2014, 19:41  [ТС]     БПФ и сравнение двух генетических последовательностей #3
Суть в том, что допустим имеем последовательности AGTCAAGT и CCGAG, нужно найти такой сдвиг одной последовательности относительно другой, чтобы совпало наибольшее число символов, в данном случае сдвиг второй последовательности на два символа относительно другой дает наибольшее кол-во совпадающих символов.
gazlan
2900 / 1848 / 277
Регистрация: 27.08.2010
Сообщений: 4,989
Записей в блоге: 1
06.10.2014, 21:15     БПФ и сравнение двух генетических последовательностей #4
Цитата Сообщение от Maxim_Aliev Посмотреть сообщение
наибольший участок совпадения
Longest common substring problem
OstapBender
 Аватар для OstapBender
581 / 519 / 35
Регистрация: 22.03.2011
Сообщений: 1,585
10.10.2014, 17:16     БПФ и сравнение двух генетических последовательностей #5
Цитата Сообщение от Maxim_Aliev Посмотреть сообщение
Суть в том, что допустим имеем последовательности AGTCAAGT и CCGAG, нужно найти такой сдвиг одной последовательности относительно другой, чтобы совпало наибольшее число символов, в данном случае сдвиг второй последовательности на два символа относительно другой дает наибольшее кол-во совпадающих символов.
для этого можно воспользоваться корреляцией: http://www.mathworks.co.uk/help/signal/ref/xcorr.html
см. пример "Delay Between Two Correlated Signals"
можно написать такой простой код (примеры на матлабе):
Matlab M
1
2
3
4
5
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
1
2
3
4
5
6
7
8
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) % <--- ваше смещение
дополнение: перестановка необходима в следствие того, что свертка (корреляция) через БПФ получается циклической, а мы возвращаем её в последовательную.
Yandex
Объявления
10.10.2014, 17:16     БПФ и сравнение двух генетических последовательностей
Ответ Создать тему
Опции темы

Текущее время: 19:39. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru