# US 2020/0286589 A1 · Methods of optimizing genome assembly parameters

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

- Number: US 2020/0286589 A1
- Document ID: US20200286589A1
- Status: Published application
- Kind: A1
- Application number: 16/295,836
- Filed: 2019-03-07
- Published: 2020-09-10
- Earliest claimed: 2019-03-07
- Assignees: International Business Machines Corporation
- Applicants: International Business Machines Corporation
- Inventors: Matthew A. Davis; Mark Kunitomi; Kun Hu
- Web page: https://patentgrep.com/patent/US20200286589A1

## CPC

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

## Abstract

An iterative process for optimizing one or more parameters used by a k-mer based de novo genome assembler program to assemble a set of sequenced nucleic acids is described. The method utilizes quality metrics whose desired values are initially specified. Computed values of the quality metrics are calculated during the assembly process and compared to the desired values. The assembly process stops when the computed values are not desired values. After modification of one or more of the parameters (e.g., k-mer value), the assembly process re-initiates using the modified parameter set. This process repeats until the computed values of the quality metrics meet the desired values. The final parameter set is then used to generate or complete one or more final assembled genomes.

## Claims

### Claim 1

A method, comprising:
selecting a k-mer-based de novo genome assembler program, designated assembler;
providing a set of parameters for assembly of a set of sequenced nucleic acids, the parameters having respective values and respective priority scores, the parameters including a k-mer parameter having an initial length k in number of nucleotides, k being a positive integer equal to at least 35;
providing a set of quality metrics for assembly of a set of sequenced nucleic acids, the quality metrics having respective weights indicating importance, respective target values, and respective computed values calculated during assembly, a given quality metric depending on one or more of the parameters;
initiating assembly of the set of sequenced nucleic acids by the assembler, the assembler utilizing the set of parameters and the set of quality metrics, thereby forming intermediate assembled sequences;
performing a procedure iteratively until the respective computed values of the quality metrics equal the respective target values, the procedure comprising the steps of: i) stopping the assembler when the respective computed values of the quality metrics do not equal the respective target values, ii) modifying at least one of the parameters and/or at least one of the quality metrics, iii) deleting any intermediate assembled sequences, iv) initiating assembly of the set of sequenced nucleic acids by the assembler, and v) calculating values of the quality metrics including any modified quality metrics, the procedure terminating while utilizing a set of final parameters and a set of final quality metrics, the final parameters including a final k-mer parameter of length k′; and
completing assembly of the set of sequenced nucleic acids using the assembler, the set of final parameters, and the set of final quality metrics, thereby forming one or more final assembled genomes.

### Claim 2 (depends on 1)

The method of claim 1, wherein the method comprises storing the final parameters and the final quality metrics with the one or more final assembled genomes.

### Claim 3 (depends on 1)

The method of claim 1, wherein the method is performed by a computer system without human intervention.

### Claim 4 (depends on 1)

The method of claim 1, wherein the intermediate assembled sequences are partially assembled genomes.

### Claim 5 (depends on 1)

The method of claim 1, wherein the intermediate assembled sequences are wholly assembled genomes.

### Claim 6 (depends on 1)

The method of claim 1, wherein the quality metrics include a member selected from the group consisting of N50, NA50, NG50, NGA50, L50, LA50, LG50, LGA50, and combinations thereof.

### Claim 7 (depends on 1)

The method of claim 1, wherein the quality metrics include a member selected from the group consisting of number of contigs, number of contigs above a given size, number of contig edges, number of connections within contigs, and combinations thereof.

### Claim 8 (depends on 1)

The method of claim 1, wherein i) the intermediate assembled sequences have sizes, a mean size, a median size, and a standard deviation of the sizes of the intermediate assembled sequences calculated during the assembly, ii) a given taxonomic rank contains reference genomes having sizes, a mean size, a median size, and a standard deviation of the sizes of the reference genomes, and iii) the assembly includes a quality metric for the difference between the mean size of the intermediate assembled sequences and the mean size of the reference genomes.

### Claim 9 (depends on 8)

The method of claim 8, wherein the assembly includes a quality metric for the difference between the median size of the intermediate assembled sequences and the median size of the reference genomes.

### Claim 10 (depends on 5)

The method of claim 5, wherein the assembly includes a quality metric for the difference between the standard deviation of the sizes of the intermediate assembled sequences and the standard deviation of the sizes of the reference genomes.

### Claim 11 (depends on 1)

The method of claim 1, wherein the quality metrics include a member selected from the group consisting of coverages per nucleotide base, coverages per contig, coverages per assembly, number of misassembles, relative abundances of nucleotides, repetitive content of nucleotides, and combinations thereof.

### Claim 12 (depends on 1)

The method of claim 1, wherein k′ is optimal for one of the final assembled genomes.

### Claim 13 (depends on 1)

The method of claim 1, wherein k′ is an average of values of the k-mer parameter used in the procedure.

### Claim 14 (depends on 1)

The method of claim 1, wherein the k-mer parameter has a lower priority score and/or lower ranking compared to another parameter.

### Claim 15 (depends on 14)

The method of claim 14, wherein said another parameter is a member selected from the group consisting of coverage cutoff value, number of mismatches allowed, expected genome size, insert size, and sequencing error rate of the intermediate assembled sequences.

### Claim 16 (depends on 1)

The method of claim 1, wherein k′ is optimal for a subset of the final assembled genomes, the subset comprising more than one final assembled genome.

### Claim 17 (depends on 16)

The method of claim 16, wherein the subset is defined by taxonomic rank.

### Claim 18 (depends on 16)

The method of claim 16, wherein the subset is defined by sequencing method.

### Claim 19 (depends on 18)

The method of claim 18, wherein the sequencing method is a member selected from the group consisting of Sanger, Illumina, PacBio, 454, Ion Torrent, and SOLid.

### Claim 20

A system comprising one or more computer processor circuits configured and arranged to:
select a k-mer-based de novo genome assembler program, designated assembler;
provide a set of parameters for assembly of a set of sequenced nucleic acids, the parameters having respective values and respective priority scores, the parameters including a k-mer parameter having an initial length k in number of nucleotides, k being a positive integer equal to at least 35;
provide a set of quality metrics for assembly of a set of sequenced nucleic acids, the quality metrics having respective weights indicating importance, respective target values, and respective computed values calculated during assembly, a given quality metric depending on one or more of the parameters;
initiate assembly of the set of sequenced nucleic acids by the assembler, the assembler utilizing the set of parameters and the set of quality metrics, thereby forming intermediate assembled sequences;
perform a procedure iteratively until the respective computed values of the quality metrics equal the respective target values, the procedure comprising the steps of: i) stopping the assembler when the respective computed values of the quality metrics do not equal the respective target values, ii) modifying at least one of the parameters and/or at least one of the quality metrics, iii) deleting any intermediate assembled sequences, iv) initiating assembly of the set of sequenced nucleic acids by the assembler, and v) calculating values of the quality metrics including any modified quality metrics, the procedure terminating while utilizing a set of final parameters and a set of final quality metrics, the final parameters including a final k-mer parameter of length k′; and
complete assembly of the set of sequenced nucleic acids using the assembler, the set of final parameters, and the set of final quality metrics, thereby forming one or more final assembled genomes.

### Claim 21

A computer program product, comprising a computer readable hardware storage device having a computer-readable program code stored therein, said program code configured to be executed by a processor of a computer system to implement a method comprising:
selecting a k-mer-based de novo genome assembler program, designated assembler;
providing a set of parameters for assembly of a set of sequenced nucleic acids, the parameters having respective values and respective priority scores, the parameters including a k-mer parameter having an initial length k in number of nucleotides, k being a positive integer equal to at least 35;
providing a set of quality metrics for assembly of a set of sequenced nucleic acids, the quality metrics having respective weights indicating importance, respective target values, and respective computed values calculated during assembly, a given quality metric depending on one or more of the parameters;
initiating assembly of the set of sequenced nucleic acids by the assembler, the assembler utilizing the set of parameters and the set of quality metrics, thereby forming intermediate assembled sequences;
performing a procedure iteratively until the respective computed values of the quality metrics equal the respective target values, the procedure comprising the steps of: i) stopping the assembler when the respective computed values of the quality metrics do not equal the respective target values, ii) modifying at least one of the parameters and/or at least one of the quality metrics, iii) deleting any intermediate assembled sequences, iv) initiating assembly of the set of sequenced nucleic acids by the assembler, and v) calculating values of the quality metrics including any modified quality metrics, the procedure terminating while utilizing a set of final parameters and a set of final quality metrics, the final parameters including a final k-mer parameter of length k′; and
completing assembly of the set of sequenced nucleic acids using the assembler, the set of final parameters, and the set of final quality metrics, thereby forming one or more final assembled genomes.

### Claim 22

A method of genome assembly for single assembly or sets of assemblies by optimizing the k-mer length parameter, the method comprising the following steps:
using high throughput sequencing to sequence one or more genomes, thereby forming sequence data;
processing the sequence data for quality control;
selecting a quality metric for assembly of the sequence data, the quality metric having a calculated value during an assembly and a target value;
initiating assembly of the sequence data using a set of k-mer values for the one or more genomes, the k-mer values having scores and ranks;
performing a procedure during the assembly when the calculated value of the quality metric does not equal to the target value, the procedure comprising:
a) deleting any intermediate assembled sequences,
b) modifying the k-mer values,
c) initiating assembly using the modified k-mer values,
d) assessing the calculated value of the quality metric relative to the target value before the assembly is complete;
e) updating the scores and ranks of the k-mer values;
repeating the procedure until the calculated value of the quality metric equals the target value; and
completing the assembly.
