Systems and methods for analyzing viral nucleic acids
First Claim
1. A method for analyzing a virus, the method comprising using at least one hardware processor connected to a tangible memory subsystem to perform:
- obtaining a plurality of sequence reads from a sample containing viral nucleic acid;
creating, in the tangible memory subsystem, a viral DNA reference graph representing a plurality of known viral sequences, the viral DNA reference graph comprising a directed acyclic graph (DAG) comprising a plurality of vertices stored as objects in the tangible memory subsystem, wherein sequence strings of the known viral sequences that match each other when aligned are each represented by a single object and sequence strings that vary are represented as alternate objects, wherein at least one sequence string comprises a plurality of symbols, and wherein each object is stored in the tangible memory subsystem as a sequence string and a list of one or more pointers to adjacent objects, wherein each pointer identifies a physical location in the tangible memory subsystem at which an adjacent object is stored, such that the objects are linked to represent each of the known viral sequences as a path through the viral DNA reference graph;
aligning the sequence reads to paths through the viral DNA reference graph, wherein the aligning comprises calculating match scores between a sequence read and a sequence string associated with each vertex, and looking backwards at each vertex to predecessor vertices if and only if a symbol comprises the first symbol of the sequence string associated with its vertex to select a path with an optimal score;
retrieving, based on the aligned sequence reads to paths through the viral DNA reference graph, an identity of a virus for the one of the plurality of known viral sequences; and
providing a report that includes the identity of the virus.
12 Assignments
0 Petitions
Accused Products
Abstract
The invention provides systems and methods for analyzing viruses by representing viral genetic diversity with a directed acyclic graph (DAG), which allows genetic sequencing technology to detect rare variations and represent otherwise difficult-to-document diversity within a sample. Additionally, a host-specific sequence DAG can be used to effectively segregate viral nucleic acid sequence reads from host sequence reads when a sample from a host is subject to sequencing. Known viral genomes can be represented using a viral reference DAG and the viral sequence reads from the sample can be compared to viral DAG to identify viral species or strains from which the reads were derived. Where the viral sequence reads indicate great genetic diversity in the virus that was infecting the host, those reads can be assembled into a DAG that itself properly represents that diversity.
162 Citations
20 Claims
-
1. A method for analyzing a virus, the method comprising using at least one hardware processor connected to a tangible memory subsystem to perform:
-
obtaining a plurality of sequence reads from a sample containing viral nucleic acid; creating, in the tangible memory subsystem, a viral DNA reference graph representing a plurality of known viral sequences, the viral DNA reference graph comprising a directed acyclic graph (DAG) comprising a plurality of vertices stored as objects in the tangible memory subsystem, wherein sequence strings of the known viral sequences that match each other when aligned are each represented by a single object and sequence strings that vary are represented as alternate objects, wherein at least one sequence string comprises a plurality of symbols, and wherein each object is stored in the tangible memory subsystem as a sequence string and a list of one or more pointers to adjacent objects, wherein each pointer identifies a physical location in the tangible memory subsystem at which an adjacent object is stored, such that the objects are linked to represent each of the known viral sequences as a path through the viral DNA reference graph; aligning the sequence reads to paths through the viral DNA reference graph, wherein the aligning comprises calculating match scores between a sequence read and a sequence string associated with each vertex, and looking backwards at each vertex to predecessor vertices if and only if a symbol comprises the first symbol of the sequence string associated with its vertex to select a path with an optimal score; retrieving, based on the aligned sequence reads to paths through the viral DNA reference graph, an identity of a virus for the one of the plurality of known viral sequences; and providing a report that includes the identity of the virus. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15)
-
-
16. A system for analyzing a virus, the system comprising a processor coupled to a tangible memory subsystem, wherein the tangible memory subsystem contains instructions that when executed by the processor cause the system to perform:
-
obtaining a plurality of sequence reads from a sample containing viral nucleic acid; creating, in the tangible memory subsystem, a viral DNA reference graph representing a plurality of known viral sequences, the viral DNA reference graph comprising a directed acyclic graph (DAG) comprising a plurality of vertices stored as objects in the tangible memory subsystem, wherein sequence strings of the known viral sequences that match each other when aligned are each represented by a single object and sequence strings that vary are represented as alternate objects, and wherein each object is stored in the tangible memory subsystem as a sequence string and a list of one or more pointers to adjacent objects, wherein each pointer identifies a physical location in the tangible memory subsystem at which an adjacent object is stored, such that the objects are linked to represent each of the known viral sequences as a path through the viral DNA reference graph; aligning the sequence reads to paths through the viral DNA reference graph, wherein the aligning comprises calculating match scores between a sequence read and a sequence string associated with each vertex, and looking backwards at each vertex to predecessor vertices if and only if a symbol comprises the first symbol of the sequence string associated with its vertex to select a path with an optimal score; retrieving, based on the aligned sequence reads to paths through the viral DNA reference graph, an identity of a virus for each of the plurality of sequences; and providing, via an input/output device coupled to the processor, a report that includes the retrieved identities. - View Dependent Claims (17, 18, 19, 20)
-
Specification