Bacterial Foraging Optimization -Genetic Algorithm for Multiple Sequence Alignment with Multi-Objectives

Overview

Journal Sci Rep

Specialty Science

Date 2017 Aug 20

PMID 28821841

Citations 2

Authors

P Manikandan

D Ramyachitra

Affiliations

Soon will be listed here.

Abstract

This research work focus on the multiple sequence alignment, as developing an exact multiple sequence alignment for different protein sequences is a difficult computational task. In this research, a hybrid algorithm named Bacterial Foraging Optimization-Genetic Algorithm (BFO-GA) algorithm is aimed to improve the multi-objectives and carrying out measures of multiple sequence alignment. The proposed algorithm employs multi-objectives such as variable gap penalty minimization, maximization of similarity and non-gap percentage. The proposed BFO-GA algorithm is measured with various MSA methods such as T-Coffee, Clustal Omega, Muscle, K-Align, MAFFT, GA, ACO, ABC and PSO. The experiments were taken on four benchmark datasets such as BAliBASE 3.0, Prefab 4.0, SABmark 1.65 and Oxbench 1.3 databases and the outcomes prove that the proposed BFO-GA algorithm obtains better statistical significance results as compared with the other well-known methods. This research study also evaluates the practicability of the alignments of BFO-GA by applying the optimal sequence to predict the phylogenetic tree by using ClustalW2 Phylogeny tool and compare with the existing algorithms by using the Robinson-Foulds (RF) distance performance metric. Lastly, the statistical implication of the proposed algorithm is computed by using the Wilcoxon Matched-Pair Signed- Rank test and also it infers better results.

Citing Articles

An integrative machine learning framework for classifying SEER breast cancer.

Manikandan P, Durga U, Ponnuraja C Sci Rep. 2023; 13(1):5362.

PMID: 37005484 PMC: 10067827. DOI: 10.1038/s41598-023-32029-1.

A decision support system for multi-target disease diagnosis: A bioinformatics approach.

Emmanuel Ayo F, Awotunde J, Ogundokun R, Folorunso S, Adekunle A Heliyon. 2020; 6(3):e03657.

PMID: 32258494 PMC: 7113440. DOI: 10.1016/j.heliyon.2020.e03657.

References

Wallace I, OSullivan O, Higgins D, Notredame C . M-Coffee: combining multiple sequence alignment methods with T-Coffee. Nucleic Acids Res. 2006; 34(6):1692-9. PMC: 1410914. DOI: 10.1093/nar/gkl091. View

Taheri J, Zomaya A . RBT-GA: a novel metaheuristic for solving the Multiple Sequence Alignment problem. BMC Genomics. 2009; 10 Suppl 1:S10. PMC: 2709253. DOI: 10.1186/1471-2164-10-S1-S10. View

Notredame C, Higgins D, Heringa J . T-Coffee: A novel method for fast and accurate multiple sequence alignment. J Mol Biol. 2000; 302(1):205-17. DOI: 10.1006/jmbi.2000.4042. View

Lassmann T, Sonnhammer E . Kalign--an accurate and fast multiple sequence alignment algorithm. BMC Bioinformatics. 2005; 6:298. PMC: 1325270. DOI: 10.1186/1471-2105-6-298. View

Roshan U, Livesay D . Probalign: multiple sequence alignment using partition function posterior probabilities. Bioinformatics. 2006; 22(22):2715-21. DOI: 10.1093/bioinformatics/btl472. View

Lin Y, Rajan V, Moret B . A metric for phylogenetic trees based on matching. IEEE/ACM Trans Comput Biol Bioinform. 2011; 9(4):1014-22. DOI: 10.1109/TCBB.2011.157. View

Do C, Mahabhashyam M, Brudno M, Batzoglou S . ProbCons: Probabilistic consistency-based multiple sequence alignment. Genome Res. 2005; 15(2):330-40. PMC: 546535. DOI: 10.1101/gr.2821705. View

Papadopoulos J, Agarwala R . COBALT: constraint-based alignment tool for multiple protein sequences. Bioinformatics. 2007; 23(9):1073-9. DOI: 10.1093/bioinformatics/btm076. View

Morgenstern B, Frech K, Dress A, Werner T . DIALIGN: finding local similarities by multiple sequence alignment. Bioinformatics. 1998; 14(3):290-4. DOI: 10.1093/bioinformatics/14.3.290. View

10.

Gotoh O . Significant improvement in accuracy of multiple protein sequence alignments by iterative refinement as assessed by reference to structural alignments. J Mol Biol. 1996; 264(4):823-38. DOI: 10.1006/jmbi.1996.0679. View

11.

Phillips A . Homology assessment and molecular sequence alignment. J Biomed Inform. 2005; 39(1):18-33. DOI: 10.1016/j.jbi.2005.11.005. View

12.

Mount D . Using hidden Markov models to align multiple sequences. Cold Spring Harb Protoc. 2010; 2009(7):pdb.top41. DOI: 10.1101/pdb.top41. View

13.

Lawrence C, Altschul S, Boguski M, Liu J, Neuwald A, Wootton J . Detecting subtle sequence signals: a Gibbs sampling strategy for multiple alignment. Science. 1993; 262(5131):208-14. DOI: 10.1126/science.8211139. View

14.

Loytynoja A, Goldman N . An algorithm for progressive multiple alignment of sequences with insertions. Proc Natl Acad Sci U S A. 2005; 102(30):10557-62. PMC: 1180752. DOI: 10.1073/pnas.0409137102. View

15.

Edgar R . MUSCLE: multiple sequence alignment with high accuracy and high throughput. Nucleic Acids Res. 2004; 32(5):1792-7. PMC: 390337. DOI: 10.1093/nar/gkh340. View

16.

Nozaki Y, Bellgard M . Statistical evaluation and comparison of a pairwise alignment algorithm that a priori assigns the number of gaps rather than employing gap penalties. Bioinformatics. 2004; 21(8):1421-8. DOI: 10.1093/bioinformatics/bti198. View

17.

Sievers F, Higgins D . Clustal Omega, accurate alignment of very large numbers of sequences. Methods Mol Biol. 2013; 1079:105-16. DOI: 10.1007/978-1-62703-646-7_6. View

18.

Katoh K, Kuma K, Toh H, Miyata T . MAFFT version 5: improvement in accuracy of multiple sequence alignment. Nucleic Acids Res. 2005; 33(2):511-8. PMC: 548345. DOI: 10.1093/nar/gki198. View

19.

Thompson J, Koehl P, Ripp R, Poch O . BAliBASE 3.0: latest developments of the multiple sequence alignment benchmark. Proteins. 2005; 61(1):127-36. DOI: 10.1002/prot.20527. View

20.

Notredame C, Higgins D . SAGA: sequence alignment by genetic algorithm. Nucleic Acids Res. 1996; 24(8):1515-24. PMC: 145823. DOI: 10.1093/nar/24.8.1515. View