Introduction Multiple sequence alignment (MSA) has numerous applications, including protein analysis, comparative genomics, functional prediction of sequences, and generation of phylogenetic trees [1]. Several strategies have been developed to conduct MSA. These computational strategies generally have three approaches: exact, progressive, and iterative. The exact approach is, in essence, a generalization of…