Gene database retrieval system where a key sequence is compared to database sequences by a dynamic programming device

• US 5,706,498 A
• Filed: 09/26/1994
• Issued: 01/06/1998
• Est. Priority Date: 09/27/1993
• Status: Expired due to Term

• Current Assignee: Hitachi Device Engineering Co., Ltd., Hitachi Software Engineering Co., Ltd. (Hitachi, Ltd.)
• Original Assignee: Hitachi Device Engineering Co., Ltd., Hitachi Software Engineering Co., Ltd. (Hitachi, Ltd.)
• Inventors: Yamamoto, Shinichiro, Okayama, Toshitsugu, Maru, Norio, Nasu, Hisanori, Fujimiya, Hitoshi
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Choules, Jack M.
• Application Number:
  US08/312,689
• Time in Patent Office: 1,198 Days
• Field of Search: 395/600, 395/606, 395/800, 364/413.01, 364/413.1, 364/728.03, 364/728.05, 364/728.07, 435/6, 935/80, 935/77, 935/87
• US Class Current: 702/20
• CPC Class Codes: G16B 50/00 ICT programming tools or database systems specially adapted for bioinformatics
• CPC Class Codes: G16B 50/30 Data warehousing; Computing architectures
• CPC Class Codes: G16B 50/50 Compression of genetic data
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

The gene database retrieval system, for making a retrieval for a gene sequence having a sequence similar to a sequence data from a gene database, contains a gene database for storing the sequence data of genes whose structures or sequences have already been analyzed and identified, a dynamic programming operation unit for determining the degree of similarity between target data and key data by utilizing the sequence data of the bases of the gene from the gene database as the target data and the sequence data of the bases as the key for retrieval, and a central processing device unit for executing the access process to make access to the gene database, in parallel to the operation process for determining the degree of similarity by transmitting the sequence data of the bases from the gene database continually one after another into the dynamic programming operation unit as the target data, by controlling the gene database and the dynamic programming operation unit.

Claims

1. A gene database retrieval system comprising:

a gene database for storing a sequence data of at least either of sequences of bases of a nucleic acid or sequences of amino acids of a protein, each constituting a gene whose structure has been analyzed and identified;

a dynamic programming operation unit for determining a degree of similarity between a target data and a key data, said target data being constituted by a sequence data of bases from said gene database and said key data being constituted by a sequence data of bases functioning as a retrieval key; and

a central processing device unit for parallel-executing an access process of making access to said gene database and an operation process of determining the degree of similarity by entering a sequence data of bases one after another from said gene database as the target data by making controls over both of said gene database and said dynamic programming operation unit;

wherein said central processing device unit for controlling said dynamic programming operation unit comprises;

a first operation control means for executing an operation for determining the degree of similarity between the target data and the key data by altering the target data one after another with respect to the key data, acquiring the sum value of the sequence data of each target data occurring at the operation, and storing only the maximal sum values for the sequence data;

a second operation control means for classifying the maximal sum values of the sequence data of the target data determined by the first operation control means and determining the order of the sequence data as an object of extraction; and

a third operation control means for performing a re-operation for determining the degree of similarity between the target data and the key data by utilizing the sequence data for the object of extraction as a target data in accordance with the order of the sequence data functioning as the object of extraction, then performing an operation for storing the sum value of the sequence data of the target data occurring at the time of the operation, acquiring a direction selection data created during the operation, and determining the optimal disposition of the sequence data of the target data with respect to the key data.

2. The gene database retrieval system as claimed in claim 1, wherein said dynamic programming operation unit further comprises a rewritable score memory for storing a score value of the degree of similarity;

wherein said central processing device unit is arranged in order to execute a process for controlling the operation by the third operation control means by altering a portion or a whole of the score values of the degrees of similarity after having stored the score values of the degree of similarity in said score memory and to perform a process for controlling the operation by the first operation control means.

3. The gene database retrieval system as claimed in claim 1, wherein said dynamic programming operation unit further comprises a rewritable score memory for storing the score values of the degree of similarity and holds in said score memory the score values in a non-symmetrical form of a matrix configuration of sequence elements in accordance with sequence elements on the key data side;

and

wherein said central processing device unit is arranged in order to perform the control of the operation by said first or third operation control means by utilizing the score value of said score memory.

4. The gene database retrieval system as claimed in claim 1, wherein said dynamic programming operation unit comprises a data conversion section for converting a data type into a predetermined form, wherein the sequence data stored in the gene database is compressed or transformed;

and

wherein said central processing device unit is arranged in order to execute the operation of the dynamic programming by reading the sequence data of the gene database in an intact form, to transmit the read sequence data to the dynamic programming operation unit and to allow the input sequence data to be converted into a predetermined form by the data conversion section of said dynamic programming operation unit.

5. The gene database retrieval system as claimed in claim 1, wherein said dynamic programming operation unit further comprises a data conversion section for converting a data type into a predetermined form, wherein the operation of the dynamic programming is executed by reading the sequence data from the gene database, allowing the read sequence data to be compressed or transformed in the central processing device unit, transmitting the compressed or transformed data to the dynamic programming operation unit, and by allowing the data conversion section of said dynamic programming operation unit to convert the data into a predetermined form.

6. The gene database retrieval system as claimed in claim 1, wherein said third operation control means performs the controls of operations comprising:

an operation for executing the operation for each row until reaching a predetermined length of the key data or the target data;

an operation for acquiring the maximal value of the sum values for each row and for interrupting the operation when the row is found which is identical to the maximal sum value determined by the operation by the first operation control means;

an operation for acquiring the contents of the sum value memory of the involved row and the direction selection data;

an operation for determining the position of the maximal value of the sum values from said sum value memory;

an operation for acquiring the direction selection data corresponding to the position of the maximal value thereof; and

an operation for acquiring the direction selection data while re-executing the operation of the dynamic programming on the basis of the direction selection data at least in the position identical to the corresponding position or in one region containing the position or more than the position.

7. The gene database retrieval system as claimed in claim 1, wherein said third operation control means performs the controls of operations comprising:

an operation for executing the operation for each column until reaching a predetermined length of the key data or the target data;

an operation for acquiring the maximal value of the sum values for each column and for interrupting the operation when the column is found which is identical to the maximal sum value determined by the operation by the first operation control means;

an operation for acquiring the contents of the sum value memory of the involved column and the direction selection data;

an operation for determining the position of the maximal value of the sum values from said sum value memory;

an operation for acquiring the direction selection data corresponding to the position of the maximal value thereof; and

an operation for acquiring the direction selection data while re-executing the operation of the dynamic programming on the basis of the direction selection data at least in the position identical to the corresponding position or in one region containing the position or more than the position.

8. The gene database retrieval system as claimed in claim 1, further comprising a device for determining a gene sequence, which outputs a sequence data of bases for the retrieval key;

wherein the sequence data of the bases output from said device is input as the key data into said dynamic programming operation unit.

9. The gene database retrieval system as claimed claim 1, wherein the access process for making access to the gene database by said central processing device unit is executed in parallel to the operation process by said dynamic programming operation unit at least for a portion of the time period of the operation of the processes, and wherein said central processing device unit is so arranged as to read the oncoming target data from the gene database prior to the operation by said dynamic programming operation unit during the period of time during which the operation is being executed by said dynamic programming operation unit.

10. The gene database retrieval system as claimed in claim 1, wherein said dynamic programming operation unit comprises:

a key memory for storing the key data of the sequence data of bases functioning as the retrieval key;

a target memory for storing the target data of the sequence data from the gene database;

a score memory for storing the definition of the degree of similarity between the individual base elements of the sequence data of the bases;

a basic operation processing section for executing a basic operation of the dynamic programming;

a direction selection memory for storing a record of a direction of selecting a locally optimal value occurring at the time when the basic operation processing section performs the basic operation of the dynamic programming;

a sum value memory for storing the sum values obtained by the operation of the dynamic programming; and

a control section for controlling the operation of the dynamic programming by controlling each of said memories and said basic operation processing section.

11. The gene database retrieval system as claimed in claim 10, wherein said dynamic programming operation unit further comprises:

a constant register for storing a constant value for use in comparing the sum values acquired by the operation of said dynamic programming; and

an operation element for replacing the sum value with the constant value when the sum value is brought into a given relationship with the constant value of the constant register.

12. The gene database retrieval system as claimed in claim 10, wherein said dynamic programming operation unit further comprises:

a constant register for storing a constant value in comparing the sum value acquired by the operation of said dynamic programming; and

an operation element for generating a signal to suspend the operation element when the sum value resulting from the operation is brought into a given relationship with the constant value of the constant register.