An Introduction to Bioinformatics Algorithmswww.bioalgorithms.info Thus We can divide up the grid into blocks and run dynamic programming only on the corners of these blocks In order to speed up the mini-alignment calculations to under n 2, we create a lookup table of size n, which consists of all scores for all t-nucleotide pairs Running time goes from quadratic, O(n 2 ), to subquadratic: O(n 2 /logn)
{}