US 2019/0164320 A1 · METHODS FOR THE GRAPHICAL REPRESENTATION OF GENOMIC SEQUENCE DATA

Abstract

This disclosure provides a computational framework with related methods and systems to enhance the analysis of genomic information. More specifically, the disclosure provides for a graph-based reference genome framework, referred to as a GNOmics Graph Model (GGM), which represents genomic sequence information in edges with nodes representing transitions between edges. The disclosed GGM framework can represent all known polymorphisms simultaneously, including, SNPs, indels, and various rearrangements, in a data-efficient manner. The edges can contain weights to reflect the likelihood of a path within the GGM incorporating any particular edge. The disclosure also provides for systems and methods for using the GGM as a reference model for the rapid assembly of short sequence reads and analysis of DNA sequence variation with enhanced computational efficiency.

Claims20

Dependent claims

A computer-implemented method of aligning reads of a read sequence to a graph that represents a genome and polymorphisms therein, wherein the graph includes a plurality of edges, the method comprising:

selecting a set of bridges from the graph;
for each bridge in the set of bridges:
selecting a subset of a read pool, wherein reads in the subset contain at least a portion of the bridge;
and
for each read in the subset:
performing a local alignment for the read;
scoring the local alignment for the read to generate a read-bridge pair score;
and
inserting the read-bridge pair score into a score matrix;
using the score matrix to determine a best combination of placements of reads for the set of bridges;
and
placing the reads on the graph.

9 more elements

A system for performing read alignments to a graph that represents a genome and polymorphisms therein, the system comprising:

a graph data store configured to store information representing the graph, the information including a plurality of edge records;
at least one bridge computing device configured to:
receive a read pool;
select a set of bridges from the edge records stored in the graph data store;
for each bridge in the set of bridges:
select a subset of the read pool, wherein reads in the subset contain at least a portion of the bridge;
and
transmit reads from the subset of the read pool and the bridge to an alignment computing device;
a plurality of alignment computing devices each configured to:
receive one or more reads and a bridge with which the reads are associated;
perform a local alignment for each of the one or more reads;
score the local alignment for each of the one or more reads to generate a read-bridge pair score for each of the one or more reads;
and
transmit the read-bridge pair scores to a matrix processing computing device;
and
at least one matrix processing computing device configured to:
receive read-bridge pair scores from the plurality of alignment computing devices;
insert the read-bridge pair scores into a score matrix;
use the score matrix to determine a best combination of placements of reads for the set of bridges;
and
place the reads on the graph.

18 more elements

Dependencies are inferred from the claim text.

Methods for the graphical representation of genomic sequence data

Life of this patent

Methods for the graphical representation of genomic sequence data

Life of this patent

Abstract

Claims20