Multiple Sequence Alignment (MSA) is a fundamental prob-lem in computational biology that is used to understand theevolutionary history of protein, DNA, or RNA sequences. Anoptimal alignment for two sequences can efficiently be foundusing dynamic programming, but computing optimal align-ments for more sequences continues to be a hard problem. Acommon method to solve MSA problems is A∗ search with admissible heuristics, computed from subsets of the input se-quences. In this paper, we consider MSA from the perspectiveof cost partitioning and relate the existing heuristics for MSAto uniform cost partitioning and post-hoc optimization, twowell-known techniques from the automated planning litera-ture. We show that the MSA heuristics are bounded by uni-form cost partitioning and that post-hoc optimization yieldsstrictly dominating heuristics. For a common benchmark setof protein sequences and a set of DNA sequences, we showthat the theoretical dominance relations between the heuris-tics carry over to practical instances