# US 2021/0174904 A1 · Merging Duplicate Marking to Optimize Computer Operations for Gene Sequencing Pipeline

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

- Number: US 2021/0174904 A1
- Document ID: US20210174904A1
- Status: Published application
- Kind: A1
- Application number: 17/114,895
- Filed: 2020-12-08
- Published: 2021-06-10
- Earliest claimed: 2019-03-14
- Assignees: Huawei Technologies Co., Ltd.
- Applicants: Huawei Technologies Co., Ltd.
- Inventors: Meysam Roodi; Zahra Lak
- Web page: https://patentgrep.com/patent/US20210174904A1

## CPC

- G16B 30/20: Sequence assembly
- G06F 16/9024: {Graphs; Linked lists (G06F16/9027 takes precedence)}
- G06N 3/126: Evolutionary algorithms, e.g. genetic algorithms or genetic programming
- G16B 50/00: ICT programming tools or database systems specially adapted for bioinformatics
- G16B 50/30: Data warehousing; Computing architectures
- G16B: BIOINFORMATICS, i.e. INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR GENETIC OR PROTEIN-RELATED DATA PROCESSING IN COMPUTATIONAL MOLECULAR BIOLOGY
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS

## Abstract

In accordance with embodiments, a processing unit performs alignment of a short read (SR) against a reference genome sequence. The processing unit determines whether the SR is aligned. If the SR is not aligned, the processing unit receives the next SR and processes the next SR by repeating. If the SR is aligned, in response to the determination that the SR is aligned with the reference genome sequence at a first position in the reference genome sequence, the processing unit generates a new SR metadata entry corresponding to the SR. The processing unit finds a linked list in a SR metadata collection. The first position of the linked list in the SR metadata collection corresponds to the first position of the reference genome sequence where the SR is aligned. The processing unit performs duplicate marking based on the SR and the linked list.

## Claims

### Claim 1

A method comprising:
performing, by at least one processing unit, alignment of a short read (SR) against a reference genome sequence, wherein the reference genome sequence comprises a first sequence of base pairs (bps), and the SR comprises a second sequence of bps;
in response to determination that the SR is aligned with the reference genome sequence at a first position in the reference genome sequence:
generating, by the at least one processing unit, a new SR metadata entry corresponding to the SR;
finding, by the at least one processing unit, a linked list in a SR metadata collection, a first position of the linked list in the SR metadata collection corresponding to the first position of the reference genome sequence where the SR is aligned; and
performing, by the at least one processing unit, duplicate marking based on the SR and the linked list.

### Claim 2 (depends on 1)

The method of claim 1, wherein the SR is in a pair end comprising the SR and a mate SR, the new SR metadata entry comprises an average quality score (AQS) of quality scores of the bps in the SR, and the new SR metadata entry further comprises a PNEXT value indicating a distance between the first position of the linked list in the SR metadata collection and a second position of a second linked list in the SR metadata collection, the second linked list comprising a second SR metadata entry corresponding to the mate SR.

### Claim 3 (depends on 2)

The method of claim 2, wherein SR metadata entries in the linked list are grouped based on PNEXT values of the SR metadata entries in the linked list.

### Claim 4 (depends on 3)

The method of claim 3, wherein the performing duplicate marking comprises:
finding, by the at least one processing unit, a group of SR metadata entries in the linked list having the same PNEXT value as the new SR metadata entry;
finding, by the at least one processing unit, a head SR metadata entry in the group, wherein an AQS of the head SR metadata entry is the highest in the group; and
marking, by the at least one processing unit, one of the new SR metadata entry or the head SR metadata entry as duplicate based on a comparison between the AQS of the head SR metadata entry and the AQS of the new SR metadata entry.

### Claim 5 (depends on 4)

The method of claim 4, wherein the marking comprises:
if the AQS of the new SR metadata entry is higher than the AQS of the head SR metadata entry, marking, by the at least one processing unit, the head SR metadata entry as duplicate; and
if the AQS of the new SR metadata entry is lower than the AQS of the head SR metadata entry, marking, by the at least one processing unit, the new SR metadata entry as duplicate.

### Claim 6 (depends on 4)

The method of claim 4, wherein the head SR metadata entry is at a beginning of the group in the linked list.

### Claim 7 (depends on 6)

The method of claim 6, further comprising:
inserting, by the at least one processing unit, the new SR metadata entry at the beginning of the group if the AQS of the new SR metadata entry is higher than the AQS of the head SR metadata entry; or
inserting, by the at least one processing unit, the new SR metadata entry after the head SR metadata entry if the AQS of the new SR metadata entry is less than the AQS of the head SR metadata entry.

### Claim 8 (depends on 1)

The method of claim 1, further comprising:
generating, by the at least one processing unit, a binary alignment map (BAM) file based on the SR metadata collection without producing an intermediate SAM file or an intermediate unmarked BAM file.

### Claim 9 (depends on 1)

The method of claim 1, wherein the SR metadata collection is an array of linked lists, and a size of the array is based on a size of the first sequence of bps in the reference genome sequence.

### Claim 10

A computing device comprising;
at least one processor unit;
a non-transitory computer readable storage medium storing programming for execution by the at least one processor unit, the programming including instructions to:
perform alignment of a short read (SR) against a reference genome sequence, wherein the reference genome sequence comprises a first sequence of base pairs (bps), and the SR comprises a second sequence of bps;
in response to determination that the SR is aligned with the reference genome sequence at a first position in the reference genome sequence:
generate a new SR metadata entry corresponding to the SR;
find a linked list in a SR metadata collection, a first position of the linked list in the SR metadata collection corresponding to the first position of the reference genome sequence where the SR is aligned; and
perform duplicate marking based on the SR and the linked list.

### Claim 11 (depends on 10)

The computing device of claim 10, wherein the SR is in a pair end comprising the SR and a mate SR, the new SR metadata entry comprises an average quality score (AQS) of quality scores of the bps in the SR, and the new SR metadata entry further comprises a PNEXT value indicating a distance between the first position of the linked list in the SR metadata collection and a second position of a second linked list in the SR metadata collection, the second linked list comprising a second SR metadata entry corresponding to the mate SR.

### Claim 12 (depends on 11)

The computing device of claim 11, wherein SR metadata entries in the linked list are grouped based on PNEXT values of the SR metadata entries in the linked list.

### Claim 13 (depends on 12)

The computing device of claim 12, the instructions to perform duplicate marking further including instructions to:
find a group of SR metadata entries in the linked list having the same PNEXT value as the new SR metadata entry;
find a head SR metadata entry in the group, wherein an AQS of the head SR metadata entry is the highest in the group; and
mark one of the new SR metadata entry or the head SR metadata entry as duplicate based on a comparison between the AQS of the head SR metadata entry and the AQS of the new SR metadata entry.

### Claim 14 (depends on 13)

The computing device of claim 13, the instructions to mark further including instructions to:
if the AQS of the new SR metadata entry is higher than the AQS of the head SR metadata entry, mark the head SR metadata entry as duplicate; and
if the AQS of the new SR metadata entry is lower than the AQS of the head SR metadata entry, mark the new SR metadata entry as duplicate.

### Claim 15 (depends on 13)

The computing device of claim 13, wherein the head SR metadata entry is at a beginning of the group in the linked list.

### Claim 16 (depends on 15)

The computing device of claim 15, the programming further including instructions to:
insert the new SR metadata entry at the beginning of the group if the AQS of the new SR metadata entry is higher than the AQS of the head SR metadata entry; or
insert the new SR metadata entry after the head SR metadata entry if the AQS of the new SR metadata entry is less than the AQS of the head SR metadata entry.

### Claim 17 (depends on 10)

The computing device of claim 10, the programming further including instructions to:
generate a binary alignment map (BAM) file based on the SR metadata collection without producing an intermediate SAM file or an intermediate unmarked BAM file.

### Claim 18 (depends on 10)

The computing device of claim 10, wherein the SR metadata collection is an array of linked lists, and a size of the array is based on a size of the first sequence of bps in the reference genome sequence.

### Claim 19

A non-transitory computer-readable medium having instructions stored thereon that, when executed by at least one processor unit, cause the at least one processor unit to perform operations, the operations comprising:
performing alignment of a short read (SR) against a reference genome sequence, wherein the reference genome sequence comprises a first sequence of base pairs (bps), and the SR comprises a second sequence of bps;
in response to determination that the SR is aligned with the reference genome sequence at a first position in the reference genome sequence:
generating a new SR metadata entry corresponding to the SR;
finding a linked list in a SR metadata collection, a first position of the linked list in the SR metadata collection corresponding to the first position of the reference genome sequence where the SR is aligned; and
performing duplicate marking based on the SR and the linked list.

### Claim 20 (depends on 19)

The non-transitory computer-readable medium of claim 19, wherein the SR is in a pair end comprising the SR and a mate SR, the new SR metadata entry comprises an average quality score (AQS) of quality scores of the bps in the SR, and the new SR metadata entry further comprises a PNEXT value indicating a distance between the first position of the linked list in the SR metadata collection and a second position of a second linked list in the SR metadata collection, the second linked list comprising a second SR metadata entry corresponding to the mate SR.
