CN113782097B - Anchor point screening method and device based on bloom filter and computer equipment - Google Patents

Abstract

The present application relates to a method, apparatus and computer equipment for anchor point screening based on Bloom filter. The method includes: selecting a query sequence and a fragment of the reference sequence between the two anchor points as the query sequence fragment and the reference sequence fragment according to the pre-located anchor points, and respectively selecting the reference sequence fragment and the query sequence fragment according to the preset length. Generate multiple consecutive overlapping sub-segments, build indexes through multiple preset hash functions, map the reference sequence sub-segments to the bit vector of the Bloom filter, and then query according to the index, when the query sequence sub-segment is in the reference sequence If it does not exist in the query sequence sub-segment, it is judged that the query sequence sub-segment has not passed the screening; all the query sequence sub-segments in the query sequence fragment are traversed, the total number of the query sequence sub-segments that have not passed the screening is counted, and when it is greater than the preset threshold, the left anchor point is removed; Iterates through all anchors until the anchor filtering is complete. The present invention can improve the accuracy and speed of DNA sequence alignment.

Description

An anchor point screening method, device and computer equipment based on Bloom filter

technical field

The present application relates to the field of computer technology, in particular to a method, device and computer equipment for long-read DNA sequence alignment anchor point screening based on Bloom filter.

Background technique

The third-generation sequencing is a single-molecule detection technology that does not need to amplify the template, avoiding the base preference caused by the polymerase chain reaction. Moreover, the read length of the third-generation sequencing is longer, and it can find information such as genome repeats and structural variation that cannot be found by the second-generation sequencing. New breakthroughs have been made in the fields of genome assembly, structural variation detection, and genome resequencing.

Sequence alignment is a basic and important link in sequencing data analysis, and the result of the alignment is the premise of other steps. Different from the alignment algorithms for second-generation short-read sequences, achieving fast and accurate alignment of third-generation long-read sequences faces challenges in terms of longer read lengths and higher sequencing error rates. In response to this problem, most of the three generations of long-read sequence alignments use a heuristic method, namely "seed-expansion", the idea is to first select some short fragments from the reads and the reference genome as seeds; Point positioning, the comparison range is narrowed from the entire genome to some candidate regions; finally, the dynamic programming method is used to perform base comparisons on the candidate regions, refine the comparison results, and realize extended verification. Therefore, the sequence alignment algorithm mainly includes three steps: seed generation, anchor location and base alignment.

Due to sequencing errors and the local homology of the genome itself, the existing alignment tools will locate some wrong anchors during global positioning, and aligning fragments between these wrong anchors will produce suboptimal results or even wrong result. Moreover, these wrong anchor points also require extended verification, which will bring a lot of useless calculations, which will not only affect the comparison accuracy, but also reduce the speed.

SUMMARY OF THE INVENTION

Based on this, it is necessary to provide a method, device, computer equipment and storage medium for long-read DNA sequence alignment anchor screening based on Bloom filter capable of eliminating false anchors.

An anchor point screening method based on Bloom filter, the method comprises:

Obtain the query sequence to be compared, the reference sequence and multiple anchor points obtained by pre-positioning; the query sequence is a long-read DNA sequence;

Select the fragment of the query sequence between the first anchor point and the second anchor point as the query sequence fragment, and select the fragment of the reference sequence between the first anchor point and the second anchor point as the reference sequence fragment;

generating a plurality of consecutive overlapping reference sequence sub-segments according to the reference sequence fragment according to a preset length, and generating a plurality of consecutive overlapping query sequence sub-segments according to the query sequence fragment according to the preset length;

Indexing is established by a plurality of preset hash functions, and the sub-segment of the reference sequence is mapped to the bit vector of the Bloom filter;

Query whether the sub-segment of the query sequence exists in the reference sequence according to the index, and when the sub-segment of the query sequence does not exist in the reference sequence, determine that the sub-segment of the query sequence has not passed the screening;

Traverse all the query sequence sub-segments in the query sequence fragment, and count the cumulative value of the query sequence sub-fragments that have not passed the screening, and when the cumulative value is greater than a preset threshold, remove the first anchor point;

Iterates through all anchors until filtering of all said anchors is complete.

In one of the embodiments, the method further includes: generating a plurality of consecutive overlapping reference sequence sub-segments according to the reference sequence segment according to a preset length, and generating a plurality of consecutive overlapping reference sequence sub-segments according to the query sequence segment according to the preset length. Before the sub-segment of the query sequence, the same parts at both ends of the query sequence segment and the reference sequence segment are deleted, and the query sequence segment and the reference sequence segment are updated.

In one of the embodiments, the method further includes: before deleting the same parts at both ends of the query sequence segment and the reference sequence segment, and updating the query sequence segment and the reference sequence segment, updating the query sequence segment The fragment is aligned with the reference sequence fragment; extends from the two ends of the sequence to the middle, and aligns base by base; obtains the same part at both ends of the query sequence fragment and the reference sequence fragment.

In one embodiment, it further includes: if the two bases that are being aligned between the query sequence fragment and the reference sequence fragment are the same, continue to extend to the next base; if the query sequence fragment and the reference sequence fragment are the same The two bases at which the sequence fragment is being aligned are different and the extension is stopped.

In one of the embodiments, the method further includes: obtaining multiple hash values of each reference sequence sub-segment according to a plurality of preset hash functions; The value at the corresponding position of the vector is set to 1.

In one of the embodiments, the method further includes: obtaining multiple hash values of each sub-segment of the query sequence according to a plurality of preset hash functions; filtering the Bloom filter according to the hash values of the sub-segments of the query sequence If the corresponding positions of the multiple hash values of the sub-segment of the query sequence are all 1, it is judged that the sub-segment of the query sequence has passed the screening; if not all of them are 1, it is judged that the The subfragments of the query sequence did not pass the screening.

In one of the embodiments, the method further includes: using the second anchor point as the first anchor point, and using the anchor point adjacent to the right side of the second anchor point as the second anchor point, and performing the next round of anchor points filter.

An anchor point screening device based on a Bloom filter, the device comprising:

a sequence acquisition module, used to acquire a query sequence to be compared, a reference sequence and a plurality of anchor points obtained by pre-positioning; the query sequence is a long-read DNA sequence;

A fragment selection module is used to select a fragment of the query sequence between the first anchor point and the second anchor point as a query sequence fragment, and select the reference sequence between the first anchor point and the second anchor point. The fragments between are reference sequence fragments;

a sub-segment generation module, configured to generate a plurality of consecutive overlapping reference sequence sub-segments according to the reference sequence segment according to a preset length, and generate a plurality of consecutive overlapping query sequence sub-segments according to the query sequence segment according to the preset length ;

an index establishment module, for establishing an index through a plurality of preset hash functions, and mapping the reference sequence sub-segment into the bit vector of the Bloom filter;

A query module, configured to query whether the sub-segment of the query sequence exists in the reference sequence according to the index, and when the sub-segment of the query sequence does not exist in the reference sequence, determine that the sub-segment of the query sequence has failed filter;

An anchor point elimination module is used to traverse all query sequence sub-segments in the query sequence segment, and count the cumulative value of the query sequence sub-segments that have not passed the screening, and when the cumulative value is greater than a preset threshold, remove the first anchor;

The traversal module is used to traverse all the anchors until the screening of all the anchors is completed.

A computer device includes a memory and a processor, the memory stores a computer program, and the processor implements the following steps when executing the computer program:

Obtain the query sequence to be compared, the reference sequence and multiple anchor points obtained by pre-positioning; the query sequence is a long-read DNA sequence;

Select the fragment of the query sequence between the first anchor point and the second anchor point as the query sequence fragment, and select the fragment of the reference sequence between the first anchor point and the second anchor point as the reference sequence fragment;

generating a plurality of consecutive overlapping reference sequence sub-segments according to the reference sequence fragment according to a preset length, and generating a plurality of consecutive overlapping query sequence sub-segments according to the query sequence fragment according to the preset length;

Indexing is established by a plurality of preset hash functions, and the sub-segment of the reference sequence is mapped to the bit vector of the Bloom filter;

Query whether the sub-segment of the query sequence exists in the reference sequence according to the index, and when the sub-segment of the query sequence does not exist in the reference sequence, determine that the sub-segment of the query sequence has not passed the screening;

Traverse all the query sequence sub-segments in the query sequence fragment, and count the cumulative value of the query sequence sub-fragments that have not passed the screening, and when the cumulative value is greater than a preset threshold, remove the first anchor point;

Iterates through all anchors until filtering of all said anchors is complete.

A computer-readable storage medium on which a computer program is stored, and when the computer program is executed by a processor, the following steps are implemented:

Obtain the query sequence to be compared, the reference sequence and multiple anchor points obtained by pre-positioning; the query sequence is a long-read DNA sequence;

Select the fragment of the query sequence between the first anchor point and the second anchor point as the query sequence fragment, and select the fragment of the reference sequence between the first anchor point and the second anchor point as the reference sequence fragment;

generating a plurality of consecutive overlapping reference sequence sub-segments according to the reference sequence fragment according to a preset length, and generating a plurality of consecutive overlapping query sequence sub-segments according to the query sequence fragment according to the preset length;

Indexing is established by a plurality of preset hash functions, and the sub-segment of the reference sequence is mapped to the bit vector of the Bloom filter;

Query whether the sub-segment of the query sequence exists in the reference sequence according to the index, and when the sub-segment of the query sequence does not exist in the reference sequence, determine that the sub-segment of the query sequence has not passed the screening;

Traverse all the query sequence sub-segments in the query sequence fragment, and count the cumulative value of the query sequence sub-fragments that have not passed the screening, and when the cumulative value is greater than a preset threshold, remove the first anchor point;

Iterates through all anchors until filtering of all said anchors is complete.

The above-mentioned anchor point screening method, device, computer equipment and storage medium based on Bloom filter, according to the pre-positioned anchor point, select the fragment of the query sequence between the first anchor point and the second anchor point as the query sequence fragment, A segment of the reference sequence between the first anchor point and the second anchor point is selected as a reference sequence segment, and a plurality of consecutive overlapping sub-segments are generated for the reference sequence segment and the query sequence segment according to a preset length, and the preset multiple sub-segments are generated. The hash function builds an index, maps the sub-segment of the reference sequence to the bit vector of the Bloom filter, and then queries whether there is a sub-segment of the query sequence in the reference sequence according to the index. When the sub-segment of the query sequence does not exist in the reference sequence, judge The query sequence sub-segment fails the screening; traverses all the query sequence sub-segments in the query sequence fragment, and counts the cumulative value of the query sequence sub-segments that do not pass the screening. When the cumulative value is greater than the preset threshold, remove the first anchor point; traverse all the query sequence sub-segments Anchors until all anchors are filtered. The invention realizes the screening of DNA sequence alignment anchor points through Bloom filter, eliminates wrong anchor points, and can improve the accuracy and speed of DNA sequence alignment.

Description of drawings

1 is a schematic flowchart of an anchor point screening method based on a Bloom filter in one embodiment;

Figure 2 is a schematic diagram of obtaining subfragments from sequence fragments in one embodiment;

3 is a schematic flowchart of an anchor point screening method based on a Bloom filter in another embodiment;

4 is a structural block diagram of an apparatus for anchor point screening based on a Bloom filter in one embodiment;

FIG. 5 is a diagram of the internal structure of a computer device in one embodiment.

Detailed ways

In order to make the purpose, technical solutions and advantages of the present application more clearly understood, the present application will be described in further detail below with reference to the accompanying drawings and embodiments. It should be understood that the specific embodiments described herein are only used to explain the present application, but not to limit the present application.

The Bloom filter-based anchor point screening method provided in this application can be applied to the following application environments. The terminal executes an anchor point screening method based on a Bloom filter, selects a fragment of the query sequence between the first anchor point and the second anchor point as the query sequence fragment according to the pre-located anchor points, and selects the reference sequence The segment between the first anchor point and the second anchor point is the reference sequence segment, and the reference sequence segment and the query sequence segment are respectively generated according to preset lengths. Multiple consecutive overlapping sub-segments, through preset multiple hash functions Build an index, map the reference sequence sub-segment to the bit vector of the Bloom filter, and then query whether the query sequence sub-segment exists in the reference sequence according to the index. When the query sequence sub-segment does not exist in the reference sequence, determine the query sequence sub-segment. The fragment fails the screening; it traverses all the sub-fragments of the query sequence in the query sequence fragment, and counts the cumulative value of the sub-fragments of the query sequence that do not pass the screening. When the cumulative value is greater than the preset threshold, the first anchor point is eliminated. Wherein, the terminal may be, but not limited to, various personal computers, notebook computers and tablet computers.

In one embodiment, as shown in FIG. 1 , a Bloom filter-based anchor point screening method is provided, comprising the following steps:

Step 102: Obtain the query sequence to be compared, the reference sequence, and multiple anchor points obtained by pre-positioning.

The query sequence is a long-read DNA sequence. The three-generation long-read sequence alignment mostly adopts the heuristic method, namely "seed-expansion". The long-read DNA sequence alignment algorithm mainly includes three steps: seed generation, anchor point positioning and base alignment.

Step 104 , a segment of the query sequence between the first anchor point and the second anchor point is selected as a query sequence segment, and a segment of the reference sequence between the first anchor point and the second anchor point is selected as a reference sequence segment.

Align the sequences between the anchors at the interval of the anchors. When performing anchor point screening in the present invention, anchor points are also used as intervals, and anchor point screening is performed by the sequence between the anchor points.

Step 106: Generate a plurality of continuously overlapping reference sequence sub-segments according to the reference sequence segment according to a preset length, and generate a plurality of consecutively overlapping query sequence sub-segments according to the query sequence segment according to the preset length.

As shown in Figure 2, the sub-segments overlap continuously, covering the entire sequence segment.

In step 108, indexes are established by using a plurality of preset hash functions, and the reference sequence sub-segments are mapped to the bit vector of the Bloom filter.

A bloom filter is a bit vector. To map a value to a bloom filter, multiple hash values need to be generated using multiple different hash functions, and the bit position pointed to by each generated hash value is 1 .

Step 110 , according to the index to query whether the sub-segment of the query sequence exists in the reference sequence, and when the sub-segment of the query sequence does not exist in the reference sequence, it is determined that the sub-segment of the query sequence has not passed the screening.

When the sub-segment of the query sequence does not exist in the reference sequence, it means that the query sequence segment has a sequence segment that does not exist in the reference sequence segment, that is, there is a difference between the query sequence segment and the reference sequence segment.

Step 112 , traverse all the query sequence sub-segments in the query sequence segment, and count the accumulated values of the query sequence sub-segments that have not passed the screening. When the accumulated value is greater than a preset threshold, the first anchor point is eliminated.

When a considerable number of sub-segments in the sub-segment of the query sequence do not exist in the reference sequence segment, it indicates that the query sequence segment is quite different from the reference sequence segment, and it can be judged that the anchor point is the wrong anchor point.

Step 114, traverse all anchor points until all anchor points are screened.

In the above-mentioned anchor point screening method based on Bloom filter, according to the pre-positioned anchor points, the fragment of the query sequence between the first anchor point and the second anchor point is selected as the query sequence fragment, and the reference sequence is selected at the first anchor point. The segment between the point and the second anchor point is the reference sequence segment, and the reference sequence segment and the query sequence segment are respectively generated according to preset lengths. Multiple consecutive overlapping sub-segments are indexed by multiple preset hash functions, and the The reference sequence sub-segment is mapped to the bit vector of the Bloom filter, and then the query sequence sub-segment is queried according to the index. If the query sequence sub-segment does not exist in the reference sequence, it is judged that the query sequence sub-segment has not passed the screening ; traverse all query sequence sub-segments in the query sequence segment, and count the cumulative value of the query sequence sub-segments that have not passed the screening, when the cumulative value is greater than the preset threshold, remove the first anchor point; traverse all anchor points until all anchor points are completed point filter. The invention realizes the screening of DNA sequence alignment anchor points through Bloom filter, eliminates wrong anchor points, and can improve the accuracy and speed of DNA sequence alignment.

In one embodiment, the method further includes: before generating a plurality of consecutive overlapping reference sequence sub-segments according to the reference sequence segment according to a preset length, and before generating a plurality of consecutive overlapping query sequence sub-segments according to the query sequence segment according to the preset length, Delete the same parts at both ends of the query sequence fragment and the reference sequence fragment, and update the query sequence fragment and the reference sequence fragment.

Deleting the same parts at both ends of the query sequence fragment and the reference sequence fragment, and updating the query sequence fragment and the reference sequence fragment, can reduce redundant data.

In one of the embodiments, the method further includes: aligning the query sequence segment and the reference sequence segment before deleting the same parts at both ends of the query sequence segment and the reference sequence segment and updating the query sequence segment and the reference sequence segment; The ends are extended to the middle, and the base-by-base alignment is carried out; the identical parts at both ends of the query sequence fragment and the reference sequence fragment are obtained.

In one embodiment, it also includes: if the two bases that are being aligned between the query sequence fragment and the reference sequence fragment are the same, continue to extend to the next base; if the query sequence fragment and the reference sequence fragment are aligning two bases The bases are different and the extension is stopped.

In one of the embodiments, the method further includes: obtaining multiple hash values of each reference sequence sub-segment according to a plurality of preset hash functions; corresponding to the Bloom filter bit vector according to the hash values of the reference sequence sub-segments The value of position is set to 1.

In one of the embodiments, the method further includes: obtaining multiple hash values of each sub-segment of the query sequence according to a plurality of preset hash functions; The corresponding position is queried; if the values of the corresponding positions of the multiple hash values of the query sequence sub-segment are all 1, the query sequence sub-segment is judged to pass the screening; if not all are 1, the query sequence sub-segment is judged to have not passed the screening.

In one of the embodiments, the method further includes: taking the second anchor point as the first anchor point, and taking the adjacent anchor point on the right side of the second anchor point as the second anchor point, and performing the next round of anchor point screening.

It should be understood that although the various steps in the flowchart of FIG. 1 are shown in sequence according to the arrows, these steps are not necessarily executed in the sequence shown by the arrows. Unless explicitly stated herein, the execution of these steps is not strictly limited to the order, and these steps may be performed in other orders. Moreover, at least a part of the steps in FIG. 1 may include multiple sub-steps or multiple stages. These sub-steps or stages are not necessarily executed and completed at the same time, but may be executed at different times. The execution of these sub-steps or stages The sequence is also not necessarily sequential, but may be performed alternately or alternately with other steps or sub-steps of other steps or at least a portion of a phase.

In a specific embodiment, as shown in FIG. 3 , a method for anchor point screening based on a Bloom filter is provided, including:

Step 1: Align the query sequence query and the reference sequence target by anchor points, where the number of anchor points is N;

Step 2: Select the fragment between the first anchor point P1 on the left and the second anchor point P2 on the left, where the fragment of the query sequence is qseq1, and the fragment of the reference sequence is tseq1;

Step 3: Remove the same parts at both ends of the query sequence fragment qseq1 and the reference sequence fragment tseq1;

Step 4: Create an index for the remaining part of the reference sequence fragment tseq1;

Step 5: Query the remaining part of qseq1 in the index to determine whether to retain the left anchor point P1;

Step 6: Complete the screening of anchor point P1;

Step 7: Go back to Step 2, and process the fragments of the anchor point P2 and the anchor point P3 until the N anchor points are screened.

More specific steps are:

Step 1: Align the query sequence query and the reference sequence target by anchor points, where the number of anchor points is N;

Step 2: Select the fragment between the first anchor point P1 on the left and the second anchor point P2 on the left, where the fragment of the query sequence is qseq1, and the fragment of the reference sequence is tseq1;

Step 3: Remove the same parts at both ends of the query sequence fragment qseq1 and the reference sequence fragment tseq1;

Step 3.1: After aligning the two ends of qseq1 and tseq1, extend from the two ends to the middle, and align base by base;

Step 3.1.1: If the two bases are the same, continue to extend to the next base;

Step 3.1.2: If the two bases are different, stop the extension;

Step 3.2: Remove the same parts at both ends;

Step 4: Create an index for the remaining part of the reference sequence fragment tseq1;

Step 4.1: Generate a continuous overlapping fragment q-mer of length q for the remaining part of the reference sequence fragment tseq1;

Step 4.2: Use the hash function to calculate the hash value of q-mer;

Step 4.3: Insert the calculated hash value of q-mer into the bit vector of the Bloom filter;

Repeat steps 4.1 to 4.3 until all q-mers are processed;

Step 5: Query the remaining part of qseq1 in the index to determine whether to retain the left anchor point P1;

Step 5.1: Generate a continuous overlapping fragment q-mer of length q for the remaining part of the query sequence fragment qseq1;

Step 5.2: Use the hash function to calculate the hash value of q-mer;

Step 5.3: Query the hash value calculated in step 5.2 in the bit vector of the Bloom filter;

Step 5.3.1: The corresponding hash values in the bit vector are all 1, and the q-mer passes the screening;

Step 5.3.2: At least one bit of the corresponding hash value in the bit vector is 0, the q-mer does not pass the screening, and the cumulative value Count of the number of failed q-mers is incremented by 1;

Step 5.3.3: Determine whether the Count value is greater than the filtering threshold T;

Step 5.3.3.1: Count is greater than the filtering threshold T, indicating that the anchor point P1 is not positioned correctly, and the anchor point P1 is eliminated;

Step 5.3.3.2: Count is not greater than the filtering threshold T, indicating that the anchor point P is positioned correctly, and the anchor point P1 is reserved;

Step 6: Complete the screening of anchor point P1;

Step 7: Go back to Step 2, and process the fragments of the anchor point P2 and the anchor point P3 until the N anchor points are screened.

In one embodiment, as shown in FIG. 4, an anchor point screening apparatus based on a Bloom filter is provided, including: a sequence acquisition module 402, a segment selection module 404, a sub-segment generation module 406, an index establishment module 408, The query module 410, the anchor point culling module 412 and the traversal module 414, wherein:

The sequence obtaining module 402 is used to obtain the query sequence to be compared, the reference sequence and the multiple anchor points obtained by pre-positioning; the query sequence is a long-read DNA sequence;

A fragment selection module 404, configured to select a fragment of the query sequence between the first anchor point and the second anchor point as a query sequence fragment, and select a fragment of the reference sequence between the first anchor point and the second anchor point as a reference sequence fragment ;

A sub-segment generation module 406, configured to generate a plurality of continuously overlapping reference sequence sub-segments according to a preset length according to the reference sequence segment, and generate a plurality of consecutively overlapping query sequence sub-segments according to the query sequence segment according to a preset length;

The index establishment module 408 is used to establish an index through a plurality of preset hash functions, and map the reference sequence sub-segment into the bit vector of the Bloom filter;

The query module 410 is configured to query whether the sub-segment of the query sequence exists in the reference sequence according to the index, and when the sub-segment of the query sequence does not exist in the reference sequence, determine that the sub-segment of the query sequence has not passed the screening;

Anchor point elimination module 412, configured to traverse all query sequence sub-segments in the query sequence segment, and count the cumulative value of the query sequence sub-segments that have not passed the screening, and when the cumulative value is greater than a preset threshold, remove the first anchor point;

The traversal module 414 is used to traverse all the anchor points until the screening of all the anchor points is completed.

The segment selection module 404 is further configured to delete the same parts at both ends of the query sequence segment and the reference sequence segment, and update the query sequence segment and the reference sequence segment.

The fragment selection module 404 is also used for aligning the query sequence fragment and the reference sequence fragment; extending from both ends of the sequence to the middle, and performing base-by-base alignment; obtaining the same part at both ends of the query sequence fragment and the reference sequence fragment. If the two bases of the query sequence fragment and the reference sequence fragment being aligned are the same, continue to extend to the next base; if the two bases of the query sequence fragment and the reference sequence fragment being aligned are different, stop the extension.

The index establishment module 408 is further configured to obtain a plurality of hash values of each reference sequence sub-segment according to a plurality of preset hash functions; Set to 1.

The query module 410 is further configured to obtain a plurality of hash values of each sub-segment of the query sequence according to a plurality of preset hash functions; query the corresponding position of the Bloom filter bit vector according to the hash value of the sub-segment of the query sequence ; If the values of the corresponding positions of the multiple hash values of the query sequence sub-segment are all 1, the query sequence sub-segment is judged to pass the screening; if not all are 1, the query sequence sub-segment is judged to have not passed the screening.

The query module 410 is further configured to use the second anchor point as the first anchor point, and use the adjacent anchor point to the right of the second anchor point as the second anchor point to perform the next round of anchor point screening.

For the specific definition of the apparatus for anchor point screening based on a Bloom filter, reference may be made to the above definition of the method for anchor point screening based on a Bloom filter, which will not be repeated here. Each module in the above-mentioned Bloom filter-based anchor point screening apparatus can be implemented in whole or in part by software, hardware, and combinations thereof. The above modules can be embedded in or independent of the processor in the computer device in the form of hardware, or stored in the memory in the computer device in the form of software, so that the processor can call and execute the operations corresponding to the above modules.

In one embodiment, a computer device is provided, and the computer device may be a terminal, and its internal structure diagram may be as shown in FIG. 5 . The computer equipment includes a processor, memory, a network interface, a display screen, and an input device connected by a system bus. Among them, the processor of the computer device is used to provide computing and control capabilities. The memory of the computer device includes a non-volatile storage medium, an internal memory. The nonvolatile storage medium stores an operating system and a computer program. The internal memory provides an environment for the execution of the operating system and computer programs in the non-volatile storage medium. The network interface of the computer device is used to communicate with an external terminal through a network connection. The computer program, when executed by a processor, implements a Bloom filter-based anchor point screening method. The display screen of the computer equipment may be a liquid crystal display screen or an electronic ink display screen, and the input device of the computer equipment may be a touch layer covered on the display screen, or a button, a trackball or a touchpad set on the shell of the computer equipment , or an external keyboard, trackpad, or mouse.

Those skilled in the art can understand that the structure shown in FIG. 5 is only a block diagram of a part of the structure related to the solution of the present application, and does not constitute a limitation on the computer equipment to which the solution of the present application is applied. Include more or fewer components than shown in the figures, or combine certain components, or have a different arrangement of components.

In one embodiment, a computer device is provided, including a memory and a processor, where the memory stores a computer program, and the processor implements the steps in the above method embodiments when the processor executes the computer program.

In one embodiment, a computer-readable storage medium is provided, on which a computer program is stored, and when the computer program is executed by a processor, implements the steps in the above method embodiments.

Those of ordinary skill in the art can understand that all or part of the processes in the methods of the above embodiments can be implemented by instructing relevant hardware through a computer program, and the computer program can be stored in a non-volatile computer-readable storage In the medium, when the computer program is executed, it may include the processes of the above-mentioned method embodiments. Wherein, any reference to memory, storage, database or other medium used in the various embodiments provided in this application may include non-volatile and/or volatile memory. Nonvolatile memory may include read only memory (ROM), programmable ROM (PROM), electrically programmable ROM (EPROM), electrically erasable programmable ROM (EEPROM), or flash memory. Volatile memory may include random access memory (RAM) or external cache memory. By way of illustration and not limitation, RAM is available in various forms such as static RAM (SRAM), dynamic RAM (DRAM), synchronous DRAM (SDRAM), double data rate SDRAM (DDRSDRAM), enhanced SDRAM (ESDRAM), synchronous chain Road (Synchlink) DRAM (SLDRAM), memory bus (Rambus) direct RAM (RDRAM), direct memory bus dynamic RAM (DRDRAM), and memory bus dynamic RAM (RDRAM), etc.

The technical features of the above embodiments can be combined arbitrarily. In order to make the description simple, all possible combinations of the technical features in the above embodiments are not described. However, as long as there is no contradiction in the combination of these technical features It is considered to be the range described in this specification.

The above-mentioned embodiments only represent several embodiments of the present application, and the descriptions thereof are specific and detailed, but should not be construed as a limitation on the scope of the invention patent. It should be pointed out that for those skilled in the art, without departing from the concept of the present application, several modifications and improvements can be made, which all belong to the protection scope of the present application. Therefore, the scope of protection of the patent of the present application shall be subject to the appended claims.

Claims (10)

1. an anchor point screening method based on Bloom filter, is characterized in that, described method comprises: Obtain the query sequence to be compared, the reference sequence and multiple anchor points obtained by pre-positioning; the query sequence is a long-read DNA sequence; Select the fragment of the query sequence between the first anchor point and the second anchor point as the query sequence fragment, and select the fragment of the reference sequence between the first anchor point and the second anchor point as the reference sequence fragment; generating a plurality of consecutive overlapping reference sequence sub-segments according to the reference sequence fragment according to a preset length, and generating a plurality of consecutive overlapping query sequence sub-segments according to the query sequence fragment according to the preset length; Indexing is established by a plurality of preset hash functions, and the sub-segment of the reference sequence is mapped to the bit vector of the Bloom filter; Query whether the sub-segment of the query sequence exists in the reference sequence according to the index, and when the sub-segment of the query sequence does not exist in the reference sequence, determine that the sub-segment of the query sequence has not passed the screening; Traverse all the query sequence sub-segments in the query sequence fragment, and count the cumulative value of the query sequence sub-fragments that have not passed the screening, and when the cumulative value is greater than a preset threshold, remove the first anchor point; Iterates through all anchors until filtering of all said anchors is complete. 2 . The method according to claim 1 , wherein a plurality of consecutive overlapping reference sequence sub-segments are generated according to the reference sequence segment according to a preset length, and the query sequence segment is generated according to the preset length according to the query sequence segment. 3 . Before multiple consecutive overlapping sub-segments of the query sequence, also include: The same parts at both ends of the query sequence fragment and the reference sequence fragment are deleted, and the query sequence fragment and the reference sequence fragment are updated. 3. The method according to claim 2, wherein, before deleting the same part at both ends of the query sequence fragment and the reference sequence fragment, and before updating the query sequence fragment and the reference sequence fragment, Also includes: aligning the query sequence fragment and the reference sequence fragment; Extend from both ends of the sequence to the middle, and align base by base; The same portion at both ends of the query sequence fragment and the reference sequence fragment is obtained. 4. The method according to claim 3, wherein the two ends of the sequence are extended to the middle, and the base-by-base alignment is performed, comprising: If the two bases on which the query sequence fragment and the reference sequence fragment are being aligned are the same, continue to extend to the next base; If the query sequence fragment and the reference sequence fragment are different by two bases being aligned, the extension is stopped. 5. The method according to claim 4, wherein indexing is established by multiple preset hash functions, and the reference sequence sub-segment is mapped to the bit vector of the Bloom filter, comprising: Obtain multiple hash values of each reference sequence sub-segment according to the preset multiple hash functions; The value of the corresponding position of the bloom filter bit vector is set to 1 according to the hash value of the reference sequence sub-segment. 6 . The method according to claim 5 , wherein the query sequence sub-segment is inquired about whether the query sequence sub-segment exists in the reference sequence according to the index, when the query sequence sub-segment does not exist in the reference sequence. 7 . , judging that the sub-fragments of the query sequence have not passed the screening, including: Obtain multiple hash values of each query sequence sub-segment according to multiple preset hash functions; Perform a query at the corresponding position of the Bloom filter bit vector according to the hash value of the sub-segment of the query sequence; If the values of the corresponding positions of the plurality of hash values of the sub-segment of the query sequence are all 1, it is judged that the sub-segment of the query sequence passes the screening; If not all are 1, it is judged that the sub-fragment of the query sequence has not passed the screening. 7. The method according to any one of claims 1 to 6, wherein after removing the first anchor point, the method comprises: Taking the second anchor point as the first anchor point, and taking the adjacent anchor point on the right side of the second anchor point as the second anchor point, the next round of anchor point screening is performed. 8. An anchor point screening device based on a Bloom filter, wherein the device comprises: a sequence acquisition module, used to acquire a query sequence to be compared, a reference sequence and a plurality of anchor points obtained by pre-positioning; the query sequence is a long-read DNA sequence; A fragment selection module is used to select a fragment of the query sequence between the first anchor point and the second anchor point as a query sequence fragment, and select the reference sequence between the first anchor point and the second anchor point. The fragments between are reference sequence fragments; a sub-segment generation module, configured to generate a plurality of consecutive overlapping reference sequence sub-segments according to the reference sequence segment according to a preset length, and generate a plurality of consecutive overlapping query sequence sub-segments according to the query sequence segment according to the preset length ; an index establishment module, for establishing an index through a plurality of preset hash functions, and mapping the reference sequence sub-segment into the bit vector of the Bloom filter; A query module, configured to query whether the sub-segment of the query sequence exists in the reference sequence according to the index, and when the sub-segment of the query sequence does not exist in the reference sequence, determine that the sub-segment of the query sequence has failed filter; An anchor point elimination module is used to traverse all query sequence sub-segments in the query sequence segment, and count the cumulative value of the query sequence sub-segments that have not passed the screening, and when the cumulative value is greater than a preset threshold, remove the first anchor; The traversal module is used to traverse all the anchors until the screening of all the anchors is completed. 9. The apparatus according to claim 8, wherein the segment selection module is further configured to delete the same part at both ends of the query sequence segment and the reference sequence segment, and the query sequence segment and the reference sequence segment are Reference sequence fragments are updated. 10. A computer device comprising a memory and a processor, wherein the memory stores a computer program, wherein the processor implements the steps of the method according to any one of claims 1 to 7 when the processor executes the computer program .

Images