Systems and methods for analyzing sequence data

• US 9,817,944 B2
• Filed: 02/11/2014
• Issued: 11/14/2017
• Est. Priority Date: 02/11/2014
• Status: Active Grant

• Current Assignee: Seven Bridges Genomics, Inc.
• Original Assignee: Seven Bridges Genomics, Inc.
• Inventors: Kural, Deniz
• Primary Examiner(s): Lin, Jerry
• Application Number:
  US14/177,958
• Publication Number:
  US 20150227685A1
• Time in Patent Office: 1,372 Days
• Field of Search: 702 19
• CPC Class Codes: C12Q 1/6869 Methods for sequencing
• CPC Class Codes: C12Q 1/6883 for diseases caused by alterations of genetic material
• CPC Class Codes: C12Q 2521/301 Endonuclease
• CPC Class Codes: C12Q 2537/165 Mathematical modelling, e.g. logarithm, ratio
• CPC Class Codes: G16B 30/00 ICT specially adapted for sequence analysis involving nucleotides or amino acids
• CPC Class Codes: G16B 30/10 Sequence alignment; Homology search
• CPC Class Codes: G16B 30/20 Sequence assembly
• CPC Class Codes: G16B 45/00 ICT specially adapted for bioinformatics-related data visualisation, e.g. displaying of maps or networks

Abstract

The invention provides methods for comparing one set of genetic sequences to another without discarding any information within either set. A set of genetic sequences is represented using a directed acyclic graph (DAG) avoiding any unwarranted reduction to a linear data structure. The invention provides a way to align one sequence DAG to another to produce an alignment that can itself be stored as a DAG. DAG-to-DAG alignment is a natural choice wherever a set of genomic information consisting of more than one string needs to be compared to any non-linear reference. For example, a subpopulation DAG could be compared to a population DAG in order to compare the genetic features of that subpopulation to those of the population.

Claims

1. A method for genomic analysis, the method comprising:

representing a plurality of nucleic acids from a population of individuals as a reference directed acyclic graph (DAG) stored in a non-transitory memory, wherein the reference DAG includes nodes connected by edges in which at least one node includes a string of a plurality of nucleotide characters corresponding to a nucleotide sequence found within the plurality of nucleic acids;

obtaining a second DAG representing a second plurality of nucleic acids, the second plurality of nucleic acids comprising nucleic acids from one or more individuals;

determining, using a processor coupled to the non-transitory memory, an alignment between the second DAG and the reference DAG; and

creating, from the alignment, an aligned DAG comprising an aligned combination of the reference DAG and the second DAG.

2. The method of claim 1, wherein each DAG comprises at least two alternative sequences per position at multiple positions in that DAG.

3. The method of claim 2, wherein determining the alignment comprises:

scoring sequence overlaps between the reference DAG and the second DAG, wherein greater overlap results in a higher score; and

aligning portions of the second DAG to locations in the reference DAG such that the scores for the sequence overlaps are maximized.

4. The method of claim 1, wherein said alignment is an optimal alignment.

5. The method of claim 4, wherein said optimal alignment is a best-scoring DAG matrix alignment produced from a combination of said reference DAG and said second DAG.

6. The method of claim 5, wherein said best-scoring DAG alignment is determined by a mathematical construct representing the optimal path through a matrix of similarity scores in said combination.

7. The method of claim 1, wherein the second DAG is obtained from sequence reads from a sample from a subject.

8. The method of claim 7, wherein the reference DAG comprises a plurality of alleles associated with a disease.

9. The method of claim 7, wherein homozygous loci in the sample are represented using a single node in the second DAG and at least one heterozygous loci in the sample is represented using a plurality of different nodes in the second DAG.

10. The method of claim 1, wherein the steps are performed using a computer system comprising the processor coupled to the non-transitory memory having the reference DAG stored therein and further wherein the alignment is stored as a final DAG in the non-transitory memory.

11. The method of claim 1, wherein a DAG is stored as a computer file comprising:

nodes, each node comprising a character string and a label, and

edges, each edge comprising a pair of labels.

12. The method of claim 1, wherein a DAG is stored as a computer file comprising:

nodes, each node comprising one or more characters representing nucleotides, and

edges, each edge representing a connection between a pair of the nodes.

13. The method of claim 1, wherein at least one path through the reference DAG represents a sequence of a human chromosome.

14. The method of claim 13, wherein at least one path through the second DAG represents an alternative sequence of the human chromosome.

15. The method of claim 1, wherein the second DAG represents a transcriptome from an organism and the reference DAG represents one or more genomes from organisms of a same species as the organism.

16. The method of claim 1, wherein finding an optimally-scoring alignment between the second DAG and the reference DAG comprises:

calculating each of a plurality of values for entries in a matrix of similarities between the reference DAG and the second DAG based on a highest-valued neighboring entry and associating each calculated value with the highest-valued neighboring entry upon which the calculation of that calculated value was based; and

identifying a path through the matrix that originates at the entry with the highest calculated value and traces sequentially through each associated neighboring entry until a zero entry is met, wherein the identified path indicates the optimally-scoring alignment.

17. The method of claim 1, wherein:

the reference DAG comprises a plurality of binary alignment map (BAM) entries that have been mapped to a first genomic reference; and

the second DAG comprises a second plurality of BAM entries that have been mapped to a second genomic reference.

18. The method of claim 1, further comprising comparing genetic features between the population and the one or more individuals using the aligned DAG.

19. The method of claim 1, further comprising aligning a set of sequence reads to the aligned DAG.