Alignment of multiple protein or DNA sequences is an important problem in Bioinformatics. Previous work has shown that the A* search algorithm can find optimal alignments for up to several sequences, and that a K-group generalization of A* can find approximate alignments for much larger numbers of sequences [6]. In this paper, we describe the first implementation of K-group A* that uses quasi-natural gap costs, the cost model used in practice by biologists. We also introduce a new method for computing gap-opening costs in profile alignment. Our results show that K-group A* can efficiently find optimal or close-to-optimal alignments for small groups of sequences, and, for large numbers of sequences, it can find higher-quality alignments than the widely-used CLUSTAL family of approximate alignment tools. This demonstrates the benefits of A* in aligning large numbers of sequences, as typically compared by biologists, and suggests that K-group A* could become a practical tool for multiple sequence alignment.