JP3395633B2 - DNA base sequence comparison method - Google Patents

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a DNA base sequence comparison method and a search method, and more particularly to a method for sensitively detecting the degree of similarity between DNA base sequences and a method for estimating an amino acid sequence encoded by the DNA base sequences. Regarding

[0002]

2. Description of the Related Art In recent years, movements for determining the DNA base sequences of various organisms and analyzing the functions of proteins encoded by the DNA base sequences have become popular. The DNA base sequence is a sequence of four types of bases A, C, G and T.
A part of the nucleotide sequence codes for a protein that functions in a living body. A protein having an important function can be used for drug design and development, and a technique for accurately estimating the function of a protein encoded by a DNA base sequence is desired. Generally, it is technically easier to determine a DNA base sequence than to experimentally determine the sequence of a protein.

In the estimation of the function of the protein encoded by the newly determined DNA base sequence, the starting point of translation into amino acids is determined in correspondence with each well-known codon table (3 base units (codon unit)), The end point of translation into amino acid, the type of amino acid is defined), and the DNA base sequence is translated into an amino acid sequence (a protein sequence can be obtained from this amino acid sequence), and the obtained protein sequence and function Is compared and compared with the data on a known protein to determine whether or not they are similar.

In the DNA base sequence, an exon region containing protein information is a region translated into an amino acid. Translation from a codon to an amino acid is performed uniquely, and if the translation direction of the DNA base sequence and the translation start point are known, every 3 bases are extracted from the DNA base sequence and DN
The A base sequence can be translated into an amino acid sequence, that is, a protein. However, in the DNA base sequence, when there is an error due to the insertion or deletion of bases in the DNA base sequence, the exon region of the DNA base sequence is displaced.
Since the DNA base sequence is translated into amino acids on a codon basis, it may be translated as a completely different amino acid when a base insertion or deletion is present.

When comparing two DNA base sequences, 2
To compare and execute translated amino acid sequences obtained by translating three DNA base sequences into amino acid sequences,
It is necessary to determine the translated amino acid sequence from each DNA base sequence.

FIG. 1 is a diagram for explaining six types of reading frames for a DNA base sequence when translating a DNA base sequence into an amino acid sequence ((first prior art): eg, Document 1: Biotechnology textbook). Series 11 “Introduction to Computers for Biotechnology”, Haruki Nakamura
Kenta Nakai, pp. 66-67 (1995) (Tokyo: Corona).

The six types of translation frames are frame (1): a frame in which the 5'end of the DNA base sequence is sequentially translated into amino acids in codon units, and frame (2): the start position of the codon is sequentially 1 from frame (1). Base shift (s
frame for translating amino acid by hift), frame (3): frame for translating amino acid by sequentially shifting the start position of codon by 2 bases from the start position of frame (1),
Frame (4): A frame in which translation of amino acids is sequentially started in a codon unit from the 5'end of the complementary strand of the DNA base sequence. Frame (5): One amino acid is sequentially shifted from the translation start position of frame (4) to an amino acid. And a frame (6): a frame for starting translation into amino acids by sequentially shifting two bases from the translation start position of frame (4).

The frame (1) to the frame (3) are 5 '
Frames (4) to (6) are sequentially shifted from the end by 1 base, and 5'end of the complementary strand of the original DNA base sequence (3 'end of the original DNA base sequence)
Since one base is sequentially shifted from, there are six types of translation frames, frame (1) to frame (6). For frame (1) to frame (6), D
The NA base sequence is translated into an amino acid sequence. 2 each DN
A comparison is performed between the translated amino acid sequences obtained by translation using the same type of frame for the A base sequence, and a total of 6 types of translated amino acid sequences are compared.

BLAST developed by Altshul et al. Of NCBI, which is an organization of NIH in the United States, whose source program is open to the public as a typical program for searching for similar sequences, is widely known (for example, 141st of Reference 1). Pp. 143). In the BLAST family,
BLASTN comparing DNA base sequences, BLASTP comparing amino acid sequences, and 6 kinds of translated amino acid sequences obtained by mechanically translating the DNA base sequences for the above 6 kinds of frames are stored in an amino acid sequence database. BLASTX to search using, and
Search DNA base sequence (Query DNA base)
sequence) and a DNA base sequence (Target DNA) read from a database of DNA base sequences.
The first and second DNA base sequences of base sequence) are mechanically translated for each of the above-mentioned 6 types of frames, and 36 sequences between the translated amino acid sequences of the first and second sets (6 types each). There is TBLASTX that compares for all combinations of types. In the BLAST family, first, Query DNA base sequence
ence constant length base sequence and Target DNA b
Performs high-speed pattern matching with the target sequence and obtains Target DNA base sequence.
Query DNA base sequence based on the position of the detected base sequence of fixed length
An area similar to e is detected.

In the Smith-Waterman method, Q
user DNA base sequence and Ta
The bases of the two DNA base sequences of the rget DNA base sequence are compared one by one, and a score (similarity) according to the base pair is given and totaled. , Juxtaposition) ((Third Prior Art): For example, Reference 2: “Identification of Comm.
on Molecular Subsequence
s ", Journal of Molecular Biology, 147 (1981) pp. 195-197 (J.M.
ol. Biol, 147 (1981) pp195-19.
7)).

In the third conventional technique, a dynamic programming method (dynamic programming method is used to compare base pairs between two DNA base sequences to obtain a score between the two DNA base sequences. A specific DNA base sequence of interest (hereinafter, referred to as a search DNA base sequence (Query DNA)
base sequence) or a first DNA base sequence), when searching a DNA base sequence database for a DNA base sequence similar to the first DNA base sequence, the searched DNA base sequence (the number of bases is M) is the first axis (for example, x axis)
DNA read from the DNA nucleotide sequence database
Base sequence (the number of bases is N, hereinafter Target DN
A base sequence, or second DNA base sequence) along the second axis (eg, y-axis),
It is arranged from the 5 ′ end to form a matrix (hereinafter referred to as a score matrix in the present invention) (FIG. 2).

FIG. 2 is a diagram for explaining a score addition path when the first and second DNA base sequences are compared.
Base pairs between the first and second DNA base sequences are score matrix elements (i, j) (where i = 1, 2, ...,
M, j = 1, 2, ..., N).

In dynamic programming, a score matrix element (i, j) is reached,
Considering a movement route (search route) in three directions of vertical, horizontal, and diagonal (a, b, and c shown in FIG. 2), i is 1, 2, → M, j is 1, 2, → N. In the direction from the score matrix element (1, 1) at the upper left end to the score matrix element (M, N) at the lower right end (i,
j) is moved to move the first DNA base sequence to the second
The optimal path (optimal alignment, optimal juxtaposition) that represents the optimal similarity correspondence between each base of the DNA nucleotide sequence of

The value H of the score matrix element (i, j)
(I, j) is the overall similarity (score) between the base sequence up to the i-th base of the first DNA base sequence and the base sequence up to the j-th base of the second DNA base sequence Represents the total of. The total H of the similarities (scores) corresponding to the moving paths in the directions a, b, and c shown in FIG.
_a (i, j), H _b (i, j), H _c (i, j) are the first
Score s (i, which represents the degree of similarity between the i-th base of the DNA base sequence and the j-th base of the second DNA base sequence
j), the gap penalty score p, and the source score matrix elements (i-1, j-1), (i
-1, j), (i, j-1) similarity (score)
Of H (i-1, j-1), H (i-1, j), H
Using (i, j-1), each is defined by (Equation 1), (Equation 2), (Equation 3). As H (i, j), H _a
The maximum value ((Equation 4)) of (i, j), H _b (i, j), and H _c (i, j) is selected. The score s (i,
j) can be determined using a pre-stored score table. For example, the score for a matching 1 base pair is 4 points, and the score when an n base insertion or deletion is (-8n). -4) and the score for different one base pairs are set to (-3).

[0015] _{H a (i, j) =} H (i-1, j-1) + s (i, j) ... ( number _{1) H b (i, j} ) = H (i, j-1) + p ... (Equation 2) H _c (i, j) = H (i−1, j) + p (Equation 3) H (i, j) = max {H _a (i, j), H _b (i, j) , H _c (i, j)} (Equation 4) It should be noted that the gap penalty score p added in the movement path b is calculated based on the deletion of the base after the i-th base of the first DNA base sequence. The gap penalty score p corresponding to the existence and added in the movement path c is the second DNA.
Corresponds to the presence of a base deletion after the jth base in the base sequence.

Along the moving path from the score matrix element (1, 1) to the score matrix element (M, N), i is changed to 1, 2, → M, j is changed to 1, 2, → N. The first DNA base sequence and the second DNA base sequence are compared with each other by adding a score or a gap penalty score according to the movement route.
H ^* = H (M, N), which maximizes the total similarity (score) with the base sequence, is obtained, and as a result, between the first and second DNA base sequences. It is possible to find the arrangement in which the similarity is the best, that is, the optimum alignment (alignment) that represents the optimum correspondence relationship between each base of the first DNA base sequence and each base of the second DNA base sequence.

The third conventional technique can be used for examining the similarity between two amino acid sequences as well as for examining the similarity between two DNA base sequences.

[0018]

In the first prior art described above, when there is a base insertion or deletion in the DNA base sequence, a frame shift is made at the position where the base insertion or deletion exists. However, there is a problem in that the base sequence after the position where this frame shift occurs does not lose the similarity of the amino acid sequence that it originally has, and the amino acid sequence that should have it cannot be extracted, resulting in missing search. Of the six types of frames, for example, even if an amino acid sequence very similar to the amino acid sequence translated in frame (1) of one DNA base sequence exists in the translated amino acid sequence of the other DNA base sequence, When there is an insertion or deletion of a base in the base sequence, the position of the frame is changed to frame (2) or (3) in the base sequence after the position where the insertion or the deletion exists. . In the prior art, D considering the case where the position of the reading frame caused by the insertion or deletion of the base in the DNA base sequence is changed.
Neither NA base sequence comparison method nor search method is disclosed.

The above-mentioned second prior art TBLASTX
In the BLAST family that includes, because no gaps due to insertions or deletions of bases in the DNA base sequence or amino acids in the amino acid sequence are taken into consideration in order to ensure high-speed calculation, there is a missing search. There is a problem that it will occur.

The above-mentioned third conventional technique is one of the accurate search methods, but it has a problem that it takes a long time to perform the comparison for each base of the DNA base sequence. In addition, by combining the first conventional technique with the third conventional technique, two DNA base sequences (Query DNA bases) are combined.
Sequence and Target DNA base
When the translated amino acid sequences are compared with each other after being translated into amino acid sequences, the first and second DNAs obtained by translation corresponding to the six types of frames described in the first conventional technique. Since it is necessary to perform the comparison for each combination (36 types) of translated amino acid sequences related to the base sequence, there is a problem that it takes more search time.

Furthermore, the Smith-Wa of the third prior art is used.
When the terman method is combined with the first conventional technique, insertion or deletion in an amino acid unit or a codon unit of a DNA base sequence can be considered, but in a base unit other than a multiple of the codon unit in the DNA base sequence. There is a problem that the insertion or the deletion cannot be taken into consideration, and hence the change of the position of the frame cannot be taken into consideration.

In the prior art, it was not considered to prevent the occurrence of erroneous search results caused by the insertion or deletion of bases existing in the DNA base sequence. That is, translation of a DNA base sequence into an amino acid sequence in consideration of the presence or absence of base insertion or deletion is not a known document, but Japanese Patent Application No. 7-265157 (Reference 3) describes , The first and second DNA base sequences are each 3
The first and second intermediate DNA base sequences are generated by dividing them into bases, and the first and second intermediate DNA base sequences are translated into amino acids to generate the first and second translated amino acid sequences. 1
A first similarity between the DNA base sequence and the first intermediate DNA base sequence, and a second similarity between the second DNA base sequence and the second intermediate DNA base sequence, Third between the first translated amino acid sequence and the second translated amino acid sequence
Of the first, second, and third similarities so that the parameter obtained by using a predetermined function becomes maximum, and the first and second intermediate DNA base sequences, and the first and second intermediate DNA base sequences A method for comparing DNA base sequences, which selects the second translated amino acid sequence, is disclosed.

Although not a known document, Japanese Patent Application No. 8-1
No. 67770 (Reference 4) contains a search DNA base sequence (Q
A translated amino acid sequence obtained by translating a user DNA base sequence into an amino acid in consideration of insertion or deletion of a base, and an amino acid sequence (Target aminoac) read from an amino acid database.
id sequence) and Smith-Wate
Based on the rman method, the i-th amino acid in the translated amino acid sequence was compared with the target aminoacids.
The score (similarity) in the comparison with the jth amino acid of the sequence was evaluated in consideration of the seven types of pathways, and the translated amino acid sequence and the Target amino acid
Disclosed is a sequence comparison method that performs a sequence comparison with a sequence.

However, Document 3 does not disclose a technique regarding a specific path in the operation of dynamic programming.
Further, in Reference 4, a method for translating a search DNA base sequence into an amino acid sequence by translating a codon by shifting 1 or 2 bases and translating it into an amino acid (corresponding to the first translation method of the present invention) is disclosed. However, there is no disclosure of the second and third translation methods of the present invention, which will be described in detail later. Further, Document 4 does not disclose a technique of comparing a translated amino acid sequence obtained from a searched DNA base sequence with a translated amino acid sequence obtained by translating a DNA base sequence read from a DNA base sequence database into amino acids.

The object of the present invention is to consider the insertion and deletion of the bases existing in the DNA base sequence and to consider the query DNA base sequence (Query DNA base sequence).
e), D read from the DNA nucleotide sequence database
NA base sequence (Target DNA base seq
of the DNA base sequences are translated into amino acid sequences, and the two amino acid base sequences are compared with each other by interposing the translated amino acid sequences. It is intended to provide a method for detecting similarity between sequences with high sensitivity and a method for estimating an amino acid sequence encoded by a search DNA base sequence.

[0026]

In the DNA nucleotide sequence comparison method of the present invention, first, when comparing the similarity between the first and second DNA nucleotide sequences, each DNA nucleotide sequence is inserted,
Alternatively, divide every 3 bases containing the deletion. Each of the three divided bases is translated into an amino acid based on the codon table, and the amino acids are inserted between the obtained first and second translated amino acid sequences in consideration of insertion and deletion of amino acids in each amino acid sequence. The similarities are summed up to obtain the total score (similarity). A combination of amino acids of the first and second translated amino acid sequences having the maximum total similarity (score total) is obtained, and the maximum score total value and the juxtaposition of the first and second translated amino acid sequences are arranged. The alignment between the DNA base sequence corresponding to the first translated amino acid sequence and the DNA base sequence corresponding to the second translated amino acid sequence is obtained. A search DNA base sequence (specific DNA base sequence of interest, Query DNA base sequence) is used as the first DNA base sequence.
e) as the above-mentioned second DNA base sequence, and various DN
A known DNA base sequence read from the A base sequence database (Target DNA base sequence)
nce).

In the method for translating a DNA base sequence into an amino acid sequence used in the method for comparing DNA base sequences of the present invention, the first, second and third translation methods are used in combination.

In the first translation method, a frame for reading a DNA base sequence is translated into an amino acid sequence according to a predetermined translation rule while sequentially shifting the bases by 3 bases in units of 3 bases from the end of the DNA base sequence.

In the second translation method, the frame for reading the DNA base sequence is sequentially shifted by 1 base in units of 4 bases from the end of the DNA base sequence, and the second of the 4 bases is regarded as the inserted base. The remaining 3 bases out of 4 bases are used to translate into an amino acid sequence according to a predetermined translation rule.

In the third translation method, the frame for reading the DNA base sequence is sequentially shifted by one base in units of four bases from the end of the DNA base sequence, and the third base of the four bases is regarded as the inserted base. The remaining 3 bases out of 4 bases are used to translate into an amino acid sequence according to a predetermined translation rule.

In the DNA base sequence comparison method of the present invention, a total score (similarity) is obtained as a sequence comparison method between first and second translated amino acid sequences translated from the first and second DNA base sequences. Dynamic programming is used as the calculation method. In the calculation in dynamic programming, the first and second DNA
The i-th position of the first translated amino acid sequence represented by the element (i, j) of the score matrix composed of the first and second translated amino acid sequences, each translated from the base sequence by the above-mentioned first translation method When the scores (similarity) of the amino acid of γ and the j-th amino acid of the second translated amino acid sequence are summed, an integer satisfying k ≧ 1, m ≧ 1 and an integer satisfying n ≧ 2 are score matrix elements. , (I-3,
j-3), (i, j-3k), (i-3k, j), (i
-3n + 1, j-3n), (i-3n, j-3n +
1), (i-3m, j-3m-1), (i-3m-1,
Consider 7 routes from j-3m). k = 1, m =
If 1, n = 2, score matrix element, (i
-3, j-3), (i, j-3), (i-3, j),
(I-5, j-6), (i-6, j-5), (i-3,
j-4) and (i-4, j-3) will be considered. However, each element in parentheses is a positive number. Note that i ≦ M (M is the number of amino acids in the first translated amino acid sequence) and j ≦ N (N is the number of amino acids in the second translated amino acid sequence).

The DNA nucleotide sequence comparison method of the present invention is summarized as follows using FIG. The search DNA base sequence and the DNA base sequence read from the database are translated into amino acid sequences (304, 306), and the similarity between the translated amino acid sequences is calculated in consideration of the insertion and deletion of bases and amino acids, Calculation of total score by dynamic programming (307) and calculation of total upper score and path by dynamic programming for two translated amino acid sequences that give the total upper score obtained as a result of comparative search (312)
And the trace calculation (313) of the path that gives the maximum score total, and the alignment result between translated amino acid sequences is displayed together with the alignment of DNA base sequences. Even when there are insertions and deletions in the two DNA base sequences to be compared, it is possible to compare the similarity between the DNA base sequences by interposing the translated amino acid sequence, and the search sensitivity is improved.

[0033]

BEST MODE FOR CARRYING OUT THE INVENTION Hereinafter, a search DNA base sequence (query DN
An example of executing the search for the (A base sequence) will be described.

FIG. 3 is a flow chart for explaining an example of processing steps in the embodiment of the present invention. An outline of the DNA nucleotide sequence comparison method of the example of the present invention will be described with reference to FIG. First, (step 301) to (step 304) are executed.

(Step 301): A score table representing the degree of similarity of amino acid pairs is input.

(Step 302): As a result of searching the DNA base sequence database, the number of output of the search result having the total upper scores, which is output and displayed on the output device, is input.

(Step 303): Search DNA base sequence (Q
Enter the user DNA base sequence.

(Step 304) The translated DNA sequence is translated into an amino acid sequence by the first, second, and third translation methods, which will be described later, and the translated amino acid sequence. A ₁ , A ₂ , A ₃ , A ₄ , A ₅ , A ₆
To get

The translated amino acid sequence A ₁ is translated from the searched DNA base sequence by the first translation method. The translated amino acid sequence A ₂ is translated by the first translation method from the complementary chain sequence of the searched DNA base sequence. The translated amino acid sequence A ₃ is translated from the searched DNA base sequence by the second translation method. The translated amino acid sequence A ₄ is translated from the searched DNA base sequence by the third translation method. Translated amino acid sequence A ₅
Is translated by the second translation method from the complementary strand sequence of the search DNA base sequence. The translated amino acid sequence A ₆ is the search DNA
It is translated by the third translation method from the complementary chain sequence of the base sequence.

Next, all DNA base sequences (Target DN) read from the DNA base sequence database
The following (step 305) to (step 308) are executed for A base sequence.

(Step 305): DNA base sequence (Target DNA ba) from the DNA base sequence database
(se sequence) is read.

(Step 306): The read DNA base sequence and the complementary strand sequence of the read DNA base sequence are subjected to an amino acid sequence by each of the first, second and third translation methods described later. Translated into the translated amino acid sequence B ₁ ,
B ₂ , B ₃ , B ₄ , B ₅ , and B ₆ are obtained.

The translated amino acid sequence B ₁ is the read DN
The A base sequence is translated by the first translation method. The translated amino acid sequence B ₂ is translated from the complementary chain sequence of the read DNA base sequence by the first translation method. The translated amino acid sequence B ₃ is translated from the read DNA base sequence by the second translation method. The translated amino acid sequence B ₄ is translated from the read DNA base sequence by the third translation method. The translated amino acid sequence B ₅ is the read DNA
The complementary chain sequence of the base sequence is translated by the second translation method. The translated amino acid sequence B ₆ is translated by the third translation method from the complementary chain sequence of the read DNA base sequence.

(Step 307): Combination of four kinds of translated amino acid sequences obtained in (Step 304) and Step (306), that is, (a) combination of translated amino acid sequences A ₁ and B ₁ , (b) A combination of translated amino acid sequences A ₁ and B ₂ , (c)
For the four combinations of the translated amino acid sequences A ₂ and B ₁ and (d) the translated amino acid sequences A ₂ and B ₂ , the total similarity between the translated amino acid sequences was calculated by dynamic programming. Calculate each.

(Step 308): A DNA base sequence having a total of upper scores up to the number of output of the search result is selected, and information of the DNA base sequence having the total of upper scores is read from the DNA base sequence database and stored.

Next, after performing the following (step 305) to (step 308) for all the DNA base sequences read from the DNA base sequence database, (step 309) to (step 311) are performed. Run.

(Step 309): The highest total score corresponding to the number of output of the search result is sorted by arranging from the largest total value of the similarity (score).

(Step 310): D having the total of the upper scores
The NA base sequence is displayed on the display (403 in FIG. 18). At this time, the DNA base sequence having the total upper scores is stored in an external storage device such as a hard disk (404 in FIG. 18).
You may output to.

(Step 311): In (Step 310), the number of retrieval comparison results (the number of outputs of the juxtaposition result) which is considered to be desirable to display the juxtaposition result is judged from the displayed total upper scores. input.

Next, a DNA base sequence (Target DNA base sequence) displaying the alignment result is displayed.
e)), from (step 312) to (step 31)
Execute 4).

(Step 312): The total score and the route by the dynamic programming are calculated.

(Step 313): By calculating the trace of the route that gives the total score, the alignment result between the searched DNA base sequence and the two translated amino acid sequences obtained from the DNA base sequence of the DNA base sequence database and , Alignment results between DNA base sequences corresponding to each translated amino acid sequence are obtained.

(Step 314): The juxtaposed result obtained in (Step 313) is displayed on the display (403 in FIG. 18). At the same time, the data may be output to an external storage device (404 in FIG. 18) such as a hard disk.

FIG. 4 is a diagram showing Blosum 62, which is an example of a table of the prior art which defines the scores to be given to the amino acid pairs used in the examples of the present invention. A, R, N, ..., Shown on the horizontal and vertical axes of FIG.
W, Y, V are abbreviations for amino acids. Symbol "B (As
*) "Indicates either Asn or Asp, the symbol" Z (Gl *) "indicates either Gln or Glu, and the symbol" X (***) " Indicates an untranslatable or unknown amino acid, and the number "O (Stp)" indicates
Indicates the termination codon.

In the following description, the searched DNA base sequence and DNA are considered in consideration of the insertion and deletion of bases.
A method of translating each base sequence of the DNA base sequence read from the base sequence database into an amino acid sequence ((step 304), (step 306) will be described.

FIG. 5 is a diagram showing a codon table of the prior art in which the termination of translation into amino acids and the types of amino acids are defined in correspondence with each of the three base units (codon units) in the codon table. The symbols in parentheses indicate the abbreviations for the one-letter amino acids. According to FIG. 5, the DNA base sequence is encoded by one type of amino acid every 3 base units (codon).

FIG. 6 shows DNA in the embodiment of the present invention.
It is a figure explaining the 1st translation method which translates a base sequence into an amino acid sequence. In the first translation method, a codon (3 bases) was cut out from the 5'end of the DNA base sequence, and
According to FIG. 5, it is translated into an amino acid, then the codon is excised by shifting one base and translated into an amino acid according to FIG. Similarly, the translation is continued by shifting one base at a time until the last base of the excised codon coincides with the last base at the 3'end of the DNA base sequence, and the DNA base sequence is translated into an amino acid sequence. , The translated amino acid sequence A ₁ or B ₁
To get Similarly, the complementary chain sequence of the DNA base sequence is translated into an amino acid sequence according to FIG. 5 to obtain a translated amino acid sequence A ₂ or B ₂ . As a result, a total of two types of translated amino acid sequences (A ₁ , A ₂ ; or B ₁ , B ₂ ) can be obtained using the first translation method.

In the example shown in FIG. 6, ATGCC, ..., CGAT is selected as an example of the DNA base sequence, and the codon ATG is cut out from the 5 ′ end and translated into amino acid M according to FIG. TGC is excised and translated into amino acid C according to FIG. 5, and similarly, codons GCC, ..., CGA, GAT are excised by shifting by one base, and translated into amino acids A, ..., R, D. The resulting translated amino acid sequence is MCA, ..., RD. As shown in FIG. 6, the complementary strand sequence A of the DNA base sequence
Similarly, TCG, ..., GGCAT are translated into amino acid sequences according to FIG.
S, ..., GAH is obtained.

FIG. 7 shows DNA in the embodiment of the present invention.
It is a figure explaining the 2nd, 3rd translation method which translates a base sequence into an amino acid sequence.

In the second translation method, 4 bases are cut out from the 5'end of the DNA base sequence, the second base is regarded as an insertion, and the remaining 3 bases (first corrected DNA base sequence).
Is used to translate into amino acids according to FIG. Then 1
The same translation is carried out by shifting the bases in accordance with FIG. 5, and the translation is repeated until the final 4 bases cut out correspond to the final 3'-terminal base of the DNA base sequence.
The base sequence is translated into an amino acid sequence to obtain the translated amino acid sequence A ₃ or B ₃ .

In the third translation method, 4 bases are cut out from the 5'end of the DNA base sequence, the 3rd base is considered to be inserted, and the remaining 3 bases (the second corrected DNA base sequence).
Is used to translate into amino acids according to FIG. Then 1
The same translation is carried out by shifting the bases in accordance with FIG. 5, and the translation is repeated until the final 4 bases cut out correspond to the final 3'-terminal base of the DNA base sequence.
The base sequence is translated into an amino acid sequence to obtain the translated amino acid sequence A ₄ or B ₄ .

Similarly, by applying the second and third translation methods to the complementary strand sequence of the DNA base sequence, the translated amino acid sequence A ₅ or B ₅ (not shown) and A ₆ or B ₆ are obtained. obtain. As a result, a total of 4 kinds of translated amino acid sequences (A ₃ , A ₅ ; or B ₃ , B ₅ ) were obtained using the second translation method, and a total of 4 kinds of translated amino acid sequences were obtained using the third translation method. The translated amino acid sequence of (A ₄ , A ₆ ; or B ₄ , B ₆ ) is obtained.

In the example of FIG. 7, the DNA base sequence is ATGC.
Since C, ..., CGAT, when translating into an amino acid sequence according to the second and third translation methods, first, 4 bases of ATGC were cut out from the 5 ′ end and the second base T was regarded as an insertion. (First corrected DNA base sequence), and 3
ATC that considers insertion of the second base G (second corrected DN
A base sequence) is translated into amino acids S and I respectively according to FIG. Next, the TCC (first corrected DNA base sequence) and TGC (second corrected DNA base sequence) obtained from the four bases of TGCC shifted by 1 base were replaced with the amino acid S according to FIG.
Translate to C. In the same manner, the translation is continued while shifting the bases one by one to obtain a translated amino acid sequence from the DNA base sequence. The resulting translated amino acid sequence is S
S, ..., H, and translated amino acid sequences are IC, ..., R
Is. Furthermore, the complementary strand AT of the DNA base sequence shown in FIG.
Similarly, CG, ..., GGCAT are translated into amino acid sequences according to the second and third translation methods to obtain a translated amino acid sequence not shown in FIG.

The calculation of the total score by the dynamic programming for calculating the total similarity between the translated amino acid sequences will be described in detail below (step 307).

In the present invention, Smith-W shown in FIG.
The score matrix for comparing DNA base sequences based on the aterman method is modified to construct a score matrix for comparing amino acid sequences, and using the score table defined for the pair of amino acids shown in FIG. The similarity of amino acid pairs between the two translated amino acid sequences to be compared is determined and the total similarity is evaluated.
The translated amino acid sequences A ₁ , A ₂ obtained in (step 304),
Use _{A 3, A 4, A 5} , A 6, and translated amino acid sequence B ₁ obtained in (step _{306), B 2, B 3} , B 4, B 5, B 6,
The total similarity between translated amino acid sequences is calculated by dynamic programming.

The first translated amino acid sequence (A ₁ or A ₂ ) along the first axis (eg, the x-axis) and the second translated amino acid sequence along the second axis (eg, the y-axis). The sequence (B ₁ or B ₂ ) is arranged from the 5 ′ end of each base sequence of the first and second translated amino acid sequences, and the value H (i, j) of the matrix element (i, j) is , A score matrix H representing the total degree of similarity between the amino acid sequence up to the i-th amino acid of the first translated amino acid sequence and the amino acid sequence up to the j-th amino acid of the second translated amino acid sequence. . Along the first axis, the first, third, fifth, seventh, or ninth translated amino acid sequence (A ₁ ,, A ₂ ,
A _3, A _4, A _5, one) of A _6, second along a second axis, the fourth, sixth, eighth, or tenth translated amino acid sequence (B _1, B _2, B _3, B _4, the B _5, any one of B _6), are arranged from the 5 'end of each of the base sequence of the translated amino acid sequence,
First, second, which represents the score (similarity) of a pair of amino acids
Third, fourth and fifth matrices (s ₁ (i, j) to s ₅
(I, j)). Translated amino acid sequence A ₁ , A ₂ ,
A ₃ , A ₄ , A ₅ , A ₆ and translated amino acid sequences B ₁ , B ₂ , B
_A first to a fourth matrix group consisting of five matrices is formed by the combination with ₃ , B ₄ , B ₅ , and B ₆ . The translated amino acid sequences arranged along the first and second axes in each of the five matrices are A _i and B _j, and for the sake of simplicity, the sequences (A _i , B _j ) are used in each matrix. 3 represents the translated amino acid sequence arranged along the first and second axes.

The first matrix group has the first, third, and fifth translated amino acid sequences as A ₁ , the seventh translated amino acid sequence as A ₃ , the ninth translated amino acid sequence as A _4, and the second ,
Score matrix H having the sequences (A ₁ , B ₁ ) where the eighth and tenth translated amino acid sequences are B ₁ , the fourth translated amino acid sequence is B ₃ , and the sixth translated amino acid sequence is B _4. If the sequence (a _1, B ₁₎ and the first matrix s ₁ with SEQ (a _1, B ₃₎ a second matrix with s ₂
And a third matrix s with array (A ₁ , B ₄ ).
₃ and a fourth matrix s with array (A ₃ , B ₁ )
₄ and a fifth matrix s ₅ having an array (A ₄ , B ₁ ).

In the second matrix group, the first, third, and fifth translated amino acid sequences are A ₁ , the seventh translated amino acid sequence is A ₃ , and the ninth translated amino acid sequence is A ₄ , ,
Score matrix H having the sequences (A ₁ , B ₂ ) with the 8th and 10th translated amino acid sequences as B ₂ , the 4th translated amino acid sequence as B ₅ , and the 6th translated amino acid sequence as B _6. If the sequence (a _1, B ₂₎ and the first matrix s ₁ with SEQ (a _1, B ₅₎ a second matrix with s ₂
And a third matrix s with array (A ₁ , B ₆ ).
₃ and a fourth matrix s with arrays (A ₃ , B ₂ ).
₄ and a fifth matrix s ₅ having an array (A ₄ , B ₂ ).

In the third matrix group, the first, third, and fifth translated amino acid sequences are A ₂ , the seventh translated amino acid sequence is A ₅ , and the ninth translated amino acid sequence is A ₆ . ,
Score matrix H having the sequences (A ₂ , B ₁ ) with the 8th and 10th translated amino acid sequences as B ₁ , the 4th translated amino acid sequence as B ₃ , and the 6th translated amino acid sequence as B _4. having the sequence and (a _2, B ₁₎ a first scoring matrix s ₁ with, sequence (a _2, B ₃₎ second scoring matrix s ₂ with the sequence of (a _2, B ₄₎ a third score matrix s ₃ of sequence (a _5, B ₁₎ fourth score matrix s ₄ of having, consists fifth score matrix s ₅ Metropolitan of having sequence (a _6, B _1).

The fourth matrix group has the first, third, and fifth translated amino acid sequences as A ₂ , the seventh translated amino acid sequence as A ₅ , the ninth translated amino acid sequence as A _6, and the second ,
Score matrix H having the sequences (A ₂ , B ₂ ) with the 8th and 10th translated amino acid sequences as B ₂ , the 4th translated amino acid sequence as B ₅ , and the 6th translated amino acid sequence as B _6. If the sequence (a _2, B ₂₎ and the first matrix s ₁ with SEQ (a _2, B ₅₎ a second matrix with s ₂
And a third matrix s with array (A ₂ , B ₆ ).
₃ and a fourth matrix s with arrays (A ₅ , B ₂ )
₄ and a fifth matrix s ₅ having an array (A ₆ , B ₂ ).

FIG. 8 is a diagram for explaining a score addition route when comparing translated amino acid sequences in the example of the present invention.

The first to fourth matrix groups are independently used, and dynamic matrix programming is performed for each matrix group to reach the score matrix element (i, j) in the nine directions of the paths ~ shown in FIG. , I is 1, 2, → M (the number of amino acids constituting the amino acid sequence arranged on the first axis of the scorematrix), and j is 1,
2, → N (the number of amino acids constituting the amino acid sequence arranged on the second axis of the scorematrix), and FIG.
By moving the position (i, j) from the score matrix element (1, 1) at the upper left end to the score matrix element (M, N) at the lower right end as shown in FIG. An optimum path (optimal alignment, optimum juxtaposition) that represents the optimum similarity correspondence between each amino acid of the second amino acid sequence is obtained.

The value H of the score matrix element (i, j)
(I, j) is the amino acid sequence up to the i-th amino acid of the first translated amino acid sequence and j of the second translated amino acid sequence.
The total similarity (score) with the amino acid sequence up to the th amino acid is shown.

Corresponding to the movement routes (from) in the 9 directions from the points (1) to (11) shown in FIG. 8 toward the point (i, j), the total similarity H (i, j) is calculated. As j), the maximum value ((Equation 16)) of H ₁ (i, j) to H ₁₁ (i, j) is selected. The score table shown in FIG. 4 is used to obtain s ₅ (i, j) from the scores s ₁ (i, j). H ₁ (i, j) to H ₁₁ (i, j)
Is a score s ₁ (i, j) to a score s representing the similarity between the i-th amino acid of the amino acid sequence arranged on the first axis and the j-th amino acid of the amino acid sequence arranged on the second axis. ₅ (i, j) and Gipp penalty scores w _a , w _n
And and the value H of the score matrix element of the movement source
(I-3, j-3), H (i-3, j), H (i, j-
3), H (i-5, j-6), H (i-6, j-5),
H (i-3, j-4), H (i-4, j-3), H (i
-6, j-7), H (i-7, j-6),
Each is defined by (Equation 5) to (Equation 15).

9 and 10, H ₈ (i, j),
And H ₉ (i, j) shows the positional relationship between (i-6, j-7) and (i, j) in the first term. 11 and 12 show H
₁₀ (i, j), and (i− of the first term of H ₁₁ (i, j).
7, j-6) and (i, j). The points (i-3, j-4) in FIGS. 9 and 10 are points for which the score s ₄ is obtained, and the points (i-4, j) in FIGS. 11 and 12 are.
-3) indicates a point for obtaining the score s ₅ .

H ₁ (i, j) = H (i-3, j-3) + s ₁ (i, j) = H (i-3, j-3) + s ^* ₁ (A ^* _i , B ^* _j ) (Equation 5) H ₁ (i, j) is converted from the point (i-3, j-3) to the point (i,
Corresponds to the travel route to j).

[0077] _{H 2 (i, j) =} H (i, j-3) + w a ... ( number _{6) H 2 (i, j} ) is a point from the point (i, j-3) ( i, j)
Corresponds to the travel route to.

[0078] _{H 3 (i, j) =} H (i-3, j) + w a ... ( number _{7) H 3 (i, j} ) is, point (i-3, j) from the point (i, j)
Corresponds to the travel route to.

H ₄ (i, j) = H (i-5, j-6) + w _n + s ₁ (i, j) = H (i-5, j-6) + w _n + s ₁ ^* (A ^* _i , B ^* _j ) (Equation 8) H ₄ (i, j) is calculated from the point (i-5, j-6) to the point (i,
Corresponds to the travel route to j).

H ₅ (i, j) = H (i-6, j-5) + w _n + s ₁ (i, j) = H (i-6, j-5) + w _n + s ₁ ^* (A ^* _i , B ^* _j ) (Equation 9) H ₅ (i, j) is calculated from the point (i-6, j-5) to the point (i,
Corresponds to the travel route to j).

H ₆ (i, j) = H (i-3, j-4) + w _n + s ₁ (i, j) = H (i-3, j-4) + w _n + s ₁ ^* (A ^* _i , B ^* _j ) ... (Equation 10) H ₆ (i, j) is from point (i-3, j-4) to point (i, j
Corresponds to the travel route to j).

H ₇ (i, j) = H (i-4, j-3) + w _n + s ₁ (i, j) = H (i-4, j-3) + w _n + s ₁ ^* (A ^* _i , B ^* _j ) ... (Equation 11) H ₇ (i, j) is from point (i-4, j-3) to point (i,
Corresponds to the travel route to j).

H ₈ (i, j) = H (i-6, j-7) + w _n + s ₂ (i-3, j-4) + s ₁ (i, j) = H (i-6, j- _{7) + w n + s 2} * (A * i-3, {b j-4 b j-3 b j-1}) + s 1 * (A * i, B * j) ... ( number 12) H ₉ (i , j) = H (i- 6, j-7) + w n + s 3 (i-3, j-4) + s 1 (i, j) = H (i-6, j-7) + w n + s 3 * _{^{(A * i-3, {}} b j-4 b j-2 b j-1}) + s 1 * (A * i, B * j) ... ( number _{13) H 8 (i, j} ), H 9 ( i, j) is the point (i-6, j-
7) Includes a travel route from point to point (i, j).

H ₁₀ (i, j) = H (i-7, j-6) + w _n + s ₄ (i-4, j-3) + s ₁ (i, j) = H (i-7, j- 6) + w _n + s ₄ ^* ({a _i-4 a _i-3 a _i-1 }, B ^* _j-3 ) + s ₁ ^* (A ^* _i , B ^* _j ) ... (Equation 14) H ₁₁ (i , j) = H (i- 7, j-6) + w n + s 5 (i-4, j-3) + s 1 (i, j) = H (i-7, j-6) + w n + s 5 * ({A _i-4 a _i-2 a _i-1 }, B ^* _j-3 ) + s ₁ ^* (A ^* _i , B ^* _j ) (Equation 15) H ₁₀ (i, j), H ₁₁ ( i, j) is the point (i-7, j-
6) Includes a travel path from point (i, j).

H (i, j) = max {H ₁ (i, j), H ₂ (i, j), H ₃ (i, j), H ₄ (i, j), H ₅ (i, j) ), H ₆ (i, j), H ₇ (i, j), H ₈ (i, j), H ₉ (i, j), H ₁₀ (i, j), H ₁₁ (i, j)}. (Equation 16) s ₁ (i, j) = s ₁ ^* (A ^* _i , B ^* _j ) ... (Equation 17) s ₂ (i-3, j-4) = s ^* (A ^* _i-3) , {B _j-4 b _j-3 b _j-1 }) (Equation 18) s ₃ (i-3, j-4) = s ^* (A ^* _i-3 , {b _j-4 b _{j- 2} b _j-1 }) (Equation 19) s ₄ (i-4, j-3) = s ^* ({a _i-4 a _i-3 a _i-1 }, B ^* _j-3 ) ... ( (Equation 20) s ₅ (i-4, j-3) = s ^* ({a _i-4 a _i-2 a _i-1 }, B ^* _j-3 ) ... (Equation 21) Note that A ^* _i is , The first translated amino acid sequence (Query
DNA base sequence (A ^* ))
Is the i-th codon (3 bases). B ^* _j is the second translated amino acid sequence (Target DNA bases).
sequence (denoted as B ^* )) j-th codon (3
Base). a _i is the i-th base of A ^* , b _j is _j of B ^*
It is the second base. Since the right side of (Equation 17) to (Equation 21) shows the score between codons, each codon can be translated into an amino acid according to FIG. 5, and can be determined using the score table of FIG.

As described above, the first to fourth matrix groups are independently used, and each matrix group is subjected to the dynamic programming for each amino acid of the first translated amino acid sequence and the second amino acid sequence. The optimal path (optimal alignment, optimal juxtaposition) that represents the optimal similarity correspondence between

In addition, w _a represents an amino acid, and w _n represents a gap penalty associated with insertion or deletion of a base of a DNA base sequence. In this embodiment, w _a = w _n = −12. Also,
1 if amino acid insertions and deletions appear consecutively
In the second appearance, w _a = -12, and in the second and subsequent appearances, w _a = -4.

Next, regarding the score total and the route by the dynamic programming for obtaining the juxtaposed result (step 312), and about the route tracing the route giving the maximum score total (step 313) The details will be described.

In (step 312), the same operation as in (step 307) is performed on the two amino acid sequences which give the total of the upper scores, which are obtained from the searched DNA base sequence and the DNA base sequence of the DNA base sequence database. Calculate the total score by dynamic programming. However, similarity (score)
In addition to the total of, for each element of the score matrix,
The information indicating which of the calculation paths represented by (Equation 5) to (Equation 16) has been selected, and the movement path that gives the maximum total value of the similarity (score) are the positions (i) of the final points of the elements of the score matrix. , J).

At (step 313), each element is stored from the position (i, j) of the final point of the element of the score matrix that gives the maximum value of the total similarity stored at (step 312). The existing calculation paths can be traced in reverse to obtain the alignment result between the translated amino acid sequences that gives the maximum total similarity (score).

FIG. 13 is a diagram showing a general example of the juxtaposition result corresponding to each moving path in nine kinds of directions in the calculation of the dynamic programming in the embodiment of the present invention.

FIG. 14 is a diagram showing a specific example of the juxtaposition result corresponding to each moving path in nine kinds of directions in the calculation of the dynamic programming in the embodiment of the present invention.

The first of the juxtaposed examples shown in FIGS. 13 and 14.
The line is the first DNA base sequence, the second line is the translated amino acid translated from the first DNA base sequence, and the third line is the second DN.
Translated amino acid translated from nucleotide sequence A, line 4 is the second
Represents the DNA base sequence of The symbol "-" represents a deletion of the sequence or amino acid sequence, and the symbol "*" represents
It represents a non-translatable amino acid due to a base deletion or the presence of an indeterminate n which has not been determined to be any of a, c, g and t.

Next, an actual application example of this embodiment will be described. Ge, a public database of DNA nucleotide sequences
Arabidopsis thalia, registered in the nBank EST database.
search sequence concerning "na" (Query sequence)
, and all the sequences derived from rice (oriza sativa) registered in the EST database are targeted for comparison search (Target sequence).
And Since the DNA base sequence registered in the EST database has registered the output result of the DNA sequencer as it is, it contains a certain amount of sequence error, and insertion of bases existing in two DNA base sequences to be compared, and This is a preferable example for confirming the effectiveness of the present invention in which the comparison is carried out by interposing an amino acid sequence in consideration of the deletion.

FIG. 15, FIG. 16 and FIG. 17 are diagrams showing examples of juxtaposition results obtained by the comparison search of the embodiment of the present invention. The results of the comparative search will be described below. Figure 1
5, FIG. 16 and FIG. 17, the query sequence
In the “nce” column, the name given to the searched DNA base sequence and a brief description are described.
In the column of “uence”, the EST extracted by the comparative search
The name given to the DNA base sequence from the database,
And a brief description is given. In the Score column, the total degree of similarity (score) is described.
ery and Target length, Quer juxtaposed
The y and Target regions are listed.

In the “Query” column showing the parallel value result, the search DNA base sequence (Query sequence) is displayed from the top.
)) and the translated amino acid sequence translated from the searched DNA base sequence are described, and the target value is displayed.
In the column of sequence, the DNA base sequence extracted by the comparative search from the bottom and the translated amino acid sequence translated from this DNA base sequence are described.

Query showing the parallel value result shown in FIG.
The DNA base sequence and the translated amino acid sequence in the column of are shown by SEQ ID NOS: 1 and 2, respectively, and show the results of average value.
The translated amino acid sequence and DNA base sequence in the column of t are shown by SEQ ID NOs: 3 and 4, respectively. The DNA base sequence and the translated amino acid sequence in the column of Query showing the parallel value result shown in FIG. 16 are shown by SEQ ID NOs: 5 and 6, respectively, and the translated amino acid sequence and the DNA base sequence in the column of Target showing the parallel value result are These are shown by SEQ ID NOS: 7 and 8, respectively. FIG. 17
The DNA base sequence and translated amino acid sequence in the Query column showing the parallel value result shown in are shown by SEQ ID NOs: 9 and 10, respectively, and the translated amino acid sequence and the DNA base sequence in the Target column showing the parallel value result are Number 11, 12
Indicated by.

Incidentally, in FIG. 15, FIG. 16 and FIG.
The symbol ":" connecting the translated amino acid sequences in the upper and lower rows indicates that the corresponding translated amino acids match, and the symbol "."
Indicates that the value of the score matrix corresponding to the pair between the corresponding amino acids is positive. The symbol "" (blank) indicates that the value of the score matrix corresponding to the pair between the corresponding amino acids is 0 or negative. The symbol "-" indicates a base or amino acid sequence deletion. The symbol “n” indicates that none of a, c, g, and t has been determined and is indefinite. The symbol "*" represents an amino acid that cannot be translated due to a deletion of a base or the presence of an indeterminate n.

The areas b, b ', indicated by the squares shown in FIG.
The following describes c, d, and e. Regions b and b ′ are amino acid insertions or deletions, that is, (Equation 6) or (Equation 7).
It is shown that the result corresponding to is included in the optimal route. Area c
Indicates that it contains a base deletion, that is, (Equation 8) or (Equation 9). Regions d and e correspond to the insertion of bases, and the region d
Indicates that the optimum route includes the result corresponding to (Equation 10) or (Equation 11), and the region e is (Equation 12) to (Equation 1).
It is shown that the result corresponding to any one of 5) is included in the optimum route.

Only the portion surrounded by a square shown in FIGS. 16 and 17 is a region obtained by applying the TBLASTX of the prior art. In the method of the present invention, prior art TBLAST
For regions that cannot be obtained by applying X, information on the similarity relationship between the two base sequences is obtained via the translated amino acid sequence. In particular, when the example result shown in FIG. 16 is compared with the result obtained by TBLASTX of the prior art, the result of the present invention provides information regarding the similarity relationship in a continuous wider region. In particular, in the example shown in FIG. 17, the method of the present invention provides information about the similarity relation in a region that is three times longer than the method of the prior art TBLASTX.

In the present invention, amino acid insertions, deletions, DNs
Since all the insertions and deletions of the bases of the A base sequence are taken into consideration, it is possible to compare and search over a wide base sequence region with a high degree of similarity (the total score is large), and the base sequence is wide. The juxtaposition result in the area can be obtained. As a result, it becomes possible to obtain a more complete sequence regarding the amino acid sequence encoded by the DNA base sequence. Knowing the amino acid sequence of a protein encoded by a DNA base sequence is the first step in proceeding with the analysis of the biological function of a gene. Currently, the number of data available in the amino acid sequence database is much smaller than that in the DNA base sequence database, and the DN obtained as a result of the measurement is
Knowing the information on the amino acid sequence from the A base sequence by interposing the amino acid sequence by the method of the present invention provides information useful for analysis of protein function.

FIG. 18 is a diagram showing the construction of an apparatus for carrying out the DNA base sequence comparison method of the present invention. D of the present invention
The apparatus for executing the NA nucleotide sequence comparison method is the first
And a device 401 for inputting the second DNA base sequence, and
A translation program for translating an A base sequence into an amino acid sequence, a sequence comparison program for the above-mentioned first and second translated amino acid sequences, juxtaposition of the first and second translated amino acid sequences, and first and second translated amino acids An arithmetic processing unit 402 having a built-in program for executing a juxtaposition of DNA base sequences corresponding to the respective sequences, a maximum value of the total degree of similarity and juxtaposition results of the first and second translated amino acid sequences, and first and second An output device 403 that outputs the juxtaposed result of the DNA base sequences corresponding to the translated amino acid sequences, and an external storage device 404 that stores and stores various DNA base sequence databases, various amino acid sequence databases, score tables, codon tables, and the like. Is included.

The outline of the present invention will be summarized below. The present invention divides the (A) (1) first and second DNA base sequences into base groups each having a length of 3 bases, and translates each base group into an amino acid to produce the first and second base groups. Determining the amino acid sequence, (2) insertion and deletion of bases in the first and second DNA base sequences, and insertion of amino acids in the first and second translated amino acid sequences, and Considering each deletion, the similarity obtained as a result of comparing the sequences of the respective amino acids in the first translated amino acid sequence and the second translated amino acid sequence is totaled so that the total similarity is maximized. A step of obtaining a correspondence relationship between each amino acid of the first and second translated amino acid sequences, (3) a maximum value of the total similarity, and a juxtaposition of the first and second translated amino acid sequences, The alignment between the first translated amino acid sequence and the first DNA base sequence and the second translated nucleotide sequence And a step of outputting the juxtaposition between acid sequence and the second DNA sequence, step (1) is
Translating the first and second DNA base sequences into amino acid sequences by shifting each one base by 3 bases from the (I) end, and sequentially translating each one base by 4 bases from the (II) end. Shifting, translating the remaining 3 bases of 4 bases excluding the 2nd base of 4 bases into an amino acid sequence, (III) sequentially shifting by 1 base in units of 4 bases Translating the remaining 3 bases out of the 4 bases excluding the 3 rd base into an amino acid sequence, and comparing the degree of similarity between the first and second DNA base sequences. There are features.

In (A), an integer satisfying k ≧ 1 and m ≧ 1 and an integer satisfying n ≧ 2, i ≦ M (M is the number of amino acids in the first translated amino acid sequence), j ≦ N (N
Is the number of amino acids in the second translated amino acid sequence), in step (2), each amino acid of the first translated amino acid sequence is sequentially arranged in the direction of the first axis, To form a matrix obtained by sequentially arranging the amino acids of the translated amino acid sequence in the direction of the second axis, and the i-th amino acid of the first translated amino acid sequence and the j-th amino acid of the second translated amino acid sequence. When calculating the total similarity in the elements (i, j) of the matrix, which represent the position of the pair with and, the elements of the matrix (i-3, j- 3), (i, j-3k),
(I-3k, j), (i-3n + 1, j-3n), (i
-3n, j-3n + 1), (i-3m, j-3m-
It is characterized in that any one of the seven routes 1) and (i-3m-1, j-3m) is selected so that the total sum of the similarities is maximized.

In addition, the present invention (B) (1) divides the first and second DNA base sequences into base groups each having a length of 3 bases, translates each base group into amino acids, And (2) the insertion and deletion of bases in the first and second DNA base sequences, and the first and second translated amino acid sequences. Taking into account insertion and deletion of amino acids, the similarity obtained as a result of comparing the sequences of the respective amino acids in the first translated amino acid sequence and the second translated amino acid sequence is totaled, and the total similarity is calculated. And (3) determining the correspondence between the amino acids of the first and second translated amino acid sequences that maximizes
Maximum total similarity, alignment of first and second translated amino acid sequences, first translated amino acid sequence, and first DNA
The alignment between the base sequence and the second translated amino acid sequence, and the step of outputting the alignment, and the degree of similarity between the first and second DNA base sequences. Is characterized by a DNA base sequence comparison method for comparing

Further, in (A) and (B), the first
Replacing the second DNA base sequence with the second DNA base sequence by replacing the second DNA base sequence with the complementary strand base sequence of the first DNA base sequence.
It is characterized in that it has a step of performing steps (1), (2) and (3) by substituting the base sequence of the complementary chain of the NA base sequence.

[0107]

EFFECTS OF THE INVENTION According to the present invention, since it is possible to compare the degree of similarity between DNA base sequences mediated by translated amino acid sequences, the score table used for comparing the degrees of similarity can be
In addition to conformity and disagreement of amino acids, by reflecting chemical properties such as hydrophilicity or hydrophobicity of amino acids and physical properties such as size of amino acids, it becomes possible to make a finer comparison and The sensitivity of similarity search between base sequences is improved.

In addition, insertion, deletion of bases existing in the DNA base sequence, and insertion of amino acids in the translated amino acid sequence,
Since the comparison considering the deletion can be realized, the search omission can be reduced.

[0109]

[Sequence list]

Sequence listing SEQ ID NO: 1 Sequence length: 254 Sequence type: Nucleic acid Number of chains: both forms Topology: linear Sequence type: cDNA to mRNA origin Species: Arabidopsis thaliana Sequence features Characteristic symbol: mRNA How the feature was determined: E Array TTCATTCATC CGTNGTTCCC CAGCTCCAAT CAGTCTCCGT TCCCTTCCAT CAGCCAACAC 60 ACAATCCCTC TTCGGTCTCA AATCAGGCAC CGCTCGTGGT GGACGTGTCA CAGCCATGGC 120 TACATACAAG GTCAAGTTCA TCACACCAGA AGGTGAGCTA GAGGTTGAGT GTGACGNCGN 180 CGTCTACGTT CTTNATGCTG CTGAGGAAGC TGGAATCGAT TTTGCCTTAC TCTTGCCGTG 240 CTGGTTCTTG TTCG 254 SEQ ID NO: 2 Sequence length: 84 Sequence type: Amino acid Topology: unknown Sequence type: Protein Hypothetical array: Yes Array Phe Ile His Pro Xaa Phe Pro Ser Ser Asn Arg Leu Arg Ser Leu Pro 16 Ser Ala Asn Thr Gln Ser Leu Phe Gly Leu Lys Ser Gly Thr Ala Arg 32 Gly Gly Arg Val Thr Ala Met Ala Thr Tyr Lys Val Lys Phe Ile Thr 48 Pro Glu Gly Glu Leu Glu Val Glu Cys Asp Xaa Xaa Val Tyr Val Leu 64 Xaa Ala Ala Glu Glu Ala Gly Ile Ile Leu Pro Tyr Ser Cys Arg Ala 80 Gly Ser Cys Ser 84 SEQ ID NO: 3 Sequence length: 87 Sequence type: Amino acid Topology: unknown Sequence type: Protein Hypothetical array: Yes Array Phe Leu Asn Pro Ala Arg Pro Leu Leu Arg Arg Pro Arg Ala Leu Pro 16 Ser Leu Val Thr Gln Ser Lys His Xaa Asn Met Ser Gly Leu Arg Ile 32 Ser Asn Lys Phe Arg Val Ser Ala Thr Gly Xaa His Lys Val Lys Leu 48 Ile Gly Pro Asp Gly Val Glu His Glu Phe Glu Ala Pro Glu Asp Thr 64 Tyr Ile Leu Glu Ala Ala Glu Thr Ala Gly Val Xaa Leu Pro Xaa Xaa 80 Cys Arg Ala Gly Ser Cys Ser 87 SEQ ID NO: 4 Sequence length: 260 Sequence type: Nucleic acid Number of chains: both forms Topology: linear Sequence type: cDNA to mRNA origin Species: Oriza sativa Sequence features Characteristic symbol: mRNA How the feature was determined: E Array TTCCTAAACC CGGCGCGGCC ATTGCTCCGG CGACCAAGAG CCCTTCCTTC ATTGGTTACG 60 CAAAGCAAAC ATTGAACATG TCAGGCCTAA GGATCTCCAA CAAGTTCAGG GTGTCCGCGA 120 CAGGTNGTCA CAAGGTAAAG CTTATAGGCC CGGACGGTGT CGAGCACGAG TTTGAAGCCC 180 CTGAAGATAC CTACATTCTC GAGGCCGCTG AAACTGCCGG GGTGGNGCTG CCATTNTNAT 240 GCCGTGCTGG ATCATGCTCC 260 SEQ ID NO: 5 Sequence length: 258 Sequence type: Nucleic acid Number of chains: both forms Topology: linear Sequence type: cDNA to mRNA origin Species: Arabidopsis thaliana Sequence features Characteristic symbol: mRNA How the feature was determined: E Array ATGGCGAATT CCGGCGAAGA GAAGTTGAAG CTCTACTCTT ACTGGAGAAG CTCGTGTGCT 60 CATCGTGTCC GTATCGCCCT CGCTTTGAAA GGGCTTGATT ATNAGTATAT ACCAGTGAAT 120 TTNCTCAAGG GTGATCAATT CGATTCANAT TTCAAGAAGA TCAATCCAAT GGGAACTGTA 180 CCAGCTCTGG TGGATGGAGA TGTTGTGATT AATGATTCTT TTGCGATAAT AATGTATCTG 240 GATGAGAAGT ACCCTGAG 258 SEQ ID NO: 6 Sequence length: 86 Sequence type: Amino acid Topology: unknown Sequence type: Protein Hypothetical array: Yes Array Met Ala Asn Ser Gly Glu Glu Lys Leu Lys Leu Tyr Ser Tyr Trp Arg 16 Ser Ser Cys Ala His Arg Val Arg Ile Ala Leu Ala Leu Lys Gly Leu 32 Asp Tyr Xaa Tyr Ile Pro Val Asn Xaa Leu Lys Gly Asp Gln Phe Asp 48 Ser Xaa Phe Lys Lys Ile Asn Pro Met Gly Thr Val Pro Ala Leu Val 64 Asp Gly Asp Val Val Ile Asn Asp Ser Phe Ala Ile Ile Met Tyr Leu 80 Asp Glu Lys Tyr Pro Glu 86 SEQ ID NO: 7 Sequence length: 83 Sequence type: Amino acid Topology: unknown Sequence type: Protein Hypothetical array: Yes Array Met Ala Gly Ser Gly Asp Glu Leu Met Leu Leu Gly Lys Trp Pro Ser 16 Pro Phe Val Thr Arg Val Glu Leu Ala Leu Gly Leu Lys Gly Leu Ser 32 Tyr Glu Tyr Val Lys Gln Asp Leu Val Asn Lys Ser Glu Leu Leu Leu 48 Ala Ser Asn Pro Val His Lys Lys Ile Pro Val Leu Ile His Asn Gly 64 Lys Pro Val Cys Glu Ser Ser Ile Ile Val Gln Tyr Ile Asp Glu Ala 80 Phe Pro Asp 83 SEQ ID NO: 8 Sequence length: 249 Sequence type: Nucleic acid Number of chains: both forms Topology: linear Sequence type: cDNA to mRNA origin Species: Oriza sativa Sequence features Characteristic symbol: mRNA How the characteristics were determined: E Array ATGGCCGGAT CAGGAGACGA GCTGATGCTG CTCGGCAAAT GGCCAAGCCC ATTCGTCACC 60 AGGGTTGAGC TCGCGCTCGG CCTCAAGGGC CTCAGCTACG AGTACGTCAA GCAGGACCTC 120 GTCAACAAGA GCGAGCTCCT CCTCGCCTCC AACCCGGTGC ACAAGAAGAT CCCCGTGCTC 180 ATCCACAACG GCAAGCCGGT CTGCGAGTCG TCAATCATCG TGCAGTACAT CGACGAGGCC 240 TTCCCCGAC 249 SEQ ID NO: 9 Sequence length: 186 Sequence type: Nucleic acid Number of chains: both forms Topology: linear Sequence type: cDNA to mRNA origin Species: Arabidopsis thaliana Sequence features Characteristic symbol: mRNA How the feature was determined: E Array GGAAGAGCTC CATGCTGCGA CAAGGCAAAC NTGAAGAAAG GACCATGGTC ACCGGAAGAN 60 GATGTGAAGC TCAAGGTTTA CATCGACAAA TATGGCACTG GTGGCAACTG GTTCGCACTG 120 CCTCAGAAAN TTGGNCTGAA GAGATGTGGT AAGANTTGCA GACTGAGATG GCTTAATTNC 180 TTAAGA 186 SEQ ID NO: 10 Sequence length: 62 Sequence type: Amino acid Topology: unknown Sequence type: Protein Hypothetical array: Yes Array Gly Arg Ala Pro Cys Cys Asp Lys Ala Asn Xaa Lys Lys Gly Pro Trp 16 Ser Pro Glu Xaa Asp Xaa Glu Ala Gln Gly Leu His Arg Gln Ile Trp 32 His Trp Trp Gln Leu Val Arg Leu Pro Gln Lys Xaa Xaa Leu Lys Arg 48 Cys Gly Lys Xaa Cys Arg Leu Arg Trp Leu Asn Xaa Leu Arg 62 SEQ ID NO: 11 Sequence length: 62 Sequence type: Amino acid Topology: unknown Sequence type: Protein Hypothetical array: Yes Array Gly Arg His Ser Cys Cys Tyr Lys Gln Lys Leu Arg Lys Gly Leu Trp 16 Ser Xaa Glu Glu Asp Glu Glu Ala His Gly Pro His Asn Gln Ala Trp 32 Xaa Trp Leu Leu Gly His Arg Phe Gln Asn Leu Gln Gly Phe Gln Arg 48 Cys Ala Lys Ala Phe Arg Leu Arg Trp Xaa Asn Tyr Leu Arg 62 SEQ ID NO: 12 Sequence length: 188 Sequence type: Nucleic acid Number of chains: both forms Topology: linear Sequence type: cDNA to mRNA origin Species: Oriza sativa Sequence features Characteristic symbol: mRNA How the feature was determined: E Array GGGAGACATT CCTGCTGCTA CAAGCAGAAG CTGAGGAAGG GGCTCTGGTC ANCTGAGGAG 60 GATGAGGAAG CTCATGGACC ACATAACCAA GCATGGNCAT GGCTGCTGGG GCACCGTTTC 120 CAAAACTTGC AGGGGTTTCA GAGATGTNGC AAAAGCTTTC AGGCTGAGGT TGGGTNAACT 180 ACTTGAGG 188

[Brief description of drawings]

FIG. 1 is a diagram for explaining six types of reading frames for a DNA base sequence when translating a DNA base sequence into an amino acid sequence in the prior art.

FIG. 2 is a diagram for explaining a score addition path when comparing DNA base sequences using the Smith-Waterman method of the prior art.

FIG. 3 is a flowchart illustrating an example of processing steps according to the embodiment of the present invention.

FIG. 4 is a diagram showing an example of a prior art table that defines the scores to be assigned to amino acid pairs, used in the examples of the present invention.

FIG. 5 is a diagram showing a codon table of the prior art which defines termination of translation into amino acids and types of amino acids corresponding to each of the three base units (codon units) of the codon table.

FIG. 6 is a diagram illustrating a first translation method for translating a DNA base sequence into an amino acid sequence in the example of the present invention.

FIG. 7 is a diagram illustrating second and third translation methods for translating a DNA base sequence into an amino acid sequence according to an example of the present invention.

FIG. 8 is a diagram illustrating a score addition route when comparing translated amino acid sequences in an example of the present invention.

FIG. 9 shows the score s ₂ (i− in the example of the present invention.
The figure which shows the point (i-3, j-4) which calculates | requires 3, j-4).

FIG. 10 shows the score s ₃ (i− in the example of the present invention.
The figure which shows the point (i-3, j-4) which calculates | requires 3, j-4).

FIG. 11 shows the score s ₄ (i− in the example of the present invention.
4, j-3) is a diagram showing points (i-4, j-3) to be obtained.

FIG. 12 shows the score s ₅ (i− in the example of the present invention.
4, j-3) is a diagram showing points (i-4, j-3) to be obtained.

FIG. 13 is a diagram showing a general example of juxtaposition results corresponding to movement paths in nine types of directions in the dynamic programming calculation in the embodiment of the present invention.

FIG. 14 is a diagram showing a specific example of juxtaposition results corresponding to movement paths in nine types of directions in the dynamic programming calculation according to the embodiment of the present invention.

FIG. 15 is a diagram showing an example of juxtaposition results obtained by a comparative search according to an example of the present invention.

FIG. 16 is a diagram showing an example of juxtaposed results obtained by a comparative search according to an example of the present invention.

FIG. 17 is a diagram showing an example of juxtaposition results obtained by a comparative search according to an example of the present invention.

FIG. 18 is a view showing a configuration of an apparatus for carrying out the DNA base sequence comparison method of the present invention.

[Explanation of symbols]

301 ... Inputting score table, 302 ... Inputting output number of search results, 303 ... Inputting search DNA base sequence, 304 ... Translating search DNA base sequence into amino acid sequence, 305 ... DNA base Step of reading sequence, 306 ... Translation of DNA base sequence into amino acid sequence, 307 ... Step of total score by dynamic programming, 308 ... Select DNA base sequence having upper total score up to output number of search results Step, 309 ... Sorting of total score, 310 ... Displaying DNA base sequence having upper score total, 311 ... Inputting output number of juxtaposition result, 312 ... Total score and path by dynamic programming , 313 ... Calculating the trace of the route that gives the maximum score total, 3
14 ... Process of displaying juxtaposition result, 401 ... Input device, 4
02 ... Arithmetic processing device, 403 ... Output device, 404 ... External storage device.

─────────────────────────────────────────────────── ─── Continuation of the front page (72) Inventor Naoko Kasahara 1-280, Higashi Koikekubo, Kokubunji, Tokyo Inside Central Research Laboratory, Hitachi, Ltd. (56) Reference JP 10-5000 (JP, A) JP 9 -105748 (JP, A) HEIN, J, An Algorithm Combining DNA and Protein Alignment, Journal of Theoretical Biology, AC ADEMIC PRESS, March 21, 1994, Vol. 167, no. 2, p. 169-174 HEIN, J et al. , Genomic Alignment, Journal of Molecular E evolution, Springer International, March 1994, Vol. 38, No. 3, p. 310-316 HOMPSON, J. D. GIBSO N, T. J. , PairWise and SearchWise: find the optimal alignment in a simultaneous companion of a protein. ． ． ． , Nucleic Acids Research, United Kingdom, Oxford University Press, 1996, Vol. 24, No. 14, p. 2730-2739 GUAN, X. UBERBACHE R, E. C. , Alignments of DNA and protein sequences contenting flameshift errors, Computer Applications in the Bio sciences, United Kingdom, OXFORD UNIVERSITY, 1996. 12, No. 1, p. 31-40 Hirofumi Uchimiya, Atsuyuki Kato, Large-scale analysis of rice cDNA, protein / nucleic acid / enzyme, Japan, Kyoritsu Shuppan Co., Ltd., May 10, 1992, Vol. 37, No. 7, p. 1364-1368 (58) Fields surveyed (Int.Cl. ⁷ , DB name) G06F 17/30 C12N 15/00 JISST file (JOIS)

Claims (6)

(57) [Claims] 1. A step of inputting a search DNA base sequence as a first base sequence, a step of inputting a DNA base sequence read from a DNA base sequence database as a second base sequence, said first base sequence And the second DNA base sequence is divided into 3 bases and translated into amino acids to obtain a first amino acid sequence and a second amino acid sequence, respectively, the first amino acid sequence and In the step of forming the second amino acid sequence, the first DNA base sequence and the second DNA base sequence are translated into amino acids while shifting the bases by 3 bases in units of 3 bases from the 5 ′ end. The bases are shifted by 1 base by 4 bases, and the 3 bases except the second base among the 4 bases are translated into amino acids. The 5'-end is shifted by 1 base by 4 bases unit by 1 base by 4 bases. The three bases except the Chino third base combined translation method to translate the amino acid, insertion of the base in the first DNA sequence and said second nucleotide sequence, deletion and the first amino acid sequence and By considering the insertion and deletion of amino acids in the second amino acid sequence and comparing the first amino acid sequence with the second amino acid sequence, the similarity is summed up, and the total similarity is calculated. Determining the correspondence that maximizes the maximum value, the maximum value of the similarity, the juxtaposition of the first amino acid sequence and the second amino acid sequence, the first DNA base sequence and the first amino acid Juxtaposition with an array, said second DN
A DNA base sequence comparison method comprising the step of outputting the A base sequence and the juxtaposition of the second amino acid sequence. 2. The DNA base sequence comparison method according to claim 1, wherein the total of the similarities is i ≦ M (M: the number of amino acids of the first amino acid sequence), j ≦ N (N: the second amino acid). The number of amino acids of 2 amino acids), the first amino acid sequence is arranged on the first axis, and the second amino acid sequence is arranged on the second axis to form a matrix,
Which is the sum of the similarities in the elements (i, j) of the matrix, which represent the paired positions of the i-th amino acid of the amino acid sequence of and the j-th amino acid of the second amino acid sequence, (I-3, j-3), which are elements of the matrix leading to element (i, j),
(I, j-3k), (i-3k, j), (i-3n +)
1, j-3n), (i-3n, j-3n + 1), (i-
3m, j-3m-1), (i-3m-1, j-3m)
From (k ≧ 1, m ≧ 1, n ≧ 2), a route is selected so that the sum of the similarities is maximized, and a correspondence relation is obtained so that the sum of the similarities is maximized. DNA
Nucleotide sequence comparison method. 3. The DNA base sequence comparison method according to claim 1, wherein the first DNA base sequence is replaced with the first DN.
A method for comparing DNA base sequences, further comprising a sequence which is a base sequence complementary to A base sequence and the second DNA base sequence is a base sequence complementary to the second DNA base sequence. 4. An input means for inputting a searched DNA base sequence as a first base sequence and a DNA base sequence read from a DNA base sequence database as a second base sequence, and the first DNA base sequence. And the second base sequence,
It is divided into 3 bases and translated into amino acids to obtain a first amino acid sequence and a second amino acid sequence, and the first D
Considering the insertion and deletion of bases in the NA base sequence and the second base sequence and the insertion and deletion of amino acids in the first amino acid sequence and the second amino acid sequence,
An arithmetic means for comparing the first amino acid sequence and the second amino acid sequence to total the degree of similarity to obtain a correspondence relationship that maximizes the total degree of similarity; And the second DNA base sequence from the 5'end in units of 3 bases.
Translation into amino acids while shifting bases 4 from the 5'end
The base unit is shifted by 1 base, and 2 of the 4 bases are shifted.
Th base obtained by removing 3 bases translated into amino acids, the 5 'end shifted by one nucleotide in units of 4 bases from the 3 base excluding the third base of said 4 bases translation program to translate the amino acid A combination of the maximum value of the similarity , the alignment of the first amino acid sequence and the second amino acid sequence, the alignment of the first DNA base sequence and the first amino acid sequence, the 2 DN
A DNA base sequence comparison device comprising: an output unit that outputs the A base sequence and the juxtaposition of the second amino acid sequence. 5. The DNA base sequence comparison method according to claim 4, wherein the arithmetic means has a sum of the degrees of similarity i ≦ M.
(M: number of amino acids in the first amino acid sequence), j ≦ N
(N: the number of amino acids of the second amino acid), the first amino acid sequence is aligned on the first axis, and the second amino acid sequence is aligned on the second axis to form a matrix. The sum of the similarities in the element (i, j) of the matrix, which represents the paired position of the i-th amino acid of the first amino acid sequence and the j-th amino acid of the second amino acid sequence. Is an element of the matrix up to an element (i, j) of the matrix, (i
-3, j-3), (i, j-3k), (i-3k,
j), (i-3n + 1, j-3n), (i-3n, j-
3n + 1), (i-3m, j-3m-1), (i-3m
-1, j-3m) (k ≧ 1, m ≧ 1, n ≧ 2), the route is selected so that the total sum of the similarities is maximized, and the correspondence relation is selected so that the total sum of the similarities is maximized. A base sequence comparison device comprising a program for obtaining 6. The DNA base sequence comparison apparatus according to claim 4, wherein the first DNA base sequence is replaced with the first DN.
A DNA which further comprises a sequence which is a complementary chain base sequence of the A base sequence and which is the second DNA base sequence is a complementary chain base sequence of the second DNA base sequence.
Base sequence comparison device.