Table of Contents 1Introduction1.1Overview 2A history of pairwise alignment 3Problem statement 4Variations on pairwise alignment4.1Alignment types 4.2Cost Models 4.3Minimizing Cost versus Maximizing Score 5The classic quadratic DP algorithms 6Linear Memory using Divide and Conquer 7Dijkstra’s algorithm and A* 8Computational volumes and band doubling 9Diagonal transition 10Subquadratic methods and lower bounds 11Parallelism 12LCS and Contours 13Some tools 14Summary 15TODO15.1A*PA2Summary/ove...
