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

C++

Войти
Регистрация
Восстановить пароль
 
Maxim_Aliev
0 / 0 / 0
Регистрация: 06.10.2014
Сообщений: 2
#1

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

06.10.2014, 15:55. Просмотров 466. Ответов 4
Метки нет (Все метки)

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

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

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

Сравнение двух предложений по смыслу - C++
Необходимо сравнить два коротких предложения по смыслу. Я так понимаю, нужно семантическое сравнение предложений. Как его можно...

сравнение двух лиц людей - C++
Здравствуйте! подскажите пожалуйста, есть ли в сети готовые библиотеки на Си или С++, которые выдают % схожести одного лица на...

БПФ - C++
Добрый день, скажите кто знает, как на С/C++ сосчитать БПФ, какую библиотеку для этого можно использовать?

Сравнение двух значений - C++ Builder
Здрастувуйте! На форме есть компонент Edit и Button. Нужно нажавши по кнопке сравнить вместимое Edit с строкой прописаной в самой...

Сравнение двух дат - C++ Builder
Нужно сравнить две даты, первая берется из таблицы, вторая дата это текущая, написал код, выдает ошибку, подскажите CompareDate(Date(),...

Сравнение двух дат - C++ Builder
Всем Доброго времени суток!!! Подскажите, пожалуйста, как сравнить 2 даты в формате "ДД.ММ.ГГГГ ЧЧ.ММ.СС" в C++ Builder, для того чтобы...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
OstapBender
583 / 521 / 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
3131 / 1906 / 285
Регистрация: 27.08.2010
Сообщений: 5,132
Записей в блоге: 1
06.10.2014, 21:15 #4
Цитата Сообщение от Maxim_Aliev Посмотреть сообщение
наибольший участок совпадения
Longest common substring problem
OstapBender
583 / 521 / 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) % <--- ваше смещение
дополнение: перестановка необходима в следствие того, что свертка (корреляция) через БПФ получается циклической, а мы возвращаем её в последовательную.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.10.2014, 17:16
Привет! Вот еще темы с ответами:

Сравнение двух изображений с IP-камеры - C++ Builder
Доброго времени суток! задача стоит в определении изменения положения IP-камеры, фокусировки и т.д. все то, что отличается он начального...

Сравнение двух ячеек в StringGrid - C++ Builder
Доброго времени дня. Есть StringGrid1, в котором 4 столбца*10 строк(картотека). Он заполняется. Потом в Edit вводится фамилия. При...

TStringList - сравнение двух листов - C++ Builder
У меня есть текстовыйй документ и TStringList создаваемый при выполении программы, как сравнить их содержание и найти соответсвия?

Сравнение указанных последовательностей битов в двух разных заданных числах - C (СИ)
Очень долго сидел и не получается решить,только недавно начал учить си сама задача: Сравнение указанных последовательностей битов в...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
10.10.2014, 17:16
Ответ Создать тему
Опции темы

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