I. INTRODUCTION
Sequence alignment has a long history in molecular biology and genetics, dating back to the first decoding of protein sequences in the 1960s. A pairwise alignment of two proteins identifies subsequences of amino acids that are position-wise similar, respecting the order in which they occur in the two proteins. The original goal of alignment was to uncover the evolutionary relationship between two proteins: positions that match represent the sequence of a common ancestor, and positions that differ represent mutations that occurred in one or both proteins since the divergence of their most recent common ancestor.