Systems, methods, and apparatuses for sequence alignment
AssigneeKoninklijke Philips N.V.
InventorSitharthan Kamalakaran
Life of this patent
Estimating the term…
Abstract
Systems, methods, and apparatuses are disclosed for reducing the computational time of assigning a species to an infection isolate. A method for dividing a search index into one or more sub-indices based on a phylogenetic tree of reference sequences is disclosed. A method for dividing reads into test sets and aligning to sub-indices for assigning a species to an infection isolate is disclosed. A system for aligning sequence reads to a database of reference sequences using sub-indices is disclosed.
Claims22
(canceled)
(canceled)
The method of claim 8, wherein the index comprises a hash table.
The method of claim 8, wherein the index comprises a sorted dictionary.
The method of claim 8, wherein the phylogenetic tree is generated by a neighbor joining method.
(canceled)
(canceled)
A method of assigning a species to a plurality of sequence reads from an organism, the method comprising:
- receiving the plurality of sequence reads;
- selecting a test set of the plurality of sequence reads, wherein the test set includes selected ones of the plurality of sequence reads;
- selecting a plurality of sub-indices of an index, wherein the index points to all sequences of a set of sequences corresponding to a plurality of species, wherein the sub-indices point to selected sequences of the set of sequences, wherein each of the sub-indices corresponds to sectors of a phylogenetic tree of the set of sequences, wherein the phylogentic tree is based on evolutionary distances between each of the sequences of the set of sequences;
- aligning the test set to the plurality of sub-indices, wherein the aligning is performed in parallel by one or more processing units;
- identifying, with the one or more processing units, a certain sub-index of the plurality of sub-indices, wherein the certain sub-index includes sequences that have a highest alignment to the test set, based on said aligning the test set to the plurality of sub-indices;
- aligning, with the one or more processing units, the plurality of sequence reads to the certain sub-index;
- and
- assigning the species to the plurality of sequence reads based on said aligning the plurality of sequence reads to the certain sub-index, wherein the species assigned is based on a sequence of the certain sub-index that had a highest alignment to the plurality of sequence reads.
(canceled)
(canceled)
(canceled)
A system for determining a species of an infection isolate, the system comprising:
- a processing unit;
- a memory accessible to the processing unit;
- a database accessible to the processing unit;
- and
- a display coupled to the processing unit;
- wherein the processing unit is configured to:
- align a plurality of sequence reads of the infection isolate stored in the memory to at least one sub-index of an index stored in the database to determine a species of the infection isolate, wherein the index points to sequences of a set of reference sequences corresponding to a plurality of species, wherein the sub-index points to selected sequences of the set of sequences, wherein the sub-index corresponds to a sector of a phylogenetic tree of the set of reference sequences, wherein the phylogenetic tree is based on evolutionary distances between each of the sequences of the set of sequences;
- wherein the species is determined based on a sequence of the set of reference sequences having a highest alignment to the plurality of sequence reads;
- and
- provide to the display a determination of the species of the infection isolate.
Dependencies are inferred from the claim text.