找到一个共同的动机

Question

我需要帮助解决Rosalind中的一个问题这里是指向该问题的链接以获取更多信息：http://rosalind.info/problems/lcsm/

以下是示例输入：

>Rosalind_1
GATTACA
>Rosalind_2
TAGACCA
>Rosalind_3
ATACA

示例输出为：

^{pr2}$

这就是输入和输出的基本信息：

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中找到最长的motif？在

Answer 1

这是计算机科学和生物信息学中的一个经典问题。它通常被称为最长公共子串（LCS）问题。在您的情况下，这扩展到两个序列的LCS。在

一种称为“动态规划”的技术通常用于两个序列的LCS，并且可以扩展到>；2。动态规划是将问题分解为子问题，求解（并记住答案）子问题，最后回溯得到完整问题的答案。另一种方法是使用a general suffix tree。在

我建议您首先看看如何对2个字符串进行求解：wikibooks。在

然后看看如何将其扩展到>；2。前一个问题似乎也非常relevant，并且有相关的代码。在

祝你好运！在