Information Technology Journal1812-56381812-5646Asian Network for Scientific Information10.3923/itj.2010.274.281XiangXuyu ZhangDafan QinJiaohua FuYuanyuan 2201092Multiple Sequence Alignment (MSA), known as NP-complete
problem, is among the most important and challenging tasks in computational
biology. For multiple sequence alignment, it is difficult to solve this
type of problems directly and always results in exponential complexity.
In order to effectively solve the MSA problem, in this study, we present
a novel algorithm of ant colony with genetic algorithm (ACG) based on
the planar graph representation for MSA. Firstly, the planar graph is
described a representation for multiple sequences that took every possible
aligning result into account by defining the representation of gap insertion,
the value of heuristic information in every optional path and scoring
rule for the processes of MSA. Secondly, we use an ant colony with genetic
algorithm to find the better path that denotes a better aligning result
for multidimensional graph. Experimental results show that ACG could bring
about a rise in the quality of MSA when compared with standard Clustal
algorithm.]]>Notredame, C., E.A. Brien and D.G. Higgins,19972545704580Zhang, C. and A.K.C. Wong,199713565581Feng, D.F., M.S. Johnson and R.F. Doolittle,198521112125Davis, L.,1981Burke, E.K. and A.J. Smith,200015122128Fogel, D.B.,19945314Chellapilla, K. and G.B. Fogel,19991999pp: 445452Gusfield, D.,1997Pages: 534Pages: 534Carrillo, H. and D. Lipman,19884810731082Notredame, C. and D.G. Higgins,19962415151524Wang, L. and T. Jiang,19941337348Jiao, L. and L. Wang,200030552561Merz, P. and B. Freisleben,20004337352Sankoff, D.,19726946Wallace, I.M., G. Blackshields and D.G. Higgins,200515261266Chen, W.B.L., W. Zhu and X. Xiang,20093020312038Lee, Z.J., S.F. Su and C.Y. Lee,200333113121Lee, Z.J., S.F. Su and C.Y. Lee,200325287295Lee, Z.J., S.F. Su, C.C. Chuang and K.H. Liu,200885578