Multiple sequence alignment (MSA) is a sequence alignment of three or more biological sequences, which are assumed to have an evolutionary relationship. Because three or more sequences of biologically relevant length can be difficult and are almost always time-consuming to align by hand, computational algorithm are used to produce and analyze the alignments. Computational algorithm can be constructed by transforming multiple sequence alignment problems into graph problems. The problem of finding anoptimal alignment turns into finding a gapped trace of a gapped extended alignment graph. However, this process is difficult to be done manually. Hence, we study the properties of a gapped trace and using these properties to build a general integer linear programming formulation for MSA problem.