An efficient method for searching characteristic patterns of a subset in a large set of character sequences (Q1210058)

It is important to search similarities between two character sequences or characteristic patterns of a subset in a large set of sequences, in the areas of modular biology, computer science and so on. For simplicity, we call sequences instead of character sequences. The problem of searching similarities between two sequences has been formulated as the one of searching the longest common subsequence of two sequences under certain deletion/insertion constraints. This problem can be modified so as to search an optimum alignment under certain scoring rules, such as \(+1\) for a base match and \(-g\) for a gap. With the development of large database of sequences such as genes or images, it is necessary to compare several sequences. Relating to this problem, \textit{S. Karlin}, \textit{G. Ghandour}, \textit{F. Ost}, \textit{S. Tavare} and \textit{L. J. Korn} [Proc. Natl. Acad. Sci. USA 80, 5660-5664 (1983; Zbl 0517.92013)] developed a program for searching sequences common to all of several sequences. In the paper we consider the problem of searching characteristic patterns of a subset in a large set of sequences.