SYSTEMS AND METHODS FOR GENOTYPING WITH GRAPH REFERENCE

• US 20170242958A1
• Filed: 02/24/2016
• Published: 08/24/2017
• Est. Priority Date: 02/24/2016
• Status: Active Application

• Current Assignee: Seven Bridges Genomics, Inc.
• Original Assignee: Seven Bridges Genomics, Inc.
• Inventors: Brown, Richard
• Granted Patent: US 10,262,102 B2
• Time in Patent Office: Days
• CPC Class Codes: G16B 20/00 ICT specially adapted for functional genomics or proteomics, e.g. genotype-phenotype associations
• CPC Class Codes: G16B 20/20 Allele or variant detection, e.g. single nucleotide polymorphism [SNP] detection
• CPC Class Codes: G16B 45/00 ICT specially adapted for bioinformatics-related data visualisation, e.g. displaying of maps or networks

Abstract

Genomic references are structured as a reference graph that represents diploid genotypes in organisms. A path through a series of connected nodes and edges represents a genetic sequence. Genetic variation within a diploid organism is represented by multiple paths through the reference graph. The graph may be transformed into a traversal graph in which a path represents a diploid genotype. Genetic analysis using the traversal graph allows an organism'"'"'s diploid genotype to be elucidated, e.g., by mapping sequence reads to the reference graph and scoring paths in the traversal graph based on the mapping to determine the path through the traversal graph that best fits the sequence reads.

Claims

1. A method of determining a genotype, the method comprising:

providing a reference graph comprising nodes connected by edges into a plurality of paths, the plurality of paths including a first path representing a first haplotype A and a second path representing a second haplotype B;

identifying one or more genotypes corresponding to either or both of the first haplotype A and the second haplotype B;

assigning, based on genetic information from the organism, scores to each of the identified genotypes; and

identifying a genotype having a highest score in said assigning step, thereby providing a genotype.

2. The method of claim 1, wherein the genetic information comprises a plurality of sequence reads, and wherein assigning scores comprises:

mapping the plurality of sequence reads to the reference graph; and

scoring each genotype based on properties of the mapped sequence reads.

3. The method of claim 2, wherein the properties of the mapped reads are selected from the group consisting of position, count, and quality.

4. The method of claim 1, further comprising enumerating a plurality of genotypes based on a plurality of haplotypes in the reference graph, assigning scores to each genotype, and identifying a most likely sequence of genotypes for the organism using dynamic programming.

5. The method of claim 4, wherein the dynamic programming comprises using Viterbi decoding.

6. The method of claim 2, wherein the plurality of sequence reads represent at least a majority of a genome of an organism.

7. The method of claim 2, wherein the identified genotypes include a first genotype AA, a second genotype AB, and a third genotype BB.

8. The method of claim 7, further comprising:

representing the first genotype AA, the second genotype AB, and the third genotype BB using a traversal graph comprising nodes connected by edges into a plurality of paths, the plurality of paths including a first traversal path representing the first genotype AA, a second traversal path representing the second genotype AB, and a third traversal path representing the third genotype BB; and

determining weights for the first traversal path, the second traversal path, and the third traversal path based on properties of the sequence reads that map to the reference graph.

9. The method of claim 8, further comprising enumerating a plurality of genotypes from the reference graph, representing the plurality of genotypes as paths in the traversal graph, and identifying the most likely sequence of genotypes by determining a most probable path through the traversal graph.

10. The method of claim 9, wherein identifying the most likely sequence of genotypes by determining a most probable path through the traversal graph comprises using dynamic programming.

11. The method of claim 10, wherein using dynamic programming comprises using a Dijkstra operation to find a least-cost path.

12. The method of claim 1, wherein A represents an allele of a gene known to be dominant and B represents an allele of the gene known to be recessive.

13. The method of claim 12, wherein the organism is a patient, the method further comprising providing a report for the patient that reports the identified one of the first genotype AA, the second genotype AB, and the third genotype BB.

14. A system for determining a genotype, the system comprising a processor coupled to a tangible memory subsystem having stored therein:

a reference graph comprising nodes connected by edges into a plurality of paths, the plurality of paths including a first path representing a first haplotype A and a second path representing a second haplotype B; and

instructions that when executed by the processor cause the system to;

identify one or more genotypes corresponding to either or both of the first haplotype A and the second haplotype B;

assign—

based on genetic information from an organism—

scores to each of the identified genotypes; and

identify a genotype having a highest score in said assigning step, thereby providing a genotype.

15. The system of claim 14, wherein the identified genotypes include a first genotype AA, a second genotype AB, and a third genotype BB, and further wherein the genetic information comprises a plurality of sequence reads, and wherein the system assigns the scores by:

mapping the plurality of sequence reads to the reference graph; and

scoring each genotype based on properties of the mapped sequence reads.

16. The system of claim 15, wherein the instructions are further operable to:

represent the first genotype AA, the second genotype AB, and the third genotype BB using a traversal graph comprising nodes connected by edges into a plurality of paths, the plurality of paths including a first traversal path representing the first genotype AA, a second traversal path representing the second genotype AB, and a third traversal path representing the third genotype BB; and

determine weights for the first traversal path, the second traversal path, and the third traversal path based on numbers of the sequence reads that map to the traversal graph.

17. The system of claim 16, wherein the instructions are further operable to:

enumerate a plurality of genotypes from the reference graph;

represent the plurality of genotypes as paths in the traversal graph; and

identify the most likely sequence of genotypes by determining a most probable path through the traversal graph.

18. The system of claim 17, wherein identifying the most likely sequence of genotypes by determining a most probable path through the traversal graph comprises using dynamic programming.

19. The system of claim 18, wherein using dynamic programming comprises using a Dijkstra operation to find a least-cost path.

20. The system of claim 15, wherein the organism is a patient and the system is operable to provide a report for the patient that gives the identified one of the first genotype AA, the second genotype AB, and the third genotype BB.