System and method for sequence identification in reassembly variant calling
Inventors
Assignees
Interested in licensing this patent?
MTEC can help explore whether this patent might be available for licensing for your application.
Publication Number
US-12046325-B2
Publication Date
2024-07-23
Expiration Date
Abstract
In one embodiment, a method for identifying candidate sequences for genotyping a genomic sample comprises obtaining a plurality of sequence reads mapping to a genomic region of interest. The plurality of sequence reads are assembled into a directed acyclic graph (DAG) comprising a plurality of branch sites representing variation present in the set of sequence reads, each branch site comprising two or more branches. A path through the DAG comprises a set of successive branches over two or more branch sites and represents a possible candidate sequence of the genomic sample. One or more paths through the DAG are ranked by calculating scores for one or more branch sites, wherein the calculated score comprises a number of sequence reads that span multiple branch sites in a given path. At least one path is selected as a candidate sequence based at least in part on its rank.
Core Innovation
The invention provides a system and method for identifying variation in a genomic sample relative to a human reference genome. It accesses a set of sequence reads in an electronic format, aligns the set against the human reference genome to obtain an alignment mapping reads to respective regions of the human reference genome, and selects sequence reads that map to a genomic region of interest and contain variation relative to the genomic region of interest.
From the selected sequence reads, the invention generates at least one data structure embodying a directed acyclic graph (DAG) by assembling the DAG. In the DAG, nodes and edges represent relationships among nodes, and at least some nodes represent branch sites representing variation present in the plurality of sequence reads. A plurality of paths through the DAG represent a plurality of candidate sequences, and a first path comprising successive branches over two or more branch sites represents a first candidate sequence.
The invention selects a subset of the plurality of candidate sequences represented by the plurality of paths through the DAG, including the first candidate sequence. Selection involves determining a number of sequence reads that span successive branches over the two or more branch sites, and using multiple priority queue data structures including a first priority queue and a second priority queue to identify the first candidate sequence, where the first priority queue manages partial paths through the DAG and the second priority queue manages complete paths through the DAG. The variation is identified by aligning the selected subset of candidate sequences against the human reference genome and identifying at least one variant using the aligning results.
Claims Coverage
The partial content provides three independent claims: clm-00001 (system), clm-00007 (method), and clm-00013 (computer-readable storage medium with processor-executable instructions). Across these independent claims, the inventive features revolve around DAG-based candidate sequence representation and priority-queue-guided selection of candidate sequences based on read support spanning successive branch sites, followed by variant identification via aligning selected candidate sequences back to the human reference genome.
DAG-based candidate sequence representation from selected reads
Accessing sequence reads; aligning the reads against a human reference genome to map reads to regions; selecting sequence reads mapping to a genomic region of interest and containing variation; and generating at least one data structure embodying a directed acyclic graph (DAG) assembled from the selected reads, where branch sites representing variation are represented and a plurality of paths through the DAG represent a plurality of candidate sequences, including a first candidate sequence represented by a path comprising successive branches over two or more branch sites.
Read-span driven selection using partial-path and complete-path priority queues
Selecting a subset of candidate sequences represented by the plurality of paths through the DAG, including the first candidate sequence, by determining a number of sequence reads that span successive branches over the two or more branch sites and selecting the first candidate sequence using the number and multiple priority queue data structures including a first priority queue and a second priority queue, where the first priority queue manages partial paths through the DAG and the second priority queue manages complete paths through the DAG.
Variant identification by re-aligning selected candidate sequences to the reference
Identifying the variation in the genomic sample by identifying at least one variant using the selected subset of candidate sequences, where the identifying includes aligning the selected subset of candidate sequences against the human reference genome and identifying the at least one variant using results of the aligning.
Across clm-00001, clm-00007, and clm-00013, the claims consistently cover DAG-based candidate sequence representation, selection of candidate sequences using read-span counts and priority queue structures, and variant identification by aligning selected candidate sequences back to the human reference genome.
Stated Advantages
Computational efficiency improvements, including reduced runtime, versus a conventional independent-variant scoring approach.
Accuracy improvements, including improved precision/recall/F-score.
Reduced false negatives versus a conventional independent-variant scoring approach.
Documented Applications
Genotyping/variant identification in a genomic sample relative to a human reference genome using an assembly-graph (DAG)-based reassembly variant calling approach.
Interested in licensing this patent?