SYSTEMS AND METHODS FOR ANALYZING SEQUENCE DATA

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

representing a plurality of nucleic acids as a reference directed acyclic graph (DAG); obtaining a second DAG representing a second plurality of nucleic acids; and determining an alignment between the second DAG and the reference 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 a processor coupled to a 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 . A method of identifying chromosomal structural variants, the method comprising:

obtaining a plurality of paired-end reads from a nucleic acid sample, each comprising an upstream pair member and a downstream pair member and characterized by an insert length approximating a number of nucleotides spanning a distance from an upstream end of the upstream pair member to a downstream end of the downstream pair member;

mapping the upstream pair member of each of the plurality of paired-end reads to a reference;

finding a subset of the plurality of paired-end reads for which the upstream pair members map to the reference within a window of some pre-determined size; and

for the subset of the plurality of paired-end reads, assembling the downstream pair members into a directed acyclic graph (DAG), wherein the DAG represents one or more chromosomal structural variants within the sample.

19 . A method of identifying haplotypes, the method comprising:

obtaining a plurality of nucleic acid sequence reads from a number k of diploid genomes; assembling the plurality of sequence reads into a directed acyclic graph (DAG)

representing optimally-scoring alignments among the sequence reads;

determining support for each of a plurality of paths through the DAG according to a number of reads consistent with a location in that path that is consistent with fewer reads than any other location in that path; and

identifying a number of the paths meeting a pre-determined support criteria as describing relevant haplotypes.

20 . The method of claim 19 , wherein the pre-determined support criteria includes: identifying a number n of paths for which the support meets a constant; and identifying the min(n, k) best-supported of the paths as the relevant haplotypes.