WE CLAIM:
[Claim 1] A pattern extraction device to extract a standard pattern that
iteratively appears in first sequence data, from second sequence data, the pattern extraction device comprising:
an extraction unit to extract a pattern similar to a sample pattern that is data of a specified interval in the second sequence data, from the first sequence data;
an evaluation unit to calculate a first evaluation value representing a frequency of occurrence of the pattern extracted by the extraction unit in the first sequence data and a second evaluation value representing a degree of expansion or contraction of the pattern extracted by the extraction unit in a sequence direction of the first sequence data and to calculate goodness of fit of the sample pattern for the standard pattern based on the first evaluation value and the second evaluation value; and
a control unit to alter the specified interval and to make the extraction unit and
the evaluation unit operate afresh, in case where the goodness of fit calculated by the
evaluation unit does not exceed a threshold, or to output information that indicates the
specified interval as an interval corresponding to the standard pattern, in case where the
goodness of fit calculated by the evaluation unit exceeds the threshold.
[Claim 2] The pattern extraction device according to claim 1, wherein
the evaluation unit calculates, as the goodness of fit of the sample pattern for
the standard pattern, a smaller value as the frequency of occurrence represented by the
first evaluation value becomes lower.
[Claim 3] The pattern extraction device according to claim 1 or 2, wherein
the evaluation unit calculates, as the goodness of fit of the sample pattern for the standard pattern, a larger value as the degree of the expansion or the contraction represented by the second evaluation value becomes lower.

[Claim 4] The pattern extraction device according to any one of claims 1 to 3,
further comprising:
a calculation unit to divide the first sequence data and the second sequence data into fixed-length frames and to calculate a similarity matrix that is a matrix representing degrees of similarity between the frames for each combination of a frame of the first sequence data and a frame of the second sequence data; and
a selection unit to select a submatrix corresponding to the specified interval from the similarity matrix calculated by the calculation unit, wherein
the extraction unit calculates paths that trace elements corresponding to combinations of the frames of the second sequence data and the frames of the first sequence data that are similar to the frames of the second sequence data in the submatrix selected by the selection unit, and
the evaluation unit calculates the first evaluation value and the second
evaluation value based on the paths calculated by the extraction unit.
[Claim 5] The pattern extraction device according to claim 4, wherein
the evaluation unit calculates, as the first evaluation value, a value representing
a lower degree as spaces between intervals in the first sequence data where the paths
calculated by the extraction unit exist become larger.
[Claim 6] The pattern extraction device according to claim 4 or 5, wherein
the evaluation unit calculates, as the first evaluation value, a value representing a lower degree as overlaps of intervals of the first sequence data where the paths calculated by the extraction unit exist become larger.
[Claim 7] The pattern extraction device according to any one of claims 4 to 6,
wherein
the evaluation unit calculates, as the second evaluation value, a value

representing a lower degree as the paths calculated by the extraction unit become closer to straight lines.
[Claim 8] A pattern extraction method of extracting a standard pattern that
iteratively appears in first sequence data, from second sequence data, the pattern extraction method comprising:
by an extraction unit, extracting a pattern similar to a sample pattern that is data of a specified interval in the second sequence data, from the first sequence data;
by an evaluation unit, calculating a first evaluation value representing a frequency of occurrence of the pattern extracted by the extraction unit in the first sequence data and a second evaluation value representing a degree of expansion or contraction of the pattern extracted by the extraction unit in a sequence direction of the first sequence data and calculating goodness of fit of the sample pattern for the standard pattern based on the first evaluation value and the second evaluation value; and
by a control unit, altering the specified interval and making the extraction unit
and the evaluation unit operate afresh, in case where the goodness of fit calculated by
the evaluation unit does not exceed a threshold, or outputting information that indicates
the specified interval as an interval corresponding to the standard pattern, in case where
the goodness of fit calculated by the evaluation unit exceeds the threshold.
[Claim 9] A pattern extraction program to extract a standard pattern that
iteratively appears in first sequence data, from second sequence data, the pattern extraction program that causes a computer to execute:
an extraction process of extracting a pattern similar to a sample pattern that is data of a specified interval in the second sequence data, from the first sequence data;
an evaluation process of calculating a first evaluation value representing a frequency of occurrence of the pattern extracted in the extraction process in the first

sequence data and a second evaluation value representing a degree of expansion or contraction of the pattern extracted in the extraction process in a sequence direction of the first sequence data and calculating goodness of fit of the sample pattern for the standard pattern based on the first evaluation value and the second evaluation value; and a control process of altering the specified interval and executing the extraction process and the evaluation process afresh, in case where the goodness of fit calculated in the evaluation process does not exceed a threshold, or outputting information that indicates the specified interval as an interval corresponding to the standard pattern, in case where the goodness of fit calculated in the evaluation process exceeds the threshold.