Systems and methods for adaptive local alignment for graph genomes

Inventors

Ghose, Kaushik • Lee, Wan-Ping

Assignees

Seven Bridges Genomics Inc

Interested in licensing this patent?

MTEC can help explore whether this patent might be available for licensing for your application.

Publication Number

US-11810648-B2

Patent

Publication Date

2023-11-07

Expiration Date


Abstract

Systems and methods for analyzing genomic information can include obtaining a sequence read including genetic information; identifying, within a graph representing a reference genome, a plurality of candidate mapping positions that relate to the genetic information, the graph comprising nodes representing genetic sequences and edges connecting pairs of nodes; determining, by means of a computer system, whether an alignment with the graph surrounding each of the plurality of candidate mapping positions is advanced or basic; and performing for each candidate mapping position, by means of the computer system, a local alignment based on whether the local alignment is advanced or basic. The advanced local alignment can include a first-local-alignment algorithm, and the basic local alignment includes a second-local-alignment algorithm. Based on the local alignments, the mapped position of the sequence read can be identified within the genome.

Core Innovation

The document describes graph-genome read mapping using a reference genome represented as a directed acyclic graph. A sequence read including genetic information is aligned to a portion of the reference genome graph that includes a candidate mapping position, and an alignment algorithm is selected from multiple alignment algorithms based on a measure of complexity of the first portion of the graph.

The complexity of the first portion of the graph is determined by a number of paths through the first portion of the graph or a number of nodes in the first portion of the graph. When the number of paths is greater than a threshold number of paths, or when the number of nodes is greater than a threshold number of nodes, a first alignment algorithm is selected; when the number of paths is less than or equal to the threshold number of paths, or when the number of nodes is less than or equal to the threshold number of nodes, a second alignment algorithm is selected.

The document further describes aligning the sequence read to the first portion of the graph using the selected alignment algorithm. It also describes using an advanced local alignment algorithm for more complex regions and a basic local alignment algorithm for less complex regions, where advanced local alignment can use a graph-aware, modified Smith-Waterman approach and basic local alignment can use pattern matching algorithms or a linear alignment algorithm.

In addition, the document describes generating candidate mapping positions from the global stage and refining by local alignment around each candidate, including optional selection between global and local strategies, storing a graph as adjacency lists with index-free adjacency via native pointers, and linearizing DAG subsections by depth-first search path enumeration to produce linear sequences for use with linear or pattern alignment tools.

Claims Coverage

The independent claims cover a method, a system, and processor-executable instructions for aligning a sequence read to a reference genome graph by selecting between two different alignment algorithms based on graph-portion complexity. The inventive selection mechanism is grounded in determining the number of paths and/or the number of nodes in a graph portion and comparing those measures to threshold values, followed by aligning the read using the selected algorithm.

Complexity-based alignment algorithm selection for graph-portion read alignment

Determining a number of paths through the first portion of the graph or a number of nodes in the first portion of the graph; selecting the first alignment algorithm when either the number of paths through the first portion of the graph is greater than a threshold number of paths or when the number of nodes is greater than a threshold number of nodes; and selecting the second alignment algorithm when either the number of paths through the first portion of the graph is less than or equal to the threshold number of paths or when the number of nodes is less than or equal to the threshold number of nodes.

Aligning a sequence read to a graph portion using the selected alignment algorithm

Aligning the sequence read to the first portion of the graph using the selected alignment algorithm after identifying the first portion of the graph including a first candidate mapping position.

Graph read alignment with repeated complexity-based algorithm selection for additional graph portions

Selecting the second alignment algorithm based on a second measure of complexity of the second portion of the graph after identifying a second portion of the graph including a second candidate mapping position, and aligning the sequence read to the second portion of the graph using the selected second alignment algorithm.

Processor-executable instructions for complexity-based graph-portion read alignment

Storing processor-executable instructions on a non-transitory computer readable storage medium that cause at least one processor to access data indicative of the sequence read including genetic information and the graph representing a reference genome and variation, identify the first portion including a first candidate mapping position, select the alignment algorithm based on determining a number of paths or a number of nodes and comparing to threshold numbers, and align the sequence read to the first portion using the selected alignment algorithm.

Across the independent claims, the core coverage is the same: identify a graph portion with a candidate mapping position, determine complexity by number of paths and/or number of nodes, select between two different alignment algorithms based on threshold comparisons, and align the sequence read to that graph portion using the selected alignment algorithm. The system claim additionally extends the process to a second graph portion, and the medium claim expresses the same functionality as processor-executable instructions.

Stated Advantages

Documented Applications

No documented applications found

JOIN OUR MAILING LIST

Stay Connected with MTEC

Keep up with active and upcoming solicitations, MTEC news and other valuable information.