System and method for a precompiled database for biomolecular sequence information

Abstract

A computer system stores biomolecular data in a database in a memory. The biomolecular database has a set of entities. Each entity stores attributes for a plurality of entries. At least one attribute is stored in an array. Data associated with an entry is stored at a location in the array. An entity offset designates the location of the data in the array. The same entity offset value is used to access data associated with a particular entry for all attributes within the entity.

Claims

What is claimed is:

1. A method of accessing biomolecular data stored in a database, comprising the steps of:

generating a set of entities, each entity storing attributes for a plurality of entries, at least one attribute being stored in an array wherein data associated with an entry is stored at a location in the array, an entity offset designating the location of the data associated with each entry within the array, wherein the same entity offset is used to access data associated with a particular entry for all attributes within the entity;

storing the generated set of entities in a memory; and

retrieving data associated with the at least one attribute of a particular entry of one of the entities in the set of entities using an associated entity offset.

2. The method of claim 1 wherein at least one entity is a clone entity having a clone name attribute associated with a clone name, further comprising the step of:

generating the clone name attribute as a function of the entity offset of the clone entity.

3. The method of claim 1 wherein at least one entity has a first attribute, further comprising the step of:

generating the first attribute value based on the associated entity offset.

4. The method of claim 1, wherein the set of entities includes a first entity and a second entity, and further comprising the steps of:

storing a particular offset value associated with a particular entry of the second entity in a first array for an entry of the first entity; and

accessing the particular entry of the second entity using the particular offset value stored in the first array for the entry of the first entity.

5. The method of claim 1 wherein the set of entities includes a clone entity and a library entity, and further comprising the steps of:

storing a particular library offset value associated with a particular library entry of the library entity in a clone.library array for a clone entry of the clone entity; and

accessing the particular library entry of the second entity using the particular library offset value stored in the clone.library array for the clone entry of the clone entity.

6. The method of claim 1 wherein the set of entities includes:

a first entity with plurality of first entries in a first array, and

a second entity with a plurality of second entries in a second array, one of the plurality of second entries being a particular second entry associated with a particular second offset value, and

further comprising the step of:

associating a set of first entries having a set of first offset values with the particular second entry by:

storing the set of first offset values in a subsidiary array at a location associated with a particular subsidiary array offset value; and

storing the particular subsidiary array offset value in the second array at a location designated by the particular second offset value.

7. The method of claim 6 further comprising the steps of:

storing, in the second array, a count representing the number of entries of the set of first entries; and

wherein said step of storing the set of first offset values sequentially stores the offset values of the set of first offset values in the subsidiary array.

8. The method of claim 7 further comprising the steps of

retrieving the count value;

retrieving the set of first offset values in the subsidiary array; and

accessing the entries of the set of first entries based on the set of first offset values.

9. The method of claim 1 wherein the set of entities includes:

a clone entity with plurality of clone entries, a portion of the plurality of clone entries being a first set of clone entries and having a first set of clone offset values, and

a cluster entity with a plurality of cluster entries in a Cluster.Clone attribute array, one of the plurality of cluster entries being a particular cluster entry with an associated a particular cluster offset value, and

further comprising the step of:

associating the first set of clone entries with the particular cluster entry by:

storing the first set of clone offset values in a subsidiary array at a location associated with a particular subsidiary array offset value; and

storing the particular subsidiary array offset value in the Cluster.Clone attribute array at a location designated by the particular cluster offset value for the particular cluster entry.

10. The method of claim 9 wherein the cluster entries include high scoring pairs of associated clone entries having a region of sequence homology such that the region of sequence homology comprises a first predetermined number of matches that exceeds a threshold number of matches, wherein the threshold number of matches was increased when the region of sequence homology was not 100% similar.

11. The method of claim 9 further comprising:

a MapPos entity wherein a portion of the entries of the clone entity and a portion of the entries of the cluster entity are associated with the MapPos entity.

12. The method of claim 1 wherein the set of entities includes:

a tissueclass entity for establishing a predefined hierarchy of tissue classes; and

a library entity including a library.tissueclass attribute array for associating an entry of the library entity with at least one entry of the tissueclass entity.

13. The method of claim 12 wherein the tissueclass entity has a TissueClass.Name attribute array and a tissueclass.sub-class attribute array; further comprising the steps of:

storing a particular tissueclass name for a particular entry in the TissueClass.Name attribute array; and

storing a tissueclass offset value in the tissueclass.sub-class attribute array for the particular entry such that the tissueclass offset value associates another tissueclass entry having a different tissueclass name with the particular tissueclass entry.

14. The method of claim 13 further comprising the step of:

populating a portion of the tissueclass entity with tissueclass entries having predetermined relationships among the tissueclass entries as defined by the TissueClass.Name attribute array, a tissueclass.parent attribute array and the tissueclass.sub-class attribute array.

15. The method of claim 1 wherein the set of entities includes:

a cluster entity;

a HitID entity for associating entries of the cluster entity with entries of the HitID entity, the entries of the HitID entity being identifiers of known biomolecules; and

a proteinfunction entity for establishing a predefined hierarchy of biomolecules by protein function, having a proteinclass.hitid attribute array for associating entries of the proteinfunction entity with entries of the HitID entity,

wherein the proteinclass.hitid attribute array associates a biomolecule entry with at least one identifier of a known biomolecule in the HitID entity, allowing a user to search for biomolecular information by protein function and to identify clusters performing that protein function.

16. The method of claim 15 wherein the proteinfunction entity has a proteinfunction.name attribute array and a proteinfunction.subclass attribute array;

further comprising the steps of:

storing a particular biomolecule name for a particular entry in the proteinfunction.name attribute array; and

storing a proteinfunction offset value in the proteinfunction.subclass attribute array for the particular entry such that the proteinfunction offset value associates another proteinfunction entry having a different biomolecule name with the particular proteinfunction entry for establishing a hierarchy of protein functions.

17. A computer system for a biomolecular database, comprising:

a biomolecular database stored on memory media associated with the computer system, the biomolecular database having a set of entities, each entity storing attributes for a plurality of entries, at least one attribute being stored in an array wherein data associated with an entry is stored at a location in the array, an entity offset designating the location of the data associated with each entry within the array, wherein the same entity offset is used to access data associated with a particular entry for all attributes within the entity; and

a data retrieval process that includes instructions for:

receiving a request for data associated with a particular attribute of the particular entry of a particular entity and returning the retrieved data to the requester,

determining a particular entity offset value associated with the particular entry of the particular entity, and

retrieving data using the particular entity offset value.

18. The computer system of claim 17 wherein at least one entity is a clone entity having a clone name attribute associated with a clone name, the data retrieval process further including instructions for:

generating the clone name attribute as a function of the entity offset of the clone entity.

19. The computer system of claim 18 wherein the set of entities includes:

a library entity having library entries including a particular library entry associated with a particular library offset value; and

a clone entity having a clone.library array storing associated library entity offset values, the particular library offset value being stored in the clone.library array to associate a particular clone entry with the particular library entry;

the data retrieval process further including instructions for:

accessing the particular library entry of the library entity using the particular library offset value stored in the clone.library array.

20. The computer system of claim 17 wherein at least one entity has a first attribute, the data retrieval process further including instructions for:

generating the first attribute value based on the associated entity offset.

21. The computer system of claim 17, wherein the set of entities includes:

a clone entity with plurality of clone entries, a portion of the plurality of clone entries being a first set of clone entries and having a first set of clone offset values, and

a cluster entity with a plurality of cluster entries in a Cluster.Clone attribute array, one of the plurality of cluster entries being a particular cluster entry with an associated a particular cluster offset value,

wherein the first set of clone entries is associated with the particular cluster such that the first set of clone offset values is stored in a subsidiary array at a location associated with a particular subsidiary array offset value; and the particular subsidiary array offset value is stored in the Cluster.Clone attribute array at a location designated by the particular cluster offset value for the particular cluster entry; and

the data retrieval process further includes instructions for

retrieving the first set of clone offset values from the subsidiary array; and

accessing the entries in the clone entity using the first set of clone offset values.

22. The computer system of claim 21 wherein clusters have a high scoring pairs having a region of sequence homology such that the region of sequence homology comprises a first predetermined number of matches, that exceeds a threshold number of matches, wherein the threshold number of matches was increased when the region of sequence homology was not 100% similar.

23. The computer system of claim 21 wherein the set of entities further includes:

a MapPos entity wherein a portion of the entries of the clone entity and a portion of the entries of the cluster entity are associated with the MapPos entity.

24. The computer system of claim 17 wherein the set of entities includes:

a tissueclass entity for establishing a predefined hierarchy of tissue classes; and

a library entity including a library.tissueclass attribute array for associating an entry of the library entity with at least one entry of the tissueclass entity.

25. The computer system of claim 17 wherein the set of entities includes:

a cluster entity;

a HitID entity for associating entries of the cluster entity with entries of the HitID entity, the entries of the HitID entity being identifiers of known biomolecules, and

a proteinfunction entity for establishing a predefined hierarchy of biomolecules by protein function, having a proteinclass.hitid attribute array for associating entries of the proteinfunction entity with entries of the HitID entity,

wherein the proteinclass.hitid attribute array associates a biomolecule entry with at least one identifier of a known biomolecule in the HitID entity, allowing a user to search for biomolecular information by protein function and to identify clusters performing that protein function.

26. A computer program product for a computer system that stores a biomolecular database comprising a computer readable storage medium and a computer program mechanism embedded therein, the computer program product comprising:

a biomolecular database stored on memory media associated with the computer system, the biomolecular database having a set of entities, each entity storing attributes for a plurality of entries, at least one attribute being stored in an array wherein data associated with an entry is stored at a location in the array, an entity offset designating the location of the data associated with each entry within the array, wherein the same entity offset is used to access data associated with a particular entry for all attributes within the entity; and

a data retrieval module that includes instructions for:

receiving a request for data associated with a particular attribute of the particular entry of a particular entity and returning the retrieved data to the requester,

determining a particular entity offset value associated with the particular entry of the particular entity, and

retrieving data using the particular entity offset value.

27. The computer program product of claim 26 wherein at least one entity of the set of entities is a clone entity having a clone name attribute associated with a clone name, and

the data retrieval module includes instructions for:

generating the clone name attribute as a function of the entity offset of the clone entity.

28. The computer program product of claim 27 wherein the set of entities includes:

a cluster entity;

a HitiD entity for associating entries of the cluster entity with entries of the HitID entity, the entries of the HitID entity being identifiers of known biomolecules; and

a proteinfunction entity for establishing a predefined hierarchy of biomolecules by protein function, having a proteinclass.hitid attribute array for associating entries of the proteinfunction entity with entries of the HitID entity,

wherein the proteinclass.hitid attribute array associates a biomolecule entry with at least one identifier of a known biomolecule in the HitID entity, allowing a user to search for biomolecular information by protein function and to identify clusters performing that protein function.

29. The computer program product of claim 26 wherein at least one entity of the set of entities has a first attribute, and

the data retrieval module includes instructions for:

generating the first attribute value based on the associated entity offset.

30. The computer program product of claim 26 wherein the set of entities includes:

a library entity having library entries including a particular library entry associated with a particular library offset value, and

a clone entity having a clone.library array storing associated library entity offset values, the particular library offset value being stored in the clone.library array to associate a particular clone entry with the particular library entry; and

the data retrieval module includes instructions for:

accessing the particular library entry of the library entity using the particular library offset value stored in the clone.library array.

31. The computer program product of claim 26, wherein the set of entities includes:

a clone entity with plurality of clone entries, a portion of the plurality of clone entries being a first set of clone entries and having a first set of clone offset values, and

a cluster entity with a plurality of cluster entries in a Cluster.Clone attribute array, one of the plurality of cluster entries being a particular cluster entry with an associated a particular cluster offset value,

wherein the first set of clone entries is associated with the particular cluster such that the first set of clone offset values is stored in a subsidiary array at a location associated with a particular subsidiary array offset value; and the particular subsidiary array offset value is stored in the Cluster.Clone attribute array at a location designated by the particular cluster offset value for the particular cluster entry; and

the data retrieval module further includes instructions for

retrieving the first set of clone offset values from the subsidiary array; and

accessing the entries in the clone entity using the first set of clone offset values.

32. The computer program product of claim 31 wherein clone entries associated with cluster entries of the cluster entity include high scoring pairs of associated clone entries having a region of sequence homology such that the region of sequence homology comprises a first predetermined number of matches that exceeds a threshold number of matches wherein the threshold number of matches was increased when the region of sequence homology was not 100% similar.

33. The computer program product of claim 30 wherein the set of entities includes:

a MapPos entity, wherein a portion of the entries of the clone entity and a portion of the entries of the cluster entity are associated with the MapPos entity.

34. The computer program product of claim 26 wherein the set of entities includes:

a tissueclass entity for establishing a predefined hierarchy of tissue classes; and

library entity including a library.tissueclass attribute array wherein the library.tissueclass attribute array associates an entry of the library entity with at least one entry of the tissueclass entity.

Description

The present invention relates generally to a system and method for storing and retrieving biomolecular sequence information. More particularly, the invention relates to a system and method for storing biomolecular sequence information in a precompiled, modular format which allows for rapid retrieval of the information.

BACKGROUND OF THE INVENTION

Informatics is the study and application of computer and statistical techniques to the management of information. In genome projects, bioinformatics includes the development of methods to search databases quickly, to analyze nucleic acid sequence information, and to predict protein sequence and structure from DNA sequence data. Increasingly, molecular biology is shifting from the laboratory bench to the computer desktop. Advanced quantitative analyses, database comparisons, and computational algorithms are needed to explore the relationships between sequence and phenotype.

One use of bioinformatics involves studying genes differentially or commonly expressed in different tissues or cell lines such as in normal or cancerous tissue. Such expression information is of significant interest in pharmaceutical research. A sequence tag method is used to identify and study such gene expression. Complementary DNA (cDNA) libraries from different tissue or cell samples are available. cDNA clones, or expressed sequence tags (ESTs) that cover different parts of the mRNA(s) of a gene are derived from the cDNA libraries. The sequence tag method generates large numbers, such as thousands, of clones from the cDNA libraries. Each cDNA clone can include about 100 to 800 nucleotides, depending on the cloning and sequencing method. Assuming that the number of sequences generated is directly proportional to the number of mRNA transcripts in the tissue or cell type used to make the cDNA library, then variations in the relative frequency of occurrence of those sequences can be stored in computer databases and used to detect the differential expression of the corresponding genes.

Sequences are compared with other sequences using heuristic search algorithms such as the Basic Alignment Search Tool (BLAST). BLAST compares a sequence of nucleotides with all sequences in a given database. BLAST looks for similarity matches, or `hits`, that indicate the potential identity and function of the gene. BLAST is employed by programs that assign a statistical significance to the matches using the methods of Karlin and Altschul (Karlin S., and Altschul, S. F. (1990) Proc. Natl. Acad. Sci. U.S.A. 87(6): 2264-2268; Karlin, S. and Altschul, S. F. (1993) Proc. Natl. Acad. Sci. U.S.A. 90(12): 5873-5877). Homologies between sequences are electronically recorded and annotated with information available from public sequence databases such as GenBank. Homology information derived from these and other comparisons provides a basis for assigning function to a sequence.

Typically computer systems use relational databases to store, process, and manipulate nucleotide and amino acid sequences, expression information, chromosomal location, and protein function information. As the amount of biomolecular information increases, the computer systems and their databases must accommodate the storage, retrieval, comparison, and display of very large amounts of data. Typically, the data is stored in multiple files making up a relational database. Each file has records with predefined fields. Records are accessed using at least one field that is designated as a key or index. Relational databases typically use a join operation to cross reference data stored in different files based on a common key field. The join operation basically combines data stored in multiple files. However, if one of the files being joined, such as the cDNA or clone file, is unusually large, then even a simple join operation with a small file is time consuming and slow.

In addition, relational databases use separate data and index files. Index files are used to access information in corresponding data files. Typically, a large amount of storage is needed to store both the data and index files. Therefore, in a system with many data and index files, it is unlikely that all data can be stored at any one time in the main memory of the computer system. The data that remains on the disk must be swapped into main memory. The swapping of data into main memory further contributes to the slow response time of data retrieval systems having unusually large database tables.

Therefore, there is a need for a biomolecular database that eliminates the need for using join operations. In addition, there is a need for a biomolecular database that can be stored in the main memory of ordinary desktop computer systems. There is also a need for a biomolecular database with a common set of tissue classes that can assign a cDNA library to many different tissue classes.

The present invention provides a self-sufficient modular database that organizes and precompiles data to eliminate the need for using join operations. In addition, the database is organized such that the entire database can be stored in the main memory of the computer system. The present invention also provides a way to associate a cDNA library with multiple tissue classes.

SUMMARY OF THE INVENTION

A computer system stores biomolecular data in a database in a memory. The biomolecular database has a set of entities. Each entity stores attributes for a plurality of entries. At least one attribute is stored in an array. Data associated with an entry is stored at a location in the array. An entity offset designates the location of the data in the array. The same entity offset value is used to access data associated with a particular entry for all attributes within the entity.

The modular database allows extremely rapid search, comparison, and retrieval of information from very large databases. In the database, joins are eliminated through the use of a set of predefined addressing techniques. The data is organized into entities and the relationships of the data between entities is pre-compiled. Offsets or pointers define relationships between entities. Although entity offsets may be stored in multiple locations, the biomolecular data is stored once.

The addressing technique allows for rapid searching and comparisons of very large amounts of sequence data. Such rapid processing of sequence information provides the capability for significant analysis of the biological function of the huge numbers of sequences currently residing in public and private databases.

The present invention also provides a database and system that allows for comparison of libraries. Library comparison techniques include direct comparisons of sequence expression between libraries that were derived from normal and diseased tissues to provide expression information useful for identifying target molecules for pharmaceutical therapy.

In addition, the present invention provides a database that is structured so as to facilitate quick access to expression level information for a specified cluster or set of clusters of sequences in a specified set of libraries (each of which represents a specific source of expression information). The present invention also provides tools for quickly determining the sensitivity and specificity of expression level values.

The invention also provides an improved technique for assessing similarities between sequences and clustering multiple sequences.

The modular database increases the speed of analyzing sequences which will help accelerate biomolecular research for numerous applications.

BRIEF DESCRIPTION OF THE DRAWINGS

Additional objects and features of the invention will be more readily apparent from the following detailed description and appended claims when taken in conjunction with the drawings, in which:

FIG. 1 is a diagram of a client-server system suitable for use with the present invention.

FIG. 2 is depicts the modules of the modular database system in connection with user interface.

FIG. 3A is an exemplary clone entity with several exemplary attribute arrays.

FIG. 3B is a portion of an exemplary cluster entity illustrating use of a POS structure and secondary array to associate a single entry of the cluster entity with multiple clones.

FIG. 4 depicts the logical data structure of the entities of the modular database.

FIG. 5 shows various procedures stored in the memory of the modular database.

FIG. 6A is a block diagram of a clone offset determination procedure.

FIG. 6B is a block diagram of a clone name determination procedure.

FIG. 7 is a flowchart showing a method of populating the POS structure of FIG. 3B to associate a single entry of a cluster entity with multiple clones.

FIG. 8A shows exemplary sequences suitable for use with the clustering method of FIG. 8B.

FIG. 8B is a flowchart of an improved clustering method of the present invention.

DESCRIPTION OF THE PREFERRED EMBODIMENTS

FIG. 1 depicts a network system for retrieving information stored in the biomolecular database of the present invention. The major computer system components of the network are:

at least one client computer system 20,

multiple HTTP servers 22, 24 to access the world-wide-web (WWW),

a LifeSeq Atlas Database Server 26 that stores the modular database 28,

another data base server 30, and

a firewall gateway server 32 that connects to the Internet 34.

The client computer system 20 connects to at least one HTTP server, 22, 24, that is used to access the world wide web. The network can have multiple servers, server (1) 22 to server (N) 24. In an alternate embodiment, to ensure high availability, the system automatically switches between the servers if one of the servers becomes unavailable. The client system 20, via the firewall gateway server 32, also has access to public domain resources 36, 38, 40, 42 and 44 on the Internet 34. On the client computer system 20, a user runs web browser software 46 to access both the public domain resources 36, 38, 40, 42 and 44 and the biomolecular data in the modular database 28.

One of the HTTP servers, HTTP Server 1, 22 stores and executes the LifeSeq Atlas interface module 50 to process user requests for data. The LifeSeq Atlas Interface module 50 includes many types of modules such as CGI procedures 52, configuration files 54 and HTML pages 56. The CGI procedures 52 allow the client web browser 46 to access data stored on the LifeSeq Atlas database server 26. The configuration files 54 store the paths where the local resources reside, such as BLAST files and also store the URLs of outside resources. The HTML pages 56 are static documents that are transmitted to the client Web browser 46 and may include HTTP hyperlinks to other resources.

The client system 20, HTTP servers 22, 24, the LifeSeq Atlas database server 26 and the other database server 30 may be networked via an intranet using TCP/IP protocol. The servers 22, 24, 26, 30 and 32 may be UNIX workstations having 512 MB of main memory, a F4VSCSI-2 adapter or Fiber Link Disk Controller, a CD-ROM Drive, an internal floppy disk drive X560A and multiprocessor systems with at least four processors. The client computer system 20 can be a personal computer or UNIX workstation.

FIG. 2 shows the flow of information between the various modules of the system to generate a response to a user's query of the modular database. The client computer's web browser provides a graphical user interface (GUI) 60 that allows the user to graphically construct search requests to retrieve data from the databases.

The GUI 60 includes well-known elements such as buttons, pull down menus, and scroll bars that provide a way for the user to construct the search request.

The user selects parameters and the desired information using the GUI 60 of the web browser (46, FIG. 1). The web browser 46 passes the input to a CGI script 62 on one of the HTTP servers. The CGI script 62 sends a string of commands and passes the input to the modular database module 64 which returns the requested data to the CGI script 62. The CGI script uses HTTP protocol. The CGI script 62 sends the data back to the HTTP server. The HTTP server passes the data back to the user's web browser 46 and the results are displayed on the GUI 60 on the client computer.

The software modules of the modular database 66 form a hierarchy having a server level 68, a function level 70, and data access procedures 72. A data level 74 includes the entities (e.g., database tables) that store the biomolecular data such as the clone entity 76 and the library entity 78.

In the server level 68, a communications interface module 80 communicates with the CGI procedures 62 using UNIX sockets. The communication interface 80 receives commands from the CGI procedures 62 and sends the commands to the query/response module 82. The query/response module 82 has modules that authenticate a password 84 that is part of the command, generate or update a log file 86, and parse the command 88. The query/response module 82 also has a module 90 that calls a function level procedure in response the parsed command.

The function level 70 has modules or procedures that accumulate the data for the different types of queries available from the user interface. In other words, the function level modules 70 populate predefined structures with data and return the predefined structures to the query/response module 82, and will call various data access procedures 72 to retrieve the requested information from the data level 74. For example, the function level 70 includes procedures such as get clone information 92, get transcript image 94 and a function to send results to the query/response module 96.

The data access procedures 72 are the lowest level procedures and retrieve the biomolecular data from the entities 76, 78 of the modular database 74. Exemplary procedures comprise a clone offset determination procedure 98, a clone name determination procedure 100 and a library name determination procedure 102. After the requested data is retrieved, the function level 70 returns the data to the query/response module 82. In response to the query/response module 82, the communications interface 80 opens a socket and transmits the data to the CGI procedure 62.

One advantage of the modular database is that the database provides a consistent Application Programming Interface (API) 103. Even if the database schema changes, the user interface 60 and CGI procedures 62 need not be changed.

Structure of the Database

The database stores precompiled biomolecular data and organizes the biomolecular information into entities (e.g., database tables). Each entity has a set of attributes (sometimes called the columns of a database table). Generally, information for an attribute is stored in an array or database table. Each array has multiple entries. For a particular entry of an entity, the same offset value provides access to all the attribute information for that entry within that entity. For instance, if the offset for a particular entry is 11225, then all the attribute information for that entry will be found at offset 11225 in the various attribute arrays for the entity. Each array may be stored in a separate file.

The following naming convention will be used to refer to an attribute of an entity: "entity name. attribute name."

FIG. 3A shows an exemplary portion of a clone entity 76 with clone.name 112, clone.library 114 and clone.sequence 116 attribute arrays. As shown by the dashed lines of FIG. 3A, a single clone offset (e.g., with a value of "10") points to the location or address in which information for a particular clone is stored in all the clone entity arrays. In other words, the attribute information for the 10.sup.th clone in the clone entity is located at clone.name(10), clone.library(10) and clone.sequence(10).

In the present discussion, the term "location" refers to the "logical" location of the information, as opposed to its physical location in memory. Arrays are made up of a repeating data structure. Because arrays can use different data structures, the same logical location for different arrays may generate very different physical addresses.

An entity stores three types of data: absolute or actual data, offset data, and POS structures. FIG. 3A shows an example of absolute data in which the clone offset 10 points to an entry having a clone name of I0009 in the clone.name attribute array.

The offset data is used to define the relationships among the entries of the entities. In FIG. 3A, as an example of offset data, the clone.library attribute array 114 does not store a library name, but stores an appropriate offset value, shown as "offset lib," which is used to access the corresponding entry storing "HUVELPB01" in the library.name attribute array 117 of the library entity 78. The use of offset data reduces the amount of absolute data stored in the database thereby reducing the size of the database.

The database allows multiple entries to be associated with a single entry. A POS structure and a secondary array are used to define this many to one relationship. The many to one relationship can be defined for entries in the same or different entities. For example, as shown in FIG. 3B, an attribute array, called cluster.clone 118, uses a POS structure with a secondary attribute array, called cluster.clone.2119, to associate multiple clone offset values with a single cluster entry. The attribute array, cluster.clone 118, is an array of POS structures and is stored in a file. The secondary attribute array is also stored in a file. The POS structure has two fields: a count and an offset. The count and the offset fields are integers. The count field stores the number of offset values associated with the entry. The offset points to a location in the secondary attribute array where the offset values are stored. In FIG. 3B, a cluster offset called "X" points to a cluster.clone entry having a count of three and a secondary offset of 400. The count indicates that the cluster has three clones. The offset of 400 points to the location in the cluster.clone.2 array 119 that stores a clone offset of 18 that is used to access data from the clone entity. In other words, the offset into the secondary array points to the first associated offset value of a set of offset values, and the count represents the number of offset values in the set. The other two offsets that are used to access the remaining clones of the cluster, offsets 300 and 1036, are stored in consecutive locations in the cluster.clone.2 secondary array 119.

More generally, as shown in FIG. 3B, a count can have any integer value N, and the cluster entry can be associated with N entries of the clone array with N clone offset values.

Alternately, the POS structure with a secondary array is used to store variable length information in which the POS count stores the length of the data and the POS offset points to the starting address of the data.

In another alternate embodiment, the secondary array need not always store offsets into entities but stores actual or absolute data.

In yet another alternative embodiment, the secondary array uses POS structures that have a count and an offset pointing to a tertiary array.

When the modular database is created, the offsets are generated and populated, and the relationships among the data are precompiled. Therefore, the modular database eliminates the need for time consuming table joins. As a result, the database efficiently retrieves data in which a small subset of the entities stored in the database have a disproportionately large amount of data compared to other entities stored in the database.

From another viewpoint, the precompiled offset values stored in the database enable the system to form "limited range" joins, joining the data from two or more tables for a limited (i.e., specified) set of records without having to form full table joins. As a result, when a join is needed that involves the use of data from a very large table (such as the clone entity in the preferred embodiment), the present invention is very efficient because (A) very little memory is needed for the "mini-join" records that are formed compared to the enormous full table joins that would normally have to be formed using conventional relational database management system (RDBMS) technology, (B) very few computational resources are needed to form the mini-join records, since all the offsets needed to retrieve the data for the mini-join have been precomputed and stored in the database.

The entities of the database can be compared to the tables of a relational database. However, the entities of the database comprise a set of separate arrays for each attribute. Unlike in relational databases, instead of having attributes that match between tables, the database has precomputed offsets. Therefore, joins are done on a record-by-record basis, and not on a table basis.

FIG. 4 is a block diagram of the logical structure of the database. Each block is an entity and is labeled with the name of the entity. The attributes are listed inside the block. The underlined attributes represent absolute attribute values. To save storage space, absolute data is generally stored in one entity and other entities store offsets to access the absolute data. Those attributes represented by plain text without underlining represent either an offset or a POS structure. The symbol [ ] indicates that, for a single entry, the attribute can have multiple attribute values, in other words, that the attribute uses the POS structure with a secondary array.

The physical structure of the database is similar to the logical structure. The data type of each attribute is shown next to the attribute's name. The data type is the form in which the attribute is stored within the array. The abbreviations are defined as follows: int means integer and POS means the POS structure described above. Generally "char" means a character string, with certain exceptions. The name attribute in the HitID entity uses a forty-four bit character string. In an alternate embodiment, the name attribute of the HitID entity uses a POS structure. The ProteinClass.name, TissueClass.name, library.comment and library.description attributes use a POS structure to store variable length strings.

For a definition of each attribute, see Table 2.

Procedures

FIG. 5 shows an exemplary list of procedures stored in a memory of a computer system 120 of the modular database. This computer system 120 functions as both HTTP server 1 with the LifeSeqAtlas Interface module and the LifeSeqAtlas database server. In an alternate embodiment, two different computer systems perform these functions.

The computer system has a CPU 122, display 124, keyboard 126, mouse 128 and memory 130. The memory 130 may include RAM and various other storage devices such as disk drives. The procedures will be described in more detail below.

Clone Names

In a preferred embodiment, a clone name is not physically stored in the clone entity. Therefore, in FIG. 4, the name attribute of the clone entity does not have a data type. The modular database uses clone name mapping arrays 140 (FIG. 5) which map the clone offset value to the clone name to avoid assigning the same clone offset to different clone names. The clone name mapping arrays are stored in files, and are built each time the modular database is constructed. To build the clone name mapping arrays, clones and the corresponding clone names are collected from many sources. Each source has its own naming convention. For example, clone names begin with certain characters such as I, Y, Z, N and E. The clone names have the format shown in Table 1 below.

         TABLE 1
         First Character of
         Clone Name       Format of Clone Name
         I                I [number]
         Y                Y [a . . . 2]  [01 . . . 99] [a . . . h] [01 . . .
     12]
         Z                Z [a . . . 23] [01 . . . 99] [a . . . h] [01 . . .
     12]
         N                N [a . . . 23] [01 . . . 99] [a . . . h] [01 . . .
     12]
         E                EST[000001 . . . 999999]

    TABLE 2
    Entity Description
    Clone Entity
    name-derived from clone offset to clone entity table
    library-offset to library entity associated with the clone name
    sequence-array of offsets (POS structure) for clone nucleic acid
    sequence
    cluster-offset to cluster entity containing clone
    annotation-offset to annotation entity
    MapPos-array of offsets to MapPos Entity
    BAC-array of offsets to BAC entity for associated Bacterial artificial
    chromosome clones
    YAC-array of offsets to YAC entity for associated Yeast artificial
    chromosome clones
    Cluster Entity
    Clone-is a POS structure to indicate the clones belongs to a particular
    cluster
    LibCount-stores a POS structure and is used to indicate the number
    of libraries in which that cluster appears, and the associated
    offset values of the entries of the library antedate in which that
    cluster appears.
    Annotation-offset to the Annotation entity
    MapPos-is POS structure for associating mapping information with a
    cluster.
    BAC-array of offsets to BAC entity for associated Bacterial artificial
    chromosome.
    YAC-array of offsets to YAC entity for associated Yeast artificial
    chromosome
    Library Entity
    Name-the library name
    Clone-a POS structure for associating multiple clones with a library
    Type-a number representing library preparation condition
    Usable-number of usable clones in library
    AnnotSGL clone[ ]-POS structure for associating annotated singleton
    (a cluster consisting of one clone) clones with Cluster names
    that are identical to their Clone name
    UNISGL clone [ ]-POS structure for associating unique singleton
    clones with cluster name
    Specific Cluster-array of offsets to cluster entity, for those clusters
    that occur in a single library or class
    Unspecific Cluster-array of offsets to cluster entity for those clusters
    that occur in multiple libraries or tissue classes
    Tissue Class-array of offsets into TissueClass entity to associate a
    library with tissue classes
    Description-uses a POS structure to store variable length data stored
    in a secondary file. The description information describes the
    tissue pathology.
    Comment-similar to description and uses a POS structure to store
    variable Length data stored in a secondary file.
    Annotation Entity
    HitID-an offset pointing to the HitID Entity
    Product Score-an integer representing a normalized value between 0
    and 100 indicating the strength of a BLAST match between two
    sequences.
    LogLikelihood-an integer representing the probability that a sequence
    match was due to random chance.
    Extent-an integer which indicates whether any coding information is
    present within the clone.
    FunctionHit-uses a POS structure to point to multiple entries in the
    FunctionHit Entity. Function Hit means protein function and is
    taken from the annotation.
    TissueClass Entity
    Name: uses a POS structure to store a name having any number of
    characters
    parent tissue class: is an offset pointing to another entry in the
    TissueClass table that is the parent tissue of the tissue in the
    Name attribute. (such as if name is "leucocyte", then the parent
    would be the tissue class having a name attribute equal to
    "blood.")
    subclass TissueClass: since a tissue class can have many subclasses,
    a POS structure points to the starting entry a secondary array or
    file. The information stored in the secondary array or file is
    actually another offset pointing to another entity in the Tissue
    Class. If there are no subclasses, the POS structure stores a 0
    in its number or count.
    Specific library[ ]-an array of offsets pointing to the library entity that
     is
    specific for the cluster
    Specific Usable-an integer meaning the number of clones in the
    library(ies) that the cluster is specific to
    Total Library [ ] -an array of offsets pointing to total number of usable
    clones in the library(ies) a clone is specific to
    Total Usable-an integer meaning the total number of usable clones in
    library(ies) a cluster is specific to
    MapPos Entity
    Marker-A unique positional identifier for a chromosomal location
    MapType-an annotation specifying the type of map
    Chromosome-an integer specifying the chromosome
    Position-an integer indicating a Location on a chromosome
    LodScore-an integer representing a ratio of likelihood of being within
    a Location on a chromosome
    Source-an integer indicating the map source
    ProteinClass Entity
    Name has a variable length and uses a POS structure.
    parentClass-an offset pointing to a higher protein function class
    subClass-an offset pointing to a protein function subclass
    HitID-an array of offsets to the HitID entity
    HitID Entity
    Name is a GenBank internal identifier that is associated with a
    homolog which is used to access data in GenBank.
    Clone-an offset into the clone entity
    Cluster-an array of offsets to the cluster entity
    Singleton-an offset into the clone entity
    FunctionHit Entity
    Type-an integer representing a protein function class
    FunctionID-an integer identifying a protein function derived from
    annotation
    YAC Entity
    Name is an identifier for the YAC
    clone-an array of offsets to the clone table associated with a YAC
    clone
    Source-an integer representing the source of the YAC
    BAC Entity
    Name is an identifier for the BAC
    clone-an array of offsets to the clone table associated with a BAC
    clone
    Source-an integer representing the source of the BAC

• Inventors
  Rigault, Philippe E.; Curtis, Anne L.; Goold, Richard D.; Hadley, David A.; Hibbert, Harold H.; Klingler, Tod M.; Lagace, Robert E.; Stuve, Laura L.; Walker, Michael G.; Wood, Michael P.;
• Assignee
  Incyte Pharmaceuticals, Inc. (Palo Alto, CA)
• Published
  Apr-24-2001
• Current US Classes:
  435/6
  702/19
  707/100
  707/104.1
  707/6
• Application #
  175738
• International Classes
  G06F 017/30
• Field of Search
  707/100 707/104 707/2 707/5 707/6-10 707/101 707/102 707/103
• Examiner
  Alam; Hosain T.
• Agent
  Squire, Sanders & Dempsey L.L.P.
• US Patent References:
  5295256
  5392428
  5577249
  5706498
  5953727
  5970500
  6023659