One of the dominant problems in computational molecular biology is
multiple sequence alignment (MSA) of DNA. Many methods have been
proposed to solve MSA problem such as dynamic programming and heuristic.
A method has been proposed by Althaus et al. to solve MSA problem which is
based on integer linear programming (ILP). The general ILP formulation of
the MSA is derived from the graph representation of the MSA problem.
Although we have the general ILP formulation of the MSA problem,
constructing the ILP model of an MSA that can be solved directly using an
ILP solver is not straightforward. We develop a MATLAB program that can
generate and solve the ILP model of an MSA problem. The method that is
used to solve the ILP model is branch-and-bound. The constructed program
can generate the ILP model of any given MSA problem but can only solve an
MSA problem of a small number of short DNA sequences. The result of the
program is the aligned sequences of the MSA problem.
S-Pudiahwai Anton Wibowo.pdf :: Unduh