Methods, circuits, systems, and articles of manufacture for searching a reference sequence for a target sequence within a specified distance
AssigneeUniversity of Virginia Patent Foundation
InventorsChunkun Bo, Kevin Skadron, Elaheh Sadredini, Vinh Dang
Life of this patent
Estimating the term…
Abstract
A method of operating a finite state machine circuit can be provided by determining if a target sequence of characters included in a string of reference characters occurs within a specified difference distance using states indicated by the finite state machine circuit to indicate a number of character mis-matches between the target sequence of characters and a respective sequence of characters within the string of reference characters.
Claims20
A method of operating a finite state machine on a system comprising a memory and at least one processor coupled to the memory and configured to perform the method, the method comprising:
- determining if an off-target site to a target nucleic acid sequence occurs within a reference nucleic acid sequence using states indicated by the finite state machine to indicate a number of nucleobase mismatches between the target nucleic acid sequence and a string within the reference nucleic acid sequence, wherein determining comprises:
- comparing, in a first state of the finite state machine, one nucleobase of the target nucleic acid sequence to a respective one nucleobase of the reference nucleic acid sequence;
- transitioning from the first state to a second state of the finite state machine responsive to a match between the one nucleobase of the target nucleic acid sequence and the respective one nucleobase of the reference nucleic acid sequence when in the first state;
- and
- transitioning from the first state to a third state of the finite state machine that is different from the second state, responsive to a mismatch between the one nucleobase of the target nucleic acid sequence and the respective one nucleobase of the reference nucleic acid sequence when in the first state,
- wherein an off-target nucleic acid sequence is determined to be included in the string within the reference nucleic acid sequence if the number of character mismatches has a value within a specified Hamming distance from the string within the reference nucleic acid sequence, and
- wherein the reference nucleic acid sequence comprises a chromosome or a genome.
A method for determining if an off-target site for a target nucleic acid sequence occurs within a reference nucleic acid sequence, the method comprising:
- operating a finite state machine on a system comprising a memory and at least one processor coupled to the memory and configured to perform the method using states indicated by the finite state machine to indicate a number of nucleobase mismatches between the target nucleic acid sequence and a string within the reference nucleic acid sequence, wherein determining comprises:
- comparing, in a first state of the finite state machine, one nucleobase of the target nucleic acid sequence to a respective one nucleobase of the reference nucleic acid sequence;
- transitioning from the first state to a second state of the finite state machine responsive to a match between the one nucleobase of the target nucleic acid sequence and the respective one nucleobase of the reference nucleic acid sequence when in the first state and maintaining a value of the number of nucleobase mismatches from the first state to the second state;
- and
- transitioning from the first state to a third state of the finite state machine that is different from the second state, responsive to a mismatch between the one nucleobase of the target nucleic acid sequence and the respective one nucleobase of the reference nucleic acid sequence when in the first state and increasing the value of the number of nucleobase mismatches from the first state to the third state,
- wherein a string within the reference nucleic acid sequence is determined to comprise an off-target site if the value of the number of nucleobase mismatches is within a specified Hamming distance from the target nucleic acid sequence,
- wherein a string within the reference nucleic acid sequence is determined to not comprise an off-target site if the value of the number of nucleobase mismatches is greater than the specified Hamming distance from the target nucleic acid sequence, and
- wherein the reference nucleic acid sequence comprises a chromosome or a genome.
Dependencies are inferred from the claim text.