Solving the Multiple Sequence Alignment Problem with Metaheuristics

What is it about?

In the bioinformatics realm, multiple sequence alignment (MSA) is an difficult to solve problem. It may refer to the process or the outcome of sequence alignment of three or more biological sequences, tipically protein, DNA, or RNA. In several cases, the input set of query sequences are considered as having an evolutionary relationship to share a linkage and descendeding from a common ancestor. The resulting MSA allows inferring sequence homology and phylogenetic analysis can help evaluate the sequences' shared evolutionary origins. Visual depictions of alignments illustrate mutations such as point mutations (single amino acid or nucleotide modifications). Mutations show up as differing characters in a single alignment column. Insertion or deletion mutations (indels or gaps) look like hyphens in one or more sequences in the alignment. Frequently, MSA assesses sequence conservation of protein domains, tertiary and secondary structures, including individual amino acids or nucleotides. Nature-inspired methodologies configure potent tools to outsmart conventional optimization to encounter an approximate solution for MSA.

Featured Image

Photo by National Cancer Institute on Unsplash

Photo by National Cancer Institute on Unsplash

Why is it important?

MSA analyses present difficulties and intractability issues to be solved. Manual sequences' processing is not feasible given their biologically-relevant length. MSAs need more sophisticated methods than pairwise alignment at the cost of increased computational complexity. Most MSA programs utilize heuristics rather than global optimization because identifying the optimal alignment between more than a few sequences of moderate length is way too computationally expensive. However, heuristic methods generally fail to offer a high-quality solution.

Perspectives