Searching Through the Haystack

In “Finding a Motif in DNA”, we searched a given genetic string for a motif; however, this problem assumed that we know the motif in advance. In practice, biologists often do not know exactly what they are looking for. Rather, they must hunt through several different genomes at the same time to identify regions of similarity that may indicate genes shared by different organisms or species.
The simplest such region of similarity is a motif occurring without mutation in every one of a collection of genetic strings taken from a database; such a motif corresponds to a substring shared by all the strings. We want to search for long shared substrings, as a longer motif will likely indicate a greater shared function.

Problem

A common substring of a collection of strings is a substring of every member of the collection. We say that a common substring is a longest common substring if there does not exist a longer common substring. For example, “CG” is a common substring of “ACGTACGT” and “AACCGTATA”, but it is not as long as possible; in this case, “CGTA” is a longest common substring of “ACGTACGT” and “AACCGTATA”.
Note that the longest common substring is not necessarily unique; for a simple example, “AA” and “CC” are both longest common substrings of “AACC” and “CCAA”.
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.)

Sample Dataset

  1. >Rosalind_1
  2. GATTACA
  3. >Rosalind_2
  4. TAGACCA
  5. >Rosalind_3
  6. ATACA

Sample Output

  1. AC

Solution1：两两求最长公共子串【错误：当两串的lcs不止一个】

其实本例就是一个求 Finding a Shared Motif - 图1 串最长公共子串的问题，普通方法就是两串对比后再和之后的进行对比，即两串对比进行 Finding a Shared Motif - 图2次。如下面程序用动态规划求两串的思想时间复杂度为 Finding a Shared Motif - 图3，其中 w 是最长公共子串的长度。

  1. class Solution:
  2.     def readFasta(self, fileName: str) -> List[str]:
  3.         seqs = []
  4.         with open(fileName) as f:
  5.             seq = []
  6.             for line in f:
  7.                 line = line.strip()  # withespace
  8.                 if line.startswith('>'):  # ID
  9.                     if seq:  # last sequence finished
  10.                         seqs.append(''.join(seq))
  11.                         seq = []
  12.                 elif line:  # bases
  13.                     seq.append(line.strip())
  14.             # last sequence
  15.             if seq:
  16.                 seqs.append(''.join(seq))
  17.         return seqs
  19.     def solve(self) -> str:
  20.         def findLCS(s: str, t: str) -> str:
  21.             m, n = len(s), len(t)
  22.             dp = [[0] * (n + 1) for _ in range(m + 1)]
  23.             max_len = 0
  24.             start_idx = -1
  25.             for i in range(m - 1, -1, -1):
  26.                 for j in range(n - 1, -1, -1):
  27.                     if s[i] == t[j]:
  28.                         dp[i][j] = dp[i + 1][j + 1] + 1
  29.                     else:
  30.                         dp[i][j] = 0
  31.                     if dp[i][j] > max_len:
  32.                         max_len = dp[i][j]
  33.                         start_idx = i
  34.             # print("lcs-{},{}:{}".format(s, t, s[start_idx:start_idx+max_len]))
  35.             return s[start_idx:start_idx + max_len]
  36.         seqs = self.readFasta('./rosalind_lcsm.txt')
  37.         return reduce(findLCS, seqs)
  39. print(Solution().solve())