Поиск Shared Motif

Question

мне нужна помощь с одной проблемой в Розалинды здесь ссылка на проблему для получения дополнительной информации: http://rosalind.info/problems/lcsm/

Ниже входной пример:

>Rosalind_1 
GATTACA 
>Rosalind_2 
TAGACCA 
>Rosalind_3 
ATACA 

выход Образец:

AC 

и это основная информация о входе и выходе:

Given: A collection of k (k≤100) DNA strings of length at most 
     1 kbp each in FASTA format. 

Return: A longest common substring of the collection. (If multiple 
     solutions exist, you may return any single solution.) 

Проблема просит, чтобы найти самую длинную общую строку, которая присутствует во всех трех последовательностях, и общая длинная строка найдены в этом примере является AC.

Теперь, перейдя к вопросу с его программированием.

Идея, которую я имел - и попытался - взять первую строку GATTACA и проверить все комбинации символов и проверить, присутствует ли она в последовательности два и три.

Как это сделать, чтобы перебрать все возможные базы для всех трех последовательностей и найти самый длинный мотив в python?

Answer 1

Это классическая проблема в информатике и в биоинформатике. Его часто называют проблемой самой длинной общей подстроки (LCS). В вашем случае это распространяется на LCS для> 2 последовательностей.

Техника, называемая «Динамическое программирование», часто используется для LCS для двух последовательностей и может быть расширена для> 2. Динамическое программирование как разбиение проблемы на подзадачи, решение (и повторение ответов) на подзадачи и, наконец, отслеживание, чтобы получить ответ на полную проблему. Другой подход заключается в использовании a general suffix tree.

Предлагаю вам сначала взглянуть на то, как это решить для 2 строк: wikibooks.

Затем посмотрите, как это можно расширить для> 2. Этот предыдущий вопрос также кажется очень relevant и имеет связанный код.

Удачи вам!