New Zealand Journal of Agricultural Research abstracts
An efficient algorithm for multiple sequence alignment based on ant
colony optimisation and divide-and-conquer method
Wei Liu1
Ling Chen2,3,*
Juan Chen2
1Institute of Information Science and Technology
Nanjing University of Aeronautics and Astronautics
Nanjing, 2 3, China
2Department of Computer Science
Yangzhou University
Yangzhou, 22 , China
3State Key Laboratory of Novel Software Technology
Nanjing University
Nanjing, 2 3, China
*Author for correspondence: lchen@yzcn.net
Abstract Obtaining an accurate multiple
alignment of protein
sequences is a difficult computational problem for which many heuristic
techniques sacrifice optimality to achieve reasonable running time. The
algorithm in this paper solves the multiple sequence alignment in three
steps. Firstly, a divide-and-conquer strategy based on the genetic
algorithm is used to divide the set of sequences into several
subsections vertically. Secondly, a multiple sequence alignment
approach based on the ant colony algorithm is used for sequences of
each subsection. Finally, the alignment of original sequences can be
obtained by assembling the result of each subsection. The local
optimality of ant colony algorithm is prevented by combining global
updating and local updating the pheromone and by adjusting the
parameters adaptively. The divide-and-conquer technique helps to
improve the quality of solution greatly and to reduce the running time.
It has been shown experimentally that the algorithm is efficient for
multiple sequence alignment problem.
Keywords ant colony optimisation; bioinformatics;
divide-and-conquer; genetic algorithm; multiple sequence alignment
A07070; Online publication date 17 December 2007; Received and
accepted 10 August 2007
New Zealand Journal of Agricultural Research, 2007, Vol. 50:
617–626
0028–8233/07/5005–0617 © The Royal Society of New Zealand 2007
PDF file of entire paper: Print-quality
(1227K) | screen-quality (1007K)
This year's abstracts |
Journal home page |
All abstracts |
Publishing home page
