CN105069325B - It is a kind of that matched method is carried out to nucleic acid sequence information - Google Patents

Abstract

The present invention relates to the field of information processing, and provides a method for matching nucleic acid sequence information. The method includes the following steps: A. Perform BWT transformation on a reference sequence in a database to obtain a matching reference sequence, and store the matching reference sequence In the database; B. Space marking is performed on the matching reference sequence in the database; C. The nucleic acid sequence fragments are sequentially matched with the matching reference sequence in the database to obtain a matching nucleic acid sequence. The method for matching nucleic acid sequence information of the present invention can realize rapid matching between nucleic acid sequence information and reference sequences.

Description

A method for matching nucleic acid sequence information

This case was filed on July 08, 2012, the application number is 201210263634.7, and the title of the invention is a divisional application of "A System and Method for Matching Nucleic Acid Sequence Information".

technical field

The present invention relates to the field of information processing, more specifically, to a system and method for matching nucleic acid sequence information.

Background technique

American scientists proposed the Human Genome Project in 1985, and through the joint efforts of scientists from the United States, the United Kingdom, the French Republic, the Federal Republic of Germany, Japan and China, the "working framework map" of the human genome was completed in 2000. And in 2001 published the human genome map and preliminary analysis results. Its research content also includes creating a computer analysis management system (that is, processing the sequencing results through a computer analysis system to obtain nucleic acid sequence information), and examining related ethical, legal and social issues. After the publication of the human genome map, domestic and foreign countries began to actively invest in the drawing of the genetic maps of various biological races. By comparing the nucleic acid sequence information with the existing genome map (reference sequence), the gene expression profile, gene mutation, etc. can be matched and analyzed through transcriptomics, proteomics and other related technologies to obtain information about genes related to diseases. Matching and analyzing the nucleic acid sequence information with the genome map, and revealing the root cause of the disease, has become a highly concerned issue in the field of biochemical medicine. The global gene sequencing technology is also developing rapidly, but it is necessary to accurately and quickly analyze the vast number of sequencing results Obtaining genetic information from data has become a bottleneck in the development of current gene sequencing technology.

The system for matching nucleic acid sequence information uses a computer to match nucleic acid sequence fragments obtained by sequencing with known reference sequences, that is, one-to-one comparison, and perform subsequent analysis based on the matching results. The method for matching nucleic acid sequence information is a process of matching nucleic acid sequence information based on a system for matching nucleic acid sequence information.

In the prior art, a method for matching nucleic acid sequence information, said method comprising the steps of: A. Dividing each nucleic acid sequence fragment into at least n+1 short fragments participating in matching according to the number n of allowable mismatches , to obtain a database of short fragments; B, to establish and store a reference sequence index according to the length of the short fragments participating in the matching, to obtain a database; C, to separately match the short fragments established by each nucleic acid sequence fragment in the database, to obtain matching results. Because the reference sequence indexes are of equal length, according to the principle of probability, there are multiple identical reference sequence indexes. In this technical solution, each short segment participating in the matching is matched with the reference sequence index in turn, and the short segment needs to be matched with all the reference sequence indices respectively (short segments need to be matched with multiple identical reference sequence indices respectively), which Will greatly reduce the speed of information processing. Moreover, both the reference sequence and the nucleic acid sequence need to be segmented, which will further increase the workload of information processing, thereby further reducing the speed of information processing. In addition, the reference sequence index established by the reference sequence and the short fragments established by nucleic acid sequence segmentation will generate a large amount of information, which will increase the storage space of the information processing device.

Therefore, there is a need for a new system and method for matching nucleic acid sequence information, which can quickly match nucleic acid sequences with reference sequences.

Contents of the invention

The purpose of the present invention is to provide a system and method for matching nucleic acid sequence information, aiming at solving the problem of slow speed when matching nucleic acid sequence information with reference sequences in the prior art.

In order to achieve the purpose of the invention, a system for matching nucleic acid sequence information includes a database, a reference sequence variation unit, a marking unit and a matching unit. The database is used to store reference sequences; the reference sequence transformation unit is used to perform BWT transformation on the reference sequences in the database to obtain matching reference sequences; the marking unit is used to space the matching reference sequences in the database Marking; the matching unit is used to sequentially perform consistent matching of the nucleic acid sequence fragments with matching reference sequences in the database to obtain a matching nucleic acid sequence.

Consistent matching includes cases where mismatches are allowed and cases where mismatches are not allowed. In the case where N mismatches are allowed, at most N bases of the nucleic acid sequence fragment are inconsistent with the matching reference sequence in the database, which is called a consensus match; The complete identity of the reference sequence is called a consensus match. N is a positive integer.

Wherein, the reference sequence conversion unit includes a reference sequence matrix module and a BWT matrix module. The reference sequence matrix module is used to add an identifier to the end or front end of the reference sequence in the database, and move the reference sequence cyclically to obtain a reference sequence matrix; the BWT matrix module is used to convert the reference sequence matrix according to Sort in dictionary order to get the BWT reference sequence matrix. The reference sequence conversion unit may further include a matching reference sequence module, which is used to obtain the first column and the last column of the BWT reference sequence matrix to obtain a matching reference sequence and store them in the database.

Wherein, the marking unit is used for marking the matching reference sequences in the database at intervals according to an arithmetic sequence.

Further, the marking unit is further used for further marking the matching reference sequence in the database by using the arithmetic sequence in each arithmetic sequence interval.

In any of the above technical solutions, the matching unit is used to reverse complement the nucleic acid sequence fragments to form reverse complementary nucleic acid sequence fragments, and perform consistent matching between the reverse complementary nucleic acid sequence fragments and matching reference sequences in the database to obtain Match nucleic acid sequences.

Wherein, the matching unit uses the backtracking method to sequentially perform base substitution at the position before the position where the reverse complementary nucleic acid sequence fragment cannot be matched, and continues to perform the matching in the database from the substitution position.

In any of the above technical solutions, the system for matching nucleic acid sequence information further includes an information receiving unit; the information receiving unit is configured to obtain nucleic acid sequence fragments and reference sequences through a USB interface or an optical disc drive interface or the Internet.

In order to better realize the present invention, the present invention also includes a method for matching nucleic acid sequence information.

The method comprises the steps: A. performing BWT transformation on the reference sequences in the database to obtain matching reference sequences, and storing the matching reference sequences in the database; B. marking the matching reference sequences in the database with interval marks; C. The nucleic acid sequence fragments are sequentially matched with the matching reference sequences in the database to obtain a matching nucleic acid sequence. Wherein, the reference sequence is stored in the database, and step A and step B respectively transform the reference sequence in the database.

Consistent matching includes cases where mismatches are allowed and cases where mismatches are not allowed. In the case where N mismatches are allowed, at most N bases of the nucleic acid sequence fragment are inconsistent with the matching reference sequence in the database, which is called a consensus match; The complete identity of the reference sequence is called a consensus match. N is a positive integer.

Wherein, the step A includes: A1, adding an identifier to the end or front end of the reference sequence in the database, and moving the reference sequence cyclically to obtain a reference sequence matrix; A2, sorting the reference sequence matrix according to lexicographical order to obtain The BWT reference sequence matrix is stored in the database. Step A3 may also be included after step A2, obtaining the first column and the last column of the BWT reference sequence matrix to match the reference sequence and store it in the database.

Wherein, in the step B, the matching reference sequences in the database are spaced according to the arithmetic sequence.

Wherein, in the step B, the arithmetic sequence is used in each arithmetic sequence interval to further mark the matching reference sequence in the database.

In any of the above-mentioned technical schemes, the step C is to reverse complement the nucleic acid sequence fragments to form reverse complementary nucleic acid sequence fragments, and then carry out consistent matching between the reverse complementary nucleic acid sequence fragments and the matching reference sequences in the database to obtain Match nucleic acid sequences.

Wherein, in the step C, under the condition that mismatches are allowed, the backtracking method is used to sequentially perform base replacement at the position before the position where the reverse complementary nucleic acid sequence fragment cannot be matched, and continue to perform the matching on the database from the replacement position .

It can be seen from the above that the nucleic acid sequence fragments of the present invention do not need to be segmented, and are directly matched with the database. At the same time, the nucleic acid sequence fragments do not need to be matched one by one with all the same matching reference sequences, and only need to be matched with all the same sequences once. Yes, thereby improving the speed of information processing as a whole; in addition, the reference sequences in the database do not need to establish a reference sequence index, and the matching reference sequences in the database do not need to be marked one by one, thereby greatly reducing the storage space requirements of the system.

Description of drawings

Fig. 1 is a schematic structural diagram of a system for matching nucleic acid sequence information in an embodiment of the present invention.

Fig. 2 is a schematic structural diagram of a system for matching nucleic acid sequence information in another embodiment of the present invention.

Fig. 3 is a schematic structural diagram of a reference sequence transformation unit in an embodiment of the present invention.

Fig. 4 is a schematic structural diagram of a reference sequence transformation unit in another embodiment of the present invention.

Fig. 5 is a flowchart of a method for matching nucleic acid sequence fragments in an embodiment of the present invention.

Fig. 6 is a schematic structural diagram of a system for matching nucleic acid sequence information in another embodiment of the present invention.

Fig. 7 is a flowchart of a method for transforming a reference sequence in an embodiment of the present invention.

Fig. 8 is a flowchart of a method for matching nucleic acid sequence fragments in an embodiment of the present invention.

Fig. 9 is a schematic diagram of consensus matching of forward nucleic acid sequence fragments in an embodiment of the present invention.

Fig. 10 is a schematic diagram of consensus matching of reverse nucleic acid sequence fragments in an embodiment of the present invention.

Fig. 11 is a schematic diagram of matching nucleic acid sequence fragments in an embodiment of the present invention.

Fig. 12 is a schematic diagram of matching nucleic acid sequence fragments in an embodiment of the present invention.

Detailed ways

In order to make the object, technical solution and advantages of the present invention clearer, the present invention will be further described in detail below in conjunction with the accompanying drawings and embodiments.

For the convenience of illustrating the technical solutions of the present invention, the nucleic acid sequence fragments and reference sequences in the following examples only give short base sequences, which do not represent the true nucleic acid sequence fragments and reference sequence fragments. Generally, the nucleic acid sequence fragment length is 20 bp or more, and the reference sequence length is 2000 bp or more. Of course, this is only a general situation. There are also cases where the nucleic acid sequence fragment length is less than 20 bp and the reference sequence length is less than 2000 bp.

The nucleic acid sequence fragments of the present invention can generally be obtained by sequencing a certain species, or artificially synthesized, that is, artificial sequences. The reference sequence is a known nucleic acid sequence, which is used as a matching template. The nucleic acid sequence fragment is matched with the reference sequence, and information such as whether the sequencing is accurate can be obtained according to the matching situation. It should be noted that the nucleic acid sequence fragments in the present invention are not particularly limited, and may include sequence fragments composed of bases such as A, G, C, T or A, G, C, U, such as: ATTACGTTA, UUCCUCAAGGU, etc.

The present invention proposes a first embodiment. As shown in FIG. 1 , the system for matching nucleic acid sequence information includes a database, a reference sequence transformation unit, a marking unit and a matching unit. Details will be given below.

(1) Database 1, used to store reference sequences.

The reference sequences stored in the database may be stored inside the system or outside the system. The reference sequence is a base sequence, that is, nucleic acid sequence information. The reference sequence and the nucleic acid sequence fragment are nucleic acid sequence information of the same species. For example, the nucleic acid sequence fragment is obtained by sequencing the nucleic acid of Paramecia, and the corresponding reference sequence is the nucleic acid sequence information of Paramecia, or it can be an artificial sequence Resulting reference sequences and nucleic acid sequence fragments. There is no particular limitation on the reference sequence and nucleic acid sequence fragment, wherein the reference sequence is a known base sequence.

(2) The reference sequence transformation unit 2 is used to perform BWT transformation on the reference sequence in the database to match the reference sequence.

The BWT transformation described above is a transformation method that Mike Burrows perfected and successfully applied to actual data compression based on the transformation idea proposed by David Wheeler. This transformation is currently a research hotspot in the field of lossless compression. BWT is a reversible data transformation method that takes data blocks as the operation object.

The reference sequence changing unit performs BWT transformation on the reference sequences in the database to obtain matching reference sequences, and automatically stores the matching reference sequences in the database.

(3) Marking unit 3, used for interval marking the matched reference sequences in the database.

There is no limit to the way of marking the intervals of the matched reference sequences in the database, and regular intervals can be marked by arithmetic sequence or other sequence. The data type used by the mark can be selected according to needs, such as Int, Byte and other data types.

(4) The matching unit 4 is used to sequentially perform consistent matching of the nucleic acid sequence fragments with matching reference sequences in the database to obtain a matching nucleic acid sequence.

Consistent matching includes cases where mismatches are allowed and cases where mismatches are not allowed. In the case where N mismatches are allowed, at most N bases of the nucleic acid sequence fragment are inconsistent with the matching reference sequence in the database, which is called a consensus match; The complete identity of the reference sequence is called a consensus match. N is a positive integer.

The nucleic acid sequence fragment is a nucleic acid sequence fragment stored inside the system, or stored on a memory outside the system. The entire nucleic acid sequence fragment is directly matched with the matching reference sequence in the database or the entire nucleic acid sequence fragment is simultaneously matched with the matching reference sequence in the database. The consistent matching means that under the condition that N mismatches are allowed, at most N pieces of the entire nucleic acid sequence fragment cannot be matched with the matching reference sequence, then the entire nucleic acid sequence fragment is considered to be matched, and a match is obtained. Nucleic acid sequence fragment, otherwise, consider that this nucleic acid sequence fragment cannot be matched, and discard this nucleic acid sequence fragment. All other nucleic acid sequence fragments are subjected to consistent matching in the database in this way, and then a matched nucleic acid sequence is obtained. The matching nucleic acid sequence can be output in readable form or stored in the system. When the matched nucleic acid sequence is output, the output information may include information such as the start position and end position of each nucleic acid sequence fragment corresponding to the reference sequence, the position and number of mismatches of each nucleic acid sequence fragment, and the like.

In this embodiment, the system for matching nucleic acid sequence information described in this embodiment may include a computer and a program for matching nucleic acid sequence information on the computer. When matching nucleic acid sequence information, the reference sequence transformation unit first performs BWT transformation on the reference sequences in the database, then the marking unit performs interval marking on the reference sequences in the database through BWT transformation, and finally the matching unit sequentially places the nucleic acid sequence fragments in the database. for consistent matching. In the technical solution of this embodiment, the whole nucleic acid sequence fragments are directly matched in the database, and the same matching reference sequence is only matched once, thereby improving the matching efficiency. At the same time, the reference sequence stored in the database does not need to be segmented to establish a reference sequence index (assuming that the length of the reference sequence index is K, then in two adjacent reference sequence indexes, the last K-1 bases of the previous reference sequence index and The first K-1 bases of the latter reference sequence index are exactly the same), and interval marks are carried out, which greatly reduces the storage space compared with the prior art.

Based on the first embodiment, the present invention proposes a second embodiment. A system for matching nucleic acid sequence information of the present invention includes a computer and a program for matching nucleic acid sequence information on it. The computer may also include A program that controls the sequencer. A specific description is given below, as shown in FIG. 2 . The computer is connected with multiple sequencers, and the computer receives the sequencing data measured by the sequencer, and processes the sequencing data to obtain nucleic acid sequence fragments. Wherein, the nucleic acid sequence fragment may be a nucleic acid sequence fragment obtained by processing sequencing data obtained by sequencing with any sequencer on the market. Preferably, the nucleic acid sequence fragment may be a nucleic acid sequence fragment obtained by processing the sequencing data generated by Pstar series sequencers, MiSeq series sequencers, GS Junior/Senior sequencers and SOLID sequencers. More preferably, the nucleic acid sequence fragment can be a nucleic acid sequence fragment obtained by processing the sequencing data generated by the Pstar series sequencer. The computer is any information processing device sold on the market with information processing function and data storage function.

It should be noted that the nucleic acid sequence fragment in the computer of the present invention may be a nucleic acid sequence fragment obtained by receiving the sequencing data of the sequencer and then processed, or may be a nucleic acid sequence fragment directly stored in the computer or directly received by the computer from the outside world, There is no particular limitation on the source of the nucleic acid sequence fragment.

The reference sequence transformation unit in the above embodiment will be further described in detail below. As shown in FIG. 3 , the reference sequence transformation unit includes a reference sequence matrix module and a BWT matrix module. Each module will be described in detail below.

(1) The reference sequence matrix module 21 is used to add an identifier to the end or front end of the reference sequence in the database, and move the reference sequence cyclically to obtain a reference sequence matrix.

In order to make the working principle of the reference sequence matrix module easier to understand, an example is given below. The reference sequence is generally long, and the length is generally between several thousand to hundreds of millions, or even longer. The examples given below are just for understanding, not a real reference sequence. Assuming that the reference sequence is ACCACCTG, first add a marker at the front or end of the reference sequence. There are no special restrictions on the symbol of the marker, just to distinguish the beginning and end of the reference sequence. In this example, add the $ marker at the end to get ACCACCTG $; Then move the reference sequence circularly to obtain the reference sequence matrix. The specific results are shown in the table below.

Table 1

Table 1 is the reference sequence matrix obtained by processing the reference sequence ACCACCTG through the reference sequence matrix module. Wherein, the above-mentioned A, G, C, T are the corresponding nucleic acids in the field of biochemistry.

(2) The BWT matrix module 22 is used to sort the reference sequence matrix in lexicographical order to obtain the BWT reference sequence matrix.

In order to make the description easier to understand, the following will take the reference sequence matrix in Table 1 as an example, assuming that the $ marker is smaller than A, G, C, and T, and sort the reference sequence matrix in lexicographical order, the obtained BWT reference sequence matrix As shown in table 2.

Table 2

Wherein, the BWT reference sequence matrix is stored in the database. The dictionary order refers to sorting according to the search order A, B, C, . . . , Z of the Chinese dictionary.

In the above technical solution, the nucleic acid sequence fragments can only be matched once in the same reference sequence. The reason is that after the reference sequence is transformed by BWT, each adjacent row sequence of the BWT reference sequence matrix in the database has the largest common prefix. When matching, if the nucleic acid sequence fragment is matched with the rth row, and the length of the nucleic acid sequence fragment is m, then the largest common prefix of the rth row of the BWT reference sequence matrix is at least m, all of which can be compared. It is enough to determine the largest common prefix, and there is no need to perform consistent matching on the nucleic acid sequence fragments, that is, only one matching is required. For example, the length of the nucleic acid sequence fragment is 3, which is ACC, and the largest common prefix in the second and third rows of the BWT reference sequence matrix is 3, both of which are ACC. At this time, as long as the comparison with the common prefix is performed, the nucleic acid Matching of sequence fragments in the database. This technical solution greatly improves the efficiency of nucleic acid sequence fragment matching.

As shown in Fig. 4, the reference sequence conversion unit may further include a matching reference sequence module, which will be described in detail below. The matching reference sequence module 23 is used to obtain the first column and the last column of the BWT reference sequence matrix to match the reference sequence and store it in the database.

In order to save storage space, an auxiliary matrix is used. Taking the matrix in Table 2 as an example, the obtained matching reference sequence is shown in Table 3.

table 3

The corresponding database in Table 3 is more concise, thereby greatly reducing the storage space requirements of the database.

In order to search more quickly, an auxiliary matrix can be further used. The following continues to take the matrix in Table 2 as an example, and the obtained matching reference sequence information stored in the database is shown in Table 4.

Table 4

The third column in the table is the position of the first column in the reference sequence, and the fourth column is the first column of the reference sequence matrix. When the subsequent nucleic acid sequence fragments are matched, the nucleic acid sequence fragments in the reference sequence can be directly obtained. The position makes the database easier to use and improves the efficiency of subsequent nucleic acid sequence fragment matching.

The reference sequence conversion unit in the second embodiment processes the database, thereby making the database easier to use and more efficient in nucleic acid sequence fragment matching, which greatly saves storage space compared with the database in the prior art. The technical scheme overcomes the problems of slow sequence matching speed and large storage space in the traditional technology as a whole.

The marking unit in the second embodiment will be described in detail below. The marking unit 3 is used for marking the matching reference sequences in the database at intervals according to arithmetic progressions. Based on the above scheme, the reference sequence or matching reference sequence is marked, so that when the nucleic acid sequence fragments are matched, the position of the nucleic acid sequence fragments can be determined. The marking method of the marking unit will be specifically described below.

table 5

The marks in Table 5 are marked according to the arithmetic sequence, and the tolerance of the arithmetic sequence is not limited, and only 256 is selected for the tolerance in this embodiment. The technical scheme adopts interval marks, which greatly reduces the storage space occupied by the database. In addition, when the reference sequence or matching reference sequence is long, it is preferable to use the Int type for marking (the length of the reference sequence that can be marked is 2 ³¹ ), and when the reference sequence or matching reference sequence is short, it is preferable to use the Byte type for marking. Compared with using the LongInt type for marking, this technical solution further reduces the storage space occupied by the database.

The above marking unit will be further described in detail below. The marking unit is also used for further marking the matching reference sequence in the database by using the arithmetic sequence in each arithmetic sequence interval. In order to make the description clearer and easier to understand, further functions of the marking unit are given below on the basis of Table 4. See Table 6.

table 6

The technical solution in this embodiment can realize the specific position of the matched nucleic acid sequence fragment on the reference sequence after the nucleic acid sequence fragment is matched on the reference sequence or matching reference sequence. For example: the starting position of the nucleic acid sequence fragment matching is 274 of the reference sequence. When the reference sequence is marked only once, it is necessary to push back 18 bits from 256 to know the specific position. However, when the reference sequence or matching sequence is done After further marking, it can be known that 256+16=272, and the starting position of the matching position can be obtained by only advancing two bits backward, thus greatly improving the matching efficiency of the matching unit. Wherein, there is no special restriction on the data type marked in this solution, and it is preferably a Byte type. Compared with other data types, this preferred solution greatly reduces the storage space occupied by the database.

It should be noted that, in the above example, only two layers of marking are performed on the reference sequence or the label matching the reference sequence. The notation of is not limited to the examples given above.

The matching unit 4 in the second embodiment will be further described below. The matching unit 4 is used to reverse the nucleic acid sequence fragments to form reverse nucleic acid sequence fragments or to reverse complement nucleic acid sequence fragments to form reverse complementary nucleic acid sequence fragments, and to reverse nucleic acid sequence fragments or reverse complementary nucleic acid sequence fragments Nucleic acid sequence fragments are congruently matched to matching reference sequences in databases.

Corresponding specific embodiments will be given below for the technical schemes for consistent matching of nucleic acid sequence fragments, reverse complementary nucleic acid sequence fragments, and reverse complementary nucleic acid sequence fragments with reference sequences or matching reference sequences in the database.

Among them, we will make the following assumptions: the nucleic acid sequence fragment is ACC; the reference sequence G$CCAACTC in the database, and the matching reference sequence information in the database is shown in Table 7.

table 7

(1) Consistent matching of forward nucleic acid sequence fragments. The specific process is shown in Figure 9.

For the convenience of explanation, ①②③④⑤⑥ are marked below each column respectively. Among them, columns ① to ⑤ are matching reference sequence information in the database, and column ⑥ is nucleic acid sequence fragments. Column ① and column ② are the first column and the last column of the BWT reference sequence matrix respectively. Column ③ marks the position of the base in column ① in the reference sequence, and column ④ marks the position of the reference sequence (reference sequence The marking method of the position can be marked in a spaced way), and the fifth column is the reference sequence. In this scheme, the last position on the ACC match is 3, from the third column, find the position of 3, start from this position, find the position of base C in the first column, and then in the BWT reference sequence matrix Obtain the largest common prefix, if the largest prefix is greater than or equal to 3, then all positions of the nucleic acid sequence fragment on the reference sequence can be obtained according to the third column. In this technical solution, the nucleic acid sequence fragment only needs to be matched once with the same reference sequence in the reference sequence, and the starting positions of all reference sequences corresponding to the nucleic acid sequence fragment can be obtained, thereby greatly improving the efficiency of consistent matching of nucleic acid sequence fragments.

(2) Consistent matching of reverse nucleic acid sequence fragments.

In order to help understand the technical solution more clearly, as shown in FIG. 10 , the technical solution is described below starting from the BWT reference sequence matrix.

The above-mentioned technical scheme is explained in detail below, wherein, the first line C, CC, and ACC are the first, first two and first three positions of the reverse nucleic acid sequence fragment, and the consistent matching is performed from the first position in turn, indicated by the arrow The upper and lower positions of the pointer represent the start position and end position of the matching position respectively. The matching of each bit of the reverse nucleic acid sequence fragment is matched according to the method in the table, and the first three positions are given in the table. match. From the matching results in the above table, we can see that there are two matching positions. From the corresponding matching reference sequence information in the database, we can know that the starting position of the matching is at the first and fourth positions of the reference sequence. In this technical solution, the nucleic acid sequence fragment only needs to be matched with the same reference sequence in the reference sequence once, and the starting positions of all reference sequences corresponding to the nucleic acid sequence fragment can be obtained, thereby greatly improving the efficiency of consistent matching of nucleic acid sequence fragments .

(3) Consistent matching of reverse complementary nucleic acid sequence fragments.

An example is given below, as shown in A in Figure 11, the reverse complementary nucleic acid sequence fragment obtained by transforming the nucleic acid sequence fragment, proceed to (2) to step (3), and the specific scheme is, the reverse complementary nucleic acid of ACC The sequence fragment is GGT, and its matching process is shown in B in Figure 9 . In this technical solution, the reverse complementary nucleic acid sequence fragments are matched from the back to the bottom, and the position of the corresponding reference sequence is found in the third column. In this specific embodiment, the last position on the GGT match is 6, starting from the third column In column ③, find the position of 6. From this position, find the position of the last occurrence of the complementary base C of base G in column ①, and then obtain the largest common prefix in the BWT reference sequence matrix. If the largest If the prefix is greater than or equal to 3, all positions of the nucleic acid sequence fragment on the reference sequence can be obtained according to the third column. In this technical solution, the nucleic acid sequence fragment only needs to be matched once with the same reference sequence in the reference sequence, and the starting positions of all reference sequences corresponding to the nucleic acid sequence fragment can be obtained, thereby greatly improving the efficiency of consistent matching of nucleic acid sequence fragments.

The consistent matching described in the embodiment of this scheme includes complete matching or under the condition that each nucleic acid sequence fragment is allowed to have N mismatches, at most N mismatches cannot be matched, and the following will give a list of mismatches The specific scheme is shown in Figure 5. In the figure, when a certain base C is matched, it cannot be matched, then the previous base "C" in the base C is replaced by a base, and then matched, and the base "C" is replaced in turn After the bases "T, G, A" are still unable to match, the previous base is replaced. When the previous base "C" is replaced with the base "T", it can be Once matched, proceed to other matches. The situation of allowing mismatches is given in this technical solution. When one mismatch is allowed, at most one base in the nucleic acid sequence fragment cannot be matched in the database; when N mismatches are allowed, the nucleic acid sequence in the nucleic acid sequence fragment The fragment has at most N bases that cannot be matched in the database, that is, any N positions on the nucleic acid sequence fragment can be matched in the database after modification. This technical solution can realize the detection of gene mutations while satisfying fast matching. At the same time, the method of base replacement (that is, correcting base recognition errors) solves the problem that the nucleic acid sequence cannot be matched due to base recognition errors, thereby It provides a guarantee for the accuracy improvement of nucleic acid sequencing.

For any of the above technical solutions, the present invention proposes a third embodiment, the system for matching nucleic acid sequence information includes an information receiving unit, a database, a reference sequence conversion unit, a marking unit and a matching unit. As shown in Figure 6. In this embodiment, the database, the reference sequence transformation unit, the marking unit, and the matching unit will not be described in detail. For a specific technical solution, refer to any of the above technical solutions, and only the information receiving unit will be further described below. The information receiving unit is configured to receive nucleic acid sequence fragment information and reference sequence information. The system may include a computer, which may include a USB interface or an optical disk drive interface or an INTERNET network interface. Preferably, the information receiving unit obtains the nucleic acid sequence fragment and the reference sequence through a USB interface or an optical disk drive interface or the Internet. Wherein, the information receiving unit stores the received information, wherein the nucleic acid sequence fragment and the reference sequence are stored separately, and the matching unit can obtain the nucleic acid sequence fragment from the database storing the nucleic acid sequence fragment, and match the reference sequence fragment in the database storing the reference sequence Sequences are matched consistently to obtain matching results. The matching results can be output in a readable format, for example, including: the length of each nucleic acid sequence fragment, the number of unmatched matches for each nucleic acid sequence fragment, the matching position of the nucleic acid sequence fragment, etc. The output is only a formality , which will not be described in detail here.

Based on the first embodiment, the present invention proposes a fourth embodiment. The method for matching nucleic acid sequence information includes the following steps.

Step S1, perform BWT transformation on the reference sequence in the database to obtain a matching reference sequence, and store the matching reference sequence in the database.

The reference sequences stored in the database are reference sequences stored inside the computer or in a memory outside the computer. The reference sequence is a base sequence, that is, nucleic acid sequence information. The reference sequence and the nucleic acid sequence fragment are nucleic acid sequence information of the same species. For example, the nucleic acid sequence fragment is obtained by sequencing the nucleic acid of Paramecia, and the corresponding reference sequence is the nucleic acid sequence information of Paramecia, or it can be an artificial sequence Resulting reference sequences and nucleic acid sequence fragments. There is no particular limitation on the reference sequence and nucleic acid sequence fragment, wherein the reference sequence is a known base sequence.

The BWT transformation described above is a transformation method perfected and successfully applied to actual data compression by Mike Burrows based on the transformation idea proposed by David Wheeler. This transformation is currently a research hotspot in the field of lossless compression. BWT is a reversible data transformation method that takes data blocks as the operation object. Its core idea is to sort and transform the character matrix obtained after the string rotation. After performing BWT transformation on the reference sequences in the database, the obtained matching reference sequences are stored in the database.

Step S2, marking the matching reference sequences in the database with intervals.

There is no limit to the way of marking the intervals of the matched reference sequences in the database, and regular intervals can be marked by arithmetic sequence or other sequence. The data type used by the mark can be selected according to needs, such as Int, Byte and other data types.

Step S3, reverse complementing the nucleic acid sequence fragment to form a reverse complementary nucleic acid sequence fragment, and then performing consistent matching between the reverse complementary nucleic acid sequence fragment and the matching reference sequence in the database to obtain a matching nucleic acid sequence.

Consistent matching includes cases where mismatches are allowed and cases where mismatches are not allowed. In the case where N mismatches are allowed, at most N bases of the nucleic acid sequence fragment are inconsistent with the matching reference sequence in the database, which is called a consensus match; The complete identity of the reference sequence is called a consensus match. N is a positive integer.

The nucleic acid sequence fragment is a nucleic acid sequence fragment stored in the system, or stored in a memory outside the system. The entire nucleic acid sequence fragment is directly matched with the matching reference sequence in the database or the entire nucleic acid sequence fragment is simultaneously matched with the matching reference sequence in the database. The consistent matching means that under the condition that N mismatches are allowed, at most N bases of the entire nucleic acid sequence fragment cannot be matched with the matching reference sequence, then the entire nucleic acid sequence fragment is considered to be matched, A matching nucleic acid sequence fragment is obtained, otherwise, the nucleic acid sequence fragment is considered unmatched, and the nucleic acid sequence fragment is discarded. All other nucleic acid sequence fragments are subjected to consistent matching in the database in this way, and then a matched nucleic acid sequence is obtained. The matching nucleic acid sequence can be output in readable form or stored in a database. When the matched nucleic acid sequence is output, the output information may include information such as the starting position and the ending position of each nucleic acid sequence fragment corresponding to the reference sequence, the position and number of mismatches of each nucleic acid sequence fragment, and the like.

In the technical solution of this embodiment, the whole nucleic acid sequence fragments are directly matched in the database, and the same matching reference sequence is only matched once, thereby improving the matching efficiency. At the same time, the reference sequence stored in the database does not need to be segmented to establish a reference sequence index (assuming that the length of the reference sequence index is K, then in two adjacent reference sequence indexes, the last K-1 bases of the previous reference sequence index and The first K-1 bases of the latter reference sequence index are exactly the same), and interval marks are carried out, which greatly reduces the storage space compared with the prior art.

The above step S1 includes: S11. Add an identifier to the end or front end of the reference sequence in the database, and move the reference sequence cyclically to obtain a reference sequence matrix. S12. Sorting the reference sequence matrix in lexicographical order to obtain a BWT reference sequence matrix.

For this technical solution, an example is given. If the nucleic acid sequence segment to be matched is CCACC, the BWT reference sequence matrix is the matrix shown below.

The first line $ACCACCTG

The second line ACCACCTG$

The third line ACCTG$ACC

The fourth line CACCTG$AC

The fifth line CCACCTG$A

Line 6 CCTG$ACCA

Seventh line CTG$ACCAC

Eighth line G$ACCACCT

Line 9 TG$ACCACC

Then, when performing alignment, the first base of the nucleic acid sequence fragment is C, and it is only necessary to start the alignment from the fourth row of the BWT matrix, the second base of the nucleic acid sequence fragment and the first base of the fourth row of the BWT matrix Two positions are compared, if the second position is compared, then compare the nucleic acid sequence fragment with the base on the third position of the fourth row of the BWT matrix, ..., if the second position is not compared, then shift To the fifth row, the above-mentioned comparison method is repeated until the comparison reaches the seventh row. It should be noted that if the nucleic acid sequence fragment has only M bases, it is only necessary to compare the nth position of the nucleic acid sequence fragment in the row where the alignment of the BWT matrix is located, and only compare to the Mth position. In this technical solution, the BWT reference sequence matrix sorted in lexicographical order is a matching reference sequence. When the nucleic acid sequence fragment is compared with the matching reference sequence, when the first base of the nucleic acid sequence fragment is A, it only needs to be in the BWT The row where the first column of the reference sequence matrix is A can be compared. When the first base of the nucleic acid sequence fragment is G, C, T, only the first column of the BWT reference sequence matrix is G, C , and the row where T is located can be compared. Thereby, the comparison speed is greatly improved.

After the step S12, it may further include: S13. Obtain the first column and the last column of the BWT reference sequence matrix to match the reference sequence and store it in the database. The specific method flowchart of step S1 is shown in FIG. 7 . First, the identifier added at the end or front of the reference sequence of the reference sequence, the identifier can be any character except A, G, C, T, the character is added to distinguish the beginning and the end of the reference sequence; the length is X After adding a character, the length of the reference sequence becomes X+1; then, the reference sequence with the added identifier is cyclically moved, and the reference sequence matrix of (X+1)*(X+1) can be obtained; then, the The reference sequence matrix is sorted in lexicographical order, and the BWT reference sequence matrix is sorted according to A, B, C, D... in Chinese Pinyin. Finally, the first and last columns are extracted and stored. Preferably, the added identifier is considered the largest or smallest.

In the above technical solution, the nucleic acid sequence fragments can only be matched once in the same reference sequence. The reason is that after the reference sequence is transformed by BWT, each adjacent row sequence of the BWT reference sequence matrix in the database has the largest common prefix. When matching, if the nucleic acid sequence fragment is matched with the rth row, and the length of the nucleic acid sequence fragment is m, then the largest common prefix of the rth row of the BWT reference sequence matrix is at least m, all of which can be compared. It is enough to determine the largest common prefix, and there is no need to perform consistent matching on the nucleic acid sequence fragments, that is, only one matching is required. For example, the length of the nucleic acid sequence fragment is 3, which is ACC, and the largest common prefix in the second and third rows of the BWT reference sequence matrix is 3, both of which are ACC. At this time, as long as the comparison with the common prefix is performed, the nucleic acid Matching of sequence fragments in the database. This technical solution not only solves the problem of slow matching speed of nucleic acid sequence fragments in the traditional technology, but also solves the problem of large storage space, realizes fast matching speed of nucleic acid sequence fragments, and occupies less space for matching reference sequences.

In this embodiment, in the above step S2, the matching reference sequence in the database is spaced, and this technical solution enables the matching start position to be quickly obtained when nucleic acid sequence fragments are matched. Preferably, in the above step S2, the matching reference sequence in the database is spaced according to an arithmetic sequence, and in this technical solution, an arithmetic sequence is used for marking, thereby greatly reducing the storage space of the database. More preferably, in step S2, the matching reference sequence in the database is further marked by using the arithmetic sequence in each arithmetic sequence interval. This technical solution can not only quickly obtain the matching position of the nucleic acid sequence fragment, but also can further Reduce database storage space. In this technical scheme, when further marking, renumbering can be carried out. Compared with the marking in the preferred scheme, a data type with a smaller footprint can be used for storage. For example, the Int type is used for marking in the preferred scheme. The more preferred technology The scheme can use the Byte type for further marking.

In this embodiment, in the above step S3, it is used to reverse complement the nucleic acid sequence fragment to form a reverse complementary nucleic acid sequence fragment, and perform consistent matching between the reverse complementary nucleic acid sequence fragment and the matching reference sequence in the database to obtain a matching nucleic acid sequence. Further, in the above step S3, the backtracking method is used to sequentially perform base replacement at the position before the position where the reverse complementary nucleic acid sequence fragment cannot be matched, and continue to perform the matching on the database from the replacement position.

Based on the fourth embodiment, the present invention proposes a fifth embodiment, a flowchart of a method for matching nucleic acid sequence fragments is shown in FIG. 8 . First, match a nucleic acid sequence fragment with the matching reference sequence in the database. If the match is successful, then end the match; if the match is unsuccessful, judge whether to allow mismatch; if no mismatch is allowed, end the match ; If a mismatch is allowed, start at the position before the position that cannot be matched, perform base replacement, and then perform a match.

An example is given below, as shown in Figure 12. In this example, when the base in the nucleic acid sequence fragment is replaced, it continues to be matched with the matching reference sequence in the database. In this example, when the base A in the third position of the nucleic acid sequence is replaced with T, it is matched with The matching reference sequence in the database is completely matched, and at this time, the matching of the nucleic acid sequence fragment is completed.

In this embodiment, there is no special limit to the number of allowable mismatches. The number of allowable mismatches is determined according to the length of the nucleic acid sequence fragment. When the nucleic acid sequence fragment is longer, the number of allowable mismatches can be more. When the sequence fragment is short, the number of mismatches allowed is small. For example, 4 mismatches are allowed for a nucleic acid sequence fragment length of 50 bp, 2 mismatches are allowed for a nucleic acid sequence fragment length of 30 bp, and 10 bp mismatches are allowed for a nucleic acid sequence fragment length. 0. In this embodiment, the nucleic acid sequence fragments are matched in the reference sequence. When mismatches are not allowed, a nucleic acid sequence cannot be completely matched, and the nucleic acid sequence fragments are considered unmatched; when M mismatches are allowed, a nucleic acid sequence cannot be matched. Sequence fragments allow at most M bases to be replaced. When M positions are replaced and still cannot be matched, it is considered that the nucleic acid sequence fragment cannot be matched. Otherwise, the nucleic acid sequence is considered to be unmatched. fragment matches.

It should be noted that the typical application of the present invention is not limited to the matching of nucleic acid sequence fragments in the field of biochemical sequencing, and the method described in the present invention can also be applied in other similar information processing fields.

The above descriptions are only preferred embodiments of the present invention, and are not intended to limit the present invention. Any modifications, equivalent replacements and improvements made within the spirit and principles of the present invention should be included in the protection of the present invention. within range.

Claims (6)

1. a kind of carrying out matched method to nucleic acid sequence information, which is characterized in that the described method comprises the following steps：

A, BWT transformation is carried out to the reference sequences in database, obtains matching reference sequences, and matching reference sequences are stored in number According in library；

B, spaced markings are carried out according to arithmetic progression to the matching reference sequences in database, and in each arithmetic progression interval Arithmetic progression is recycled further to mark the matching reference sequences in database；

C, nucleic acid sequence fragments are subjected to consistency matching with the matching reference sequences in database respectively successively, obtain matching nucleic acid Sequence.

2. according to claim 1 carry out matched method to nucleic acid sequence information, which is characterized in that the step A packets It includes：

A1, by database reference sequences end or front end add identifier, and by the reference sequences loopy moving, obtain reference Sequence matrix；

A2, reference sequences matrix is sorted according to lexicographic order, obtain BWT reference sequences matrix and stored in the database.

3. according to claim 2 carry out matched method to nucleic acid sequence information, further include after the step A2：

A3, BWT reference sequences matrix first rows and last row are obtained, and stored in the database.

4. according to claim 1 carry out matched method to nucleic acid sequence information, which is characterized in that the step C is, Nucleic acid sequence fragments are reversely formed to reverse nucleic acid sequence segment, or nucleic acid sequence fragments reverse complemental is formed into reverse complemental core Then acid sequence segment joins reverse nucleic acid sequence segment or reverse complemental nucleic acid sequence fragments with the matching in database successively It examines sequence and carries out consistency matching, obtain matching nucleic acid sequence.

5. according to any one of claim 1 to 4 carry out matched method to nucleic acid sequence information, which is characterized in that The step C is nucleic acid sequence fragments reverse complemental to be formed reverse complemental nucleic acid sequence fragments, then by reverse complemental nucleic acid Sequence fragment and progress consistency matching in the matching reference sequences in database, obtain matching nucleic acid sequence.

6. according to claim 5 carry out matched method to nucleic acid sequence information, which is characterized in that in the step C, In the case where allowing mispairing, position that successively cannot be before matched position in reverse complemental nucleic acid sequence fragments using backtracking method It sets and carries out base replacement, and continue to carry out consistency matching on the database from position is replaced.