# US 2021/0343373 A1 · Sequence alignment filtering processing method, system and device, and readable storage medium

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2021/0343373 A1
- Document ID: US20210343373A1
- Status: Published application
- Kind: A1
- Application number: 17/280,926
- Filed: 2019-08-30
- Published: 2021-11-04
- Earliest claimed: 2019-01-31
- Assignees: Zhengzhou Yunhai Information Technology Co., Ltd.
- Applicants: Zhengzhou Yunhai Information Technology Co., Ltd.
- Inventors: Jian ZHAO; Hongzhi SHI; Xingchen CUI; Yunfeng YIN
- Web page: https://patentgrep.com/patent/US20210343373A1

## CPC

- G16B 30/10: Sequence alignment; Homology search
- G16B: BIOINFORMATICS, i.e. INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR GENETIC OR PROTEIN-RELATED DATA PROCESSING IN COMPUTATIONAL MOLECULAR BIOLOGY

## Abstract

A filter processing method for a sequence alignment is provided. The method includes: searching for absolute locations of all seeds of a to-be-aligned sequence in a reference sequence; performing segmentation on the absolute locations of the seeds to obtain relative locations of the seeds; dividing the reference sequence into multiple reference sub-sequences and establishing a mapping relationship between a relative location of each seed and a corresponding reference sub-sequence; determining a reference sub-sequence to which each seed belongs and counting the occurrence numbers of the seeds in each reference sub-sequence; filtering out a reference sub-sequence that does not meet a preset condition to obtain a target reference sub-sequence; and recovering a real CAL based on a difference between a relative location and an absolute location of each seed in the target reference sub-sequence.

## Claims

### Claim 1

A filter processing method for a sequence alignment, comprising:
searching for absolute locations of all seeds of a to-be-aligned sequence in a reference sequence;
performing segmentation on the absolute locations of all the seeds in the reference sequence, to obtain relative locations of all the seeds;
dividing the reference sequence into a plurality of reference sub-sequences in advance, and establishing a mapping relationship between a relative location of each seed and a reference sub-sequence corresponding to the seed;
determining a reference sub-sequence to which each seed belongs according to a feature identifier of the seed and the mapping relationship, and counting the numbers of occurrences of the seeds in each reference sub-sequence;
filtering out a reference sub-sequence that does not meet a preset condition based on the numbers of occurrences of the seeds in each reference sub-sequence, to obtain a target reference sub-sequence meeting the preset condition; and
recovering a real CAL based on a difference between a relative location and an absolute location of each seed in the target reference sub-sequence.

### Claim 2 (depends on 1)

The filter processing method for a sequence alignment according to claim 1, wherein the determining a reference sub-sequence to which each seed belongs according to a feature identifier of the seed and the mapping relationship comprises:
calculating a hash value of each seed; and
determining the reference sub-sequence to which each seed belongs from a filter hash table storing the mapping relationship, with the hash value of each seed as an address.

### Claim 3 (depends on 1)

The filter processing method for a sequence alignment according to claim 1, wherein the filtering out a reference sub-sequence that does not meet a preset condition based on the numbers of occurrences of the seeds in each reference sub-sequence comprises:
setting a dynamic filtering threshold according to the numbers of occurrences of the seeds in each reference sub-sequence, a mean value of the numbers of occurrences, and/or a maximum descending gradient of the numbers of occurrences; and
filtering out a reference sub-sequence that does not meet the dynamic filtering threshold.

### Claim 4

A filter processing system for a sequence alignment, comprising:
an absolute location searching module configured to search for absolute locations of all seeds of a to-be-aligned sequence in a reference sequence;
an absolute location segmentation module configured to perform segmentation on the absolute locations of all the seeds in the reference sequence, to obtain relative locations of all the seeds;
a mapping relationship establishing module configured to divide the reference sequence into a plurality of reference sub-sequences in advance, and establish a mapping relationship between a relative location of each seed and a reference sub-sequence corresponding to the seed;
an occurrence number counting module configured to determine a reference sub-sequence to which each seed belongs according to a feature identifier of the seed and the mapping relationship, and count the numbers of occurrences of the seeds in each reference sub-sequence;
a sub-sequence filtering module configured to filter out a reference sub-sequence that does not meet a preset condition based on the numbers of occurrences of the seeds in each reference sub-sequence, to obtain a target reference sub-sequence meeting the preset condition; and
a CAL recovering module configured to recover a real CAL based on a difference between a relative location and an absolute location of each seed in the target reference sub-sequence.

### Claim 5 (depends on 4)

The filter processing system for a sequence alignment according to claim 4, wherein the occurrence number counting module comprises:
a hash value calculating unit configured to calculate a hash value of each seed; and
a determining unit configured to determine the reference sub-sequence to which each seed belongs from a filtered hash table storing the mapping relationship, with the hash value of each seed as an address.

### Claim 6 (depends on 4)

The filter processing system for a sequence alignment according to claim 4, wherein the sub-sequence filtering module comprises:
a threshold setting unit configured to set a dynamic filtering threshold according to the numbers of occurrences of the seeds in each reference sub-sequence, a mean value of the numbers of occurrence, and/or a maximum descending gradient of the number of occurrence; and
a filtering unit configured to filter out a reference sub-sequence that does not meet the dynamic filtering threshold.

### Claim 7 (depends on 1)

A filter processing device for a sequence alignment, comprising:
a memory configured to store a computer program; and
a processor configured to execute the computer program to perform the filter processing method for a sequence alignment according to claim 1.

### Claim 8 (depends on 1)

A computer-readable storage medium storing a computer program, wherein the computer program is executed by a processor to perform the filter processing method for a sequence alignment claim 1.

### Claim 9 (depends on 7)

The filter processing device for a sequence alignment according to claim 7, wherein the determining a reference sub-sequence to which each seed belongs according to a feature identifier of the seed and the mapping relationship comprises:
calculating a hash value of each seed; and
determining the reference sub-sequence to which each seed belongs from a filter hash table storing the mapping relationship, with the hash value of each seed as an address.

### Claim 10 (depends on 7)

The filter processing device for a sequence alignment according to claim 7, wherein the filtering out a reference sub-sequence that does not meet a preset condition based on the numbers of occurrences of the seeds in each reference sub-sequence comprises:
setting a dynamic filtering threshold according to the numbers of occurrences of the seeds in each reference sub-sequence, a mean value of the numbers of occurrences, and/or a maximum descending gradient of the numbers of occurrences; and
filtering out a reference sub-sequence that does not meet the dynamic filtering threshold.

### Claim 11 (depends on 8)

The computer-readable storage medium storing a computer program according to claim 8, wherein the determining a reference sub-sequence to which each seed belongs according to a feature identifier of the seed and the mapping relationship comprises:
calculating a hash value of each seed; and
determining the reference sub-sequence to which each seed belongs from a filter hash table storing the mapping relationship, with the hash value of each seed as an address.

### Claim 12 (depends on 8)

The computer-readable storage medium storing a computer program according to claim 8, wherein the filtering out a reference sub-sequence that does not meet a preset condition based on the numbers of occurrences of the seeds in each reference sub-sequence comprises:
setting a dynamic filtering threshold according to the numbers of occurrences of the seeds in each reference sub-sequence, a mean value of the numbers of occurrences, and/or a maximum descending gradient of the numbers of occurrences; and
filtering out a reference sub-sequence that does not meet the dynamic filtering threshold.
