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".