Method And System For A Reduced Computation Hidden Markov Model In Computational Biology Applications

A method for using a computation hidden markov model (HMM) used by a computational biology application, the method comprising:

• performing operations of an HMM pre-filter engine, the operations of the HMM pre-filter engine comprising:
• receiving, by the HMM pre-filter engine, a haplotype sequence;
• receiving, by the HMM pre-filter engine, a read sequence;
• defining, by the HMM pre-filter engine, an offset value of zero to be where a first base of the received read sequence overlaps a first base of the haplotype sequence;
• performing, by the HMM pre-filter engine, a correlation between the haplotype sequence and the read sequence, wherein performing the correlation comprises:
• for each of a plurality of different offset values:
• comparing, by the HMM pre-filter engine, the read sequence to the haplotype sequence;
• determining, by the HMM pre-filter engine, a maximum correlation offset value, wherein the maximum correlation offset value is indicative of a particular offset value of the plurality of offset values where the comparison of the read sequence to the haplotype sequence, by the HMM pre-filter engine, yielded a maximum number of bases of the read sequence that matched the haplotype sequence;
• defining, by the HMM pre-filter engine, a starting center point for a first row of an HMM matrix structure using the maximum correlation offset value;
• and
• generating, by the HMM pre-filter engine, a plurality of control parameters based on the correlation, wherein the plurality of control parameters includes data describing the starting center point for the first row of the HMM matrix structure;
• and
• performing operations of an HMM computation engine using a plurality of hardwired digital logic circuits in an integrated circuit, the operations of the HMM computation engine comprising:
• receiving, by the HMM computation engine, the plurality of control parameters, the read sequence and the haplotype sequence;
• selecting, by the HMM computation engine, a reduced number of cells of the HMM matrix structure using the received plurality of control parameters, wherein the reduced number of cells of the HMM matrix structure is less than all of the cells of the HMM matrix structure;
• and
• computing, by the HMM computation engine, an HMM metric by processing data within each cell of the reduced number of cells selected by the HMM computation engine.

A system for implementing a reduced computation hidden markov model (HMM) used by a computational biology application comprising:

• one or more processors;
• and
• one or more memory devices operatively coupled to the one or more processors to form a computing device, wherein the one or more memory devices store processor-executable instructions which, when executed on the one or more processors, cause the one or more processors to perform operations, the operations comprising:
• performing operations of an HMM pre-filter engine, the operations of the HMM pre-filter engine comprising:
• receiving, by the HMM pre-filter engine, a haplotype sequence;
• receiving, by the HMM pre-filter engine, a read sequence;
• performing, by the HMM pre-filter engine, a correlation between the haplotype sequence and the read sequence, wherein performing the correlation comprises:
• generating, by the HMM pre-filter engine, a correlation between the haplotype sequence and the read sequence using a Fourier transform;
• determining, by the HMM pre-filter engine and based on the correlation, one or more values, wherein each of the one or more determined values corresponds to at least one of an offset of a max match count value, a ratio of a max match count value to a read length, and a ratio of a max match count value to a second highest match count value;
• defining, by the HMM pre-filter engine, at least a portion of a first row of an HMM matrix structure and a cell width of the portion based on at least one of the offset of the max match count value, the ratio of the max match count value to the read length, and the ratio of the max match count value to the second highest match count value;
• and
• generating, by the HMM pre-filter engine, a plurality of control parameters based on the correlation, wherein the plurality of control parameters includes data describing the portion of the first row and the cell width of the portion;
• and
• performing operations of the HMM computation engine using a plurality of hardwired digital logic circuits in an integrated circuit, the operations of the HMM computation engine comprising:
• receiving, by the HMM computation engine, the plurality of control parameters, the read sequence and the haplotype sequence;
• selecting, by the HMM computation engine, a reduced number of cells of the HMM matrix structure using the received plurality of control parameters, wherein the reduced number of cells of the HMM matrix structure is less than all of the cells of the HMM matrix structure;
• and
• computing, by the HMM computation engine, an HMM metric by processing data within each cell of the reduced number of cells selected by the HMM computation engine.

A system for implementing a reduced computation hidden markov model (HMM) used by a computational biology application comprising:

• one or more processors;
• and
• one or more memory devices operatively coupled to the one or more processors to form a computing device, wherein the one or more memory devices store processor-executable instructions which, when executed on the one or more processors, cause the one or more processors to perform operations, the operations comprising:
• performing operations of the HMM pre-filter engine, the operations of the HMM pre-filter engine comprising:
• receiving, by the HMM pre-filter engine, a haplotype sequence;
• receiving, by the HMM pre-filter engine, a read sequence;
• defining, by the HMM pre-filter engine, an offset value of zero to be where a first base of the received read sequence overlaps a first base of the haplotype sequence;
• performing, by the HMM pre-filter engine, a correlation between the haplotype sequence and the read sequence, wherein performing the correlation comprises:
• for each of a plurality of different offset values:
• comparing, by the HMM pre-filter engine, the read sequence to the haplotype sequence;
• determining, by the HMM pre-filter engine, a maximum correlation offset value, wherein the maximum correlation offset value is indicative of a particular offset value of the plurality of offset values where the comparison of the read sequence to the haplotype sequence, by the HMM pre-filter engine, yielded a maximum number of bases of the read sequence that matched the haplotype sequence;
• defining, by the HMM pre-filter engine, a starting center point for a first row of an HMM matrix structure using the maximum correlation offset value;
• and
• generating, by the HMM pre-filter engine, a plurality of control parameters based on the correlation, wherein the plurality of control parameters includes data describing the starting center point for the first row of the HMM matrix structure;
• and
• performing operations of the HMM computation engine using a plurality of hardwired digital logic circuits in an integrated circuit, the operations of the HMM computation engine comprising:
• receiving, by the HMM computation engine, the plurality of control parameters generated by one of the HMM pre-filter engines, the read sequence and the haplotype sequence;
• selecting, by the HMM computation engine, a reduced number of cells of the HMM matrix structure using the received plurality of control parameters, wherein the reduced number of cells of the HMM matrix structure is less than all of the cells of the HMM matrix structure;
• and
• computing, by the HMM computation engine, an HMM metric by processing data within each cell of the reduced number of cells selected by the HMM computation engine.