Aligning Multiple Protein Sequences by Hybrid Clonal Selection Algorithm with Insert-Remove-Gaps and BlockShuffling Operators - Artificial Immune Systems - page 332

The values used in table3 are drawn from data reported in [15]. Hybrid CSA
obtains comparable values of SP score on Ref 1, Ref2 and Ref 5 — despite the
fact that the value obtained on Reference 3 is the fourth best value. This table
also shows that future effort should focus on improving the CS metric.

6 Conclusions and Future Works

Experimental results of benchmark BaliBASE v.1.0 show that the proposed algo-
rithm is superior to PRRP, ClustalX, SAGA, DIALIGN, PIMA, MULTIALIGN
and PILEUP8. Whilst on BaliBASE v.2.0 the algorithm shows interesting re-
sults in terms of SP score with respect to established and leading methods, e.g.
ClustalW, T-Coffee, MUSCLE, PRALINE, ProbCons and Spem.
A strong point of the IA is the ability of generating more than a single align-
ment for every MSA instance. This behaviour is due to the stochastic nature
of the algorithm and the populations evolved during the convergence process.
Another advantage of the aligner is that the alignment process is not affected by
the presence of distant sequences in the starting protein set. As shown by the
experimental results, the scoring function used by the IA produces high SP val-
ues and low CS scores, therefore future work will first focus on the improvement
of the CS score values using the T-Coffee scoring function. The second step will
be the more accurate tuning of the parameters and the operators in order to
improve the convergence speed.

Acknowledgments

This work was supported by the National Research Laboratory Grant (2005-
01450) from the Ministry of Science and Technology. D.L. and M.P. would like
to thank CHUNG Moon Soul Center for BioInformation and BioElectronics for
providing research and computing facilities.

References

1. Eidhammer I., Jonassen I., Taylor W. R.; “ Protein Bioinformatics ,” Chichester,
West Sussex, UK, Wiley, (2004)
2. Durbin R., Eddy S., Krogh A., Mitchison G.; “ Biological sequence analysis ”, Cam-
bridge, UK, Cambridge University Press (2004)
3. Thompson J. D., Plewniak F., Ripp R., Thierry J.C., Poch O.; “Towards a Reliable
Objective Function for Multiple Sequence Alignments”, in J. Mol. Biol., vol. 301,
pp. 937-951 (2001)
4. Altschul S. F., Lipman D. J.; “ Trees stars and multiple biological sequence align-
ment ,” in SIAM Journal on Applied Mathematics, vol. 49, pp. 197-209, (1989).
5. Altschul S. F., Carroll R. J., Lipman D. J.; “ Weights for data related by a tree ,”
in Journal on Molecular Biology, vol. 207, pp. 647-653, (1989).
6. Bonizzoni P., Della Vedova G.; ” The Complexity of Multiple Sequence Alignment
with SP-score that is a Metric ,” in Theoretical Computer Science, vol. 259 (1), pp.
63-79 (2001).