Форум программистов, компьютерный форум, киберфорум
C++
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/6: Рейтинг темы: голосов - 6, средняя оценка - 5.00
0 / 0 / 0
Регистрация: 06.10.2014
Сообщений: 2
1

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

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


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

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

Подайте идею, пожалуйста, объясните, как это сделать. Было бы замечательно, если ответ был бы в виде кода.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
06.10.2014, 15:55
Ответы с готовыми решениями:

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

Сравнение сумм последовательностей чисел
Пусть дан набор из Ai не повторяющихся положительных целых чисел в количестве N штук. Требуется...

Объединение двух последовательностей
Даны 2 последовательности class Arr1 { public int ID { get; set; } ...

Вычислить значения двух последовательностей
Помогите, пожалуйста, решить! Пусть a1=u, b1=v, ai=2bi-1+ai-1, bi=2a2i-1+bi-1. Получите a2, a3,...

4
591 / 529 / 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
0 / 0 / 0
Регистрация: 06.10.2014
Сообщений: 2
06.10.2014, 19:41  [ТС] 3
Суть в том, что допустим имеем последовательности AGTCAAGT и CCGAG, нужно найти такой сдвиг одной последовательности относительно другой, чтобы совпало наибольшее число символов, в данном случае сдвиг второй последовательности на два символа относительно другой дает наибольшее кол-во совпадающих символов.
0
3170 / 1929 / 313
Регистрация: 27.08.2010
Сообщений: 5,131
Записей в блоге: 1
06.10.2014, 21:15 4
Цитата Сообщение от Maxim_Aliev Посмотреть сообщение
наибольший участок совпадения
Longest common substring problem
0
591 / 529 / 76
Регистрация: 22.03.2011
Сообщений: 1,585
10.10.2014, 17:16 5
Цитата Сообщение от Maxim_Aliev Посмотреть сообщение
Суть в том, что допустим имеем последовательности AGTCAAGT и CCGAG, нужно найти такой сдвиг одной последовательности относительно другой, чтобы совпало наибольшее число символов, в данном случае сдвиг второй последовательности на два символа относительно другой дает наибольшее кол-во совпадающих символов.
для этого можно воспользоваться корреляцией: http://www.mathworks.co.uk/hel... 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) % <--- ваше смещение
дополнение: перестановка необходима в следствие того, что свертка (корреляция) через БПФ получается циклической, а мы возвращаем её в последовательную.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
10.10.2014, 17:16

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь или здесь.

Построить объединение двух последовательностей
Даны натуральное число n, целые числа a1,..., a25, b1,..., bn. Среди a1,..., a25 нет повторяющихся...

Слияние двух отсортированных последовательностей
Помогите с заданием ! Даны две последовательности a1≤a2... ≤an и b1≤b2...≤bm...

Сформировать последовательность С - разницу двух последовательностей В и А
Сформировать последовательность C, содержащую все элементы последовательности A без повторений, не...

Построить объединение двух заданных последовательностей
Даны натуральное число n, целые числа а_1,…,а_25,b_1,…,b_n. Среди а_1,…,а_25 нет повторяющихся...


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

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

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