Far East Journal of Experimental and Theoretical Artificial Intelligence
Volume 1, Issue 2, Pages 137 - 150
(May 2008)
|
|
INCORPORATING RANDOM PAIRWISE DYNAMIC PROGRAMMING WITH PARTICLE SWARM OPTIMIZATION IN SOLVING MULTIPLE SEQUENCE ALIGNMENT
Wang-Sheng Juang (Taiwan) and Shun-Feng Su (Taiwan)
|
Abstract:
While solving Multiple Sequence Alignment (MSA) problems, Dynamic Programming (DP) is a commonly-used approach. It is simple and effective. However, when the number of sequences is large, multiple dimensional DP often suffers from large storage and computational complexities. Traditionally, progressive pairwise DP is employed for MSA. It can be expected that such an approach also suffers from local optimal problems. In our previous work, a hybrid algorithm by combining the pairwise DP with the particle swarm optimization (PSO) techniques to overcome the above drawbacks is proposed. The experimental results show promising performance of that algorithm. In this paper, we further propose to consider a random sequence order in aligning pairwise DP progressively. Again, the PSO is employed to avoid the result of alignment being trapped into local optima. From our experiments, it can be found that the proposed algorithm indeed has excellent performance. |
| Keywords and phrases: multiple sequence alignment, dynamic programming, particle swarm optimization. |
| Communicated by K. K. Azad |
| Number of Downloads: 142 | Number of Views: 485 |
|
