Binary integer programming for Multiple Sequence Alignment

Abstract

Molecular biology advances in the past few decades have contributed to the rapid increase in genome sequencing of various organisms; sequence alignment is usually considered as the first step in understanding the molecular function of a sequence. An optimal alignment adjusts two or more sequences in a way that it could compare the maximum number of identical or similar residues. The two sequence alignments types are: Pairwise Sequence Alignment (PSA) and Multiple Sequence Alignment (MSA). While dynamic programming (DP) technique is used in PSA to provide the optimal method, it will lead to more complexity if used in MSA. So, the MSA mainly uses heuristic and approximation methods. This paper presents a mathematical model for MSA that can be used as a basis for optimal solution in different ways. In order to obtain the results, the model is implemented using Genetic Algorithm method on the web.