PATTERN DISCOVERY OF GENOME SEQUENCES BY SUBSTRING AMPLIFICATION

In this paper, we study a problem which is, given a set of genome sequences, to find common subsequences. We assume that the sequences are generated by some fixed but unknown pattern. The authors developed a method, called “substring amplification,” to find the template part of a pattern from semi-structured documents, such as HTML files, generated by the pattern. Substring amplification exploits the disparity of frequency distributions between the template and background parts, and so requires only positive data. In HTML files, many characters are used and the length of a successive part of a template is enough long compared to genome sequences. In this paper, we examine the applicability of the method to genome sequences in which a constant sequence is embedded. By a series of experiments in which the length and alphabet size of the embedded sequences are varied, we show the effectiveness and limit of our method to genome sequences