Efficiently calculating scores for chains of sequence alignments

摘要

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.