+ Site Statistics
+ Search Articles
+ Subscribe to Site Feeds
EurekaMag Most Shared ContentMost Shared
EurekaMag PDF Full Text ContentPDF Full Text
+ PDF Full Text
Request PDF Full TextRequest PDF Full Text
+ Follow Us
Follow on FacebookFollow on Facebook
Follow on TwitterFollow on Twitter
Follow on LinkedInFollow on LinkedIn

+ Translate

RBT-GA: a novel metaheuristic for solving the Multiple Sequence Alignment problem

RBT-GA: a novel metaheuristic for solving the Multiple Sequence Alignment problem

Bmc Genomics 10 Suppl 1(): S10-S10

Multiple Sequence Alignment (MSA) has always been an active area of research in Bioinformatics. MSA is mainly focused on discovering biologically meaningful relationships among different sequences or proteins in order to investigate the underlying main characteristics/functions. This information is also used to generate phylogenetic trees. This paper presents a novel approach, namely RBT-GA, to solve the MSA problem using a hybrid solution methodology combining the Rubber Band Technique (RBT) and the Genetic Algorithm (GA) metaheuristic. RBT is inspired by the behavior of an elastic Rubber Band (RB) on a plate with several poles, which is analogues to locations in the input sequences that could potentially be biologically related. A GA attempts to mimic the evolutionary processes of life in order to locate optimal solutions in an often very complex landscape. RBT-GA is a population based optimization algorithm designed to find the optimal alignment for a set of input protein sequences. In this novel technique, each alignment answer is modeled as a chromosome consisting of several poles in the RBT framework. These poles resemble locations in the input sequences that are most likely to be correlated and/or biologically related. A GA-based optimization process improves these chromosomes gradually yielding a set of mostly optimal answers for the MSA problem. RBT-GA is tested with one of the well-known benchmarks suites (BALiBASE 2.0) in this area. The obtained results show that the superiority of the proposed technique even in the case of formidable sequences.

(PDF emailed within 0-6 h: $19.90)

Accession: 055333698

Download citation: RISBibTeXText

PMID: 19594869

DOI: 10.1186/1471-2164-10-S1-S10

Related references

RBT-L: a location based approach for solving the Multiple Sequence Alignment problem. International Journal of Bioinformatics Research and Applications 6(1): 37-57, 2010

A Parallel Multiobjective Metaheuristic for Multiple Sequence Alignment. Journal of Computational Biology, 2018

M2Align: parallel multiple sequence alignment with a multi-objective metaheuristic. Bioinformatics 33(19): 3011-3017, 2017

Multiple Sequence Alignment Based on a Suffix Tree and Center-Star Strategy: A Linear Method for Multiple Nucleotide Sequence Alignment on Spark Parallel Framework. Journal of Computational Biology, 2017

Combining partial order alignment and progressive multiple sequence alignment increases alignment speed and scalability to very large alignment problems. Bioinformatics 20(10): 1546-1556, 2004

Resolving the multiple sequence alignment problem using biogeography-based optimization with multiple populations. Journal of Bioinformatics and Computational Biology 13(4): 1550016-1550016, 2016

Sequence alignment of citrate synthase proteins using a multiple sequence alignment algorithm and multiple scoring matrices. Protein Engineering 2(8): 597-604, 1989

A min-cut algorithm for the consistency problem in multiple sequence alignment. Bioinformatics 26(8): 1015-1021, 2010

A Lagrangian relaxation approach for the multiple sequence alignment problem. Journal of Combinatorial Optimization 16(2): 127-154, 2008

A hybrid solver for protein multiple sequence alignment problem. Journal of Bioinformatics and Computational Biology: 1850015-1850015, 2018

Simulated annealing algorithm for the multiple sequence alignment problem: the approach of polymers in a random medium. Physical Review. E, Statistical, Nonlinear, and Soft Matter Physics 72(3 Pt 1): 031915-031915, 2005

A greedy method with clique finding for the maximum weight trace formulation of the multiple sequence alignment problem. Bulletin of the Okayama University of Science A Natural Science (43A): 57-65, 2007

Optimization of multiple-sequence alignment based on multiple-structure alignment. Proteins 62(1): 209-217, 2005

Using Problem-solving Therapy to Improve Problem-solving Orientation, Problem-solving Skills and Quality of Life in Older Hemodialysis Patients. Clinical Gerontologist: 1-14, 2017

Improvement in accuracy of multiple sequence alignment using novel group-to-group sequence alignment algorithm with piecewise linear gap cost. Bmc Bioinformatics 7: 524-524, 2006