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 Liu¹

Ling Chen^2,3,*

Juan Chen²

¹Institute of Information Science and Technology
Nanjing University of Aeronautics and Astronautics
Nanjing, 2 3, China

²Department of Computer Science
Yangzhou University
Yangzhou, 22 , China

³State 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