Apparatus for calculating scores for chains of sequence alignments
US8571809B2 · kind B2 · utility
Assignee
Inventor
Key dates
| Filing date | Sep 19, 2010 |
| Grant date | Oct 29, 2013 |
| Priority date | — |
| Expiry date | Sep 19, 2030 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG16B50/00
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
Each of a plurality of substantially co-linear alignments has a score. Each alignment may comprise a starting alignment that has been diagonally extended to meet a length requirement. Dynamic programming is performed in interalignment regions between the extended alignments to generate a corresponding set of interalignment scores. Alignment scores and interalignment scores are summed to generate a score for the entire chain of alignments. This process is repeated for multiple chains. Chains of alignments are ranked by chain score and are displayed to a user. In one embodiment, additional dynamic programming is performed at the head and tail of each chain to increase the chain score when possible. An integrated circuit that performs the method at high speed in hardware is disclosed. Techniques are disclosed that reduce the amount of interalignment dynamic programming. The method increases sensitivity and gives an order of magnitude speed improvement over NCBI-BLAST.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.