# US 8,751,165 B2 · Error correcting method of test sequence, corresponding system and gene assembly equipment

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

- Number: US 8,751,165 B2
- Document ID: US8751165B2
- Status: Granted
- Kind: B2
- Application number: 13/132,038
- Filed: 2009-12-11
- Published: 2011-12-01
- Granted: 2014-06-10
- Earliest claimed: 2008-12-12
- Assignees: Bgi Tech Solutions Co., Ltd.
- Applicants: Jun Wang; Huanming Yang; Jian Wang
- Inventors: Jun Wang; Huanming Yang; Jian Wang
- Web page: https://patentgrep.com/patent/US8751165B2

## CPC

- G16B 30/20: Sequence assembly
- C12Q 1/6874: involving nucleic acid arrays, e.g. sequencing by hybridisation
- G16B 30/00: ICT specially adapted for sequence analysis involving nucleotides or amino acids
- G16B 40/00: ICT specially adapted for biostatistics; ICT specially adapted for bioinformatics-related machine learning or data mining, e.g. knowledge discovery or pattern finding
- G16B: BIOINFORMATICS, i.e. INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR GENETIC OR PROTEIN-RELATED DATA PROCESSING IN COMPUTATIONAL MOLECULAR BIOLOGY
- C12Q: MEASURING OR TESTING PROCESSES INVOLVING ENZYMES, NUCLEIC ACIDS OR MICROORGANISMS (immunoassay G01N33/53); COMPOSITIONS OR TEST PAPERS THEREFOR; PROCESSES OF PREPARING SUCH COMPOSITIONS; CONDITION-RESPONSIVE CONTROL IN MICROBIOLOGICAL OR ENZYMOLOGICAL PROCESSES

## Abstract

The present invention provides an error correcting method of test sequence, which involves receiving test sequences, configuring high frequency short string list based on a preset high frequency threshold value, traversing each received test sequence, searching an area with the largest number of continuous high frequency short strings on each test sequence in combination with high frequency short string list, configuring whole left sequence and/or right sequence of high frequency short strings at left side and/or right side of searched area according to corresponding received test sequence and high frequency short string list, and constituting corresponding test sequence according to configured left and/or right sequence and searched area. The present invention also provides corresponding error correcting system of test sequence and gene assembly equipment.

## Claims

### Claim 1

A computer-implemented method for correcting test sequences comprising:
dividing, using a processor, a test sequence into short strings with a preset length on the basis of one-base-by-one-base, wherein the preset length is n;
configuring a high frequency short string list based on the short strings using a processor, wherein the high frequency short string list consists of short strings with a frequency of occurrence larger than a preset high frequency threshold value;
traversing the test sequence using a processor, and searching for an area [s1, s2] with the largest number of continuous high frequency short strings on each test sequence by referring to the high frequency short string list; wherein s1, s2 are respectively the starting base and the ending base of the searched area with the largest number of continuous high frequency short strings; wherein the test sequence has a length of ln and an area of [s1, s2];
taking a sequence with length of n−1 starting from the s1-th base of the test sequence as a root node of a tree, and using a processor to configure a left side tree having depth of s1 with four types of bases A, C, G, T as the leaves of each node;
traversing from a leaf node on the left side tree, using a processor, searching for a path that consists of high frequency short strings, and configuring a left sequence that consists of high frequency short strings along the path upwardly;
taking a sequence with the length of n−1 starting from the s2-th base of the test sequence as a root node of a tree, and using a processor to configure a right side tree having depth of ln−(s2−1) with four types of bases A, C, G, T as the leaves of each node;
traversing from the root node on the right side tree, using a processor, searching for a path consisting of high frequency short strings, and configuring a right sequence consisting solely of high frequency short strings along the path downwardly;
and using a processor to recover the test sequence according to the left sequence and/or the right sequence and the area [s1, s2] by adding the left sequence at the left side of the area [s1, s2] and/or adding the right sequence at the right side of the area [s1, s2].

### Claim 2 (depends on 1)

The method according to claim 1, wherein the preset high frequency threshold value is determined according to a frequency distribution of the short strings with the preset length, wherein the preset length is 17 bases in length.

### Claim 3 (depends on 1)

The method according to claim 1, wherein the length of the test sequence is equal to or less than 200 bases.

### Claim 4

A computer-implemented system for correcting test sequences comprising:
hardware instructed by a program for dividing a test sequence into short strings with a preset length on the basis of one-base-by-one-base, wherein the preset length is n;
hardware instructed by a program for configuring a high frequency short string list based on the short strings, wherein high frequency short string list consists of short strings with a frequency of occurrence larger than the preset high frequency threshold value;
hardware instructed by a program for traversing the test sequence, and searching for an area [s1, s2] with the largest number of continuous high frequency short strings on each test sequence by referring to the high frequency short string list; wherein s1, s2 are respectively the starting base and the ending base of the searched area with the largest number of continuous high frequency short strings; wherein the test sequence has a length of ln and an area of [s1, s2];
hardware instructed by a program for configuring a left side tree by taking a sequence with the length n−1 starting from the s1-th base of the corresponding test sequence as a root node of a tree, and configuring a left side tree having the depth of s1 with four types of bases A, C, G, T as the leaves of each node;
hardware instructed by a program for traversing from a leaf node on the left side tree, searching for a path consisting of high frequency short strings, and configuring a left sequence consisting of high frequency short strings along the path upwardly;
hardware instructed by a program for configuring a right side tree by taking a sequence with the length of n−1 starting from the s2-th base of the test sequence as a root node of a tree, and configuring a right side tree having the depth of ln−(s2−1) with four types of bases A, C, G, T as the leaves of each node;
hardware instructed by a program for traversing from the root node on the right side tree, searching for a path consisting of high frequency short strings, and configuring a right sequence consisting of high frequency short strings from the root node along the path downwardly; and
hardware instructed by a program for recovering the test sequence according to the left sequence and/or right sequence and the area [s1, s2] by adding the left sequence at the left side of the area [s1, s2] and/or adding the right sequence at the right side of the area [s1, s2].

### Claim 5 (depends on 4)

The system according to claim 4, wherein the preset high frequency threshold value is determined according to a distribution frequency of the short strings with the preset length, wherein the preset length is 17 bases in length.