WO2010066115A1 - Method and system for lowering time complexity in short sequences assembly - Google Patents

Abstract

The invention is applicable to the technical field of gene engineering, and provides a method for lowering time complexity in short sequences assembly and a system thereof. The method comprises the following steps: receiving sequencing sequences; respectively processing base sliding cutting to the received sequencing sequences one by one to obtain short strings with constant base length and to obtain left and right connection relations of the short strings; and storing the sequence values of the obtained all short strings, left and right connection relations and connection amount as one node of a de Bruijn graph, using a hash table to store the nodes of the de Bruijn graph, the hash key is the sequence value, the hash value is the node. Because of using the de Bruijn graph and applying the hash table for storing, it makes updating the connection relation of the nodes to be equal to searching nodes and updating the connection amount of bases having left and right connections for searched nodes. Thus, the searching and adding nodes and updating the connection relations of nodes can be finished during the time of 0(1). The lowering time complexity in the short sequences assembly can be realized and the short sequences of large genome can be assembled.

Description

 Method and system for reducing time complexity of short sequence assembly process

 The invention belongs to the technical field of genetic engineering, and in particular relates to a method and system for reducing the time complexity of a short sequence assembly process. Background technique

 The short sequence generated by the new sequencing technology has two characteristics:

 1. The sequence length is short;

 2. The amount of data is large.

 In the long sequence assembly process, the commonly used software such as phrap is based on the overlap between sequences. If the application is on a short sequence, the amount of calculation is too large, and there is no practical application value. In the emerging short-sequence assembly software, short sequences are successfully processed, such as velvet based on de Bruijn graphs. However, due to limitations in memory, time, etc., these short sequence assembly software can only assemble smaller prokaryotic genomes, for large genomes, such as eukaryotic genomes, especially mammalian genomic data, due to data processing. The time complexity is high and the memory usage is large. It is difficult to assemble short sequences by the existing short sequence assembly software. Summary of the invention

 It is an object of embodiments of the present invention to provide a method for reducing the time complexity of a short sequence assembly process, which aims to solve the problem that existing short sequence assembly software cannot assemble a large genome.

 The embodiment of the present invention is implemented as a method for reducing the time complexity of a short sequence assembly process, and the method includes the following steps:

Receiving a sequencing sequence; The received sequencing sequence is slid and cut one by one to obtain a short string of a fixed base length, and the left and right connection relationships of the short string are obtained, and the left and right connection relationships include a short string sequence value and a left connection exists. The number of connections for each base and the number of connections for each of the right connections;

 And storing the obtained sequence values of the short strings, the left and right connection relationships and the number of connections thereof as a node of the de Bruijn graph, and storing the nodes of the de Bruijn graph by using a hash table, wherein the hash key For the sequence value, the hash value is the node.

 Another object of embodiments of the present invention is to provide a system for reducing the time complexity of a short sequence assembly process, the system comprising:

 a receiving unit, configured to receive a sequencing sequence;

 a sequence cutting unit, configured to separately slide the received sequencing sequence one by one to obtain a short string of a fixed base length, and obtain a left and right connection relationship of the short string, wherein the left and right connection relationships include short strings a sequence value, the number of linkages of each base in which there is a left junction, and the number of linkages of each base in which a right junction exists;

 a composition unit, configured to store the obtained sequence values of the short strings, the left and right connection relationships, and the number of connections thereof as a node of the de Bruijn graph, and store the nodes of the de Bruijn graph by using a hash table, The hash key is the sequence value, and the hash value is the node.

In the embodiment of the present invention, the short sequence of the fixed base length is obtained by slidingly cutting the received sequencing sequence one by one, and the left and right connection relationships of the short strings are obtained, and the sequence values of the obtained short strings are obtained. The left and right connection relationships and their number of connections are stored as a node of the de Bruijn graph and stored using a hash table. Since the hash table storage is used to make the update node connection relationship equal to the number of connections of the node to find and update the left and right connected bases of the found node, the search, insertion, and insertion of the node can be completed within O ( l ) time. The update of the node connection relationship, thereby reducing the time complexity in the short sequence assembly process, and thus achieving short sequence assembly of large genomes. DRAWINGS

 1 is a flowchart of an implementation of a method for reducing time complexity of a short sequence assembly process according to an embodiment of the present invention;

 2 is a schematic diagram of a node storage content according to an embodiment of the present invention;

 FIG. 3 is a structural diagram of a system for reducing the time complexity of a short sequence assembly process according to an embodiment of the present invention. detailed description

 The present invention will be further described in detail below with reference to the accompanying drawings and embodiments. It is understood that the specific embodiments described herein are merely illustrative of the invention and are not intended to limit the invention.

 In the embodiment of the present invention, the short sequence of the fixed base length is obtained by slidingly cutting the received sequencing sequence one by one, and the left and right connection relationships of the short strings are obtained, and the sequence values of the obtained short strings are obtained. The left and right connection relationships and their number of connections are stored as a node of the de Bruijn graph, and the hash table is used to store the nodes of the de Bruijn graph, wherein the hash key is a sequence value and the hash value is a node.

 FIG. 1 is a flowchart showing an implementation process of a method for reducing time complexity of a short sequence assembly process according to an embodiment of the present invention, which is described in detail as follows:

 In step S101, receiving a sequencing sequence;

 In step S102, the received sequencing sequence is slid and cut one by one to obtain a short length (kmer) of a fixed length, and a left and right connection relationship of the short string is obtained, and the left and right connection relationships include short sequence values. The number of connections of each base in which there is a left connection and the number of connections of each base in which a right connection exists;

In step S103, the obtained sequence values of the short strings, the left and right connection relationships and the number of connections thereof are stored as a node of the de Bruijn graph, and the hash table is used to store de Each node of the Briiijn graph, where the hash key is a sequence value and the hash value is a node.

 In the embodiment of the present invention, the sequencing sequence has a base length of 25 - 75 and is cut into short strings of a fixed length of 21 - 31. Of course, the length of the short string obtained by the cutting is smaller than the length of the sequence, and the length can be set according to the length of the sequencing sequence and the actual situation. Each node in the de Bruijn diagram uses the corresponding bits to store its sequence value, the number of connections for each base with left joins, and the number of connections for each base with right joins. Here, each node on the de B ijn map is stored in 16 bytes, and its storage format is as follows:

 [ seq: 64, left links: 24, right- links: 24, ...];

Where seq stores the sequence value of the short string, the sequence value is calculated by using 2 bits to store a nucleotide sequence, A is represented by 00, C is represented by 01, T is represented by 10, G is represented by 11, and the sequence is encoded to generate a The 64-bit integer value, and considering the short string of even length, its complementary short string may be itself, for example, the short string GATC's complementary short string is GATC itself. In order to prevent such confusion, the lengths of the short strings are all odd. Due to the limitation of the data structure in the embodiment of the present invention, the length of the short string is not more than 31; the leftjinks uses 24 bits to store the left connection relationship and the number, and divides the 24 bits into 4 6-bit, ie A: 6, T: 6, G: 6, C: 6, respectively, using 6 bits to store the number of connections to the base A, T, G or C with the left link of the short string, each The number of connections is in the range [0, 63]; right-link uses 24 bits to store its right connection and number, and divides 24 bits into 4 6 bits, ie A: 6, T: 6, G: 6, C: 6, respectively, the number of connections of A, T, G or C with the right connection of the short string is stored by 6 bits, and the number of each connection is in the range of [0, 63]; the following 8 bits can be used. For storing other values, for example, the delete flag closed may be stored to identify whether the short string is deleted; the use mark in one may also be stored to identify whether the short string has been used, and other identifiers may also be stored. Thus, the connection relationship of each node in the de Bmijii diagram can be constructed according to the short string sequence value stored in the node, the number of connections of each base having the left connection, and the number of connections of each base having the right connection. For example, the short-chain A is AAAAAAAA, the number of connections of the right-connected T is 19, and the short-chain B of the right-connected base T is AAAAAAAT, which is equal to the short-chain 曱 left-shifting one base and adding the base T connected thereto. And there are 19 short strings B connected to the short string A, and the storage contents of the number of connections in the node storing the right port are as shown in FIG. 2 .

 The above step S103 is specifically:

 Step 1. Query whether the corresponding node exists in the stored node according to the obtained sequence value of the short string;

 Step 2. If no corresponding node is queried, add a node;

 Step 3. If the corresponding node is queried, the connection relationship of the corresponding node is updated. In the embodiment of the present invention, each node of the de Bruijn graph is stored using a hash table, the hash key is a sequence value, and the hash value is a node. For example, take a short string of AAAAAAAA, its sequence value is 0x0000, and use its sequence value 0x0000 as a key to query whether the corresponding node exists in the hash table. If no corresponding node is queried, add the node to the hash table. The seq of the value is the sequence value of the short string 0x0000, and the number of connections of the corresponding left and right connected bases in the node is set to 1 according to the short string adjacent to the short string; if the query already has a corresponding The node updates the connection relationship of the corresponding node, that is, updates the number of connections of the corresponding left and right connected bases in the node according to the short string adjacent to the short string, and the number of corresponding connections of the bases connected to the short string plus 1. When finished, perform step 1 to find the next short string until all short strings are found.

In the embodiment of the present invention, the hash node can be used to complete the lookup node, the insert node (ie, the storage node), and the update node connection relationship in the time of O(1). Updating the node connection relationship is equivalent to finding the node and updating the number of connections of the left and right connected bases of the found node, so the time complexity is still O ( l ). The embodiment of the present invention converts the steps that originally required multiple logical processes into one step, so that the computer completes the search, insert, and update connection relationship in the operation of identifying the step of storing the content of the node. The three steps, while the time complexity is still O ( l ), thus saving the time for the computer to make logical judgments, improving the internal performance of the computer during the short sequence assembly process, thus providing for the realization of short sequence assembly of large genomes.

In order to reduce the memory space required for storing nodes in the de Bruijn graph, as a preferred embodiment of the present invention, only one node in the de Bruijn graph can be used to store two complementary short strings, and the sequence values of the nodes are complementary to two short A smaller sequence value in the string. If the sequence value of a short string is smaller than the sequence value of its complementary short string, the node in the de Bruijn graph stores the sequence value of the short string, and seq stores the sequence value of the short string, and the number of corresponding connections to the left connected base. Update to left-links, the number of corresponding connections to its right-connected base is updated to right-links; if the sequence value of a short string is greater than the sequence value of its complementary short-string, the node in the de Bruijn graph stores its complementary short string The sequence value, seq stores the sequence value of its complementary short string, the number of corresponding connections to its right-linked base is updated to leftjinks, and the number of corresponding connections to its left-linked base is updated to ri _g M-links. When working with diagrams, you can use an additional variable in the program to mark which of the two short strings we are using. Moreover, when traversing along the graph, only the program needs to maintain one such variable, and the positive direction of all nodes in the path can be correctly obtained.

 In order to speed up the construction of the map, as another preferred embodiment of the present invention, multiple hash tables are used to uniquely store different nodes in the de Bruijn graph, and different threads are used to access different hash tables.

 In the embodiment of the present invention, eight hash tables are created, a certain number of original sequences are read, and eight threads are used to perform multi-thread cutting and short-string complementation on the original sequence to be read. After the data collection is completed, the data is collected. Eight threads are inserted into the update node, where each thread only processes the sequence value of the fixed prefix. Each hash table stores a sequence value of the specified prefix, and a hash table has only one thread access to guarantee the uniqueness of the node storage.

By using the compressed data structure provided by the embodiment of the present invention, node information (ie, sequence value) and node connection information (ie, edges) can be combined together from one section. The value of the point gives the sequence value of the short string on the node, the short string adjacent to the short string, and the number thereof.

 Of course, other structures can also be used to store the nodes of the de Bruijn graph, for example, can be stored in a tree structure, and the hash table is used to store each node in memory and usage and stored in a tree structure, but using a hash table storage. Each node is significantly better than the tree's storage structure in terms of access and modification speed.

 The African human genome resequencing data was selected. After error correction processing, the sequence data amount was 254 G bases, and after cutting into a fixed length short string of 25 base length, the total number of short strings (including the forward and reverse sequences) was 7G. The method provided by the embodiment of the present invention constructs a de Bruijn graph, and the maximum memory usage value is 110G, which consumes 23 CPU hours, wherein the CPU parameter is Quad-Core AMD Opteron(tm) Processor 8356 2.2GHZ.

 It will be understood by those skilled in the art that all or part of the steps of the foregoing embodiments may be implemented by a program to instruct related hardware, and the program may be stored in a computer readable storage medium. The storage medium, such as ROM/RAM, disk, CD, etc., is used to perform the following steps:

 1. Receiving a sequencing sequence;

 2. The received sequencing sequence is slid and cut one by one to obtain a short string of fixed base length, and the left and right connection relationships of the short strings are obtained, and the left and right connection relationships include short string sequence values and presence of left connections. The number of connections of each base and the number of connections of each base in the right junction;

 3. Store the sequence values of the short strings, the left and right connection relationships and their number of connections as a node of the de Bruijn graph, and use the hash table to store the nodes of the de Bruijn graph, where the hash key is the sequence value. , the hash value is a node.

FIG. 3 is a diagram showing the structure of a system for reducing the time complexity of a short sequence assembly process according to an embodiment of the present invention. For the convenience of description, only the embodiments related to the embodiment of the present invention are shown. section.

 The system can be used in short sequence assembly, where:

 The receiving unit 301 receives the sequencing sequence.

 The sequence cutting unit 302 respectively slid and cuts the received sequencing sequence by a base to obtain a short string of a fixed base length, and obtains a left-right connection relationship of the short strings. The actual manner is as described above, and will not be described again.

 The composition unit 303 stores the obtained sequence values of the short strings, the left and right connection relationships and the number of connections thereof as a node of the de Bruijn graph, and uses a hash table to store each node of the de Bruijn graph, wherein the hash key is The sequence value, the hash value is the node. In the embodiment of the present invention, the composition unit 303 uses the corresponding bit in the node of the de Bruijn diagram to store its sequence value, the number of connections of each base in which there is a left connection, and the number of connections in which each base of the right connection exists.

 The composition unit 303 includes:

 The query module 3031 queries, among the stored nodes, whether the corresponding node has been stored according to the obtained sequence value of the short string.

 The node adding module 3032 adds a node when the query module 3031 does not query the corresponding node, and the implementation manner is as described above, and details are not described herein.

 The connection update module 3033, when the query module 3031 queries the corresponding node, updates the connection relationship of the corresponding node, and the implementation manner thereof is as described above, and details are not described herein again.

 In order to reduce the space required for storing nodes in the de Bruijn diagram, as a preferred embodiment of the present invention, the composition unit 303 uses a node in the de Bruijn diagram to store complementary two short strings, and the sequence values of the nodes are taken in two complementary short strings. The smaller sequence values are implemented as described above and will not be described again.

In order to speed up the construction of the map, as another preferred embodiment of the present invention, the composition unit 303 uniquely stores different nodes in the de Bruijn map using a plurality of hash tables, and uses different threads to access different hash tables. In the embodiment of the present invention, the short sequence of the fixed base length is obtained by slidingly cutting the received sequencing sequence one by one, and the left and right connection relationships of the short strings are obtained, and the sequence values of the obtained short strings are obtained. The left and right connection relationships and their number of connections are stored as a node of the de Bruijii diagram and stored using a hash table. Since the composition mode of the embodiment of the present invention is used and stored by using a hash table, the update node connection relationship is equivalent to the number of connections of the left and right connected bases of the node searched and updated by the node, and thus at O ( l ) The search, insertion and node connection relationship of the node can be updated in time, thereby reducing the time complexity in the short sequence assembly process and realizing the short sequence assembly of the large genome.

 The above is only the preferred embodiment of the present invention, and is not intended to limit the present invention. Any modifications, equivalent substitutions and improvements made within the spirit and principles of the present invention should be included in the protection of the present invention. Within the scope.

Claims

A method of reducing the time complexity of a short sequence assembly process, the method comprising the steps of:  Receiving a sequencing sequence;  The received sequencing sequence is slid and cut one by one to obtain a short string of a fixed base length, and the left and right connection relationships of the short string are obtained, and the left and right connection relationships include a short string sequence value and a left connection exists. The number of connections of each base and the number of connections of each base in the right junction;  And storing the obtained sequence values of the short strings, the left and right connection relationships and the number of connections thereof as a node of the de Bruijn graph, and storing the nodes of the de Bruijn graph by using a hash table, where the hash key is The sequence value, the hash value is the node.  2. The method according to claim 1, wherein the node of the de Bruijn graph stores a sequence value of the short string, a number of connections of each base having a left connection, and a presence of a right connection using a corresponding bit. The number of base connections.  The method according to claim 1, wherein the step of storing the obtained sequence values of the short strings, the left and right connection relationships, and the number of connections thereof as a node of the de Bruijn graph is specifically:  Querying, according to the obtained sequence value of the short string, whether the corresponding node exists in the stored node;  Add a node if no corresponding node is queried;  If the corresponding node is queried, the connection relationship of the corresponding node is updated.  4. The method according to claim 1, wherein two nodes of the de Bruijn graph store complementary two short strings. 5. The method of claim 1 wherein a plurality of hash tables are employed Uniquely store the different nodes of the de Bruijn graph and access different hash tables with different threads.  6. A system for reducing the time complexity of a short sequence assembly process, the system comprising:  a receiving unit, configured to receive a sequencing sequence;  a sequence cutting unit, configured to respectively slide the received sequencing sequence one by one to obtain a short string of a fixed base length, and obtain a left and right connection relationship of the short string, wherein the left and right connection relationships include short strings a sequence value, the number of linkages of each base in which there is a left junction, and the number of linkages of each base in which a right junction exists;  a composition unit, configured to store the obtained sequence values of the short strings, the left and right connection relationships and the number of connections thereof as a node of the de Bruijn graph, and store the different nodes in the de Bruijn graph by using a hash table Where the hash key is the sequence value and the hash value is the node.  7. The system according to claim 6, wherein the composition unit stores a sequence value of the short string, a number of connections of each base having a left connection, and a presence using a corresponding bit in a node of the de Bruijn diagram. The number of connections for each base connected to the right.  8. The system of claim 7, wherein the composition unit comprises:  a query module, configured to query, according to the obtained sequence value of the short string, whether the corresponding node is already stored in the stored node;  a node adding module, configured to add a node when the query module does not query the corresponding node;  And a connection update module, configured to update a connection relationship of the corresponding node when the query module queries the corresponding node.