JP2944434B2 - Apparatus and method for predicting RNA secondary structure - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

The present invention applies to a system for predicting the secondary structure of RNA.

[0002]

2. Description of the Related Art RNA is a polynucleotide in which a large number of four types of nucleotides, A (adenine), U (uracil), G (guanine), and C (cytosine), are linked and linearly linked. The linear polynucleotide is folded,
Create complex three-dimensional structures. This is because A (adenine) and U
This is because (uracil), G (guanine) and C (cytosine) form a pair. G as another combination
There are combinations of U, but they are rare. An area where pairs are continuous is called a stack area. For example, if a part of RNA has a GGGGGGG region and a CCCCCC region, G and C form a pair. . This stack region spirals in three dimensions, as seen in DNA. This stack region and other structures are the RNA 2
It has the following structure.

Conventional systems for predicting the secondary structure of RNA include those using DP programming, and two methods for finding candidates for all stack regions and finding the optimal combination. For an overview of these techniques, see Akiyama,
"Prediction of secondary structure of RNA", bit, vol25, no
10, pp. 83-91. (1993) (hereinafter referred to as Reference 1).

In the method using DP programming, the calculation time increases in proportion to the cube of the length n of the target array (O (n ³ )), and the storage capacity increases in proportion to the square ( O (n ^2)). This involves first calculating the energies of all base pairs in order to find the stack region that constitutes the minimum energy. The amount of calculation at this time is 2 of length n.
It is proportional to the power (O (n ² )). Since the stack area is composed of consecutive pairs, and includes some unpaired loop areas in the middle, it is necessary to investigate all possibilities in order to find the next pair that is continuous in the stack area.
Since all of these possibilities are proportional to the length n, the complexity is ultimately proportional to the cube of the length n of the array (O (n ³ )). In this method, since it is proportional to the cube of the length n, it is difficult to apply to a long array.

In order to solve the problem of the method using DP programming, there is a method of finding candidates for all stack areas and finding an optimal combination. For this,
Akiyama, Furuya, "High-speed RNA using energy minimization in target interconnected neural networks
Secondary Structure Prediction Method ", Symposium on Informatics, pp. 125
-134. (1992) (hereinafter referred to as Reference 2). Also in this method, since the number of all the stack area candidates increases in proportion to the length n, there is a method of limiting the search range and reducing the calculation amount. However, since the search space is limited, a long-distance stack region that should be predicted is out of the search range and cannot be predicted. Real R
In NA, distant bases may interact with each other, form pairs, and eventually form a stack region. That is, the actual secondary structure cannot be predicted without considering the long-range interaction. There is an example in which a short distance and a long distance are separated based on 200 bases. This is described in detail in Reference 2.

[0006]

In the conventional method described above, the amount of calculation for the search increases in proportion to the cube of the length, so that it is difficult to apply the method to a long array, or the stack area located at a long distance. There was a problem that it became impossible to make predictions.

An object of the present invention is to provide a system in which the amount of calculation for a search is proportional to the square of the length, and a long-range interaction can be predicted.

[0008]

According to the present invention, there is provided an apparatus for predicting RNA secondary structure, comprising: a base pair holding section for holding an arbitrary base pair of an RNA sequence to form a pair; A virtual distance holding unit for holding a distance, an energy calculating unit for calculating the energy of a stack region formed of a loop and a base pair formed of a plurality of bases, and a secondary structure holding unit for holding a predicted stack region And the virtual distance
For all base pairs that are at a short distance
Section, determine stack area candidates, and
The energy of the tack region candidate is calculated in the energy calculator.
And predict the stack area candidate with the minimum energy
Registered in the secondary structure holding unit as a stack area,
The virtual distance holding unit based on the predicted stack area
A prediction control unit that predicts the secondary structure of RNA by predicting the stack region one by one by updating the virtual distance .

[0009]

In the present application, the stack regions of RNA are predicted one by one, and finally all the stack regions are predicted to obtain the secondary structure prediction results. For that purpose, RNA is added to the base pair holding part.
For every base pair in the sequence, it is determined whether a pair is formed and retained. The pair recognizes uracil and guanine as a pair in addition to the Watson Crick pair (adenine and uracil, guanine and cytosine). In the virtual distance holding unit, R
The virtual distance between any base pairs in the NA sequence is maintained. The virtual distance is expressed assuming that the distance between bases in a linear state is 1. The distance between bases in the stack region is also represented as 1. According to this distance expression, even if the distance between base pairs is large, the distance between bases may be expressed as a short distance by forming a stack region. The secondary structure holding unit is a database that holds predicted secondary structures one by one. As a result, an area where a stack is not generated can be estimated. This is because a base forms a pair with at most one base. The energy calculation unit calculates the energy for creating a loop composed of a plurality of bases and the energy of a stack region composed of base pairs. These underlying parameters are described in Turner, D .; H. , Sugimoto,
N. and Freier, S.M. M. “RNA Str
ture Prediction ", Ann. Re.
v. Biophys. Biophys. Chem. 1
7: 167-192 (1988) (hereinafter referred to as Reference 3). In the prediction control unit, for a base pair whose virtual distance is short, the energy generated when the stack region is formed is calculated by the energy calculation unit, and the stack region forming the minimum energy is searched.
Since the search for the stack region is performed only for base pairs at a short distance, the calculation amount increases at most on the order of the square,
The conventional order of the third power can be reduced. At this time, a stack area that does not overlap with the stack area registered in the secondary structure holding unit is selected.

When one stack area is predicted, it is registered in the secondary structure holding unit. At the same time, the distance between bases in the virtual distance holding unit is updated. By estimating the stack area, the distance of the base pair included in the stack area is updated to 1, and the virtual distance, which reflects the influence of the base pair in the vicinity, is updated to the short distance. As a result, the virtual distance between bases that has been recognized as a long distance in a straight chain is reduced, and an opportunity to determine whether to constitute a stack region is obtained. This makes it possible for bases that are recognized as long-distance in a straight chain to form a stack region, and also allows for long-distance interactions that have been difficult in the past.

[0011]

DESCRIPTION OF THE PREFERRED EMBODIMENTS Embodiments of the present invention will be described with reference to the drawings.

FIG. 1 is a structural diagram showing an embodiment of the RNA secondary structure prediction apparatus of the present invention. This RNA secondary structure prediction device includes a base pair holding unit 11, a virtual distance holding unit 12,
It has a secondary structure holding unit 13, an energy calculation unit 14, and a prediction control unit 15.

Next, the operation of the embodiment of the present invention will be described. FIG. 2 is a flowchart showing a prediction procedure. The secondary structure prediction predicts the stack region of the RNA one by one, and finally predicts all the stack regions.

First, it is determined whether pairs are to be formed for all base pairs of the RNA sequence in the base pair holding unit 11 and initialization is performed (step 22). Specifically, it is determined whether any two bases in the sequence form a pair, and if so, the flag is set to 1, and if not, 0 is set. The pair recognizes U and G as a pair in addition to the Watson clip pair (A and U, G and C).

Initial setting of the virtual distance holding unit 12 is performed (step 23). The virtual distance is expressed assuming that the distance between bases in a linear state is 1. FIG.
This shows the initial state of the virtual distance holding unit 12 for an RNA sequence having a length of 10. The circles in FIG. 3A correspond to each base. The numbers in the circles are serial numbers from the first five terminals, and are sequentially assigned from 1 to 10. The number below the circle is the virtual distance from the third base,
The virtual distance is 2 for the fifth base and 8 for the eleventh base. In this way, the virtual distance between all the bases is determined, and the value is set as the initial value of the virtual distance holding unit 12. FIG. 3B is an example of an initial value of the virtual distance holding unit 12. As described, the virtual distance between the third base and the eleventh base is 8.

The prediction control unit 15 first determines a stack area candidate for all base pairs whose virtual distances are short, with reference to the contents of the base pair holding unit 11 (step 24). In the stack area, pairs are continuous.
For this purpose, for example, a continuous pair of a second base and a tenth base, a third base and a ninth base, and a fourth base and an eighth base are required. Since the pairs are registered in the base pair holding unit 11, all the consecutive pairs are searched from the pairs as described above. For various ways of doing this, see Kanehis.
a, M. and God, W.C. B. , “Patter
n Recognition in Nucleic
Acid Sequences ", Nucleic A
cids Research, vol 10, no. 1,
pp. 265-278. (1982) (hereinafter cited reference 4)
).

Energy is calculated by the energy calculator 14 for all stack area candidates (step 26).
This energy is energy generated when one stack area candidate of interest is added to the current configuration of the secondary structure. Details will be described in the section of the energy calculation unit 14. From all the stack area candidates, the stack area that forms the minimum energy is selected and set as the predicted stack area. At this time, the stack area to be selected is selected so as not to overlap with the stack area registered in the secondary structure holding unit 13. This means that the base is at most 1
This is due to forming a pair with only one base. The fact that the stack region registered in the current state and a part of the prediction stack overlap also means that the base of the registered pair and the base of the prediction stack region further form a pair, and one base is This is because a pair is formed with two bases. If an appropriate stack area cannot be found, the process ends.

The energy calculator 14 calculates the energy of the stack area. This calculation algorithm is described in Studnicka, G .; M. , Rahn, G .;
M. , Cummings, W.C. and Salser,
W. A. , “Computermethod for
predicting the secondaries
structure of single-starnd
ed RNA "Nucleic Acids Rese
arch, vol5 no9, pp. 3365-338
7 (1978) (hereinafter referred to as cited document 5). The parameters used in the algorithm are
Reference 3 details this. In FIG. 6, these parameters are shown on a matrix. FIG. 7 shows parameters of the energy of the loop. An example of energy calculation will be described with reference to FIG. The energy is energy generated when one stack area candidate of interest is added. That is, it is the sum of the energy generated by the stack region and the energy generated by the loop region sandwiched between the stack regions and not forming the stack. In FIG. 5, an area of a stack having a length of 6
And a hairpin loop having a length of eight.

The energy in the stack area is given by the sum of the energy composed of the two pairs. In the example of FIG. 5, the energy of the region formed by the eighth and nineteenth base pairs and the ninth and nineteenth base pairs is -2.9 according to FIG. 6 (j). . Similarly, the energy of the region is -1.5 according to FIG. 6 (o), the energy of the region is -0.7 according to FIG. 6 (d),
The energy of the region is -1.1 according to FIG. 6 (m), and the energy of the region is -2.1 according to FIG. 6 (j). Therefore, the energy of this stack region is -8.3.
(= -2.1-1.1-0.7-1.5-2.9) kc
al / mol. Further, the energy of the hairpin loop having a length of 8 is +5.5 kcal / mol from FIG. Therefore, if this stack area is configured,
The total amount is -2.8 kcal / mol.

When one stack area is predicted, it is registered in the secondary structure holding unit 13 (step 27). Nothing is registered as the initial state of the secondary structure holding unit 13. The registration registers bases that constitute the stack area.
The stack region shown in FIG. 4 is the second region and the tenth base,
It is registered as a stack area composed of a pair of a third base and a ninth base and a fourth base and an eighth base. By registering in this manner, a stack region candidate including the second base, the third base, the fourth base, the eighth base, the ninth base, and the tenth base is not generated thereafter. This is due to the fact that a base forms a pair with at most one base. The fact that the stack region registered in the current state and a part of the prediction stack also overlaps means that the base of the registered pair and the base of the prediction stack region further form one pair of bases. It is because it becomes.

The distance between bases in the virtual distance holding unit 12 is updated (step 28). By estimating the stack region, the distance between base pairs included in the stack region is 1
And the virtual distance is updated to a short distance, the effect of which is reflected on nearby bases. FIG. 4A shows a pair of the second and tenth bases, the third and ninth bases, and the fourth and eighth bases of the RNA sequence having a length of 10 shown in the upper part of FIG. This is a state when a stack area is predicted. The numbers around the circle are virtual distances from the third base, and since the third base and the ninth base form a pair, the virtual distance has been updated to 1. Accordingly, the virtual distance is 3 for the eleventh base. FIG. 4B shows the virtual distance holding unit 1 updated in this manner.
2 shows an updated state. In this case, the second base and the tenth base, and the third base and the ninth base forming a pair are
The virtual distance between each pair of base, fourth base and eighth base is 1. Accordingly, the virtual distance between bases in the vicinity of the stack region has also been updated.

By estimating the stack region, the virtual distance between bases, which is recognized as a long distance in a straight chain, becomes shorter in this way. In the conventional method, in the method of limiting the search range and reducing the amount of calculation, the search space is limited, and the long-distance stack region that should be predicted is outside the search range. Become impossible.
In the present application, the distance between the bases is updated, and as a result of the prediction of the stack area, the virtual distance between the bases at a long distance becomes short, and an opportunity to determine whether to configure the stack area is obtained. This makes it possible for bases that are recognized as long-distance in a straight chain to form a stack region, and also allows for long-distance interactions that have been difficult in the past.

The above operation is controlled by the prediction control unit 15.

[0024]

According to the conventional method, the amount of calculation for the search increases in proportion to the cube of the length, so that it is difficult to apply the method to a long array, and it becomes impossible to predict the stack area at a long distance. There were problems such as doing.

In the present invention, the computational complexity for the search is proportional to the square of the length, and long-range interactions can also provide prediction.

[Brief description of the drawings]

FIG. 1 is a configuration example showing an embodiment of an RNA secondary structure prediction device.

FIG. 2 is a flowchart showing a procedure.

FIG. 3 is a diagram showing an initial state of a virtual distance holding unit 12;

FIG. 4 is a diagram showing an updated state of a virtual distance holding unit 12;

FIG. 5 is a diagram showing an example of energy calculation.

FIG. 6 is a diagram showing an example of an energy parameter of a stack area.

FIG. 7 is a diagram showing an example of parameters of energy of a loop.

[Explanation of symbols]

 Reference Signs List 11 base pair holding unit 12 virtual distance holding unit 13 secondary structure holding unit 14 energy calculation unit 15 prediction control unit

──────────────────────────────────────────────────続 き Continuation of front page (56) References bit, Vol. 25, No. 10, 1993. pp. 83-91 (1993) Symposium on Informatics, (1992.1) pp. 125-134 Ann. Rev .. Biophys. Chem. 1988. 17: 167-192 Nucleic Acid Research arch. Vol. 10, No. 1, 1982, pp. 265-278 Nucleic Acid Research arch. Vol. 6, No. 9, 1978, p. 3365-3387 (58) Field surveyed (Int.Cl. ⁶ , DB name) C12N 15/00 G06F 17/00

Claims (3)

(57) [Claims] 1. A base pair holding unit that holds whether any base pair of an RNA sequence forms a pair, a virtual distance holding unit that holds a virtual distance between arbitrary base pairs of an RNA sequence, and a plurality of bases. An energy calculation unit for calculating the energy of a stack region formed of loops and base pairs, a secondary structure holding unit for holding a predicted stack region, and the virtual distance
For all base pairs separated by a short distance,
Determine stack area candidates with reference to
The energy of the stack area candidate is sent to the energy calculator.
Calculation to find a stack area candidate with the minimum energy.
Registered in the secondary structure holding section as a measurement stack area,
Before the virtual distance holding unit based on the predicted stack area
A prediction control unit that predicts a secondary structure of RNA by predicting a stack region one by one by updating the virtual distance . 2. A base pair holding unit for holding whether any base pair of an RNA sequence forms a pair, a virtual distance holding unit for holding a virtual distance between arbitrary base pairs of an RNA sequence, and a plurality of bases. An energy calculation unit that calculates the energy of a stack region composed of loops and base pairs that are formed, a secondary structure storage unit that holds a predicted stack region, and a base pair whose virtual distance is short. Using the contents of the base pair holding unit to determine a stack area candidate, instructing the energy calculation unit to calculate energy for the determined stack area candidate, and predicting the stack area candidate having the minimum energy as a predicted stack area And a prediction control unit for predicting the secondary structure of RNA by predicting the stack region one by one.
Secondary structure prediction device. 3. It is determined whether pairs are formed for all bases of the RNA sequence, a virtual distance of the RNA sequence is determined, and a candidate for a stack region is determined based on the determination for base pairs whose virtual distances are short. Calculating the energy for the obtained stack area candidate, registering the calculated stack area candidate having the minimum energy as the predicted stack area, and updating the virtual distance based on the predicted stack area. Characteristic method for predicting RNA secondary structure.