JP2907169B2 - Stochastic motif discovery method for protein and gene sequences - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

The present invention relates to a method for searching for a motif in a protein or gene sequence, and more particularly to a method for finding a stochastic motif from sequence data.

[0002]

2. Description of the Related Art A motif is a structurally and functionally important site in the amino acid sequence of a protein or the base sequence of a gene, and is a partial sequence that is conserved during the evolution of an organism. Motifs are also called consensus sequences.

Heretofore, the motif of the amino acid sequence of a protein and the motif of the base sequence of a gene have been represented by an expression called a pattern. For example, in the protein motif database PROSITE, "N-
The motif was expressed as an OR (logical sum) of 20 amino acids, such as {P}-[ST] -P "or" [ST] -x- [ST] ". N, P, S, T are
Abbreviations representing the types of amino acids, each of which is a kind of amino acid, aspartic acid, proline, serine,
Shows threonine. Further, x represents an arbitrary amino acid, {P} represents all amino acids except P (proline), and [ST] represents S (serine) or T (threonine).

[0004] In some cases, an expression method called a profile is also used. This expresses the score when each amino acid or base comes at each position of the motif. On the other hand, Hidden Marko models (HMMs) hide protein and gene sequences.
v Model) is being used.

[0005] If a common site can be automatically found from different biochemically related sequences using such an expression, this common site is a partial sequence important for biochemical functions and three-dimensional structure. It can be thought of as something that has been evolutionarily preserved. Therefore, the discovery of a motif, which is a common site, is an important issue for the analysis of functions and structures of proteins and genes. As a method of discovering motifs, a bottom-up method,
Various methods are being studied, including top-down methods.

In the bottom-up method, the frequency of appearance or the amount of information (Information Content) in an array is calculated for each pattern in consideration of the pattern space.
This method uses a pattern with a high frequency of appearance or a large amount of information as a motif. For example, the 1990 magazine "Pr
oc. Natl. Acad. Sci. USA "No. 87-826-830.
Smith et al., "Finding sequence motif"
s in groups of functionally related proteins ”
No. 86, 1183-1 of the US magazine published in 1989
Stormo et al., “Identifying pr.
otein-bindingsites from unaligned DNA fragments ”
and so on.

The top-down method is a method of comparing sequences to find local similarities, and performs sequence alignment. Alignment is a technique in which gaps and the like are inserted in a given plurality of sequences so that amino acids or bases having the same or similar properties are arranged in vertical column positions. The top-down method includes a method of performing pairwise alignment of two sequences and combining the results, and a method of performing alignment between groups. In the motif extraction using such an alignment, after a sequence is aligned, a site having the same amino acid or base is searched for, or a similar local site is aligned. Such alignment includes, for example, Blast, FastA, Clust V
and so on.

[0008]

However, the conventional bottom-up method has a problem that it takes a long time to calculate. For example, for a pattern of length l with the number of characters | Σ |, the size of the search space is Ο (| Σ | ^l ), which increases exponentially with the length l of the pattern. Furthermore, P which is actually a database of protein motifs
Looking at ROSITE, although it is an evolutionarily conserved site, there are many gaps and mismatches in the sequence. When trying to consider gaps and mismatches in the bottom-up method, it is necessary to consider neighboring words that allow gaps and mismatches, and the search query becomes too large, which is difficult to achieve in terms of computation time. Moreover, the obtained pattern has lower expression ability than a stochastic model such as a hidden Markov model.

Further, in the conventional alignment method, errors in the initial stage are spread, so that the accuracy is not so good, the weight of the array must be considered, and the score depending on the position is difficult to consider. There was a problem.

[0010] The present invention solves the above-mentioned problems, and focuses on only common sites to express gaps and mismatches using a stochastic model, thereby finding a stochastic motif capable of expressing sequences in detail. The purpose is to provide. It is another object of the present invention to provide a stochastic motif discovery method that can explicitly handle a repeated motif by expressing the motif with a hidden Markov model.

[0011]

Probabilistic motif discovery method of the present invention solve problems which means for a], as described in claim 1, a method of finding the probabilistic motif from either array data of proteins and gene, the computer Using a motif extracted by symbol processing from given sequence data as an initial motif, and extracting a subsequence that best matches the initial motif from the sequence data as a first subsequence; A second step in which a second subsequence is newly generated by extending before and after the first subsequence and a stochastic representation of the second subsequence is newly set as a motif; And extracting a sub-sequence that best fits the motif obtained in the second step from the first step to make the first sub-sequence again, and after the execution of the first step Discovering probabilistic motif By repeating the second step and the third step.

According to a second aspect of the present invention, in the method for discovering a stochastic motif according to the first aspect, in the first step, the number of occurrences in sequence data of a pattern which is a sequence of any one of an amino acid and a base is included. Is calculated, and the pattern selected from the one with the largest number of appearances is set as the initial motif. According to a third aspect of the present invention, in the stochastic motif finding method according to the first aspect, in the second step, the motif is expressed using a hidden Markov model, and the motif is extracted from the sequence data in the third step. When extracting a subsequence that best matches the likelihood, the likelihood is normalized by the array length, and a subsequence having a high likelihood after normalization is extracted.

Further, in the stochastic motif finding method according to the third aspect, when the motif is stochastically generated in the second step, a hidden Markov model having a given number of states is used as an initial model, and the transition probability is determined. Generating a network structure of a new hidden Markov model by removing the transitions below a predetermined value and combining the new states, and then randomly setting a plurality of sets of initial parameters of the hidden Markov model of the generated network structure; To repeat the parameter calculation for the setting and to use the hidden Markov model that gives the best result in the parameter calculation as a new hidden Markov model, or to optimize the number of states and network structure of the hidden Markov model Then, the array data is divided into learning data and evaluation data. Is used in the learning of the hidden Markov model, and the number of states and the network structure with the highest likelihood of the evaluation data are searched from the hidden Markov model after the learning, and based on the searched number of states and the network structure. Parameters can be re-estimated, or a motif can be generated after removing a partial sequence with low likelihood at a predetermined ratio. Further, in the stochastic motif discovery method according to the third aspect, the number of states and the network structure of the hidden Markov model can be optimized on the basis of the information amount.

(Action) In the present invention, by using a probabilistic model having a higher expression ability than a pattern, it is possible to easily handle gaps and mismatches in the motif and express the motif precisely. In particular, by using a hidden Markov model, it was possible to explicitly handle repetitive motifs. When generating a motif using a hidden Markov model as a probabilistic model, for example, using the hidden Markov model creation method for protein sequence data described in JP-A-7-36920, the topology and parameters of the hidden Markov model are used. learn.

If a probabilistic model is applied from the beginning of motif discovery, the amount of sequence data of the target protein or amino acid is generally large, so that it takes too much calculation time. The sequence length of the amino acid sequence, that is, the number of residues of the target amino acid is usually about 300 to 400,
There are also sequences up to 5000. In addition, although the sequence of a gene uses a small number of characters, it is generally longer than the amino acid sequence. Therefore, in the present invention, in order to reduce the calculation time, in the first step, the pattern is roughly narrowed down to a motif part by, for example, a pattern by symbol processing, and thereafter the calculation is performed based on the probabilistic model. By repeating the generation of the motif by the probability model several times, the motif is expressed in detail while the sequence is gradually extended.

[0016]

Next, an embodiment of the present invention will be described with reference to the drawings. FIG. 1 is a diagram for explaining an embodiment of the method for discovering stochastic motifs of protein and gene sequences according to the present invention. In each of the drawings, a normal rectangle (a rectangle having a right-angled corner) represents data, a rectangle having a rounded corner represents a process, and a diamond represents a judgment and branch in the process.

In the present embodiment, sequence data 10 of an amino acid sequence in a protein or a base sequence in a gene is given as sequence data for which a motif is to be discovered. The sequence data 10 usually includes data on a plurality of sequences. First, the array data 10
Then, motif generation is performed by pattern processing, which is one type of symbol processing, to extract the motif 11 (step 101). Next, a matching part extraction process is executed (step 102), a part matching the motif 11 in the sequence data 10 is extracted, and the extracted part is set as the partial sequence data 12. A decompression process is executed (step 103), and the portion before and after the partial sequence data 12 is decompressed to obtain partial sequence data 13. Then, a motif generation process using a probability model is performed on the expanded partial sequence data 13 (step 104), a motif 11 represented by the probability model is generated, and the process returns to step 102. In the present embodiment, by repeating the steps 102 to 104,
Discover stochastic motifs.

Hereinafter, each processing will be described in more detail with reference to the drawings.

FIG. 2 shows an example of a table used in the motif generation process based on the pattern in step 101. In this table 50, the pattern and the number of arrays in which the pattern appears (the number of appearances) are written. Even when the same pattern appears twice or more in the same sequence, the number of occurrences is counted as one. This is to remove common sites that specifically appear in some sequences. Therefore, the value of the number of appearances in the table is always equal to or less than the number of arrays included in the given array data 10. The table exemplified here shows a pattern obtained when motif discovery was performed from 159 sequences including the leucine zipper motif and a part of the number of appearances thereof.

In the present embodiment, the pattern is in the form of a sequence of fixed amino acids or bases and arbitrary amino acids or bases. That is, a logical OR (OR) of amino acids or bases such as [ST] and {P} is not allowed. This means that only the simplest pattern is considered without considering the logical sum or the amount of information for the sake of calculation time. Even in the case of extraction using such a simple pattern, the present embodiment does not care since it is expressed in detail later by a probabilistic model.

The number of amino acids or bases determined in the pattern and the maximum length of any amino acid or base x are appropriately determined in advance. For example, when the number of amino acids or bases is determined to be 3 and the maximum length of x is determined to be 3, examples of patterns are “LxxExxxxL” and “Txx”.
xTA "and the like. Here, L and E represent leucine and glutamic acid, respectively, which are a kind of amino acids,
T and A represent thymine and adenine, which are a kind of base, respectively.

FIG. 3 is a flowchart showing a process for selecting patterns included in as many arrays as possible using the table shown in FIG. 2 in the motif generation process based on patterns in step 101. Sequence data 20 (=
The array data 10) is viewed from the top, and patterns are generated one by one by a pattern generation process (step 111).
It is determined whether the pattern is new in the same sequence (step 112). In step 112, if the generated pattern is not new, the process proceeds to step 116, and if the generated pattern is new, whether the pattern is a pattern already described in the table (see FIG. 2). It is determined whether the pattern is new in the table (step 113). If the pattern is not new in the table, 1 is added (incremented) to the number of occurrences of the pattern in the table (step 114), and step 116
Move to If the pattern is new in the table, the pattern is written in the table, the number of occurrences is set to 1 (step 115), and the process proceeds to step 116. In an amino acid sequence or a base sequence, not all patterns appear in the sequence.In this embodiment, each time a new pattern appears, the pattern is written in a table, and the table is extended. Saves memory for holding tables.

In step 116, it is determined whether all the arrays in the array data 20 have been extracted, that is, whether or not the data has been completed. If not, the process returns to step 111 to repeat the above-described processing, and proceeds to the next pattern generation. When the data ends, a pattern 21 having a higher number of appearances in the table is selected (step 117). This pattern 21 is used as a motif 11 in the next processing such as extraction of a matching part.

FIG. 4 shows a process for searching for a matching part when the motif 11 is represented by a pattern (step 1).
02) is a flowchart showing the process of FIG. Here, it is assumed that the motif 11 is given as the pattern 31. Note that the matching part search processing when the motif 11 is represented by a probability model will be described later with reference to FIGS. It is assumed that a partial sequence is not extracted from an array that does not include a pattern, and a large number of partial sequences are extracted from an array that includes many patterns. In addition, when the same part matches a plurality of patterns at the same time, the part is not extracted a plurality of times, but is extracted as one partial sequence.

For the given array data 30 (= array data 10), a partial array generation process is executed, and
The partial array 32 is generated (step 121). And
It is compared whether the partial array 32 matches any of the given patterns 31 (step 122). If any of them matches, the partial array 32 is written to the file (step 123), and the process proceeds to step 124. If not, the process directly proceeds to step 124. In step 124, it is determined whether or not the data is completed. If the data is not completed, the process returns to step 121 to repeat the process described here. If the data is completed in step 124, the process of searching for a matching part is ended. At this point, the partial array 33 matching the pattern 31 has been obtained in the file.

Next, the decompression process (step 103) will be described. The extension process is a process of adding a sequence element (base or amino acid) with a length before and after the partial sequence to the partial sequence data 12 searched and extracted from the sequence data 10 to extend the partial sequence. . Actually, it is only necessary to perform the extension processing at the time of extracting the matched part. This extension is performed not only to search for an evolutionary conserved site near the current motif, but also to align the start position and end position of the pattern. As an example, consider the case of finding the leucine zipper motif described above. In this motif, L (leucine) appears in cycle 7 "(L
xxxxxx) ⁿ L ". When the number of amino acids was determined to be 3 and the maximum length of x was determined to be 3 in the motif generation by the pattern, the results shown in the table of FIG. 2 were obtained as described above. If the decompression process is not performed, the partial sequence extracted by “KxxExL” or “LxKxxE” is learned as data different from the partial sequence extracted by the pattern of “LxxxxL”. Thus, learning can be performed by aligning the partial sequences extracted with those patterns.

Next, the motif generation processing using the probability model (step 104) will be described. Here, a hidden Markov model (HMM: Hidden Mar
kovModel) will be described. Hereinafter, the Hidden Markov Model is abbreviated as HMM.

Incidentally, Japanese Patent Application Laid-Open No. 7-36920 discloses a method of creating an HMM for protein sequence data. As shown in the examples in the publication, an HMM creation method for protein sequence data is as follows:
It can be applied to general signals. Therefore, in the present embodiment, the method described in JP-A-7-36920 is improved so that it can be applied to protein and gene sequences.
An HMM expressing the motif was created from the partial sequence. FIG. 5 is a flowchart showing a process of creating an HMM in the present embodiment. For details of the preparation process, see Japanese Patent Application Laid-Open No. 7-36920.

First, the maximum Nmax of the number of states of the HMM is given in advance, and the data of the given partial sequence (the partial sequence data 13 after decompression processing) is divided into learning data and evaluation data (step 131). In addition, the network structure of the initial HMM is defined as the total number of states with a small number of states plus the HM of the end state.
M (step 132). Next, the number of trials CN
Assuming that TMAX is specified, the initial parameter is set to a random number, the parameter estimation by the Baum-Welch algorithm is repeated for the training data by the number of trials CNTMAX, i represents the current number of HMM states, and candidate M has the maximum likelihood. The HMM is substituted (step 133). here,
Training data Y _1, Y _2, ..., and the likelihood for the Y _m, Prob
When (Y _i ) is the probability that the HMM outputs Y _i ,

[0030]

## EQU1 ## Prob (Y ₁ ) × Prob (Y ₂ ) ×... × P
lob (Y _m ). Then, it is determined whether or not the current state number i of the HMM has reached the maximum state number Nmax specified in advance (step 134). If i ≧ Nmax, the flow shifts to step 137 to perform post-processing. On the other hand, if i is Nma
If it is not x, the HMM at the current state number i
The above-mentioned candidate M is stored in bstMi _i (step 1).
35), the HMM to which a state is added from the candidate M except for transitions with a probability less than ε is set as the network structure of the initial HMM (step 136), and the process returns to step 133 to repeat the above process. Here, ε is a predetermined threshold value.

In the post-processing of step 137, the likelihood in the evaluation data is calculated for bstM _i , which is the HMM of each state number i, and the HMM having the maximum likelihood in the evaluation data is selected. , Erase the state not used for calculation (step 138). That is, a state in which the initial probability cannot be reached through some transitions from a state in which the initial probability is greater than zero and a state in which the final state cannot be reached through some transitions are excluded. The parameters are reestimated using both the learning data and the evaluation data based on the number of states of the HMM thus obtained and the data 35 of the network structure (step 139), and a motif based on a probability model is generated.

Although an example of the motif generation processing using the probability model has been described above, the motif generation processing using the probability model is not limited to the above-described processing. FIG.
9 is a flowchart illustrating another example of motif generation using a probability model. Hereinafter, the motif generation processing shown in FIG. 6 will be described.

First, the maximum Nmax of the number of states of the HMM is given in advance (step 141).
(Step 142). Next, the number of trials CNT
Assuming that MAX is specified, the initial parameter is set to a random number, parameter estimation by the Baum-Welch algorithm is repeated for the partial sequence data by the number of trials CNTMAX, i represents the current number of HMM states, and candidate M has the maximum likelihood. (Step 143). Then, it is determined whether or not the current state number i of the HMM has reached the maximum state number Nmax specified in advance (step 14).
4). If i ≧ Nmax, the flow shifts to step 147 to perform post-processing. On the other hand, if i is not Nmax, the above-mentioned candidate M is stored in bstM _i , which is the HMM with the current number of states i, and the description length of M is stored in MDL _i (step 145). An HMM to which a state is added from M except transitions with a probability less than ε is set as the network structure of the initial HMM (step 146), and the process returns to step 143.
Repeat the above process.

In the post-processing of step 147, M _i with the maximum MDL _i is selected (step 148), and the unused state is deleted from M _i by the same calculation as in the above example, and the unused state becomes the erased M _i to the motif by the probability model. Since MDL _i represents the description length of a candidate M _i, eventually, by the information criterion, the number of states and the network structure of the HMM will have been optimized.

The processing for creating a motif using a probability model based on the HMM has been described above. According to the HMM, gaps and mismatches can be easily expressed. The gap can be represented by a self-loop of the HMM, and the mismatch can be represented by the output probability of each state. Further, the HMM described in the present embodiment or JP-A-7-36920 is disclosed.
In the creation method, not only the left-to-right type but also a general network structure can be learned, so that a repeated motif or the like can be explicitly handled.

When actually finding a motif, there is a case in which the sequence data initially given contains a sequence containing no motif at all. This includes
A motif may be erroneously given as noise, or a motif of a subgroup of a given group may be extracted. In order to cope with these cases, the partial array Y _i having the low likelihood Prob (Y _i ) may be removed at a predetermined ratio. For example, in the case of the example shown in FIG. 5, when calculating the likelihood of the evaluation data in step 137, the likelihood is calculated by removing a partial array having a low likelihood at a predetermined ratio. Also, in this step 137, when re-estimating the parameters of the HMM of the network structure in the selected state using both the learning data and the evaluation data, the parameter estimation is performed excluding the partial sequence having a low likelihood. Similarly, in the case of the example shown in FIG. 6, in the post-processing (step 147), the parameter estimation may be performed again after removing the partial array with low likelihood.

Next, a matching part search process (step 10)
The processing when the motif 11 is represented by the probability model in 2) will be described. FIG. 7 shows an example of a table 51 used for extracting a matching part when the motif is represented by a probability model.

In Table 51, for each array, the array having the maximum likelihood for each array length among the partial arrays included in the array is written together with the maximum likelihood. Actually, for the extension process following the matching site search process, the partial sequence is extended, and the extended
1 may be written. The maximum and minimum of the array length are given in advance. For example, in the case of a protein motif, a minimum sequence length of 3 and a maximum sequence length of 50 are sufficient.
In the illustrated example, only the maximum likelihood is written, but in order to correspond to a state in which a plurality of motifs appear in the sequence, a table in which, for each sequence length, the partial sequence having the highest likelihood and the likelihood are used. You may.

FIG. 8 is a flowchart for explaining a process for extracting a matching part when a motif is represented by a probability model. Here, in the first half of the processing, candidates are narrowed down and preprocessing for normalization is performed, and in the second half, the likelihood is normalized and a partial sequence is selected from the candidates.

Assuming that data 41 indicating the maximum and the minimum of the sequence length (motif length) are given in advance, first, the sequence data 40 (= sequence data 10) is sequentially examined, and the maximum and the minimum of the sequence length (data 41) are determined. ), The partial arrays 43 are sequentially generated (step 151). Next, the likelihood (or probability) 44 of the given probability model 42 with respect to the partial array 43 is calculated (step 152). For example, when an HMM is used as the probability model 42, the likelihood of the partial sequence may be calculated by a forward-backward algorithm.

Next, pre-processing for normalizing the likelihood 44 with the array length is executed (step 153). In parallel with this preprocessing, the likelihood 44 is compared with the likelihood at the corresponding sequence number and sequence length in the table shown in FIG. 7 (step 15).
4) If the obtained likelihood 44 is not larger than the maximum likelihood described in the table, the process proceeds to step 156. If the likelihood 44 is larger than the maximum likelihood, the corresponding likelihood is determined in the table. After rewriting the partial array and likelihood (step 15
5) The process proceeds to step 156. In step 156, it is determined whether all the arrays in the array data 40 have been extracted, that is, whether or not the data has ended. If the data has not ended, the process returns to step 151 to repeat the above-described processing, and proceeds to the generation of the next partial array. On the other hand, when the data ends in step 156, at that time, a partial array having the maximum likelihood for each array and each array length and its likelihood are obtained in a table. A calculation for normalization is performed using the result of the preprocessing (step 157). In the normalization processing, the likelihood of the table is normalized using the constant obtained by the preprocessing. Then, a partial array having the maximum likelihood normalized for each array is extracted (step 1).
58). The partial sequence data 45 thus obtained
Are partial sequence data obtained as a result of the matching site search.

The constants A and B for normalization can be obtained from all likelihood data. However, since the amount of data is enormous, the calculation time and the storage area for the calculation are excessively required. And Therefore, in the preprocessing in step 153,
The obtained likelihood data 44 is put together. For example, only the data selected at random is stored, and step 1
At 57, constants A and B are calculated from the stored data. Alternatively, the likelihood of each subsequence is divided by the sequence length, further grouped by an appropriate number, and the average of the likelihoods of those groups and the standard deviation of the likelihood are stored. Using these compiled data, step 157
Then, the likelihood is normalized by the array length.

The value obtained by normalizing the likelihood by the array length is Z
It is called Score. This Z Score is obtained as follows. Now, consider normalizing the likelihood L of the partial array Y. The log likelihood log L of this subsequence Y
And the sequence length SeqLen, using constants A and B,

[0044]

## EQU2 ## It can be linearly approximated as Log L = A × SeqLen + B. From the likelihood data collected while processing in step 153 (preprocessing), constants A and B for normalization in step 157 are obtained, and a value log L (N) obtained by normalizing the likelihood by the following equation is obtained. Ask.

[0045]

(Equation 3) The average AV (N) and standard deviation SD (N) of this log L (N)
And calculate the ZScore of the subarray Y

[0046]

(Equation 4) And The average of Z Score is 0.0 and the standard deviation is 1.
0.

In the present embodiment, a stochastic motif is found by repeating the process represented by steps 102 to 104 in FIG. In the matching part extraction (step 102), when the same partial sequence as that of the previous repetition is extracted, when the length of the extracted partial sequence exceeds the predetermined sequence length, or when the predetermined number of repetitions is performed If there is, this repetition is terminated.

[0048]

As described above, according to the present invention, since a stochastic motif is discovered, a motif can be expressed more precisely than a pattern. Also, first, the array data is roughly narrowed down to the motif part by symbol processing such as patterns, and then learning using a hidden Markov model etc. is performed. It can be prevented from being applied too much.

[Brief description of the drawings]

FIG. 1 is a flowchart illustrating an embodiment of a method for discovering stochastic motifs of protein and gene sequences according to the present invention.

FIG. 2 is a diagram illustrating an example of a table used for a pattern-based motif generation process.

FIG. 3 is a flowchart illustrating a motif generation process using a pattern.

FIG. 4 is a flowchart illustrating a process of searching for a matching part when a motif is represented by a pattern.

FIG. 5 is a flowchart illustrating an example of a motif generation process using a probability model.

FIG. 6 is a flowchart illustrating another example of a process of generating a motif using a probability model.

FIG. 7 is a diagram showing an example of a table used for extracting a matching part when a motif is represented by a probability model.

FIG. 8 is a flowchart illustrating a process of extracting a matching part when a motif is represented by a probability model.

[Explanation of symbols]

10, 20, 30, 40 Sequence data 11 Motif 12, 13, 45 Partial sequence data 21, 31 Pattern 32, 33, 43 Partial sequence 35, 41 Data 42 Probability model 44 Likelihood 50, 51 Tables 101 to 104, 111 to 117, 121-124 steps 131-139, 141-148, 151-158 steps

──────────────────────────────────────────────────続 き Continuation of the front page (56) References JP-A-7-36920 (JP, A) Yada, Ishikawa, Tanaka, Asai "Hidden Markov Model and Signal Pattern Extraction of DNA Sequences by Genetic Algorithm" Information Processing Society of Japan Transactions, Vol. 37, No. 6, 1966, p. 1117-1129 Yada, Iinuma, Uchino, Ichiyoshi "Genome Information Analysis", Mitsubishi Research Institute, No. 29, 1996, p. 158-179 Konagaya, Nitta, Yamanishi "On the Concept of Genetic Information Base System" ICOT Research Bulletin, TM-1033, 1991 (58) Fields investigated (Int. Cl. ⁶ , DB name) G06F 17/30 JICST File (JOIS)

Claims (7)

(57) [Claims] 1. A method for finding a stochastic motif from sequence data of any one of a protein and a gene, wherein a motif extracted by symbol processing from given sequence data is used as an initial motif from the sequence data. A first step of extracting a subsequence that best fits the initial motif as a first subsequence; and elongating before and after the first subsequence to newly generate a second subsequence, A second step in which a probabilistic representation of the partial sequence is newly used as a motif; and a partial sequence that best matches the motif obtained in the second step is extracted from the sequence data and the second step is performed again. 1
And a third step in which the stochastic motif is found by repeatedly executing the second step and the third step after the execution of the first step. Compu
Probabilistic motif discovery method using a chromatography data. 2. In the first step, the number of appearances in the sequence data is calculated for a pattern that is a sequence of any one of amino acids and bases, and the pattern selected from the one with the largest number of occurrences is the initial pattern. The probabilistic motif finding method according to claim 1, wherein the method is a motif. 3. In the second step, the motif is expressed by using a hidden Markov model, and in the third step, a partial sequence that best fits the motif is extracted from the sequence data. The probabilistic motif finding method according to claim 1, wherein the likelihood is normalized, and a partial sequence having a high likelihood after the normalization is extracted. 4. In the second step, when the motif is stochastically generated using the sequence data, a hidden Markov model including a given number of states is used as an initial model, and a transition probability is equal to or less than a predetermined value. And combining the new states to generate a new hidden Markov model network structure, and then randomly setting a plurality of sets of initial parameters of the generated hidden Markov model of the network structure; and 4. The stochastic method according to claim 3, wherein the parameter calculation is repeatedly performed, and the hidden Markov model that gives the best result in the parameter calculation is set as a new hidden Markov model. How to discover motifs. 5. In the second step, in order to optimize the number of states and the network structure of the Hidden Markov Model, the array data is divided into learning data and evaluation data. Is used for learning the hidden Markov model, and the number of states and the network structure with the highest likelihood of the evaluation data are searched from the hidden Markov model after the learning. The method according to claim 4, wherein the parameter is re-estimated based on a structure, and the motif is generated stochastically. 6. The probabilistic motif finding method according to claim 3, wherein, in the second step, the motif is generated after removing a partial sequence having a low likelihood at a predetermined ratio. 7. The probabilistic motif discovery method according to claim 3, wherein the number of states and the network structure of the Hidden Markov Model are optimized based on the information amount.