查找共享花片

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並檢查所有符號組合，並檢查它是否出現在序列2和3中。

我該怎麼做才能循環遍歷所有三個序列的所有可能的鹼基，並找到python中最長的主題？

Answer 1

這是計算機科學和生物信息學中的一個經典問題。它通常被稱爲最長公共子串（LCS）問題。在你的情況下，這擴展到LCS> 2個序列。

一種稱爲「動態規劃」的技術通常用於兩個序列的LCS，並且可以擴展爲> 2。動態規劃將問題分解爲子問題，解決（並回答答案）子問題，最後回溯到問題的完整答案。另一種方法是使用a general suffix tree。

我建議你先看看如何解決這2個字符串：wikibooks。

然後看看如何擴展> 2。這個前面的問題似乎也很relevant並且有相關的代碼。

祝你好運！